{"id":141,"date":"2018-07-19T07:30:55","date_gmt":"2018-07-19T07:30:55","guid":{"rendered":"http:\/\/csp3.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=141"},"modified":"2018-08-07T10:12:08","modified_gmt":"2018-08-07T10:12:08","slug":"process-synchronization-semaphores","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/chapter\/process-synchronization-semaphores\/","title":{"rendered":"Process Synchronization – Semaphores"},"content":{"raw":"
\r\n\r\n \r\n

14.1 Introduction<\/strong><\/p>\r\n \r\n

Cooperating processes share data. Hence, the processes that access the shared data need to be synchronized so that there is no data inconsistency. In the earlier modules, we saw a number of solutions that helped in achieving process synchronization. We learned solutions for two processes as well as for multiple processes. The solutions to the critical section problem learned in the earlier modules are not easy to generalize to more complex problems. To overcome this difficulty, we can use a synchronization tool called a semaphore. The objectives of this module are as follows:<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nTo understand what a semaphore is\r\n\r\nTo learn how semaphores can be used to achieve synchronization\r\n\r\nTo understand the difference between counting and binary semaphores\r\n\r\nTo learn how a counting semaphore can be implemented using binary semaphores\r\n\r\n \r\n\r\n14.2. Semaphores<\/strong>\r\n\r\n \r\n

A semaphore is a synchronization tool that does not require busy waiting. The semaphore is an integer variable. The semaphore, being an integer variable, is assigned an initial value. The initial value denotes the number of processes that can simultaneously access the shared resource guarded by the semaphore. For example, if the shared resource can be accessed by only one process, then the initial value is set to 1. The semaphore can be accessed only via two atomic operations, namely, wait (P <\/em>operation) and signal (V <\/em>operation).<\/p>\r\n \r\n\r\nThe definition of the wait operation is given below:\r\n

wait <\/em>(S<\/em>):<\/p>\r\n

while S<\/em>\u00a3 0 do no-op<\/em>; S<\/em>-<\/p>\r\n

-;<\/p>\r\n \r\n

Here S is the semaphore. Any process that wants to enter its critical section should first perform the wait operation on the semaphore. The wait operation works as follows: If the value of the semaphore is less than or equal to zero, the process waits in the while loop. If the value\u00a0of the semaphore is greater than zero, then the process comes out of the while loop and the value of the semaphore is decremented. Any process that comes out of its critical section should perform the signal operation on the semaphore.<\/p>\r\n \r\n\r\nThe definition of the signal operation is given below:\r\n

signal <\/em>(S<\/em>):<\/p>\r\n

S++;<\/em><\/p>\r\n \r\n\r\nIn the signal operation, the value of the semaphore is incremented.\r\n\r\n \r\n

The wait and signal operations are atomic or indivisible. Indivisibility of the wait and signal operations is ensured by the programming language or the operating system that implements it. It ensures that race conditions cannot arise over a semaphore.<\/p>\r\n\r\n<\/div>\r\n \r\n

We \u00a0can \u00a0use \u00a0semaphores \u00a0to \u00a0deal \u00a0with \u00a0the \u00a0<\/span>n<\/em>-process \u00a0critical-section \u00a0problem. \u00a0The following section explains how a semaphore can be used to solve the critical-section problem.<\/span><\/p>\r\n\r\n

\r\n\r\n \r\n\r\n14.2.1 Critical Section of n <\/em>Processes<\/strong>\r\n\r\n \r\n\r\nShared data:\r\n

semaphore mutex; \/\/initially mutex <\/em>= 1<\/p>\r\n \r\n

The algorithm for process P<\/em>i is given below:<\/p>\r\n

do {<\/span><\/p>\r\n

\u00a0wait (mutex);<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n

critical section<\/p>\r\n

signal (mutex);<\/p>\r\n

remainder section<\/p>\r\n\r\n<\/div>\r\n

} while (1);<\/span><\/p>\r\n\r\n

\r\n\r\n \r\n

A semaphore called \u2018mutex\u2019 is used here for guarding a shared resource. The initial value of \u2018mutex\u2019 is set to one. This means that only one process can use the shared resource at a particular time. Process P<\/em>i, before entering its critical section, waits on the semaphore mutex. Process P<\/em>i, after coming out of its critical section, signals the semaphore \u2018mutex\u2019.<\/p>\r\n \r\n

Let us now see a sequence of execution of two processes P<\/em>0<\/sub> and P<\/em>1<\/sub>\u00a0 wanting to enter their respective critical sections.<\/p>\r\n \r\n\r\nP<\/em><\/strong>0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>mutex\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 P<\/em><\/strong>1<\/strong>\r\n\r\n1\r\n\r\nwait operation\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0\r\n\r\n<\/div>\r\n

Process enters critical section\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0wait operation\u00a0<\/span><\/p>\r\n\r\n

\r\n\r\n\u00a0 \u00a0signal operation \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Process waits<\/span>\r\n\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 0\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Process enters<\/span>\r\n\r\n<\/div>\r\n
\r\n\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 critical section\r\n\r\n1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0signal operation\r\n\r\n \r\n

Initially, process P<\/em>0 wants to enter its critical section. P<\/em>0 executes the wait operation on the semaphore mutex. Since the value of mutex is 1, the wait operation decrements the value of mutex. The value of mutex becomes 0. P<\/em>0 enters its critical section. In the meantime, if process P<\/em>1 wants to enter its critical section, it executes the wait operation. Since the value of mutex is 0, process P<\/em>1 continues to wait in the while loop while S<\/em><\/strong>\u00a3 0 do no-op<\/em>;<\/strong>. When process P<\/em>0 comes out of its critical section, it executes the signal operation on the semaphore mutex. This signal operation increments the value of mutex. The value of mutex now becomes 1. Process P<\/em>1, which is checking the value of mutex in the while loop, now comes out of the while loop, decrements the value of mutex to 0 and enters its critical section.<\/p>\r\n \r\n

The implementation of the wait and signal operations on a semaphore that we have seen now has a disadvantage \u2013 busy waiting. That is, when one process is in its critical section, any other process trying to enter its critical section, continuously checks the value of semaphore in the wait operation. Whenever the process waiting to enter its critical section gets the CPU, it executes while S<\/em><\/strong>\u00a3 0 do no-op<\/em>;. <\/strong>That is, the process just keeps on checking if S <\/em>\u00a3 0. The value\u00a0of S is not going to change until this process relinquishes the CPU and some other process changes it. This busy waiting wastes CPU cycles in multi-programmed systems with single CPU. Such a semaphore is called a spinlock.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Let us look at an example to understand spinlock. Let the initial value of semaphore S be 1. Assume that one process acquired a resource after executing a wait on the semaphore S and is continuing to use the resource. Let there be 2 other processes waiting to access the shared resource. Let round robin scheduling be the CPU scheduling algorithm. When the second process gets its CPU time slice, it will execute the while loop continuously in wait till its CPU time slice gets over. During this CPU time slice, the CPU time is used without doing any useful work. After this time slice, the third process gets its time slice. The third process also uses its entire time slice by just checking in the while loop of wait. The CPU\u2019s time is not used for any useful work. Thus it is seen that spinlock wastes CPU time.<\/p>\r\n \r\n

Spinlock is useful in multiprocessor systems. The advantage of spinlock is that no context switch is required when a process must wait on a lock. This is useful when locks are for short times.<\/p>\r\n \r\n

To overcome this busy waiting, the definitions of the wait and signal operations of the semaphore are modified. The semaphore is implemented as a structure or a record, rather than as just a variable. The structure has two members, an integer value and a list of processes associated with the semaphore.<\/p>\r\n \r\n\r\nThe semaphore is defined as follows:\r\n\r\ntypedef struct {\r\n

int value;<\/p>\r\n

struct process *L;<\/p>\r\n} semaphore;\r\n\r\n \r\n

Two operations are defined on processes associated with the semaphore, the block and the wakeup operations. The block operation suspends the process that invokes it. The wakeup(P) operation resumes the execution of a blocked process P.<\/p>\r\n \r\n\r\nThe wait and signal operations on a semaphore are now defined as\r\n\r\n \r\n\r\nwait<\/em><\/strong>(S):<\/strong>\r\n

S.value--;<\/p>\r\n

if (S.value < 0)<\/p>\r\n

{<\/p>\r\n

add this process to S.L;<\/p>\r\n

block;<\/p>\r\n

}<\/p>\r\n \r\n

Here S is the semaphore structure. It has an integer value (S.value) and a list of processes (S.L) associated with it. In the wait operation, the value of the semaphore is first decremented (S.value--;). Then the value of the semaphore is checked. If the value of the semaphore is less than zero, it means that the resource is not available. Therefore, the process that is executing wait is added to the list associated with the semaphore and is blocked (i.e., put to the waiting state). Compared to the earlier implementation of the wait operation, here the process does not keep on checking the value of the semaphore. Once the resource becomes available, this process is moved out of the waiting state and the process accesses the shared\u00a0resource.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nsignal(S<\/em><\/strong>):<\/strong>\r\n

S.value++;<\/p>\r\n

if (S.value <= 0)<\/p>\r\n

{<\/p>\r\n

remove a process P from S.L;<\/p>\r\n

wakeup(P);<\/p>\r\n

}<\/p>\r\n \r\n

In the signal operation, the value of the semaphore is incremented. This means that one more process can access the resource. Then the value of the semaphore is checked. If the value of the semaphore is less than or equal to zero, one of the waiting processes is woken up. The process that is woken up is moved to the ready state and can access the resource.<\/p>\r\n \r\n

The value of the semaphore is less than or equal to zero only if there are other processes waiting in the list associated with this semaphore. (The value had become less than zero when other processes had decremented the value of the semaphore earlier while executing wait).<\/p>\r\n \r\n\r\n14.3\u00a0 Semaphore as a General Synchronization Tool\u00a0<\/strong>\r\n\r\n \r\n

In this section, we see how the semaphore can be used as a synchronization tool. There are two processes P<\/em>i and P<\/em>j that want to access a common resource. Let flag <\/em>be the semaphore that guards the shared resource. The shared resource can be used by only one process at a time. Therefore, the value of the semaphore flag <\/em>is initialized to 1.<\/p>\r\n \r\n\r\nP<\/em><\/strong>i\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>Semaphore\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 P<\/em><\/strong>j<\/strong>\r\n\r\nflag = 1<\/span>\r\n\r\nwait(flag)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<\/span>\r\n\r\naccess resource\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0\u00a0flag = 0<\/span>\r\n\r\n \r\n\r\nsignal(flag)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0<\/span>\r\n\r\n<\/div>\r\n

\r\n\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0flag = -1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0wait(flag)<\/span>\r\n\r\nflag = 0\r\n\r\naccess resource\u00a0signal(flag)\r\n\r\nflag = 1\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n

Process P<\/em>i executes the wait operation on the semaphore. The wait operation decrements the value of the semaphore flag<\/em>. flag <\/em>becomes zero. Since the value of flag <\/em>is not less than zero, P<\/em>i can access the resource. In the meantime, if P<\/em>j wants to access the resource, P<\/em>j executes the wait operation on the semaphore flag<\/em>. flag <\/em>is decremented and becomes -1. Since the value of flag <\/em>is < 0, P<\/em>j is added to the list associated with the semaphore and is put to the waiting state.<\/p>\r\n \r\n

When process P<\/em>i completes the usage of the resource, it executes the signal operation on flag<\/em>. The value of flag <\/em>is incremented and becomes 0. Process P<\/em>j is woken up from the sleeping state. Process P<\/em>j now can access the resource. After P<\/em>j completes using the resource,\u00a0P<\/em>j executes the signal operation and the value of <\/span>flag <\/em>is incremented back to 1.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nIn this way, a semaphore can be used for safeguarding resources.\r\n\r\n \r\n\r\n14.4\u00a0 Deadlock and Starvation\u00a0<\/strong>\r\n\r\n \r\n

When semaphores are used for synchronization, it is possible to have deadlocks and starvation. Deadlock is a situation where two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes. For example, when two or more processes are waiting for the release of some resource that is held by another waiting process, it is a deadlock. Every process in a set of processes will be waiting for an event caused by one of the processes in the set. Starvation means indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended and it starves.<\/p>\r\n \r\n

Let us now see how deadlocks and starvation can happen with semaphores. Let S <\/em>and Q <\/em>be two semaphores initialized to 1. That is, semaphore S <\/em>is safeguarding a resource that can be accessed by only one process at a time. Similarly, semaphore Q <\/em>is also safeguarding another resource that can be accessed by only one process at a time.<\/p>\r\n

P<\/em>0<\/sub>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 P<\/em>1<\/sub><\/p>\r\n

wait<\/em>(S<\/em>);\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 wait<\/em>(Q<\/em>);<\/p>\r\n

wait<\/em>(Q<\/em>);\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 wait<\/em>(S<\/em>);<\/p>\r\n

\u00a0 \u00a0 :\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 :<\/p>\r\n

signal<\/em>(S<\/em>);\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 signal<\/em>(Q<\/em>);<\/p>\r\n

signal<\/em>(Q<\/em>)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 signal<\/em>(S<\/em>);<\/p>\r\n \r\n

Consider two processes P<\/em>0 and P<\/em>1. P<\/em>0 executes wait(S) and at the same time, P<\/em>1 executes wait(Q). The values of the semaphores S and Q become 0. P<\/em>0 then executes wait(Q) and waits till semaphore Q is signaled. P<\/em>1 then executes wait(S) and waits till the semaphore S is signaled. Here, we see that process P<\/em>0 is waiting for a resource held by P<\/em>1 and process P<\/em>1 is held by a resource held by P<\/em>0. Each of the two processes is waiting for a resource held by the other process. Therefore, both are unable to proceed. Both the processes wait indefinitely. Both the processes are caught in a deadlock and are starving.<\/p>\r\n \r\n

Therefore, the order in which wait and signal are used in processes should be selected carefully. Else, it may result in deadlocks and starvation also.<\/p>\r\n \r\n

Starvation is indefinite blocking. Starvation can also happen when processes that are added to the semaphore queue are removed in a last in first out manner. That is, whenever processes wait for a resource guarded by a semaphore, the processes are added to the queue associated with the semaphore. When more processes wait for the same resource, all these processes are also added to the end of the semaphore\u2019s queue. While removing processes from the queue, if the processes are removed from the end, the processes that were added first will starve.<\/p>\r\n \r\n\r\n14.5\u00a0 \u00a0Types of Semaphores\u00a0<\/strong>\r\n\r\n \r\n

There are two types of semaphores\u2014counting semaphores and binary semaphores. A counting semaphore takes an integer value that can range over an unrestricted domain. The semaphores that we discussed in the previous sections are counting semaphores. They are called counting semaphores because the value of the semaphores can be any integer value. A binary semaphore takes an integer value that can range only between 0 and 1. Hence, a binary\u00a0semaphore can be simpler to implement than counting semaphores. If we have the implementation of binary semaphores, we can implement\u00a0 counting semaphores using the implementation of binary semaphores.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

We now see how a counting semaphore S <\/em>can be implemented using binary semaphores. S1 and S2 are the binary semaphores using which the counting semaphore S is implemented. C is an ordinary variable and the initial value of C is set to the initial value of the counting\u00a0semaphore S. The initial value of the counting semaphore S indicates the number of processes that can access the resource guarded by the semaphore S at the same time.<\/p>\r\n \r\n\r\nData structures:<\/strong>\r\n

binary-semaphore S1, S2;<\/p>\r\n

int C;<\/p>\r\n \r\n

S1 and S2 are two binary semaphores and C is an integer variable.<\/p>\r\n \r\n\r\nInitialization:<\/span><\/strong>\r\n\r\n<\/div>\r\n

S1 = 1<\/span><\/div>\r\n
S2 = 0<\/span><\/div>\r\n
C = initial value of semaphore S<\/span><\/div>\r\n

C is assigned the initial value of the counting semaphore S. The initial values of S1 and S2 are assigned 1 and 0 respectively.<\/span><\/p>\r\n\r\n

\r\n\r\n \r\n\r\nWait and signal operations for binary semaphore:\u00a0<\/strong>\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\nIf S1 is a binary semaphore, then the wait operation on the binary semaphore is given\u00a0below:\r\n\r\n \r\n\r\nwait(S1)\r\n\r\n{\r\n\r\n<\/div>\r\n

while(S1==0)<\/span><\/p>\r\n

; S1--;<\/span><\/p>\r\n\r\n

\r\n

}<\/p>\r\n \r\n\r\nIf the value of the binary semaphore is zero, the process that executes the wait operation, waits in the while loop. If the value is not equal to zero, the process comes out of the while loop and decrements the value of the semaphore.\r\n\r\n \r\n\r\nsignal(S1)\r\n\r\n{\r\n

S1++;<\/p>\r\n}\r\n\r\n \r\n\r\nIn the signal operation, the value of the binary semaphore is incremented.\r\n\r\n \r\n\r\nThe wait and signal operations of the counting semaphore are given below:\r\n\r\n \r\n\r\nwait <\/em><\/strong>operation<\/strong>\r\n\r\nThe wait operation on the counting semaphore can be implemented using wait and signal operations on the binary semaphore as given below:\r\n\r\n \r\n\r\nwait(S1);\r\n\r\nC--;\r\n\r\nif (C < 0) {\r\n

signal(S1);<\/span><\/p>\r\n

wait(S2);<\/span><\/p>\r\n}<\/span>\r\n\r\nsignal(S1);\u00a0<\/span>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

The initial value of S1 is 1. Therefore, the wait operation on S1, finds that the value of S1 is not zero and decrements the value of S1. Next, the value of C is decremented. The initial value of C is equal to the value of the counting semaphore S. If the value of C becomes less than zero, then the process executing wait cannot proceed to execute its critical section. It has to wait. Therefore, the process signals S1 semaphore; the value of S1 becomes 1. Then, it waits on semaphore S2. Since the initial value of S2 is 0, the process waits on S2. If the value of C is not less than 0, it means that the process can enter its critical section. In this case, the process signals S1 and proceeds to enter its critical section. Here, we can see that the semaphore S1 guards the decrement of the variable C. The process waits on S1 before decrementing C and signals S1 after decrementing C. Semaphore S2 guards the shared resource.<\/p>\r\n \r\n\r\nsignal <\/em><\/strong>operation<\/strong>\r\n\r\n \r\n

The signal operation on S is also implemented using wait and signal operations on S1 and S2. The implementation of signal(S) is given below:<\/p>\r\n \r\n\r\nwait(S1);\r\n\r\nC ++;\r\n\r\nif (C <= 0)\r\n

signal(S2);<\/p>\r\nelse<\/span>\r\n

signal(S1);<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

The executing process first waits on S1. If no other process is currently incrementing or decrementing C, the value of S1 will be 1. wait(S1) decrements the value of S1 to 0. Then, C is incremented. If the value of C becomes less than or equal to zero, then it means that there is(are) other process(es) waiting to use the shared resource. In that case, signal(S2) is executed. As mentioned earlier, S2 is the semaphore that guards the shared resource. When signal(S2) is executed, another process waiting on S2 will come out of waiting, signal S1 (this is the signal(S1) in the wait operation) and proceed\u00a0 to use the shared\u00a0 resource. If C > 0, signal(S1) (in the signal operation) is executed.<\/p>\r\n \r\n\r\nLet us see with an example, how a counting semaphore is implemented using binary semaphores. Let C = 2 (initial value of semaphore S). Since the value of semaphore S is 2, two processes can use the shared resource at the same time. Let us see what happens when three processes want to use the shared resource at the same time.\r\n\r\n \r\n\r\nWhen wait(S) is executed by the first process, say P<\/em>0<\/sub>\r\n\r\n \r\n\r\nwait(S) by P<\/em>0<\/sub>:\u00a0<\/strong>\r\n\r\n \r\n\r\nS<\/strong>1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0C\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 S2<\/strong>\r\n\r\n1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0\r\n\r\n0\r\n\r\n1\r\n\r\n1\r\n\r\n<\/div>\r\n \r\n

Initially, S1 is 0, C is 2 and S2 is 0. wait(S1) decrements the value of S1 to 0. Then C is decremented from 2 to 1. signal(S1) increments the value of S1 back to 1. <\/span>P<\/em>0 gets access to the shared resource.<\/span><\/p>\r\n\r\n

\r\n\r\n \r\n\r\nIn the meantime, suppose process P<\/em>1 \u00a0wants to access the shared resource. The sequence is shown below:\r\n\r\n \r\n\r\nwait(S) by P<\/em>1<\/sub>:\u00a0<\/strong>\r\n\r\n \r\n\r\nS<\/strong>1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0C\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 S2<\/strong>\r\n\r\n1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0\r\n\r\n0\r\n\r\n0\r\n\r\n1\r\n\r\n \r\n

wait(S1) decrements the value of S1 from 1 to 0.Then C is decremented from 1 to 0. signal(S1) increments the value of S1 back to 1. P<\/em>1 gets access to the shared resource.<\/p>\r\n \r\n

In the meantime, suppose the third process P<\/em>2 \u00a0wants to access the shared resource. The sequence is shown below:<\/p>\r\n \r\n\r\nwait(S) by P<\/em>2<\/sub>:\u00a0<\/strong>\r\n\r\n \r\n\r\nS<\/strong>1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0C\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 S2<\/strong>\r\n\r\n1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0\r\n\r\n0\r\n\r\n-1\r\n\r\n1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Process P<\/em>2 waits on S2\r\n\r\n \r\n

wait(S1) decrements the value of S1 from 1 to 0.Then C is decremented from 0 to -1. Since the value of C goes below 0, process P<\/em>2 executes wait(S2). P<\/em>2 does not get access to the shared resource. Since the initial value of the semaphore S was 2, only two processes are able to access the shared resource. The other processes wait.<\/p>\r\n \r\n\r\nLet P<\/em>0 complete the usage of the shared resource. P<\/em>0 executes signal(S). The changes in the semaphores\u2019 values are shown below:\r\n\r\n \r\n\r\nWhen signal(S) is executed by P<\/em>0<\/sub>:\u00a0<\/strong>\r\n\r\n \r\n\r\nS<\/strong>1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 C\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 S2<\/strong>\r\n\r\n1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 -1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0\r\n\r\n0\r\n\r\n0<\/span>\r\n\r\nReleased process <\/span>P<\/em>2\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 <\/span><\/sub>1<\/span>\r\n\r\nsignals S1 1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<\/span>Process <\/span>P<\/em>2 \u00a0waiting on S2 is released<\/span>\r\n\r\n<\/div>\r\n \r\n

wait(S1) in the signal operation decrements the value of S1 from 1 to 0.Then C is incremented from \u20131 to 0. Since the value of C becomes 0, signal(S2) is executed. Process P<\/em>2 waiting on S2 is released. Process P<\/em>2 signals S1 (signal(S1) in the wait operation) and gains access to the shared resource.<\/p>\r\n \r\n

When signal(S) is executed by P<\/em>1<\/sub>:<\/strong><\/p>\r\n \r\n

S<\/strong>1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0C\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 S2<\/strong><\/p>\r\n

1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0<\/p>\r\n

0<\/p>\r\n

\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 1<\/p>\r\n

1<\/p>\r\n

wait(S1) in the signal operation\u00a0 decrements the value of S1 from 1 to 0.\u00a0 Then C is incremented from 0 to 1. Since the value of C becomes greater than 0, signal(S1) is executed. The value of S1 is changed from 0 to 1. Thus, we see that a counting semaphore can be implemented using binary semaphores.<\/p>\r\n \r\n

14.6\u00a0 \u00a0Summary<\/strong><\/p>\r\n \r\n

In this module, we learnt how a semaphore can be used as a synchronization tool. We understood that there are two types of semaphores \u2013 counting and binary semaphores. We also learnt how a counting semaphore is implemented using binary semaphores.<\/p>\r\n \r\n\r\n \r\n

References<\/strong><\/p>\r\n\r\n

    \r\n \t
  1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, \u201cOperating System Concepts\u201d, Ninth Edition, John Wiley & Sons Inc., 2012.<\/li>\r\n<\/ol>","rendered":"
    \n

     <\/p>\n

    14.1 Introduction<\/strong><\/p>\n

     <\/p>\n

    Cooperating processes share data. Hence, the processes that access the shared data need to be synchronized so that there is no data inconsistency. In the earlier modules, we saw a number of solutions that helped in achieving process synchronization. We learned solutions for two processes as well as for multiple processes. The solutions to the critical section problem learned in the earlier modules are not easy to generalize to more complex problems. To overcome this difficulty, we can use a synchronization tool called a semaphore. The objectives of this module are as follows:<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    To understand what a semaphore is<\/p>\n

    To learn how semaphores can be used to achieve synchronization<\/p>\n

    To understand the difference between counting and binary semaphores<\/p>\n

    To learn how a counting semaphore can be implemented using binary semaphores<\/p>\n

     <\/p>\n

    14.2. Semaphores<\/strong><\/p>\n

     <\/p>\n

    A semaphore is a synchronization tool that does not require busy waiting. The semaphore is an integer variable. The semaphore, being an integer variable, is assigned an initial value. The initial value denotes the number of processes that can simultaneously access the shared resource guarded by the semaphore. For example, if the shared resource can be accessed by only one process, then the initial value is set to 1. The semaphore can be accessed only via two atomic operations, namely, wait (P <\/em>operation) and signal (V <\/em>operation).<\/p>\n

     <\/p>\n

    The definition of the wait operation is given below:<\/p>\n

    wait <\/em>(S<\/em>):<\/p>\n

    while S<\/em>\u00a3 0 do no-op<\/em>; S<\/em>–<\/p>\n

    -;<\/p>\n

     <\/p>\n

    Here S is the semaphore. Any process that wants to enter its critical section should first perform the wait operation on the semaphore. The wait operation works as follows: If the value of the semaphore is less than or equal to zero, the process waits in the while loop. If the value\u00a0of the semaphore is greater than zero, then the process comes out of the while loop and the value of the semaphore is decremented. Any process that comes out of its critical section should perform the signal operation on the semaphore.<\/p>\n

     <\/p>\n

    The definition of the signal operation is given below:<\/p>\n

    signal <\/em>(S<\/em>):<\/p>\n

    S++;<\/em><\/p>\n

     <\/p>\n

    In the signal operation, the value of the semaphore is incremented.<\/p>\n

     <\/p>\n

    The wait and signal operations are atomic or indivisible. Indivisibility of the wait and signal operations is ensured by the programming language or the operating system that implements it. It ensures that race conditions cannot arise over a semaphore.<\/p>\n<\/div>\n

     <\/p>\n

    We \u00a0can \u00a0use \u00a0semaphores \u00a0to \u00a0deal \u00a0with \u00a0the \u00a0<\/span>n<\/em>-process \u00a0critical-section \u00a0problem. \u00a0The following section explains how a semaphore can be used to solve the critical-section problem.<\/span><\/p>\n

    \n

     <\/p>\n

    14.2.1 Critical Section of n <\/em>Processes<\/strong><\/p>\n

     <\/p>\n

    Shared data:<\/p>\n

    semaphore mutex; \/\/initially mutex <\/em>= 1<\/p>\n

     <\/p>\n

    The algorithm for process P<\/em>i is given below:<\/p>\n

    do {<\/span><\/p>\n

    \u00a0wait (mutex);<\/span><\/p>\n<\/div>\n

    \n

    critical section<\/p>\n

    signal (mutex);<\/p>\n

    remainder section<\/p>\n<\/div>\n

    } while (1);<\/span><\/p>\n

    \n

     <\/p>\n

    A semaphore called \u2018mutex\u2019 is used here for guarding a shared resource. The initial value of \u2018mutex\u2019 is set to one. This means that only one process can use the shared resource at a particular time. Process P<\/em>i, before entering its critical section, waits on the semaphore mutex. Process P<\/em>i, after coming out of its critical section, signals the semaphore \u2018mutex\u2019.<\/p>\n

     <\/p>\n

    Let us now see a sequence of execution of two processes P<\/em>0<\/sub> and P<\/em>1<\/sub>\u00a0 wanting to enter their respective critical sections.<\/p>\n

     <\/p>\n

    P<\/em><\/strong>0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>mutex\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 P<\/em><\/strong>1<\/strong><\/p>\n

    1<\/p>\n

    wait operation\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0<\/p>\n<\/div>\n

    Process enters critical section\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0wait operation\u00a0<\/span><\/p>\n

    \n

    \u00a0 \u00a0signal operation \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Process waits<\/span><\/p>\n

    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 0\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Process enters<\/span><\/p>\n<\/div>\n

    \n

    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 critical section<\/p>\n

    1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0signal operation<\/p>\n

     <\/p>\n

    Initially, process P<\/em>0 wants to enter its critical section. P<\/em>0 executes the wait operation on the semaphore mutex. Since the value of mutex is 1, the wait operation decrements the value of mutex. The value of mutex becomes 0. P<\/em>0 enters its critical section. In the meantime, if process P<\/em>1 wants to enter its critical section, it executes the wait operation. Since the value of mutex is 0, process P<\/em>1 continues to wait in the while loop while S<\/em><\/strong>\u00a3 0 do no-op<\/em>;<\/strong>. When process P<\/em>0 comes out of its critical section, it executes the signal operation on the semaphore mutex. This signal operation increments the value of mutex. The value of mutex now becomes 1. Process P<\/em>1, which is checking the value of mutex in the while loop, now comes out of the while loop, decrements the value of mutex to 0 and enters its critical section.<\/p>\n

     <\/p>\n

    The implementation of the wait and signal operations on a semaphore that we have seen now has a disadvantage \u2013 busy waiting. That is, when one process is in its critical section, any other process trying to enter its critical section, continuously checks the value of semaphore in the wait operation. Whenever the process waiting to enter its critical section gets the CPU, it executes while S<\/em><\/strong>\u00a3 0 do no-op<\/em>;. <\/strong>That is, the process just keeps on checking if S <\/em>\u00a3 0. The value\u00a0of S is not going to change until this process relinquishes the CPU and some other process changes it. This busy waiting wastes CPU cycles in multi-programmed systems with single CPU. Such a semaphore is called a spinlock.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    Let us look at an example to understand spinlock. Let the initial value of semaphore S be 1. Assume that one process acquired a resource after executing a wait on the semaphore S and is continuing to use the resource. Let there be 2 other processes waiting to access the shared resource. Let round robin scheduling be the CPU scheduling algorithm. When the second process gets its CPU time slice, it will execute the while loop continuously in wait till its CPU time slice gets over. During this CPU time slice, the CPU time is used without doing any useful work. After this time slice, the third process gets its time slice. The third process also uses its entire time slice by just checking in the while loop of wait. The CPU\u2019s time is not used for any useful work. Thus it is seen that spinlock wastes CPU time.<\/p>\n

     <\/p>\n

    Spinlock is useful in multiprocessor systems. The advantage of spinlock is that no context switch is required when a process must wait on a lock. This is useful when locks are for short times.<\/p>\n

     <\/p>\n

    To overcome this busy waiting, the definitions of the wait and signal operations of the semaphore are modified. The semaphore is implemented as a structure or a record, rather than as just a variable. The structure has two members, an integer value and a list of processes associated with the semaphore.<\/p>\n

     <\/p>\n

    The semaphore is defined as follows:<\/p>\n

    typedef struct {<\/p>\n

    int value;<\/p>\n

    struct process *L;<\/p>\n

    } semaphore;<\/p>\n

     <\/p>\n

    Two operations are defined on processes associated with the semaphore, the block and the wakeup operations. The block operation suspends the process that invokes it. The wakeup(P) operation resumes the execution of a blocked process P.<\/p>\n

     <\/p>\n

    The wait and signal operations on a semaphore are now defined as<\/p>\n

     <\/p>\n

    wait<\/em><\/strong>(S):<\/strong><\/p>\n

    S.value–;<\/p>\n

    if (S.value < 0)<\/p>\n

    {<\/p>\n

    add this process to S.L;<\/p>\n

    block;<\/p>\n

    }<\/p>\n

     <\/p>\n

    Here S is the semaphore structure. It has an integer value (S.value) and a list of processes (S.L) associated with it. In the wait operation, the value of the semaphore is first decremented (S.value–;). Then the value of the semaphore is checked. If the value of the semaphore is less than zero, it means that the resource is not available. Therefore, the process that is executing wait is added to the list associated with the semaphore and is blocked (i.e., put to the waiting state). Compared to the earlier implementation of the wait operation, here the process does not keep on checking the value of the semaphore. Once the resource becomes available, this process is moved out of the waiting state and the process accesses the shared\u00a0resource.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    signal(S<\/em><\/strong>):<\/strong><\/p>\n

    S.value++;<\/p>\n

    if (S.value <= 0)<\/p>\n

    {<\/p>\n

    remove a process P from S.L;<\/p>\n

    wakeup(P);<\/p>\n

    }<\/p>\n

     <\/p>\n

    In the signal operation, the value of the semaphore is incremented. This means that one more process can access the resource. Then the value of the semaphore is checked. If the value of the semaphore is less than or equal to zero, one of the waiting processes is woken up. The process that is woken up is moved to the ready state and can access the resource.<\/p>\n

     <\/p>\n

    The value of the semaphore is less than or equal to zero only if there are other processes waiting in the list associated with this semaphore. (The value had become less than zero when other processes had decremented the value of the semaphore earlier while executing wait).<\/p>\n

     <\/p>\n

    14.3\u00a0 Semaphore as a General Synchronization Tool\u00a0<\/strong><\/p>\n

     <\/p>\n

    In this section, we see how the semaphore can be used as a synchronization tool. There are two processes P<\/em>i and P<\/em>j that want to access a common resource. Let flag <\/em>be the semaphore that guards the shared resource. The shared resource can be used by only one process at a time. Therefore, the value of the semaphore flag <\/em>is initialized to 1.<\/p>\n

     <\/p>\n

    P<\/em><\/strong>i\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>Semaphore\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 P<\/em><\/strong>j<\/strong><\/p>\n

    flag = 1<\/span><\/p>\n

    wait(flag)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<\/span><\/p>\n

    access resource\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0\u00a0flag = 0<\/span><\/p>\n

     <\/p>\n

    signal(flag)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0<\/span><\/p>\n<\/div>\n

    \n

    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0flag = -1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0wait(flag)<\/span><\/p>\n

    flag = 0<\/p>\n

    access resource\u00a0signal(flag)<\/p>\n

    flag = 1<\/p>\n<\/div>\n

    \n

     <\/p>\n

    Process P<\/em>i executes the wait operation on the semaphore. The wait operation decrements the value of the semaphore flag<\/em>. flag <\/em>becomes zero. Since the value of flag <\/em>is not less than zero, P<\/em>i can access the resource. In the meantime, if P<\/em>j wants to access the resource, P<\/em>j executes the wait operation on the semaphore flag<\/em>. flag <\/em>is decremented and becomes -1. Since the value of flag <\/em>is < 0, P<\/em>j is added to the list associated with the semaphore and is put to the waiting state.<\/p>\n

     <\/p>\n

    When process P<\/em>i completes the usage of the resource, it executes the signal operation on flag<\/em>. The value of flag <\/em>is incremented and becomes 0. Process P<\/em>j is woken up from the sleeping state. Process P<\/em>j now can access the resource. After P<\/em>j completes using the resource,\u00a0P<\/em>j executes the signal operation and the value of <\/span>flag <\/em>is incremented back to 1.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    In this way, a semaphore can be used for safeguarding resources.<\/p>\n

     <\/p>\n

    14.4\u00a0 Deadlock and Starvation\u00a0<\/strong><\/p>\n

     <\/p>\n

    When semaphores are used for synchronization, it is possible to have deadlocks and starvation. Deadlock is a situation where two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes. For example, when two or more processes are waiting for the release of some resource that is held by another waiting process, it is a deadlock. Every process in a set of processes will be waiting for an event caused by one of the processes in the set. Starvation means indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended and it starves.<\/p>\n

     <\/p>\n

    Let us now see how deadlocks and starvation can happen with semaphores. Let S <\/em>and Q <\/em>be two semaphores initialized to 1. That is, semaphore S <\/em>is safeguarding a resource that can be accessed by only one process at a time. Similarly, semaphore Q <\/em>is also safeguarding another resource that can be accessed by only one process at a time.<\/p>\n

    P<\/em>0<\/sub>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 P<\/em>1<\/sub><\/p>\n

    wait<\/em>(S<\/em>);\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 wait<\/em>(Q<\/em>);<\/p>\n

    wait<\/em>(Q<\/em>);\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 wait<\/em>(S<\/em>);<\/p>\n

    \u00a0 \u00a0 :\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 :<\/p>\n

    signal<\/em>(S<\/em>);\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 signal<\/em>(Q<\/em>);<\/p>\n

    signal<\/em>(Q<\/em>)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 signal<\/em>(S<\/em>);<\/p>\n

     <\/p>\n

    Consider two processes P<\/em>0 and P<\/em>1. P<\/em>0 executes wait(S) and at the same time, P<\/em>1 executes wait(Q). The values of the semaphores S and Q become 0. P<\/em>0 then executes wait(Q) and waits till semaphore Q is signaled. P<\/em>1 then executes wait(S) and waits till the semaphore S is signaled. Here, we see that process P<\/em>0 is waiting for a resource held by P<\/em>1 and process P<\/em>1 is held by a resource held by P<\/em>0. Each of the two processes is waiting for a resource held by the other process. Therefore, both are unable to proceed. Both the processes wait indefinitely. Both the processes are caught in a deadlock and are starving.<\/p>\n

     <\/p>\n

    Therefore, the order in which wait and signal are used in processes should be selected carefully. Else, it may result in deadlocks and starvation also.<\/p>\n

     <\/p>\n

    Starvation is indefinite blocking. Starvation can also happen when processes that are added to the semaphore queue are removed in a last in first out manner. That is, whenever processes wait for a resource guarded by a semaphore, the processes are added to the queue associated with the semaphore. When more processes wait for the same resource, all these processes are also added to the end of the semaphore\u2019s queue. While removing processes from the queue, if the processes are removed from the end, the processes that were added first will starve.<\/p>\n

     <\/p>\n

    14.5\u00a0 \u00a0Types of Semaphores\u00a0<\/strong><\/p>\n

     <\/p>\n

    There are two types of semaphores\u2014counting semaphores and binary semaphores. A counting semaphore takes an integer value that can range over an unrestricted domain. The semaphores that we discussed in the previous sections are counting semaphores. They are called counting semaphores because the value of the semaphores can be any integer value. A binary semaphore takes an integer value that can range only between 0 and 1. Hence, a binary\u00a0semaphore can be simpler to implement than counting semaphores. If we have the implementation of binary semaphores, we can implement\u00a0 counting semaphores using the implementation of binary semaphores.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    We now see how a counting semaphore S <\/em>can be implemented using binary semaphores. S1 and S2 are the binary semaphores using which the counting semaphore S is implemented. C is an ordinary variable and the initial value of C is set to the initial value of the counting\u00a0semaphore S. The initial value of the counting semaphore S indicates the number of processes that can access the resource guarded by the semaphore S at the same time.<\/p>\n

     <\/p>\n

    Data structures:<\/strong><\/p>\n

    binary-semaphore S1, S2;<\/p>\n

    int C;<\/p>\n

     <\/p>\n

    S1 and S2 are two binary semaphores and C is an integer variable.<\/p>\n

     <\/p>\n

    Initialization:<\/span><\/strong><\/p>\n<\/div>\n

    S1 = 1<\/span><\/div>\n
    S2 = 0<\/span><\/div>\n
    C = initial value of semaphore S<\/span><\/div>\n

    C is assigned the initial value of the counting semaphore S. The initial values of S1 and S2 are assigned 1 and 0 respectively.<\/span><\/p>\n

    \n

     <\/p>\n

    Wait and signal operations for binary semaphore:\u00a0<\/strong><\/p>\n<\/div>\n

    \n

     <\/p>\n

    If S1 is a binary semaphore, then the wait operation on the binary semaphore is given\u00a0below:<\/p>\n

     <\/p>\n

    wait(S1)<\/p>\n

    {<\/p>\n<\/div>\n

    while(S1==0)<\/span><\/p>\n

    ; S1–;<\/span><\/p>\n

    \n

    }<\/p>\n

     <\/p>\n

    If the value of the binary semaphore is zero, the process that executes the wait operation, waits in the while loop. If the value is not equal to zero, the process comes out of the while loop and decrements the value of the semaphore.<\/p>\n

     <\/p>\n

    signal(S1)<\/p>\n

    {<\/p>\n

    S1++;<\/p>\n

    }<\/p>\n

     <\/p>\n

    In the signal operation, the value of the binary semaphore is incremented.<\/p>\n

     <\/p>\n

    The wait and signal operations of the counting semaphore are given below:<\/p>\n

     <\/p>\n

    wait <\/em><\/strong>operation<\/strong><\/p>\n

    The wait operation on the counting semaphore can be implemented using wait and signal operations on the binary semaphore as given below:<\/p>\n

     <\/p>\n

    wait(S1);<\/p>\n

    C–;<\/p>\n

    if (C < 0) {<\/p>\n

    signal(S1);<\/span><\/p>\n

    wait(S2);<\/span><\/p>\n

    }<\/span><\/p>\n

    signal(S1);\u00a0<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    The initial value of S1 is 1. Therefore, the wait operation on S1, finds that the value of S1 is not zero and decrements the value of S1. Next, the value of C is decremented. The initial value of C is equal to the value of the counting semaphore S. If the value of C becomes less than zero, then the process executing wait cannot proceed to execute its critical section. It has to wait. Therefore, the process signals S1 semaphore; the value of S1 becomes 1. Then, it waits on semaphore S2. Since the initial value of S2 is 0, the process waits on S2. If the value of C is not less than 0, it means that the process can enter its critical section. In this case, the process signals S1 and proceeds to enter its critical section. Here, we can see that the semaphore S1 guards the decrement of the variable C. The process waits on S1 before decrementing C and signals S1 after decrementing C. Semaphore S2 guards the shared resource.<\/p>\n

     <\/p>\n

    signal <\/em><\/strong>operation<\/strong><\/p>\n

     <\/p>\n

    The signal operation on S is also implemented using wait and signal operations on S1 and S2. The implementation of signal(S) is given below:<\/p>\n

     <\/p>\n

    wait(S1);<\/p>\n

    C ++;<\/p>\n

    if (C <= 0)<\/p>\n

    signal(S2);<\/p>\n

    else<\/span><\/p>\n

    signal(S1);<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    The executing process first waits on S1. If no other process is currently incrementing or decrementing C, the value of S1 will be 1. wait(S1) decrements the value of S1 to 0. Then, C is incremented. If the value of C becomes less than or equal to zero, then it means that there is(are) other process(es) waiting to use the shared resource. In that case, signal(S2) is executed. As mentioned earlier, S2 is the semaphore that guards the shared resource. When signal(S2) is executed, another process waiting on S2 will come out of waiting, signal S1 (this is the signal(S1) in the wait operation) and proceed\u00a0 to use the shared\u00a0 resource. If C > 0, signal(S1) (in the signal operation) is executed.<\/p>\n

     <\/p>\n

    Let us see with an example, how a counting semaphore is implemented using binary semaphores. Let C = 2 (initial value of semaphore S). Since the value of semaphore S is 2, two processes can use the shared resource at the same time. Let us see what happens when three processes want to use the shared resource at the same time.<\/p>\n

     <\/p>\n

    When wait(S) is executed by the first process, say P<\/em>0<\/sub><\/p>\n

     <\/p>\n

    wait(S) by P<\/em>0<\/sub>:\u00a0<\/strong><\/p>\n

     <\/p>\n

    S<\/strong>1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0C\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 S2<\/strong><\/p>\n

    1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0<\/p>\n

    0<\/p>\n

    1<\/p>\n

    1<\/p>\n<\/div>\n

     <\/p>\n

    Initially, S1 is 0, C is 2 and S2 is 0. wait(S1) decrements the value of S1 to 0. Then C is decremented from 2 to 1. signal(S1) increments the value of S1 back to 1. <\/span>P<\/em>0 gets access to the shared resource.<\/span><\/p>\n

    \n

     <\/p>\n

    In the meantime, suppose process P<\/em>1 \u00a0wants to access the shared resource. The sequence is shown below:<\/p>\n

     <\/p>\n

    wait(S) by P<\/em>1<\/sub>:\u00a0<\/strong><\/p>\n

     <\/p>\n

    S<\/strong>1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0C\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 S2<\/strong><\/p>\n

    1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0<\/p>\n

    0<\/p>\n

    0<\/p>\n

    1<\/p>\n

     <\/p>\n

    wait(S1) decrements the value of S1 from 1 to 0.Then C is decremented from 1 to 0. signal(S1) increments the value of S1 back to 1. P<\/em>1 gets access to the shared resource.<\/p>\n

     <\/p>\n

    In the meantime, suppose the third process P<\/em>2 \u00a0wants to access the shared resource. The sequence is shown below:<\/p>\n

     <\/p>\n

    wait(S) by P<\/em>2<\/sub>:\u00a0<\/strong><\/p>\n

     <\/p>\n

    S<\/strong>1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0C\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 S2<\/strong><\/p>\n

    1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0<\/p>\n

    0<\/p>\n

    -1<\/p>\n

    1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Process P<\/em>2 waits on S2<\/p>\n

     <\/p>\n

    wait(S1) decrements the value of S1 from 1 to 0.Then C is decremented from 0 to -1. Since the value of C goes below 0, process P<\/em>2 executes wait(S2). P<\/em>2 does not get access to the shared resource. Since the initial value of the semaphore S was 2, only two processes are able to access the shared resource. The other processes wait.<\/p>\n

     <\/p>\n

    Let P<\/em>0 complete the usage of the shared resource. P<\/em>0 executes signal(S). The changes in the semaphores\u2019 values are shown below:<\/p>\n

     <\/p>\n

    When signal(S) is executed by P<\/em>0<\/sub>:\u00a0<\/strong><\/p>\n

     <\/p>\n

    S<\/strong>1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 C\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 S2<\/strong><\/p>\n

    1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 -1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0<\/p>\n

    0<\/p>\n

    0<\/span><\/p>\n

    Released process <\/span>P<\/em>2\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 <\/span><\/sub>1<\/span><\/p>\n

    signals S1 1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<\/span>Process <\/span>P<\/em>2 \u00a0waiting on S2 is released<\/span><\/p>\n<\/div>\n

     <\/p>\n

    wait(S1) in the signal operation decrements the value of S1 from 1 to 0.Then C is incremented from \u20131 to 0. Since the value of C becomes 0, signal(S2) is executed. Process P<\/em>2 waiting on S2 is released. Process P<\/em>2 signals S1 (signal(S1) in the wait operation) and gains access to the shared resource.<\/p>\n

     <\/p>\n

    When signal(S) is executed by P<\/em>1<\/sub>:<\/strong><\/p>\n

     <\/p>\n

    S<\/strong>1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0C\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 S2<\/strong><\/p>\n

    1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0<\/p>\n

    0<\/p>\n

    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 1<\/p>\n

    1<\/p>\n

    wait(S1) in the signal operation\u00a0 decrements the value of S1 from 1 to 0.\u00a0 Then C is incremented from 0 to 1. Since the value of C becomes greater than 0, signal(S1) is executed. The value of S1 is changed from 0 to 1. Thus, we see that a counting semaphore can be implemented using binary semaphores.<\/p>\n

     <\/p>\n

    14.6\u00a0 \u00a0Summary<\/strong><\/p>\n

     <\/p>\n

    In this module, we learnt how a semaphore can be used as a synchronization tool. We understood that there are two types of semaphores \u2013 counting and binary semaphores. We also learnt how a counting semaphore is implemented using binary semaphores.<\/p>\n

     <\/p>\n

     <\/p>\n

    References<\/strong><\/p>\n

      \n
    1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, \u201cOperating System Concepts\u201d, Ninth Edition, John Wiley & Sons Inc., 2012.<\/li>\n<\/ol>\n","protected":false},"author":4,"menu_order":11,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-mary-anitha-rajam"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-141","chapter","type-chapter","status-publish","hentry","contributor-dr-mary-anitha-rajam"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/141","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":5,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/141\/revisions"}],"predecessor-version":[{"id":416,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/141\/revisions\/416"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/141\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/media?parent=141"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapter-type?post=141"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/contributor?post=141"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/license?post=141"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}