The following questions appeared on exams from the version of this class that I gave in Winter 2000.

P(s): < when (s > 0) do s = s - 1 >
V(s): < when (s < max) do s = s + 1 >

Note that unlike general semaphores, a V operation on a symmetric semaphore will block if the value of the semaphore is equal to max.

1. Give a monitor implementation of these two operation. Be sure to state the monitor invariant and the conditions associated with any condition variables you use.
2. Are there problems that can be solved with symmetric semaphores that cannot be solved with general semaphores? Are there problems that can be solved with general semaphores that cannot be solved with symmetric semaphores? Explain

The language construct is as follows. A block of code can be bracketed with a statement:

where v1, v2, ... is a list of strings called tags. Any two tagged critical regions that have at least one tag in common execute in mutual exclusion of each other. For example, consider the three tagged critical regions:
 

The code S1 and S2 execute in mutual exclusion (they both have x as a tag), and S2 and S3 execute in mutual exclusion (They both have y as a tag), but S1 and S3 can execute at the same time (they don't share any tags).

1. Explain how a tagged critical region can be implemented using general semaphores. Illustrate your technique with the three tagged critical regions above.
2. Is your employee correct: are tagged critical regions as powerful as semaphores or monitors? Explain.

1. Two P operations working on different semaphores must be mutually excluded.
2. The value of a semaphore cannot be modified by an operation other than P or V.
3. Several processes can concurrently execute entry procedures of the same monitor.
4. Binary semaphores are weaker than general semaphores.
5. Any program written with cobegin and coend can be written instead with fork and join.
6. A monitor must run with interrupts disabled.

1. What is the algorithm that results if A=B and is positive?
2. What is the algorithm that results if A=B and is negative, and the scheduler is non-preemptive?
3. Can you specify A and B to get Shortest Job First? If so, what are the values of A and B? If not, why not?

• The virtual memory system, which uses a demand paging policy, has a miss probability of 10^-5 for the typical mix of processes that run in the system.
• The disk has an average seek time of 10 milliseconds, an average rotational latency of 4 milliseconds, and a bandwidth of 10 megabytes per second.
• Main memory has a size of 64M and a latency of 100 nanoseconds.
• The page size is 8K.

The effective access time is 1 - F x p, where F is the page fault penalty and p is the miss probability. The page faulty penalty F is the ratio of the time it takes to read from a virtual address that results in a page fault and the time to read from a virtual address when the page is already in physical memory.

What is the impact on the effective access time of this system for each of the following changes? Consider each change as being done to the original system; for example, change (c) is done with 100 nsec memory.

State and justify any assumptions that you find necessary to answer the question.
 

1. Replacing the main memory with memory that has a latency of 80 nanoseconds.
2. Replacing the channel controller to the disk with one that allows a bandwidth of 20 megabytes per second.
3. Doubling the amount of main memory to 128M.
4. Doubling the page from 8K to 16K.

• Allocate four buffers.
• Open two files for writing. The names are supplied as parameters to the program. We will denote these files as f1 and f2. The local file system supports exclusive access to files that are opened for writing. File f1 is opened before file f2.
• Read the first character of f1. If the first character is a '0', then allocate two more buffers and create a temporary file t (that is, a file that is local to the program and is given a unique name). Doing so makes use of two of the allocated buffers.
• Compute something fascinating and write different parts of the results to f1 and f2, and also to t if it has been opened. Doing so makes use of all of the buffers that the program has allocated.
• Close the files.
• Deallocate the buffers.

1. If multiple copies of the program are run, then deadlock can occur. Show a resource allocation graph that denotes such a deadlock state (Note that there may be more than one way deadlock can occur).
2. Explain how the program can be changed to use hierarchical locking in order to prevent deadlocks. You will need to change the way and the order that the program does allocations so that it obeys hierarchical locking.
3. Explain how the original program can be changed to use the Banker's Algorithm to avoid deadlock.
4. Explain how a deadlock detection scheme can be used with this program. The number of points you will receive for this part will depend on how efficient your deadlock detection scheme is. You do not need to address how to recover from the deadlock.
5. Which if the three methods do you think is the best approach? Explain briefly.

cobegin
int x = 0, i = 0, j = 0;
for (i = 0; i < 100; i++) x = x + 1;
||
for (j = 0; j < 100; j++) x = x - 1;
coend;