Monitors: An Operating System Structuring Concept

Hoare74

Goal of OS is to share resources amongst many programs.

Separate schedulers should be created for each class of resource.

Each scheduler contains local data + procedures that programs may use to acquire and release resources. Such a collection of data + procedures is a monitor. Only one program may enter a procedure of a monitor at a given time.

Hence, only one program may modify local data of the monitor at a given time. If more than one program attempts to enter at the same time, only one will succeed, and the remaining programs will remain on a queue.

Since monitors are used to provide access to resources, there may be cases in which a monitor procedure has been entered, but the resource is not available to be granted yet. Hence, we need wait & signal operations. If a procedure calls wait, the calling program will block until some other procedure calls signal. When wait is called, the “lock” on the monitor is released, such that another program may enter a monitor procedure that will call signal. When a procedure calls signal, the “lock” on the monitor is also released, and another program that previously called wait is run immediately.

Wait and signal are operations on condition variables (ie. Condvar.wait(), and condvar.signal()) such that if there are multiple reasons for waiting, they can be modeled appropriately in a single monitor.

Semaphores can be implemented using monitors, and monitors can be implemented using semaphores. (The latter is a little tricky, and both are recommended as exercises.)

Example: Write a bounded buffer (“queue”) that is accessible by producers and consumers using a monitor.

Extensions

Hoare originally assumes that when a signal takes place, the program waiting the longest is the one that is resumed. In a later section, he extends wait such that it can be passed a priority p. (i.e., condvar.wait(p)). Then, when a signal takes place, the scheduler will resume execution of the program that is blocked with the lowest value of p. To illustrate usage of this, he develops an alarmclock monitor, where each program that wants to be awoken in n cycles calls wakeup.wait(now+n). A tick procedure is called every time quantum and calls signal. Due to the priority scheme, those programs who desire to be woken up the earliest will resume execution when tick calls signal.

Monitors do nothing to prevent deadlock and livelock, and it is the responsibility of the programmer to prevent such problems.

Examples: The paper provides several other examples of using monitors and condition variables to solve common synchronization problems to prove their utility. Some of these problems are buffer allocation, disk head scheduling, and multiple readers/writers to a file.

Note of interest: Every class in Java defines a monitor. A synchronized method in a class becomes a monitor procedure. Every object is allocated its own mutex, and that mutex is locked whenever a thread enters a synchronized method. The class as a whole is also allocated its own mutex, and that mutex is locked whenever a static synchronized method is called. Every Java object also has a condition variable associated with it. When wait() or signal() are called in a method, the wait or signal takes place on the condition variable associated with the object. Wait() and signal() calls can only be made in synchronized methods. The wait() method in the class Object is overloaded, and has a version that takes an integer, but this is different than the priority wait extension that Hoare suggests. In addition, I do not believe that the Java scheduler guarantees that when signal is called a thread that had previously called wait immediately runs, but I could be wrong about this.

One big advantage of monitors over semaphores is that the merge will with program structure, becoming like classes in programs. Semaphores, by contrast, are spread all over a program.

Questions:

Should signal be required to be the last call in a monitor procedure?

Should monitors that provide access to resources be developed such that they all make independent decisions about whether to grant a resource, or should they be developed to take into account the utilization of other resources as well?

Interesting quote for debate: “Do not seek to present the user with a virtual machine that is better than the actual hardware; merely seek to pass on the speed, size, and flat un-opinionated structure of a simple hardware design.”

Boundedbuffer: monitor

Int head, tail;

Int [] buffer = new buffer [SIZE];

Condvar full;

Condvar empty;

Void append (int value) {

If ((head+1) % SIZE == tail) full.wait();

buffer [(head+1) % SIZE] = value; head= (head+1) % SIZE;

Empty.signal();

}

int remove () {

int value;

if ((tail+1) % SIZE == head) empty.wait();

value = buffer[(tail+1) % SIZE]; tail = (tail +1) % SIZE;

full.signal();

}