第十一章 I/O管理和磁盘调度
复习题
11.1列出并简单定义执行I/O的三种技术。
·可编程I/O：处理器代表进程给I/O模块发送给一个I/O命令，该
进程进入忙等待，等待操作的完成，然后才可以继续执行。
·中断驱动I/O：处理器代表进程向I/O模块发送一个I/O命令，然
后继续执行后续指令，当I/O模块完成工作后，处理器被该模块中断。如果该进程不需要等待I/O完成，则后续指令可以仍是该进程中的指令，否则，该进程在这个中断上被挂起，处理器执行其他工作。 ·直接存储器访问（DMA）：一个DMA模块控制主存和I/O模块之间的
数据交换。为传送一块数据，处理器给DMA模块发送请求，只有当整个数据块传送完成后，处理器才被中断。
11.2逻辑I/O和设备I/O有什么区别？
·逻辑I/O：逻辑I/O模块把设备当作一个逻辑资源来处理，它并不
关心实际控制设备的细节。逻辑I/O模块代表用户进程管理的一般I/O功能，允许它们根据设备标识符以及诸如打开、关闭、读、写之类的简单命令与设备打交道。
·设备I/O：请求的操作和数据（缓冲的数据、记录等）被转换成适
当的I/O指令序列、通道命令和控制器命令。可以使用缓冲技术，以提高使用率。
11.3面向块的设备和面向流的设备有什么区别？请举例说明。 面向块的设备将信息保存在块中，块的大小通常是固定的，传输过程中
一次传送一块。通常可以通过块号访问数据。磁盘和磁带都是面向块的设备。
面向流的设备以字节流的方式输入输出数据，其末使用块结构。终端、
打印机通信端口、鼠标和其他指示设备以及大多数非辅存的其他设备，都属于面向流的设备。
11.4为什么希望用双缓冲区而不是单缓冲区来提高I/O的性能？
双缓冲允许两个操作并行处理，而不是依次处理。典型的，在一个进
程往一个缓冲区中传送数据（从这个缓冲区中取数据）的同时，操作系统正在清空（或者填充）另一个缓冲区。
11.5在磁盘读或写时有哪些延迟因素？ 寻道时间，旋转延迟，传送时间
11.6简单定义图11.7中描述的磁盘调度策略。
FIFO:按照先来先服务的顺序处理队列中的项目。
SSTF:选择使磁头臂从当前位置开始移动最少的磁盘I/O请求。
SCAN:磁头臂仅仅沿一个方向移动，并在途中满足所有未完成的请求，直到
它到达这个方向上最后一个磁道，或者在这个方向上没有其他请求为止。接着反转服务方向，沿相反方向扫描，同样按顺序完成所有请求。 C-SCAN:类似于SCAN，
11.7简单定义图7层RAID。 0：非冗余
1：被镜像；每个磁盘都有一个包含相同数据的镜像磁盘。 2：通过汉明码实现冗余；对每个数据磁盘中的相应都计算一个错误校正码，并且这个码位保存在多个奇偶校验磁盘中相应的文件。
3：交错位奇偶校验；类似于第二层，不同之处在于RAID3为所有数据磁盘中同一位置的位的集合计算一个简单的奇偶校验位，而不是错误校正码。 4：交错块分布奇偶校验；对每个数据磁盘中相应的条带计算一个逐位奇偶。 5：交错块分布奇偶校验；类似于第四层，但把奇偶校验条带分布在所有磁盘中。
6：交错块双重分布奇偶校验；两种不同的奇偶校验计算保存在不同磁盘的不同块中。
11.8典型的磁盘扇区大小是多少？ 512比特
习题
11.1考虑一个程序访问一个I/O设备，并比较无缓冲的I/O和使用缓冲区的I/O。
说明使用缓冲区最多可以减少2倍的运行时间。
如果计算的时间正好等于它的I/O时间（它是最佳环境），操作者和外围设备同时运行。如果单独运行，只要花费他们的一半时间，设C是整个程序的计算时间，T为所要求总的I/O时间，因而寄存器最好的运行时间是 max(C,T)，不需要寄存器的运行时间是C+T， 显然（(C+T)/2）≤max(C,T)≤(C+T).
11.2把习题11.1的结论推广到访问n个设备的程序中。 最佳比是（n+1）﹕n
11.3使用与表11.2类似的方式，分析下列磁道请求：27，129，110，186，147，
41，10，64，120。假设磁头最初定位在磁道100处，并且沿着磁道号减小的方向移动。假设磁头沿着磁道增大的方向移动，请给出同样的分析。 FIFO SSTF SCAN C-SCAN 下一个被访问的磁道 横跨的磁道数 下一个被访问的磁道 110 横跨的磁道数 下一个被访问的磁道 64 横跨的磁道数 下一个被访问的磁道 64 横跨的磁道数 36 27 129 110 186 147 41 10 64 120 平均寻道长度 73 10 36 102 19 76 39 106 31 54 56 61.8 120 129 147 186 64 41 27 10 平均寻道长度 10 9 18 39 122 23 14 17 29.1 41 27 10 110 120 129 147 186 平均寻道长度 23 14 17 100 41 27 10 186 147 129 120 110 平均寻道长度 23 14 17 176 39 18 9 10 38 10 9 18 39 29.6 如果磁头沿着增大的方向，只有SCAN和C-SCAN的结果有变化
SCAN C-SCAN 下一个被访问的磁道 110 横跨的磁道数 下一个被访问的磁道 110 横跨的磁道数 10 10 120 129 147 186 64 41 27 10 平均寻道长度 10 9 18 39 120 129 147 186 10 27 41 64 平均寻道长度 10 9 18 39 176 17 14 23 35.1 122 23 14 17 29.1 11.4考虑一个磁盘，有N个磁道，磁道号从0到(N-1)，并且假设请求的扇区随机地均匀分布在磁盘上。现在要计算一次寻道平均跨越的磁道数。
a.首先，计算当磁头当前位于磁道t时，寻道长度为j的可能性。提示：
这是一个关于确定所有组合数目的问题，所有磁道位置作为寻道目标的可能性是相等的。
b.接下来计算寻道长度为K的可能性。提示：这包括所有移动了K个磁道
的可能性之和。
c.使用下面计算期望值得公式，计算一次寻道平均跨越的磁道数目： N-1
E[X]=∑i∑Pr[x=i] i=0
d．说明档N比较大时，一次寻道平均跨越的磁道数接近N/3.
（a）设P[j/t]表示位于磁道t，寻道长度为j的概率，知随机访问一个任
何一个磁道的可能性为相等为1/N，因此我们有P[j/t]=1/N,t<=j-1或者t>=N-j;P[j/t]=2/N,j-1 （b）令P[k]=∑P[k/t]*P[t]=1/N∑P[k/t],由（a）可知，取值1/N的有 2k个磁道，取值为2/N有（N-k）个， 所以有 P[k]=（2k/N+2(N-k)/N）/N=2(N-k)/N*N (c)E[k]=∑k*P[k]=∑2k(N-k)/N*N =(N*N-1)/3N (d)当N比较大时，从上文可以看出一次寻道平均跨越磁道数接近N/3 11.5下面的公式适用于高速缓冲存储器和磁盘高速缓存： Ts=Tc+M×Td 请把这个公式推广到N级存储器结构，而不是仅仅2级。 定义： Ai=从i级存储器找到信息的时间； Hi=消息在第i级存储器并且没有在更高级存储器的概率； Bi=从第（i+1）级向第i级传送一块数据的时间。 假设缓存在1级存储上，主存在2级存储上，如此下去，形成一个N 级存储结构，因此有 Ts=∑AiHi 若消息在M1层，可以立即被读，如果在M2中，不在M1中，那么这块 数据从M2传到M1中再读。 因此 A2=B1+A1 进而有 A3=B2+A2=B1+B2+A1 即有 Ai=A1+∑Bj 所以 Ts=T1∑Hi+∑∑BjHi 因为 ∑Hi=1 最后可得 Ts=T1+∑∑BjHi 11.6对基于频率的替换算法（见图11.12），定义Fnew,Fmiddle和Fold分别为包含 新区，中间区和的高速缓存片段，显然Fnew+Fmiddle+Fold=1.如果有 a．Fold=1—Fnew b. Fold=1/（高速缓存大小） 请分别描述该策略。 a． 图11.11的中间区是空的，因 此这种策略退化为图11.11a的策略。 b． 老区由一块组成，并且我们有LRU替换策略。 11.7对于一个有9个磁道的磁带，磁带速度为120英寸每秒，磁带密度为1600 线位/英寸，请问它的传送率为多少？ 密度可表示为1600线位每英寸，因此传送速率为1600×1200=192000线位每秒。 11.8假设有一个2400英寸的磁带盘，记录间的间隙为0.6英寸，这个间隙是磁 带在读操作之间的停止；在间隙期间磁带速度成线性增加或减小，磁带的其他与习题11.7相同。磁带上的数据按物理记录组织，每个物理记录包含固定数目的由用户定义的单元，称为逻辑记录。 a.在磁带上读取分装在10个物理记录中的120个逻辑记录需要多少时间？ b．同样。如果是分装在30个物理记录中，则需要多少时间？ c.对于上述每种分块方案，整个磁带分别可以保存多少个逻辑记录？
操作系统精髓与设计原理-第11章 IO管理和磁盘调度
