Shared Memory
Shared memory allows multiple processes to share a given memory
process. Since the data does not need to be copied between processes,
this is the fastest form of
IPC.
Shared Memory Prototypes
There are four shared memory functions:
- int shmget(key_t key, size_t size, int flag); - Obtains a shared memory identifier
- int shmctl(int shmid, int cmd, struct shmid_ds *buf); - Performs various operations
- void *shmat(int shmid, const void *addr, int flag); - Attach a shared memory to process address space
- int shmdt(void *addr); - Detaches a shared memory address
Semaphores
A semaphore is a type of
IPC that uses a
counter to track access to a shared resource across separate processes.
The value of the counter indicates the remaining units available for a
given resource. When a unit of the resource is successfully obtained,
the counter is decremented, indicating one less unit of the resource is
available.
There are two main types of semaphores, binary semaphores and counting
semaphores. A binary semaphore can be used as a type of mutual-exclusion lock,
where there is only one unit of the resource available for use at a time —
The value of the semaphore counter is always either one or zero.
A counting semaphore can be used where there is more than one unit of the
resource, one example being to limit a server to a number of connections.
The idea of a semaphore can be explained using two main operations. The
first being a wait() or P() operation where a process is waiting for
a resource to be released or become available for it's use. The second
is a signal() or V() operation that is used when a process has finished
it's work and is ready to release the resource and allow other processes
to use it.
P() could be defined using pseudo-code as follows:
P(S) {
while S <= 0; // busy-wait while no resource available
S--; // decrement available resources
}
... and V() defined as:
V(S) {
S++; // increment available resources
}
Please note that for these definitions to work, they must be mutual-exclusive.
That is, the checking, fetching, and decrementing/incrementing must be atomic
within the function operations. For example sake we are assuming this to be the case.
Semaphore C Prototypes
Semaphores are implemented in C using three POSIX standard prototypes defined below. One semaphore
can be obtained (using semget()) and used as a set of counter values. This case will be
demonstrated below in the Dining Philosophers problem.
- int semget(key_t key, int nsems, int flag); - Used to obtain a semaphore ID
- int semctl(int semid, int semnum, int cmd, /* union semun arg */); - Perform various semaphore operations
- int semop(int semid, struct sembuf semoparray[], size_t nops); - Atomically performs array of operations on a semaphore set
Semaphore example — Dining Philosophers
The example code below demonstrates the classic computer science problem,
The Dining Philosophers' Problem. There are N number of philosophers dining around
a table. There is one chopstick both on the left and right of each philosopher.
Each chopstick is shared between two philosophers, but in order for a philosopher
to eat, they must obtain both at the same time.
Notice in the example below that a philosopher will first try to pick up their
right chopstick. The code has been written so that if the right chopstick is not
available to the process (or philosopher), it will go to sleep (or think) until it becomes available, and then the process will attempt to pick it up again.
After picking up the right chopstick, the process will then try to pick up the left
chopstick. This time the process will not automatically go to sleep and wait for the
left chopstick to become available, in other words it does not block.
If the left chopstick cannot be picked up, it will instead immediately put down the right chopstick, sleep (or think) for 1 second and then try again to pick up the right and
left chopstick. This operation prevents deadlocks from occuring, where two philosophers
cannot finish eating because each only has one chopstick and is holding onto it.
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/wait.h>
#include <signal.h>
#include <unistd.h>
#define FOODUNITS 2; /* units of food a philosopher must eat */
/* define structure for a philosopher */
struct phil {
int foodleft; /* units of food left to eat */
int lstick; /* semaphore member for left chopstick */
int rstick; /* semaphore member for right shopstick */
};
/* routine prototypes */
int forkPhil(struct phil, int);
bool P(int, bool);
bool V(int);
/* global vars */
int sid; /* semaphore id */
int main(int argc, char *argv[])
{
int philc; /* philosopher count */
int i; /* iterative variable used in loops */
union semun { /* semaphore union used for semctl() */
int val; /* value for SETVAL */
struct semi_ds *buf; /* buffer for IPC_STAT, IPC_SET */
unsigned short *array; /* array for GETALL, SETALL */
struct seminof *__buf; /* buffer for IPC_INFO (Linux-specific) */
} sunion;
struct phil phils; /* philosopher structure */
int pid; /* children process ids of philosophers */
/* get philosopher count */
if (argc == 2) {
philc = atoi(argv[1]);
if (philc < 2) {
fprintf(stderr, "ERROR: there must be at least 2 philosophers\n");
exit(1);
}
}
else if (argc == 1) {
philc = 6;
}
else {
fprintf(stderr, "Usage: dp <philosophers>\n");
exit(1);
}
/* create semaphore set for chopsticks (1 stick per philosopher) */
if ( (sid = semget(IPC_PRIVATE, philc, IPC_CREAT | 0700)) < 0) {
fprintf(stderr, "ERROR: failed to create semaphore\n");
exit(1);
}
/* initialize value for chopsticks to 1 (1 unit available) */
sunion.val = 1;
for (i = 0; i < philc; ++i) {
if (semctl(sid, i, SETVAL, sunion) != 0) {
fprintf(stderr, "ERROR: failed to initialize chopsticks!\n");
exit(1);
}
}
/* create philosophers (child processes) */
for (i = 0; i < philc; ++i) {
phils.foodleft = FOODUNITS;
phils.lstick = i;
phils.rstick = (i == 0) ? philc - 1 : i - 1;
if ( (pid = forkPhil(phils, i)) < 0) {
fprintf(stderr, "ERROR: forkPhil() failed!\n");
exit(1);
}
/* wait for process to send itself SIGSTOP */
waitpid(pid, NULL, WUNTRACED);
}
/* send continue signal to philosophers */
kill(0, SIGCONT);
/* wait for the philosopher's to finish eating */
for (i = 0; i < philc; ++i) {
wait(NULL);
}
printf("All philsopher's are done eating!\n");
return 0;
}
/*
* forks a new process simulating a dining philosopher
* Arguments:
* -struct phil phils - structure representing philosopher
* -int philid - philosopher id number
* Returns child process id on success, -1 on error
*/
int forkPhil(struct phil phils, int philid)
{
int pid; /* process id */
if ( (pid = fork()) < 0) {
fprintf(stderr, "ERROR: fork failed\n");
return -1;
}
else if (pid > 0) { /* parent process */
return pid;
}
/* child process */
/* stop the process to allow for creation of other philosophers */
fprintf(stderr, "DEBUG: Philsopher %d stopping...\n", philid);
kill(getpid(), SIGSTOP);
fprintf(stderr, "DEBUG: Philsopher %d continuing...\n", philid);
while (phils.foodleft > 0) {
fprintf(stderr, "DEBUG: Philosopher %d has %d units of food left\n",
philid, phils.foodleft);
/* pick up right chopstick */
if (!P(phils.rstick, true)) {
fprintf(stderr, "DEBUG: Philosopher %d failed to pick up right chopstick\n",
philid);
sleep(1);
continue; /* retry eating */
}
fprintf(stderr, "DEBUG: Philosopher %d has right chopstick\n", philid);
/* pick up left chopstick */
if (!P(phils.lstick, false)) {
fprintf(stderr, "DEBUG: Philosopher %d failed to pick up left chopstick\n",
philid);
V(phils.rstick);
fprintf(stderr, "DEBUG: Philosopher %d put down right chopstick\n",
philid);
sleep(1);
continue; /* retry eating */
}
fprintf(stderr, "DEBUG: Philosopher %d has left chopstick\n", philid);
/* eat a unit of food */
--phils.foodleft;
/* put down left chopstick */
V(phils.lstick);
fprintf(stderr, "DEBUG: Philosopher %d put down left chopstick\n", philid);
/* put down right chopstick */
V(phils.rstick);
fprintf(stderr, "DEBUG: Philosopher %d put down right chopstick\n", philid);
}
fprintf(stderr, "DEBUG: Philosopher %d has finished eating\n", philid);
/* kill the philosopher child process */
exit(0);
}
/**
* int P()
*
* Obtains a chopstick
*
* @param chopstick ID number of chopstick to obtain
* @param wait whether to wait or return immediately
*
* @return true when chopstick is obtained, false if in use
*/
bool P(int chopstick, bool wait)
{
struct sembuf sbuf; /* semaphore buffer for semop() */
sbuf.sem_op = -1; /* -1 to obtain resource */
sbuf.sem_num = chopstick;
if (!wait)
sbuf.sem_flg = IPC_NOWAIT;
if (semop(sid, &sbuf, 1) != 0)
return false;
return true;
}
/**
* int V()
*
* Releases a chopstick
*
* @param chopstick ID number of chopstick to release
*
* @return true on success, false on error
*/
bool V(int chopstick)
{
struct sembuf sbuf; /* semaphore buffer for semop() */
sbuf.sem_op = 1; /* +1 to release resource */
sbuf.sem_num = chopstick;
sbuf.sem_flg = IPC_NOWAIT;
if (semop(sid, &sbuf, 1) != 0)
return false;
return true;
}