Talk:Monitor (synchronization)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing  
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

Hi guys, I added the bit about Mesa vs. Hoare semantics, but was logged in anonymously. Just wanted to put a name to the edit. I'm not sure if it's really the most elegant way to display the information; does anyone have any suggestions? --Voorhies 22:22, 7 March 2007 (UTC)

Hi, I was just wondering, is there some way that this page can appear when one searches for "java monitor"? Currently the Javan Rhinocerous gets a higher relevancy then "concurrent programming languages" when using that search term, and this page doesn't appear at all. Thanks! Nekonobaka

A good overview article, but the paragraph "In most modern implementations,..." is a bit misleading to my mind. This "modern" monitor way is the sematics of Java Programming Language. For some reason (perhaps speed which is a bad argument in safety critical systems) they did not follow monitor semantics defined in 70's but made their own. This causes much confusion (in this very page the queue examples do not work correctly if they are to be implemented in java).


Perhaps this page should tell that there are three semantics in use for monitors: hoare (signal-and-wait), mesa (signal-and-continue) and Java (the "modern").


I don't think that "modern" is a standard term for either signal-and-continue (as the article stands now) or for Java semantics (as proposed). I'd suggest dropping that word. Also there are a few other semantics that could be mentioned. Theodore.norvell (talk) 14:40, 26 August 2008 (UTC)


"C# does not have monitors as a feature of the language". We-ell. C# has a "lock" mechanism which is directly analagous to Java's synchronized mechanism; it happens that it's implemented using the Framework's Monitor class internally (see http://research.microsoft.com/~birrell/papers/ThreadsCSharp.pdf ), but any hypothetical "free-standing" C# implementation (i.e. one not tied to Rotor, .NET FX, Mono, DotGNU, etc.) would have to have an equivalent mechanism. As such it seems to me that C# probably does have built-in monitors, at least to the same extent as Java does. DrPizza 18:07, 9 October 2005 (UTC)

Condition variable[edit]

I think that 'Condition variables' can live without a monitor. If that is right, why Condition variable redirects here?

You're mistaken. Condition variables were developed specifically for monitors, and I've never heard of anyone recommending their use outside that context. Gazpacho 04:30, 14 April 2006 (UTC)
condition variables are used all over the place. even with java, for example, every object has a condition variable built in with the wait(), signal(), and signalAll() methods supported at the Object class. 68.83.85.175 00:25, 6 November 2006 (UTC)
Condition variables were introduced for use with monitors, but they are definitely useful in and of themselves. By way of reference, none of the pthread condition variable man pages mention the word "monitor". The key behavior of condition variables, allowing a single thread to signal multiple waiting threads, is not monitor-specific. I don't know if that means a condition variable is worthy of its own article, but they are perfectly okay to use outside monitors. ScotS (talk) 23:42, 12 December 2007 (UTC)
In pthreads, the mutex takes the role of the monitor. Condition variables are associated with some other lock: In pthreads it is a mutex, in monitors it is the monitor lock Theodore.norvell (talk) 14:40, 26 August 2008 (UTC)

I think the key thing that is missing here is the notion that a condition variable is (or ought to be) associated with some boolean expression. This is what makes programming with monitors effective. When I have time, I'd like to add that and also make the use of invariants clearer. Any objections? Theodore.norvell (talk) 14:40, 26 August 2008 (UTC)

Monitors and condition variables are different concepts. The PThread condition variables are not monitors, because it is for example possible to use multiple cvars with the same mutex lock. Also, in a monitor, every operation is mutually exclusive, which rules out typical cvar operations such as signal_all(). Condition variables make perfect sense without a monitor. A monitor is implemented using mutexes and condition variables, that is the relationship. I think it would be better to have an own article for conditation variables. --95.91.236.185 (talk) 11:37, 8 June 2010 (UTC)

Room_synchronization[edit]

Someone queried the difference between this article and Room_synchronization, can someone who knows more than I take a quick look at that page? 212.44.19.62 13:27, 21 April 2006 (UTC)

Room synchronization is quite different from monitors. With monitors there is only one room and only one process may be in it at a time. With room synchronization, there are a number of rooms and all processes that are in any room must be in the same room, but there is no limit on how many processes can be in that room. You could use a monitor to implement room synchronization. —Preceding unsigned comment added by Theodore.norvell (talkcontribs) 20:30, 15 December 2008 (UTC)

Condition Variable example ?[edit]

I think the example is wrong: when doing wait(), the queueSize is increased, but never decreased. I think there should be a queueSize-- following the waiting.up(). -- Marc —The preceding unsigned comment was added by 193.49.124.107 (talk) 11:17, 15 May 2007 (UTC). Marc, you must be right, decreasing it that way is safe as it's protected, and else you would always have signal>0 once this is true once, therefore i correct the algorithm... Cédric —Preceding unsigned comment added by Gonnet (talkcontribs) 01:35, August 27, 2007 (UTC)

