chap5(43-44).ppt

qSPOOLing技术技术（虚拟设备的实现）（虚拟设备的实现）1、作用：将一台、作用：将一台独占的物理独占的物理I/O设备设备虚拟虚拟为为多台逻多台逻辑辑I/O设备，即允许多个用户共享一台独占物理设备，即允许多个用户共享一台独占物理I/O设备。设备。2、什么是、什么是SPOOLing：（1）定义：联机情况下实现同时外围操作，称为定义：联机情况下实现同时外围操作，称为SPOOLing或假脱机或假脱机I/O技术。技术。（2）实现：在多道环境下，用其中的一道程序来）实现：在多道环境下，用其中的一道程序来模拟脱机输入；另一道程序来模拟脱机输出，这模拟脱机输入；另一道程序来模拟脱机输出，这样在主机直接控制下实现脱机样在主机直接控制下实现脱机I/O功能。功能。5、5 设备分配设备分配 3、SPOOLing系统的组成：系统的组成：（1）输入井和输出井：在）输入井和输出井：在磁盘上磁盘上开辟的两个大存开辟的两个大存储空间。储空间。输入井：模拟脱机输入时的磁盘设备，暂存I/O设备输入的数据。输出井：模拟脱机输出时的磁盘设备，暂存用户程序的输出数据。5、5 设备分配设备分配（2）输入、输出缓冲区。在）输入、输出缓冲区。在内存中内存中开辟，为了缓开辟，为了缓和和CPU 和磁盘之间速度不匹配的矛盾。和磁盘之间速度不匹配的矛盾。输入缓冲区：暂存由输入设备送来的数据，以后再成批送入输入井。输出缓冲区：暂存由输出井送来的数据，以后再慢慢送入输出设备。5、5 设备分配设备分配（3）输入进程）输入进程Spi和输出进程和输出进程Spo。利用两个进程利用两个进程来模拟脱机来模拟脱机I/O 时的时的外围控制机外围控制机。输入进程Spi：模拟脱机输入，任务是将慢速设备上的信息写入输入缓冲区再到输入井。CPU从输入井中取数据。输出进程Spo:模拟脱机输出，任务是将内存的数据写入输出井再到输出缓冲区，从输出缓冲区送到输出设备。5、5 设备分配设备分配 4、共享打印机的实现共享打印机的实现v当用户进程提出打印申请时，当用户进程提出打印申请时，OS并不是给该进程并不是给该进程分配打印机分配打印机，而是将其，而是将其送入等待队列中排队送入等待队列中排队，真，真正排到的时候才将打印机分配给进程。具体实现正排到的时候才将打印机分配给进程。具体实现过程：过程：由Spo（输出进程）在磁盘开辟输出井，并将打印数据送入其中。5、5 设备分配设备分配 由Spo（输出进程）为该进程申请一个空白的打印申请表，将相关数据填入其中，然后挂到请求打印队列上。当得到打印机执行打印任务时，仍由Spo（输出进程）将打印数据从输出井送入内存的输出缓冲区，由打印机输出。5、5 设备分配设备分配 5、SPOOLing系统的特点（1）提高了I/O的速度。CPU读取数据和输出数据针对的是输入井和输出井。（2）将独占设备改造为共享设备。在输入井和输出井中为进程分配一个存储区和建立一张I/O申请表，而没有真正为进程分配设备。（3）实现了虚拟设备功能。物理上一个设备，逻辑上多个设备。5、5 设备分配设备分配 v磁盘不仅容量大、存取速度快，而且可以实现随机存取，是当前存放大量数据和程序的理想设备。v对文件的操作，都将涉及到对磁盘的访问，磁盘I/O速度的高低和磁盘系统的可靠性，都将直接影响到系统性能。5、6 磁盘存储器管理磁盘存储器管理 q磁盘性能简述1、数据的组织和格式（1）磁盘设备由一个或多个盘片构成（2）每个盘片分为两面，每面可分为若干磁道，各磁道之间留有必要的空隙。（3）每条磁道又分为若干扇区（盘块），各扇区之间保留一定的间隙。5、6 磁盘存储器管理磁盘存储器管理 移动臂读写磁头盘面柱面磁道扇区轴硬磁盘结构（4）磁盘地址：磁道号(柱面号)、磁头号及扇区号（5）在每条磁道上可存储相同数目的二进制位。这样磁盘密度，内层高于外层。（6）磁盘密度：每英寸所存储的位数。（7）磁道的典型值（5002000），扇区的典型值（10100）。（8）为了在磁盘上存储数据，必须先将磁盘格式化。5、6 磁盘存储器管理磁盘存储器管理（9）扇区的构成：标识符字段：数据字段：（10）扇区（盘块）是信息读写的最小单位。5、6 磁盘存储器管理磁盘存储器管理 p磁盘文件的存储（n个盘面、k个磁道、m个扇区）l先将0盘面、0磁道中的所有扇区(0m-1)装满;l再将1盘面、0磁道中的所有扇区装满。l再将n-1盘面、0磁道中的所有扇区装满。5、6 磁盘存储器管理磁盘存储器管理 先将先将0号柱面装满号柱面装满l先将0盘面、1磁道中的所有扇区(0m-1)装满;l再将1盘面、1磁道中的所有扇区装满。l再将n-1盘面、1磁道中的所有扇区装满。5、6 磁盘存储器管理磁盘存储器管理 再将再将1号柱面装满号柱面装满p磁盘文件的地址分为：柱面号磁盘文件的地址分为：柱面号 磁头号（盘面号）磁头号（盘面号）扇区号扇区号u假定一个磁盘组共有100个柱面，每个柱面上有8个磁道，每个磁道被划分成8个扇区。现有一个含有6400个逻辑记录的文件，逻辑记录的大小与扇区大小一致，该文件以顺序结构的形式被存放到磁盘上。柱面、磁道、扇区的编号均从0开始，文件的信息从0柱面、0磁头、0扇区开始存放，试问：（1）该文件的第3680个逻辑记录应存放在哪个柱面的第几磁头的第几个扇区。（2）第78柱面的第6磁头的第6扇区中存放了该文件的第几个逻辑记录。补充习题：磁盘文件的存储补充习题：磁盘文件的存储3、磁盘访问时间：磁盘工作时，以恒定速率旋转。为了读或写，磁头必须能移动到所要求的磁道上，并等待所要求的扇区的开始位置旋转到磁头下，然后再开始读或写数据。访问时间可分为三部分：（1）寻道时间TS：把磁臂（磁头）移动到指定磁道上所经历的时间。（2）旋转延迟时间：指定扇区移动到磁头下面所经历的时间。（3）传输时间：把数据从磁盘读出或向磁盘写入数据所经历的时间。5、6 磁盘存储器管理磁盘存储器管理 v寻道时间和旋转延迟时间基本上都与所读/写数据的多少无关，而且它通常占据了访问时间中的大头。适当地集中数据进行传输，将有利于提高传输效率。5、6 磁盘存储器管理磁盘存储器管理 q磁盘调度1、磁盘是供多个进程共享的设备，当有多个进程都要求访问磁盘时，应采用一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。2、磁盘调度分为：移臂调度和旋转调度。3、移臂调度的目的是为了减少寻道时间。旋转调度的目的是为了减少延迟时间。4、四种移臂调度算法：5、6 磁盘存储器管理磁盘存储器管理（1）先来先服务FCFS：算法不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。优点：公平、简单，且每个进程的请求都能依次地得到处理。不会出现某进程的请求长期得不到满足的情况。缺点：未对寻道进行优化，使平均寻道时间可能较长。5、6 磁盘存储器管理磁盘存储器管理举例：现读写磁头正在53号柱面上执行输入输出操作，而等待访问者依次要访问的柱面为98,183,37,122,14,124,65,67.所有的请求访问完，总共移动多少个柱面？5、6 磁盘存储器管理磁盘存储器管理0 14 37 53 65 67 98 122 124 183总移动640个柱面。（2）最短寻道时间优先SSTF该算法选择：其要求访问的磁道，与当前磁头所在的磁道距离最近。优点：获得较好的寻道性能缺点：不能保证平均寻道时间最短，进程饥饿即某进程的请求长期无法得到保证。5、6 磁盘存储器管理磁盘存储器管理举例：现读写磁头正在53号柱面上执行输入输出操作，而等待访问者依次要访问的柱面为98,183,37,122,14,124,65,67.所有的请求访问完，总共移动多少个柱面？5、6 磁盘存储器管理磁盘存储器管理0 14 37 53 65 67 98 122 124 183总移动236个柱面。（3）扫描(SCAN)算法：又称为电梯调度算法考虑两个条件必须同时满足：A、与磁头当前的移动方向一致；B、离当前磁头距离最近者。才对这个请求访问。优点：避免进程饥饿。缺点：延迟进程的请求。举例：现读写磁头正在53号柱面上执行输入输出操作，而等待访问者依次要访问的柱面为98,183,37,122,14,124,65,67.所有的请求访问完，总共移动多少个柱面？5、6 磁盘存储器管理磁盘存储器管理(1)由里向外移：总共移动由里向外移：总共移动208个柱面个柱面0 14 37 53 65 67 98 122 124 183(2)由外向里移：总共移动299个柱面0 14 37 53 65 67 98 122 124 1835、6 磁盘存储器管理磁盘存储器管理（4）循环扫描CSCAN算法：规定磁头单向移动。即若方向为自里向外移动，磁头移动到最大的访问磁道并访问它后，磁头立即返回到访问磁道号最小的磁道。举例：现读写磁头正在53号柱面上执行输入输出操作，而等待访问者依次要访问的柱面为98,183,37,122,14,124,65,67.所有的请求访问完，总共移动多少个柱面？5、6 磁盘存储器管理磁盘存储器管理5、6 磁盘存储器管理磁盘存储器管理q磁盘高速缓存(Disk Cache)：磁盘的I/O速度远低于对内存的访问速度，人们千方百计地去提高磁盘I/O的速度，其中最主要的技术，便是采用磁盘高速缓存。1、磁盘高速缓存的形式（1）在内存中开辟一个单独的存储空间来作为磁盘高速缓存，大小固定；5、6 磁盘存储器管理磁盘存储器管理（2）把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘 I/O 时共享。2、数据交付方式：（1）将磁盘高速缓存中的数据传送给请求者进程。（2）处理流程：5、6 磁盘存储器管理磁盘存储器管理进程请求访问某块中的数据要求的数据在磁盘高速缓存？从高速缓存中提取数据先从磁盘中将所需的数据读入在不在将数据交给请求者将数据交给请求者将数据送高速缓存返回5、6 磁盘存储器管理磁盘存储器管理（3）数据交付给请求进程的两种形式：数据交付：直接将高速缓存中的数据，传送到请求者进程的内存工作区。指针交付：将指向高速缓存中某区域的指针，交付给请求者进程。3、置换算法（1）当缓冲区满时，存在置换问题。较常用的置换算法是最近最久未使用算法LRU、最近未使用算法NRU 及最少使用算法LFU等。5、6 磁盘存储器管理磁盘存储器管理（2）除了考虑最近最久未用这一原则，还考虑：访问频率 可预见性 数据的一致性 4、周期性地写回磁盘：避免数据丢失。5、6 磁盘存储器管理磁盘存储器管理q提高磁盘I/O 速度的其它方法1、提前读：为了加快对文件的访问，减少等待。2、延迟写：为了减少I/O启动次数，节省盘空间。3、优化物理块的分布：使磁头的移动距离最小。5、6 磁盘存储器管理磁盘存储器管理例：记录在磁道上的排列方式会影响输入输出操作的时间。某系统对磁盘初始化时把每个盘面分成 8个扇区，今有8个逻辑记录被存放在同一个磁道上供处理程序使用，现在要按顺序读出这8个记录。每次请求从磁盘上读一个记录，然后对读出的记录要花5毫秒的时间处理，磁盘转速为20毫秒/周。现把这8个逻辑记录依次存放在磁道上，如图所示：读一个记录要花2.5毫秒，花5毫秒时间进行处理，处理这8个记录要花费的时间为：5、6 磁盘存储器管理磁盘存储器管理12345876始点 旋转方向13852746始点旋转方向 （a）8*(2.5+5)+7*(6*2.5)=165(ms)（b）8*(2.5+5)=60(ms)5、6 磁盘存储器管理磁盘存储器管理4、虚拟盘：利用内存空间去仿真磁盘，是易失性存储器，无需格式化，可接受所有标准的磁盘操作，都在内存中进行。5、6 磁盘存储器管理磁盘存储器管理1、假定某磁盘共有、假定某磁盘共有200个柱面，编号为个柱面，编号为0199，如果在为访，如果在为访问问143号柱面的请求者服务后，当前正在为请求号柱面的请求者服务后，当前正在为请求125号柱号柱面的请求者服务，同时有若干请求者在等待服务，他们依面的请求者服务，同时有若干请求者在等待服务，他们依次要访问的柱面号为：次要访问的柱面号为：86，147，91，177，94，150，102，175，130，请回答下列问题：，请回答下列问题：（1）分别用先来先服务算法、最短寻找时间优先算法、电）分别用先来先服务算法、最短寻找时间优先算法、电梯调度算法和循环扫描算法来规定实际的服务次序。梯调度算法和循环扫描算法来规定实际的服务次序。（2）按实际服务次序计算上述算法下移动臂需移动的距离。）按实际服务次序计算上述算法下移动臂需移动的距离。补充习题补充习题2、假定某磁盘的旋转速度是每圈、假定某磁盘的旋转速度是每圈20毫秒，格式化时，每个毫秒，格式化时，每个盘面被分成盘面被分成10个扇区，现有个扇区，现有10个逻辑记录存放在同一磁个逻辑记录存放在同一磁道上，安排如下：道上，安排如下：补充习题补充习题扇区号扇区号逻辑记录逻辑记录扇区号扇区号逻辑记录逻辑记录12345ABCDE678910FGHIJ处理程序要顺序处理这些记录，每读出一个记录后，处理程处理程序要顺序处理这些记录，每读出一个记录后，处理程序要花费序要花费4毫秒的时间进行处理，然后再顺序读下一个记毫秒的时间进行处理，然后再顺序读下一个记录并处理，直到处理完这些记录，回答：录并处理，直到处理完这些记录，回答：（1）顺序处理完这）顺序处理完这10个记录总共花费了多少时间？个记录总共花费了多少时间？（2）请给出记录优化分布的方案，使处理程序能在最短时）请给出记录优化分布的方案，使处理程序能在最短时间内处理完这间内处理完这10个记录，并计算优化分布时需要花费的时个记录，并计算优化分布时需要花费的时间。间。补充习题补充习题