1
$\begingroup$

I am looking for a library which provides a "serializer" ADT for synchronization. (http://courses.cs.vt.edu/~cs5204/fall99/Summaries/Concurrency/serializers2.html)

Googling leads me to nowhere, unlike monitors,semaphores and other constructs, serializers are hardly discussed over the web in depth.

Any other pointers are welcome. :)

$\endgroup$
  • $\begingroup$ Maybe this fits Stack Overflow better. $\endgroup$ – Juho Sep 21 '13 at 19:53
  • $\begingroup$ I thought cs stackexchange better. :/ $\endgroup$ – Nitish Upreti Sep 21 '13 at 19:57
  • $\begingroup$ A library in what language? I don't think Computer Science is a good fit if you are looking for actual implementations. $\endgroup$ – Juho Sep 21 '13 at 20:06
1
$\begingroup$

This is the first I've ever heard of serializers, and I don't know of any libraries that implement them. From reading the course notes you pointed to and the paper by Hewitt and Atkinson referenced in the course notes, there seem to be two differences between serializers and monitors. The first is that serializers have a more "elegant" but less efficient way of waiting for invariants to become true, the second is that a notion of reader/writer locks seems to be built-in to serializers, but wasn't built in to the original notion of monitors.

The present-day conception of a monitor largely follows Lampson and Redell. "Experience with processes and monitors in Mesa," Comm. ACM 23(2):106-117, 1980. A monitor is an object (some private data with public methods that act as the interface to the abstract data type that the object implements) with a private mutex. Every public method starts by acquiring the mutex, and releases the mutex on exit. In Java this would be equivalent to marking every public method "synchronized". In C++11 this would be equivalent to declaring a private mutex, m, and having every public method begin with a declaration std::unique_lock<std::mutex> lock(m) (an RAII-style critical section).

While in monitors the notion of condition variables is explicit, in a serializer the condition variables are implicit in the enqueue...until statement. In a monitor you could implement something similar by associating a condition variable, cv, with each monitor. Then the enqueue...until (<invariant-test>) statement is written cv.wait(m, []{return <invariant-test>;}) (that's C++ syntax for an anonymous function that returns true when the invariant is satisfied.) And you would then need to make sure that you cv.notify_all() at the end of each public procedure (in C++ I would do this by subclassing unique_lock, giving it a destructor that calls cv.notify_all() in addition to releasing the mutex.)

Finally, the serializer has this bizarre join_crowd/leave_crowd operation. It took me a while to figure this one out, but as best I've been able to determine it is a slightly weird way of implementing a reader-writer lock. In a serializer when you want a reader-lock you join the crowd and you release the reader-lock by leaving the crowd. (The "crowd" is the set of readers.) I think monitors make this operation much clearer. You can protect a monitor by a reader/writer mutex instead of a normal mutex. The rule for when you can acquire the read lock instead of the write lock is completely clear in monitors: a method that does any mutation of the data structure must be protected with a write-lock. Only if the method is completely immutable (const in C++ parlance) can you protect it with the read-lock. (Note though that C++11 didn't include reader/writer locks for very good reasons, so if you wanted to do this in C++ you'd need to use Boost's reader/writer locks.)

I can hazard some guesses about why serializers never got much notice. The first reason is that they were proposed by Carl Hewitt, who was the primary proponent of the Actor model of concurrent programming, and the Actor model uses different terminology than most people in the systems programming community are used to. The second reason is that the serializer enqueue...until statement requires you to add a notify_all() at the end of each public method. This in turn causes every thread waiting on an invariant to wake up and retest its invariant. Standard condition variables allow you to put notify_one() statements only where they are actually useful, which can lead to real performance benefits. Finally, it is not clear (to me) how to use the join_crowd/leave_crowd operation correctly, while it is at least easy to state what you must not do with a reader/writer lock (and even then reader/writer locks are one of the most common causes of bugs in multi threaded programs, so who knows what horrors would have been perpetrated in a world where serializers were standard practice.)

$\endgroup$
  • $\begingroup$ I am new to multithreading programming, so might be a stupid question but: Do I need a separate thread for all the internal book keeping of serializer and making the scheduling decision? If yes, what happens if this thread does not get chance to run. $\endgroup$ – Nitish Upreti Oct 2 '13 at 18:16
  • $\begingroup$ I don't think you need any extra threads. The bookkeeping is done by the "normal" threads as they call and leave the methods of the serializer. (In particular, calling cv.notify_all() in the destructor of your unique_lock subclass is the real extra bookkeeping work beyond what a monitor does.) $\endgroup$ – Wandering Logic Oct 4 '13 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.