EEL 358 - Operating
Systems
Fall 2006
Indian Institute of
Technology
Last Updated on 4/12/2006
Please read marking schemes/comments carefully before you come to see your scripts on 5/12/2006.
Major Test
Solutions and Marking Scheme
1. Short Answers
(a) UNIX uses the notion of a ¡§Current Working Directory¡¨ (CWD) in which file names that don¡¦t start at the root are assumed to be relative to the CWD. This is a convenience for users but also can improve system performance. State how this approach can improve performance and give an example. [1]
¡@
It improves performance by reducing the directory look ups necessary to find the file. For example, if the CDW is ¡§z¡¨ and I want to access the file /x/y/z/foo.txt then I can skip looking up the
directories for root, x, and y.
¡@
(b) What needs to be saved and restored on a context switch between two threads in the same process? What if the two threads are in different processes? Be explicit. [2]
¡@
Need to save the processor registers, stack pointer, program counter into the TCB of the thread that is no longer running. Need to reload the same things from the TCB of the new thread.
When the threads are from different processes, need to not only save and restore what was given above, but you also need to load the pointer for the top-level page-table of the new
address space. You don¡¦t need to save the old pointer, since this will not change and is already stored in the PCB.
Most common error - saving TCB (rather than into TCB) and restoring TCB
¡@
(c) Assume that you have a RAID-5 system with five disks. One of the disks fails. Explain how the operating system can continue to satisfy block reads for that disk. Can the system deal with two failures? Why or why not? [2]
¡@
Assume that data on disk 5 is generated as the parity of data on disks 1-4. Then, for each block Bx, we have B5 = B1 ¡ò B2 ¡ò B3 ¡ò B4 . ⇒ B1 ¡ò B2 ¡ò B3 ¡ò B4 ¡ò B5=0.
Data from any block on disk can be recovered by XOR-ing together data from parallel blocks on the other 4 disks (or above: one equation, one unknown).
¡@
The system cannot deal with 2 failures, because there isn¡¦t enough information to recover 2 disks worth of data (or above: one equation, two unknowns).
Another way to put this is that for every five blocks (one from each disk), we have four blocks full of data and one redundant block (the parity). If we have 4 working disks, we have arranged it
so that we can recover 4 actual data blocks. If we only have three working disks, there is not enough information in three disks to generate 4 disks worth of actual data.
Answers citing 'using parity information' received only half credit as how/explanation was required.
¡@
2. Hungry Aliens Revisited ¡V Please use the following parameter values to answer the parts of this question. Clearly show your work in order to get any credit.
PEarth
Probability that the pasta can be found on Earth.
0.20
PMoon
Probability that the pasta can be found on the Moon
0.50
PPluto
Probability that the pasta can be found on Pluto
1.0
LEarth
Time required to try Earth
10 minutes
LMoon
Time required to try the Moon
100 minutes
LPluto
Time required to try Pluto
2000 minutes
(a) Earth and Pluto ¡V Assume an alien has arrived on earth looking to eat his favorite type of Pasta (no need to worry about how many arms the alien has). He starts looking on earth, if he can¡¦t find it there, he flies his space ship to Pluto where he knows they always have that kind of pasta (in this case, if the pasta is not on Earth, it will take 2010 minutes for the Alien to get the pasta). On average, how long should it take for the Alien to find his pasta? [2]
¡@
Ave. Access Time = L_Earth + (1 - P_Earth) * L_Pluto
= 10 + (1 - 0.2) * 2000
= 1610 minutes
(b) Add the Moon ¡V Now consider the case where the pasta may also be located on the moon (according to the probabilities and miss penalties shown above). In this case, how long should it take for the Alien to find his pasta (assuming he goes from Earth to the Moon, and then to Pluto if necessary)?
¡@
Ave. Access Time = L_Earth + (1 - P_Earth) [L_Moon + (1 - P_Moon)(L_Pluto)]
= 10 + (1 - 0.2) [100 + (1 - 0.5)(2000)]
= 890 minutes
(c) For the problem in part ¡§b¡¨ above, for what values (if any) of LMoon would it make sense for the Alien to skip searching the moon and go straight to Pluto?
¡@
The alien should skip the moon if the part from part b is larger than the answer from part a. That is:
L_Earth + (1 - P_Earth) [L_Moon + (1 - P_Moon)(L_Pluto)] > 1610
10 + (1 - 0.2) [L_Moon + (1 - 0.5)(2000)] > 1610
L_Moon > 1000 minutes
¡@
3. Consider an architecture combining segmentation and paging with 32-bit addresses divided into fields as follows:
4-bit seg id
12 bit page number
16 bit offset into page
¡@
Given the contents of physical memory shown on the left and the segment table on the right below, what is the phyical address do the following virtual addresses map to (if a virtual address is invalid, state why) . Please write your answer in the space provided in this question paper itself. All values are in hexadecimal. [5]
(+ 1 marks a piece, -0.5 for every incorrect answer!)
¡@
Address
Value
0x10000
0x10
0xA
0xB
0x5
¡K
¡K
0x20000
0x3
0x7
0x5
0x9
¡K
¡K
0x30000
0x6
0x4
0x8
0x11
¡K
¡K
SegID
Page Table Ptr
Page Table Size
0
0x20000
0x4
1
0x30000
0x4
2
Not Valid
-----
3
0x10000
0x4
4
Not Valid
-----
¡K
Not Valid
-----
15
Not Valid
-----
¡@
¡@
¡@
¡@
¡@
0x00001234 = ¡K¡K¡K 0x31234 ¡K¡K¡K¡K¡K¡K¡K¡K¡K
¡@
0x10001234 = ¡K¡K.¡K 0x61234 ¡K¡K¡K¡K¡K¡K¡K¡K¡K
¡@
0x11111234 = ¡K¡K¡K invalid - virtual page num. exceeds size of segment
¡@
0x20021234 = ¡K¡K¡K segment 2 does is not valid
¡@
0x30031234 = ¡K¡K¡K 0x51234 ¡K¡K¡K¡K¡K¡K¡K¡K¡K
If you failed to write correct reason for 'invalid', you only received half mark.
¡@
4. Suppose that we have a multiprogrammed computer in which each job has identical characteristics. In one computation period, T, for a job, half the time is spent in I/O and the other half in processor activity. Each job runs for a total of N periods. Assume that a simple round-robin scheduling scheme is used and that I/O operations can overlap with processor operation. We define the following quantities:
¡P Turnaround time = actual time to complete a job.
¡P Processor utilization = percentage of time that the processor is active (not waiting).
For large N, compute approximate values for these quantities for one, two, and four simultaneous jobs, assuming that the period T is distributed in each of the following ways:
a. I/O first half, processor second half [3]
i) 1 job, Turnaround time and Processor utilization
ii) 2 jobs, Turnaround time and Processor utilization
iii) 4 jobs, Turnaround time and Processor utilization
b. I/O first and fourth quarters, processor second and third quarters. [3]
i) 1 job, Turnaround time and Processor utilization
ii) 2 jobs, Turnaround time and Processor utilization
iii) 4 jobs, Turnaround time and Processor utilization
a. 1 job, Turnaround time and Processor utilization:
5 points, 3 for correct answer for TAT and 2 for correct utilization.
TAT = NT, CPU utilization = 50%.
ii) 2 jobs, Turnaround time and Processor utilization:
TAT = NT, CPU utilization = 100%.
iii) 4 jobs, Turnaround time and Processor utilization:
TAT = (2N ¡V 1)T, CPU utilization = 100%. 2NT for TAT is also acceptable.
b. I/O first and fourth quarters, processor second and third quarters.
i) 1 job, Turnaround time and Processor utilization:
2 points for TAT and 1 for utilization. Same answer as part a for 1 job.
ii) 2 jobs, Turnaround time and Processor utilization:
Same answer as above for part a for 2 jobs.
iii) 4 jobs, Turnaround time and Processor utilization:
Same answer as above for part a for 4 jobs.
5. You¡¦ve been hired by the HAL computer company to review their code for a large application. In the application you find the atomic swap procedure. Say whether it either (i) works, (ii) doesn¡¦t work, or (iii) is dangerous that is, sometimes works and sometimes doesn¡¦t. If the implementation does not work or is dangerous, explain why (there may be several errors) and rewrite the code to fix it so it does work. [8]
¡@
The problem statement is as follows: The atomic swap routine pops an item from each of two stacks and pushes the items onto the opposite stack. If either stack does not contain an item, the swap fails and the stacks are left as before the swap was attempted. The swap must appear to occur atomically: there should be no interval of time during which an external thread can determine that an item has been removed from one stack but not yet pushed onto another one. In addition, the implementation must be highly concurrent ¡V it must allow multiple swaps between unrelated stacks to happen in parallel. You may assume that stack1 and stack2 never refer to the same stack.
¡@
void AtomicSwap (Stack *stack1, *stack2) {
Item thing1; /* First thing being transferred */
Item thing2; /* Second thing being transferred */
stack1->lock.Acquire();
thing1 = stack1->Pop();
if (thing1 != NULL) {
stack2->lock.Acquire();
thing2 = stack2->Pop();
if (thing2 != NULL) {
stack2->Push(thing1);
stack1->Push(thing2);
stack2->lock.Release();
stack1->lock.Release();
}
}
}
¡@
This routine is (iii) dangerous for three reasons: [0+3] Each reason is worth one mark
1. Deadlock could occur because there is no resource ordering during lock acquisition.
2. The routine fails to release the locks if either stack is empty.
3. The routine does not leave stack1 unchanged if stack two is empty (it fails to repush thing1).
¡@
I subtracted 1 marks if you claimed that the routine is not atomic ¡V an outside application cannot see whether something has been removed from one stack and not yet pushed onto another stack (this includes the error that fails to repush thing1. It does not release the lock on stack1, so the error is not externally visible).
The code solution is worth 5 marks total: 3 marks for fixing deadlock and one mark for fixing each of remaining two errors. I also subtracted 1 mark for the overall implementation quality (if deadlock is fixed) - one mark is also subtracted for solutions that used a global lock (where the lock was held for the entire swap routine) and subtracted 1 mark for solutions that used a global lock around lock acquisition (where the lock was only held while each lock was acquired).
void AtomicSwap (Stack *stack1, *stack2) {
Item thing1; /* First thing being transferred */
Item thing2; /* Second thing being transferred */
if (stack1 > stack2) {
stack1->lock.Acquire();
stack2->lock.Acquire();
} else {
stack2->lock.Acquire();
stack1->lock.Acquire();
}
thing1 = stack1->Pop();
if (thing1 != NULL) {
thing2 = stack2->Pop();
if (thing2 != NULL) {
stack2->Push(thing1);
stack1->Push(thing2);
} else {
stack1->Push(thing1);
}
}
stack2->lock.Release();
stack1->lock.Release();
}
6. A restaurant would like to serve four dinner parties, P1 through P4. The restaurant has a total of 8 plates and 12 bowls. Assume that each group of diners will stop eating and wait for the waiter to bring a requested item (plate or bowl) to the table when it is required. Assume that the diners don't mind waiting. The maximum request and current allocation tables are shown as follows:
Maximum
Request
Plates
Bowls
P1
7
7
P2
6
10
P3
1
2
P4
2
4
Current
Allocation
Plates
Bowls
P1
2
3
P2
3
5
P3
0
1
P4
1
2
¡@
¡@
¡@
¡@
¡P Will the restaurant be able to feed all four parties successfully? Clearly explain your answer ¡V specifically, why no or why/how there is a safe serving order. [1.5]
¡P Assume a new dinner party, P5, comes to the restaurant at this time. Their maximum needs are 5 plates and 3 bowls. Initially, the waiter brings 2 plates to them. In order to be able to feed all five parties successfully, the restaurant needs more plates. [2.5]
(a) At least how many plates would the restaurant need to add?
(b) Show a safe serving sequence.
A. Need matrix
Need
Plates
Bowls
P1
5
4
P2
3
5
P3
1
1
P4
1
2
The vector of available resources is A = (2, 1).
First, serve P3, and A will be (2, 2).
Then, serve P4, and A will be (3, 4).
There are not enough resources available to serve P1 or P2. Therefore, the original resource allocation state is unsafe. The restaurant cannot feed all four parties successfully.
¡@
B. New need matrix
(a)
Need
Plates
Bowls
P1
5
4
P2
3
5
P3
1
1
P4
1
2
P5
3
3
¡@
If add 1 plate, there are 9 plates and 12 bowls totally.
Initially, A = (1, 1).
Serve P3, A = (1, 2).
Serve P4, A = (2, 4).
So there are not enough resources for serving the 5 parties.
If add 2 plates, there are 10 plates and 12 bowls totally.
Initially, A = (2, 1).
Serve P3, A = (2, 2).
Serve P4, A = (3, 4).
Serve P5, A = (5, 4).
Serve P1, A = (7, 7).
Serve P2, A = (10, 12).
Therefore, at least 2 plates are needed.
(b) A safe serving sequence is P3-P4-P5-P1-P2.
¡@Solutions that just cited answers, without any specific explanation, did not receive any credit (zero). Solutions that did not cite Bankers Algorithm or safe/unsafe state/sequence also did not receive any credit.