第五章 设备管理.

Presentation on theme: "第五章 设备管理."— Presentation transcript:

1 第五章 设备管理

2 内容 （1）I/O组成； （2）I/O控制； 指I/O完成的方法。 （3）I/O缓冲； （4）I/O分配； （5）I/O处理。

3 5.1 I/O系统 5.1.1 I/O设备 一、类型 （1）按速度分： 中：打印机 高：磁盘。 （2）按信息交换单位分： 字符：打印机、串口
低：键盘 中：打印机 高：磁盘。 （2）按信息交换单位分： 块：磁盘,可定位 字符：打印机、串口

4 5.1 I/O系统 5.1.1 I/O设备 一、类型 （3）按设备的共享属性分： 独占：如临界资源 共享：磁盘
虚拟：如本身因有属性为独占，但将其虚拟为几个逻辑设备。

5 二、设备与控制器之间的接口：(图5.1) CPU―――控制器―――设备 三种信号： （1）数据信号：——双向，有缓存
（2）控制信号：控制器发给设备；要求其完成相关操作 （3）状态信号：设备发给控制器，后者“显示”；

6 5.1.2 设备控制器 一、功能：接收CPU命令，控制I/O设备工作，解放CPU. 1.接收和识别命令。
设备控制器 一、功能：接收CPU命令，控制I/O设备工作，解放CPU. 1.接收和识别命令。 应有相应的Register来存放命令（“命令寄存器”） 2.数据交换 CPU——控制器的数据寄存器——设备 3.设备状态的了解和报告 设备控制器中应用“状态寄存器” 4.地址识别 CPU通过“地址”与设备通信，设备控制器应能识别它所控制的设备地址以及其各寄存器的地址。

7 5.1.2 设备控制器 一、功能：接收CPU命令，控制I/O设备工作，解放CPU， 5.数据缓冲 6.差错控制 二、组成（图5.2）
设备控制器 一、功能：接收CPU命令，控制I/O设备工作，解放CPU， 5.数据缓冲 6.差错控制 二、组成（图5.2） 各类寄存器：数据、命令、状态 信号线：数据线(独立寻址、内存寻址)、地址线、控制线 I/O逻辑：在其控制下完成与CPU、设备的通信。

8 5.1.3 I/O通道 一、引入 通道 一种特殊的执行I/O指令的处理机，与CPU共享内存，可以有自己的总线。 引入目的
解脱CPU对I/O的组织、管理。 CPU只需发送I/O命令给通道，通道通过调用内存中的相应通道程序完成任务。

9 5.1.3 I/O通道 二、类型 1.字节多路通道：（图5-3） 各子通道以时间片轮转方式共享通道，适用于低、中速设备。 2.数组选择通道：
无子通道，仅一主通道，某时间由某设备独占，适于高速设备。 但通道未共享，利用率低。 3.数组多路通道： 在图5-3中，多子通道不是以时间片方式，而是“按需分配”，综合了前面2种通道类型的优点。

10 I/O通道 三、通道“瓶颈”问题： 解决：采用复联方式 图5.4

11 5.1.4 总线系统 微机I/O系统 设备控制器：与设备是一对多的关系，系统是通过它与设备通信 系统―――设备控制器――― 设备
总线系统 微机I/O系统 设备控制器：与设备是一对多的关系，系统是通过它与设备通信 系统―――设备控制器――― 设备 如：磁盘设备，打印设备 缺点：总线瓶颈，CPU瓶颈。

12 5.1.4 总线系统 二、主机I/O系统（四级结构） 计算机―――I/O通道―――I/O控制器―――设备
总线系统 二、主机I/O系统（四级结构） 计算机―――I/O通道―――I/O控制器―――设备 I/O通道相当于对总线的扩展，即多总线方式，且通道有一定的智能性，能与CPU并行，解决其负担。 ISA/EISA/LocalBUS/VESA/PCI

13 5.2 I/O控制方式 四个阶段： 程序I/O——中断I/O——DMA控制——通道控制。 趋势：提高并行度。

