数据缓冲区管理

1、数据缓冲区管理讲授者：李川C O i 的缓冲区可定义为：n B i = x:d ( x, O i ) 最简单的情况2. b 不在相应的 hash 表中，而且空闲表不为空= 由空闲表中获得一个空闲缓冲区，然后将块 b 由磁盘读入其中3. b 不在相应的 hash 表中，而且空闲表为空= 首先获得一个缓冲区，然后将该块读入其中，若没有空闲块，则睡眠等待4. b 在相应的 hash 表中，而且该缓冲区是上锁的 (即该缓冲区不在空闲表中)= 睡眠等待缓冲区变为空闲主要的四种情形被请求访问的块 b 在相应的 hash 表中么?该缓冲区是上锁的还是开锁的？ (在不在空闲表中)?空闲表是空的么？在不在开锁上

2、锁14空的不空32情形 1q最简单的情形qb 在相应的 hash 表上q并且缓冲区是开锁的 (该块在空闲表中)= 内核将该缓冲区由空闲表取出，并对其加锁然后进行存取，使用完毕后，将该缓冲区放置到空闲表的尾部，并对其解锁块在散列表中而且该块是空闲块块在散列表中而且该块是空闲块情形 2qb 不在相应的 hash 表中 (该块必须有磁盘中读入到一个新的缓冲区中)q而且空闲表不为空= 内核由空闲表的表头取出一个缓冲区，准备把块b由磁盘读入该缓冲区中= 这时，可能有两种不同的情况，分别记为情形 2a和情形 2b.情形 2aq有空闲表头取得的缓冲区不包含有效数据 (即该缓冲区不同时在一个 hash 表的链

3、中)q或者该缓冲区包含有效数据，但该缓冲区被标记为不是“脏”的 (因此，该缓冲区中的数据无需写入磁盘)= 将该缓冲区放置于 hash 表中合适的链上，等候有磁盘中读取块 b 至该缓冲区中= 启动一个异步磁盘操作加载块 b= 发出块访问请求的进程睡眠，等待 I/O 操作完成然后对该缓冲区进行访问，使用完毕后，将该块放置回空闲缓冲区表的末尾块不在散列表中但有空闲块第18块不在缓冲区中但有空闲块块不在散列表中但有空闲块情形 2bq由空闲表头取得的缓冲区包含一个有效的块，而且该块的“脏”位被设置 (因此，在该块继续被其他进程使用读取其他块之前，必须将该块的内容写回磁盘)= 内核启动一个异步的写操作，将

4、该块写回磁盘= 内核重复情形 2 ，由空闲表中取得下一个缓冲区，试图以情形 2a 获取一个缓冲区来处理块 b当上述写操作完成时，该缓冲区被置于空闲表的表头，并把该缓冲区的“脏”位置位取消块不在散列表中空闲块被标记为延迟写第18块不在缓冲区中3#被标记为“延迟写”块不在散列表中空闲块被标记为延迟写情形 3qb 不在相应的 hash 表中 (该块必须有磁盘中读入到一个新的缓冲区中)q 而且空闲表为空= 请求进程睡眠直至空闲表中有空闲缓冲区为止= 当该进程被唤醒时，内核立即重新从头开始缓冲区分配程序的执行过程内核不能直接把空闲缓冲区表的头一个缓冲区立即分配给该进程，因为其他进程可能已经把块 b 读入

5、其他的某个缓冲区中 (如果再分配给该进程则将导致磁盘快和缓冲区的一对一对应性被破坏)，因此，该进程必须重新在 hash 表中检查块 b 是否已被缓冲存储块不在散列表中空闲块表为空第18块不在缓冲区中空闲表为空情形 4qb 在相应的 hash 表中q而且该缓冲区已被加锁 (该缓冲区不在空闲表中)= 请求进程睡眠等待直至该缓冲区被释放= 当该缓冲区变为空闲时内核唤醒所有等待该缓冲区的进程 (可能有许多进程在等待)= 当该进程被唤醒时，内核重新从头开始缓冲区分配程序的执行过程内核不能直接把该缓冲区分配给该进程，因为其他新近被唤醒的进程可能已经抢先获得了该缓冲区，或者同时该缓冲区的内容可能已被其他进程

6、读入了其他的磁盘块块在散列表中但块忙第99块“忙”，请求进程睡眠等待提纲n数据缓冲区概念的引入n数据缓冲区的结构n缓冲区分配的5种可能的情况n分配缓冲区的算法getblkn缓冲区的释放算法brelsen缓冲区预读取和延迟写n缓冲区机制的优点和不足为文件块读写分配缓冲区n缓冲区分配算法 getblkn算法 getblkn输入：文件系统号n 块号n输出：现在可用的缓冲区，使用之前系统加锁nwhile (尚未分配块)qif (块在散列队列中)q if (块忙) / 第五种情况q sleep(等候块空闲);q continue;q q 标记该块为“忙”; / 第一种情况q 由空闲表中取出该块;q re

