Q1: Link the following and give me the memory map and symbol table of the executable.
2 bab 3 aba 4 1 cd 3 -1 6 I 1004 A 5678 R 2002 E 8002 R 2001 R 2003 0 2 bab 1 -1 cd 3 2 -1 6 R 8002 E 1000 E 1000 E 3000 R 1002 A 1010 1 cd 3 3 bab 2 -1 cd 1 -1 aba 4 -1 5 A 8000 E 1001 E 2000 I 2000 E 7004 0 2 cd 1 -1 aba 4 -1 7 A 8000 E 1001 A 2000 I 2000 E 7004 R 1002 R 1003
Answer: Let's first rearrange the input in a more readable format. That is, put newline at the end of every subsection although newline is of no real significance in the object code syntax.
2 bab 3 aba 4 1 cd 3 -1 6 I 1004 A 5678 R 2002 E 8002 R 2001 R 2003 0 2 bab 1 -1 cd 3 2 -1 6 R 8002 E 1000 E 1000 E 3000 R 1002 A 1010 1 cd 3 3 bab 2 -1 cd 1 -1 aba 4 -1 5 A 8000 E 1001 E 2000 I 2000 E 7004 0 2 cd 1 -1 aba 4 -1 7 A 8000 E 1001 A 2000 I 2000 E 7004 R 1002 R 1003
Now the answer (the executable machine code):
Symbol Table bab = 0+3 = 3 (bab is defined at 3 of 1st obj code -- offset 0 -- see below) aba = 0+4 = 4 (aba is defined at 4 of 1st obj code -- offset 0) cd = 12+3 = 15 (cd is defined at 3 of 3rd obj code -- offset 12) Memory Map +0 0: I 1004 1004 1: A 5678 5678 2: R 2002 2002+0 = 2002 3: bab: E 8002 ->cd 8015 4: aba: R 2001 2001+0 = 2001 5: R 2003 2003+0 = 2003 +6 0: R 8002 8002+6 = 8008 1: E 1000 ->bab 1003 2: E 1000 ->cd 1015 3: E 3000 ->cd 3015 4: R 1002 1002+6 = 1008 5: A 1010 1010 +12 0: A 8000 8000 1: E 1001 ->cd 1015 2: E 2000 ->bab 1003 3: cd: I 2000 2000 4: E 7004 ->aba 7004 +17 0: A 8000 8000 1: E 1001 ->cd 1015 2: A 2000 2000 3: I 2000 2000 4: E 7004 ->aba 7004 5: R 1002 1002+17 = 1019 6: R 1003 1003+17 = 1020
Q2: Consider the following snapshot of a system:
Alloc Max Avail. P1 0 0 0 2 4 5 6 2 1 3 2 2 P2 1 1 2 0 4 5 6 2 P3 1 1 2 0 2 4 3 2 P4 1 0 0 0 3 4 3 1
The system is in a safe state. Prove this by giving a sequence where everybody's max needs are satisfied. Do this by showing Available and Event columns.
Answer:
Need ------- P1 4 5 6 0 P2 3 4 4 2 P3 1 3 1 2 P4 2 4 3 1 Available Event (or we also call it Action) --------- ----- 1 3 2 2 0 0 1 0 <= minus Need(P3) = 1 3 1 2 gP3 (grant) 2 4 4 2 <= plus Max(P3) = 2 4 3 2 fP3 (finish) 0 0 1 1 <= minus Need(P4) = 2 4 3 1 gP4 3 4 4 2 <= plus Max(P4) = 3 4 3 1 fP4 0 0 0 0 <= minus Need(P2) = 3 4 4 2 gP2 4 5 6 2 <= plus Max(P2) = 4 5 6 2 fP2 0 0 0 2 <= minus Need(P1) = 4 5 6 0 gP1 4 5 6 4 <= plus Max(P1) = 4 5 6 2 fP1
Q3: Explain the difference between deadlock prevention, avoidance, and detection.
Answer:
Deadlock prevention: The system is designed such that one of the conditions required for a deadlock to happen can never happen by design. Hence, by design a deadlock can never happen so there is no need to check if a grant will cause deadlock (avoidance) or to check if we are in a deadlock (detection).
Deadlock avoidance: Deadlocks are not ruled out by design. Instead we take every step (ie. grant) carefully and check if there is any possibility a particular grant action may possibly result in a deadlock state. If yes, that step takes us to an unsafe state and hence we do not take that step. If we are currently in a safe state (and we should be if we are using deadlock avoidance), then we are guaranteed to have at least one possible next step that is safe.
Deadlock detection: is used in systems where prevention is impossible and avoidance is too compute-intensive and deadlocks are rare. In such cases, we say we will let a deadlock happen and that is OK as long as we are able to detect it. So, every once in a while we run a deadlock detection algorithm to see if there is deadlock formed by our system of processes.
Q4: Banker's algorithm is for
(a) deadlock
prevention
(b) deadlock avoidance
(c) deadlock detection
(d) deadlock
resolution
(e) resource locking
Answer: (b) deadlock avoidance: That is, at every step it makes sure it does not grant a request that can result us to get into a deadlock state. So deadlocks are possible by system design but we avoid them.
Q5: What are the shared variables needed to implement a FIFO between a writer process and a reader process without using semaphores?
Answer: readPointer: modified and read by the ReaderProcess, only read by the WriterProcess. writePointer: modified and read by the WriterProcess, only read by the ReaderProcess. full and empty flags are read and modified by one the two processes. So they do not qualify.
Q6: The only way to implement semaphores with user-level code in the lack of OS functions is an IPC server daemon. True or false?
Answer: True: Remember our discussion of Cygwin IPC daemon. We need to make certain sequences of code atomic (ie. serial or also called non-reentrant). That is we have to make sure timer interrupt does not hit in the middle of such code. The only ways of doing it is to have an instruction that does the job of all that code. Or to have an OS function (ie. system call) which disables the timer interrupt. When we lack all that and have to write user-level code (ie. we cannot disable the timer interrupt with user-level code), then the only option is to have a central authority through which all IPC transactions go through. That is synonymous with a daemon (ie. service).
Q7: In Windows let's say I just wrote and compiled a program in C:\myprogs\mynewprog\bindir directory. I want to be able to run this program from a cmd window while in other directories without typing the path to the executable. How do I do this?
Answer: When you type a command in a Windows or UNIX shell, the shell first checks to see if it is a built-in shell command. If not, it assumes it is an executable (ie. program) and searches for it in the directories listed in the environment variable named PATH. In Windows cmd shell, it also checks pwd in addition to what is in PATH. SO the answer is, we need to append C:\myprogs\mynewprog\bindir to variable PATH. And that is done by:
SET PATH=%PATH%;C:\myprogs\mynewprog\bindir
Q8: Consider the following snapshot of a system:
Alloc Max Avail. P1 0 0 0 2 4 5 6 2 1 3 2 2 P2 1 1 2 0 4 5 6 2 P3 1 1 2 0 2 4 3 2 P4 1 0 0 0 3 4 3 1
The system is in a safe state. Prove this by giving a sequence where everybody's max needs are satisfied. Do this by showing Available and Event columns.
Answer:
Need ------- P1 4 5 6 0 P2 3 4 4 2 P3 1 3 1 2 P4 2 4 3 1 Available Event (or we also call it Action) --------- ----- 1 3 2 2 0 0 1 0 <= minus Need(P3) = 1 3 1 2 gP3 (grant) 2 4 4 2 <= plus Max(P3) = 2 4 3 2 fP3 (finish) 0 0 1 1 <= minus Need(P4) = 2 4 3 1 gP4 3 4 4 2 <= plus Max(P4) = 3 4 3 1 fP4 0 0 0 0 <= minus Need(P2) = 3 4 4 2 gP2 4 5 6 2 <= plus Max(P2) = 4 5 6 2 fP2 0 0 0 2 <= minus Need(P1) = 4 5 6 0 gP1 4 5 6 4 <= plus Max(P1) = 4 5 6 4 fP1
Q9: Consider 5 dining philosophers in a circle -- numbered 4 through 0 from left to right. We will coordinate their eating with an arbiter. Each philosopher eats for 2 mins non-stop when he eats. The arbiter uses a mix of a queue scheme and a fixed-priority (FP) scheme. 0 has the highest priority and the rest are arbitrated based on a "queue". Philosopher 4 and 3 immediately get hungry after they finish eating. Philosopher 0 stays 3 minute not-hungry between each feast. 1 stays not-hungry for 2 mins. 2 stays not-hungry for 1 min. The arbiter checks and decides who will eat next in the middle of every minute. When the arbiter gives them a go-ahead at the beginning, assume that they all came to the table from a restaurant. Show the progression of events for 12 minutes. H stands for hungry and waiting. e for 1st min and E for 2nd min eating. [1-3] for not-hungry. Assume that the queue is 4321 initially.
Answer: Let's summarize the specs:
- eat 2 mins - numbered 43210 - priority: 0 first then queue - queue: 4321 at t=0 - arbitrate in the middle - 00123 are mins not-hungry - initially just ate
Below is the answer. Also see picture 3303-nov24-fri-2hr_2.gif of the slides in Lectures page for an answer to the version in MQS1A.
43210 Queue G
----- ----- -
1. HH123 4321 4
2. eHH12 3214 2
3. EHeH1 3142
4. HHEHH 3142 0
5. HH1He 3142 3
6. HeHHE 1423
7. HEHH3 1423 1
8. HHHe2 4231 4
9. eHHE1 2314
10. EHH2H 2314 2
11. HHe1H 3142 0
12. HHEHe 3142
Q10: Link the following and give me the memory map and symbol table of the executable.
0 2 bab 1 -1 cd 3 2 -1 6 R 8002 E 1000 E 1000 E 3000 R 1002 A 1010 1 cd 3 3 bab 2 -1 cd 1 -1 aba 4 -1 5 A 8000 E 1001 E 2000 I 2000 E 7004 0 2 cd 1 -1 aba 4 -1 7 A 8000 E 1001 A 2000 I 2000 E 7004 R 1002 R 1003 2 bab 3 aba 4 1 cd 3 -1 6 I 1004 A 5678 R 2002 E 8002 R 2001 R 2003
Answer: Let's first rearrange the input in a more readable format. That is, put newline at the end of every subsection although newline is of no real significance in the object code syntax.
0 2 bab 1 -1 cd 3 2 -1 6 R 8002 E 1000 E 1000 E 3000 R 1002 A 1010 1 cd 3 3 bab 2 -1 cd 1 -1 aba 4 -1 5 A 8000 E 1001 E 2000 I 2000 E 7004 0 2 cd 1 -1 aba 4 -1 7 A 8000 E 1001 A 2000 I 2000 E 7004 R 1002 R 1003 2 bab 3 aba 4 1 cd 3 -1 6 I 1004 A 5678 R 2002 E 8002 R 2001 R 2003
Now the answer (the executable machine code):
Symbol Table cd = 9 bab = 21 aba = 22 Memory Map +0 0: R 8002 8002+0 = 8002 1: E 1000 ->bab 1021 2: E 1000 ->cd 1009 3: E 3000 ->cd 3009 4: R 1002 1002+0 = 1002 5: A 1010 1010 +6 0: A 8000 8000 1: E 1001 ->cd 1009 2: E 2000 ->bab 7021 3: cd: I 2000 2000 4: E 7004 ->aba 7022 +11 0: A 8000 8000 1: E 1001 ->cd 1009 2: A 2000 2000 3: I 2000 2000 4: E 7004 ->aba 7022 5: R 1002 1002+11 = 1013 6: R 1003 1003+11 = 1014 +18 0: I 1004 1004 1: A 5678 5678 2: R 2002 2002+18 = 2020 3: bab: E 8002 ->cd 8009 4: aba: R 2001 2001+18 = 2019 5: R 2003 2003+18 = 2021
Q11: Link the following and give me the memory map and symbol table of the executable.
2 ba 3 ab 2 1 z 2 3 -1 4 I 1004 A 5678 E 2000 E 8002 0 2 ba 1 -1 z 3 2 -1 6 R 8002 E 1000 E 1000 E 3000 R 1002 A 1010 1 z 3 3 ba 2 -1 z 1 -1 ab 4 -1 5 A 8000 E 1001 E 2000 I 2000 E7004
Answer: Let's first rearrange the input in a more readable format. That is, put newline at the end of every subsection although newline is of no real significance in the object code syntax.
2 ba 3 ab 2 1 z 2 3 -1 4 I 1004 A 5678 E 2000 E 8002 0 2 ba 1 -1 z 3 2 -1 6 R 8002 E 1000 E 1000 E 3000 R 1002 A 1010 1 z 3 3 ba 2 -1 z 1 -1 ab 4 -1 5 A 8000 E 1001 E 2000 I 2000 E 7004
Now the answer (the executable machine code):
Symbol Table ab = 2 ba = 3 z = 13 Memory Map +0 0: I 1004 1004 1: A 5678 5678 2: ab: E 2000 ->z 2013 3: ba: E 8002 ->z 8013 +4 0: R 8002 8002+4= 8006 1: E 1000 ->ba 1003 2: E 1000 ->z 1013 3: E 3000 ->z 3013 4: R 1002 1002+4= 1006 5: A 1010 1010 +10 0: A 8000 8000 1: E 1001 ->z 1013 2: E 2000 ->ba 2003 3: z: I 2000 2000 4: E 7004 ->ab 7002
Q12: Consider 5 dining philosophers in a circle -- numbered 4 through 0 from left to right. We will coordinate their eating with an arbiter. They all eat for 2 mins at a time. The arbiter uses a mix of a round-robin (RR) scheme and a fixed-priority (FP) scheme. The priorities go as follows: 2 is the highest, then comes 1, then 0; philosophers 4 and 3 are equal priority and the lowest of all. The arbiter does an RR between 4 and 3. Philosopher 4 and 3 immediately get hungry after they finish eating. Philosopher 0 stays 1 minute not-hungry between each feast. 1 stays not-hungry for 2 mins. 2 stays not-hungry for 3 mins. The arbiter checks and decides who will eat next in the middle of every minute. When the arbiter gives them a go-ahead at the beginning, assume that they all came to the table from a restaurant. Show the progression of events for 10 minutes. H stands for hungry and waiting. e for 1st min eating and E for 2nd min eating. [1-3] for not-hungry. P stands for ptr. G for grant. Assume that P=4 initially.
Answer: Let's summarize the specs:
- eat 2 mins - numbered 43210 - priority: 210(43) - arbitrate in the middle - 00321 are mins not-hungry - initially just ate
Below is the answer. Also see picture 3303-nov24-fri-1hr_1.gif of the slides in Lectures page.
43210 P G
----- - -
1. HH321 4 4
2. eH21H 3
3. EH1HH 3 1
4. HHHeH 3 3
5. HeHEH 4
6. HEH2H 4 0
7. HHH1e 4 2
8. HHeHE 4
9. HHEH1 4 4
10. eH3HH 3 1
Q13: Consider the following snapshot of a system:
Alloc Max Avail. P1 0 0 0 4 5 6 1 3 2 P2 1 1 2 4 5 6 P3 1 0 0 3 4 3 P4 1 1 2 2 4 3
The system is in a safe state. Prove this by giving a sequence where everybody's max needs are satisfied. Do this by showing Available and Event columns.
Answer:
Need ----- P1 4 5 6 P2 3 4 4 P3 2 4 3 P4 1 3 1 Available Event (or we also call it Action) --------- ----- 1 3 2 0 0 1 <= minus Need(P4) = 1 3 1 gP4 (grant) 2 4 4 <= plus Max(P4) = 2 4 3 fP4 (finish) 0 0 1 <= minus Need(P3) = 2 4 3 gP3 3 4 4 <= plus Max(P3) = 3 4 3 fP3 0 0 0 <= minus Need(P2) = 3 4 4 gP2 4 5 6 <= plus Max(P2) = 4 5 6 fP2 0 0 0 <= minus Need(P1) = 4 5 6 gP1 4 5 6 <= plus Max(P1) = 4 5 6 fP1
Q14: A FIFO can only be written with non-binary semaphores. True or false?
Answer: False: Remember the solution we came up with that used no semaphores. It used shared variables called readPointer, writePointer, empty, full. Not every shared variable is a semaphore. If a shared variable is modified by only one process, then it does not necessarily have to be implemented by a semaphore.
Q15: If there is no IPC implemented in an OS, processes cannot exchange data. True or false?
Answer: False: They can still exchange data through files.
Q16: Consider 5 dining philosophers in a circle -- numbered 4 through 0 from RIGHT to LEFT. We will coordinate their eating with an arbiter. They all eat for 2 mins. The arbiter uses a mix of a round-robin (RR) scheme and a fixed-priority (FP) scheme. The priorities go as follows: 0 is the highest, then comes 1, then 2. Phil. 3 and 4 are equal priority and the lowest of all. The arbiter does an RR between 3 and 4. Philosophers 3 and 4 immediately get hungry after they finish eating. Philosopher 0, stays 3 minutes not-hungry between each feast. 1 stays not-hungry for 1 min. 2 stays not-hungry for 1 min as well. The arbiter checks and decides who will eat next in the middle of every minute. When the arbiter gives them a go-ahead at the beginning, assume that they all came to the table from a restaurant. Show the progression of events for 10 minutes. H stands for hungry and waiting. e for 1st min E for 2nd min eating. [1-3] for not-hungry. P stands for ptr. G for grant. Assume that P=3 initially.
Answer: Let's summarize the specs:
- eat 2 mins - numbered 01234 - priority: 012(34) - arbitrate in the middle - 31100 are mins not-hungry - initially just ate
Below is the answer. Also see picture 3303-nov24-fri-1hr_1.gif of the slides in Lectures page for the answer to the same problem in MQS2A.
01234 P G
----- - -
1. 311HH 3 3
2. 2HHeH 4 1
3. 1eHEH 4
4. HEHHH 4 4
5. H1HHe 3 2
6. HHeHE 3
7. HHEHH 3 0
8. eH1HH 3 3
9. EHHeH 4
10. 3HHEH 4 1
Q17: Link the following and give me the memory map and symbol table of the executable.
1 yz 4 3 ba 2 -1 yz 1 -1 ab 4 -1 5 A 8010 E 2001 E 2000 I 2000 E 7004 2 ba 3 ab 2 1 yz 2 3 -1 4 I 1004 A 5678 E 2000 E 8002 0 2 ba 1 -1 yz 3 2 -1 6 R 8002 E 5000 E 1000 E 3000 R 1002 A 1010
Answer: Let's first rearrange the input in a more readable format. That is, put newline at the end of every subsection although newline is of no real significance in the object code syntax.
1 yz 4 3 ba 2 -1 yz 1 -1 ab 4 -1 5 A 8010 E 2001 E 2000 I 2000 E 7004 2 ba 3 ab 2 1 yz 2 3 -1 4 I 1004 A 5678 E 2000 E 8002 0 2 ba 1 -1 yz 3 2 -1 6 R 8002 E 5000 E 1000 E 3000 R 1002 A 1010
Now the answer (the executable machine code):
Symbol Table yz = 4 ba = 8 ab = 7 Memory Map +0 0: A 8010 8010 1: E 2001 ->yz 2004 2: E 2000 ->ba 2008 3: I 2000 2000 4: yz: E 7004 ->ab 7007 +5 0: I 1004 1004 1: A 5678 5678 2: ab: E 2000 ->yz 2004 3: ba: E 8002 ->yz 8004 +9 0: R 8002 8002+9= 8011 1: E 5000 ->ba 5008 2: E 1000 ->yz 1004 3: E 3000 ->yz 3004 4: R 1002 1002+9= 1011 5: A 1010 1010
Q18: Consider the following snapshot of a system:
Alloc Max Avail. P0 0 0 0 4 5 6 1 3 2 P1 1 0 0 3 4 3 P2 1 1 2 2 4 3 P3 1 1 2 3 5 6
The system is in a safe state. Prove this by giving a sequence where everybody's max needs are satisfied. Do this by showing Available and Event columns.
Answer:
Need ----- P0 4 5 6 P1 2 4 3 P2 1 3 1 P3 2 4 4 Available Event (or we also call it Action) --------- ----- 1 3 2 0 0 1 <= minus Need(P2) = 1 3 1 gP2 (grant) 2 4 4 <= plus Max(P2) = 2 4 3 fP2 (finish) 0 0 1 <= minus Need(P1) = 2 4 3 gP1 3 4 4 <= plus Max(P1) = 3 4 3 fP1 1 0 0 <= minus Need(P3) = 2 4 4 gP3 4 5 6 <= plus Max(P3) = 3 5 6 fP3 0 0 0 <= minus Need(P0) = 4 5 6 gP0 4 5 6 <= plus Max(P0) = 4 5 6 fP0
Q19: DMA means Direct Memory Access. What is it that accesses
memory directly?
(a) Cache
(b) Peripherals
(c) Hard disk
(d)
CPU
(e) Graphics adapter
Answer: (b) Peripherals
Q20: A queue can only be written with binary semaphores. True or false?
Answer: False: Remember the solution we came up with that used no semaphores. It used shared variables called readPointer, writePointer, empty, full. Not every shared variable is a semaphore. If a shared variable is modified by only one process, then it does not necessarily have to be implemented by a semaphore. (Note that queue and FIFO often mean the same thing.)
Q21: Consider 6 dining philosophers in a circle. Here are the key parameters of the problem:
- philosophers numbered as 543210 - 0 eats for 1 min while rest eat for 2 mins - priority: 543 then queue - queue: 210 at t=0 - arbitrate in the middle of a min - 200022 are mins not-hungry - initially all are * hungry *
Show the progression of events for 12 minutes. H stands for hungry and waiting. e for 1st min eating and E for 2nd min eating. [1-2] for not-hungry.
Answer: The key points are as follows. Only 210 are in a queue. You need to show the granted philosophers. The arbiter tries to grant as many philosophers as possible each min. Although you and I know for how long each philosopher will eat and stay not-hungry, the arbiter does not know that and makes his decisions purely on priority order in that particular min and who is eating, who is hungry, and who is not.
543210 Que G
------ --- ---
1. HHHHHH 210 531
2. eHeHeH 201
3. EHEHEH 201
4. 2HHH2H 201 420
5. 1eHe1e 120
6. HEHEH2 120
7. HHHHH1 120 531
8. eHeHeH 201
9. EHEHEH 201
10. 2HHH2H 201 420
11. 1eHe1e 120
12. HEHEH2 120
Q22: Link the following and give me the memory map and symbol table of the executable.
2 foo 3 fn 1 1 foo 3 -1 6 I 2014 R 2002 A 3333 E 7003 R 1001 R 3003 0 2 fn 4 -1 foo 3 2 -1 5 R 8002 R 8002 E 2111 E 1000 E 4002 1 main 4 3 foo 1 2 -1 main 3 -1 fn 4 -1 5 R 8004 E 1011 E 4000 E 2000 E 7004 0 2 fn 1 -1 foo 4 -1 7 A 8000 E 1001 A 2000 I 2000 E 7004 R 1002 R 1003
Answer:See below for the straight answer. See MQ solutions for a more detailed answer of a different version of the question.
symbol table: fn = 1 foul = 3 main = 15 executable: 2014 2002 3333 7003 1001 3003 8008 8008 2003 1003 4001 8015 1003 4003 2015 7001 8000 1001 2000 2000 7003 1018 1019
Q23: Consider the following snapshot of a system:
Alloc Max Avail
A B C D A B C D A B C D
------- ------- -------
P0 2 0 0 2 5 5 4 3 1 1 2 4
P1 1 0 2 0 2 2 2 2
P2 1 1 0 0 3 4 5 6
P3 1 3 2 0 3 5 6 2
(a) The system is in an unsafe state. Explain why. (b) What is the min number extra resources we need to add to Avail to make the system safe. (c) Add that many resources and then show that the system is now in a safe state by giving a sequence where everybody's max needs are satisfied. Do this by showing Avail and Event columns.
Answer:
(a) The Need matrix is as follows.
3 5 4 1 1 2 0 2 2 3 5 6 2 2 4 2
There is no i such that Need(Pi) > Avail. That means if all processes suddenly wanted their Max resources, we would not be able to grant any of them, and hence be in a deadlock state.
(b) Let's compute the Difference matrix between Need and Avail. That is Diffi = Need(Pi) - Avail. Put zero in place of numbers that are negative.
2 4 2 0 0 1 0 0 1 2 3 2 1 1 2 0Let's sum up each row.
P0 8 P1 1 P2 8 P3 4
Since we are looking for the MIN number of resources that could make the system safe, we should take the row with the smallest sum. That is P1. Hence if we added 0 1 0 0 to Avail, we can at least grant P1. That does not mean that, we will not get stuck later and the system is safe. However, when we apply Banker's algorithm all the way, we see that there is a sequence in which all processes are granted their Max resources. Hence, the system is safe after the addition of 0 1 0 0 (ie. one more B).
(c) Now Avail is 1 2 2 4.
Avail Event --------- ----- 1 2 2 4 0 0 2 2 <= minus Need(P1) = 1 2 0 2 gP1 2 2 4 4 <= plus Max(P1) = 2 2 2 2 fP1 0 0 0 2 <= minus Need(P3) = 2 2 4 2 gP3 3 5 6 4 <= plus Max(P3) = 3 5 6 2 fP3 0 0 2 3 <= minus Need(P0) = 3 5 4 1 gP0 5 5 6 6 <= plus Max(P0) = 5 5 4 3 fP0 3 2 1 0 <= minus Need(P2) = 2 3 5 6 gP2 6 6 6 6 <= plus Max(P2) = 3 4 5 6 fP2
Q24: How do we implement a semaphore mechanism with user-level code if the OS has no semaphore implementation. Explain why.
Answer: With a client/server approach where the server is a process that always runs (ie. a daemon) and manipulates shared variables (ie. semaphores). Clients, on the other hand, are the processes that use semaphores. Clients simply write requests to a pipe (ie. buffer unique to that process). The semaphore (or also called IPC daemon) picks requests from buffers one by one. The reason the client/server approach is the only option is because there is no way we can write atomic semaphore P and V functions with user level code. When we write them as part of OS, we can turn off the timer interrupt and hence guarantee atomicity. However, with user level code, the OS may switch to a different process and hence to a different P call in the middle of a P call, for example.
Q25: What are the two steps a compiler performs? And what is the advantage of separating the two steps?
Answer: Compile and Link. This way, we only link files that have not been modified and hence save a lot of compile time.
Q26: There are 2 processes that process packets: process A and B. Every once in a while, process A receives a burst of N packets from outside and it has a buffer for exactly N packets. Process A either receives the N packets as a whole or declines the transfer. For efficency purposes, the 2 processes process packets in groups of multiple packets. Process A processes 2 packets at a time and produces 2 packets and sends them to process B. Process B processes 3 packets at a time and sends 2 result packets to process A. Process B has a considerably large buffer. (a) If N=5, there would be deadlock after a while. Show the sequence which leads to deadlock. (b) Trace the sequence of events, for N=1 thru 4 and see for each N, if a deadlock occurs.
Answer: (a) For N=5:
A 0 5 1 3 1 3 1
B 0 0 4 1 3 0 2
^
|____ DEADLOCK
Here is what goes on. Both processes start with 0 pkts. After a while 5 pkts arrive in the buffer of process A (hence 5/0). It processes 4 pkts (multiple of 2) and produces 4 pkts for B (1/4). B process 3 out of the 4 pkts and produces 2 new pkts for A (3/1). A processes 2 out of 3 pkts in its buffer and produces 2 pkts for B (1/3). B processes 3 to generate 2 (3/0). A takes 2 of 3 and sends 2 (1/2). At this point, neither A or B can process any pkts because A needs 2 pkts to perform its job and B needs 3. A cannot receive any pkts from outside because it does not have enough buffer space. It has a buffer of size N=5 where currently 1 slot is full. The pkts from outside come in groups of 5 and for A to accept them its buffer needs to be totally empty. Hence, we are stuck (ie. DEADLOCK) forever unless the OS detects the deadlock and flushes A's buffer. However, flushing A's buffer may require flushing B's buffer in some applications. Even that may not be enough in some cases and further remedies are needed. Or even in some cases, flushing A's buffer may be undoable and cause the system to get unstable or require a lot of data to be lost.
(b)
For N=1:
A 0 1
B 0 0
^
|____ DEADLOCK
As soon as A receives N=1 pkt, its buffer is full and cannot receive any other pkts. On the other hand, it cannot send out any pkts because it has fewer than 2 pkts. B cannot function either because it has no pkts to process.
For N=2:
Deadlock cannot occur. For a deadlock to occur we need to end up in A=1, B=2 (hence 1/2) state. In N=2, A can never be 1 because pkts always come to A in groups of 2 from outside and B.
For N=3:
A 0 3 1
B 0 0 2
^
|____ DEADLOCK
This case is pretty obvious. We get immediate deadlock.
For N=4:
Deadlock cannot occur. For a deadlock to occur we need to end up in A=1, B=2 (hence 1/2) state. In N=4, A can never be 1 because pkts always come to A in even numbers -- 4 from outside and 2 from B.
Comments: Out of buffer sizes between 1-5, 2 and 4 do not result in deadlock. The more bursting is allowed, the higher the performance is. So we would rather go with N=4. However, note that bigger buffer size (due to overusage of memory) can be a disadvantage as well. In a real application,
Q27: See here for linker inputs and outputs (hence solutions). See the link on our YahooGroup titled "A simple linker from NYU".
Q28: Consider 4 dining philosophers in a circle -- numbered 3, 2, 1, 0. We will coordinate their eating with a referee (ie. hakem). The referee uses a round-robin (RR) scheme as follows (see here for general info). He has a pointer that points to the VIP (Very Important Philosopher) of the moment. If ptr=2 for ex., then 2 gets to eat in the next min if he is hungry (H). If not, the ref. checks to see 1 is H, if not 0 is H, if not 3 is H. Consider a clock that advances one minute at a time. Every philosopher eats for 2 minutes when he eats. Philosopher 0 stays full (ie. not-hungry) for 0 minutes. That is, as soon as he finishes eating, he immediately gets hungry. Philosopher 1, stays 1 minute not-hungry between each feast. 2 stays not-hungry for 2 mins. 3 stays not-hungry 3 mins. The ref. checks and decides who will eat next in the middle of every minute. When the ref. gives them a go-ahead at the beginning, assume that they all came to the table from a restaurant. Show the progression of events. H stands for hungry and waiting. E for eating. [1-3] for not-hungry. P stands for ptr. G for grant. Assume that P=3 initially.
Answer:
3210 P G
---- - ---
1. 321H 3 0
2. 21He 3=0-1
3. 1HHE 3 2
4. HeHH 1=2-1 0
5. HEHe 3=0-1
6. H2HE 3
7. H1HH 3 3,1
8. eHeH 0=1-1
9. EHEH 0 ---
10. 3H1H 0 0,2 |
11. 2eHe 1=2-1 |
12. 1EHE 1 |
13. H2HH 1 1,3 |
14. e1eH 2=3-1 |
15. EHEH 2 |
16. 3H1H 2 2,0 |
17. 2eHe 3=0-1 |
18. 1EHE 3 |
19. H2HH 3 3,1 v
20. e1eH 0=1-1 --- 9-20 repeats from this point on.
21. EHEH 0 -----> same as 9.
Let's look at what's going on above:
min 1: 0 gets H right away. Although P=3, since only 0 is H, it gets
granted.
min 2: After a 1 min lapse, 1 gets H. P moves to the right of 0
because we want to make 0 the lowest priority. Hence, P becomes
0-1(mod4)=3. The only philosopher requesting to eat is 1. However,
since one of its forks is taken by 0, it cannot be granted.
min 3: 2 has not been hungry for 2 mins, so it gets H. 0 is in the
last min of its feeding interval. (e indicates 1st min and E indicates
2nd min.) Irrespective of P, the only one that can be granted is 2.
min 4: Since 2 is granted, P becomes 1. Similar to the
previous min, the only one that can be granted is 0, since 2 is
already eating.
min 6: 2 finishes eating and it is now not-hungry based on
its eating pattern given in the question.
min 7: P=3, and 3 is H. So the ref. grants 3 and continues
to scan the rest of the philosophers and notices that granting 1 is
also possible and hence grants 1 too.
min 8: Since the ref. granted 1 last, P becomes 0.
The minutes listed above are the interesting ones.
Let's look at the performance of this scheme. The pattern between 7-18 repeats forever and dictates the performance. Therefore we can ignore the sequence between 1-6. The pattern is such that either 3 and 1 eat or 2 and 0 eat. There are 1 min intervals in between the two during which nobodys eats. This is due to the fact that the ref. arbitrates not for the current minuet for the next (ie. the non-zero latency of arbitration). The best scheme would let 2 philosophers eat per min. The scheme above has 16 e/E's in 12 mins. That is 1.33 philosophers per minute. Not the ultimate maximum.
The above scheme is not very efficient due to the 1.33 number. However, it does not have deadlock or starvation. Due to the use of a ref. it is not supposed to have deadlock. Nevertheless, a ref. does not necessarily rule out starvation.
Is the scheme above, or more specifically the sequence it results in, "fair"? Since every philosophers eats twice in the repeating 12 mins, one may claim it is fair. I would disagree with that. We do not necessarily want them to eat as often because 3 gets H less than others, and 0 gets H more often than anybody else. We should instead look at either how many mins they are left H. Or we should look at the ratio of E/H. 3 is 2 mins H out of 12. 2 is 4 mins H. 1 is 6 mins H. 0 is 8 mins H. E/H ratio-wise, 3=>4/2=2, 2=>4/4=1, 1=>4/6=0.7, 0=>4/8=0.5. To alleviate this issue, one could use a weighted RR scheme, where the weight comes from for how many mins a philosopher has been hungry.
Q29: Consider the above problem with the above RR scheme but assume all philosophers get hungry immediately. Can you come up with a state such that when the RR scheme gets into that state, it will go into such a vicious cycle that half of the philosophers would starve.
Answer: Once we get into eHEH state, the above RR scheme would only grant 3 and 1, and 2 and 0 will starve. This could happen if 0 gets hungry in min 1 and the rest get hungry in min2, and then get hungry immediately after eating thereafter.
3210 P G
---- - -
1. 111H 3 0
2. HHHe 3=0-1 2 ---
3. HeHE 1=2-1 v
4. HEHH 1 0 --- 2-4 repeats from this point on.
5. HHHe 3=0-1 2 --------> same as 2.
Q30: Consider the problem in Q5 with the same eating habits there. However, modify the RR scheme as follows. The ref executes RR scheme at the beginning of every minute in the blink of an eye. Show the sequence of events and look at effiviency and fairness isues.
Answer:
begin. P G during the minute ------ - --- ----------------------- 1. 321H 3 0 -> 321e 2. 21HE 3 -> 21HE 3. 1HHH 3 2,0 -> 1eHe 4. HEHE 3 -> HEHE 5. H2HH 3 3,1 -> e2eH 6. E1EH 0 -> E1EH 7. 3H1H 0 0,2 -> 3e1e 8. 2EHE 1 -> 2EHE 9. 12HH 1 1 -> 12eH 10. H1EH 0 3 -> e1EH --- 11. EH1H 2 -> EH1H | 12. 3HHH 2 2,0 -> 3eHe | 13. 2EHE 3 -> 2EHE v 14. 12HH 3 1 -> 12eH --- repeats 15. H1EH 0 3 -> e1EH
Efficiency is 8/5, ie. 1.6 philosophers eat per min on the average. Hence, this scheme has a better utilization than the previous one where arbitration has a non-zero latency. Every philosopher eats 2 min every 5 mins. The E/H ratios are 2/0 for 3, 2/1 for 2, 2/2 for 1, 2/3 for philosopher 0.
Q31: Consider Q5. Show me the sequence in the case where a "Queue" based scheduling is used. As we discussed in class, the queue method is as follows. Instead of maintain just a pointer, we maintain a complete queue. Every cycle, we scan the queue starting from the topmost entry in the queue, we schedule all the philosophers who can eat to the following cycle, and move them to the end of the queue in the order they are scheduled. While the queue is always in a 3210 order or its rotated versions in RR arbitration, in the queue method, the philosophers may have any order. Therefore, in RR there are 4 different possible orders, in the queue method, there are 4! orders, ie. 24.
Answer:
3210 Queue G
---- ----- ---
1. 321H 3210 0
2. 21He 3210
3. 1HHE 3210 2
4. HeHH 3102 0
5. HEHe 3120
6. H2HE 3120
7. H1HH 3120 3,1
8. eHeH 2031
9. EHEH 2031
10. 3H1H 2031 2,0 ---
11. 2eHe 3120 |
12. 1EHE 3120 |
13. H2HH 3120 3,1 |
14. e1eH 2031 v
15. EHEH 2031 --- 10-15 repeats from this point on.
16. 3H1H 2031 2,0 -----> same as 9.
17. 2eHe 3=0-1
Above is the sequence. As you may see, the end result is no different than Q5. In a 4-philosopher problem, we do not have much room for different solutions. Either 0,2 eat or 1,3. Since there is a latency of one cuycle in ref's decision, one cycle is wasted. However, I beileve the queue method would result in a different pattern from RR in a 5-philosopher problem. The queue method has the potential to result in fairer sequences than RR.
Q32: Solve MHW1-Q1 such that no buffer slots are wasted. You are allowed to use two additional shared variables but still no semaphores.
Answer:
// writePointer, readPointer, full, empty,
// writeRollOver, readRollOver
// are global variables that both processes can see.
// ===> ProcessW:
size = endAddress -beginAddress +1;
writeRollOver = 0;
...
if (!full) {
writeData ();
writerUpdate ();
}
...
void writerUpdate () {
void *writeIndex;
writeIndex = writePointer -beginAddress;
writeIndex = (writeIndex +1)%size;
writeRollOver = !writeRollOver;
full = 0;
if (((writeIndex +1)%size +beginAddress) == readPointer)
if (writeRollOver != readRollOver)
full = 1;
writePointer = writeIndex +beginAddress;
}
// ===> ProcessR:
readRollOver = 0;
...
if (!empty) {
readData ();
readerUpdate ();
}
...
void readerUpdate () {
void *readIndex;
readIndex = readPointer -beginAddress;
readIndex = (readIndex +1)%size;
readRollOver = !readRollOver;
empty = 0;
if ((readIndex +beginAddress) == writePointer)
if (readRollOver == writeRollOver)
empty = 1;
readPointer = readIndex +beginAddress;
}
What we are doing above is equivalent to the following. We are doubling the pointer space with the help of RollOver flags, which serves as one additional pointer digits. However, when we are accessing we ignore that digit so that the actual buffer still stays the same size. When empty, the read and write pointers are supposed to be equal including the RollOver (ie. flags) digits. However, when full, the two pointers are supposed equal while the RollOver digits are supposed to be opposite of each other. That is, when one of them is 0, the other is 1.
Q33: Writes to shared memory from parallel processes require serialization. What are the different ways of achieving serialization?
Answer: (i) Atomic instructions (ii) Atomic functions: functions in which the timer interrupt (ie. context-switch) is turned off (iii) a client-server approach where a server (in other words daemon=service) is in charge of the shared memory.
Q34: What is cooperative multitasking? And how is it different from preemptive (ie. regular) multitasking?
Answer: Cooperative multitasking means the OS cannot premept processes. The OS can switch to another process only when the process in possession of the CPU makes a system call (hence switches to the OS).
Q35: Exercise 8-13 in the 6th edition of Silberschatz. (Just to make sure we are looking at the same problem, Available = [1 5 2 0]).
Answer:
(a) 0 0 0 0
0 7 5 0
Need = 1 0 0 2
0 0 2 0
0 6 4 2
(b) The system is in a safe state. First of all, P0 can finish anytime it wants because it does not require any extra resources. P3 can also be granted in this current state. After these two processes finish, extra resources will free up and we will reach an Available vector of [1 11 6 4]. Equipped with this vector, P2 and P4 can simultaneously be granted and finish. And last P1 can finish.
Available Event
---------- -----
1 5 2 0 P0 finishes
1 5 3 2 grant P3 max need of [0 0 2 0]
1 5 1 2 P3 finishes
1 11 6 4 grant P2 max need of [1 0 0 2]
grant P4 max need of [0 6 4 2]
0 5 2 0 P2 and P4 finish
2 14 12 12 grant P1 max need of [0 7 5 0]
2 7 7 12 P1 finishes
3 14 12 12
(c)If we grant a request from P1 of [0 4 2 0] and we grant it, then we will end up with an Available vector of [1 1 0 0] and need matrix of:
(a) 0 0 0 0
0 3 3 0
Need = 1 0 0 2
0 0 2 0
0 6 4 2
All Need vectors are greater than Available vector at least in one
component, and hence the system may get into a deadlock. Therefore, we
will end up in an unsafe state if we grant this request. We should not
immediately grant that request. If we wait until P3 finishes, at that
point, we can finish the remaining jobs in any order.
Q36: What is .o file? What is .a file in UNIX?
Answer: You figure it out.
Q37: How do I control whether I run a process in the background when issued from a command window in UNIX? DO I have a similar control mechanism in Windows?
Answer: If I put & sign at the end of the command-line, then the process is run in the background, otherwise is run in the foreground and we cannot issue subsequent commands to the command shell. There is no equivalent control mechanism in Windows.
Q38: What is the name of the first PC-UNIX? Which company developed it and which company funded the development?
Answer: Name is XENIX. SCO (Santa Cruz Operation) developed it for Microsoft.
Q39: For what reasons early mainframes used magnetic tapes as main memory?
Answer: In those days, RAM was expensive and big. Hence, mainframes had limited RAM. Even in those days, many applications required significant amount of memory. Therefore, the mainframes had no choice but use magnetic tapes as main memory (not just virtual memory). Even one magnetic tape was not enough sometimes. These main frames used magnetic tapes also as what we use HD these days for.
Q40: Silberschatz 6th edition, exercise 7.9 (Cigarette-Smokers Problem).
Answer: You figure it out.
Q41: Consider 5 dining philosophers in a circle -- numbered 4 through 0 from left to right. We will coordinate their eating with an arbiter. Each eats for 2 mins when he eats. The arbiter uses a mix of a queue scheme and a fixed-priority (FP) scheme. 0 has the highest priority and the rest are arbitrated based on a "queue". Philosophers 4 and 3 immediately get hungry after they finish eating. Philosopher 0 stays 4 minute not-hungry between each feast. 1 stays not-hungry for 2 mins. 2 stays not-hungry for 1 min. The arbiter checks and decides who will eat next in the middle of every minute. When the arbiter gives them a go-ahead at the beginning, assume that they all came to the table from a restaurant. Show the progression of events for 12 minutes. H stands for hungry and waiting. e for 1st min eating and E for 2nd min eating. [1-4] for not-hungry. Assume that the queue is 4321 initially.
Answer: Let's summarize the specs:
- eat 2 mins - numbered 43210 - priority: phil. 0 then queue - queue: 4321 at t=0 - arbitrate in the middle - 00124 are mins not-hungry - initially just ate
Below is the answer. Also see picture 3303-nov24-fri-2hr_2.gif of the slides in Lectures page.
43210 Queue G
----- ----- -
1. HH124 4321 4
2. eHH13 3214 2
3. EHeH2 3142
4. HHEH1 3142 4
5. eH1HH 3124 1
6. EHHeH 3241
7. HHHEH 3241 3
8. HeH2H 2413 0
9. HEH1e 2413
10. HHHHE 2413 2
11. HHeH4 4132 4
12. eHEH3 1324
Q42: What is BIOS? Give me a short description.
Answer: When a PC boots up, that is when the PC is loading the OS from the hard disk (HD), it cannot talk to the HD because all those system functions come with the OS and the OS has not been loaded yet. Hence, we need a basic set of system functions especially those to read the master boot record (MBR) of the HD. These functions need to be stored in an easily readable device. This device is a ROM (read-only memory). Think of it like a non-volatile version of RAM. This ROM contains some basic OS functions. BIOS stands for Basic Input Output System. BIOS is mistaknely known as Basic Integrated Operating System by some people. Also see Wikipedia.