14 5.2.1 程序I/O（忙—等待方式） 查询方式：CPU需花代价不断查询I/O状态（图5-7a） CPU资源浪费极大。
例：99.9ms+0.1ms=100ms 在5.2.1中99.9在忙等

15 5.2.2 中断I/O 向I/O发命令——返回——执行其它任务。 I/O中断产生——CPU转相应中断处理程序。
如：读数据，读完后以中断方式通知CPU，CPU完成数据从I/O——内存

16 5.2.3 DMA方式——用于块设备中 一、引入 中断I/O，CPU“字节”干预一次，即每“字节”传送产生一次中断。
DMA：由DMA控制器直接控制总线传递数据块。DMA控制器完成从I/O——内存。 图5.7c 二、组成 一组寄存器+控制逻辑。图5.8 CR（命令/状态）; DR（数据）; MAR（内存地址）; DC（计数） DMA工作过程（例）：

17 Direct Memory Access

18

19 DMA

20 DMA

21 DMA

22 5.2.4 I/O通道控制方式 DMA方式：对需多离散块的读取仍需要多次中断。 通道方式：CPU只需给出 （1）通道程序首址。
后，通道程序就可完成一组块操作 操作 P Record 计数 内存地址 Write 80 813 140 1034 1 60 5830 300 2000 250 1850 720

23 5.3 缓冲管理 目的：组织管理、分配、释放buffer 5.3.1 引入 1.缓和CPU和I/O设备间速度不匹配的矛盾。
5.3 缓冲管理 目的：组织管理、分配、释放buffer 引入 1.缓和CPU和I/O设备间速度不匹配的矛盾。 如：计算——打印buffer——打印 2.减少对CPU的中断频率 如：buffer越大，“buffer满”信号发生频率越低。 3.提高CPU和I/O并行性

24 5.3 缓冲管理 5.3.2 单缓冲 由于C和T可并行，M和C或M和T不能并行，因此处理一块数据时间：Max(C,T)+M
5.3 缓冲管理 单缓冲 由于C和T可并行，M和C或M和T不能并行，因此处理一块数据时间：Max(C,T)+M 用户进程何时阻塞？

25 5.3 缓冲管理 5.3.2双缓冲 效率有所提高，且进一步平滑了传输峰值。 系统处理一块数据的时间约为：MAX(C,T)
5.3 缓冲管理 5.3.2双缓冲 效率有所提高，且进一步平滑了传输峰值。 系统处理一块数据的时间约为：MAX(C,T) 收发可双向同时传送。（图5－13）

26 5.3 缓冲管理 循环多缓冲 类型： R:空缓冲；G：满缓冲；C：当前缓冲

27 循环多缓冲的使用 nextg：指示下一个应取数据的buf nexti：指示下一个空buf. Getbuf：
取nextg对应缓冲区提供使用，将Nextg置为空，Nextg=（Nextg+1）Mod N 将Nexti对应缓冲区提供使用，将Nexti置为满，Nexti=（Nexti+1）Mod N Releasebuf: 若C满，则改为G； 若C空，则改为R；

28 循环多缓冲的同步问题 Nexti 追上Nextg： 表示输入速度>输出速度，全部buf满，这时输入进程阻塞 Nextg追上Nexti：

29 5.3.4 缓冲池 缓冲池：系统提供的公用缓冲 一、组成： 3个队列： 空缓冲队列emq 输入队列inq 输出队列outq 四个工作缓冲区：
缓冲池 缓冲池：系统提供的公用缓冲 一、组成： 3个队列： 空缓冲队列emq 输入队列inq 输出队列outq 四个工作缓冲区： hin：收容输入数据 sin：提取输入数据 hout：收容输出数据 sout：提取输出数据

30 二、4种工作方式 1.收容输入；2.提取输入 3.收容输出；4.提取输出

31 5.3 缓冲管理 1.hin=getbuf(emq); putbuf(inq,hin)
5.3 缓冲管理 1.hin=getbuf(emq); putbuf(inq,hin) 2.sin=getbuf(inq); 计算； putbuf(emq,sin) 3.hout=getbuf(emq); putbuf(outq, hout) 4.sout=getbuf(outq);输出；putbuf(emq,sout)

