CSE 120 Winter 2001 Sample Questions

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


Consider the following definition of a symmetric semaphore:

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. monitor SymmSem {
    private:
    int s, max;        // 0 <= s <= max
    condition ltMax;   // s < max
    condition gtZero;  // s > 0

    public SymmSem(int s, max) {
        this->s = s;
        this->max = max;
        }

    public void P(void) {
        if (s == 0) gtZero.wait;
        s--;
        ltMax.signal;
        }

    public void V(void) {
        if (s == max) ltMax.wait;
        s++;
        gtZero.signal;
        }
    };
     

  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.

    3. No, there are no such problems. A problem solved with symmetric semaphores can be translated into one using general semaphores by using the monitor implementation above and then translating it to general semaphores. And, one can use symmetric semaphores to implement general semaphores by using the same translation used to implement general semaphores with binary semaphores.


You are heading the programming group of a large Northwestern software company. One of your employees suggests that a new concurrency construct called tagged critical regions is all that one needs for writing concurrent programs.

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

critical v1, v2, ..., vk; statements; end_critical

where v1, v2, v3, ... 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:
 

critical x, z; critical x, y; critical y, u, v;
S1; S2; S3;
end_critical;  end_critical;  end_critical; 

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. Declare a binary semaphore for each tag, and give each such semaphore an initial value of 1. Prefix each tagged critical region with P operations on the corresponding semaphores in lexiographic order to avoid deadlock (hierarchical locking). Affix each tagged region with the corresponding V operations, in any order.
     

    P(x);  P(x);  P(u);
    P(z); P(y); P(v);
    S1; S2; P(y);
    V(x); V(x); S3;
    V(z); V(y); V(u);
    V(v);
    V(y);

     
  2. Is your employee correct: are tagged critical regions as powerful as semaphores or monitors? Explain.

    3. No, he's not correct and they're not as powerful. One can't implement semaphores with tagged critical regions without using busy waiting. There is no way to conditionally block a process.


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

Consider a scheduling algorithm whose priority function is based on dynamically changed priorities. Larger numbers mean higher priority; all processes are given a priority of 0 when they enter the system. When a job is waiting for the CPU (i.e., in the ready queue, not running) its priority changes at a rate A; when it is running its priority changes at a rate B. The parameters A and B can be set to give many different scheduling algorithms.
  1. What is the algorithm that results if A=B and is positive? FCFS.
  2. What is the algorithm that results if A=B and is negative, and the scheduler is non-preemptive? LIFO.
  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?

    4. No, it cannot. The priority of a job depends on its deadline. This scheduling algorithm is based only on blocking time and accuumulated execution time.

Consider the following properties of a computer system: You can assume that there is no cache: all references to physical memory take 100 nanoseconds. You can also ignore the effects of TLBs.

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. Increases F by a factor of 100/80 = 1.25. This increases the effective access time.
  2. Replacing the channel controller to the disk with one that allows a bandwidth of 20 megabytes per second. Decreases the effective access time, but not by much. The numerator of F is dominated by the seek time and rotational latency (14 msec plus 0.1 msec to read a page with the slower channel vs. 0.05 msec to read a page with the faster channel).
  3. Doubling the amount of main memory to 128M. Probably no change. The system wasn't thrashing before and so physical memory was not a bottleneck.
  4. Doubling the page from 8K to 16K. Probably decrease the effective access time. The value of F increases slightly from 14.1 msec to 14.2 msec. But, our system does not prefetch (it uses demand paging) and doubling the page size is a cheap way to do one-page prefetching. The miss probability will probalby become significantly smaller thereby offsetting the small increase in F.

