CLIPC Semaphores: Synchronization

The Short Story

A semaphore is a mechanism for synchronizing two processes. Synchronization is needed when two separate processes can interfere with each other. Semaphores work via decrement (reserve) and increment (release) operations.

The Long Story Part I: What is Synchronization?

Semaphores are a method of inter-process communication (IPC) for synchronizing multiple processes.

The Lost Update

Suppose you had a bank application that managed deposits and withdraws to one account. Here is a simple pseudo program for doing this:

1. Read the account balance
2. Calculate the new balance/decision the withdraw
3. Write out the new balance

Here is what the program, balance, etc. might look like if we wanted to deposit $40:

Action	Amount	Balance
Read balance	N/A	100
Calculate new balance	140	100
Write updated balance	140	140

This works fine so long as there is only one process working with the account, but what if two processes are trying to handle operations on the account? Suppose one of them is trying to deposit $40, while the other wants to withdraw $70. Here is how it might look:

Process	Action	Amount	Balance
Deposit 40	Read balance	N/A	100
Withdraw 70	Read balance	N/A	100
Deposit 40	Calculate new balance	140	100
Deposit 40	Write updated balance	140	140
Withdraw 70	Calculate new balance	30	140
Withdraw 70	Write updated balance	30	30

The $40 deposit has been lost because of concurrent update issues.

Fix for the Lost Update Found!

Suppose the pseudo program were changed so that it took other processes into account:

1. Lock the account
2. Read the account balance
3. Calculate the new balance/decision the withdraw
4. Write out the new balance
5. Unlock the account

Now if the same problematic situation were to arise, here is how things might play out:

Process	Action	Amount	Balance
Deposit 40	Lock account	N/A	100
Deposit 40	Read balance	N/A	100
Withdraw 70	Lock account	Operation blocks	100
Deposit 40	Calculate new balance	140	100
Deposit 40	Write updated balance	140	140
Deposit 40	Unlock account	N/A	140
Withdraw 70	Lock account	operation completes	100
Withdraw 70	Read balance	N/A	140
Withdraw 70	Calculate new balance	70	140
Withdraw 70	Write updated balance	70	70
Withdraw 70	Unlock account	N/A	70

By putting in the locks, the deposit is no longer lost.

Binary Semaphores as Exclusive Locks

In this situation, a binary semaphore could implement the "lock/unlock" operations used to synchronize access to the account.

A binary semaphore allows two states: reserved and available. If a process tries to reserve a semaphore that has already been reserved, as when the withraw process tries to perform its operation when the deposit processes has locked the account, the requesting process will block and go into a waiting/sleep state.

When the process that has reserved the semaphore releases it, the operating system chooses a process that is waiting for the semaphore and unblocks it. The above scenario depicts just such a situation.

The underlying mechanism for a semaphore is an integer value. When a process wants to reserve the semaphore, they decrement the semaphore's value. When the process is done with the resource, it releases the semaphore by incrementing its value.

With a binary semaphore, the object can have a value of 0 or 1. Therefore, if the semaphore has a value of 1 and a processes wants to reserve it by decrementing the semaphore, the semaphore's value becomes 0. When done with the resource, the process increments the semaphore and the value becomes 1.

If a process tries to decrement a semaphore whose value is already 0, the operation blocks until the other process that "owns" the semaphore increments it again.

Conclusion

That was a quick introduction to synchronization and semaphores. In future posts, I will go over how semaphores are used in CLIPC.