1. Explain why busy-waiting mechanisms for critical region access are bad. Describe a mechanism that improves on busy waiting.

   ---

   A process spinning in a busy-wait loop wastes CPU time. A process cannot do anything until it gains the critical region, so it essentially burns CPU time until it does.

   A scheduler-based mechanism for critical region access is an improvement over busy waiting because as soon as a process begins its wait for the critical region, the scheduler can yank it from the CPU until it actually has permission to enter.

   ---

2. Explain how to use message passing to solve the producer-consumer problem. Don't go into code-level detail, just describe the general approach.

   ---

   The producer can send its data in a message to the consumer. This eliminates the need for the producer and consumer to synchronize over access to a shared buffer. See Section 2.2.7 of the text for more details.

   ---

3. Explain at least two different ways in which you might apply two-level scheduling in a multi-processor system.

   ---

   One way is as we discussed in class: one scheduler between cpu and primary store and the other between primary store and secondary store. These two schedulers are different (the CPU scheduler is, in some sense, faster and more sensitive than the disk scheduler), but the schedulers are related in that they both deal with processes.

   Another way in which two-level scheduling might apply is in assigning processes to processors. Each process that enters the system needs to be assigned to a processor (or, if you like, the processes on one processor may need to be redistributed to improve load balancing). A scheduler that assigns processes to processors is different than a scheduler that shuffles processes into and out of a particular process, but they are related in that they both deal with processes.

   ---

4. A colleague of yours thinks it would be really cool to develop a scheduler that moved processes into and out of the CPU on every instruction (that is, the scheduler is a round-robin scheduler with a quantum equal to the length of one instruction execution), because then there would be a lot of processes executing all the time. Explain whether you think this idea is good or bad. Assume a general-purpose hardware architecture.

   ---

   It is a bad idea. The problem is, even with a hardware assist, it takes more than one instruction to switch contexts. Executing one instruction per context switch means at least a 100% overhead, and at least half - and probably significantly more than half - your computing resources go towards running the operating system.

   ---

This page last modified on 12 October 2000.