While re-visiting to recall the differences between Semaphores and Monitors, I came across one of my OS class homework where I had written a summary on Monitors. So I thought I may as well blog about it.
Author: C. A. R. Hoare
What is it about?
- One of the major problems in building an operating system is to allow sharing of computer installations among different processes that may make unpredictable demands upon its resources. The paper attempts to address this issue by introducing the concepts of “signal” and “wait”.
- Creating resource allocation algorithms for different kinds of resources can be a challenge for a developer. There wasn’t an easy way to construct separate schdeulers for each class of resource. The paper introduces the concept of monitors that attempts to solve this issue.
- The paper also talks about the problem where multiple processes are trying to access the same resource and what can be done to prevent this race condition.
- The author has built upon the work done in the paper “Proof of correctness of data representations. Acta Informatica” by Hoare.
Some key contributions
- The paper talks about monitors – a synchronization structure. A monitor is a class like structure that contains data and functions. One significant property of monitors is that only one program may be executing a monitor procedure at any given point in time.
- The paper demonstrates the usefulness of monitors in structuring operating system designs. Monitors provide an effective way to enforce synchronization of processes (like critical sections).
- It also introduces the concept of condition variables. The condition variables stop one process to acquire resources being used by another process. It creates a queue of processes waiting in line to acquire the resource.
- “Signal” and “wait” operations are also introduced in the paper. Like the name suggests, “signal” means resume the execution of a process waiting in the queue, while “wait” is used to cause a delay in the execution of a process.
- How to implement semaphores using monitors is also described in the paper. Monitors are powerful like semaphores but provide a higher level of abstraction by providing data and code encapsulation.
- Introduce a new type of variable called “condition” for cases where there may be more than one reason for waiting and they need to be distinguished by both the waiting and the signalling operation.
- The paper talks about how semaphores can be implemented using monitors and vice-a-versa. They also provide a proof that the monitor condition concepts are not any less powerful than semaphores and that they can be used for all the same purposes.
- The paper makes some good suggestions towards the end and one of them is “Never seek to make an optimal decision; merely seek to avoid persistently pessimal decisions.” This observation calls for the need of good scheduling algorithms and the paper presents one.
The above is only a high-level summary and doesn’t contain all the details mentioned in the paper. For a thorough review, please go through the entire paper. If you have any questions, feel free to leave a comment.