UNIX的缓冲区的管理机制

班级：09092313UNIX能在从微型机直到大型机地各种机器上运行，已成为当今世界最流行的多用户操作系统。UNIX系统在不太长的时间内取得很大成功的根本原因在于UNIX本身的性能和特点。正如图灵奖评选委员会对UNIX的评价中指出：“UNIX系统关于程序设计的新的思想方法成了整整一代软件设计师的楷模。UNIX的天才在于它为程序员提供了一种可以利用别人工作成果的机构。”在Unix系统中，不论是块设备缓冲区管理，还是字符设备缓冲区管理，都采用多缓冲技术，其目的有两个：一是尽力提高CPU和I/O设备的并行工作程度；二是力争提高文件系统信息读写的速度和效率。Unix的块设备共设立了15个512字节的缓冲区；字符设备共设立了100个6字节的缓冲区。每类设备设计了相应的数据结构以及缓冲区自动管理软件。系统设置了多种队列对所有缓冲区进行管理，因为buf记录了与缓冲区有关的各种管理信息，所以缓冲区管理队列实际上是缓存控制块buf队列。图5-9自由buf队列(1)自由buf队列系统把空闲缓冲区的buf组成空闲buf队列，即自由buf队列。这个队列是双向链结构，队首块为bfreelist，bfreelist和自由buf通过av_forw和av_back作为双向指针，见图5-9。1.多种缓冲区管理队列图5-10设备buf队列(2)设备缓冲区队列设备缓冲区队列连接所有各类设备使用过的缓冲区，这也是一个双向队列，buf中的b_forw和b_back分别为该队列的前指针和后指针，头部为hbuf，共64个队列。如图5-10所示。一个缓冲区被分配用于读、写某个设备的字符块时，其相应的buf就进入该设备的设备buf队列，并一直保留在该设备buf队列中，除非被移作它用。系统V与第六版有所不同，不是每个块设备一个缓冲队列，同一个块设备的缓冲区可以分布在不同的散列队列，不同设备的缓冲分布均匀，加快缓冲区的搜索速度。(3)空设备队列（NODEV队列）NODEV队列是一个特殊的设备buf队列。当系统需要缓存，但它不与特定的设备字符块相关联时，将分配到的缓存控制块buf送入NODEV队列。其队列控制块也是bfreelist，用的指针是b_forw和b_back。在UNIX中有两种情况将buf送入NODEV队列。一种是在进程执行一个目标程序的开始阶段，它用缓存存放传向该目标程序的参数；另一种情况是用缓存存放文件系统的资源管理块。在系统初启时，所有空闲缓冲区的buf既在自由buf队列，又在NODEV的设备buf队列中。(4)设备I/O请求队列每个块设备有一个设备I/O请求队列，单向连接，头部为iobuf，b_actf和b_actl分别指向队首和队尾。以上四个队列所属缓冲区之间的关系总结任何一个缓冲区在稳定的状态下，同时属于二个队列。在自由buf队列中缓冲区可能同时属于NODEV队列（未分配给指定设备），也可能属于设备buf队列（已经分配给某设备用过，因I/O结束而释放）。在设备buf队列中的缓冲区，可能挂在自由buf队列（已用过被释放），也可能挂在设备I/O请求队列（正在使用）。在NODEV队列中的缓冲区如已用过被释放，肯定在自由buf队列中。在设备I/O请求队列中的缓冲区则肯定属于设备buf队列。2.缓冲区管理算法1、一个缓存刚分配用于读写某一块设备，buf的b_flags含有B_BUSY标志。它一定位于相应设备buf队列，不在自由队列。2、一旦读写完成，就释放缓存，清B_BUSY标志。送入自由队列尾，但仍留在原设备队列。3、特点和好处：一个缓存既在设备队列，又在自由队列，只要还要重复使用原设备队列中该缓存内容，就只要简单地将其从自由队列抽出即可，避免了重复I/O。有必要可将缓存重新分配它用，将它从自由队列首和原设备队列同时抽出，送入新的设备队列。操作完成后仍留在新的设备队列并送入自由队列。4、为使一个已释放地缓存尽可能长地保持原先内容，以增加重复使用可能，将其送入自由队列尾，分配作它用缓存从自由队列首取（FIFO）。5.当一个buf在自由队列中移动时，只要原设备队列又重新使用它，立即将其从自由队列中间抽取，使用完毕，再次送入自由队列尾（LRU算法）。6．对于写，如一块未写满，在b_flags中设置B_DELWRI标志，推迟写，再清B_BUSY，释放至自由队列尾。7.当设置B_DELWRI标志的缓存排到自由队列首时，不能立即淘汰，它作重新分配处理，而是提出I/O，将其内容复制到块设备后，再次释放到自由队列尾(也有释放到自由队列首），也清B_DELWRI标志。getblk(dev,blkno){while(未找到相应buf){if(盘块在设备buf队列中){if(buf忙){//b_flags&B_BUSYsleep(buf成为空闲);//B_WANTEDcontinue;/*回到while循环*/}标记buf忙；从自由buf队列中移走该buf;return(buf);}else{/*盘块不在设备buf队列中*/if(自由队列中已无buf){//bfreelist&sleep(任一buf成为空闲);//B_WANTEDcontinue;/*回到while循环*/}从自由队列中移走该buf；if(buf标志为“延迟写”){//B_DELWRI异步写buf到相应设备上；continue;/*回到while循环*/}3.缓冲区的分配和释放从原来的设备buf队列中移走该buf；/*找到空闲的buf*/把它放在新的设备buf队列中;return(buf);}}}brelse(bp){唤醒所有等待自由队列成为“非空”的进程；唤醒所有等待本buf成为空闲的进程；提升处理机执行级别，屏蔽中断；if(buf内容有效且不是过时的)把本buf放入自由队列末尾；/*以备将来使用*/else/*如偶尔遇到出错*/把本buf放入自由队列的开头；/*以后很少使用它*/降低处理机执行级别，开放中断；解除封锁(buf);}空闲字符缓冲区队列1、空闲字符缓冲区队列2、设备的字符缓冲区队列在字符设备进行I/O时，内核可利用getcf过程从空闲字符缓冲区队列中取得一个空闲缓冲区，若队列空，表明已无空闲缓冲区可提供，便返回；否则，从队首取得一个空闲缓冲区，并把指向该缓冲区的指针bp返回给调用者。由于空闲缓冲区队列属于临界资源，故还须采取互斥访问措施，在过程开始处，将处理机的优先级提升为6，在取得空缓冲区之后，再恢复处理机的优先级。其中缓冲队列的基本操作有:从空闲缓冲区队列中摘下一个缓冲区分配给驱动程序。将一个缓冲区释放后放入空闲缓冲队列中。从i/o缓冲队列中提取一个字符，并调整该i/o缓冲低劣的字符计数。把一个字符放入i/o缓冲队列中的最后一个缓冲区的尾部。从i/o缓冲队列中每次移走一个缓冲区的所有字符或者n（n1）个字符。往i/o缓冲队列中每次送一个缓冲区的字符或者n（n1）个字符。设备的字符缓冲区队列getc过程该过程用于从一个clist结构的队首指针所指示的字符缓冲队列中，取出为首的字符，然后修改该队列的可用字符计数和队首指针。当取完一个缓冲区中的所有字符时，将释放该缓冲区。该过程的返回值是取出的字符。putc过程该过程用于将一个字符C放入设备的指定字符缓冲区队列的末尾。若此时该队列空、或队列的最后一个缓冲区已满，且空闲字符缓冲区队列也空，该过程无法将字符放入队列中，则返回“-1”。getcb过程该过程用于从指定的设备字符缓冲区队列中，取出第一个缓冲区，并将该队列的可用字符计数减去第一个缓冲区中的字符数，然后返回指向该缓冲区的指针bp。若该缓冲区已是该队列中惟一的缓冲区，则置队尾指针为空。putcb过程该过程用于将由bp所指向的缓冲区放入指定的设备字符缓冲区队列的末尾，然后将该队列的可用字符计数加上bp缓冲区中的字符数后返回。1、盘块缓冲区及其首部空闲队列(链)及散列队列缓冲首部2、盘块缓冲池结构3、盘块缓冲区的分配getblk()过程该过程用于从空闲缓冲区队列中获得任一空闲缓冲区。该过程首先检查空闲块缓冲队列是否为空，若空，便调用sleep过程进入睡眠等待，直至在空闲块缓冲队列中出现空闲缓冲区为止；否则，从空闲块缓冲队列中摘下第一个缓冲区。若在其缓冲首部中还有延迟写标志，则还须调用bdwrite过程，将此缓冲区中的数据写回到磁盘中，再从空闲队列中取得一个空缓冲区；否则，便将b-flag中的b[CD*2]busy标志置为1，并返回指向该缓冲区的指针bp。getblk过程分配缓冲区时，可分为如下两种情况：（1）缓冲区在散列队列上。进入getblk过程后，首先根据文件系统号和盘块号去查找散列队列，若找到与文件系统号和盘块号相匹配的缓冲区，便可进一步检查该缓冲区是否空闲。若空闲，则应先上锁，以防止其他进程对它进行访问，然后把它从空闲缓冲区链上摘下；若忙，则表明缓冲区已被其他进程上锁，因此暂时不能对它进行访问，进程进入睡眠，直至该缓冲区变为空闲时再将进程唤醒。（2）缓冲区不在散列队列上。若在散列队列中找不到与文件系统号及盘块号相匹配的缓冲区，便只有从空闲缓冲区链表中找一个缓冲区。若空闲缓冲区链表已空，则无法进行分配，进程睡眠，直到空闲缓冲区链表中出现缓冲区为止；若空闲缓冲区链表不空，这时可从链首摘下一个缓冲区，若此缓冲区标记有“延迟写”，此时应将该缓冲区内容异步地写到磁盘上，再从空闲缓冲区链表中摘下一个缓冲区，并调整该缓冲区所在的散列队列，即将该缓冲区从原来的空闲缓冲区链表调整到新的散列队列中。因为当该缓存区重新分配后，缓冲区对应的盘块号发生了变化，从而也相应的改变了其所在的散列队列。getblk(dev,blkno)过程该过程用于为指定设备dev和盘块号为blkno的盘块申请一个缓冲区。核心首先检查要读入的盘块内容是否已在某个缓冲区中，若发现已在某缓冲区中，便不再从磁盘上读；否则，核心须从磁盘上将数据读入，这时才需为其分配一个空缓冲区。类似地，当要把数据写入一特定盘块时，核心先检查该盘块的内容是否已在某缓冲区，仅当该块的内容尚不在缓冲区中时，才需调用getblk()过程，分配一个空缓冲区。4、盘块缓冲区的回收当核心用完某缓冲区时，可调用brelse过程将之收回。此前，可能有些进程因等待使用该缓冲区而睡眠，此时，释放者进程应将睡眠队列的队首进程唤醒。此外，还有可能有进程因空闲链表空而处于等待状态，同样也应将之唤醒。如果在所释放的缓冲区中的数据是有效的，为使以后在某进程需要它时，也能直接从缓冲区中读出而不必启动磁盘的I/O操作，可将该缓冲区链入空闲链表的末尾；否则(缓冲区中数据无效)，应将它链入空闲队列的头部。空闲链表属于临界资源，为了保证对它操作的互斥性，UNIX系统通过提高处理机的运行级对中断加以屏蔽的方法来实现。