1. Consider three processes (P1, P2, P3) accessing two semaphores (A, B) with the following code segments:
P1 P2 P3
-- -- --
1. wait(A); 5. wait(A); 9. signal(A);
2. signal(B); 6. wait(B); 10. wait(A);
3. signal(A); 7. wait(B); 11. signal(B);
4. wait(B); 8. signal(B); 12. signal(A);
The semaphores are not initially available (i.e., the counts are 0).
You can schedule these semaphore calls in any order you like by indicating the associated line number (1..12).
Of course, you cannot schedule line 2 before line 1, line 6 before line 5, etc.
If a wait blocks, don't list it again even if it unblocks later.
In both a) and b) below, your answers should be exactly 12 numbers.
In c), it should be less than 12 numbers.
a) Give a schedule such that all processes will eventually finish but NEVER block on any call to wait.
b) Give a schedule such that all processes will eventually finish but at least one call to a wait does block.
c) Give a schedule such that all processes become deadlocked.
Given: terminology for semaphore usage.
| Silberschatz |
Dijkstra |
Tannenbaum |
| wait(s) |
P(s) |
down(s) |
| signal(s) |
V(s) |
up(s) |
2. Let f(a,b,c,d) = a'b'c'd + a'b'cd + ab'c'd' + abcd' + abcd.
a) Use a 4x16 decoder and a minimal number of additional logic gates to implement f.
b) Use a 16-to-1 multiplexor (and no other gates) to implement f.
Use block diagrams for the decoder and multiplexor.
3. Consider the Banker's Algorithm in a system with two processes (P0, P1) and three types of resources (A, B, C), each in a quantity of N>1 units.
Initially, both P0 and P1 indicate that their maximum requirement is that they might need all the units in the system, that is, (N, N, N). In your descriptions below be sure to state whether the Banker would grant the actual requested resources.
Now the processes begin their work.
a) Describe what would happen, and why, if P0 asked for all the resources (N, N, N) followed immediately by the same request from P1.
Start the system over again and let the processes begin their work.
b) Describe what would happen, and why, if P0 asked for just one unit of resource A followed immediately by the same request from P1.
Start the system over again and let the processes begin their work.
c) Describe what would happen, and why, if P0 asked for just one unit of resource A followed immediately by a request from P1 for one unit of resource B.
4. An Intel processor instruction CMP AX,BX performs the subtraction AX - BX and affects the bits ZF, SF and OF as follows:
ZF <--- 1 if the result of the CMP subtraction is zero
ZF <--- 0 otherwise
SF <--- 1 if the result of the CMP subtraction is a negative number
SF <--- 0 otherwise
OF <--- 1 if the result of the CMP subtraction results in signed overflow
OF <--- 0 otherwise
Draw a diagram for a circuit that has 3 inputs (ZF, SF, OF) whose output will be 1 if and only if AX < BX (as signed integers). (This could be useful in deciding if the branch BLE label should be taken.)