32 三、Getbuf和Putbuf过程 Putbuf(type) Getbuf(type) Begin Begin
wait(MS(type)); addbuf(type,number); signal(MS(type)); signal(RS(type)); end Getbuf(type) Begin wait(RS(type)); wait(MS(type)); B(number):=takebuf(type); signal(MS(type)); end

33 5.4 设备分配 包括：对设备、设备控制器、通道的分配 5.4.1 数据结构 一、设备控制表DCT：
5.4 设备分配 包括：对设备、设备控制器、通道的分配 数据结构 一、设备控制表DCT： 二、控制器控制表（COCT），通道表（CHCT），系统设备表（SDT），图5-17 SDT:记录了系统中全部设备及其驱动程序地址。

34 设备控制表DCT DCT1 DCT2 DCTn 设备类型type 设备标识符:deviceid 设备状态：等/不等 忙/闲
指向控制器表的指针 重复执行次数或时间 设备队列的对首指针 DCT1 DCT2 DCTn

35 设备分配应考虑的若干因素 一、设备的固有属性： 共享+虚拟：注意调度的合理性； 独享：排它性分配，控制不好可能死锁。 二、分配算法： （1）FIFO； （2）优先权。

36 5.4.2 设备分配应考虑的若干因素 三、安全性： 安全分配(同步)：每进程获得一I/O后，即block，直到其I/O完成。
设备分配应考虑的若干因素 三、安全性： 安全分配(同步)：每进程获得一I/O后，即block，直到其I/O完成。 即打破了死锁条件。 缺点：CPU、I/O对该进程是串行，进程进展缓慢。 不安全分配（异步）：需进行安全性检查，进程执行效率高。

37 5.4.3 设备独立性 一、概念： 即设备无关性，指应用程序独立于具体使用的物理设备。 逻辑设备 物理设备 逻辑设备表（LUT）： 逻辑设备
设备独立性 一、概念： 即设备无关性，指应用程序独立于具体使用的物理设备。 逻辑设备 物理设备 逻辑设备表（LUT）： 逻辑设备 物理设备 Driver入口

38 5.4.3 设备独立性 分配流程：进程给出逻辑名——通过LUT得到物理设备及其driver入口。 优点： 设备分配更灵活；
设备独立性 分配流程：进程给出逻辑名——通过LUT得到物理设备及其driver入口。 优点： 设备分配更灵活； 逻辑设备和物理设备间可以是多——多的映射关系。提高了物理设备的共享性，以及使用的灵活性。如： 某逻辑名可对应这一类设备，提高均衡性与容错性。 几个逻辑名可对应某一个设备，提高共享性。

39 5.4.3 设备独立性 易于实现I/O重定向。 不变程序，只需改变LUT表的映射关系。 二、设备独立性软件 执行所有设备的公有操作
设备独立性 易于实现I/O重定向。 不变程序，只需改变LUT表的映射关系。 二、设备独立性软件 执行所有设备的公有操作 分配回收 名字映射 保护 缓冲 差错控制 向用户层软件提供统一接口 read、write

