操作系统设备管理培训课程

1、1,操作系统 第五章 设备管理,南京大学软件学院 2013,Chap 5.55.9,2,第五章 设备管理,5.1 I/O硬件原理 5.2 I/O软件原理 5.3 具有通道的I/O系统 5.4 缓冲技术 5.5 驱动调度技术 5.6 设备分配 5.7 虚拟设备 5.8 Linux设备管理 5.9 Windows 2003 I/O系统,3,5.5 驱动调度技术(1),5.5.1 存储设备的物理结构 5.5.2 循环排序 5.5.3 优化分布 5.5.4 搜查定位 5.5.5 独立磁盘冗余阵列 5.5.6 提高磁盘I/O速度的一些方法,4,驱动调度技术(2),驱动调度和驱动调度算法。 驱动调度能减少为若干个I/O请求服务所需的总时间，提高系统效率、除了I/O请求的优化排序外，信息在辅助存储器上的排列方式，存储空间分配方法都能影响存取访问速度。,5,5.5.1 存储设备的物理结构(1),顺序存取存储设备是严格依赖信息的物理位置进行定位和读写的存储设备 具有存储容量大、稳定可靠、卷可装卸和便于保存等优点,6,存储设备的物理结构(2) 直接存取存储设备,磁盘是一种直接(随机)存取存储设备。每个物理

2、记录有确定的位置和唯一的地址，存取任何一个物理块所需的时间几乎不依赖于此信息的位置。 访问磁盘记录参数：柱面号、磁头号、扇区号,7,8,9,Moving-head Disk Mechanism,10,磁头,11,多组磁头,12,Disk Performance Parameters,为了读或者写，磁头必须定位于指定的磁道和该磁道中指定的扇区的开始处。磁道选择包括在活动头系统中移动磁头或者在固定头系统中选择一个磁头。 磁头定位到磁道所需要的时间称为寻道时间(seek time)。 在任何一种情况下，一旦选择好磁道，磁盘控制器就开始等待，直到适当的扇区旋转到磁头处。磁头到达扇区开始位置的时间称为旋转延迟(rotational delay)。 寻道时间(如果有的话)和旋转延迟的总和称为存取时间(access time)，这是达到读或者写的位置所需要的时间。 传送所需的时间是传送时间(transfer time)。,13,14,5.5.2循环排序(1),考虑磁道上保存四个物理块的旋转型设备，旋转1周需时20ms，假定收到以下四个I/O请求。 请求次序 记录号 (1) 读记录4 (2) 读记录3

3、 (3) 读记录2 (4) 读记录1,15,循环排序(2) 多种I/O请求排序方法,方法1：按照I/O请求次序读记录4、3、2、1，平均用1/2周定位，再加上1/4周读出记录，总处理时间等于1/2+1/4+33/4=3周，即60毫秒。 方法2：如果次序为读记录1、2、3、4。总处理时间等于1/2+1/4+31/4=1.5周，即30毫秒。 方法3：如果知道当前读位置是记录3，则采用次序为读记录4、1、2、3。总处理时间等于41/41周，即20毫秒。,16,5.5.3 优化分布(1),考虑10个逻辑记录A，B，J被存于旋转型设备上，每道存放10个记录，安排如下： 物理块 逻辑记录 1-10 A-J (A B C D E ) 处理10个记录的总时间 10毫秒(移动到记录A的平均时间)+ 2毫秒(读记录A)+4毫秒(处理记录A)+916毫秒(访问下一记录) +2毫秒(读记录)+4毫秒(处理记录) 214毫秒,17,处理10个记录的总时间 10毫秒(移动到记录A的平均时间)+ 2毫秒(读记录A)+4毫秒(处理记录A)+916毫秒(访问下一记录) +2毫秒(读记录)+4毫秒(处理记录) 214毫秒

4、,18,优化分布(2) 按照下面方式对信息优化分布,物理块 逻辑记录 1 A 2 H 3 E 4 B 5 I 6 F 7 C 8 J 9 G 10 D,19,优化分布(3),处理10个记录的总时间为 10毫秒(移动到记录A的平均时间)+102毫秒(读记录)+4毫秒(处理记录) =70毫秒,20,5.5.4 搜查定位(1),移臂调度有若干策略 (1)先来先服务算法 (FCFS) (2)“电梯调度”算法 (Elevator) (3)“最短查找时间优先”算法(SSTF) (4)“扫描”算法 (SCAN) (5)“分步扫描”算法 (N-steps SCAN) (6)“单向扫描”算法 (C-SCAN) 未来趋势: SSD硬盘(固态硬盘),21,搜查定位(2) 先来先服务算法,磁头臂按照FCFS队列顺序移动，处理队列中的请求，不考虑各I/O请求之间的相对次序和移动臂当前所处位置，进程等待I/O请求的时间会过长，寻道性能较差。 公平,22,搜查定位(3) “电梯调度”算法,23,搜查定位(4) SSTF“最短查找时间优先”算法,本算法考虑了各个请求之间的区别，总是先执行查找时间最短的那个磁盘请求，从

