Semaphores can be thought of as simple counters that indicate the status of a resource. The usage of this semaphore variable is simple. If counter is greater that 0, then the resource is available, and if the counter is 0 or less, then that resource is busy or being used by someone else. This simple mechanism helps in synchronizing multithreaded and multiprocess based applications. [updated:3/5/2010]
A semaphore is as an object with an integer value that we can manipulate with two routines (sem_wait() and sem_post() in POSIX standard). Because the initial value of the semaphore determines its behavior, before calling any other routine to interact with the semaphore, we must first initialize it to some value, as this code below does:
sem_wait() will either return right away (because the value of the semaphore was 1 or higher when we called sem_wait()), or it will cause the caller to suspend execution waiting for a subsequent post. Of course, multiple calling threads may call into sem_wait(), and thus all be queued waiting to be woken. Once woken, the waiting thread will then decrement the value of the semaphore and return to the user.
sem_post() does not ever suspend the caller. Rather, it simply increments the value of the semaphore and then, if there is a thread waiting to be woken, wakes 1 of them up.
#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1); // replace 1 with X
...
// lock the resource
int sem_wait(sem_t *s) {
wait until value of semaphore s is > 0
decrement the value of semaphore s by 1
}
... do some stuff
// release the resource
int sem_post(sem_t *s) {
increment the value of semaphore s by 1
if there are 1 or more threads waiting, wake 1
}
Look at the following code, the *producer/consumer* problem:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#define MAX 1 //2
sem_t empty;
sem_t full;
int loops = 100;
int buffer[MAX];
int fill = 0;
int use = 0;
void put(int value) {
buffer[fill] = value; // line F1
fill = (fill + 1) % MAX; // line F2
}
int get() {
int tmp = buffer[use]; // line G1
use = (use + 1) % MAX; // line G2
return tmp;
}
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&empty); // line P1
put(i); // line P2
sem_post(&full); // line P3
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&full); // line C1
int tmp = get(); // line C2
sem_post(&empty); // line C3
printf("%d\n", tmp);
}
}
int main(int argc, char *argv[])
{
pthread_t pid, cid, pid2;
sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with...
sem_init(&full, 0, 0); // ... and 0 are full
pthread_create(&pid, NULL, producer, NULL);
//pthread_create(&pid2, NULL, producer, NULL);
pthread_create(&cid, NULL, consumer, NULL);
pthread_join(pid, NULL);
//pthread_join(pid2, NULL);
pthread_join(cid, NULL);
return 0;
}
Let MAX=1 first. Assume the consumer gets to run first. Thus, the consumer will hit line C1 in the figure above, calling sem_wait(&full). Because full was initialized to the value 0, the call will block the consumer and wait for another thread to call sem_post() on the semaphore, as desired.
Let's say the producer then runs. It will hit line P1, calling sem_wait(&empty). Unlike the consumer, the producer will continue through this line, because empty was initialized to the value MAX (in this case, 1). Thus, empty will be decremented to 0 and the producer will put a data value into the first entry of buffer (line P2). The producer will then continue on to P3 and call sem_post(&full), changing the value of the full semaphore from 0 to 1 and waking the consumer (e.g., move it from blocked to ready).
In this case, one of two things could happen. If the producer continues to run, it will loop around and hit line P1 again. This time, however, it would block, as the empty semaphore's value is 0. If the producer instead was interrupted and the consumer began to run, it would call sem_wait(&full) (line C1) and find that the buffer was indeed full and thus consume it. In either case, we achieve the desired behavior.
When MAX > 1, and we have multiple producers and consumers (uncomments pid2). There is problem. Imagine two producers both calling into put() at roughly the same time. Assume producer 1 gets to run first, and just starts to fill the first buffer entry (fill = 0 @ line F1). Before the producer gets a chance to increment the fill counter to 1, it is interrupted. Producer 2 starts to run, and at line F1 it also puts its data into the 0th element of buffer, which means that the old data there is overwritten!
What we've forgotten here is *mutual exclusion*. The filling of a buffer and incrementing of the index into the buffer is a *critical section*, and thus must be guarded carefully. So let's use our friend the binary semaphore and add some locks. Here is our first try:
sem_t empty;
sem_t full;
sem_t mutex;
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&mutex); // line P0 (NEW LINE)
sem_wait(&empty); // line P1
put(i); // line P2
sem_post(&full); // line P3
sem_post(&mutex); // line P4 (NEW LINE)
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&mutex); // line C0 (NEW LINE)
sem_wait(&full); // line C1
int tmp = get(); // line C2
sem_post(&empty); // line C3
sem_post(&mutex); // line C4 (NEW LINE)
printf("%d\n", tmp);
}
}
int main(int argc, char *argv[]) {
// ...
sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with...
sem_init(&full, 0, 0); // ... and 0 are full
sem_init(&mutex, 0, 1); // mutex = 1 because it is a lock (NEW LINE)
// ...
}
Deadlock happens here.
Imagine two threads, one producer and one consumer. The consumer gets to run first. It acquires the mutex (line C0), and then calls
sem_wait() on the full semaphore (line C1); because there is no data yet, this call causes the consumer to block and thus yield the CPU; importantly, though, the consumer still
holds the lock.
A producer then runs. It has data to produce and if it were able to run, it would be able to wake the consumer thread and all would be good. Unfortunately, the first thing it does is call sem_wait on the binary mutex semaphore (line P0). The lock is already held. Hence, the producer is now stuck waiting too.
There is a simple cycle here. The consumer holds the mutex and is waiting for the someone to signal full. The producer could *signal* full but is waiting for the mutex. Thus, the producer and consumer are each stuck waiting for each other: a classic deadlock.
Solution:
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&empty); // line P1
sem_wait(&mutex); // line P1.5 (MOVED THE MUTEX TO HERE ...)
put(i); // line P2
sem_post(&mutex); // line P2.5 (... AND TO HERE)
sem_post(&full); // line P3
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&full); // line C1
sem_wait(&mutex); // line C1.5 (MOVED THE MUTEX TO HERE ...)
int tmp = get(); // line C2
sem_post(&mutex); // line C2.5 (... AND TO HERE)
sem_post(&empty); // line C3
printf("%d\n", tmp);
}
}all are from following
class, a free book about semaphore
here, and an article comparing mutex, semaphore
here.
--
A semaphore is the number of free identical toilet keys. Example, say we have four toilets with identical locks and keys. The semaphore count - the count of keys - is set to 4 at beginning (all four toilets are free), then the count value is decremented as people are coming in. If all toilets are full, ie. there are no free keys left, the semaphore count is 0. Now, when eq. one person leaves the toilet, semaphore is increased to 1 (one free key), and given to the next person in the queue.
A mutex is a key to a toilet. One person can have the key - occupy the toilet - at the time. When finished, the person gives (frees) the key to the next person in the queue. [quote from following
link, update:3/5/2010]
