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