操作系统设计与实现(第三章)

1、操作系统设计与实现第三章 输入/输出系统 操作系统的功能，很大的一部分是花费在I/O设备的控制和管理上，它负责对庞杂的外部设备提供一个通用的简易接口。它对外部设备作了一个分层次的管理，解决了各设备间的交互及各自的输入/输出操作。 每个类型的操作系统都是在对I/O的管理基础上搭建起来的。*发展历史第一代用键盘和打印机第二代用鼠标和调制解调器（俗称“猫”） 第三代用手写笔和扫描仪等另外，还有众多的专业领域的设备。*外部设备分类1.按使用特性分 存储型设备 输入型设备（外设主机） 输出型设备（主机外设） 输入输出型设备2.按数据组织分 块设备 以数据块为单位存储、传输信息 字符设备 以字符为单位存储

2、、传输信息3.按外部设备的从属关系分 系统设备 指操作系统生成时，登记在系统中的标准设备 （如终端、打印机、磁盘机等） 用户设备 指在系统生成时，未登记在系统中的非标准设备。对于这类设备的处理程序由用户提供，并将其纳入系统，由系统代替用户实施管理。 （如A/D，D/A转换器，CAD所用专用设备）4. 按资源分配角度分 独占设备 在一段时间内只能有一个进程使用的设备，一般为低速I/O设备。（如打印机，磁带等） 共享设备 在一段时间内可有多个进程共同使用的设备，多个进程以交叉的方式来使用设备，其资源利用率高。（如硬盘）虚设备 在一类设备上模拟另一类设备，常用共享设备模拟独占设备，用高速设备模拟低速

3、设备，被模拟的设备称为虚设备 （将慢速的独占设备改造成多个用户可共享的设备，提高设备的利用率）（为了提高资源利用率，如SPOOLing技术就使用了虚设备技术用硬盘模拟输入输出设备。） SPOOLing技术 为解决独立设备数量少，速度慢，不能满足众多进程的要求，而且在进程独占设备期间，设备利用率比较低而提出的一种设备管理技术。5.从程序使用角度分 逻辑设备 物理设备* 设备管理的目的和任务1. 按照用户的请求，控制设备的各种操作，完成I/O设备与内存之间的数据交换（包括设备分配与回收；设备驱动程序；设备中断处理；缓冲区管理），最终完成用户的I/O请求(1) 选择和分配I/O设备，以便进行数据传输

4、操作(2) 控制I/O设备与内存之间交换数据2.向用户提供使用外部设备的方便接口，使用户摆脱繁琐的编程负担 方便性 友好界面 透明性3.充分利用各种技术（通道，中断，缓冲等）提高CPU与设备、设备与设备之间的并行工作能力，充分利用资源，提高资源利用率 并行性 均衡性（使设备充分忙碌）*I/O管理的重要性1. 没有I/O设备的计算机就像一个没有轮子的汽车2. I/O性能经常成为系统性能的瓶颈 (1)CPU性能不等于系统性能，响应时间也是一个重要因素 (2)CPU性能越高，与I/O差距越大； 弥补：更多的进程 (3)进程切换多，系统开销大；3. 操作系统庞大复杂的原因之一是：资源多、杂，并发，均来

5、自I/O4 . 理解I/O的工作过程与结构是理解操作系统的工作过程与结构的关键。4. 保证在多道程序环境下，当多个进程竞争使用设备时，按一定策略分配和管理各种设备，使系统能有条不紊的工作5. 与设备无关性（设备独立性） 用户在编制程序时，使用逻辑设备名，由系统实现从逻辑设备到物理设备（实际设备）的转换 用户能独立于具体物理设备而方便的使用设备 用户申请使用设备时，只需要指定设备类型，而无须指定具体物理设备，系统根据当前的请求，及设备分配的情况，在相同类别设备中，选择一个空闲设备，并将其分配给一个申请进程 统一性： 对不同的设备采取统一的操作方式，在用户程序中使用的是逻辑设备优点： 设备忙碌或设

