操作系统之资源分配与死锁资料.pptVIP

第三章 资源分配与死锁 ;目录;2;3;4;5;6;7;8;9;10;三.磁盘存储器管理;数据的组织和格式：;数据的组织和格式：;2. 磁盘的类型 ; 3) 传输时间Tt 把数据从磁盘读出或向磁盘写入数据所经历的时间。;4.磁盘调度 当有大量磁盘I/O请求时，恰当选择调度顺序，以降低完成这些I/O服务的总时间。 ;（1）先来先服务FCFS(First-Come, First Served) ;假设当前磁道在100号磁道，磁头正向磁道号增加的方向（由外向里）移动。现依次有如下磁盘请求队列：;（3）扫描(SCAN)算法 ：（又称为电梯算法） （1）欲访问磁道与当前磁道的距离； （2）磁头当前的移动方向。;（4） N-Step-SCAN算法 ;（5）FSCAN算法 该算法实质上是N步SCAN算法的简化， 它只将磁盘请求队列分成两个子队列： ① 由当前所有请求磁盘形成的队列，由磁盘调度按SCAN算法进行处理。 ② 在扫描期间，将新出现的所有磁盘I/O请求， 放入另一个等待处理的请求队列。;13;一.死锁的定义;例2. 竞争外部设备。设系统中有打印机、扫描仪各一台，进程A、B的申请如下：; 一组进程中，每个进程都无限等待被该组进程中另一进程所占有的且永远无法释放的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。;产生死锁的原因有两点： (1)竞争资源：为多个进程所共享的资源不够，引起它们对资源的竞争而产生死锁； (2)进程推进顺序不当：在进程运行过程中，请求资源和释放资源的顺序不当，也会产生死锁。 ;1、竞争资源引起的死锁 可剥夺性资源：是指系统中那些已被进程占用但又可被其它进程所抢占的系统资源。 如处理机、内存区等。 非剥夺性资源：是指系统中那些已被进程占用后便不能被其它进程所抢占的系统资源。 如：打印机、扫描仪等。;例. 竞争外部设备。设系统中有打印机、扫描仪各一台，进程A、B的申请如下：;执行顺序1： P1: … Release(S1);Request(S3);… P2: … Release(S2);Request(S1);… P3: … Release(S3);Request(S2);… 执行顺序2： P1: …Request(S3); Release(S1); … P2: …Request(S1); Release(S2); … P3: …Request(S2); Release(S3); …;（1）进程推进顺序合法：如按曲线① 、②和③不会产生“死锁” ;①;二. 产生死锁的必要条件 ; 预防与避免死锁 检测与解除死锁;一.预防死锁;二. 避免死锁;1、系统安全状态 （2）安全状态之例 我们通过一个例子来说明安全性。假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： ;1、系统安全状态 （3） 由安全状态向不安全状态的转换 如果不按照安全顺序分配资源，则系统可能由安全状态进入不安全状态。 例：假定系统有三个进程P1、P2和P3，有12台磁带机。 进程 最大需求量 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 在T0时刻P3又申请了一台磁带机，若将剩余3台中的一台分配给P3 则系统会进入不安全状态。为什么？;2、利用银行家算法避免死锁 ;（1） 银行家算法中的数据结构 ; ③ 分配矩阵Allocation[1..n,1..m] 该矩阵表示系统中每个进程当前已分配到的每类资源数量。 Allocation[i,j]=K，表示进程i当前已分得Rj类资源的数目为K。 ④ 需求矩阵Need[1..n,1..m] 该矩阵表示每个进程尚需的各类资源数。Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 ;当进程Pi提出资源申请Request[i]时，系统执行下列步骤： ⑴ 若Request[i]≤Need[i]