I have another question about the CV example code. Consider thread A running wait(), after releasing lock but before pending on waiting. Thread A is pre-empted by thread B which does signal(), which runs to completion, leaving waiting "up" and lock unlocked, meaning a possible lucky thread C could wait() and run straight through, bypassing the poor original thread A, even though C arrived at wait() after signal() ran and should therefore have had to wait until the next call to signal(). The fact that A didn't get signalled isn't the end of the world, since it will catch the signal intended for C the next time and A's wait() hadn't returned anyway, so A didn't really expect to catch the first signal() -- the possible problem is C getting to skip a wait(). I may be missing something, perhaps specific to the monitor use case of CV's or to the assumed semantics of waiting.up(), that makes this okay. Can you clarify what I'm missing? ScotS (talk) 23:55, 12 December 2007 (UTC)

Proposed rewrite[edit]

While I think the page is pretty good as it stands, I think it is missing a few things, in particular mention of Hoare's rules for using signal and wait. As a result I rewrote the article. The proposed rewrite is at http://en.wikipedia.org/wiki/User:Theodore.norvell/monitor . Please leave comments on it there. If there aren't too many negative comments that can't be easily responded to, I'll put it up here in a few weeks. Theodore.norvell (talk) 12:43, 31 December 2008 (UTC)

There were no negative comments, so I've gone ahead with the rewrite. Theodore.norvell (talk) 21:17, 3 February 2009 (UTC)
The rewrite is very good. TiagoCogumbreiro (talk) 16:28, 21 April 2009 (UTC)

According to Per Brinch Hansen, he didn't invent monitors[edit]

Not to cast flys into everyones drink, Per Brinch Hansen wrote in his books and notes that E. W. Dijkstra invented monitors. In turn, E. W. Dijkstra himself credits Per Brinch Hansen. You can of course simply ascribe this to the modesty of the authors, but take into account that these two men were good friends and close collaborators working on the same subject at the same time. I would say there is a good case for co-invention here, despite the common assertion that professor Hansen was the sole inventor. —Preceding unsigned comment added by 71.198.201.162 (talk) 20:03, 25 January 2009 (UTC)

I've changed it to credit Hoare and Brinch Hansen equally. I also mention that they were basing the concept of earlier ideas of Dijkstra as well as themselves. In Hansen's "Monitors and concurrent Pascal: a personal history", I didn't find any direct credit to Dijkstra.
If you read Dijkstra's "Hierarchical Ordering of Sequential Processes" you will find: "A secretary presents itself primarily as a bunch of non-reentrant routines with a common state space. But as far as the activity of the main program is concerned there is a difference between the routine of a secretary and a normal subroutine." It sounds a lot like a monitor. However, the way that a secretary puts processes to sleep or wakes them up it a bit different from the "wait" and "signal" of monitors. Theodore.norvell (talk) 21:32, 3 February 2009 (UTC)

Occupy a Monitor[edit]

I think we should be using the original usage of "inside" and "outside" of a monitor instead of using "occupy" and "unoccupying" monitors. TiagoCogumbreiro (talk) 16:28, 21 April 2009 (UTC)

Here's the reason that I changed it from "inside"/"outside" to "occupying"/"unoccupying". To me the word "inside" suggests that a thread is executing code that is "inside" of an object (or module). That is, in OO terms, a thread is "inside" whatever object is currently "this", and in, nonOO terms, it is "inside" whatever module is associated with its program counter. Say a thread calls a monitor's public method but then, before it returns, it calls a method in another object. At this point the thread is inside the other object. Is it still "inside" the original monitor? Well maybe and maybe not. Conversely if a thread calls a monitor and then calls "wait" is it "inside" the monitor? Another reason I like "occupy" is that it then lets me talk about the module's "occupant". Theodore.norvell (talk) 10:03, 14 May 2009 (UTC)

Monitors as objects[edit]

Monitors are not necessarily objects. Although they are used in object-oriented programming languages like Java, a monitor is infact introduced by Hoare as a module. The reader does not need to know what an object in order to grasp the concept of a monitor. Understanding what a module is is easier than an object. TiagoCogumbreiro (talk) 16:28, 21 April 2009 (UTC)

You are quite right. (By the way, I learned monitors while using Concurrent Euclid, which was a modular language.) My thinking was that very few people these days would be familiar with the term "module" as used in Concurrent Euclid and Modula 2. And those who are would probably be familar with OO concepts as well. It would probably be a good idea to add a mention that in nonOO languages, monitors can be modules. By the way, in Concurrent Pascal, monitors were "classes" and could have multiple instances. Theodore.norvell (talk) 10:03, 14 May 2009 (UTC)

assertion? Or predicate?[edit]

Since this major rewrite, this article uses the word assertion several times, e.g.

  • "Threads attempting an operation may need to wait until some assertion P holds true."

At least when it comes to the usage of the word assertion as defined within Wikipedia, is it correct speak of assertions throughout this monitor article? An assertion is a predicate that a developer expects to always be true. I would have expected predicate within the monitor article wherever assertion is used (also see conditional (programming)). --Abdull (talk) 18:30, 13 September 2010 (UTC)