6、备故障时，用户不必修改程序改善了系统的可适应性和可扩展性*设备管理的任务按用户需求提出的要求接入外部设备，系统按一定算法分配和管理控制，而用户不必关心设备的实际地址和控制指令.尽量提高输入输出设备的利用率，例如，发挥主机与外设以及外设与外设之间的真正并行工作能力.*设备管理的功能 设备分配与回收 记录设备的状态 根据用户的请求和设备的类型，采用一定的分配算法，选择一条数据通路 分配设备：按设备的不同类型和操作系统选用的算法分配。包括分配相应的通道、设备控制器以及对未分配到的任务或怍业进行排队等；控制和实现真正的输入输出操作。包括通道程序控制、启动设备、及时响应及处理中断讯号等；对输入输出缓冲区

7、进行管理。例如逻辑名的管理，多个缓冲区的分时以及串并行操作，同类多个外部设备的均衡工作，避免“忙的忙”和“闲的闲”；在一些较大系统中实现虚拟设备技术（虚拟硬盘、虚拟内存）。3.1 I/O硬件原理 I/O设备对不同的人有不同的理解，设计硬件的人员和对硬件编程的人员以及用户都有不同的观点和见解，我们主要分析如何对这些设备编程控制，更好地使设备之间协调工作，即主要从程序员的角度来分析它。3.1.1 I/O设备 对于Linux/UNIX来说，I/O设备主要分为两类：块设备（block device）和字符(character device)设备。 块设备将信息存放在可寻址的固定大小的数据块中，数据块大

8、小的范围常从512字节到32768字节。特征：能够独立地读写单个数据块 - (涉及到了寻址操作) 字符设备可以接受或发送字符流，主要的设备有打印机、调制解调器等设备。这是种不合理的分法，比如 时钟 无法寻址也无法发送接收字符流，但它可以把控制不同I/O设备的操作系统软件成分隔离开来。 如文件系统主要负责磁盘相关的块设备。3.1.2 设备控制器 I/O设备一般由机械和电子两部分组成。把这两部分分开处理，以提供更加模块化，更加通用的设计： * 机械部分是设备本身； * 电子部分叫做设备控制器或适配器。 在小型和微型机中，它常采用印刷电路卡插入计算机中。 控制器卡上通常有一个插座，通过电缆与设备相连

9、； 控制器和设备之间的接口是一个标准接口，它符合ANSI、IEEE或ISO这样的国际标准。 关注点：对该硬件如何进行程序设计，不考虑设备内部如何工作 程序员：软件接口 即硬件所接受的命令，它所完成的功能，出错信息等。 因此我们所关心的就是控制器，因为它和操作系统打交道，也就是我们要分析的重点。*设备接口 一次完整的I/O传送过程，是由一系列信号组成，这些信号启动设备所执行的操作，并通过测试设备状态来监控设备操作的进展 。 一个I/O过程由四步组成： * 准备 * 启动 * 测试和等待 * 结果检查和错误处理 这个过程均是通过对设备接口寄存器组的读写来完成* 设备连接模式 指I/O设备与CPU之

10、间的连接方式，亦即将设备连接到一个计算机系统上的方式。在一个确定的连接模式下，从I/O设备到CPU间的所有连接成分构成了一条I/O路径（I/O链）。1.设备与主机间最基本的连接方式 四个要素： 设备接口形式 I/O指令形式 I/O地址空间分配及译码 连线问题CPU内存(1)设备接口形式 * 端口地址译码 * 按照主机与设备的约定格式和过程接受或发送数据和信号 计算机 设备 设备 计算机 * 将计算机的数字信号转换为机械部分能识别的模拟信号，或反过来 (2) I/O指令形式与I/O地址是相互关联的，主要有两种形式： 内存映像I/O模式 I/O专用指令要考虑的几个问题：设备完成技术：系统如何知道设

11、备的一次I/O操作是否完成？对CPU编程的I/O技术：CPU必须亲自完成I/O的启动与完成的处理，亲自执行所有数据在内存和设备之间的实际物理传送进一步改善：*使CPU利用率尽可能不被I/O降低，使CPU脱离I/O的负担* 提高I/O本身的绝对速度* 减少或缓解速度差距* 使CPU不等待I/O* 使CPU尽可能摆脱I/O* 提高设备利用率* 在设备与主机的硬连接上，引入总线，节省连线并提供配置扩充与改变时的灵活性；引入控制器，扩大设备与主机间的相互适用范围- 总线的引入2.总线 将计算机系统中的各个子系统（CPU、内存、外设等）相互连接，且连接是共享的。 好处：低成本（一线多用） 灵活性（易于增

