The next program uses a pipe for semaphore operations. It works because:
UNIX input and output operations are indivisible.
The semaphore value is implicit in the number of bytes in the pipe.
A waiting thread is awakened when a byte arrives in the pipe to read.
In the criticalSection.c, the semaphore is used to guard a critical section consisting of 3 lines of printout.
If the syncronization works, we should never see printout lines interleaved with lines from another thread.
UNIX System V Semaphores
UNIX System V provides not just semaphores but Semaphore Sets.
They provide a powerful mechanism for solving complex synchronization problems.
Semaphore sets can exist independently of the processes that created and used them. That is, they are persistent, like files. You have to explicitly remove them from the system.
There is a shell command for looking at them:
ipcs -s -a
Take a look on your machine and on turing
UNIX System V Semaphores
If they belong to you, you can remove them with the command:
ipcrm -s <semid>
A Semaphore set is an array of semaphores, not just one.
In a single atomic operation you can alter the value of each semaphore in the set in different ways.
You can wait for a semaphore in the set to be non-zero.
You can also wait for a semaphore in the set to be zero.
UNIX System V Semaphores
Semaphore sets are created using a key of type key_t.
A process can create a semaphore set using a key.
A process can also access an already existing one using it's key.
The routine:
#include <sys/types.h>
#include <sys/ipc.h>
key_t ftok(const char *pathname, int pin);
ftok is used to create a key from:
An existing accessible file pathname.
An non-zero number pin.
Thus unrelated processes can access the same semaphore set.
When used strictly for related processes or threads, the key can be IPC_PRIVATE.
UNIX System V Semaphores
A semaphore in a set takes a non-negative short int value.
int semop(int semid, struct sembuf *sops, unsigned nsops);
UNIX System V Semaphores
Overlooking the issue of generating keys, semget:
int semget(
key_t key, /* the key or IPC_PRIVATE */
int nsems, /* the number of semaphores in the set */
int semflg /* IPC_CREAT, IPC_EXCL, or file permissions */
);
The return value is -1 on failure, and errno is set.
The return value on success is the semid of the semaphore set.
The remaining operations use this semid to refer to the semaphore set.
The semflg uses the file permission modes of open and creat.
For more details, read man semget.
UNIX System V Semaphores
Operations are performed on a semaphore set using semctl.
int semctl(
int semid, /* the id of the semaphore set */
int semnum, /* the element of the set we are focused on */
int cmd, /* one of the ten (10) possible operations */
...
);
Semaphore elements of the semaphore set start at 0 and go to nsems - 1.
For each command semctl has either three (3) or four (4) arguments.
For some commands the second argument is irrelevant.
The fourth argument, when needed, is of type union semun.
UNIX System V Semaphores
The commands we are interested in are:
SETALL - initialize (or set) all the values of the set.
Four arguments are needed for this command.
IPC_RMID - remove the set from the file system.
Three arguments are needed for this command.
UNIX System V Semaphores
semctl returns -1 on failure, and sets errno.
On success semctl returns a non-negative value, depending on the command.
To remove a semaphore set with id semid from the file system:
semctl(semid, 0, IPC_RMID);
To initialize (all to zero) a semaphore set with id semid and, say, 4 elements:
int retval;
union semun arg; /* copy the definition from the man pages */
unsigned short values[4] = { 0, 0, 0, 0};
arg.array = values;
retval = semctl(semid, 0, SETALL, arg);
UNIX System V Semaphores
Operations on elements of a semaphore set are carried out by semop.
int semop(
int semid, /* the id of the semaphore set */
struct sembuf *sops, /* an array of operations */
unsigned nsops /* the length of the array */
);
The struct sembuf has the following relevant fields:
unsigned short sem_num; /* semaphore number from 0 upto nsems - 1 */
short sem_op; /* the aamout to add to the value */
short sem_flg; /* flags: 0, IPC_NOWAIT or SEM_UNDO */
UNIX System V Semaphores
semop attempts to atomically:
increment the sem_num semaphore by sem_op, if this is positive.
decrement the sem_num semaphore by sem_op, if this is negative.
As usual decrementing a semaphore whose value is 0 blocks.
The whole operation blocks if one operation in it blocks.
If the whole operation blocks, none of the operations take place.
To post each semaphore in our four (4) element
semaphore set:
int i, retval;
struct sembuf ops[4];
for(i = 0; i < 4; i++){
ops[i].sem_num = i;
ops[i].sem_op = 1;
ops[i].sem_flg = 0;
}
retval = semop(semid, ops, 4);
UNIX System V Semaphores
To wait on all semaphores in our four (4) element semaphore set:
int i, retval;
struct sembuf ops[4];
for(i = 0; i < 4; i++){
ops[i].sem_num = i;
ops[i].sem_op = -1;
ops[i].sem_flg = 0;
}
retval = semop(semid, ops, 4);
If one of these waits blocks, they all do.
If one of these blocks, none get decremented.
The operations as a whole are atomic.
They take place simultaneously, and indivisibly!
The Dining Philosophers
The Dining Philosophers problem demonstrates another synchronization problem. The solution will use sem_ops.h
There are 5 philosophers who spend their time either thinking or eating.
The dining room consists of 5 plates with 5 forks, one between each plate.
In order to eat, a philosopher must have both the forks beside his plate.
The immediate problem is deadlock. If all 5 philosophers sit at a plate, then grab the fork to their left, and wait for the fork on their right to become available, we have a classic circular waiting deadlock problem.
The Dining Philosophers
This solution uses a general semaphore initially set to 4 to guard access to the dining room. Thus only 4 philosophers can get into the room at a time and the circular wait can't happen.
A semaphore (which may be binary) is used to guard access to each fork.
Producers and Consumers (Again)
There is a simple and elegant semaphore solution to the producers and consumers problem: prodcons.c
We require only two semaphores for the conditional waiting:
full has the number of slots that are currently in use.
empty has the number of slots that are currently free.
Thus, at all times, slots = empty + full
Notice the simplicity of the access protocols.
A Final Example
Finally, a brief hint at the power of semaphore set operations.
Reconsider the Dining Philosophers problem.
The first issue was to avoid deadlock. This issue goes away if the philosophers can simultaneously grab both forks - or neither.
That is, the semaphores guarding each fork are part of the same set and operations can then be atomically applied to two at once.