40 Struct general_op{ int (*read)(…) int (*write)(…) }; driver1: Struct general_op dev_op={ dev1_read, dev1_write }; driver2: Struct general_op dev_op={ dev2_read, dev2_write Gen_read(fd,…) { dev_op=map(fd); dev_op->read(…); }

41 5.4.3 设备独立性 三.名字映射 LUT的生成 LUT的配置 （1）整个系统一张LUT表： 要求：逻辑名不重复，（一般用于单用户系统）
设备独立性 三.名字映射 LUT的生成 在用户进程第一次请求设备时完成映射并在LUT中生成相应项 LUT的配置 （1）整个系统一张LUT表： 要求：逻辑名不重复，（一般用于单用户系统） （2）每个用户一张LUT表。 可重名/可限制用户对某些设备的使用。 逻辑设备 物理设备 Driver入口

42 5.4.4 独占设备分配程序 进程n请求设备： begin search (sdt, phdevice)
独占设备分配程序 进程n请求设备： begin search (sdt, phdevice) if not busy (phdevice) then compute(safe)——对独占设备 if safe then alloc (n, phdevice); else begin insert (DL(phdevice), n);-----将n插入设备等待队列DL上 return end;

43 设备忙—else begin; insert (DL (phdevice), n); return; end; controllerid=controllerid (COCT ptr(dct)); ――device分配成功 if not busy (COCT (controllerid)) then alloc (n, controllerid); else begin insert (col, n); channeled=channeled(chatptr (controllerid)); ――控制器分配成功

44 if not busy (chct (channelid)) then
allocation (n, channelid); else begin insert (chl, n) return; end; 优化： 1）增加设备的独立性 2）考虑多通路情况

45 SPOOLING技术 1概念 假脱机技术，在联机情况下同时出现外围操作 作用：通过缓冲方式，将独占设备改造为共享设备

46 2、spooling组成： 1.输入＃和输出＃： 在磁盘上开辟的2个大存储空间，模拟输入和输出设备。 2.输入buf和输出buf（内存中）
3.输入Spi和输出SPo进程。 分别控制（1），（2）的动作。 SPi相当于脱机输入控制器。 SPo相当于脱机输出控制器。

47 3例 (1)输入 a.进程n请求――> SPi为n在输入＃中分配空间——>设备数据由输入buf送输入#——>生成输入请求表挂输入请求队列。 b.CPU空——取请求表中的任务,送进程缓冲区。 （2）输出：（打印） a.进程n请求——>SPo为n在输出#中分配空间——>将数据由进程buf转到输出#——>生成一打印请求表挂打印请求队列。 b.打印机空——>查打印请求表中的任务——> 取输出＃中对于数据——>输出buf ——>打印

48 4特点 1.提高I/O速度： 对低速设备操作——>变为对输入/出#操作。 2.将独占设备改造为共享设备 分配设备的实质时分配输入/出#
3.实现了虚拟设备功能

49 5.5设备处理 设备处理程序即是设备驱动程序。 设备驱动程序的功能和特点 设备驱动程序的处理过程

50 设备驱动程序的功能和特点 功能： 接收进程的I/O命令 检查命令合法性 检查设备状态 设置设备工作方式 驱动I/O操作 响应设备中断
构成通道程序

51 设备驱动程序的功能和特点 特点： 和硬件紧密相关、各个设备有自己的设备驱动

52 5.5.2设备驱动程序处理过程 包括 启动过程 中断处理过程 将抽象要求转化为具体要求 检查I/O请求合法性 读出和检查设备状态
传送必要的参数 设置工作方式 启动I/O设备

53 5.5.3中断处理程序 流程 设备启动－>I/O完成－>发送中断－>CPU调用中断处理过程 中断处理过程
唤醒被阻塞的驱动程序进程 保护被中断进程环境 转入相应的设备处理程序 中断处理(特性) 恢复被中断进程的现场

54 5.6磁盘存储器管理 5.6.1 磁盘性能简述 一、数据组织和格式（图5－22） 磁道——扇区——字节 二、类型 1.固定头磁盘：
每个磁道上有一个磁头，快 2.移动头磁盘： 每个盘面仅有一个磁头，慢

55 5.6.1 磁盘性能简述 三、磁盘访问时间： 1.寻道时间：TS=m*n+S m：常量，n：磁道数，s：磁盘启动时间。 2.旋转延时间Tr：
指定扇区旋转到磁头下所需时间。 设每秒r转，则Tr＝1/2r（均值） 3.数据传输时间Tt＝b/rN b：读写字节数 N：每道上的字节数 访问时间：Ta=Ts+1/2r+b/rN 可见，由于特定磁盘，只有集中放数据，集中读写（b大）才能更好提高传输效率。

56 例子 寻道时间: 20ms 磁盘通道传输速率: 1MB/s 转速r=3600rpm 每扇区512字节 每磁道32 扇区
目标：读 128k 数据

57 时间比较 60*16k=960k<1MB/s 顺序组织 (20＋8.3＋16.7)＋(8.3＋16.7)×7＝220(ms) 随机组织 (20＋8.3＋0.5)×256＝7373(ms)

58 5.6.2 磁盘调度 目标：减少寻道时间 一、FCFS（Fisrt Come First Second）
特点：简单，寻道时间长，相当于随机访问模式。 二、SSTF（最短寻道优先） 三、扫描算法。 1.进程“饥饿现象” SSTF存在。 2.SCAN算法： 在移动方向固定的情况下采用了SSTF，以避免饥饿现象

59 FCFS调度算法 SSTF调度算法 100道开始 被访问的下一个磁道 移动距离 55 45 58 3 39 19 18 21 90 72
160 70 150 10 38 112 184 146 平均寻道长度：55.3 100道开始 被访问的下一个磁道 移动距离 90 10 58 32 55 3 39 16 38 1 18 20 150 132 160 184 24 平均寻道长度：27.5

60 5.6.2 磁盘调度 四、循环扫描CSCAN（图9-5） 一个方向读完，不是象SCAN那样回头，而是循环。 访问时间：2TT+Smax
五、N—Step—SCAN和FSCAN算法。 1. N—Step—SCAN 粘臂：由于连续对某磁道访问引起的垄断访问，将磁盘请求队列分为长为N的子队列m个，如下图处理。当N=1时，为FCFS。当N时，为SCAN.

61 5.6.2 磁盘调度 2.FSCAN

62 SCAN调度算法 CSCAN调度算法 100道开始，增加方向 被访问的下一个磁道 移动距离 150 50 160 10 184 24 90
94 58 32 55 3 39 16 38 1 18 20 平均寻道长度：27.8 100道开始，增加方向 被访问的下一个磁道 移动距离 150 50 160 10 184 24 18 166 38 20 39 1 55 16 58 3 90 32 平均寻道长度：27.5

63 5.6.3 磁盘高速缓存 形式 逻辑上是磁盘、物理上是驻留在内存中的盘块 固定大小和可变大小 数据交付方式
数据交付指将磁盘高速缓存中的数据传送给请求者进程 步骤：先查缓存、后查磁盘并更新缓存 方式： 数据交付 指针交付

64 5.6.3 磁盘高速缓存 置换算法 最近最久 访问频率 可预见性 数据一致性：将需要一致性的块放在替换队列的头部，优先回写。 周期性回写磁盘
例：ms－dos采用写穿透方式

65 5.6.4 提高磁盘I/O速度的其它方法 提前读 延迟写 访问频率高的磁盘块放在替换队列的尾部，减少回写次数 优化物理块的分布
目的是减小磁头移动距离 簇分配方式：一个簇为多个连续的块 虚拟盘（RAM盘） 和磁盘高速缓存区别：虚拟盘由用户控制；磁盘高速缓存由系统控制。

66 5.6.5 廉价磁盘冗余阵列 并行交叉存取（条化存取） 冗余存取 校验存取 优点 可靠性高 磁盘I/O速度高 性价比高

67 RAID 0 (不冗余）

68 RAID 0

69 RAID 0 不冗余 不校验 分布式存储 低可靠性 低价格 并行 I/O 访问

70 RAID 1 (镜像) 分布存放 镜像冗余 不校验

71 RAID 1 读性能比 RAID 0好 (选择寻道时间小的磁盘访问) 写性能比 RAID 0差 存储开销大 可靠性高

72 RAID 2 (汉明码校验冗余)

73 RAID 3 用一个校验盘

74 RAID 4 (Block-Level Parity)

75 RAID 4 和RADI3相比较，RAID4基于大的块校验

76 RAID 5

77 RAID 5 解决了RAID4校验盘不可靠性问题

78 试验 实现SSTF算法和SCAN算法 要求 给出任意的输入流、计算平均寻道长度。 输入流长度、磁头移动方向可定制。 测试：设有100各磁道，访问序列如下： 23，5，98， 14，66，25，78，34，66，74，56，87，12，39，71，49，58 当前磁头在50道，上次访问的磁道是18道。