第十二章 块设备I/O和缓冲区管理
12.1 块设备I/O缓冲区
I/O缓冲的基本原理非常简单。文件系统使用一系列I/O缓冲区作为块设备的缓存内存。当进程试图读取（dev，blk）标识的磁盘块时。它首先在缓冲区缓存中搜索分配给磁盘块的缓冲区。如果该缓冲区存在并且包含有效数据、那么它只需从缓冲区中读取数据、而无须再次从磁盘中读取数据块。如果该缓冲区不存在，它会为磁盘块分配一个缓冲区，将数据从磁盘读人缓冲区，然后从缓冲区读取数据。当某个块被读入时、该缓冲区将被保存在缓冲区缓存中，以供任意进程对同一个块的下一次读/写请求使用。同样，当进程写入磁盘块时，它首先会获取一个分配给该块的缓冲区。然后，它将数据写入缓冲区，将缓冲区标记为脏，以延迟写入，并将其释放到缓冲区缓存中。由于脏缓冲区包含有效的数据，因此可以使用它来满足对同一块的后续读/写请求，而不会引起实际磁盘I/O。脏缓冲区只有在被重新分配到不同的块时才会写人磁盘。
对于I/O缓冲。将从缓冲区缓存中动态分配缓冲区。假设BUDDER是缓冲区的结构类型（如下），而且getblk（dev,blk）从缓冲去缓冲中分配一个指定（dev,blk）的缓冲区。定义一个bread（dev,blk）函数，它会返回一个包有有效数据的缓冲区（指针）。
BUFFER *bread(dev,blk)
{
BUFFER *bp = getblk(dev,blk); //为磁盘块分配缓冲区
if (bp data valid) //如果该缓冲区包含有效数据
return bp; //则返回该缓冲区
bp->opcode = READ; //否则将数据读入该缓冲区
strat_io(bp);
wait for I/O completion;
return bp;
}
write_block(dev, blk, data) //对磁盘块进行写入
{
BUFFER *bp = bread(dev,blk);
write data to bp;
(synchronous write)? bwrite(bp) : dwrite(bp);
}
bwrite (BUFFER *bp) //同步写入
{
bp->opcode = WRITE;
start_io(bp);
wait for I/O completion;
brelse(bp);
}
dwrite(BUFFER *bp) //延迟写入
{
mark bp dirty for delay_write;
brelse(bp);
}
同步写入等待写操作完成，用于顺序快或者可移动块设备。
延迟写入即上文提到的脏缓冲区，只有脏缓冲区重新分配到不同的磁盘块才会被写入磁盘。
I/O队列，包含等待I/O操作的缓冲区。伪代码：
start_io(BUFFER *bp)
{
enter bp into device I/O queue;
if (bp is first buffer in I/O queue)
issue I/O command for bp to device;
}
12.2 Unix I/O缓冲区管理算法
- I/O缓冲区：内核中的一系列NBUF 缓冲区用作缓冲区缓存。每个缓冲区用一个结构体表示。如下：
typdef struct buf[
struct buf*next__free;// freelist pointer
struct buf *next__dev;// dev_list pointer int dev.,blk;
// assigmed disk block;int opcode;
// READ|wRITE int dirty;
// buffer data modified
int async;
// ASYNC write flag int valid;
//buffer data valid int buay;
// buffer is in use int wanted;
// some process needs this buffer struct semaphore lock=1; /
// buffer locking semaphore; value=1
struct semaphore iodone=0;// for process to wait for I/0 completion;// block data area char buf[BLKSIZE];)
} BUFFER;
BUFFER buf[NBUF],*freelist;// NBUF buffers and free buffer list
- 设备表：每个块设备用一个设备表结构表示。如下：
struct devtab{
u16 dev;
BUFFER *dev_list;
BUFFER *io_queue;
}devtab[NDEV];
- 缓冲区初始化:系统启动时，所有I/O缓冲区都在空闲列表中，所有设备列表和I/O队列均为空。
- 缓冲区列表：缓冲区分配给磁盘时，将被插入设备表的dev_list中。此时若缓冲区正在使用，处于繁忙，则将其从空闲列表删除，而繁忙的缓冲区也可能在设备表的io_queue中。当其不在繁忙时，会将其释放回空闲列表，仍保留在dev_list中。像前文中一样，当其重新分配时才可能从一个dev_list更改到另一个dev_list。
- Unix getblk/brelse算法：
BUFFER *getblk(dev,blk){
while(1){
(1).search dev_list for a bp=(dev,blk); //为标识的磁盘块分配缓冲区
(2).if (bp in dev_list){ //若缓冲区在设备表的dev_list中
if (bp BUSY){ //若该缓冲区处于繁忙状态
set bp WANTED flag;
sleep(bp); //等待该缓冲区释放
continue； //重试该算法
}
take bp out of freelist; //若该缓冲区处于空闲状态，将缓冲区从空闲列表中删除
mark bp BUSY; //将该缓冲区标记为繁忙
reurn bp;
}
(3).
if (freelist empty){ //若没有缓冲区处于空闲状态
set bp WANTED flag;
sleep(freelist); //等待一个空闲状态的缓冲区
continue； //重试该算法
}
/*若存在空闲状态的缓冲区*/
(4).
bp =first bp taken out of freelist; //分配空闲列表最前面的缓冲区
mark bp BUSY; //将其标记为繁忙
if (bp DIRTY){ //若为延迟写入
awrite(bp);
continue;
}
(5).
reassign bp to (dev,blk); //重新分配时，将缓冲区数据写入磁盘
return bp;
}
}
brelse (BUFFER *bp){
if (bp WANTED){
wakeup(bp);
if (freelist WANTED)
wakeup(freelist);
clear bp and freelist WANTED flags;
insert bp to (tail of) freelist;
}
- Unix算法的优点：1.数据的一致性；2.缓存效果；3.临界区；
- Unix算法的缺点： 1.效率低下；2.缓存效果不可预知；3.可能会出现饥饿；4.该算法使用只适用于单处理系统的休眠/唤醒操作。
12.3 新的I/O缓冲区管理算法
- 信号量的主要优点是：
(1)计数信号量可用来表示可用资源的数量，例如：空闲缓冲区的数量。
(2)当多个进程等待一个资源时，信号量上的V操作只会释放一个等待进程，该进程不必重试，因为它保证拥有资源。
使用信号量的缓冲区管理方法
- 当是应用计数信号量上的P/V来设计新的缓冲区管理方法时，具有以下优势：
１．保证数据一致性
２．良好的缓存效果
３．高效率：没有重试循环，，没有不必要的进程唤醒
４．无死锁和饥饿
12.4 P/V算法
- 算法如下：
BUFFER *getblk(dev,blk)
{
while(1){
(1). p(free); //首先获取一个空闲缓冲区
(2). if (bp in dev_list){ //若该缓冲区在设备表的dev_list中
(3). if (bp not BUSY){ //且处于空闲状态
remove from freelist; //将其从空闲列表中删除
P(bp); //lock bp not wait
return bp;
}
//若缓冲区存在缓存内且繁忙
V(free); //放弃空闲缓冲区
(4). P(bp); //在缓冲队列中等待
return bp;
}
//缓冲区不在缓存中，为磁盘创建一个缓冲区
(5). bp = first buffer taken out of freelist;
P(bp); //lock bp no wait
(6). if (bp dirty){ //若为脏缓冲区
awrite(bp); //缓冲区写入磁盘
continue;
}
(7). reassign bp to (dev,blk); //重新分配
return bp;
}
}
brelse (BUFFER *bp)
{
(8).if (bp queue has waiter) {V(bp); return; }
(9).if (bp dirty && freee queue has waiter){ awrite(bp); return;}
(10).enter bp into (tail of) freelist; V(bp); V(free);
}
- 证明PV算法的正确性:
（1）缓冲区唯一性：在 getblk（）中，如果有空闲缓冲区，则进程不会在（1）处等待，而是会搜索 dev list。如果所需的缓冲区已经存在，则进程不会重新创建同一个缓冲区。如果所需的缓冲区不存在。则进程会使用个空闲缓冲区来创建所需的缓冲区。而这个空闲缓冲区保证是存在的。如果没有空闲缓冲区，则需要同一个缓冲区的几个进程可能在（1）处阻塞。
（2）无重试循环：进程重新执行while（1）循环的唯一位置是在（6）处，但这不是重试，因为进程正在不断地执行。
（3）无不必要唤醒：在 getblk（中，进程可以在（1）处等待空闲缓冲区也可以在（4）处等待所需的缓冲区。在任意一种情况下，在有缓冲区之前，都不会唤醒进程重新运行。。
（4）缓存效果：在 Unix算法中，每个释放的缓冲区都可被获取。而在新的算法中，始终保留含等待程序的缓冲区以供重用。只有缓冲区不含等待程序时，才会被释放为空闲。这样可以提高缓冲区的缓存效果。
（5）无死锁和饥饿：在 getblk（）中，信号量锁定顺序始终是单向的，即 P（free），然后是P（bp），但决不会反过来，因此不会发生死锁。
实践内容
1.生产者——消费者
- 代码如下：
include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>
#define N 100
#define true 1
#define producerNum 10
#define consumerNum 5
#define sleepTime 1000
typedef int semaphore;
typedef int item;
item buffer[N] = {0};
int in = 0;
int out = 0;
int proCount = 0;
semaphore mutex = 1, empty = N, full = 0, proCmutex = 1;
void * producer(void * a){
while(true){
while(proCmutex <= 0);
proCmutex--;
proCount++;
printf("produce a product: ID %d, buffer location:%d\n",proCount,in);
proCmutex++;
while(empty <= 0){
printf("buffer is full\n");
}
empty--;
while(mutex <= 0);
mutex--;
buffer[in] = proCount;
in = (in + 1) % N;
mutex++;
full++;
sleep(sleepTime);
}
}
void * consumer(void *b){
while(true){
while(full <= 0){
printf("buffer is empty\n");
}
full--;
while(mutex <= 0);
mutex--;
int nextc = buffer[out];
buffer[out] = 0;//消费完将缓冲区设置为0
out = (out + 1) % N;
mutex++;
empty++;
printf("produce a product: ID %d, buffer location:%d\n", nextc,out);
sleep(sleepTime);
}
}
int main()
{
pthread_t threadPool[producerNum+consumerNum];
int i;
for(i = 0; i < producerNum; i++){
pthread_t temp;
if(pthread_create(&temp, NULL, producer, NULL) == -1){
printf("ERROR, fail to create producer%d\n", i);
exit(1);
}
threadPool[i] = temp;
}//创建生产者进程放入线程池
for(i = 0; i < consumerNum; i++){
pthread_t temp;
if(pthread_create(&temp, NULL, consumer, NULL) == -1){
printf("ERROR, fail to create consumer%d\n", i);
exit(1);
}
threadPool[i+producerNum] = temp;
}//创建消费者进程放入线程池
void * result;
for(i = 0; i < producerNum+consumerNum; i++){
if(pthread_join(threadPool[i], &result) == -1){
printf("fail to recollect\n");
exit(1);
}
}//运行线程池
return 0;
}
- 实践结果：
