Saturday, October 13, 2007

Advanced OOP: Understanding Semaphores

One very useful programming algorithm that is very useful in Flash comes from concurrent programming, and is called mutual exclusion. If you've taken classes in operating systems these concepts may be familiar to you.

About Mutual Exclusion
Mutual Exclusion is all about common resources and making sure blocks of code that share these resources aren't halted when requests are made. For example, if we have 2 programs and 2 resources, both of which are required for a specific operation, both programs must take turns using the resources.

Say program 1 acquires resource 1 the same moment that program 2 acquires resource 2. Since neither program can complete their operation without the other resource; we have what we call a dead lock. This stops the program from running or creates undesired effects. Without a specific implementation to prevent this situation from occurring we have a race condition where program 1 and 2 are competing to finish their blocks of code.

What is a Semaphore
A semaphore is a classic example of an algorithm used to solve this particular situation.

Here's code for a semaphore:

class Semaphore extends EventHandler {
// events
public static var ADDED : String = 'added'; // resource was added

// used as events and states
public static var LOCKED : String = 'locked'; // anything locked
public static var UNLOCKED : String = 'unlocked'; // everything unlocked

private var _lockHash : Object;
private var _state : String; // defaults to unlocked
private var _numLocked : Number;
private var _numTotal : Number;

public function Semaphore($state:String) {
_state=($state) ? $state : UNLOCKED;

public function lock($name:String):Void {
// change count
if(_lockHash[$name]==undefined) _numTotal++;
if(_lockHash[$name]!=LOCKED) _numLocked++;

// lock item
_lockHash[$name] = LOCKED;

// something locked
if(_state == UNLOCKED) {
type: LOCKED,
target: this

public function unlock($name:String):Void {
// change count
if(_lockHash[$name]==undefined) _numTotal++;
if(_lockHash[$name]==LOCKED) _numLocked--;

// unlock item
_lockHash[$name] = UNLOCKED;

// everything unlocked
if(_numLocked==0 && _state==LOCKED) {
target: this

public function get numLocked():Number { return _numLocked; }

public function get numTotal():Number { return _numTotal; }

public function get state():String { return _state; }

public function remove():Void {

In this class definition we store locks in a hash called _lockHash. We'll store things when a lock or an unlock is invoked. We'll also store the number or locks and total locks. This way we won't have to count all of the locks each time we change their values.

By default the Semaphore starts in an UNLOCKED state. If anyone requests a lock when the semaphore is in a UNLOCKED state we'll dispatch a LOCK event to tell everyone and we'll change the state to LOCKED. When the last lock is released we'll dispatch an UNLOCK event and set the state of the semaphore to UNLOCKED.

And there we have it. I'll show some more examples when I get a chance. There's some interesting applications that simplify a lot of programmatic situations.

No comments: