5.4设备分配

5.4设备分配●设备分配中的数据结构●设备分配的策略/应考虑的因素●设备独立性●设备分配程序●SPOOLing技术5.4.1设备分配中的数据结构1.设备控制表DCT(devicecontroltable)2.控制器控制表COCT(controllercontroltable)3.通道控制表CHCT（channelcontroltable）4.系统设备表SDT(systemdevicetable)系统设备表SDT表目1…表目i…设备类设备标识符DCT驱动程序入口设备类型：type设备标识符：deviceid设备状态：等待/不等待忙/闲连接COCT的指针重复执行次数或时间设备队列的队首指针……设备控制表DCT控制器标识符：controllerid控制器状态：忙/闲与控制器连接的CHCT指针控制器队列的队首指针控制器队列的队尾指针通道标识符：channelid通道状态：忙/闲与通道连接的控制器表首址通道队列的队首指针通道队列的队尾指针控制器控制表COCT通道控制表CHCT5.4.2设备分配策略/应考虑的因素1、设备的固有属性：独享分配、共享分配、虚拟分配2、设备分配算法先请求先服务：当有多个进程对同一设备提出I/O请求时，系统根据这些进程发出请求的先后次序将它们排成一个设备请求队列，总是把设备分配给队首的进程。优先级高者优先：当有多个进程对同一设备提出I/O请求时，系统将将设备分配给优先级高者。若优先级相同，则按先请求先服务进行分配。3、设备分配的安全性：防止进程死锁4、设备独立性：是指用户在编制程序时所用的(逻辑)设备与实际使用的(物理)设备无关5.4.3独占设备的分配程序基本的设备分配过程1.分配设备2.分配控制器3.分配通道分配设备物理设备名在SDT找DCT设备状态忙进程插入设备等待队列按算法计算本次分配的安全性安全分配设备进程插入设备等待队列返回yNNY设备类设备标识符DCT驱动程序入口设备类型：type设备标识符：deviceid设备状态：等待/不等待忙/闲指向控制器表的指针重复执行次数或时间设备队列的队首指针分配控制器物理设备分配DCT找COCT控制器状态忙进程插入控制器等待队列分配控制器返回YN设备类型：type设备标识符：deviceid设备状态：等待/不等待忙/闲指向控制器表的指针重复执行次数或时间设备队列的队首指针控制器标识符：controllerid控制器状态：忙/闲与控制器连接的通道表指针控制器队列的队首指针控制器队列的队尾指针分配通道控制器分配COCT找CHCT通道状态忙进程插入通道等待队列分配通道返回YN通道标识符：channelid通道状态：忙/闲与通道连接的控制器表首址通道队列的队首指针通道队列的队尾指针控制器标识符：controllerid控制器状态：忙/闲与控制器连接的通道表指针控制器队列的队首指针控制器队列的队尾指针5.4.3独占设备的分配程序问题（“瓶颈”）进程以物理设备名提出I/O请求采用的是单通路的I/O系统结构设备分配程序的改进增加设备的独立性(进程以逻辑设备名来提出I/O请求)考虑多通路情况5.4.4虚拟设备和SPOOL系统一、虚拟设备的引入1.独占型设备数量有限，许多进程由于申请某些独占设备而被阻塞，而占有独占型设备的进程在占有设备期间不一定一直使用此设备，降低了设备的利用率，影响其它进程的推进速度2.独占型设备的速度一般较慢，进程常需要长时间等待I/O完成数据传输，影响进程自身的推进速度二、虚拟设备是指通过虚拟技术将一台独占设备变换为若干台逻辑设备，供若干个用户进程使用，通常把这种经过虚拟技术处理后的设备称为虚拟设备。5.4.4虚拟设备和SPOOL系统二、虚拟设备技术的实现在独占型设备与进程之间加入一个共享型设备(如高速磁盘)作为过渡。共享型设备的某一区域是由若干设备块构成的，对进程而言相当于真实的设备。进程内存某一区域高速磁盘连续传输独占型设备间断传输5.4.4虚拟设备和SPOOL系统三、输入型虚拟设备的实现对于输入型虚拟设备，数据的流向：独占型设备→共享型设备→进程空间(内存)假定用于输入的独占型设备是读卡机，用于实现虚拟设备的共享型设备是磁盘，则对于进程所发出的资源申请、使用及释放命令，OS需要完成以下工作：进程内存某一区域高速磁盘连续传输独占型设备间断传输5.4.4虚拟设备和SPOOL系统四、输出型虚拟设备的实现对于输出型虚拟设备，数据的流向：进程空间(内存)→共享型设备→独占型设备假定用于输出的独占型设备是打印机，用于实现虚拟设备的共享型设备是磁盘，则对于进程所发出的资源申请、使用及释放命令，OS需要完成以下工作：进程内存某一区域高速磁盘连续传输独占型设备间断传输5.4.4虚拟设备和SPOOL系统五、SPOOL系统SPOOL：SimultaneousPeripheralOperationsOn-Line，联机情况下同时进行的外围设备操作，称为假脱机操作，是对脱机输入输出工作的模拟，是OS中采用的一种将独占设备改造成为共享设备的技术。5.4.4虚拟设备和SPOOL系统SPOOLing技术：在多道程序环境下，用二个程序来模拟外围控制机，分别实现将数据从磁盘传送到低速I/O设备上(输出)或相反(输入)，从而可在主机的直接控制下，实现脱机输入、输出功能，进而实现外围操作与CPU对数据处理的并行。5.4.4虚拟设备和SPOOL系统细箭头：控制流粗箭头：数据流用户进程逻辑设备管理模块磁盘输入井输出井SPOOL井管理程序输入SPOOL进程输出SPOOL进程读卡机打印机SPOOL技术实现原理示意图注：输入SPOOL和输出SPOOL是两个专门负责I/O设备与磁盘间数据传输的进程，独占型设备是分配给输入SPOOL进程和输出SPOOL进程的。5.4.4虚拟设备和SPOOL系统组成：输入井、输出井；输入缓冲区、输出缓冲区；SPOOL输入进程、SPOOL输出进程SPOOLing系统的组成SPOOLSPOOL输入进程输出进程输入缓冲区输出缓冲区输入设备输出设备输入井输出井磁盘内存5.4.4虚拟设备和SPOOL系统共享打印机①当用户进程有打印请求时，SPOOL输出进程首先在输出井中申请一块区域(虚拟设备)，将要打印的数据送入，然后将用户打印请求填入申请的空白请求打印表中，再把该表挂到请求打印队列上。如果还有后续打印请求，重复上述过程。②当打印机空闲时，SPOOL输出进程就可以从请求队列上取下第一张请求打印表，根据要求将打印数据从输出井送到内存缓冲区，由打印机输出。经过这样的循环，就可将请求打印队列中的所有打印要求予以满足。队列为空时，输出进程阻塞自己直到再有打印请求时才被唤醒。5.4.4虚拟设备和SPOOL系统SPOOLing系统的特点提高了I/O速度将独占设备改造为共享设备实现了虚拟设备功能软件设计师试题在OS中，虚拟设备通常采用__设备来提供虚拟设备。A.Spooling技术，利用磁带B.Spooling技术，利用磁盘C.脱机批处理技术，利用磁盘D.通道技术，利用磁带5.5磁盘存储器的管理一、磁盘性能1.磁盘的物理特性①磁盘由若干张圆形盘片组成，每张盘片分为上下两个盘面，两面都涂有磁层，用于记录数据。盘面由下至上从0开始编号，称为盘面号②每个盘面有若干磁道，同一盘面的所有磁道由外向内从0开始编号，称为磁道号；各盘面上序号相同的磁道构成一个柱面，由外向内从0开始编号，称为柱面号图5-23磁盘的结构和布局盘面9盘面8盘面7盘面6盘面5盘面4盘面3盘面2盘面1盘面0轴心读写磁头主杆扇区磁道磁道间隔扇区间隔柱面扇区5.5磁盘存储器的管理1.磁盘的物理特性③每个磁道有若干大小相同的块，称为扇区。扇区容量为2nB，如512B。每个磁道上的扇区从0开始编号，称为扇区号④磁盘的基本存储单元(扇区)的寻址方式为三维地址：柱面号（磁道号）、盘面号、扇区号⑤为方便管理及屏蔽物理细节，OS常使用一维地址(逻辑扇区号)，将磁盘中所有的扇区从0开始编号磁道扇区图5-24磁盘的格式化Gap102031292293FieldGapFieldGapGapFieldGapFieldGap17741515201774151520IDDataIDDataGap1292293FieldGapField1774151520IDDataSectorPhysicalSector0PhysicalSector1PhysicalSector29ByteSynchByteTrack#Head#Sector#Byte1211CRC3SynchByteDataCRC15122600Byte/SectorGap5.5磁盘存储器的管理一、磁盘性能2.磁盘的类型①固定头磁盘：每条磁道上都有一个读/写磁头优点：可以并行读/写，I/O速度快缺点：成本较高，容量受磁头数量限制②移动头磁盘：每一个盘面配一个磁头，磁盘I/O时，必须移动磁头(寻道)优点：结构简单、成本较低、容量不受磁头数量限制而被广泛使用缺点：只能串行读/写，I/O速度相对较慢5.5磁盘存储器的管理一、磁盘性能3.磁盘访问时间磁盘读/写数据的过程①磁盘接收到读/写指令后，磁头从当前磁道移到目标磁道，所需的时间为寻道时间②然后，旋转磁盘，定位数据所在扇区，所需时间为旋转延迟时间③最后，从扇区上读取或向扇区写入数据，所需时间为数据传输时间5.5磁盘存储器的管理一、磁盘性能3.磁盘访问时间访问时间=寻道时间+旋转延迟时间+数据传输时间寻道时间：是影响磁盘数据传输率的重要参数。衡量磁盘的寻道性能时，通常使用平均寻道时间。旋转延迟时间：旋转时间不可改变，由磁盘转速决定。传输时间：取决于数据量和转速，不可改变。5.5磁盘存储器的管理二、磁盘的调度算法目标：使磁盘的平均寻道时间最少。先来先服务算法FCFS最短寻道时间优先算法SSTF扫描算法Scan循环扫描算法CScan二、磁盘的调度算法1.先来先服务算法FCFS特点：简单、较合理，但未对寻道进行优化。①磁头移动频繁，时间开销大，影响效率，易使磁臂疲劳，磁盘很容易损坏②只适合于负载很轻的系统即请求磁盘I/O的进程数目较少二、磁盘的调度算法2.最短寻道时间优先算法SSTF缺点①饥饿现象：中间磁道的访问优于边缘磁道②并不一定总会使磁头移动次数最少优点：比FCFS的吞吐量高二、磁盘的调度算法3.扫描算法Scan（电梯调度算法）假定开始时磁头处于最外磁道并向内磁道方向移动。在磁头移动过程中，如果经过的磁道有访问请求，则为其服务，然后判断当前磁道以内的磁道是否还有访问请求有，则磁头继续向内磁道方向移动无，判断当前磁头以外的磁道是否有访问请求有，则磁头掉转方向朝外移动无，则停止不动二、磁盘的调度算法3.扫描算法Scan缺点：两侧磁道被访问的频率仍低于中间磁道。优点：能防止饥饿现象；效率很高。二、磁盘的调度算法4.循环扫描算法CScan当磁臂向内移动时，它对本次移动开始前到达的各访问要求自外向内依次给予服务，直到对最内柱面的访问要求满足后，磁臂直接向外移动使磁头停在所有新的访问要求的最外面的柱面上，然后再重复扫描。二、磁盘的调度算法4.循环扫描算法CScan特点：减少了Scan算法的服务延迟。作业设某磁盘有200个柱面，编号为0，1，2，…，199，磁头刚从140道移到143道完成了读写。若某时刻有9个磁盘请求分别对如下各道进行读写：86，147，91，177，94，150，102，175，130。请分别求FCFS、SSTF及SCAN磁盘调度算法响应请求的次序及磁头移动的总距离。