LOCKS aren't all that and a bag of chips.

Locks are primitive and crude and you can't really clever sophisticated mutual exclusion with locks.

Semaphores.

A lock only has two states:  locked and unlocked.

A semaphore is actually a nonnegative integer.  It can have the value 0, 1, 2, 3, etc.

Semaphore has two commands:  wait and signal.  Wait is like lock, but not exactly.  Signal is like unlock, but not exactly.

The abbreviation for wait is P and the abbreviation for signal is V.

P (sem) : <await (sem > 0) sem--;> //wait until the semaphore is positive and then subtract one from the semaphore and then proceed.

V (sem) : <sem++;> //adds one to the semaphore and then proceeds.

<await (test) command;> waits (or blocks) until the test becomes true and then executes command atomically.  THIS IS NOT A REAL COMMAND IN A PROGRAMMING LANGUAGE.  It's just pseudocode.


What does UNLOCK (lock); UNLOCK (lock) do?

The first lock unlocks the lock.  The second does nothing since you're attempting to lock an unlocked lock.

However, V (sem); V (sem); actually something not completely crazy.  The first increments the semaphore.  The second increments the semaphore again.

Let's say our semaphore starts at 0.  V (sem); V(sem); sets the semaphore to 2.

At some point, some thread issues P (sem).  Well, since sem is 2, sem becomes 1 and the thread continues on.  Another thread issues P (sem).  Since sem is 1, sem becomes 0 and the thread continues on.

A third thread issues P (sem).  And since sem is 0, it blocks.  If at some point, sem becomes 1, then my thread will decrease it back to 0, and then proceed.

So, we have used semaphores to allow two threads into the critical code, but not a third.

DIGRESSION:  If several threads are waiting on the same semaphore (or lock) and the resource gets released, which of the waiting threads gets to be unblocked?  The answer is the operating system gets to decide.  A queuing system is easy to implement and often is, allowing the first thread to get blocked to also be the first one to get released.

But there's no law that says this must be the case.  We are working under the assumption only that if you a lock a resource, and it's released continually (meaning that you know at any given time that another release is coming), your thread will eventually be the one released.  We call this a "fair" scheduling system.)

The advantages of semaphores over locks:  The signaler doesn't have to be the same thread that issued the wait command.  (With locks, the thread that locks has to be the thread that unlocks.)

Semaphores can signal before waiting, and that actually means something and does something.  (Unlocking before locking may not do that much at all.)

With semaphores, you can allow not just one but two, three, four, etc., even an infinite number of threads into a critical section, if that suits your needs.

The big downside is that the techniques for using properly are often confusing and not obvious.

READER/WRITER PROBLEM with semaphores

We can have as many readers as want to read from the database.  But only one writer at a time.  And you can't have readers and writers in there together.

We will use a read semaphore, a write semaphore, and an administrative semaphore.  read and write are initialized to 0.  admin is initialized to 1.

We will keep track of number of readers (nr), number of writers (nw), number waiting to read (nrw) and number waiting to write (nww).

READ:

P (admin);
if (nw > 0) {nrw++; V (admin); P (read);}
nr++;
if (nrw > 0) {nrw--; V (read);}
else V (admin);

READ THE DATABASE

P (admin);
nr--;
if (nr==0 && nww > 0) {nww--; V (write);}
else V (admin);


WRITE

P (admin);
if (nr > 0 || nw > 0) {nww++; V (admin); P (write);}
nw++;
V (admin);

WRITE TO THE DATABASE

P (admin);
nw--;
if (nrw > 0) {nrw--; V (read);}
else if (nww > 0) {nww--; V (write);}
else V (admin);


Now some things to observe:  We want the administrative semaphore to be held as briefly as possible.  The admin sem is used to regulate who wants to read and who wants to write.  We don't want to be holding onto admin while we're actually in the database reading and writing.  And what's cool with semaphores is that one who grabs the admin semaphore (waits on it) is not necessarily the one who releases it (signals it).