Semaphore

Semaphore

A semaphore manages process synchronization for finite resources. For example, bank customers receive numbers and can use a service counter when their number is called.

A semaphore provides counting synchronization: acquire() reduces the available count and release() increases it. An acquire blocks when no permit is available.

A Lock normally allows one participant at a time; a semaphore can manage concurrent access to a limited number of resources.

Semaphore Synchronization

import multiprocessing
import time

def work(semaphore):
	with semaphore:
		print("[Process %d] Start" % multiprocessing.current_process().pid)
		time.sleep(2)
		print("[Process %d] End" % multiprocessing.current_process().pid)

def main():
	semaphore = multiprocessing.Semaphore(3)
	workers = [multiprocessing.Process(target=work, args=(semaphore,))
			   for _ in range(10)]
	for worker in workers:
		worker.start()
	for worker in workers:
		worker.join()

if __name__ == "__main__":
	main()

A semaphore is an integer accessed, except for initialization, through atomic wait() and signal() operations. These are also called P/V, from the Dutch proberen (test) and verhogen (increment).

wait(s) {
	while (s <= 0) { }
	s--;
}

signal(s) {
	s++;
}

This is not the final implementation. A blocking semaphore should address two issues:

1. Avoid busy waiting.
2. Record the number of waiting processes.

To avoid busy waiting, wait() and signal() must change. If no resource is available, the process blocks itself; after another process executes signal(), a waiter is awakened and becomes ready.

In a signed-count implementation, the values mean:

• $s>0$: s resources are available.
• $s=0$: no resource is available.
• $s<0$: the wait queue contains $|s|$ processes.

A semaphore based on blocking and wakeup can be defined as:

typedef struct {
	int value;
	struct process *list;
} Semaphore;

Non-busy-waiting wait() / signal() require coordinated atomic count and queue updates:

wait(Semaphore *s) {
	s->value--;
	if (s->value < 0) {
		add this process to s->list;
		block();
	}
}

signal(Semaphore *s) {
	s->value++;
	if (s->value <= 0) {
		remove a process from s->list;
		wakeup(that process);
	}
}