Homework 2

Short-Answer Problems

These can be answered in a sentence or two, and are intended to reinforce important points.

1. (10 points) In FreeBSD, what is the ZOMBIE state? What causes the process to exit that state?
2. (5 points) In FreeBSD, how does the system tailor the short-term scheduling algorithm to favor interactive jobs?
3. (5 points) What are the three conditions that any solution to the critical section problem must meet?

Long-Answer Problems

These questions require some thought and longer answers than the short-answer questions. They are intended to have you use the concepts discussed in class, to be sure you understand them and can work with them.

1. (20 points) A binary semaphore is most commonly defined as a semaphore whose integer value can range only between 0 and 1. Implement the usual type of semaphore using binary semaphores.
2. (20 points) The sleeping barber problem takes place in a barber shop. The barber shop has one barber, one barber’s chair, and 5 chairs for waiting customers. If there are no customers, the barber sits in the barber’s chair and falls asleep. When a customer comes in, if there are no other customers, he wakes the barber, sits in the barber’s chair, and the barber cuts his hair. If customers arrive while someone is having his hair cut, they sit in the chairs for waiting customers, if any are empty, or leave, if all are full. Write a program using semaphores to solve the sleepy barber problem.
3. (20 points) An operating system designer has proposed a multilevel feedback queueing scheme in which there are five levels with round robin scheduling on each level. The quantum at the first level is 0.5 seconds, and each lower level has a quantum twice the size of the quantum at the previous level. A process cannot be pre-empted until its quantum expires, and then it is moved to the next lower queue (unless it is in the lowest queue, of course). If the process does I/O, upon completion it is returned to the queue from which it left. The system runs both batch and interactive jobs, and these, in turn, consist of both CPU-bound and I/O-bound jobs.
   1. Why is this scheme deficient?
   2. What minimal changes would you propose to make the scheme more acceptable for its intended job mix?
4. (20 points) Measurements of a certain system have shown that the average process runs for a time t before blocking on I/O. A process switch requires a time s, which is effectively wasted (i.e., it is overhead time). For round robin scheduling with a quantum q, give a formula for the processor utilization for each of the following:
   1. q = ∞
   2. q ≥ t
   3. s < q < t
   4. q = s
   5. q nearly 0

Extra Credit Problems

1. (10 points) Consider a computer that does not have a test-and-set instruction but does have an instruction to swap the contents of a register and a memory word in a single indivisible action. Can that be used to solve the critical section problem? If so, how; if not, why not?