6.7.4 缓冲池(Buffer Pool)
1. 缓冲池的组成
空缓冲链队列emp:由空缓冲区组成
输入缓冲链队列inq:由装满输入数据的缓冲区组成
输出缓冲链队列out:由装满输出数据的缓冲区组成
4种工作缓冲区
收容输入、提取输入、收容输出、提取输出。
从某队列上取下来操作完后再挂到另一队列上
2. Getbuf过程和Putbuf过程
缓冲池中的队列是临界资源要考虑互斥与同步
Procedure Getbuf(q,buf); 从q队列头摘下缓冲区buf begin Wait(RS(q)); 信号量RS(q)是队列q的长度 Wait(MS(q)); MS(q)是对q操作的互斥信号量 buf:=Takbuf(q); Signal(MS(q)); end Procedure Putbuf(q,buf); buf加到q队列的队尾 begin Wait(MS(q)); Addbuf(q,buf); Signal(MS(q)) Signal(RS(q)); end
3. 缓冲区的工作方式
收容输入的工作方式:当输入进程需要输入数据时
调用Getbuf(emp,hin)过程, 从emp队列首摘下空缓
冲区作为收容输入工作缓冲区hin
(2) 把数据输入到工作缓冲区hin
(3) 调用Putbuf(inq,hin),将hin挂到inq队列尾
提取输入工作方式：当计算进程需要提取输入数据时
(1) 调用Getbuf(inq, sin)过程,从inq队列头摘下缓冲区
作为提取输入工作缓冲区sin
(2) 计算进程从工作缓冲区sin中提取数据
(3) 调用Putbuf(emp,sin), 将sin挂在emp队列尾
6.8 磁盘存储器的性能和调度
改善磁盘系统的性能：
1）选择好的磁盘调度算法，以减少磁盘的寻道时间。
2）提高磁盘 I/O 速度，以提高对文件的访问速度。
3）采取冗余技术，提高磁盘系统的可靠性，建立高度可靠的文件系统。
6.8.1 磁盘性能简述
1. 数据的组织和格式
磁盘设备可包括一个或多个物理盘片，每个磁盘片分一个或两个存储面(Surface)，每个盘面上有若干个磁道(Track)，磁道之间留有必要的间隙(Gap)。为使处理简单起见，在每条磁道上可存储相同数目的二进制位。 这样，磁盘密度即每英寸中所存储的位数，显然是内层磁道的密度较外层磁道的密度高。每条磁道又被逻辑上划分成若干个扇区(sectors)，软盘大约为 8～32 个扇区，硬盘则可多达数百个，图中显示了一个磁道分成 8 个扇区。一个扇区称为一个盘块(或数据块)，常常叫做磁盘扇区。各扇区之间保留一定的间隙。
磁盘上存储的物理记录块数目是由扇区数、磁道数以及磁盘面数所决定的。
为了在磁盘上存储数据，必须先将磁盘低级格式化。下图示出了一种温盘(温切斯特盘)中一条磁道格式化的情况。
其中每条磁道含有 30 个固定大小的扇区，每个扇区容量为 600 个字节，其中 512 个字节存放数据，其余的用于存放控制信息。
每个扇区包括两个字段：
1）标识符字段(ID Field)，其中一个字节的 SYNCH 具有特定的位图像，作为该字段的定界符，利用磁道号(Track)、 磁头号(Head #)及扇区号(Sector #)三者来标识一个扇区；CRC 字段用于段校验。
2）数据字段(Data Field)，其中可存放 512 个字节的数据。
值得强调的是，在磁盘一个盘面的不同磁道(Track)、每个磁道的不同扇区(Sector)，以及每个扇区的不同字段(Filed)之间，为了简化和方便磁头的辨识，都设置了一个到若干个字节不同长度的间距(Gap，也称间隙)。
磁盘格式化完成后，一般要对磁盘分区。
但是，在真正可以使用磁盘前，还需要对磁盘进行一次高级格式化，即设置一个引导块、空闲存储管理、根目录和一个空文件系统，同时在分区表中标记该分区所使用的文件系统。
2. 磁盘的类型
对磁盘，可以从不同的角度进行分类。最常见的有：将磁盘分成硬盘和软盘、单片盘和多片盘、固定头磁盘和活动头(移动头)磁盘等。
1）固定头磁盘。在每条磁道上都有一读/写磁头，所有的磁头都被装在一刚性磁臂中。这种结构的磁盘主要用于大容量磁盘上。
2）移动头磁盘。每一个盘面仅配有一个磁头，也被装入磁臂中。为能访问该盘面上的所有磁道，该磁头必须能移动以进行寻道。广泛应用于中小型磁盘设备中，在微型机上配置的温盘和软盘都采用移动磁头结构。
3. 磁盘访问时间
1）寻道时间 Ts，这是指把磁臂(磁头)移动到指定磁道上所经历的时间。
2）旋转延迟时间 Tr，这是指定扇区移动到磁头下面所经历的时间。
3）传输时间 Tt，这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。
6.8.2 早期的磁盘调度算法
由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标是使磁盘的平均寻道时间最少。
1. 先来先服务 FCFS
根据进程请求访问磁盘的先后次序进行调度。
优点：简单, 公平；
缺点：效率低, 相临两次请求可能会造成最内到最外的柱面寻道, 使磁头反复移动, 增加了平均寻道时间
设磁盘访问序列: 80, 55, 58, 39, 18, 90,160,150, 38,184
2. 最短寻道时间优先
该算法选择这样的进程：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。
优点：磁盘的平均寻道时间最小
缺点：进程"饥饿"现象, 有时会造成与当前磁道距离远的访问请求长期等待得不到服务(不公平)
6.8.3 基于扫描的磁盘调度算法
1. 扫描(SCAN)算法
SSTF算法可能导致优先级低(即不断出现的新进程所要访问的磁道与当前磁头的位置时钟较劲，使原本较远的进程一直得不到满足)的进程发生“饥饿”现象。
扫描算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN 算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动。这时，同样也是每次选择这样的进程来调度，即要访问的磁道在当前位置内且距离最近者。
由于在这种算法中磁头移动的规律颇似电梯的运行，因而又常称之为电梯调度算法。
2. 循环扫描(CSCAN)算法
循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。
3. NStepSCAN 和 FSCAN 调度算法
1）NStepSCAN算法。
在 SSTF、 SCAN 及 CSCAN 几种调度算法中，都可能会出现磁臂停留在某处不动的情况。例如，有一个或几个进程对某一磁道有较高的访问频率，即这个(些)进程反复请求对某一磁道的 I/O 操作，从而垄断了整个磁盘设备。我们把这一现象称为“磁臂粘着”。
NStepSCAN 算法是将磁盘请求队列分成若干个长度为 N 的子队列，磁盘调度将按 FCFS 算法依次处理这些子队列。而每处理一个队列时又是按 SCAN 算法，对一个队列处理完后，再处理其他队列。当正在处理某子队列时，如果又出现新的磁盘 I/O 请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。当 N 值取得很大时，会使 N 步扫描法的性能接近于 SCAN 算法的性能；当 N=1 时，N 步 SCAN 算法便蜕化为 FCFS 算法。
2）FSCAN 算法。
FSCAN 算法实质上是 N 步 SCAN 算法的简化，即 FSCAN 只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘 I/O 的进程形成的队列，由磁盘调度按 SCAN 算法进行处理。在扫描期间，将新出现的所有请求磁盘 I/O 的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。
