引言摘要
普通文件的读写算法依赖于两个关键操作——put_block和get_block，这两个操作将磁盘块读写到内存缓冲区中。由于与内存访问相比，磁盘I/O速度较慢，所以不希望在每次执行读写文件操作时都执行磁盘I/O。因此大多数文件系统使用I/O缓冲来减少进出存储设备的物理I/O数量，合理设计的I/O缓冲方案可显著提高文件I/O效率并增加系统吞吐量。
K块设备I/O缓冲区
I/O缓冲的基本原理非常简单。文件系统使用一系列I/O缓冲区作为块设备的缓存内存。当进程试图读取（dev，blk）标识的磁盘块时。它首先在缓冲区缓存中搜索分配给磁盘块的缓冲区。如果该缓冲区存在并且包含有效数据、那么它只需从缓冲区中读取数据、而无须再次从磁盘中读取数据块。如果该缓冲区不存在，它会为磁盘块分配一个缓冲区，将数据从磁盘读人缓冲区，然后从缓冲区读取数据。当某个块被读入时、该缓冲区将被保存在缓冲区缓存中，以供任意进程对同一个块的下一次读/写请求使用。同样，当进程写入磁盘块时，它首先会获取一个分配给该块的缓冲区。然后，它将数据写入缓冲区，将缓冲区标记为脏，以延迟写入，并将其释放到缓冲区缓存中。由于脏缓冲区包含有效的数据，因此可以使用它来满足对同一块的后续读/写请求，而不会引起实际磁盘I/O。脏缓冲区只有在被重新分配到不同的块时才会写人磁盘。
在read_file/write_file中，我们假设它们从内存中的一个专用缓冲区进行读/写。对于I/O缓冲，将从缓冲区动态分配缓冲区。
同步写入操作等待写操作完成。它用于顺序块或可移动块设备，如USB驱动器。对于随机访问设备，例如硬盘，所有的写操作都是延迟写操作。在延迟写操作中，dwrite(bp)将缓冲区标记为脏，并将其释放到缓冲区缓存中。由于脏缓冲区包含有效数据，因此可以用来满足对同一块的后续读/写请求。这不仅减少了物理磁盘I/O数量，而且提高了缓冲区缓存的效果。
Unix I/O缓冲区管理算法
（1）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
缓冲区结构体由两部分组成：用于缓冲区管理的缓冲头部分和用于数据块的数据部分。为了保护内核内存，状态字段可以定义为一个位向量，其中每个位表示一个唯一的状态条件。这里为了方便将它们定义为int类型。
（2）设备表：
每个块设备用一个设备表结构表示。
struct devtab{
u16 dev;// major device number
BUFFER *dev_list; // device buffer list
BUFFER*io_queue;// device I/0 queue
}devtab[NDEV];
每个设备都有一个dev_list，包含当前分配给该设备的I/O缓冲区，还有一个io_queue，包含设备上等待I/O操作的缓冲区。I/O队列的组织方式应确保最佳I/O操作。为了简单起见，Unix使用了FIFO队列(先进先出，队列）。
（3）缓冲区初始化：当系统启动时，所有I/O缓冲区都在空闲列表中，所有设备列表和I/O队列均为空。
（4）缓冲区列表：当缓冲区分配给（dev，blk）时，它会被插入设备表的 dev_list中。如果缓冲区当前正在使用，则会将其标记为 BUSY（繁忙）并从空闲列表中删除。繁忙缓冲区也可能会在设备表的I/O队列中。
Unix算法优点：
（1）数据一致性：为了确保数据一致性，getblk一定不能给同一个（dev,blk)分配多个缓冲区。这可以通过让进程从休眠状态唤醒后再次执行“重新循环”来实现。分配的每个缓冲区都是唯一的。
（2）缓冲效果：释放的缓冲区保留在设备列表中，以便可能重用。标记为延迟写入的缓冲区不会立即产生I/O，并且可以重用。
（3）临界区：设备中断处理程序可操作缓冲区列表，例如从设备表的I/O队列中删除bp,更改其状态并调用brelse(bp)。
Unix算法缺点：
（1）效率低下；同时唤醒多组进程，但最后只有一组进程可以获取释放的缓冲区，其他所有被唤醒的进程必须重新进入休眠状态。
（2）缓存效果不可预知；每个释放的缓冲区都有可能被获取。如果缓冲区由需要空闲缓冲区的进程获取，那么将会重新分配缓冲区，即使有些进程仍然需要当前的缓冲区。
（3）可能会出现进程饥饿；
（4）该算法使用只适用于单处理系统的休眠/唤醒操作。
使用信号量的缓冲区管理算法
信号量的主要优点：
（1）计数信号量可用来表示可用资源的数量，例如∶空闲缓冲区的数量。
（2）当多个进程等待一个资源时，信号量上的V操作只会释放一个等待进程，该进程不必重试，因为它保证拥有资源。
这些信号量属性可用于设计更有效的缓冲区管理算法。
使用信号量的缓冲区管理算法：
假设有一个单处理器内核（一次运行一个进程）。使用计数信号量上的P/V来设计满足以下要求的新的缓冲区管理算法∶
（1）保证数据一致性。
（2）良好的缓存效果。
（3）高效率∶没有重试循环，没有不必要的进程"唤醒"。
（4）无死锁和饥饿。
PV算法
BUFFER *getb1k(dev,blk)：
while(1){
(1). P(free);
//get a free buffer first
if (bp in dev_1ist){
(2). if (bp not BUSY){
remove bp from freelist;P(bp);
// lock bp but does not wait
(3).return bp;
// bp in cache but BUSY V(free);
// give up the free buffer
(4).P(bp);
// wait in bp queue
return bp;v
// 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){
awzite(bp);
// write bp out ASYNC,no wait
continue;
// continue from (1)
(7).reassign bp to(dev,blk);1/ mark bp data invalid,not dir 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);zeturn;}(10).enter bp into(tail of) freelist;V(bp);V(free);
}
编程实践
C语言编程实现PV操作
(1)pv操作伪代码：
array[3]:interger;//缓冲区定义,大小为三
int empty=3,full=0;
int mutex=1;
i=0,j=0;//缓冲区指针
x，y：item; //产品变量
生产者，消费者：
begin：
produce a product to x;
P(empty);
P(mutex);
array[i]=x;
ii=(i+1)%3;
V(full);
V(mutex);
....
End
(2)编程实现
代码如下：
#include<string.h>
#include <sys/time.h>
#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
#include<stdlib.h>
#include<sys/sem.h>
#include<sys/select.h>
#include<sys/wait.h>
#include<sys/ipc.h>
#include<sys/shm.h>
#include<time.h>
#define SEM_ID1 225
#define SEM_ID2 97
#define SEM_ID3 234
#define SHMKEY 75
struct buf{
char buffer[3];
int read;
int write;
};
int rand_1()
{
return rand()%300;
}
void sleep_ms(int s)
{
usleep(s*10000);
}
char* cur_time()
{
time_t timep;
time(&timep);
return ctime(&timep);
}
char rand_char()
{
return rand()%26+'A';
}
void P (int s)//p操作
{
struct sembuf sem_op;
sem_op.sem_num=0;
sem_op.sem_op=-1;
sem_op.sem_flg=0;
semop(s,&sem_op,1);
}
void V(int s)//v操作
{
struct sembuf sem_op;
sem_op.sem_num=0;
sem_op.sem_op=1;
sem_op.sem_flg=0;
semop(s,&sem_op,1);
}
void pro()//生产者
{
int tim,shmid,i=6;
int sem_mutex,sem_empty,sem_full;
void * addr;
struct buf *pint;
struct sembuf sem_op;
struct timeval tv;
sem_mutex=semget(SEM_ID1,1,0600);
sem_empty=semget(SEM_ID2,1,0600);
sem_full=semget(SEM_ID3,1,0600);
shmid=shmget(SHMKEY,sizeof(struct buf),0777);
addr=shmat(shmid,0,0);
while(i--)
{
gettimeofday(&tv,NULL);
srand((unsigned)tv.tv_usec);
tim=rand_1();
sleep_ms(tim);
//P(empty)
P(sem_empty);
//P(mutex)
P(sem_mutex);
pint=(struct buf *)addr;
// pint[semctl(sem_full,0,GETVAL)]=time;
pint->buffer[pint->write]=rand_char();
pint->write=(pint->write+1)%3;
printf("当前生产者进程:%d 写入数据:\t%c\t%c\t%c\t@%lds%ldus\n",
getpid(),pint->buffer[0],pint->buffer[1],
pint->buffer[2],tv.tv_sec,tv.tv_usec);
//V(mutex)
V(sem_mutex);
//V(full)
V(sem_full);
}
shmdt(addr);
}
void con()//消费者
{
int tim,shmid,i=4;
int sem_mutex,sem_empty,sem_full;
void * addr;
struct buf *pint;
struct sembuf sem_op;
struct timeval tv;
sem_mutex=semget(SEM_ID1,1,0600);
sem_empty=semget(SEM_ID2,1,0600);
sem_full=semget(SEM_ID3,1,0600);
shmid=shmget(SHMKEY,sizeof(struct buf),0777);
addr=shmat(shmid,0,0);
while(i--)
{
gettimeofday(&tv,NULL);
srand((unsigned)tv.tv_usec);
tim=rand_1();
sleep_ms(tim);
//P(full)
P(sem_full);
//P(mutex)
P(sem_mutex);
pint=(struct buf *)addr;
pint->buffer[pint->read]=' ';
pint->read=(pint->read+1)%3;
printf("当前消费者进程:%d 读取数据:\t%c\t%c\t%c\t@%ldst%ldms\n",
getpid(),pint->buffer[0],pint->buffer[1],
pint->buffer[2],tv.tv_sec,tv.tv_usec);
//V(mutex)
V(sem_mutex);
//V(empty)
V(sem_empty);
}
shmdt(addr);
}
int main()
{
int sem_mutex,sem_empty,sem_full,shmid;
void * addr;
union semun {
int val;
}empty,full,mutex;
//建立信号量
sem_mutex=semget(SEM_ID1,1,IPC_CREAT|0600);
sem_empty=semget(SEM_ID2,1,IPC_CREAT|0600);
sem_full=semget(SEM_ID3,1,IPC_CREAT|0600);
full.val=0;
empty.val=3;
mutex.val=1;
semctl(sem_mutex,0,SETVAL,mutex);
semctl(sem_empty,0,SETVAL,empty);
semctl(sem_full,0,SETVAL,full);
//建立共享内存并进行映射
shmid=shmget(SHMKEY,sizeof(struct buf),0777|IPC_CREAT);
if(-1==shmid)
{
printf("建立共享内存失败\n");
exit(0);
}
addr=shmat(shmid,0,0);
memset(addr,0,sizeof(struct buf));
//执行生产者进程
for(int i=0;i<2;i++)
if(fork()==0)
{
pro();
exit(0);
}
//执行消费者进程
for(int i=0;i<3;i++)
if(fork()==0)
{
con();
exit(0);
}
while(-1 != wait(0));
semctl(sem_mutex,0,IPC_RMID);
semctl(sem_empty,0,IPC_RMID);
semctl(sem_full,0,IPC_RMID);
shmdt(addr);
}
运行结果如下：
标签：12,struct,int,bp,缓冲区,mutex,sem,设备 From： https://www.cnblogs.com/ssssspm/p/16849063.html