Technique: Semaphores

For the past year(!) or so I’ve had a series of articles I meant to write about some intermediate programming concepts that can allow you to write code at a higher level. I regret that it’s taken so long to come around to them, but I hope they can be of some use. This series will cover semaphores, asynchronous tokens, and green threads, and I may extend it with some brief notes on assertions and iterators. Today I’d like to talk about semaphores.

Part The First, In Which There is Much Hemming and Hawing

First, allow me a word of philosophical introduction. None of these concepts is very complicated, and even if you’re unfamiliar with the terminology, you are likely to have programmed something similar to them yourself. However, ingesting them conceptually and being able to use them in an encapsulated way makes code you write more high-level, and thus more powerful and more succinct, and to me, more beautiful. For any given programming language, some concepts are encoded in the language itself, but all other concepts must be built on top of the language. For example, the idea of objects is built into ActionScript 3.0 with keywords like new and class, but a concept like a loading queue is built using the language. For every language there is a line where this distinction is drawn, making for interesting languages like JavaScript where you are free to simulate Object Oriented programming in your own way with your own syntax by using closures. However, there is no Turing complete language – which is to say, no language you’re likely to use on a computer – for which there is a line defining things you simply cannot build. And the point here is that the distinction between things the language provides and things you build yourself is only the syntax, and how it runs. Furthermore, perhaps I am biased to say so, but I believe that OOP gives us fairly good syntax with which to define our own ways of doing things. What I’m coming to here, is that you can make a language smarter – and make it look natural doing it – and in this I take great joy.

So we come to my series of topics for some intermediate computer science topics. My articles have this in common: They cover features that could have been in the language, but since they aren’t, we can create our own versions which are no less, or only slightly less, useable and readable. By encapsulating these concepts in objects rather than solving them differently in different places, we are freed from again thinking of that specific problem, and code which relies on the concept becomes beautifully concise.

If you are a student of design patterns, you may well read this introduction and think that I will be writing a series of articles on patterns. However, I am reluctant to call these topics patterns. Perhaps this is because their use was understood far before patterns, or because I learned of them far before patterns. Or perhaps it has something to do with the fact that you can build these structures once and use them, so that they are more like utilities. However, if you want to call them patterns, go ahead. I think patterns serve the same purpose. They are ways to organize ideas in a higher level than the syntax of the language itself; and indeed some languages have no need for some patterns because the pattern is behind that invisible line of “things you can do inside the language.”

So, You Mentioned Semaphores…

At any rate, today’s topic is the humble semaphore. Semaphore is one of those glorious Computer Science words that makes me feel good about having spent 4 years at a prestigious university. Actually there are two categories of such words: inscrutable names for simple things, and inscrutable names for quite difficult things. Semaphore is one of the former. (NP-Complete is one of the latter.)

A semaphore in CS-speak is just a lock. Let’s not forget that semaphores are also signals made with flags in two arms to transmit information at a distance. It’s quite probable that the original meaning inspired the name for a lock, so let’s use it as an analogy.

These objects are quite old and venerable, because once our hardware and software was slow and not quite so parallel as it is now, and we used locks as a solution. Let’s say you have an old 15MB hard drive in your computer. Process A wants to write some data to the disk. Process B also wants to write some data to the disk. With nobody watching, they both go ahead and start writing merrily away. If you’re lucky, everything goes fine. If you’re not, they both end up writing to the same spot on the disk and one, or both, gets hosed. So venerable old operating systems put in a gatekeeper, and that’s your semaphore. Instead of saying

disk.write();

You now check with the gatekeeper.

while (disk.isLocked())
{
	wait();
}
disk.lock();
disk.write();
disk.unlock();

Okay, so in our imaginations let’s picture a little man with bronzed skin and zinc on his nose, sitting on his tall chair on the disk, and he signals by crossing his arms with two flags: “Sorry buddy, disk is closed for business right now. Some other fella is using it.” You check up later and he traces out the path of a circle, one hemisphere with each arm, from top to bottom: “Coast is clear, go ahead!” I guess semaphore kinda works as an analogy. But it’s really just easier to call it a lock.

No matter what you call it, a semaphore has only one purpose: prevent concurrent access.

What Are They Good For?

Thankfully we don’t have to lock down the entire disk when we’re writing data nowadays, though the physical limitations of the device really do prevent us from writing two bits of data to two locations at the same time. Operating systems are smarter than this now and will do all the queueing, and indeed often journaling, of disk writes for you.

However, we run into plenty of other situations where we still lock things down unequivocally while in use. For instance, some tools will lock a database from being accessed while writing to it.

You might want to use a semaphore for…

1. preventing actions which interfere with a process in motion
2. objects that can’t be used by two simultaneous clients
3. processes that take multiple steps over a period of time

And here’s the thing… they’re pretty useful in websites too. I usually want to prevent any kind of navigations when a transition is in progress, or when the next section is loading. You want to prevent input into a form while a form is submitting. Because web programming is so event-driven, asynchronous, and animation-heavy, it often makes sense to lock actions or objects for a short period of time.

Does It Really Need Its Own Class?