12、加设备 便于两个计算机系统之间共享外设）总线的缺点： 本身形成了通讯瓶颈，限制I/O吞吐量总线分类： 数据总线、地址总线、控制总线控制器，即设备的电子部分,完成设备与主机间的连接和通讯CPU与控制器间通讯： 单总线模型（微机、小型机） 多总线模型（中、大型机）-I/O通道控制器与设备的接口是一种低层次的接口：*比如从硬盘读信息，读出的是一个比特流，其中包括磁盘数据、扇区大小、校验码等信息，读出来后由控制器对这些串行的比特流进行转换，并进行校验，最后装入主存。*对显示器的显示，由CRT终端控制器从内存中读出要显示的字符的字节流，然后产生来调制产生射线的信号，并最终将结果显示出来。控制器与CPU的

13、联系每个控制器都有一些用来和CPU通信的寄存器，如果把这些寄存器放入内存，即内存映像I/O(这点在显卡上尤为突出)。每个控制器还可以利用终端来通知CPU他们所承担的任务的开始或结束。即固定设备中断。(如网卡，ISA口的网卡)CPU通过向控制器的寄存器中写入信息来控制这些设备工作。DMA（direct memory access） 数据在内存与I/O设备间的直接成块传送 CPU在开始时向设备发“传送一块”命令，结束时进行相应处理，实际操作由DMA硬件直接完成 DMA需要附加的辅助硬件，且该DMA硬件属于设备的电子部分的功能（由控制器实现）。许多控制器，尤其是块设备控制器都支持DMA。 3.1.3

14、 存储器直接存取例如：对磁盘进行访问 不用DMA时，磁盘如何读：首先，控制器从磁盘驱动器串行地一位一位地读一个块，直到将整块信息放入控制器的内部缓冲区中。其次，它做个校验计算，以核实没有读错误发生。然后控制器产生一个中断。CPU响应中断，控制转给操作系统。当操作系统开始运行时，它重复地从控制器缓冲区中一次一个字节或一个字地读这个磁盘块的信息，并将其送入内存中 采用DMA方式时，允许DMA控制器接管地址线的控制权，直接控制DMA控制器与内存的数据交换。从而使磁盘设备与存储器之间的数据传送不需要CPU介入，因而减轻了CPU负担； 当采用DMA时，除向控制器提供要读数据块的磁盘地址外，还要向控制器提

15、供两个信息：数据块送往内存的起始地址和要传送的字节数。 当DMA硬件控制磁盘与存储器之间进行信息交换时，每当磁盘把一个数据读入控制器的数据缓冲区时，DMA控制器取代CPU，接管地址总线的控制权，并按照DMA控制器中的存储器地址寄存器内容把数据送入相应的内存单元中。然后，DMA硬件自动地把传送字节计数器减1，把存储器地址寄存器加1，DMA控制器对每一个传送的数据重复上述过程，直到传送字节计数器为“0”时，向CPU产生一个中断信号。当操作系统接管CPU控制权时，再无需做块复制的工作了。CPU向控制器发出启动DMA通知和有关参数控制器向内存发出询问请求访问内存（读、写）计数器减1结束否发中断NYDM

16、A的实现流程使用DMA的优点: 通过让控制器进行数据的第一步收集校验，可以缓解设备之间对总线的控制权的争夺，因为，一旦不用DMA这种方式，当开始传输时，总线的控制权必须长时间被此控制器所获得，而长时间的占用会使大量其他任务阻塞；而他们本身也会因为传送和读取的速度的差异，会使本身的结构设计复杂化。通过这种内部的缓冲机制，使得在启动DMA传送前完全不使用总线，而自己本身的设计也就自然简化起来。类共享区域的管理-磁盘块的交叉编址 当数据从控制器被传到内存时，控制器本身也正在读扇区上的信息时，控制器就可以被认为是一个共享的区域，而这时就会出现竞争。此时只能满足一方要求，即要么数据从磁盘到控制器，要么数

17、据从控制器到内存。 如果数据从控制器到内存，而数据仍需要被读取，则必然会发生数据丢失的情况，需要用一些方法来避免-即隔一个数据块读一个（因为硬盘是连续转动的，不可能停止）或几个的方案。 对于a图进行编址，控制器只能做到隔一个块读取一个的速度，则读完全部的信息需要磁盘旋转8周，此时b图只需要2周，对于c图，主要是针对从控制器向内存传数据比从硬盘向控制器传数据慢的情况。未编码单交叉编码双交叉编码有关技术 通道技术： 定义：通道是独立于CPU的专门负责数据输入/输出传输工作的处理机，对外部设备实现统一管理，代替CPU对输入/输出操作进行控制，从而使输入，输出操作可与CPU并行操作。 引入通道的目的：