Multiple copies of the following program are run concurrently on the same computer: Assume that the buffers are allocated from a buffer pool that initially contains twelve 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). There are lots of ways that processes can deadlock in this program. Here's a simple one: P1 has parameters f1 = "B" and f2 = "A" while P2 has parameters f1 = "A" and f2 = "B".
                    |--------->[ File "A" ]---------|
                    |                               |
                    |                               |
                    |          ____________         |
                    |         |            |        |
                    |         |            |        v
                   P1<----4---|     12     |---4--->P2
                    ^         |            |        |
                    |         |____________|        |
                    |                               |
                    |                               |
                    |                               |
                    -----------[ File "B" ]<---------
  1. 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. The process opens files in lexiographic order, e.g. open(min(f1, f2)); open(max(f1, f2)); Then, the process requests six buffers.
  2. Explain how the original program can be changed to use the Banker's Algorithm to avoid deadlock. Each process has a maximum claim of one on each file in the system and a maximum claim of 6 on the buffer pool. These values are used with the Banker's Algorithm in the standard manner.
  3. 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. Have a process request one buffer at a time. Given single unit requests, a deadlock is equivalent to a knot in the expedient resource allocation graph. Have the processes jointly maintain such a graph. When a process blocks waiting for a request, it tests for a knot.
  4. Which if the three methods do you think is the best approach? Explain briefly. They all have their problems. Hierarchical locking limits the number of processes that can run at any time to two, since between the two they will exhaust the buffer pool. A similar problem occurs with the Banker's algorithm with respect to the buffer pool, but a worse problem occurs with the files: once a process has one file open, the Banker's algorithm considers any resource allocation state in which a second process has a file open to be unsafe. The deadlock detection scheme allows the most parallelism (which is three programs running simultaneously), but it has the bad effect of causing some programs to be aborted while running.

    5. If it is rare to run concurrent copies of the program, then the deadlock detection approach is perhaps the best (or, one could use the Unix ^C approach!) If it is common for multiple copies of the program to be run concurrently, then the hierarchical locking approach might be the best since it avoids breaking deadlocks, allows more concurrency then the Banker's algorithm, is simpler to implement, and has lower overhead.


Some operating systems support the fork primitive but not the join primitive. That is, there is no explicit primitive that allows a process to wait for a child process it has forked to terminate before continuing. Show how a join can be implemented using semaphores. Have fork return a record that contains a binary semaphore with an initial value of 0. The join primitive executes a P on this semaphore. When the child process terminates, it executes a V on this semaphore.

Is the LFU (least frequently used) page replacement susceptible to Belady's anomaly? Explain. No; the frequency that a page is referenced is independent of the number of page frames, and so it can be represented as a stack algorithm.

Is the LIFO (last-in, first-out) page replacement susceptible to Belady's anomaly? Explain. No. Consider a reference string s that contains d distinct pages. Remove all stuttered references (that is, replace all subsequences of references to the same page with a single reference) since repeated references do not result in page faults. Assume that there are f page frames. The first f-1 distinct pages in s will all page fault on their initial reference and then remain in page frames. The remaining d - f - 1 pages in s will page fault with every reference.

If we increase f then the length of the reference string that results in page faults will be less. Hence the total number of page faults will decrease.

This is somewhat tricky because LIFO is not a stack replacement policy! But, not all non-stack replacement policies can exhibit Belady's anomaly.


A Unix inode is relatively small; 64 bytes is a common size. It has been suggested that inodes be enlarged so that the first block of a file be stored in the inode. Do you think that this is a good idea? Explain. It's not too bad an idea: it guarantees that the first block of the file will be close to the file's metadata. It doesn't increase internal fragmentation for most files which are small anyway. It spreads inodes apart somewhat reducing their locality somewhat, but since it is rare that one references inode i+1 having just referenced inode i, this loss of locality is not an issue.

Give a reference string and a number of page frames that show that FIFO can, on occasion, result in less page faults than LRU. As well as the reference string, show for each reference which pages are in page frames for both of the policies. Let the reference string be 1 2 1 3 2 and assume that there are two page frames. FIFO has three page faults while LRU has four.

FIFO:  1* 2* 1  3* 2        LRU:  1* 2* 1  3* 2*
       1  2  2  3  3              1  2  1  3  2
          2  1  2  2                 1  2  1  3


Consider the following concurrent program:
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;
What are the possible values of x after the coend? Explain. x can have a value between -100 and 100. Suppose that we wish x to have a positive value k. Alternate between the two processes 100 - k times. At this point x is zero; the first process increased it to 1 and the second decreased it to 0.

Interdigitate the loops as follows:

The first process fetches x;
The second process fetches x, decrements it, and stores it back;
the first process increments the value it fetched and stores it back.
Each time the two processes do this the value of x increases by 1.

A similar construction can be used for negative values of k.