Midterm Exam (Oct 5, 2005) 3:30pm-5pm OS Course (K. Gopinath)

0: Consider a concurrent program with m processes, each of n atomic
actions. How may interleavings are possible? If m=n, give an approx answer
using Stirling's formula. (n! approx = sqrt(2.pi.n) (n/e)^n)			15

1: IBM mainframes have an atomic compare&swap instruction:
	
   csw(int a, b, c, cond): < if (a==c) {c=b; cond=0} else {a=c; cond=0} >

Use this inst to develop a solution to the critical section problem. That is,
give the coe for lock and unlock using csw.

(Hint0: Think of the test&set solution!)
(Hint1: To get started, think first about which variable a, b, c
could represent the locked condition. For example, b cannot be the
lock variable as it is read but not set! Then decide how a, b, c should
be initialized. There may be more than one way to initialise a, b, c so
that a locking function is possible. If so, give all the 
possiblities.)

The above code can be costly on a SMP. Why?					25

(optional/extra credit: Can you develop a test-and-test-and-set style
locking using csw? 5)

2: In the 2-Peterson alg, the order of initialization inside the while
loop is important. Give the incorrect version and demonstrate it.

What feature of the C language is necessary so that the code is correct?

In Bakery alg, a seemingly "redundant" stmt is necessary for correct
execution. Explain how this "redundant" stmt helps wrt
ensuring mutual exclusion.							15

3: Why is that resolving GOT entries is different than for PLT entries?		10

When is the complexity of dynamic libraries not suitable? When is not
advisable to use dynamic libraries? (diff answers for each!)

4: What is an invariant? Why do we need to "weaken" the invariant sometimes?	 5

5: When is the fork+exec model sutiable? When is it problematic?		 5

   What happens in the following?						10

   main() {
   	
	if (fork()==0) {
	  execl("a.out", 0);
	  printf("exec failed\n");
	}
   }

   a.out is the result of compiling the above program.

6: The read() and write() interfaces are often not suitable when more than one
process is using a file. What is the problem? How can they be fixed?		 5

7: In the design of monitors, what are the possible scheduling options
after a process does a signal? What are the positive and negative aspects of
each design? What is the model followed by Java?				 5

8: Explain how semaphores solve the producer-consumer problem.			 5