1. On a system with two processors of unknown speed, the following two processes run in parallel. Assuming that each of the 10 instructions a - j is atomic, list all the different possible pairs of out comes (for x,y) that can be produced by this code fragment. Show each sequence and outcome. (10 points)
The shared variables x,y both are initialized to 0, and the shared semaphore mutex has initial value 1.
| Process 1 | Process 2 |
| a) x =1 | f) x = x + 2 |
| b) p(mutex) | g) p(mutex) |
| c) y = y + x | h) y = y -1 |
| d) x = 2 | i) x = x - y |
| e) v(mutex) | j) v(mutex) |
2. You have processes 1..4 with arrival times and CPU processing requirements as shown. For each of the following scheduling algorithms, show (in the table or diagram) at each time which process is running the CPU. Compute the average flow time over this set of jobs. (20 points).
| Process | Arrival time | CPU time needed |
| 1 | 0 | 5 |
| 2 | 1 | 3 |
| 3 | 2 | 6 |
| 4 | 3 | 1.5 |
(a) FIFO
(b) RR (time slices = .5)
(b) STCF
(c) SRTCF
(d) SET (implemented with time slices of .5) (Process
with shortest elapsed executiontime gets scheduled first, but we
also do time slicing just as in RR)
3. Explain the difference between a program and a process. (10 points)
4. Given the following processes and their resource allocations, use the banker's algorithm to determine if a deadlock is inevitable; show your calculations. The system has 10 units of X and 20 units of Y. (10 points)
| Process | has X | max X needed | has Y | max Y needed |
| 1 | 3 | 10 | 2 | 4 |
| 2 | 0 | 6 | 6 | 7 |
| 3 | 5 | 5 | 2 | 6 |
| 4 | 1 | 2 | 5 | 5 |
5. Define (in your own words) and give an example of each of the following terms: deadlock, priority inversion, and thread starvation. (10 points)
6. A linker or loader can place code anywhere in memory by taking a set of code pieces, and a table showing all locations in the code where address constants exist. The linker/loader then computes the correct values for those address constants, loads the code into memory and sets the values of the address constants correctly.
Let us suppose that we have a program X which has been linked/loaded and has run for a while. We have preserved all of the the tables used by the linker/loader. Can we stop the program and have the linder/loader move it to some other location in memory? If yes, explain how. If not, give as many reasons as possible as to why not. (10 points)
7. (a) Rewrite the readers/writers problem solution (as shown in class) so that readers have priority over writers. (18 points) (b) What effect will this have on the performance of a lightly loaded system? Why? (3 points) (c) What effect wil this have on the performance of a heavily loaded system? Why? (3 points). (d) Assume that this is a banking system. What effect will this have on the "semantics" of the system? (3 points)