计算机操作系统第七章--磁盘调度.ppt

第七章 磁盘存储器管理 第七章 磁盘存储器管理 7.1 磁盘I/O 磁盘性能简述 早期的磁盘调度算法 各种扫描算法 7.2 外存分配方法 连续分配 链接分配 索引分配 7.3 空闲存储空间的管理 空闲表法 空闲链表法 位示图法 成组链接法 7.1 磁盘I/O 7.1.1 磁盘性能简述 1、数据的组织格式 2、磁盘的类型 1）固定头磁盘 2）移动头磁盘 3、磁盘访问时间 寻道时间 旋转延迟时间 传输时间 7.1.2 磁盘调度 1、早期的磁盘调度算法 1、先来先服务 2、最短寻道时间优先 2、各种扫描算法 1、扫描算法 2、单向扫描算法 3、 分步扫描算法 7.1 磁盘I/O 磁盘存储器不仅容量大，存取 速度快，而且可以实现随机存取，是 实现虚拟存储器所必须的硬件，因此 在现代计算机系统中，都配置了磁盘 存储器，并以它为主存放文件。 磁盘存储器管理的主要任务是： 为文件分配必要的存储空间，使每个文 件能“各得其所”； 合理的组织文件的存取方式，以提高对 文件的访问速度； 提高磁盘存储空间的利用率； 提高对磁盘的I/O速度，以改善文件系统 的性能； 采取必要的冗余措施，来确保文件系统 的可靠性。 7.1 磁盘I/O 7.1磁盘I/O 磁盘I/O速度的高低，将直接影响到 文件系统的性能。如何改善磁盘I/O的性 能，已成为提高文件系统性能的关键。 提高磁盘I/O速度的主要途径有： 选择性能好的磁盘 采用好的磁盘调度算法 设置磁盘高速缓冲区 7.1.1磁盘性能简述 对磁盘的详细介绍有专门的课程 ，在此，仅对磁盘性能，如对数据的组 织、对磁盘的类型及访问时间等 ，做 扼要的介绍 。 一、数据的组织 磁盘设备中，可包含一个或多个 盘片，每片分两面，每面又可分成若干 条磁道(典型值为5002000条磁道)，磁 道之间有必要的空隙。 每条磁道上可存储相同数目的二进 制位。磁盘密度即每英寸中所存储的位 数，显然，内层磁道 的密度较外层磁道 的密度高。每条磁道又分成若干个扇区 ，其典型值为10100个扇区。每个扇区 的大小相当于一个盘块。各扇区之间同 样要保留一定的间隙。 为在磁盘上存储数据，必须将磁盘格 式化。 7.1.1磁盘性能简述 磁盘的结构和布局 7.1.1磁盘性能简述 温盘(温彻斯特)的一条磁道含有 30个固定大小的扇区，每个扇区容量 为600个字节。其中，512字节用于存 放数据，其余用于存放控制信息。每 个扇区包括两个字段： 标识符字段 其中一个字节的SYNCH具有特 定的位图像，作为该字段的定界符。 利用磁道号、磁头号及扇区号三者来 标识一个扇区;CRC字段用于段校验。 数据字段 存放512个字节的数据。 二、磁盘的类型 对磁盘可从不同的角度进行分类 。 硬盘和软盘 单片盘和多片盘 固定头磁盘和活动头磁盘等 7.1.1磁盘性能简述 7.1.1磁盘性能简述 1.固定头磁盘 这种磁盘在每条磁道上都有一 个读/写磁头，所有的磁头都被装在一 刚性磁臂中，通过这些磁头可访问所 有磁道，并进行并行读/写，有效地提 高了磁盘的I/O速度。这种结构的磁盘 主要用于大容量磁盘上。 2.移动头磁盘 每个盘面配一个磁头，装入磁臂 中，为能访问该盘面上的所有磁道，该 磁头必须移动进行寻道。移动头磁盘只 能进行串行读/写，I/O速度较慢，但结 构简单，广泛地用于中、小型磁盘设备 中。在微机上配置的温盘(温彻斯特)和 软盘，都采用移动磁头结构，故本节主 要针对这类磁盘的I/O进行讨论。 7.1.1磁盘性能简述 7.1.1磁盘性能简述 三、磁盘访问时间 磁盘在工作时，以恒定速率旋转。 为了读或写，磁头必须能移动到所要 求的磁道上，并等待所要求的扇区的 开始位置旋转到磁头下，然后再开始 读或写数据。对磁盘的访问时间，包 括以下三部分： 1.寻道时间Ts 把磁臂(磁头)从当前位置移动到指 定磁道上所经历的时间。该时间是启动 磁臂的时间s与磁头移动n条磁道所花费 的时间之和，即： Ts =m*n+s 7.1.1磁盘性能简述 m是一常数，它与磁盘驱动器的速 度有关。对一般磁盘，m=0.3(0.2)； 对高速磁盘，m0.1,磁臂启动时间约 为3ms(2ms)。对一般的温盘，其寻道 时间将随寻道距离的增大而增大，大 体上是1040ms.(530ms) 2.旋转延迟时间Tr 7.1.1磁盘性能简述 7.1.1磁盘性能简述 Tr是指定扇区移动到磁头下面所 经历的时间。对于硬盘，典型的旋转 速度为3 600r/min(54 000r/min或72 000r/min),每转需时16.6ms(11.1,s).平 均旋转延迟时间Tr为8.3ms(5.55ms). 对于软盘，其旋转速度为300或 600r/min，这样，平均Tr为 50100ms. 3.传输时间Tt Tt是指把数据从磁盘读出，或向磁盘 写入数据所经历的时间。 Tt的大小与每 次所读/写的字节数b及旋转速度有关： Tt = 1/r是指一圈用了多 少时间 r为磁盘以秒计的旋转速度；N为一 条磁道上的字节数。当一次读/写的字节 数相当于半条磁道上的字节数时， Tt与 Tr相同。因此，可将访问时间Ta表示为 rN b 7.1.1磁盘性能简述 7.1.1磁盘性能简述 Ta = Ts +1/2r+b/rN 由上式可以看出，在访问时 间中，寻道 时间和旋转延迟时间 ，基本上都与所读/写数据的多少 无关，而且它通常是占据了访问 时间的大头。 例如，我们假定寻道时间和旋转 延迟时间平均为30ms(20ms)，而磁道的 传输速率为1MB/s(10MB/s)，如果传输 1K(10KB)字节，此时总的访问时间为 31ms(21ms)，传输时间所占比例是相当 地小。 7.1.1磁盘性能简述 7.1.1磁盘性能简述 当传输10K(100KB)字节的数据时， 其访问时间也只是40ms(30ms)，即当 传输的数据量增加10倍时，访问时间 只增加了约30 (50%)。目前磁盘的 传输速率传输已达20MB/s(80MB/s)以 上，数据传输时间所占的比例更低。 适当地集中数据(不要太零散)传输， 将有利于提高传输效率。 7.1.2 早期的磁盘调度算法 当有多个进程都请求访问磁盘时， 采用一种适当的驱动调度算法，使各 进程对磁盘的平均访问(主要是寻道)时 间最小。目前常用的磁盘调度算法有 ： 先来先服务 最短寻道时间优先 扫描算法 循环扫描算法等 一、先来先服务FCFS(First- Come,First-Served) 最简单的磁盘调度算法。根据进程请 求访问磁盘的先后次序进行调度。 优点:公平、简单。每个进程的请求 都能依次得到处理，不会出现某一进程 的请求长期得不到满足的情况。但由于 未对寻道进行优化，致使平均寻道时间 可能较长。 7.1.2 早期的磁盘调度算法 被访问访问 的 下 一个磁道号 移动动距离 (磁道数) 5545 583 3919 1821 9072 16070 15010 38112 184146 平均寻寻道长长度：55.3 7.1.2 早期的磁盘调度算法 当用户提出的访问请求比较均匀 地遍布整个盘面，而不具有某种倾向 时，FCFS导致了随机访问模式，这 种策略无法对访问进行优化。在对盘 的访问请求比较多的情况下，将降低 设备服务的吞吐量和提高响应时间， 但各进程得到服务的响应时间的变化 幅度较小。 FCFS在访问请求不是很多的 情况下，是一个可以接受的策略。 7.1.2 早期的磁盘调度算法 二、最短寻道时间优先SSTF(Shortest Seek Time First) 首先选择要求访问的磁道与当前磁 头所在的磁道，距离最近的进程，以使 每次的寻道时间最短。 7.1.2 早期的磁盘调度算法 被访问访问 的下 一个磁道号 移动动距离 (磁道数) 9010 5832 553 3916 381 1820 150132 16010 18424 平均寻寻道 长长度：27.5 7.1.2 早期的磁盘调度算法 此策略可以得到比较好的吞吐 量和较低的平均响应时间。其缺点 是对用户的服务请求的响应机会不 是均等的，对中间磁道的访问请求 得到最好的服务，对内、外两侧磁 道的服务随偏离中心磁道的距离而 愈远愈差。 7.1.2 早期的磁盘调度算法 7.1.3 各种扫描算法 一、扫描(SCAN)算法 1.进程“饥饿”现象 SSTF算法虽然获得较好的寻道性 能，但它可能导致某些进程发生“饥饿 ”(Starvation). 对SSTF算法略加修改后所形成的 SCAN算法，即可防止老进程出现饥饿现 象。 2.SCAN算法(Denning首先提出的) 该算法不仅考虑到欲访问的磁道与当前 磁道的距离，更优先考虑的是磁头的当前 移动方向。例如，当磁头正在自里向外移 动时，SCAN算法所选择的下一个访问对 象应既在当前磁道之外，又是距离最近的 磁道。 这样自里向外地访问，直至再无 更外的磁道需要访问时，才将磁臂换向， 自外向里移动。 7.1.3 各种扫描算法 避免了饥饿现象的出现。 这种算法中磁头移动的规律颇似电梯 的运行，故又常称为电梯调度算法。下 图中表示出了按SCAN算法对9个进程进 行调度及磁头移动的情况。 7.1.3 各种扫描算法 被访问访问 的下 下个磁道号 移动动距离 (磁道数) 15050 16010 18424 9094 5832 553 3916 381 1820 平均寻寻道长长度：27.8 7.1.3 各种扫描算法 二、循环扫描CSCAN(Circular SCAN) 单向扫描 SCAN算法既能获得较好的性能， 又能访止进程饥饿，广泛用于大、中 、小型 机和网络中的磁盘调度。 7.1.3 各种扫描算法 问题：当磁头刚从里向外移动过 某一磁道时，恰有一进程请求访问 此磁道，这时该进程必须等待，待 磁头从里向外，然后再从外向里扫 描完所有要访问的磁道后，才处理 该进程的请求，致使该进程的请求 被严重地推迟。 7.1.3 各种扫描算法 CSCAN算法规定磁头单向移 动。例如，只自里向外移动，当磁头 移到最外的磁道时，磁头立即返回到 最里的欲访磁道，即将最小磁道号紧 接着最大磁道号构成循环，进行扫描 。采用循环扫描方式后，上述请求进 程的请求延迟，将从原来的2T减 T+Smax 7.1.3 各种扫描算法 T为由里向外或由外向里扫描 完所有要访问的磁道所需的寻道时 间，而Smax是将磁头从最外面被访 问的磁道直接移到最里边欲访问的 磁道所需的寻道时间(或相反)。下 图表示出了CSCAN算法对9个进程 调度的次序及每次磁头移动的距离 。 7.1.3 各种扫描算法 被访问访问 的下 一个磁道号 移动动距离 (磁道数) 15050 16010 18424 18166 3820 391 5516 583 9032 平均寻寻道长长度：27.5 7.1.3 各种扫描算法 三、N-Step-SCAN和FSCAN调度算法 1、N-Step-SCAN算法 分步扫描 在SSTF、SCAN及CSCAN几种调 度算法中，都可能出现磁臂停留在某 处不动的情况。这一现象称为磁臂粘 着(Armstickiness)。在高密度盘上出 现此情况。 7.1.3 各种扫描算法 N步SCAN算法是将磁盘请求队 列分成若干个长度为N的子队列， 磁盘调度将按FCFS算法依次处理这 些子队列。每处理一个队列时，又 是按SCAN算法，对一个队列处理 完后又处理其它队列，这样就可避 免出现粘着现象。 7.1.3 各种扫描算法 当N值取得很大时，会使N步扫描 算法的性能，接近于SCAN算法的 性能，当N=1时，N步SCAN算法退 化为FCFS算法。 7.1.3 各种扫描算法 2.FSCAN算法 FSCAN算法实质上是N步SCAN 算法的简化。它只将磁盘请求访问队 列分成两个子队列。一是当前所有请 求磁盘I/O的进程形成的队列，由磁 盘调度按SCAN算法进行处理。另一 个队列则是在 扫描期间，新出现的 所有请求磁盘I/O进程的队列，放入 另一等待处理的请求队列。这样，所 有的新请求都将被推迟到下一次扫描 时处理。 7.1.3 各种扫描算法 7.4文件系统性能的改善 文件系统的性能可表现在多个方 面，如对文件的访问的快速性，数据的 可共享性，文件系统使用的方便性，数 据的安全性和数据的一致性等等。本节 只讨论文件访问的快速性和数据的一致 性这样两个问题。 7.4文件系统性能的改善 为了提高对文件的访问速度，可从 三个层次上着手： 改进文件的目录结构以及检索目录的 方法，来减少对文件的查找时间； 选择好的文件存储结构，以提高对文 件的访问速度； 提高磁盘I/O速度，以提高数据的传送 速度。 对提高文件访问速度的讨论，就可 进一步缩小为对提高磁盘I/O速度的讨论 。 7.4文件系统性能的改善 7.4.1 磁盘高速缓存 目前，磁盘I/O速度远低于对内 存的访问速度，通常要低上47个数 量级，因此，磁盘I/O已成为计算机 系统的瓶颈。于是，人们便千方百 计地去提高磁盘I/O速度，其中最主 要的技术，便是利用磁盘高速缓存 （Disk Cache）。 磁盘高速缓存的形式 所谓的磁盘高速缓存，是指利用内 存中的存储空间，来暂存从磁盘中 读出的一系列盘块中的信息。因此 ，这里的高速缓存是一组在逻辑上 属于磁盘，而物理上是驻留在内存 中的盘块。 7.4.1 磁盘高速缓存 7.4.1 磁盘高速缓存 高速缓存在内存中可分为两种形 式： 在内存中开辟一个单独的存储空间 作为磁盘高速缓存，其大小是固定 的，不会因为受应用程序多少影响 ； 7.4.1 磁盘高速缓存 把所有未利用的内存空间变成一 个缓存池，供请求分页系统和磁盘I/O 时（作为磁盘高速缓存）共享。此时 高速缓存的大小，显然不再是固定的 。当磁盘的I/O的频繁程度较高时，该 缓存池可能包含更多的内存空间；而 在应用程序运行较多时，该缓存池可 能只剩下较少的内存空间。 数据交付 数据交换（Data Delivery）是指 将磁盘高速缓存中的数据传送给请求 者进程。当进程请求访问某个盘块中 的数据时，由核心先查看磁盘高速缓 冲器，是否存在进程所需访问的盘块 数据的拷贝。若有，从高速缓存中提 取数据交付给请求者进程，避免了访 盘操作，使本次访问速度提高47个数 量级； 7.4.1 磁盘高速缓存 7.4.1 磁盘高速缓存 否则，先从磁盘中将所访问的数据读 入并交付给请求进程，同时将数据送 高速缓存，以后需要访问该盘块的数 据时，便可直接从高速缓存中提取。 系统可以采取下述两种方式，将数 据交付给请求者进程： （1）数据交付。这是直接将高速 缓存中的数据，传送到请求者进程 的内存工作区； （2）指针交付。只将指向高速缓 存中某区域的指针，交付给请求者 进程。 后一种方式由于所传送的数 据少，因而节省了数据从存储器到 存储器的时间。 7.4.1 磁盘高速缓存 三、 置换算法 将磁盘中的盘块数据读入高速缓存 时，会因高速缓存中已装满盘块数据 ，而需要将其中的数据先换出。采用 哪种置换算法？常用的置换算法最近 最久未使用算法LRU、最近未使用算 法NRU及最少使用算法LFU等。 7.4.1 磁盘高速缓存 不少系统在设计高速缓存的置换算 法时，除了考虑到最近最久未使用原 则外，还考虑了以下几点： 访问频率。每执行一条指令时，便 可能访问一次联想存储器，联想存储 器的访问频率，与指令的执行频率相 当；而对高速缓存中的访问频率，与 磁盘的I/O的频率相当，因此，对联想 存储器的访问频率远远高于对高速缓 存的访问频率。 7.4.1 磁盘高速缓存 7.4.1 磁盘高速缓存 可预见性。在高速缓存中的各盘 块数据，哪些数据可能在较长时间内 不会再被访问，哪些数据可能很快就 被再访问，有相当一部分是可预知的 。 数据的一致性。高速缓存是在内 存中，内存又是一种易失性的存储器 ，一旦系统发生故障，存放在高速缓 存中的数据将会丢失，而其中有些盘 块（如索引节点盘块）中的数据已被 修改，但未拷回磁盘。因此，当系统 发生故障后，可能会发生数据的不一 致性。 7.4.1 磁盘高速缓存 7.4.1 磁盘高速缓存 基于上述考虑，有的系统中将高速 缓存中的所有盘块数据，拉成一条 LRU链。对于那些会严重影响到数据 一致性的盘块数据和很久都可能不再 使用的盘块数据，都放在LRU链的头 部使它们能被优先写入磁盘，以减少 发生数据不一致性的概率，或者可以 尽早的腾出高速缓存的空间。 对于那些可能在不久之后便要再使 用的盘块数据，应挂在LRU链的尾部 ，以便在不久以后需要时，只要该数 据块尚未从链中移至链首而被写回磁 盘，便可直接到高速缓存中（即LRU 链中）去找到它们。 7.4.1 磁盘高速缓存 7.4.1 磁盘高速缓存 四、周期性写回磁盘 一种情况值得注意：根据LRU算法， 那些经常被访问的盘块数据，可能会 一直保留在高速缓存中而长期的不会 被写回磁盘中。（注意，LRU链意味 着链中的任一元素在被访问到后，又 被移动到链尾） 为了解决这一问题，在UNIX系 统中专门增设了一个修改（update） 程序，使之在后台运行。该程序周期 性地调用一个系统调用SYNC。该调 用的主要功能是强制性地将所有在高 速缓存中已修改的盘块数据写回磁盘 ，一般是把两次调用SYNC的时间间 隔定为30秒钟。这样，因系统故障所 造成的工作损失不会超过30s的劳动量 。 7.4.1 磁盘高速缓存 而在MS-DOS中所采用的方 法是：只要高速缓存中的某盘块数 据被修改，便立即将它写回磁盘， 并将这种高速缓存称为“写穿透、高 速缓存”（write-through cache）。 MS-DOS所采用的写回方式，几乎 不会造成数据的丢失，但需频繁地 启动磁盘。 7.4.1 磁盘高速缓存 7.4.2 优化数据的分布 一、 优化物理块的分布 另一个提高对文件访问速度的重要 措施，是优化文件物理块的分布，使磁 头的移动距离最小。 链接分配和索引分配方式，都允许 将一个文件的物理块分散在磁盘的任意 位置，但如果将一个文件的多个物理块 ，安排得过于分散，将会增加磁头的移 动距离。如果将数据块安排在属于同一 条磁道的两个盘块上，会由于消除了磁 盘在磁道上的移动，而大大提高了对盘 块的访问速度。 对文件盘块的优化，应在为文件 分配盘块时进行。若系统的空白存储 空间采用位示图方式表示时，将同一 个文件的盘块安排在同一条磁道上或 相邻的磁道上是容易的事。只需从位 示图中找到一片相互邻接的多个空闲 盘块即可。当系统采用线性表（链） 法来组织空闲存储空间时，为一文件 分配相邻接的多个盘块，就要困难一 些。 7.4.2 优化数据的分布 7.4.2 优化数据的分布 可将在同一磁道上的若干个磁块组成 一簇，例如，一簇包括四个盘块，在 进行存储空间的分配时，以簇为单位 分配。这样就可以保证在访问这几个 盘块时，可不移动磁头或者仅移动一 条磁道的距离，从而减少了磁头的平 均移动距离。 7.4.3 提高磁盘I/O速度的其它方法 在系统中设置了磁盘高速缓存后，能 明显的减少等待磁盘I/O的时间。本小 节再介绍几种能有效的提高磁盘I/O速 度的方法，这些方法已被许多系统采用 。 7.4.3 提高磁盘I/O速度的其它方法 一、提前读（Read-Ahead） 用户（进程）对文件进行访问时，经 常顺序访问文件的各盘块的数据。在读当 前块时可以预知下一次要读的盘块。可以 采取预先读方式。即在读当前块的同时， 要求提前将下一个盘块（提前读的块）中 的数据也读入缓冲区。当下一次要读该盘 块中的数据时，便可直接从缓冲区中取得 下一盘块的数据，而不须再去启动磁盘I/O ，从而大大减少了读数据的时间。 就等效于提高了磁盘I/O的速度 。“提前读”功能已被广泛应用，如在 UNIX系统、OS/2，以及3 plus和 Netware等的网络OS中，都已采用。 7.4.3 提高磁盘I/O速度的其它方法 7.4.3 提高磁盘I/O速度的其它方法 二 延迟写 延迟写是指在缓冲区A中的数据 ，应立即写回磁盘，但考虑到该缓冲 区的数据，不久之后可能还会再被本 进程或其它进程访问（共享数据）， 因而并不立即将该缓冲区A中的数据 写入磁盘，而是将它挂在空闲缓冲区 队列末尾。 当再有进程申请到该缓冲区时， 才将该缓冲区的数据写入磁盘，而把该 缓冲区作为空闲缓冲区分配出去。当该 缓冲区A仍在队列中时，任何访问该数 据的进程，便可直接读出其中的数据， 而不必去访问磁盘。这样，又可进一步 减小等效的磁盘I/O时间。同样，“延迟 写”功能已在UNIX系统、OS/2等OS中 被广泛的采用。 7.4.3 提高磁盘I/O速度的其它方法 三、虚拟盘（Virtual Disk） 所谓虚拟盘是指利用内存空间 去仿真磁盘，又称为RAM盘。该盘 的设备驱动程序，可以接受所有标 准的磁盘操作，但这些操作的执行 ，不是在磁盘上而是在内存中。这 些对用户都是透明的。换言之，用 户们并不会发现这与真正的磁盘操 作有什么不同，而仅仅是略微快些 而已。 7.4.3 提高磁盘I/O速度的其它方法 虚拟盘问题：它是易失性存储器， 一旦系统或电源发生故障，或系统再 启动时，原来保存在虚拟盘中的数据 将会丢失。因此，虚拟盘通常用于存 放临时文件，如编译程序所产生的目 标程序等。虚拟盘与磁盘高速缓存的 主要区别在于：虚拟盘中的内容完全 由用户控制，而高速磁盘缓存中的内 容是由OS控制的。例如，RAM盘在 开始时是空的，只有当用户（程序） 在RAM盘中创建了文件后，RAM盘 中才有内容。 7.4.3 提高磁盘I/O速度的其它方法 总 结 考核要点：设备分类，I/O控制方式， Spooling系统，缓冲区的作用，设备驱动 程序，设备分配过程，共享设备，独占设 备，虚拟设备，设备独立性。 本章基础要点： 1、虚拟设备是指通过虚拟技术将一台独占设 备改造成若干台逻辑设备，供若干个用户 进程同时使用，把这种经过虚拟技术处理 后的设备称为虚拟设备。 2、按信息交换单位分类可以将设备分为块设 备和字符设备。 3、通道是负责I/O的处理机。 4、根据信息交换方式的不同，可以将通道分 为字节多路通道、数据选择通道和数据多 路通道。 5、字节多路通道用作连接大量的低速I/O设 备。 总 结 6、从资源分配的角度看，操作系统将外部设 备分为独占型设备、共享型设备和虚拟设备 。 7、设备独立性是指应用程序独立于具体使用 的物理设备。 8、缓冲技术中的缓冲池在主存中。 9、进行设备分配时所需要的数据表格主要有 设备控制表、设备控制器控制表、通道控制 表和系统设备表。 总 结 10、在应用程序中，用户在使用I/O设 备时，通常采用逻辑设备名。 11、大多数低速设备都属于独享设 备。 12、为了实现CPU与外设的并行工 作，系统引入了中断和通道硬件 机制。 总 结 13、在操作系统中，一种用空间换取时间 的资源转换技术是Spooling。 14、Spooling系统是由磁盘中的输入井和输出 井，内存中的输入缓冲区和输出缓冲区以及 输入进程和输出进程组成。 15、 Spooling技术是在共享设备上模拟独占 设备。由预输入程序将作业执行中需访问 数据预先读入到输入井中，缓输出程序则 负责将输出井中的信息在输出设备上输出 。 总 结 16、设备与内存之间的数据传输控制方式 有程序直接控制方式、中断控制方式、 通道控制方式和DMA控制方式，其中通 道方式占用CPU时间最短。 17、设备分配中的安全性是指设备分配应 保证不会引起进程死锁。 18、引起中断发生的事件称为中断源。 19、最短寻道时间优先算法选择与当前磁头所 在磁道距离最近的请求作为下一次服务的对 象。 20、磁盘访问时间由三部分组成，即寻道时间 、旋转延迟时间及传输时间。 总 结 练习题及参考答案 练习： 1、如何将独占型输入设备改造成可共享 使用的虚拟设备？ 2、设CPU和输入设备I、输出设备O并行 执行，且输入设备I和输出设备O的启动 受CPU指令的控制。另外，输出设备O 的启动还受输出缓冲区是否装满输出数 据的限制。只有装满输出数据，输出设 备才能被启动。试描述中断处理方式下 的CPU工作过程。 3、为什么要设置内存I/O缓冲区？通常有 哪几类缓冲区？ 4、什么是设备驱动程序？其功能是什么 ？ 5、在设备管理中，何谓设备独立性？如 何实现设备独立性？ 6、试给出常用的I/O调度算法。 7、为什么要引入Spooling系统？Spooling 系统可带来哪些好处？ 练习题及参考答案 8、DMA控制方式与通道控制方式有什 么不同？ 9、设备分配时为什么应考虑安全性以 及设备的无关性？ 练习题及参考答案 答案： 1、独占型设备在一段时间内只能由一个用户 使用，使许多进程因等待它们而阻塞，从而 影响了整个系统的效率。另一方面，分配到 独占设备的进程，在其整个运行期间，往往 占有这些设备，却并不是经常使用这些设备 ，因而使这些设备的利用率很低。Spooling 技术通过共享设备来虚拟独占设备，将独占 设备改造成为共享设备，从而提高了设备利 用率和系统的效率。 练习题及参考答案 采用Spooling技术，可以预先从低速 的独占型输入设备上将程序运行需要的 数据传送到高速磁盘上的输入井中，当 用户程序运行时，可以直接从输入井中 将数据读入内存。由于磁盘是共享设备 ，多个用户进程可以共享使用输入井。 这样，就将独占型的输入设备改造成了 可共享使用的虚拟设备。 练习题及参考答案 2、（1）当没有输入输出请求时，CPU正常 工作，运行多个进程。 （2）当某进程需要数据时，CPU发出“启动 ”命令启动输入设备I准备数据，同时将控 制状态寄存器中的中断允许位打开，以便 在需要时，中断程序可以被执行。在进程 发出指令启动设备I后，该进程放弃处理机 ，等待输入完成。由进程调度程序调度其 他就绪进程占据处理机。 练习题及参考答案 当输入完成后，设备控制器通过中断 请求线向CPU发出中断。CPU在收到中 断信号之后，转向相应的中断处理程序 对数据输入工作进行相应的处理。中断 结束后，CPU返回到被中断的现场，继 续执行被中断的进程。以在后的某个时 刻，进程调度程序选中提出请求输入数 据的进程，该进程获得输入数据并继续 工作。 练习题及参考答案 （3）当某进程需要输出数据时，CPU将数 据送到输出缓冲区，并判断输出缓冲区是 否装满输出数据，如不满，则等待后续的 输出数据。 练习题及参考答案 否则CPU发出“启动”命令启动输出 设备O，将输出缓冲区中的所有数据输出 。同时将控制状态寄存器中的中断允许位 打开，以便在需要时，中断程序可以被执 行。在进程发出指令启动设备后，该进程 可以继续执行，也可以放弃处理机，等待 输出完成。由进程调度程序调度其他就绪 进程占据处理机。 练习题及参考答案 当输出完成后，设备控制器通过中断 请求线向CPU发出中断。CPU在收到中断 信号之后，转向相应的中断处理程序对数 据输出工作进行相应的处理。中断结束后 ，CPU回到被中断的现场，继续执行被中 断的进程。 练习题及参考答案 3、设置内存I/O缓冲区的主要原因如下： （1）缓和CPU与I/O设备速度不匹配的矛盾。 一般情况下，程序的运行过程是时而进行计 算，时而进行输入或输出。以输出为例，如 果没有缓冲区，则程序在输出时，必然由于 打印机的速度跟不上而使CPU停下来等待； 然而在计算阶段，打印机又无事可做。如果 设置一个缓冲区，程序可以将待输出的数据 先输出到缓冲区中，然后继续执行；而打印 机则可以从缓冲区取出数据慢慢打印。 练习题及参考答案 （2）减少中断CPU的次数。例如，假 定设备只用一位二进制位数接收从系统外 传来的数据，则设备每收到一位二进制数 就要中断CPU一次，如果数据通信速率为 9.6kbps，则中断CPU的频率也为9.6kHz， 即每100us就要中断CPU一次，若设置一个 具有8位的缓冲寄存器，则可使CPU中断的 次数降低为前者的1/8。 练习题及参考答案 （3）提高CPU和I/O设备之间的并行性。由于在CPU和 设备之间引入了缓冲区，CPU可以从缓冲区中读取或 向缓冲区写入信息，相应地设备也可以向缓冲区写入 或从缓冲区读取信息。在CPU工作的同时，设备也能 进行输入输出操作，这样，CPU和I/O设备即可以并 行工作。 通常有四类缓冲区：单缓冲、双缓冲、循环缓 冲和缓冲池。 练习题及参考答案 4、设备驱动程序是直接控制设备进行运转的 程序。设备驱动程序接收来自上层的与设 备无关软件的抽象请求，将这些请求转换 成设备控制器可以接受的具体命令，再将 这些命令发送给设备控制器，并监督这些 命令是否正确执行。 练习题及参考答案 5、设备独立性是指应用程序独立于具体 使用的物理设备。 为了实现设备独立性，系统必 须能够将应用程序中所使用的逻辑设 备名映射为物理设备名。为此，系统 应为每个用户设置一张逻辑设备表， 其中的每个表项包括：逻辑设备名、 物理设备名和设备驱动程序的入口地 址。 练习题及参考答案 如下表所示：当进程用逻辑设备名请求分 配I/O设备时，系统为它分配相应的物理设备 ，并在逻辑设备表中建立一个表目，填上应用 程序中使用的逻辑设备名和系统分配的物理设 备名。以及该设备的驱动程序入口地址。以后 进程再利用逻辑设备名请求I/O操作时，系统 通过查找逻辑设备表，即可找到物理设备和设 备驱动程序。 练习题及参考答案 逻辑设备 名物理设备名设备驱动 程 序入口地址 /dev/tty31024 /dev/print52035 逻辑设备表 练习题及参考答案 6、常用的I/O调度算法有先请求先服务 和优先级高者优先两种算法。先请求 先服务的实现思想是当有多个进程对 同一设备提出I/O请求时，该算法根据 这些进程发出请求的先后次序，将这 些进程排成一个设备请求队列，系统 总是把设备首选分配给队首进程。 练习题及参考答案 优先级高者优先的实现思想是按 照进程优先级的高低进行设备分配，即 当多个进程对同一设备提出I/O请求时 ，哪个进程的优先级高，就先满足哪个 进程的请求。对优先级相同的I/O请求 ，则按先请求先服务的算法排队。 练习题及参考答案 7、所有字符设备都是独占设备并属于慢速 设备，因此，当一个进程在某台字符设备 上进行数据交换时，往往要等待较长时间 ，并且在此进程未释放该设备之前，其他 进程不能同时访问这台设备，从而使这类 设备成为系统中的瓶颈资源，使许多进程 因等待它们而阻塞。 练习题及参考答案 另一方面，分配到字符设备的进程 ，在其整个运行期间，往往占有这些设备 ，却并不是经常使用这些设备，因而使这 些设备的利用率很低。从而降低了整个系 统的性能。Spooling技术正是针对上述问 题提出的一种技术。 练习题及参考答案 Spooling技术的核心思想是利用一台 可共享、高速、大容量的块设备来模拟独占 设备的操作，使一台独占设备变成多台可并 行使用的虚拟设备。Spooling系统主要由输 入井和输出井、输入缓冲区和输出缓冲区、 输入进程和输出进程三部分组成。 练习题及参考答案 在Spooling系统中，输入进程将用 户要求的数据从输入设备送到输入井，当 CPU需要输入数据时，直接从输入井将数 据读入内存；输出进程把用户要求输出的 数据先从内存送到输出井，待输出设备空 闲时，再将输出井中的数据输出到设备上 。 练习题及参考答案 Spooling系统可带来如下好处： （1）提高了I/O速度。在对数据进行I/O操作时 ，将原来对低速设备进行的I/O操作转变为对 高速磁盘中输入井和输出井的操作，从而提高 了I/O的速度。 （2）将独占设备改造成共享设备。在Spooling 系统中，实际上并没有为任何进程分配物理的 独占设备，而只是在输入井和输出井中为进程 分配了一个磁盘存储区和建立了一张I/O请求 ，这样便将独占设备