18、 为了使CPU从I/O事务中解脱出来，同时为了提高CPU与设备，设备与设备之间的并行工作能力。分类1) 字节多路通道 字节多路通道以字节为单位传输信息，它可以分时地执行多个通道程序。当一个通道程序控制某台设备传送一个字节后，通道硬件将控制转去执行另一个通道程序，控制另一台设备传送信息。 主要连接以字节为单位的低速I/O设备。如打印机，终端。 以字节为单位交叉传输，当一台传送一个字节后，立即转去为另一台传送字节。 2)选择通道 选择通道是以成组方式工作的，即每次传送一批数据，故传送速度很高。选择通道在一段时间内只能执行一个通道程序，只允许一台设备进行数据传输。 当这台设备数据传输完成后，再选择与

19、通道连接的另一台设备，执行它的相应的通道程序。 主要连接磁盘，磁带等高速I/O设备。选择通道 3)成组多路通道 它结合了选择通道传送速度高和字节多路通道能进行分时并行操作的优点。它先为一台设备执行一条通道指令，然后自动转接，为另一台设备执行一条通道指令。 主要连接高速设备 这样，对于连接多台磁盘机的数组多路通道，它可以启动它们同时执行移臂定位操作，然后，按序交叉地传输一批批数据。数据多路通道实际上是对通道程序采用多道程序设计的硬件实现。3.2 I/O软件原理 IO软件的基本思想是按分层的思想构成，较低层软件要使较高层软件独立于硬件的特性，较高层软件则要向用户提供一个友好的、清晰的、简单的、功能

20、更强的接口。 3.2.1 I/O软件的目标 在设计IO软件时的一个关键概念是设备独立性。用户在编写使用软盘或硬盘上文件的程序时，无需考虑设备类型和特性。*设备无关性： 与设备独立性密切相关的是统一命名(uniform naming)这一目标。一个文件或一个设备的名字只应是一个简单的字符串或一个整数，不应依赖于设备. 如简单的输入： sort output 此时操作系统能够从各种设备上获得输入，也可以做同样的输出。设备的驱动和设备间的差异性均由操作系统本身来处理。* 错误处理 出错处理是I/O软件的另一个目标。一般来说，数据传输中的错误应尽可能地在接近硬件层上处理。由控制器尽可能地处理它所遇到的

21、问题，如果它真的处理不了，再交给设备的驱动程序，去再进行一次重复操作。如对磁盘的读取。 尽量把错误交给底层的软件来处理，只有底层软件处理不了的时候再交给较高一层的软件来处理。* 异步同步问题 大多数物理I/O是异步传输，即CPU在启动传输后便转向其他工作。如何在系统中实现异步，需要实现阻塞和唤醒机制，操作系统中需要有此模拟，是通过中断来实现的，利用中断来实现阻塞和唤醒，实现符合硬件的异步传输。 *独占与共享 由于一些设备是独占设备(打印机)，有些设备是共享设备(磁盘)，故操作系统需要能够同时处理这些设备。 针对以上目标，通常将I/O软件组织成如下的几个层次，使操作系统能够合理高效地实现上述目标

22、。 1. 中断处理程序（底层）； 2. 设备驱动程序； 3. 与设备无关的操作系统软件； 4. 用户层软件（高层）。3.2.2 中断处理程序 *每个进程在启动一个I/O操作后阻塞； *直到I/O操作完成并产生一个中断； *由操作系统接管CPU后唤醒该进程为止。为了将中断放入底层，需要做一定的隐藏，如进行I/O操作的进程将自己挂起，等到I/O操作完成后进行中断。挂起的方法常见的有：执行信号量的DOWN操作、条件变量的WAIT操作，或者消息的RECEIVE操作。中断发生时，中断处理程序解除进程的阻塞状态。3.2.3 设备驱动程序 与设备密切相关的代码放在设备驱动程序中，每个设备驱动程序处理一种设备