5、而，较“先来先服务”算法有较好的寻道性能。 存在“饥饿”现象。,24,搜查定位(5) “扫描”算法,磁头臂每次沿一个方向移动，扫过所有柱面，遇到最近的I/O请求便进行处理，直到最后一个柱面后，再向相反方向移动回来。 与“电梯调度”算法的不同在于：即使该移动方向暂时没有I/O请求，移动臂也需扫描到头。“最短查找时间优先”算法虽有较好寻道性能，但可能会造成进程“饥饿”，本算法能克服这一缺点。扫描算法偏爱那些最接近里面或靠外面的请求，对最近扫描跨过去的区域的I/O请求的响应会较慢。,25,搜查定位(6) “分步扫描 ”算法,进程重复请求同一磁道会垄断整个设备，造成“磁头臂的粘性”，采用分步扫描可避免这类问题。 将I/O请求分成组，每组不超过N个请求，每次选一个组进行扫描，处理完一组后再选下一组，这种调度算法能保证每个存取请求的等待时间不至太长。 当N很大时，接近于“扫描”算法的性能，当N=1时，接近于“先来先服务”算法的性能。,26,搜查定位(7) “循环扫描”算法,在磁盘请求对柱面的分布是均匀的情况下，当移动臂移动到头并转向时，靠近磁头一端的请求特少，许多请求集中分布在远离磁头的一端，它们

6、的等待时间就会较长，“循环扫描”算法能克服这个缺点，这是为适应不断有大量柱面均匀分布的存取请求进入系统的情况而设计的扫描方式。 移动臂总从0号柱面至最大号柱面顺序扫描，然后，直接返回0号柱面重复进行，归途中不再服务，构成了一个循环。,27,Disk Scheduling (Cont.),Several algorithms exist to schedule the servicing of disk I/O requests. We illustrate them with a request queue (0-199). 98, 183, 37, 122, 14, 124, 65, 67 Head pointer 53,28,FCFS,Illustration shows total head movement of 640 cylinders.,Total=640,29,SSTF,Selects the request with the minimum seek time from the current head position. SSTF scheduling is a f

7、orm of SJF scheduling; may cause starvation of some requests. Illustration shows total head movement of 236 cylinders.,30,SSTF (Cont.),Total=236,31,SCAN (Cont.),Total=208,回到0点,32,C-SCAN,Provides a more uniform wait time than SCAN. The head moves from one end of the disk to the other. servicing requests as it goes. When it reaches the other end, however, it immediately returns to the beginning of the disk, without servicing any requests on the return trip. Treats the cylinders as a circular list

8、that wraps around from the last cylinder to the first one.,33,C-SCAN (Cont.),34,C-LOOK,Version of C-SCAN Arm only goes as far as the last request in each direction, then reverses direction immediately, without first going all the way to the end of the disk.,35,C-LOOK (Cont.),36,7 Linux磁盘调度算法,Linux 2.4磁盘调度采用电梯调度算法。 Linux2.6增加两种新磁盘调度算法：最终期限调度算法和预期调度算法，尽力确保处理期限到达的请求获得响应 。 时限调度算法： 预期调度算法：,37,Linus电梯调度,1)如果新请求与队列中等待请求的数据处于同一磁盘扇区或者直接相邻的扇区，则现有请求和新请求合并成一个请求。 2)如果队列中的请求已经存在很长时间，则新请求将被插入到队列尾部。 3)如果存在合适的位置

9、，则新请求将按顺序插入到队列中；如果没有合适的位置，则新的请求将被插入到队列尾部。,38,Linus电梯调度,电梯调度算法有两个问题， 一是由于队列动态更新的原因，一个相距较远的请求可能会延迟相当长的时间； 二是由于写请求通常是异步的，而读请求大部分是同步操作，这样一来，在写一个大文件时，很可能堵塞一个读请求很长时间，从而堵塞进程。,39,时限调度算法,为了克服这些问题，引入时限调度算法，使用三个队列： 读FIFO队列、写FIFO队列和电梯排序队列。 每个新来请求被放置到电梯排序队列中，该队列与前面所述一致，此外，同样的请求还被放置在FIFO读队列(如果是读请求)或FIF0写队列(如果是写请求)中，这样，读和写队列维护一个按请求发生时间为顺序的请求列表。对每个请求都有一个到期时间，对于读请求默认值为0.5秒，对于写请求默认值为5秒； 通常，调度程序从排序队列中分派服务，当一个请求得到满足时，其将从电梯排序队列头部移走，同时也从对应的FIFO队列移走。 然而，当FIFO队列头部的请求超过其到期时间时，调度程序将从该FIFO队列中派遣任务，取出到期请求，再加上接下来的几个队列中的请求，当然，任一个请求被服务时，其也从电梯排序队列中移出。所以，时限调度算法能克服“饥饿”和读写不一致的问题。,40,预期调度算 法,预期调度是对时限调度的补充，当一个读请求被分派时 ，预期调度程序会将调度程序的执行延迟若干毫秒(取决于配置文件)； 发出上一条读请求的应用程序有机会发出后继读请求，且该请求发生在相同的磁盘区域； 如果没有新请求发生，则调度程序继续使用时限调度算法。,41,未来趋势: SSD硬盘 (solid-state drive)俗称固态硬盘,42,未来趋势: SSD硬盘,43,未来趋势: SSD硬盘,44,Disk Cache,高速缓冲存储器(cache memory)通常指一个容量比主存小且速度比主存块的存储器，这个存储器位于主存

《操作系统设备管理培训课程》由会员luobi****88888分享，可在线阅读，更多相关《操作系统设备管理培训课程》请在金锄头文库上搜索。