Archive for lock

Mutual Exclusion Definitions

Posted in Concurrency with tags , , , , , , , , on July 29, 2008 by moffdub

In my world, concurrency is poorly understood. Most of my experience with it has been with simple locks to coordinate threads. In college, they made vague reference to higher-level language constructs and mechanisms, but dared not elaborate. Such mechanisms might actually be useful in the workplace, and therefore they had no place in the classroom. After all, the students might get their money’s worth.

Mutexes. Locks. Semaphores. Monitors. I’ve never been clear on the relationship between these terms, and if relationships differ depending on your operating system and/or platform. So in this post, I will do my best to clarify the differences for myself and anyone who is reading this.


(the obligatory lock picture)

I’m going to illustrate the terms with equivalents in C/C++, C#/VB.NET, and Java. And I make no claim that I am an expert on any of this; I am but a mere a serf trying to improve his condition.

Locks

Here is a term that I wasn’t even sure was defined as anything above a way to implement mutual exclusion. If I had to come up with my own definition, it would be anything in a language that allows access to a delimited block of code by one and only one thread at a time.

In C#/VB .NET land, this is essentially what the lock keyword accomplishes.

On .NET Rocks show #166, with guest Joe Duffy, Carl Franklin infers this just before the guys get into a discussion on the differences between different synchronization mechanisms:

Carl Franklin: Yeah boy, I — don’t I know it, that is tough. I specially find it challenging because there is two things that you lock right, you can lock an object with sync locker, the lock keyword in C# and you can also lock that around a block of code. So what you are really doing is, you are locking that code. It’s not just about the object you are using as the lock object then there’s two different scenarios there.

In Java land, the synchronized keyword gets this job done. Not much more to say there.

In C/C++ land, where I will focus on POSIX because that is what they made us use in college, pthread_mutex_lock is what I dealt with the most. Note the confusing name: “lock” is the operation, and you’re locking a “mutex”, which is the next category. Functionally, though, I am putting pthread_mutex_lock in the simple lock category.

The verdict: a lock is a simple mechanism used by threads to allow one thread access to a block of code.

Mutexes

Here is where it gets kind of fun. As far as I knew, mutex is just short for mutual exclusion. That sort of clarity does not hold as you venture onto different platforms, though.

Carl Franklin: So, the difference between a lock and Mutex; that’s always a fun thing to talk about.

Joe Duffy: Well, Mutex is kind of a lock but the neat thing about Mutexes on Windows is that unlike say a monitor on the CLR you can use it to synchronize access to shared resources across multiple processes on the machine.

That answers what a mutex is in C#/VB.NET land: a synchronization mechanism that can coordinate access between both threads and processes. I found a cool example of using this class to ensure only one copy of a process is running at a time.

In Java land, I did not find an equivalent mechanism. In fact, doing anything involving IPC in Java that does not use sockets or RMI seems to involve an exercise of acrobatics. Consider using shared memory and JNI in concert with the synchronized keyword.

In C/C++ land, the same POSIX library, namely the functions pthread_mutex_lock and pthread_mutex_unlock and type pthread_mutex_t, describes a mutex as “a MUTual EXclusion device, and is useful for protecting shared data structures from concurrent modifications, and implementing critical sections and monitors” (source).

There is nothing that implies IPC here, as is implied in .NET. The closest POSIX C/C++ gets to a cross-process mutex is a binary semaphore, which is defined later in this post. which can be used to synchronize OS-level goodies. The boys on show #166 tend to agree with the binary semaphore comment:

Joe Duffy: So a Mutex is like a semaphore with a count of one, right.

The conclusion? Mutex is an ill-defined term. Sometimes it is a shorthand for the idea of mutual exclusion. Sometimes it is a synonym for simple locks. Sometimes it is a wrapper for simple locks around IPC mechanisms. I’d prefer not to use it.

Semaphores

Sure enough, the most esoteric of the terms is the most clearly defined.

