The mutex and semaphore are kernel resources that provide synchronization services. In concurrency programming when two or more threads try to access a critical section we need a synchronization between them. This is required to avoid race conditions. Critical section and race condition are explained as
Critical section
Critical section is a piece of code that accesses a shared resource (data structure or device) that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to enter it (aka bounded waiting). Some synchronization mechanism is required at the entry and exit of the critical section to ensure exclusive use, for example a semaphore.
Critical section
Critical section is a piece of code that accesses a shared resource (data structure or device) that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to enter it (aka bounded waiting). Some synchronization mechanism is required at the entry and exit of the critical section to ensure exclusive use, for example a semaphore.
Remainder Section : Anything else a process does besides using the critical section.
Race condition
A race condition is any situation in which the combined outcome of two or more threads of execution varies depending on the precise order in which the interleaved instructions of each are executed on the processor. For example, suppose you have two threads of execution in which one regularly increments a global variable (g_counter += 1;) and the other very occasionally zeroes it (g_counter = 0;). There is a race condition here if the increment cannot always be executed atomically (in other words, in a single instruction cycle).
The producer-consumer problem:Note that the content is generalized explanation. Practical details will vary from implementation.
Consider the standard producer-consumer problem. Assume, we have a buffer of 4096 byte length. A producer thread will collect the data and writes it to the buffer. A consumer thread will process the collected data from the buffer. Objective is, both the threads should not run at the same time.
Mutex
Mutex is short for mutual exclusion. Mutual exclusion lock: Block access to variables by other threads. This enforces exclusive access by a thread to a variable or set of variables. mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It means there will be ownership associated with mutex, and only the owner can release the lock (mutex).
Race condition
A race condition is any situation in which the combined outcome of two or more threads of execution varies depending on the precise order in which the interleaved instructions of each are executed on the processor. For example, suppose you have two threads of execution in which one regularly increments a global variable (g_counter += 1;) and the other very occasionally zeroes it (g_counter = 0;). There is a race condition here if the increment cannot always be executed atomically (in other words, in a single instruction cycle).
The producer-consumer problem:Note that the content is generalized explanation. Practical details will vary from implementation.
Consider the standard producer-consumer problem. Assume, we have a buffer of 4096 byte length. A producer thread will collect the data and writes it to the buffer. A consumer thread will process the collected data from the buffer. Objective is, both the threads should not run at the same time.
Mutex
Mutex is short for mutual exclusion. Mutual exclusion lock: Block access to variables by other threads. This enforces exclusive access by a thread to a variable or set of variables. mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It means there will be ownership associated with mutex, and only the owner can release the lock (mutex).
We use the mutex lock to protect critical regions and thus prevent race conditions. That is, a process must acquire the lock before entering a critical section;it releases the lock when it exits the critical section. The acquire()function acquires the lock, and the release() function releases the lock, as illustrated Figure :
A mutex lock has a Boolean Variable available whose value indicates if the lock is available or not. If the lock is available, a call to acquire() succeeds, and the lock is then considered unavailable. A process that attempts to acquire an unavailable lock is blocked until the lock is released.
The definition of acquire() is as follows:
acquire() {
while (!available)
;/* busy wait */
available = false;;
}
The definition of release() is as follows:
release() {
available = true;
}
Example : A mutex provides mutual exclusion, either producer or consumer can have the key (mutex) and proceed with their work. As long as the buffer is filled by producer, the consumer needs to wait, and vice versa.
At any point of time, only one thread can work with the entire buffer. The concept can be generalized using semaphore.
At any point of time, only one thread can work with the entire buffer. The concept can be generalized using semaphore.
Busy waiting is disadvantage of Mutex Lock
The main disadvantage of the implementation given above is that it requires busy waiting. While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the call to acquire().
In fact, this type of mutex lock is also called a spinlock because the process “spins” while waiting for the lock to become available. This continual looping is clearly a problem in a real multiprogramming system, where a single CPU is shared among many processes. Busy waiting wastes CPU cycles that some other process might be able to use productively.
Advantage of Spin Lock: Short Time Lock
Spinlocks do have an advantage, however, in that no context switch is required when a process must wait on a lock, and a context switch may take considerable time. Thus, when locks are expected to be held for short times, spinlocks are useful. They are often employed on multiprocessor systems where one thread can “spin” on one processor while another thread performs its critical section on another processor.
In fact, this type of mutex lock is also called a spinlock because the process “spins” while waiting for the lock to become available. This continual looping is clearly a problem in a real multiprogramming system, where a single CPU is shared among many processes. Busy waiting wastes CPU cycles that some other process might be able to use productively.
Advantage of Spin Lock: Short Time Lock
Spinlocks do have an advantage, however, in that no context switch is required when a process must wait on a lock, and a context switch may take considerable time. Thus, when locks are expected to be held for short times, spinlocks are useful. They are often employed on multiprocessor systems where one thread can “spin” on one processor while another thread performs its critical section on another processor.
Semaphore
Semaphore is signaling mechanism (“I am done, you can carry on” kind of signal). Think of it as an unsigned integer you can increment and decrement, but if you try to decrement it below zero, it doesn't wrap around like normal unsigned integers to, but instead it blocks the thread until another one increments it again. Semaphores usually have a maximum value; incrementing beyond this value has no effect. Decrementing the semaphore is called acquiring or locking it, incrementing is called releasing or unlocking.
Example : A semaphore is a generalized mutex. In lieu of single buffer, we can split the 4 KB buffer into four 1 KB buffers (identical resources). A semaphore can be associated with these four buffers. The consumer and producer can work on different buffers at the same time.
Semaphore is signaling mechanism (“I am done, you can carry on” kind of signal). Think of it as an unsigned integer you can increment and decrement, but if you try to decrement it below zero, it doesn't wrap around like normal unsigned integers to, but instead it blocks the thread until another one increments it again. Semaphores usually have a maximum value; incrementing beyond this value has no effect. Decrementing the semaphore is called acquiring or locking it, incrementing is called releasing or unlocking.
Example : A semaphore is a generalized mutex. In lieu of single buffer, we can split the 4 KB buffer into four 1 KB buffers (identical resources). A semaphore can be associated with these four buffers. The consumer and producer can work on different buffers at the same time.
Library Analogy : Suppose a library has 10 identical study rooms, to be used by one student at a time. To prevent disputes, students must request a room from the front desk if they wish to make use of a study room. If no rooms are free, students wait at the desk until someone relinquishes a room. When a student has finished using a room, the student must return to the desk and indicate that one room has become free.
In the simplest implementation, the clerk at the front desk does not need to keep track of which rooms are occupied or who is using them, nor does she know if any given room is actually being used, only the number of free rooms available, which she only knows correctly if all of the students actually use their room while they've signed up for them and return them when they're done. When a student requests a room, the clerk decreases this number. When a student releases a room, the clerk increases this number. Once access to a room is granted, the room can be used for as long as desired, and so it is not possible to book rooms ahead of time.
In this scenario the front desk count-holder represents a counting semaphore, the rooms are the resources, and the students represent processes. The value of the semaphore in this scenario is initially 10. When a student requests a room she is granted access and the value of the semaphore is changed to 9. After the next student comes, it drops to 8, then 7 and so on. If someone requests a room and the resulting value of the semaphore would be negative,[3] they are forced to wait until a room is freed (when the count is increased from 0).
In the simplest implementation, the clerk at the front desk does not need to keep track of which rooms are occupied or who is using them, nor does she know if any given room is actually being used, only the number of free rooms available, which she only knows correctly if all of the students actually use their room while they've signed up for them and return them when they're done. When a student requests a room, the clerk decreases this number. When a student releases a room, the clerk increases this number. Once access to a room is granted, the room can be used for as long as desired, and so it is not possible to book rooms ahead of time.
In this scenario the front desk count-holder represents a counting semaphore, the rooms are the resources, and the students represent processes. The value of the semaphore in this scenario is initially 10. When a student requests a room she is granted access and the value of the semaphore is changed to 9. After the next student comes, it drops to 8, then 7 and so on. If someone requests a room and the resulting value of the semaphore would be negative,[3] they are forced to wait until a room is freed (when the count is increased from 0).
Mutex vs Semaphore :
A mutex is essentially the same thing as a binary semaphore and sometimes uses the same basic implementation. The differences between them are in how they are used. While a binary semaphore may be used as a mutex, a mutex is a more specific use-case, which allows extra guarantees:
- Mutexes have a concept of an owner. Only the process that locked the mutex is supposed to unlock it. If the owner is stored by the mutex this can be verified at runtime.
- Mutexes may provide priority inversion safety. If the mutex knows its current owner, it is possible to promote the priority of the owner whenever a higher-priority task starts waiting on the mutex.
- Mutexes may also provide deletion safety, where the process holding the mutex cannot be accidentally deleted.
Misconception
Couple of article says that "binary semaphore and mutex are same" or "Semaphore with value 1 is mutex" but they are not! The purpose of mutex and semaphore are different. May be, due to similarity in their implementation a mutex would be referred as binary semaphore.
Strictly speaking, a mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It means there will be ownership associated with mutex, and only the owner can release the lock (mutex).In other way Mutex can be released only by thread that had acquired it.
Semaphore is signaling mechanism (“I am done, you can carry on” kind of signal). For example, if you are listening songs (assume it as one task) on your mobile and at the same time your friend called you, an interrupt will be triggered upon which an interrupt service routine (ISR) will signal the call processing task to wakeup that means you can signal semaphore from any other thread.
Couple of article says that "binary semaphore and mutex are same" or "Semaphore with value 1 is mutex" but they are not! The purpose of mutex and semaphore are different. May be, due to similarity in their implementation a mutex would be referred as binary semaphore.
Strictly speaking, a mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It means there will be ownership associated with mutex, and only the owner can release the lock (mutex).In other way Mutex can be released only by thread that had acquired it.
Semaphore is signaling mechanism (“I am done, you can carry on” kind of signal). For example, if you are listening songs (assume it as one task) on your mobile and at the same time your friend called you, an interrupt will be triggered upon which an interrupt service routine (ISR) will signal the call processing task to wakeup that means you can signal semaphore from any other thread.
No comments:
Post a Comment