Last Time I made a brief introduction to Race Conditions and performing healthy resource sharing and few solutions to this problem. Those solutions used Busy Waiting for a task to check a resource availability.
Busy waiting is a right way but still it has its own defects. Maybe the first defect that comes to your mind is that it’s cpu time consuming, the program becomes idle on this phase, but yet It wastes cpu cycles. The second defect is that Busy waiting can actually go wrong, Quoting from Andrew Tannenbaum “Consider Processes H and L. H is a high priority process and L is a low priority process. Those two processes share a critical region with L currently operating in it. Once H is ready L gets interrupted and H is scheduled and tries to enter the critical region But It’s locked so it will continue to busy wait. But L will never get to finish It’s execution now H is running”.
Instead Of Busy waiting another approach came up which blocks a process unable to enter a critical region. It’s called Sleep and Wake-up. Sleep is called by a process when it cant access a critical region which causes it to be suspended. wake up is called by another process once It finishes execution of a critical region to wake up another process waiting for the critical region.
This takes us to a famous problem called Producer Consumer Problem.
Consider we have processes P and C they share a buffer and a count variable which holds the number of entries in the buffer. P’s job is to fill the buffer with specific data and C reads the data and free it from the buffer. P invokes a sleep system call once the buffer is full and waits for C to read the buffer and free at least one slot and wakes the producer up and C invokes a sleep system call once the buffer is empty and waits for P to write to the buffer and wake C up once it wrote at least 1 slot of the buffer. Sounds nice and healthy right?
Unfortunately this is not the truth, It is somehow similar to the Locking Variables Problem. Suppose C reads the count variable and finds it to be 0 which means buffer is empty at this very moment the scheduler starts running P, then P writes entry to the buffer and makes a wake up to C. But C isn’t sleep in the first place! so this wake up is just wasted. then P sleeps and waits for C to start emptying the buffer and C starts to execute, And since it already read the count variable to be 0 it will execute a sleep system call. Now we have two processes P and C asleep forever. Which is… a problem!!
We Shall discuss Semaphores on the next post.