But wouldn’t a simple “locked” member variable do the trick, you might ask? Well, you can do it that way, but you can also add some useful features to the basic implementation of a semaphore and suddenly it becomes a lot more powerful. For instance, you could allow multiple reservations. You could track who has a reservation on the shared resource. You could broadcast an event when an object becomes available or unavailable. Here I will present two implementations of a semaphore. First, the abstract base class, so that we can use either implementation at our will.

Abstract Semaphore

package com.partlyhuman.semaphore
{
	import flash.events.EventDispatcher;

	[Event(type="com.partlyhuman.semaphore.SemaphoreEvent", name="available")]
	[Event(type="com.partlyhuman.semaphore.SemaphoreEvent", name="unavailable")]
	public class Semaphore extends EventDispatcher
	{
		protected var _description:String;
		public function get description():String {return _description;}

		protected var _owner:Object;
		public function get owner():Object {return _owner;}

		public function Semaphore(owner:Object = null, description:String = null)
		{
			_owner = owner;
			_description = description;
			initialize();
		}

		protected function initialize():void
		{
			throw new Error("Abstract Method");
		}

		public function get locks():int
		{
			throw new Error("Abstract Method");
			return 0;
		}

		public function get isLocked():Boolean
		{
			throw new Error("Abstract Method");
			return false;
		}

		override public function toString():String
		{
			return "[Semaphore " + description + "]";
		}
	}
}

And the semaphore events,

package com.partlyhuman.semaphore
{
	import flash.events.Event;

	public class SemaphoreEvent extends Event
	{
		public static const AVAILABLE:String = "semaphoreAvailable";
		public static const UNAVAILABLE:String = "semaphoreUnavailable";

		public function SemaphoreEvent(type:String, bubbles:Boolean=false, cancelable:Boolean=false)
		{
			super(type, bubbles, cancelable);
		}

	}
}

A Basic Implementation

This implementation merely uses a counter. Straightforward, but once you start using semaphore objects to lock your navigation or your input fields, you will start to see how this simple object can untangle your state logic.

package com.partlyhuman.semaphore
{
	public class SimpleSemaphore extends Semaphore
	{
		protected var _locks:int = 0;

		public function SimpleSemaphore(owner:Object = null, description:String = null)
		{
			super(owner, description);
		}

		override protected function initialize():void
		{
			_locks = 0;
		}

		override public function get locks():int
		{
			return _locks;
		}

		override public function get isLocked():Boolean
		{
			return (_locks > 0);
		}

		public function lock():void
		{
			if (_locks++ == 0)
			{
				dispatchEvent(new SemaphoreEvent(SemaphoreEvent.UNAVAILABLE));
			}
		}

		public function unlock():void
		{
			_locks--;
			if (locks < 0)
			{
				throw new Error("Semaphore Asymmetrically Unlocked!");
				locks = 0;
			} else if (locks == 0) {
				dispatchEvent(new SemaphoreEvent(SemaphoreEvent.AVAILABLE));
			}
		}
	}
}

An Alternative Implementation

In this implementation, you get a receipt for your reservation. If you happen to need to hold on to a shared resource through a multi-step process that involves many objects, you might end up with a lot of dependencies. This implementation solves the problem by allowing you to pass around a lock object. Any code with a reference to the lock can release it, without requiring a dependency on the source of the lock itself.

package com.partlyhuman.semaphore
{
	public class Lock
	{
		protected var owner:TokenSemaphore;

		public function Lock(owner:TokenSemaphore)
		{
			this.owner = owner;
		}

		public function release():void
		{
			owner.releaseLock(this);
		}
	}
}

package com.partlyhuman.semaphore
{
	public class TokenSemaphore extends Semaphore
	{
		protected var tokenPool:Array;

		public function TokenSemaphore(owner:Object = null, description:String = null)
		{
			super(owner, description);
		}

		override protected function initialize():void
		{
			tokenPool = new Array();
		}

		override public function get locks():int
		{
			return tokenPool.length;
		}

		override public function get isLocked():Boolean
		{
			return (tokenPool.length > 0);
		}

		public function getLock():Lock
		{
			if (locks == 0)
			{
				dispatchEvent(new SemaphoreEvent(SemaphoreEvent.UNAVAILABLE));
			}

			var lock:Lock = new Lock(this);
			tokenPool.push(lock);
			return lock;
		}

		internal function releaseLock(lock:Lock):void
		{
			var index:int = tokenPool.indexOf(lock);
			if (index == -1)
			{
				throw new Error("TokenSemaphore: a lock was released that could not be found");
				return;
			}

			tokenPool.splice(index, 1);
			lock = null;

			if (!isLocked) dispatchEvent(new SemaphoreEvent(SemaphoreEvent.AVAILABLE));
		}

	}
}

Conclusion

Using semaphores in your code is a great way to avoid complicated state logic. You can move the logic of tracking usage to the semaphore object, and handle the results of locking or unlocking only when it has an effect. Though a simple concept, using it as a tool in your toolkit can make your code beautiful and concise. And you can design additional functionality into your own implementation. For example, I will soon explain a semaphore which binds to an asynchronous token... or you could write a semaphore which actually queued up requests.

Let me know what you think, and see you soon with the next installment!