7、turn(块);qqelseq if(空闲表中无空闲块) / 第四种情况q sleep(等候“空闲块出现”事件);q continue;q q 由空闲表中取出该块;q if(块标记为“延迟写”) / 第三种情况q 启动异步I/O把该块写至磁盘; q continue;q q 由散列队列中取出该块; / 第二种情况q 将该块放至新散列队列;q return(块);qnUNIX 数据缓冲区管理代码BUFFER *buf_fetch(BLKNO b) nfetch a buffer for block b - the data in the buffer returned may not be “v

8、alid”void buf_release(BUFFER *bf) nput buffer back in free listBUFFER *buf_read(BLKNO b)nreturn buffer with contents of bvoid buf_write(BUFFER *bf, flag sync_or_async)nwrite contents of buffer to discvoid buf_iodone(BUFFER *bf, int error)ninterrupt service routine called on completion of IO op/* Fet

9、ch a buffer for the block b - n.b. the data in the buffer returned * does not necessarily have to be “valid”. */BUFFER *buf_fetch(BLKNO b)for(;) mutex_enter();if (block is in hash list) if (buffer not in free list - i.e. is busy) mutex_exit(); /* scenario 4 */sleep(“this buffer free”);continue; /* b

10、ack to square 1 */remove buffer from list; /* scenario 1 */mutex_exit();return buffer;while (free list not empty) /* scenario 2 */remove first buffer from free list;if (buffer has “dirty” flag set) mutex_exit(); /* scenario 2b */ buf_write(buffer, ASYNC); /* disc */mutex_enter();continue; /* inner l

11、oop */set buffers block field to b; /* scenario 2a */move buffer to new place in hash list;mutex_exit();return buffer (with “valid” flag unset);mutex_exit(); /* scenario 3 */sleep(“some buffer free”); /* end for loop */ /* end buf_fetch() */* Put buffer back in free list after it has been operated o

12、n. */void buf_release(BUFFER *bf)mutex_enter();if (bf flags “valid” and not “old”)put buf at end of free list;elseput buf at start of free list;mutex_exit();wakeup(“some buffer free”);wakeup(“this buffer free”);/* Return buffer with contents of b. */BUFFER *buf_read(BLKNO b)BUFFER *bf = buf_fetch(b)

13、; /* Get a suitable locked buffer */if (bf “valid” flag unset) initiate disk read;sleep(“this disc read complete”);return bf;/* Write contents of buffer to disc */void buf_write(BUFFER *bf, flag sync_or_async)/* we assume bf is not on free list - i.e. is locked */initiate disc write;if (sync_or_asyn

14、c = SYNC) sleep(“this disc write complete”);buf_release(bf); else if (bfs “dirty” flag set)set bfs “old” flag;/* Interrupt service routine called by the OS on completion of an IO * operation. */void buf_iodone(BUFFER *bf, int error)/* we assume bf is not on free list - i.e. is locked */if (error = 0

15、)set bfs “valid” flag;elseunset bfs “valid” flag;buf_release(bf);提纲n数据缓冲区概念的引入n数据缓冲区的结构n缓冲区分配的5种可能的情况n分配缓冲区的算法getblkn缓冲区的释放算法brelsen缓冲区预读取和延迟写n缓冲区机制的优点和不足缓冲区释放算法n缓冲区释放算法缓冲区释放算法 brelsen输入输入：加锁的块n输出输出：无q唤醒等待空闲块的进程;q唤醒等待该块的进程;q提高处理机执行级以屏蔽中断;qif(块有效且非“旧”)q 将该块放至空闲表尾部;qelseq 将该块放至空闲表头部;q降低处理机执行级以允许中断;q给缓

16、冲区解锁; 提纲n数据缓冲区概念的引入n数据缓冲区的结构n缓冲区分配的5种可能的情况n分配缓冲区的算法getblkn缓冲区的释放算法brelsen缓冲区预读取和延迟写n缓冲区机制的优点和不足磁盘块读写算法n读磁盘块算法读磁盘块算法 breadn输入输入：块号n输出输出：含有数据的缓冲区q得到该块的缓冲区(算法getblk);qif (缓冲区数据有效)q return(缓冲区);q启动磁盘读;qsleep(等待“读盘完成”事件);qreturn(缓冲区); 磁盘预读取n算法 breadan输入：(1) 立即读的文件系统块号n (2) 异步读的文件系统块号n输出：含有立即读块数据的缓冲区nif (

17、立即读的块不在缓冲区池中)n为第一块分配缓冲区(算法getblk);nif(缓冲区数据无效)n 启动磁盘读;nnif(第二块不在缓冲区池中)n 为第二块分配缓冲区(算法getblk);n if(缓冲区数据有效)n 释放缓冲区(算法brelse);nelsen 启动磁盘读;nnif(第一块在缓冲池中)n 读第一块(算法bread);n return(缓冲区);nnsleep(第一个缓冲区包含有效数据的事件);nreturn(缓冲区); 磁盘块读写算法n算法算法 bwriten输入输入：缓冲区n输出输出：无q启动磁盘写;qif(I/O 同步)q sleep(等待“I/O完成”事件);q 释放缓冲区(算法 brelse);qqelse i