BUFFER *getblk(dev, blk)
{
while(1){
(1). P(free); // get a free buffer first
(2). if (bp in dev_list){
(3). if (bp not BUSY){
remove bp from freelist;
P(bp); // lock bp but does not wait
return bp;
}
// bp in cache but BUSY
V(free); // give up the free buffer
(4). P(bp); // wait in bp queue
return bp;
}
// bp not in cache, try to create a bp=(dev, blk)
(5). bp = frist buffer taken out of freelist;
P(bp); // lock bp, no wait
(6). if (bp dirty){
awrite(bp); // write bp out ASYNC, no wait
continue; // continue from (1)
}
(7). reassign bp to (dev,blk); // mark bp data invalid, not dirty
return bp;
} // end of while(1)
}
brelse(BUFFER *bp)
{
(8). if (bp queue has waiter){ V(bp); return; }
(9). if (bp dirty && free queue has waiter){ awrite(bp); return; }
(10). enter bp into (tail of) freelist; V(bp); V(free);
}
Next, we show that the PV algorithm is correct and meets the requirements.
- Buffer uniqueness: In getblk(), if there are free buffers, the process does not wait at (1). Then it searches the dev_list. If the needed buffer already exits, the process does not create the same buffer again. If the needed buffer does not exist, the process creates the needed buffer by using a free buffer, which is guaranteed to have. If there are no free buffers, it is possible that several processes, all of which need the same buffer, are blocked at (1). When a free buffer is released at (10), it unblocks only one process to create the needed buffer. Once a buffer is created, it will be in the dev_list, which prevents other processes from creating the same buffer again. Therefore, every assigned buffer is unique.
- No retry loops: The only place a process re-executes the while(1) loop is at (6), but that is not a retry because the process is continually executing.
- No unnecessary wakeups: In getblk(), a process may wait for a free buffer at (1) or a needed buffer at (4). In either case, the process is not woken up to run again until it has a buffer. Furthermore, at (9) , when a dirty buffer is to be released as free and there are waiters for free buffers at (1), the buffer is not released but written out directly. This avoids an unnecessary process wakeup.
- Cache effect: In the Unix algorithm, every released buffer is up for grabs. In the new algorithm, a buffer with waiters is always kept for reuse. A buffer is released as free only if it has no waiters. This should improve the buffer’s cache effect.
- No deadlocks and starvation: In getblk(), the semaphore locking order is always unidirectional, i.e. P(free), then P(bp), but never the other way around, so deadlock cannot occur. If there are no free buffers, all requesting processes will be blocked at (1). This implies that while there are processes waiting for free buffer, all buffers in use cannot admit any new users. This guarantees that a BUSY buffer will eventually be released as free. Therefore, starvation for free buffers cannot occur.
Although we have shown that the new algorithm is correct, whether it can perform better than the Unix algorithm remains an open question, which can only be answered by real quantitative data. For this purpose, we have designed a programming project to compare the performances of the buffer management algorithms. The programming project should also help the reader to better understand I/O operations in file systems.
Source: Wang K.C. (2018), Systems Programming in Unix/Linux, Springer; 1st ed. 2018 edition.