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

0: In the switch code, an interrupted program when scheduled usually
restarts from the label 1f. But there is atleast one case in which a
program starts executing from somewhere else. Give atleast one such
case.									10

1: The pthread mutex functions in Linux are not async-signal safe
ie. they should not be called from a signal handler; calling
pthread_mutex_lock or pthread_mutex_unlock from a signal handler may
deadlock the calling thread. Explain.					15

2: Explain what convoys are and how they are created. How does one
schedule a system so that convoys are not formed?			15

3: Assume you have to catch a bus but there is no info when the bus
will arrive (may be immediately or never also!). An offline alg has
the info about the bus arrivals, etc. whereas an online alg has none.
Assume that the time to reach your home is same by bus or auto but
auto is k time more costlier than by bus and that your time is worth
r per hour. If your online alg has to be no worse than 2 times the
best an offline alg can do (ie. 2-competitive), how long should you
wait at the bus stop before you hop into an auto?			10

Solaris has an adaptive mutex. It spins for a while and then switches
to sleeping. Formulate the problem as a c-competitive alg.		10

4: Write down the process tree (parent and children relationships) for
the following shell command:
   zcat x.Z | grep hello | more
How many processes are there in all? What is the best order for scheduling?
In what order does it happen in Linux in the above case?		15

5: Explain how Linux 2.4 gives interactive jobs better service? Give
briefly the change in scheduling in Linux 2.6. How can you fool
Linux into giving a "CPU hogger" program better service? Why is it
hard to give "fair" service to everyone?				12

Assume that there are 4 processes in the system: mpeg, X11, a batch
and an interactive process. Show a plausible scheduling in Linux
2.4. When will any one of these programs not get good service?
Will it perform very differently in Linux 2.6?				13