[Semaphore] What is a counting semaphore?

      Comments Off on [Semaphore] What is a counting semaphore?

(Sưu tầm)

What is a counting semaphore?

A counting semaphore contains a value and supports two operations “wait” and “post”. Post increments the semaphore and immediately returns. “wait” will wait if the count is zero. If the count is non-zero the semaphore decrements the count and immediately returns.

An analogy is a count of the cookies in a cookie jar (or gold coins in the treasure chest). Before taking a cookie, call ‘wait’. If there are no cookies left then wait will not return: It will wait until another thread increments the semaphore by calling post.

In short, post increments and immediately returns whereas wait will wait if the count is zero. Before returning it will decrement count.

How do I create a semaphore?

This page introduces unnamed semaphores. Unfortunately Mac OS X does not support these yet.

First decide if the initial value should be zero or some other value (e.g. the number of remaining spaces in an array). Unlike pthread mutex there are not shortcuts to creating a semaphore – use sem_init

#include <semaphore.h>

sem_t s;
int main() {
  sem_init(&s, 0, 10); // returns -1 (=FAILED) on OS X
  sem_wait(&s); // Could do this 10 times without blocking
  sem_post(&s); // Announce that we've finished (and one more resource item is available; increment count)
  sem_destroy(&s); // release resources of the semaphore
}

Can I use a semaphore instead of a mutex?

Yes – though the overhead of a semaphore is greater. To use a semaphore:

  • Initialize the semaphore with a count of one.
  • Replace ...lock with sem_wait
  • Replace ...unlock with sem_post

A mutex is a semaphore that always waits before it posts


sem_t s;
sem_init(&s, 0, 1);

sem_wait(&s);
// Critical Section
sem_post(&s);

wait chỉ block khi count=0,

Khi wait thì count tự động trừ đi, khi post thì tự động tăng lên. Semaphore phù hợp với trường hợp nhiều thread có thể nhảy vào vùng critical section, quá maximum thì phải đợi.

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.

Officially: “Mutexes are typically used to serialise access to a section of re-entrant code that cannot be executed concurrently by more than one thread. A mutex object only allows one thread into a controlled section, forcing other threads which attempt to gain access to that section to wait until the first thread has exited from that section.” Ref: Symbian Developer Library

(A mutex is really a semaphore with value 1.)

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.

Officially: “A semaphore restricts the number of simultaneous users of a shared resource up to a maximum number. Threads can request access to the resource (decrementing the semaphore), and can signal that they have finished using the resource (incrementing the semaphore).” Ref: Symbian Developer Library

Ví dụ full

#define HAVE_STRUCT_TIMESPEC
#include<pthread.h>
#include<stdio.h>
#include<semaphore.h>
#include <windows.h>

sem_t mutex;

void * thread(void* arg) {
	int *p = (int*)arg;
	//wait
	sem_wait(&mutex);
	printf("Entered... n=%d\n",*p);

	// Critical section
	Sleep(5);
	printf("Just exiting n=%d\n",*p);
	sem_post(&mutex);
	return NULL;
}
int main() {
	sem_init(&mutex, 0, 1); // Tối đa 1 thread chạy 1 lúc, value =1 => giống với mutex lock.
	int count = 0;
	pthread_t t1, t2;
	int n1 = 10;
	int n2 = 11;
	sem_getvalue(&mutex, &count);
	printf("count = %d\n",count);
	pthread_create(&t1, NULL, thread, &n1);
	pthread_create(&t2, NULL, thread, &n2);
	pthread_join(t1, NULL);
	pthread_join(t2, NULL);
	sem_destroy(&mutex);
	return 0;
}