Comp 374 study guide answers

=========================================================

1. semaphore sync = 0;

   P1:
	print("first");
	V(sync);

   P2:
	P(sync);
	print("second");

=========================================================
 
> 2. Here is an incorrect solution for the infinite-buffer producer/consumer
> problem.  There are two semaphores, mutex (for mutual exclusion) and count
> (representing the number of items in the buffer).
> 
> producer() {                          consumer() {
>    while(1) {                            while(1) {
>       produce();                            wait(mutex);
> 	wait(mutex);                          wait(count);
> 	append();                             take();
> 	signal(mutex);                        signal(mutex);
> 	signal(count);                        consume();
>    }                                     }
> }                                     }
> 
> What can go wrong?
 
wait(count) is *inside* the critical section bracketed in
consumer() by wait(mutex)...signal(mutex). If count==0 then
wait(count) will block, **remaining in the critical section**.
producer() will never be able to get into the critical section,
and will never be able to execute signal(count).

=========================================================
 
> 3. The following example is taken from the TCP network transport protocol.
> Whenever the sender sends data, the receiver sends an ACK (acknowlegement).
> The receiver can also send the sender a message to stop transmitting
> (eg so the receiver can process its backlog). Such stop-transmit messages,
> and ACKs, are not themselves acknowleged. After a stop-transmit is sent,
> and the receiver is again able to process data, it sends a resume-transmit
> message to the sender. However, as the sender may not at that time actually
> have anything to send, no ACK of a resume-transmit is sent.
> 
> Explain the deadlock that results if the resume-transmit message is lost.
> 
> (Real TCP has a method to deal with this).
 
The sender is waiting for the resume-transmit, which is *not* acknowledged
and so can't be retransmitted if lost (the receiver would have no
way of knowing it was lost!)

The receiver is waiting for data. TCP always has the receiver wait
patiently for data; the sender sends data only if there is data to
send. The idea is that an idle connection should be truly *idle*.

=========================================================
 
> 4. Describe one method by which an operating system can have two (or more) 
> processes simultaneously in memory without the processes being able to interfere 
> with each other. Describe all necessary *hardware* features that the underlying 
> CPU must support to make your method feasible.

The crucial phrase above is WITHOUT THE PROCESSES BEING ABLE TO INTERFERE
WITH EACH OTHER. This should have more explicitly stated that there
was a memory-protection mechanism in place so that the processes
could not change each other's memory.

The hardware features needed are: 2-level supervisor/user mode and
some sort of memory protection (virtual memory or something simpler).
The instructions that handle I/O and manipulate the memory protection
must be restricted to supervisor mode.

There must also be a mechanism to get the CPU back into supervisor mode,
eg interrupts.
 
=========================================================
 
This problem shouldn't have been on the study guide; sorry.
Dining Philosophers *won't* be on the exam.

> 5. Consider the dining philosophers problem. Suppose the following 
> algorithm were implemented, which deals with potential deadlock
> by releasing all resources and waiting for later:
> 
> 	when philosopher wants to eat, repeat until success:
> 	 L: wait until left fork is available, and take it
> 	    try to take right fork
> 	        If it is available, success!
> 	        If *not*, put down left fork, wait 1 minute, goto L:
> 
> How can this fail? Is failure *likely*? What other problem do you see?

This comes *close* to working. Deadlock can occur only if the timing is
exactly coordinated: Every minute, exactly on the minute, every
philosopher picks up the left fork, discovers the right is held by
the right neighbor, puts down the left fork, and sleeps until the
next minute. Such timing is improbable, and can be made *extremely*
unlikely by chosing *random* times to wait.

However, the method also introduces extra waiting time, which 
is inefficient. A philosopher's forks may both be available,
and the philosopher may be hungry, but there is no way to wake 
the philosopher up until the wait time expires!
 
=========================================================
 
> 6. See the homework problem 5.11 about FCFS v SCAN disk algorithms

=========================================================

> 7. Explain how NT and Unix each handle running a CPU-bound process
> together with an I/O-bound process, without having the latter starve.

Unix maintains a dynamic recent-average-cpu-usage value for each process;
the lower this value the higher the priority. Thus, a process that
has spent time doing I/O wait has a higher priority, and will
get more CPU. As it gets more CPU, its priority falls, and the
CPU-bound process gets a chance. Alternatively, if the I/O-bound
process simply spends time waiting, the CPU-bound process also
gets a chance.

NT simply boosts the priority of any process that is returning
from an I/O wait.

=========================================================
 
> 8. Suppose three processes may wish to execute a critical section cs().
> Explain how to use one counting semaphore so that at most *two* processes
> may enter the critical section at a time.
 
semaphore dual = 2;

Then all three processes need:
	wait(dual);
	cs();
	signal(dual);

If one process tries to enter cs() then dual decrements to 1.
If another tries to enter, dual decrements to 0.
The third process, though, would now block.

=========================================================
 
> 9. Suppose N is a global variable, initially 0, and suppose two 
> processes both execute
> 	P() {
> 	    int i;
> 	    i = N;
> 	    i++;
> 	    N = i;
> 	}
> 
> What are the possible final values for N? For each value, describe 
> an interleaving of the two processes to yield this N.
 
N can end up either 1 or 2. N is 2 if the two executions of P are done
one after the other. N is 1 if we have
	P1		P2
	i=N
	i++		
			i=N
			i++
			N=i
	N=i