资源分配与调度分析课件.ppt

1、12 包含资源的物理名、逻辑名、类型、地址、分配状态等信息。 决定资源应分给谁，何时分配，分配多少等问题。 执行资源分配；资源收回工作。 对资源的存取进行控制并对资源实施安全保护措施。3 系统对作业一级采用资源静态分配方法。 系统在调度作业时，根据作业所需资源进行分配；并在作 业运行完毕 时，收回所分配的全部资源。这种分配通常称 为资源的静态分配。 系统对进程一级采用资源动态分配方法。 系统在进程运行中，根据进程提出的资源需求，进行资源 的动态分配和回收。这种分配通常称为资源的动态分配。4物理资源物理资源 (实资源实资源)虚拟资源虚拟资源 (逻辑资源逻辑资源) 方便用户使用方便用户使用资源可动

2、态分配，提高资源利用率资源可动态分配，提高资源利用率 资源类别资源类别 物理资源物理资源 虚拟虚拟(逻辑逻辑) 映射映射 处理机处理机 CPU存储器存储器 主存主存 设备设备 外部设备外部设备 信息信息 文件物理结构文件物理结构5程序地址空间逻辑设备名逻辑设备名进程调度进程调度地址映射地址映射设备分配设备分配动态映射动态映射磁盘空间分配磁盘空间分配文件目录查找文件目录查找进程进程虚存虚存虚拟设备虚拟设备文件逻辑结构文件逻辑结构6资源描述器定义资源描述器定义 描述描述各类资源的最小分配单位的数 据结构称为资源描述器 rd。 如：主存分区分配方法中，最小分配单 位 主存分区资源描述器内容资源描述器

3、内容 资源名、资源类型、最小分配单位的大 小、地址、分配标志、描述器链接信息、 存取权限、密级、存取时间 20KB 0 52KB66KB130KB230KB256KB 1主存主存作业作业4作业作业1作业作业3OS7资源信息块定义资源信息块定义 描述某类资源的请求者、可用资源和该类资源分配程 序等必要信息的数据结构。资源信息块内容资源信息块内容 请求者队列请求者队列可利用资源队列可利用资源队列资源分配程序资源分配程序等待队列头指针等待队列头指针可利用资源队列头指针可利用资源队列头指针资源分配程序入口地址资源分配程序入口地址8中央处理机资源信息块内容中央处理机资源信息块内容 pcb1pcb2pcb

4、k进程调度程序进程调度程序ready-q-start可用处理机信息可用处理机信息scheduler-addrcpu9每一个新产生的请求均排在队尾；当资源可用时，取队首元素，并满足其需要。 排序原则排序原则：按请求的先后次序排序。 表头表头按请求的先后次序按请求的先后次序先先后后按自然顺序排列的队列按自然顺序排列的队列10 对每一个进程指定一个优先级；每一个新产生的请求，按其优先级的高低插到相应的位置；当资源可用时，取队首元素，并满足其需要。 排序原则排序原则：按优先级的高低排序。 表头表头按按优先级的高低排序按按优先级的高低排序高高低低按优先级高低排列的就绪队列按优先级高低排列的就绪队列11调

5、度的目标调度的目标 当有大量I/O请求时，降低完成这些I/O服务的总时间。 例：例：对磁盘访问有如下5个请求柱面号 盘面号 块号 5 2 1 5 3 8 5 3 5 40 6 3 2 7 712移臂调度移臂调度 总是选取与当前移动臂前进方向上最近的那个I/O请 求，使移臂距离最短。对磁盘访问的5个请求应作如下调度柱面号 盘面号 块号 2 7 7 5 2 1 5 3 8 5 3 5 40 6 3 13旋转调度旋转调度 总是选取与当前读写头最近的那个I/O请求，使旋转圈 数最少。对磁盘访问的5个请求应作如下调度柱面号 盘面号 块号 2 7 7 5 2 1 5 3 5 5 3 8 40 6 3 14