23、类型。 每一个控制器都设有一个或多个设备寄存器，用来存放向设备发送的命令和参数。设备驱动程序负责发出这些命令，并监督它们正确执行。 一般，设备驱动程序的任务是接收来自与设备无关的上层软件的抽象请求，并执行这个请求。 在设备驱动程序的进程发出一条或多条命令后，系统有两种处理方式，多数情况下，执行设备驱动程序的进程必须等待命令完成。 这样，在命令开始执行后，它阻塞自已，直到中断处理时将它解除阻塞为止（此时，一般驱动程序需要等待控制器完成一定的操作，故阻塞自己）。而在其它情况下，命令执行不必延迟就很快完成，所以驱动程序不需要阻塞（如在一些图形卡上滚动屏幕只需要写少许字节到控制器的寄存器中，由于不需要

24、机械运行，所以整个操作能在几微秒内完成。）。 3.2.4 与设备无关的I/O软件 虽然I/O软件中一部分是设备专用的，但大部分软件是与设备无关的。设备驱动程序与设备独立软件之间的确切界限是依赖于具体系统的。 1.独立于设备的软件的基本任务是实现所有设备都需要的功能，并且向用户级软件提供一个统一的接口。 2.如何给文件和设备这样的对象命名是操作系统中的一个主要课题。独立于设备的软件负责把设备的符号名映射到正确的设备驱动上。3.设备保护 系统如何防止无权存取设备的用户存取设备呢？ 对设备文件的rwx进行控制，但一般的系统中都不允许访问。 4.不同的磁盘可以采用不同的扇区尺寸。向较高层软件掩盖这一事

25、实并提供大小统一的块尺寸，这正是设备独立软件的一个任务。它可将若干扇区合成一个逻辑块。这样，较高层的软件只与抽象设备打交道，独立于物理扇区的尺寸而使用等长的逻辑块。 5.缓冲技术 6.设备分配 7.出错处理 3.2.5 用户空间的I/O软件 尽管大部分I/O软件都包含在操作系统中，但仍有一小部分是由与用户程序连接在一起的库过程，甚至完全由运行于核外的程序构成。系统调用，包括I/O系统调用，通常由库过程实现。 这些过程所做的工作只是将系统调用时所用的参数放在合适的位置，由其它的I/O过程实现真正的操作。（1）用户进程层执行输入输出系统调用，对I/O数据进行格式化，为假脱机输入输出作准备；（2）独

26、立于设备的软件实现设备的命名、设备的保护、成块处理、缓冲技术和设备分配；（3）设备驱动程序设置设备寄存器、检查设备的执行状态；（4）中断处理程序负责IO完成时，唤醒设备驱动程序进程，进行中断处理；（5）硬件层实现物理IO的操作。3.3 死锁死锁的现象*死锁的定义： 一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到资源，这种现象称为进程死锁，这一组进程就称为死锁进程。死锁（Deadlock）饥饿（Starvation）*关于死锁的一些结论： 参与死锁的进程最少是两个； （两个以上进程才会出现死锁） 参与死锁的进程至少有两个已经占有资源； 参与死锁的所有进程都在等待

27、资源；注： 如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。3.3.1资源 资源是在任何时刻只能被单个进程使用的对象 可剥夺式资源 不可剥夺式资源 对于打印的过程（可剥夺式资源是存储器，不可剥夺式资源是打印机） 对于任一个资源，它本身必存在一个固定的模式。“被申请被分配被使用被释放”模式。 对于可剥夺式资源： 可以将可能存在死锁的情况避免，比如说直接剥夺它本身已经占有的资源，故，这种潜在威胁是可以在一定程度上获通过某些手段来避免；对于不可剥夺式资源，由于无法在尚未导致失败的情况下剥夺其资源，如果强行剥夺资源，则会使当前的任务出现混乱。而死锁的发生也正是直接与不可剥夺式资源相关，故需要分析处

28、理的是不可剥夺式资源可能导致的潜在死锁。3.3.2 死锁的原理一般来说，死锁时，没有一个进程可以触发那个能够唤醒本集合中另一个进程的时间，所以所有的进程都将永远等待下去。*发生死锁的四个必要条件：1 .互斥使用，每一资源或者已被分配给一个进程，或者空闲；（资源独占）2 .保持和等待，一个进程在申请新的资源的同时保持对原有资源的占有； （只有这样才是动态申请，动态分配）3 .不可强占,资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放；4 .循环等待，即必然有一条由两个或多个进程组成的循环链，链中每个进程都在等待相邻进程占用的资源。 存在一个进程等待队列 P1 , P2 ,

