CLIPC File Naming

NOTE

The source code shown here may not be up on SourceForge until 4/23/2009 (Friday). This is due to some last minute problems found with the Linux code. I'll provide more information as it becomes available.

The Short Story

CLIPC uses file names to identify IPC resources. If two processes use the same file name for a Semaphore, they get connected to the same Semaphore.

The Long Story

You can find the source code and examples for CLIPC on SourceForge.

Naming: The Orphan Child of IPC

It seems to me that a great deal of effort has gone into ensuring that various IPC schemes are "correct" or that their waiting schemes are "fair," while somewhat less effort has gone into ensuring that they are easy to use. In particular, how do two processes that have no prior association connect in order to communicate?

Different platforms use different schemes for dealing with this problem. For semaphores, Windows has a "namespace" set aside for Semaphores and a bunch of other objects. In Linux there are several approaches. One of them is to use a restricted name space, another is to use integer values to identify the Semaphore.

File Names: a Ubiquitous Concept Across Platforms

A lot of effort during the design and evolution of Java to make file naming across platforms easier. For example, the path "/what/ever/one" will work on both Linux and Windows.

CLIPC builds on that strength in order to solve the naming problem for some IPC mechanisms.

In the case of Semaphores, CLIPC uses a file name to identify which Semaphore a client wants to use. If two processes use the same file name when creating a Semaphore, the two processes will end up connected together through that semaphore.

A nice side-effect of using file names to identify resources is that it solves the problem of who can use the resource. For example, if a client does not have permission to read a file associated with a semaphore, then they cannot access the associated semaphore.

Semaphore File Naming in CLIPC

In CLIPC, a client must specify a file name in order to connect to a Semphore. Here is an example where the file name is specified when the constructor is called:

Semaphore s = new Semaphore("/mysem");

Here is an example where the file name is specified when the Semaphore is connected to the underlying system resource:

Semaphore s = new Semaphore();
...
s.connect("/mysem");

CLIPC uses the name of the file to store a value that, when used in the underlying system call, will identify a Semaphore to the platform. If such a file exists at the time when the connection occurs, CLIPC will use the contents of the existing file instead of creating a new file.

File Creation and Race Conditions

Such a scheme has an inherent race condition in that if two processes decide to create the file at the same time, it is possible that both with think they were successful, yet each is using a different underlying identifier.

CLIPC handles this problem by using a two step process:

• Create a temporary file and populate it with an identifier
• Rename the temp file to the desired file name

For windows and Linux, renaming can be an atomic operation. In particular, it can be made to fail if the desired name is already being used. This ensures that in the case where two processes try to create the file at the same time, only one will succeed.

Conclusion

CLIPC uses file names for handling the issue of identifying which IPC Semaphore a client wants to use. File names are ubiuitous across platforms that Java supports, making them convenient for use as IPC "names." CLIPC uses files with semaphores to store the underlying platform ID for a semaphore.

CLIPC Semaphores in Action

The Short Story

How the CLIPC Semaphore class can be used to solve the lost update problem.

The Long Story

You can find the source code for CLIPC on SourceForge. The example that I'm showing here can also be found on SourceForge.

The Lost Update: How Not to Run a Bank

Here is some code that implements the bank application described in the previous blog entry on semaphores.

An account is implemented as a text file that contains the balance of the account. Clients use the following process:

1. Pause for a random period of time
2. Read the account balance from the file
3. Pause for a random period of time
4. Calculate the new balance/decision the withdraw
5. Write out the new balance to the file

The program randomly decides the amount to deposit/withdraw, with the limitation that it cannot withdraw more money than exists in the account.

   public void run(File file, Random r) throws Exception
   {
       ThreadUtils.sleep(r.nextInt(2000));
       int balance = readBalance(file);
       sleep(r.nextInt(4000));
       int amount = generateTransactionAmount(r, balance);
       printMessage(balance, amount);
       balance = balance + amount;
       writeBalance(file, balance);
   }

Here is a screenshot of the app not working quite as desired:

With Semaphores: the Lost Update Found!

By adding a semaphore, the lost update problem can be avoided. The previous process needs to be modified a little bit:

1. Lock the account (reserve the semaphore)
2. Read the account balance from the file
3. Pause for a random period of time
4. Calculate the new balance/decision the withdraw
5. Write out the new balance to the file
6. Unlock the account (release the semaphore)

The modified code:

   public void run(Semaphore sem, File file, Random r) throws Exception
   {
       ThreadUtils.sleep(r.nextInt(2000));
       sem.decrement();
       int balance = readBalance(file);
       sleep(r.nextInt(4000));
       int amount = generateTransactionAmount(r, balance);
       printMessage(balance, amount);
       balance = balance + amount;
       writeBalance(file, balance);
       sem.increment();
   }

The output from the revised sample program:

The code to connect to the semaphore or to create it if it does not already exist is:

 Semaphore(fileName);

The file is an actual file that is used to allow clients to connect to the same semaphore. I'll explain more in the next post.

This code creates a binary semaphore. To create a semaphore that can have a max value of "n" use this call:

 Semaphore(fileName, max value);

For this example, a binary semaphore was used. A command line argument passed the name of the semaphore file.

 sem = new Semaphore(argv[1]);

Conclusion

This posting contained a quick example of how to solve the "Lost Update" problem described in a previous post using a binary semaphore from the CLIPC library. The sample code can be obtained from SourceForge, along with the rest of the CLIPC code.

This example uses file naming for semaphores without really explaining what file naming is or what it is for. In the next exciting chapter of the ongoing CLIPC saga, I will explain how that works.

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.