| COP4610: Operating Systems & Concurrent Programming | up ↑ |
It is very easy to make these errors in concurrent programming.
Especially when modifying working code, it is easy to add a reference to a shared object (which might not even have been shared before) without taking steps to protect it from concurrent access.
Similarly, if we remember to enforce mutual exclusion we might add a call to a lock operation, without realizing that the lock holder might be waiting for the thread/process that performs a the new lock call, and so get into a deadlock. We might also put in a return or conditional branch that skips over the corresponding unlock operation, with the same effect.
When implementing logical events, it is very easy for the thread/process that goes to sleep to wait for an event to get into a race with the one that is signaling the the event occurrence.
To help programmers avoid these errors, some programming languages, such as Concurrent Pascal and Ada, provide built-in concurrent programming constructs which allow the compiler and run-time system to detect erroneous programming.
For example, it is easy for a compiler to check that every lock operation has a matching unlock operation.
If an object is declared as shared, the compiler can check that no access is made to it without locking the associated lock.
Most textbooks present monitors as a programming language feature, because that is how the term was introduced. However, behind the monitor programming language concept there is an underlying design model (some people now call these programming "patterns") which can be implemented without any special language. In particular, this design model is such a natural match with with mutexes and condition variables that one might say they were designed for one another.
The POSIX thread mutex and condition variable constructs were designed specifically to provide natural (low-level) implementation mechanisms for monitors. However, even with semaphores, one can implement a conceptual monitor.
So, if one is programming using the C language and threads or semaphores, if one uses the concept of "monitor" can be used as a design tool, one is like to avoid the most common concurrent programming errors.
A monitor can be visualized as a lockable room, which contains and protects some objects from concurrent access.
There is a door with a lock that allows only one thread/process to enter the room at a time. This ensures mutual exclusion. Only one thread/process can touch the objects in the room at any one time.
If there are queues, the queues are ante-rooms, connected to the main monitor room by doors. A thread/process may step into one of these ante-rooms only from inside the main monitor room. In doing so, the thread/process releases the main door lock, allowing another thread/process to enter and locking itself out until the room is again empty.
In some models, a thread/process in an ante-room has priority for regaining the lock over a thread/process that is trying to get the lock from outside the monitor.
Conceptually, we have an object with one data component, and two methods, which we might call "get" and "set".
Ada is a language with built-in support for the monitor concept.
package Monitor1 is
protected type Bulletin_Board is
function Get return String;
procedure Put (S : String);
-- raises Constraint_Error if S is too long
private
Message : String (1 .. 48) := (others => ' ');
end Bulletin_Board;
end Monitor1;
package body Monitor1 is
protected body Bulletin_Board is
function Get return String is
begin
return Message;
end Get;
procedure Put (S : String) is
begin
if S'Length > Message'Length then
Message := S (S'First .. S'First + Message'Length - 1);
else
Message (1 .. S'Length) := S;
Message (S'Length +1 .. S'Last) := (others => ' ');
end if;
end Put;
end Bulletin_Board;
end Monitor1;
The compiler automatically generates the code to provide mutual exclusion for all calls to the protected operations Get and Put, and the language rules prevent access to the shared data Message from outside the syntactic scope of the protected object declaration.
char message [48] = " ";
semaphore s = 1;
void Get (char * buf; int len) {
int i;
semWait (s); /* wait until we can lock the semaphore */
for (i = 0; i < len-1; i++) {
if (i < 48) buf[i] = message[i];
else buf[i] = ' ';
}
message[len-1] = '\0';
semSignal (s); /* release the lock, and wake up a waiter, if any */
}
void Put (char * buf; int len) {
int i;
semWait (s); /* wait until we can lock the semaphore */
for (i = 0; i < 47; i++) {
if (i < len) message[i] = buf[i];
else message[i] = ' ';
}
message[47] = '\0';
semSignal (s); /* release the lock, and wake up a waiter, if any */
}
The big difference here is that the enforcement of mutual exclusion is left up to the self-discipline of the programmer. The connection between the lock and the data it protects is purely conceptual. There is no checking. Anyone can write (bad) code that accesses the shared data, from anywhere, without going through the lock/unlock protocol. Likewise, a programmer might forget to unlock.
char message [48] = " ";
pthread_mutex_t M = PTHREAD_MUTEX_INITIALIZER;
void Get (char * buf; int len) {
int i;
pthread_mutex_lock (&M); /* wait until we can lock the semaphore */
for (i = 0; i < len-1; i++) {
if (i < 48) buf[i] = message[i];
else buf[i] = ' ';
}
message[len-1] = '\0';
pthread_mutex_unlock (&M); /* release the lock, and wake up a waiter, if any */
}
void Put (char * buf; int len) {
int i;
pthread_mutex_lock (&M); /* wait until we can lock the semaphore */
for (i = 0; i < 47; i++) {
if (i < len) message[i] = buf[i];
else message[i] = ' ';
}
message[47] = '\0';
pthread_mutex_unlock (&M); /* release the lock, and wake up a waiter, if any */
}
This is just as unsafe as the example above, as regards the lack of checking for violations of the conceptual model.
Also beware of the similarity so far, between semaphores and mutexes. POSIX mutexes do not have a "count" value. Most of the more complicated things one uses counting semaphores for do not translate so easily. They will require at least a condition variable be used in addition to the mutex, and quite different logic.
See the Semaphore Monitor Example.
The link above is to the monitor part of the semaphore discussion. If you have time, it is best to go through this discussion from the beginning.
See the Producer-Consumer Monitor Example.
The link above is to the monitor part of the example. If you have time, it is best to go through this entire example from the beginning.
See the Barbershop Monitor Example.
| T. P. Baker. ($Id) |