1) Implement a counting semaphore using binary semaphores. Hint: Use two binary
ID: 3586120 • Letter: 1
Question
1) Implement a counting semaphore using binary semaphores.
Hint: Use two binary semaphores and an integer variable: use the integer
variable as the integer variable in the counting semaphore; use the first
binary semaphore as a mutex lock while updating the integer variable; use
the second binary semaphore to block/unblock the process depending on
the integer variable value
* Binary semaphore: A binary semaphore acts like a mutex lock. Its
definition is shown below.
wait(S){
while(S<=0)
; // busy wait
S—;
}
signal(S){
if(S==0)
S++;
}
Explanation / Answer
A semaphore can only be accessed using the following operations: wait() and signal(). wait() is called when a process wants access to a resource. This would be equivalent to the arriving customer trying to get an open table. If there is an open table, or the semaphore is greater than zero, then he can take that resource and sit at the table. If there is no open table and the semaphore is zero, that process must wait until it becomes available. signal() is called when a process is done using a resource, or when the patron is finished with his meal. The following is an implementation of this counting semaphore (where the value can be greater than 1):
wait(Semaphore s){
while (s==0); /* wait until s>0 */
s=s-1;
}
signal(Semaphore s){
s=s+1;
}
Init(Semaphore s , Int v){
s=v;
}
Historically, wait() was called P (for Dutch “Proberen” meaning to try) and signal() was called V (for Dutch “Verhogen” meaning to increment). The standard Java library instead uses the name "acquire" for P and "release" for V.
No other process can access the semaphore when P or V are executing. This is implemented with atomic hardware and code. An atomic operation is indivisible, that is, it can be considered to execute as a unit.
If there is only one count of a resource, a binary semaphore is used which can only have the values of 0 or 1. They are often used as mutex locks. Here is an implementation of mutual-exclusion using binary semaphores:
do
{
wait(s);
// critical section
signal(s);
// remainder section
} while(1);
In this implementation, a process wanting to enter its critical section it has to acquire the binary semaphore which will then give it mutual exclusion until it signals that it is done.
For example, we have semaphore s, and two processes, P1 and P2 that want to enter their critical sections at the same time. P1 first calls wait(s). The value of s is decremented to 0 and P1 enters its critical section. While P1 is in its critical section, P2 calls wait(s), but because the value of s is zero, it must wait until P1 finishes its critical section and executes signal(s). When P1 calls signal, the value of s is incremented to 1, and P2 can then proceed to execute in its critical section (after decrementing the semaphore again). Mutual exclusion is achieved because only one process can be in its critical section at any time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.