Hoare monitors

Michael DiBernardo, September 13th 2006

Slides

Submitted questions

• how do processes communicate or synchronize with one another with a condition variable when using this monitor mechanism?
• Is there no deadlock problem when multiple processes use multiple monitors? If there is not, why doesn?t the deadlock problem happen?
• Can monitors be implemented on a different level? Is it possible for each piece of hardware to have it's own monitor?
• If we extend the bounded buffer example to use an unbounded buffer, it start to look very similar to the consumer/producer example in paper#1. What are the differences between a mutex and a monitor?
• Hoare states that a signal operating immediately transfers executing to a single waiting thread, and details a "scheduled wait" policy. Why does he tie the particulars of scheduling policy so closely with a his concept of a monitor?
• How would Hoare's abstraction scale to deal a resource containing many sub-elements if we needed to synchronize access to both the sub-elements and the larger structure? For example - locking of an entire linked list, as well as per-structure locks for each list entry.
• What would be required to further generalize this concept from an OS concept to an OS supported programming language feature?
• I understand the meaning of those formula in part 3 and 4. However I am not familiar with the specific meanings for those mathmatics characters. For example, without context, I do not know the differences between the first fomula and the second one in part 3. I just want to know if this is a fixed format in such kind of papers. If yes, could you introduce some general knowledge about it ? Then I could understand it more easily in other papers.
• Could you give details of monitors used on Linux and Solaris operating system, especially those relative to head disk?
• The introduction of the "scheduled waits", introduces the possibility of infinite overtaking (i.e. starvation of a waiting process), and priority inversion. Does it make sense, at the level that monitors operate at (i.e. on a per resource basis) to allow for differing priorities, as opposed to the FIFO scheduling strategy the paper starts with?
• Monitors don't seem to offer the ability to test if the resource is busy. They merely schedule the the aquisition and release of the resource. Are methods to test for business (like pthread_mutex_trylock) necessary, or do they just make things more complicated? Would monitors benefit from having a public method for testing for waiting processes (i.e. the currently private 'condname.queue' page 553) method.
• On page 551 and 552 the author presents a proof that monitors can be implemented using P-V semaphores. Pseudocode is shown for both the  signal and wait operations of the monitor's condition variables. Do you think it would be possible to modify the given algorithms to allow signalling a waiting program from outside the monitor's critical regions? That is, modifying the algorithms to allow calling signal(condition) AFTER the monitor's mutex has been released.
• Why does the author decree that a signal operation be followed immediately by resumption of a waiting program  without possibly of an intervening procedure call from yet a third program (page 550, first column) ? If you enclose the calls to cond.wait() inside a while loop, such as "while (queue.isEmpty()) nonempty.wait();", why is it so important to make sure that no 3rd program can enter the critical section immediately after signal() is called and before a waiting thread has a chance to wake up?
• If monitors can be expressed equivalently as semaphores, then what are the advantages of this construct (over semaphores)?
• Did you laugh out loud upon reading principle #2 at the end of the paper? Specifically, how does one interpret this particular principle in 1974 terms? In 2006 terms?
• How do the principles presented compare to modern guidelines of how real time programming should be handled?
• Is it neat to notice principle #8 and how we take protected memory spaces for granted these days?
• Why avoiding the use of semaphores in order to significantly improve the implementation of monitors?
• How does the hardware help on the implementation of monitors?
• What are the benifits of using a buffer allocator? and what is the problem of merging to the slowest stream speed?
• What does the symmetry between the rules for signaling and waiting imply(the invariants)?
• In the pseudo-code for the bounded buffer example, why isn't the count decremented in the remove procedure ?
• How does a inbuilt scheduling method(for choosing which thread to wake up on a signal call) help reduce the amount of storage required for the monitors ?
• Why doesn't the release procedure in the buffer allocator monitor return the unused buffer address to the freepool set ? (It goes like freepool:=freepool -{b}, whereas in my opinion it should be freepool:=freepool + {b})
• The first question refers to Section 2. called Interpretation where Hoare shows how one can use monitors ot implement semaphores. The question is: How many semaphores would one use to achive the same implementation using only semaphores? I guess the next thing that one could ask is what would such an implementation look like?
• This question regards Section 3. called Proof Rules. And here is the question: The proof rule for waits as stated by Hoare is: invariant {b.wait} invariant & B. How can a process that suspends itself on b by a call to b.wait make sure that invariant & B happen? Who is actually in charge of making sure invariant & B does happen?
• In Section 4. called Example: Bounded Buffer what does l circle-with-a-minus 1 mean, and how is it connected to pointer addressing being modulo of N? In addition he has circle-with-a-plus that I also don't understand!
• This question is about the buffer allocator example in Section 6.1 Buffer Allocation. The question is: Why does the function release contain the following line: begin freepool := freepool - {b}; instead of the following line: begin freepool := freepool + {b}; It seems logical that b should be added back into the freepool once it is freed, rather than subtracted from it? I am confused.
• This question is again about Section 6.1. My question is: Why is it important or is it important that buffer b gets emptied before it gets released?
• General questions about terminology and the Bounded Buffer example: 6. What is a deadly embrace?
• Another question about Section 4: Who will make it certain that the allocated portions do not exhaust the memory before the address space inside of the buffer gets exhaused? Or are we to assume that each portion has the same size and that the sum of all portions is less than memory requested so that each entry in the buffer array does get an address? Do portions get written to the disk if they are too big for memory to hold?
• It seems that we've proved that semaphores and monitors are equivalent. Why use monitors?
• Monitors in practice appear to lend themselves easily to object oriented languages. Can I use monitors in a non object oriented language and why would I do so?
• Why don't the examples use mutex? For instance, in the bounded buffer example, isn't it possible for a call to remove to occur in the middle of a call to append (say, after lastpointer is incremented but before count is incremented)? Are the calls to P(mutex) and V(mutex) implied?
• In the third justification for the scheduled wait (page 553), to what storage are they referring? Is it the queue of waiting processes? I don't understand how this relates to scheduled wait.
• When you give a print command in Linux, does it actually use mutex and synchronisation features provided by the C programming language?
• Is a monitor a programming construct always implemented using semaphores?
• When is the semaphore 'urgent' associated with cond.signal operation not required?

Discussion recap

• Monitor in this context is a systems construct, not a programming language construct.
• Placing the resource handling in procedures abstracts details well from programmer, but may lead to surprising behaviour.
• We don't really like how priority was coupled with the monitor implementation.
• Many of the questions that arose about monitors will be addressed in subsequent paper readings.
• Mutex equivalence to semaphores and monitors was later demonstrated.