Joe Duffy: A semaphore is kind of like a Mutex, except — well let me reverse that. A Mutex is kind of a like a semaphore. Semaphore has a count right, and when somebody acquires it, they decrement the count and if the count ever reaches zero and somebody tries to acquire it, they block waiting on it. And the only when the semaphore is incremented will they actually be able to move forward.

Indeed, the System.Threading.Semaphore class in C#/VB.NET fulfills the job.

Java land, not to be outdone, provides its own Semaphore class.

POSIX C/C++ supports semaphores as well, though the interface is in dire need of an application of the Facade pattern. Semaphores here can be used for cross-process access via shared memory, in contrast to Java and .NET’s implementations.

Speaking of facades, here is exactly what I am talking about, given to us students by Dan Duchamp to help us with our assignment (based on the Dutch words assigned by Dijkstra for “increase” and “try-and-decrease”):

#include <stdio.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <stdlib.h>

void P(int semid)
{
	struct sembuf sbuf;
	sbuf.sem_num = 0;
	sbuf.sem_op = -1;
	sbuf.sem_flg = 0;
	
	if (semop(semid, &sbuf, 1) < 0)
		perror("semop P"), exit(1);
	
	return;
}

void V(int semid)
{
	struct sembuf sbuf;
	sbuf.sem_num = 0;
	sbuf.sem_op = 1;
	sbuf.sem_flg = 0;

	if (semop(semid, &sbuf, 1) < 0)
		perror("semop V"), exit(1);
	
	return;
}
void Init(int semid, int value)
{
	union
	{
		int val;
		struct semid_ds *buf;
		u_short *array;
	} arg;
	
	arg.val = value;
	
	if (semctl(semid, 0, SETVAL, arg) < 0)
		perror("semctl SETVAL"), exit(1);
		
	return;
}
void Print(int semid)
{
	int val;

	if ((val = semctl(semid, 0, GETVAL)) < 0)
		perror("semctl GETVAL"), exit(1);

	printf("Semaphore %d’s value = %d\n", semid, val);

	return;
}

The conclusion here: no doubt a semaphore is, abstractly, a counter that causes threads to block when it is decremented to 0. The only ambiguity can come when considering if it is cross-process or not.

Monitors

In the operating system course, monitors were alluded to for about 4 minutes as language support for mechanisms like locks and semaphores. It sounded kind of mystical. Thanks to this post, they sound as pedestrian as anything else I will have the misfortune of using.

One of the biggest surprises to me was finding out that in .NET land, monitors are below the lock statement; the lock statement is a higher-level version of monitors. Huh?

Joe Duffy: Well, Monitor gives you a couple of things that just using the lock keyword doesn’t; one is time out, so you can actually specify time out when you say monitor.enter. … In general, its easier to use the lock keyword because making sure — guaranteeing that you actually exit the Monitor requires that you use like a try-finally block. And the actual coding pattern in there is hidden behind the scenes with the lock keyword. So it makes it a lot easier for you.

OK then. For now, it is enough to know that the Monitor class provides an interface through which you can wait for a lock to be unlocked and signal to a thread waiting on that lock that the lock is available (or all threads).

Java land, not to be outdone, follows suit. The compulsive neurotic in me cheers the consistency: there is a wait method, and notify and notifyAll methods, analogous to Pulse and PulseAll in .NET.

POSIX extends their mileage by providing pthread_cond_wait, pthread_cond_signal, and pthread_cond_broadcast. Hooray for consistency! You can no doubt find a C++ monitor class somewhere that wraps these calls into something Java- or .NET-like.

The conclusion: monitors, as their lowest, are condition variables and the ability for threads to wait to be signaled that a simple lock is available and to signal one or more threads that the lock is available.

Writing it all down has a way of putting the issue to bed for me, or at least tucking it in. If we are going to be stuck with the thread model for a while, I might as well know what everyone’s talking about.

Follow

Get every new post delivered to your Inbox.