Editing Semaphore (programming) (section)

==Examples==

===Trivial example===
Consider a variable ''A'' and a boolean variable ''S''. ''A'' is only accessed when ''S'' is marked true. Thus, ''S'' is a semaphore for ''A''.

One can imagine a stoplight signal (''S'') just before a train station (''A''). In this case, if the signal is green, then one can enter the train station. If it is yellow or red (or any other color), the train station cannot be accessed.

===Login queue===
Consider a system that can only support ten users (S=10). Whenever a user logs in, P is called, decrementing the semaphore ''S'' by 1. Whenever a user logs out, V is called, incrementing ''S'' by 1 representing a login slot that has become available. When ''S'' is 0, any users wishing to log in must wait until ''S'' increases. The login request is enqueued onto a FIFO queue until a slot is freed. [[Mutual exclusion]] is used to ensure that requests are enqueued in order. Whenever ''S'' increases (login slots available), a login request is dequeued, and the user owning the request is allowed to log in. If ''S'' is already greater than 0, then login requests are immediately dequeued.

===Producer–consumer problem===

In the [[producer–consumer problem]], one process (the producer) generates data items and another process (the consumer) receives and uses them. They communicate using a queue of maximum size ''N'' and are subject to the following conditions:
* the consumer must wait for the producer to produce something if the queue is empty;
* the producer must wait for the consumer to consume something if the queue is full.

The semaphore solution to the producer–consumer problem tracks the state of the queue with two semaphores: <code>emptyCount</code>, the number of empty places in the queue, and <code>fullCount</code>, the number of elements in the queue. To maintain integrity, <code>emptyCount</code> may be lower (but never higher) than the actual number of empty places in the queue, and <code>fullCount</code> may be lower (but never higher) than the actual number of items in the queue. Empty places and items represent two kinds of resources, empty boxes and full boxes, and the semaphores <code>emptyCount</code> and <code>fullCount</code> maintain control over these resources.

The binary semaphore <code>useQueue</code> ensures that the integrity of the state of the queue itself is not compromised, for example, by two producers attempting to add items to an empty queue simultaneously, thereby corrupting its internal state. Alternatively a [[mutex]] could be used in place of the binary semaphore.

The <code>emptyCount</code> is initially ''N'', <code>fullCount</code> is initially 0, and <code>useQueue</code> is initially 1.

The producer does the following repeatedly:

 '''produce:'''
     P(emptyCount)
     P(useQueue)
     putItemIntoQueue(item)
     V(useQueue)
     V(fullCount)

The consumer does the following repeatedly

 '''consume:'''
     P(fullCount)
     P(useQueue)
     item ← getItemFromQueue()
     V(useQueue)
     V(emptyCount)

Below is a substantive example:
# A single consumer enters its critical section. Since <code>fullCount</code> is 0, the consumer blocks.
# Several producers enter the producer critical section. No more than ''N'' producers may enter their critical section due to <code>emptyCount</code> constraining their entry.
# The producers, one at a time, gain access to the queue through <code>useQueue</code> and deposit items in the queue.
# Once the first producer exits its critical section, <code>fullCount</code> is incremented, allowing one consumer to enter its critical section.

Note that <code>emptyCount</code> may be much lower than the actual number of empty places in the queue, for example, where many producers have decremented it but are waiting their turn on <code>useQueue</code> before filling empty places. Note that <code>emptyCount + fullCount ≤ ''N''</code> always holds, with equality if and only if no producers or consumers are executing their critical sections.

===Passing the baton pattern===
The "Passing the baton" pattern<ref>{{cite book |last1=Andrews |first1=Gregory R. | date=1999|publisher=	
Addison-Wesley|title=Foundations of Multithreaded, Parallel, and Distributed Programming}}</ref><ref>{{cite book |last1=Carver |first1=Richard H. |last2=Thai |first2=Kuo-Chung |date=2005|publisher=Wiley|title=Modern Multithreading: Implementing, Testing, and Debugging Multithreaded Java and C++/Pthreads/Win32 Programs}}</ref><ref>{{cite book |last1=Maurer |first1=Christian | date=2021|publisher=	
Springer|title=Nonsequential and Distributed Programming with Go}}</ref> proposed by Gregory R. Andrews is a generic scheme to solve many complex concurrent programming problems in which multiple processes compete for the same resource with complex access conditions (such as satisfying specific priority criteria or avoiding starvation). Given a shared resource, the pattern requires a private "priv" semaphore (initialized to zero) for each process (or class of processes) involved and a single mutual exclusion "mutex" semaphore (initialized to one). 
The pseudo-code for each process is:

<syntaxhighlight lang="cpp">
void process(int proc_id, int res_id)
{
	resource_acquire(proc_id, res_id);
	
	<use the resource res_id>;
	
	resource_release(proc_id, res_id);
}
</syntaxhighlight>

The pseudo-code of the resource acquisition and release primitives are:

<syntaxhighlight lang="cpp">
void resource_acquire(int proc_id, int res_id)
{
	P(mutex);
	
	if(<the condition to access res_id is not verified for proc_id>)
	{
		<indicate that proc_id is suspended for res_id>;
		V(mutex);
		P(priv[proc_id]);
		<indicate that proc_id is not suspended for res_id anymore>;
	}
	
	<indicate that proc_id is accessing the resource>;
	
	pass_the_baton(); // See below
}
</syntaxhighlight>

<syntaxhighlight lang="cpp">
void resource_release(int proc_id, int res_id)
{
	P(mutex);
	
	<indicate that proc_id is not accessing the resource res_id anymore>;
	
	pass_the_baton(); // See below
}
</syntaxhighlight>

Both primitives in turn use the "pass_the_baton" method, whose pseudo-code is:

<syntaxhighlight lang="cpp">
void pass_the_baton(int res_id)
{
	if <the condition to access res_id is true for at least one suspended process>
	{
		int p = <choose the process to wake>;
		V(priv[p]);
	}
	else
	{
		V(mutex);
	}
}
</syntaxhighlight>

'''Remarks'''

The pattern is called "passing the baton" because a process that releases the resource as well as a freshly reactivated process will activate at most one suspended process, that is, shall "pass the baton to it". The mutex is released only when a process is going to suspend itself (resource_acquire), or when pass_the_baton is unable to reactivate another suspended process.