In my previous post we discussed how Spin Locks can be useful when we need to update multiple global variables atomically. We saw that Spin Locks should be acquired only for a short duration of time as the blocking threads spin in a loop and not doing any thing useful. In this post we will discuss the scenarios where we need to grab a lock for long duration and the ways to solve such problems.
Single Printer and Multiple Users Problem
Lets consider a common example where there is a single printer and multiple threads (thread1, thread2, thread3) that want to print their files (say file1, file2, file3 respectively) As there is only one printer, while one of the threads is printing its file, the others should wait. Also, we are not sure about how much time a single job will take to finish. It may take from few seconds to few hours depending on the size of the file. So, the waiting threads cannot spin in a loop as they will waste lot of cpu cycles. The better option for them is to sleep so that some other thread can run. When the printing job is done the thread at the front of queue should be awakened so that it can start printing its file.
This kind of problem is solved by using a synchronization mechanism called Semaphore.
To implement a semaphore we need a flag to indicate if printer is in use and a queue to keep info about waiting threads.
struct semaphore {
int flag; // flag = 0, means resource BUSY,
// flag = 1, means resource is FREE
queue q; // queue to store pids of all waiting threads
// pid can be later used to issue wakeup to the
// sleeping threads
};
The thread that needs to print the file will first check if the flag is equal to 0 (printer is available). If flag == 0, it will set flag to 1 (to indicate printer is in use) and start printing its file. The test-and-set should be done atomically else two or more threads may feel that they all have acquired the lock. See my previous posts to find out the problems if test-and-set is not done atomically.
If any thread finds that the flag is already set, (printer is busy), it will put itself on the queue and will sleep.
When the printing job is done, flag is again set to 0 to indicate that the printer is free And wakeup is issued to the threads waiting for the printer to become free. No need to issue wakeup to all waiting threads. Wakeup the thread which is waiting for the longest time (ie the thread at the front of queue). The woken-up thread again sets the flag = 1 and starts printing its file.
Semaphores are also called SLEEPING LOCKS as the waiting threads don’t spin but sleep.
Semaphore and related operations.
typedef struct semaphore {
int flag;
queue q;
} semaphore;
semaphore sem; // Create a semaphore for printer
void initSem(semaphore *sem)
{
sem->flag = 0; // Mark resource as free. Printer is available
initialize the queue with all 0s. // No thread is waiting initially
}
void acquireSem(semaphore *sem)
{
while (test_and_set(sem->flag)) { // atomically test-and-set the flag
add itself to the end of queue // if flag is set, add itself to queue
sleep;
}
}
void releaseSem(semaphore *sem)
{
atomic_set(sem->flag, 0); // Mark the resource free. Set flag to 0
if threads are waiting on queue,
issue wakeup to the first thread on queue
}
Note: Care must be taken while adding/removing threads from the queue. As multiple threads may be adding/removing themselves to the queue, a spin lock should be used to prevent queue from corruption. Spin lock will ensure that only a single thread is being added/removed from the queue. In fact, a single spin lock can be used to synchronize access to both flag and queue. The spin lock should be released before going to sleep.
See the example at the end of this post to see how spin lock can be used to implement a semaphore.
This is not the actual implementation but gives you a basic idea on how semaphores work.
The semaphore discussed above can be used to implement a mutex as it allows only a single thread to access the shared resource. These are also called Binary Semaphore.
Multiple Printers and Multiple Users Problem
We saw how a semaphore can be used to synchronize the access to a shared resource. Think of a case where there are multiple resources of same type eg multiple printers. If we have 10 printers then we should allow 10 users to print their files simultaneously.
Solution is Counting Semaphore
This problem is solved by using Counting Semaphores. Here a counter is used to keep track of the threads that are using the shared resources.
struct semaphore {
int count; // initial value of count is equal to the number of shared
// resources.
queue q;
};
Implementing a Counting Semaphore
To implement a Counting Semaphore, the initial value of the count is set to the number of available resources. So, if we have 10 printers initial value of count = 10.
To aquire a semaphore, thread first decrements the value of count by 1. And then tests if count >= 0, which means some printers are available and the thread can start printing his job. So, atmost 10 threads can be printing their files simultaneously.
If the value of count after decrement becomes negative, it means no printer is free and the incoming thread will put itself on the sleep queue. After any printing job is done, count is inceremented by 1 and wakeup is issued to the first thread on the queue.
There are three cases
Case 1: count is > 0. This mean that resource is available. For our 10 printer example, if value of count is 4, it means 4 printers are free.
Case 2: count = 0. No resource available. For our 10 printer case, 0 means no printer is available and no one is waiting on the queue.
Case 3: count < 0. No resource is available. For our 10 printer case, if value of count is -3, it means all printers are busy and 3 threads are waiting in the queue.
So, the value of count may be used to determine if any thread is waiting in the queue. If value of lock < 0, it means some threads are waiting in the queue.
Implementing a Counting Semaphore
typedef struct semaphore {
int count;
queue q
} semaphore;
semaphore sem;
void initSem(semaphore *sem)
{
sem->count = 10; // Initialize the count to 10, to indicate
// 10 resources (printers) are available
initialize the queue with all 0s // No thread is waiting initially
}
void acquireSem(semaphore *sem)
{
decrement sem->count
if (sem->count < 0) {
add itself to the end of queue.
sleep; // Sleep if no resource is available
}
}
void releaseSem(semaphore *sem)
{
increment sem->count
if (sem->count <= 0) {
remove thread from the fron of waiting queue and
issue wakeup to it
}
}
Again, this is not the actual implementation. The count should be modified/checked atomically. Similarly, a thread may be added only if the resource is not available. While acquiring the semaphore, all the operations like decrementing the count, testing its value and then putting the thread on sleep queue should be done atomically. So, a single spin lock should be used to prevent access to both count and queue.
Sempahore using a spin lock to prevent access to its data
typedef struct semaphore {
int spinLock; // spin lock to prevent access to count and queue.
int count;
queue q
}
Spin lock is accessed only for short time, while modifying/testing count value and while adding thread to the queue. The spin lock should be released before going to sleep.
Semaphore operations using a spin lock
void acquireSem(semaphore *sem)
{
acquire spin lock
decrement sem->count
if (sem->count < 0) {
add itself to the end of queue.
release spin lock
sleep; // Sleep if no resource is available
}
}
void releaseSem(semaphore *sem)
{
Acquire spin lock
increment sem->count
if (sem->count <= 0) {
remove thread from the front of waiting queue
release spin lock
issue wake up to removed thread
}
}
Note: Counting semaphores can be used to implement Mutex or Binary Semaphores by initializaing the count to 1.
Hope you find this article useful. If you have any comments/suggestions please post them below.
Have Fun !!!
Excellent illustration with nice examples......
ReplyDeletethank you very much
ReplyDeleteIn last acquireSem and releaseSem, we should release the spinlock in failure case of the 'if' check also.
ReplyDelete