Tuesday, 15 December 2015
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:
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 2: Consider 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.
