Session 7: Process switching and synchronization

Textbook: Section 2.2

Process states

Synchronization

types
examples
definitions

Techniques

disabling interrupts

Process states

Moreover, Posix needs to run all the processes simultaneously - not so easy if, like the Intel CPU, you can only do one thing at a time. (Actually, that's a bit odd: Recent Intel CPUs provide better performance by doing several things at a time, but they go to great lengths to provide the illusion that it can only handle one instruction at a time. And then the OS goes to great lengths to provide the illusion that it can run many processes on the same CPU. There's some performance being lost there.)

To provide the illusion that many processes are running simultaneously, the OS implements multiprogramming. The idea behind multiprogramming is that the OS will rapidly switch processes on and off the CPU, so fast that the user can't tell.

To support this, the operating system maintains a list of processes currently vying for the CPU. At any time, only one process can be running. But many may want it.

Each process has one of three states:

running: running on the CPU
ready: waiting for the CPU
blocked: waiting for something else (like another process's behavior or a hardware event)

The OS switches processes between the running and ready states. A running process can switch itself into the blocked state, and the OS may ``wake up'' a process by switching from blocked to ready state.

Conceptually, this is what happens. But there is a complication: The CPU can only run one process at a time. It can't both run a process and run the OS. So how does control transfer from a running process into the OS?

The answer is that the OS will set up the clock to trigger a hardware interrupt after a fixed amount of time. When that interrupt occurs, then control transfers into the operating system, and it can take it from there. (Of course, if the running process triggers a software interrupt first, then the OS gets control earlier.)

So what exactly happens when an interrupt occurs? The following shows what happens in Minix, and it's similar on other operating systems.

1. The CPU places the current program counter on the stack.
2. The CPU looks up where the first instruction of the
         interrupt handler is and jumps there.
3.   The assembly code saves the registers in the table.
4.   The assembly code sets up the stack for the interrupt handling.
5.   The assembly code transfers into a C function.
6.     The C function does any immediate handling needed (usually
         buffering the input).
7.     OS moves the waiting process from blocked state to ready state.
8.     OS decides which process to run next.
9.     The C function returns to the assembly code.
10.  The assembly code restores the registers for the new process.
11.  The assembly code jumps to the stored as its program counter.

Synchronization

Types

One important issue that arises when you have multiple processes that share resources is that they are going to require some communication.

The communication can be categorized into two basic types: competitive synchronization, when multiple processes are vying for the same resource that cannot be shared, and cooperative synchronization, when one process wishes to send information to another. These two types of problems are similar, in that they involve interaction between the same processes. But they are also different: The requirement for competitive synchronization usually derives from two independently-developed processes, and the need for it rarely occurs by design. But cooperative synchronization is usually by design.

Examples

An example of competitive synchronization comes from print spooling. When you print a file in Unix, the file is actually copied into the printer's spool directory in the system. There is an independently running program (called lpd) that runs in the background looking for files in the printer's spool directory.

The competitive synchronization problem arises from what happens when multiple programs might try to print simultaneously. What file name should they choose? Let's say the order of the events is as follows: Program A decides on a file name, then program B decides on the same name, then A creates its file, and finally B creates its file. The problem is that A and B may happen decide on the same file name.

(Actually, there is a simple solution to this particular problem: Each process decides on a filename with its process id attached. For example, if A's process ID is 9123, it chooses a filename of the form X.9123.)

An example of cooperative synchronization comes from Unix pipes: If you have two processes, and the output of one (called the producer) is getting sent as the input to another (called the consumer), then they need some form of synchronization so that the consumer doesn't consume more than the producer has produced. This is the producer-consumer problem, one of the most fundamental problems in process synchronization.

Definitions

When you have a segment of code that is sensitive to these synchronization problems, that segment of code is called a critical section. Generally, a programmer should be able to mark the critical sections of code in a simple way, indicating somehow to the computer that it should not allow other processes to execute their critical section while another process is within a critical section. This is called the mutual exclusion property of critical sections.

This isn't really adequate, however, because programmers might lazily put the entire program within a critical section, blocking out all other processes as they reach their critical sections. So in practice there must somehow be different classes of critical sections.

Ways of implementing critical sections need also to avoid starvation: Every process should eventually execute its critical section. For example, say I am a process who wants to cross the road to get to the grocery store. But cars going down the road are also processes. If I have a policy of always yield to any car within 300 yards, then I could starve if there is a continuous stream of cars. (It happens to me every morning when all the early-morning commuters are going down Minnesota Street when I need to cross it to get to the bus stop. Eventually I have to force the cars to stop so that I'm not starved of my students' presence.)

Techniques

We're going to look at several approaches and see why none of them are adequate. We'll conclude finally with an adequate solution.

Disabling interrupts

  void lock() {                  void unlock() {
      disable interrupts;            enable interrupts;
  }                              }

One simple way of allowing processes to mark their critical sections is to disable interrupts in the hardware. Since once the interrupts are disabled, nothing can stop the process from doing its work, it is safe to do whatever it needs, and then it can enable interrupts once it exits its critical section. Since the OS only switches processes when it gets an interrupt from the clock, the critical section can't be split between time slices.

The problem with this is that it can be catastrophic if a process fails to enable its interrupts again, effectively halting the CPU to let the program do everything. Also, disabling interrupts is ineffective in a multiprocessor system, where disabling interrupts only seizes the processor that executes the instructions.

Typical single-processor OSes use this approach - but only within the OS itself. This is because we trust OS to be correct. (If it is not, the whole system is messed up.) But we cannot yield the same trust to user processes, which are quite likely buggy.