In this section, we shall show a new algorithm for I/O buffer management. Instead of using sleep/ wakeup, we shall use P/V on semaphores for process synchronization. The main advantages of semaphores over sleep/wakeup are
- Counting semaphores can be used to represent the number of available resources, e.g. the number of free buffers.
- When many processes wait for a resource, the V operation on a semaphore unblocks only one waiting process, which does not have to retry since it is guaranteed to have the resource.
These semaphore properties can be used to design more efficient algorithms for buffer management. Formally, we specify the problem as follows.
Buffer Management Algorithm using Semaphores
Assume a uniprocessor kernel (one process runs at a time). Use P/V on counting semaphores to design new buffer management algorithms which meet the following requirements:
- Guarantee data consistency.
- Good cache effect.
- High efficiency: No retry loops and no unnecessary process “wakeups”.
- Free of deadlocks and starvation.
It is noted that merely replacing sleep/wakeup in the Unix algorithm by P/V on semaphores is not an acceptable solution because doing so would retain all the retry loops. We must redesign the algorithm to meet all the above requirements and justify that the new algorithm is indeed better than the Unix algorithm. First, we define the following semaphores.
BUFFER buf[NBUF]; // NBUF I/O buffers
SEMAPHORE free = NBUF; // counting semaphore for FREE buffers
SEMAPHORE buf[i].sem = 1; // each buffer has a lock sem=1;
To simplify the notations, we shall refer to the semaphore of each buffer by the buffer itself. As in the Unix algorithm, initially all buffers are in the freelist and all device lists and I/O queues are empty. The following shows a simple buffer management algorithm using semaphores.
Source: Wang K.C. (2018), Systems Programming in Unix/Linux, Springer; 1st ed. 2018 edition.