I think this is a point worth considering. My first reaction was that Abdull is right, but that the word condition might be preferable to predicate. (Another possibility is boolean expression.) However, I looked back at the literature and found that the main sources agree on assertion. For example from [Hoare 74] we have "With each condition variable b the programmer may associate an assertion B which describes the condition under which a program waiting on b wishes to be resumed." Hoare also uses the term condition at one point. From [Burh et al. 1995] we have "When programming with monitors, it is common to associate with each condition variable an assertion about the state of the monitor". Admittedly, Burh et al. also use the term predicate. Lampson and Redell [1980] use predicate. Theodore.norvell (talk) 15:38, 6 December 2010 (UTC)
I have to quibble with one thing that Abdull says. He says "an assertion is a predicate that a developer expects to always be true". I think what he meant is that an assertion is a predicate that a developer expects to be true at a specified place in the program. (As the wikipedia article Assertion (computing) currently says.) This fits with the current use of assertion in the monitor article, as the assertion associated with a condition variable is expected to be true after a wait and prior to a signal. The point is that the use of boolean expressions in monitors fits in the tradition of assertional reasoning that started with Hoare's 1969 An Axiomatic Basis for Programming paper. For me, preconditions, postconditions, and object invariants are all just varieties of assertions. Theodore.norvell (talk) 15:38, 6 December 2010 (UTC)
After taking another look, I agree that the article did use the word assertion in places that where it was probably not appropriate. I've changed these occurrences to condition. Theodore.norvell (talk) 17:17, 6 December 2010 (UTC)

Error in Monitor (synchronization)-Mesa.png[edit]

See the file's talk page.

Monitor (synchronization)-Mesa.png

-Craig Pemberton 06:54, 1 March 2011 (UTC)

Fixed. Thanks Craig. Theodore.norvell (talk) 22:29, 11 May 2011 (UTC)

Small change in "Waiting and signaling"[edit]

I added some other (crappy) solutions to the busy waiting problem, just to expand a bit on the issue and how monitors are a great solution. Should I expand my explanation or remove it? It's my first wiki edit so I'm not sure on the policies.. — Preceding unsigned comment added by Mtzguido (talkcontribs) 18:09, 9 April 2013 (UTC)

Code typo[edit]

Thank you 109.193.44.29 (talk · contribs) for catching and fixing my accidental errors with "isEmpty"/"isFull" in the pseudocode samples. I think you're correct; it probably was from copying and pasting and not proofreading enough. I'm glad people are checking. --Wykypydya (talk) 22:36, 1 November 2013 (UTC)

wording problem[edit]

> the next program counter to be executed

That makes no sense. The program counter cannot be executed. It points to code to be executed.

That sounds like an "edito" from thinking of saying "the program counter points to" and thinking of saying "the next program location to be executed" and mis-fusing the two. — Preceding unsigned comment added by 2620:0:1000:1501:1260:4BFF:FE68:1974 (talk) 22:58, 4 November 2013 (UTC)

Harmful Link[edit]

Hey guys, I never used to Edit something here, but i found a "bad" link down at the end of the Article. "Tutorial multiprocessing traps" <- this one directs you to one of the "MAKE XXXXX CASH IN 10 MINUTES!!!". I just dont wanna Edit and delete it, because I dont know if it would be okay. — Preceding unsigned comment added by 194.45.13.131 (talk) 15:17, 11 November 2013 (UTC)

Deleted. Theodore.norvell (talk) 00:03, 16 March 2014 (UTC)

New introduction[edit]

An edit in October 2013 substantially changed the introductory paragraphs. For example it added this sentence. "In essence, a monitor M = (m, c) is a pair of a mutex (lock) object m and a condition variable c." To me this doesn't look right. Since the start (i.e. Hoare's paper and Brinch Hansen's work) monitors have allowed an arbitrarily large set of condition variables. The restriction to one variable (as in Java) is one variation on the monitor concept. 142.134.201.203 (talk) 12:16, 16 March 2014 (UTC)

Thanks for pointing that out! I changed it. If you think anything else was better before the October 2013 edit feel free to restore it. InverseHypercube (talk) 02:57, 6 April 2014 (UTC)

New sections[edit]

Several new subsections have been added to section 2, Condition variables. These are currently "2.2. Case study: classic bounded producer/consumer problem", "2.3 Condition variables", "2.4 Monitor usage", "2.5 synchronization primitives", and "2.6 Semaphore". There are some good ideas here, but I think that they mostly serve to make an already long and complex article longer and more complex. They also move the article more toward's a "how to", as noted by the warning "This article contains instructions, advice, or how-to content. The purpose of Wikipedia is to present facts, not to train. " that now sits in front of the article. My suggestion is to revert the article back to its earlier structure, while keeping only what is most useful from the added material. Maybe the new material can be moved elsewhere: e.g. wikibooks Theodore.norvell (talk) 13:21, 16 March 2014 (UTC)