>

Tuesday, 15 December 2015

Semaphore

Semaphore:
Semaphore is one of the common concurrency mechanisms.
The fundamental principle is this: Two or more processes can cooperate by means of simple signals, such that a process can be forced to stop at a specified place until it has received a specific signal. Any complex coordination requirement can be satisfied by the appropriate structure of signals. For signaling, special variables called semaphores are used.
A semaphore is like an integer, with three differences:
1. When you create the semaphore, its value can be initialized to any integer, but after that the only operations allowed to perform are increment (increase by one) and decrement (decrease by one). The current value of the semaphore cannot be read.
2. When a thread decrements the semaphore, if the result is negative, the thread blocks itself and cannot continue until another thread increments the semaphore.
3. When a thread increments the semaphore, if there are other threads waiting, one of the waiting threads gets unblocked.

Uses: Semaphores are used to solve the below basic synchronization problems,
1. Solves serialization problems : The simplest use for a semaphore is signaling, which means that one thread sends a signal to another thread to indicate that something has appened.Signaling makes it possible to guarantee that a section of code in one thread will run before a section of code in another thread; in other words, it solves the serialization problem.
2. Mutual exclusion: Refers to the requirement of ensuring that no two processes or threads  are in their critical section at the same time.

Implementation:

s = init(1) // s is initialized to 1
wait(s):
    s--
    if s < 0:
        the process goes to sleep
        and is put into the queue waiting for this semaphore

Signal(s):
    if s < 0: // if the queue is not empty
        remove one process from the queue and wake it up
    s++
Code:
 

Example 1: Mutual Exclusion using Semaphore:
The above code shows s solution to the mutual exclusion problem using a semaphore s. Consider n processes, all of which need access to the same resource. Each process has a critical section used to access the resource. In each process, a semWait(s) is executed just before its critical section. If the value of s becomes negative, the process is blocked. If the value is 1, then it is decremented to 0 and the process immediately enters its critical section; because s is no longer positive, no other process will be able to enter its critical section.The semaphore is initialized to 1. Thus, the first process that executes a semWait will be able to enter the critical section immediately, setting the value of s to 0. Any other process attempting to enter the critical section will find it busy and will be blocked, setting the value of s to -1. Any number of processes may attempt entry; each such unsuccessful attempt results in a further decrement of the value of s.When the process that initially entered its critical section departs, s is incremented and one of the blocked processes (if any) is removed from the queue of blocked processes associated with the semaphore and put in a Ready state.When it is next scheduled by the OS, it may enter the critical section.
Example 2Consider a semaphore named sem with initial value 0, and that Threads A and B have shared access to it.

Thread A                                        Thread B
1 statement a1                               1 sem.wait()
2 sem.signal()                                2 statement b1

The word statement represents an arbitrary program statement. To make the example concrete, imagine that a1 reads a line from a file, and b1 displays the line on the screen. The semaphore in this program guarantees that Thread A has completed a1 before Thread B begins b1.Here how it works: if thread B gets to the wait statement first, it will find the initial value, zero, and it will block. Then when Thread A signals, Thread B proceeds. Similarly, if Thread A gets to the signal first then the value of the semaphore will be incremented, and when Thread B gets to the wait, it will proceed immediately. Either way, the order of a1 and b1 is guaranteed.

Example3: :  In below scenario,a2 should happen after b1 and b2 should happen only after a1

Thread A                                        Thread B
1 statement a1                               1 statement b1
2 statement a2                               2 statement b2

Solution: Create 2 semaphores and initialize them to 0
Thread A                                               Thread B
1 statement a1                                 1. statement b1
2 aArrived.signal()                            2. bArrived.signal()
3 bArrived.wait()                               3 aArrived.wait()
4 statement a2                                 4 statement b2


Deadlock situation:
Thread A                                               Thread B
1 statement a1                                   1. statement b1
2 bArrived.wait()                               2 aArrived.wait()
3 aArrived.signal()                            3. bArrived.signal()
4 statement a2                                   4 statement b2

Assuming that A arrives first, it will block at its wait. When B arrives, it will also block, since A wasn’t able to signal aArrived. At this point, neither thread can proceed, and never will. This situation is called a deadlock and, obviously, it is not a successful solution of the synchronization problem.


0 comments:

Post a comment