29、, Pn, 其中P1等待P2占有的资源，P2等待P3占有的资源，Pn等待P1占有的资源，形成一个进程等待环路。*死锁模型-有向图a：表示，进程A已经占有了资源R;b：表示进程B在申请资源S;c：表示进程D在获得了资源T后，再申请资源U，而此时进程C也在获得了资源U后，正在申请资源T。*死锁模型-资源图单个或分开执行操作系统不分配资源给B进程，这样就会避免死锁。* 死锁的解决方案1. 产生死锁的例子 申请不同类型资源产生死锁 P1：申请打印机申请扫描仪使用释放打印机释放扫描仪P2：申请扫描仪申请打印机使用释放打印机释放扫描仪申请同类资源产生死锁（如内存） 设有资源R，R有m个分配单位，由n个进程

30、P1,P2,Pn（n m）共享。假设每个进程对R的申请和释放符合下列原则： * 一次只能申请一个单位 * 满足总申请后才能使用 * 使用完后一次性释放申请同类资源产生死锁（如内存）m=2，n=3资源分配不当导致死锁产生* 处理死锁的方法1 .忽略死锁的发生；2 .检测死锁并恢复；3 .谨慎对资源进行动态分配，避免死锁；4 .通过破坏上述四个必要条件来预防死锁的发生。3.3.3 鸵鸟算法 最简单的方法就是鸵鸟算法：把头埋到沙子里，假装根本没有问题发生。对死锁问题的看法：1. 数学家们认为不管花多大代价也要彻底防止死锁的发生 ；2. 工程师们则想要了解死锁发生的频率、系统因各种原因崩溃的频率以及死

31、锁的严重程度。 解决死锁问题通常要花很大代价，而且会给进程带来许多不便的限制。 一般来说，死锁发生的概率是很小的。3.3.4 死锁的检测和恢复 主要监测资源的申请和释放，并根据当前的资源使用情况来判断此时系统中是否存在环路，如果存在，就取消掉其中的一个进程，如果不存在则继续。 或者更简单，不去维护资源，而是去判断进程是否连续阻塞超过了预定的时间，如果有这样的进程，就将它取消。 3.3.5 死锁预防定义： 在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。破坏“互斥使用”条件 对于打印机这类设备，利用假脱机等技术来避免进程之间的资源竞争。破坏“请求和保持”

32、条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。 另一方案，当进程申请时，先释放掉自己的资源再进行申请，当申请成功后再收回刚才自己的资源。问题： 对于第一种方案，资源数目的判断只有在运行时才知道，而且效率无法提高。破坏“循环等待”条件 采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。此时进程A、B分别占有资源i、

33、j，如果死锁，即只有当构成环路时才会有，即A申请j，B申请i，但是如果有了编号，规定了进程申请资源必须按照编号的顺序，则会；ij，不允许A申请；ij，不允许B申请，这样就避免了死锁。死锁预防的方法：3.3.6 死锁避免定义： 在系统运行过程中，对进程发出的每一个资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。安全状态与不安全状态安全状态： 如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。安全序列： 一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所

34、有进程Pj (j i )当前占有资源量之和，系统处于安全状态。 (安全状态一定是没有死锁发生的)安全状态与不安全状态不安全状态:不存在一个安全序列，不安全状态一定导致死锁* 资源轨迹图pqI1I2I3I4ArtI5I6I7I8Bs打印机绘图仪绘图仪打印机 u 两进程均结束Dijkstra（1965）提出了一种能够避免死锁的调度算法，称为银行家算法。它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度。银行家不必为了能在同一时间借给每一个客户满额的贷款而在手头上保存足够的现金。银行家算法银行家算法(单种资源)问题描述：基本思想：在每个资源请求发出时对这个请求进行考察，检查满足这一

