FOR FREE MATERIALS

Synchronization without Busy Waiting 

Introduction

Problem of Busy Waiting

All the synchronization solutions like Peterson algorithm, Decker’s algorithm, Test and Set Lock instruction, Compare and Swap instruction, etc. are correct, but it has a common problem of busy waiting. The concept is, when a process wants to enter its critical section, it checks to see if the entry code allowed. If it is not satisfied, the process just sits in a tight loop waiting i.e. process check the loop infinite time until the entry code satisfied and the critical section free. This unnecessary infinite check of entry point i.e. busy waiting leads to wastage of CPU time. 

Not only does this approach waste CPU time, but it can also have unexpected effects. 

For example:

Consider there are two processes P0 with high priority and P1with low priority. Let it is priority-based scheduling where if process P0 and P1 is in a ready state at a time, then P0 run first.

At a certain moment, process P1 in its critical section, and P0 becomes a ready state (e.g. an I/O operation completes or completes other interrupts). So, P0 begins busy waiting because the critical section is busy, but P1(low priority) is not scheduled while P0 (high priority) is running.

In that case, P1 never gets the chance to exit from its critical section, and P0 loops forever to check the entry point of the critical section. This concept is called the priority inversion problem.

Solutions of busy waiting problem: Sleep  and Wakeup

To solve busy waiting, here some of the synchronization solutions block the process (who wants to enter into a critical section) where the critical section is busy with other process but not keeps its running state which checks the loop infinite time until it achieves critical section and wastes the CPU time. 

This concept is done by using two simple systems call sleep and wakeup.

# Sleep is a system call to block the process i.e. suspended until another process wakes it up (leave the critical section). 

# The wakeup call is used to awaken the process (when the critical section free).

# Both sleep and wakeup each have one parameter, a memory address used to match up sleep with wakeups.