Comp 374 Study gude and sample exam	October 11, 2000	Dordal

The exam will be October 18, 2000.

We covered up through chapter 8. Some of the sections
are general background knowledge. Here are the chapters and what
specific sections or information you should know:

Ch 1, general batch v timesharing, disk devices.
Ch 2, mainly 2.3 on processes.
Ch 3: 3.3 on CPU modes, summary of 3.2
Ch 4: computer organization, *devices* and interrupts (4.4, 4.5)
Ch 5: device management: direct v interrupt I/O (5.1), device drivers,
	"top half" v "bottom half" (5.3), optimizing disk access (5.4)
Ch 6: Mainly the process stuff in 6.4 and 6.6.
Ch 7: Cpu scheduling. 7.1-7.4. Know about preemptive v nonpreemptive,
	FCFS, SJN, RR, multi-level queues, Unix v NT.
	(You will *not* have to memorize acronyms like SJN;
	I'll spell it out "Shortest Job Next".)
Ch 8: deadlock, concurrency, semaphores, producer/consumer, reader/writer.

I will *give* you on the exam the definitions of the semaphore
P() and V() operations, and one sample mutex usage.

The main *concepts*, in rough order of importance, are:
	1. process basics
	2. concurrency (semaphores etc)
	3. process scheduling
	4. device drivers
	5. disk scheduling (disk device drivers)

Here are some sample questions.

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

1. Suppose one has two processes. The first prints "first", and the
second prints "second". Use a semaphore to synchronize the processes
so the output is in the proper order.

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

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?

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

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).

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

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.

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

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?

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

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.

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

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.

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

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.