35、请求时是否会达到安全状态。如果能达到，那么就满足该请求；如果不能达到，那么就推迟这一请求。为了判断状态是否安全，银行家看他是否有足够的资源来满足某一个客户。如果有，那么这笔贷款被认为是能够收回的，并且最接近最大限额的客户将被检查，依次类推。如果所有的贷款最终都被收回，那么该状态是安全的，最初的请求可以批准。银行家算法银行家算法当进程pi提出资源申请时，系统执行下列步骤：（1）若RequestiNeedi,转（2）； 否则错误返回（2）若RequestiAvailable, 转（3）；否则进程等待(3）假设系统分配了资源，则有：Available:=Available-Requesti;Allo

36、cationi:= Allocationi+Requesti;Needi:=Needi-Requesti若系统新状态是安全的，则分配完成若系统新状态是不安全的，则恢复原状态，进程等待银行家算法为进行安全性检查，定义数据结构：Work: integer;Finish:ARRAY1.n of Boolean;银行家算法安全性检查的步骤：(1) Work:=Available; Finish:=false;(2) 寻找满足条件的i： a.Finishi=false; b.NeediWork;如果不存在，则转(4)银行家算法(3) Work:=Work+Allocationi; Finishi:=tr

37、ue; 转(1)(4) 若对所有i,Finishi=true,则系统处于安全状态，否则处于不安全状态R1R2R3R4A3011B0100C1110D1101E0000R1R2R3R4A1100B0112C3100D0010E2110 E=(6,3,4,2) 总资源 P=(5,3,2,2) 已分配资源 A=(1,0,2,0) 剩余资源多种资源检查一个状态是否安全的算法描述如下：查找右边矩阵中是否有一行，其未被满足的资源数均小于或等于A。如果不存在这样的行，则系统将死锁，因为任何进程都无法运行结束。若找到这样一行，则可以假设它获得所需的资源并运行结束，将该进程标记为结束，并将资源加到向量A上。重复

38、以上两步，直到所有的进程都标记为结束。若能达到这种状态，则初始状态是安全的；或者直到发生死锁，则初始状态是不安全的。【作业：】 已分配的资源最大需求量 A BCABCP10 10753P2200322P3302902P4211222P5002433剩余资源ABC 33 2问题:此状态是否为安全状态，如果 是, 则找出安全序列在此基础上P2 申请（1，0，2）能否分配？为什么？P5 申请（3，3，0）能否分配？为什么？P1 申请（0，2，0）能否分配？为什么？3.4 MINIX 3 中的I/O概述3.4.1 MINIX 3 中的中断处理器和I/O访问 许多设备驱动程序在启动I/O设备后阻塞，等待

39、某种消息到达。这种消息往往由该设备的中断处理器产生。 在MINIX3中，大多数I/O通常是命令设备执行某个操作，然后等待该操作结束。大部分工作由磁盘控制器完成，而需要中断处理器做的工作很少。 有时低层中断处理器需要做更多的事情，如时钟中断处理器。 在MINIX3 中，时钟中断处理器是独特的，因为时钟是唯一运行在内核空间的中断驱动设备。只有当前进程的时间片用完或者定时器到期时才会向时钟任务发送消息。用户空间的设备驱动程序可能需要若干不同层次的I/O访问 1. 驱动程序可能需要访问其正常数据空间以外的内存。如管理RAM盘的内存驱动。 2. 驱动程序可能需要读写I/O端口。如硬盘驱动程序就需要这种访

40、问。 3. 驱动程序可能需要响应可预测中断。比如，硬盘驱动程序向磁盘控制器发送命令，这将导致在需要的操作完成后发生中断。 4. 驱动程序可能需要响应不可预测中断，键盘驱动程序属于这一类。3.4.2 MINIX 3 的设备驱动程序 每一类I/O设备都有一个单独的I/O设备驱动程序。这些驱动程序是完整的进程，每个都有其自己的状态、寄存器、堆栈等。 一个简单的设备驱动程序放在一个单独的源文件里。对于RAM盘、硬盘、软盘都各自有一个源文件来支持每种类型的设备，而支持所有块设备类型的通用例程则放在drive.c和drvlib.c中。 对于磁盘和终端这样的设备组，不仅有源文件，同时还有头文件。Drive.h支持所有的块设备驱动程序，tty.h提供对所有串口设备的通用定义。 MINIX3的设计原则是将完全独立的用户空间的进程来运行操作系统的组件。这种设计原则是高度模块化和相当有效率的。这也是MINIX3和UNIX在本质上的少数区别之一。 在MINIX3中，进程通过向文件系统进程发送消息来读取一个文件，而文件系统则向磁盘驱动程序发送一条消息来