6、 进程进程 p1、p2共享一台打印机和一台输入机共享一台打印机和一台输入机 时刻 t1：进程 p1 占用打印机， 进程 p2 占用输入机； 时刻 t2：进程 p1 又请求输入机， 进程 p2 又请求打印机。 15 设进程p1与进程p2共享一台打印机(r1) 和一台输入机(r2)， 用信号灯的p、v操作表示资源的申请和释放。 信号灯设置 s1：表示：表示r1可用，初值为可用，初值为1 s2：表示：表示r2可用，初值为可用，初值为1讨论两种资源请求序列，哪种情况可能产生互相死等的 局面。16 进程进程p1 进程进程p2 进程进程p1 进程进程p2 p(s1)； p(s2)； p(s1)； p(s2

7、)； 占用r1 占用r2 占用r1 占用r2 v(s1)； v(s2)； p(s2)； p(s1)； 又占用r2 又占用r1 p(s2)； p(s1)； 占用r2 占用r1 v(s1)； v(s2)；v(s2)； v(s1)； v(s2)； v(s1)； 17在两个或多个并发进程中，如果每个进程持有某种 资源而又都等待着别的进程释放它或它们现在保持 着的资源，否则就不能向前推进。此时，称这一组 进程产生了死锁。系统资源不足系统资源不足进程推进顺序非法进程推进顺序非法18N0A1B1C1D1A2B2C2D2P1进程进程P2进程进程A1： p1 request (r1) B1： p1 reques

8、t (r2) C1： p1 release (r1) D1： p1 release (r2) A2： p2 request (r2) B2： p2 request (r1) C2： p2 release (r2) D2： p2 release (r1)19涉及的资源是非共享的，即为临界资源。进程所获得的资源在未使用完毕之前，不能被其 他进程强行夺走。20进程每次申请它所需要的一部分资源。在等待一新 资源的同时，进程继续占用已分配到的资源。存在一种进程的循环链，链中的每一个进程已获得 的资源同时被链中下一个进程所请求。21假定一个系统包括假定一个系统包括n个进程和个进程和m类资源，表示如下类资源

9、，表示如下 一组确定的进程集合，记作：一组确定的进程集合，记作：p=p1，p2，pi，pn 一组不同类型的资源集合，记作：一组不同类型的资源集合，记作： r=r1，r2，rj，rm 矢量矢量w说明各类可利用资源的总的数目说明各类可利用资源的总的数目 w=w1，w2，wj，wm 22在时刻在时刻 t 资源请求矩阵，表示如下资源请求矩阵，表示如下11121m21222mn1n2nmdddddddddd(t) =dij 表示进程表示进程pi还需要还需要j类资源的数目类资源的数目 23在时刻在时刻 t 资源分配矩阵，表示如下资源分配矩阵，表示如下11121m21222mn1n2nmaaaaaaaaaa

10、(t) =aij 表示进程表示进程pi已占有已占有j类资源的数目类资源的数目 什么情况下系统安全的？什么情况下系统安全的？ 当进程请求某类资源时，进程对该类资源的需求量 小于当前时刻系统所拥有的该类资源的数目，那么 满足进程的这次请求，系统是安全的。24破坏产生死锁的四个必要条件之一采用静态资源分配方法预防死锁。采用有控资源分配方法避免死锁死锁的检测与忽略25在作业调度时为选中的作业分配它所需要的所有资 源，当资源一旦分配给该作业后，在其整个运行期 间这些资源为它独占。有序资源分配法有序资源分配法 系统中所有资源都给定一个唯一的编号，所有分配请 求必须以上升的次序进行。当遵守上升次序的规则 时

11、，若资源可用，则予以分配；否则，请求者等待。26银行家算法银行家算法 申请者事先说明对各类资源的最大需求量。在进程活 动期间动态申请某类资源时，由系统审查系统现有该 类资源的数目是否能满足当前进程的最大需求量，如 能满足就予以分配，否则拒绝。27银行家算法例银行家算法例 系统拥有某类资源10个， 现有进程P、Q、R共享该类资源， 它们申请该类资源的最大需求量如下。 进程 最大需求量 已占有资源 P 8 4 Q 4 2 R 9 2现申请资源个数 1 1 1 当这些进程动态申请资源时，按银行家算法应如何分配，能保证不发生死锁。28 先请求先服务先请求先服务 优先调度优先调度 针对设备特性的调度针对设备特性的调度定义定义 举例举例引起死锁的原因引起死锁的原因产生死锁的必要条件产生死锁的必要条件死锁预防死锁预防死锁避免死锁避免有序资源分配方法有序资源分配方法银行家算法银行家算法