资源分配与调度 第5章 资源分配与调度.

Slides:



Advertisements
Similar presentations
7.1 内置对象概述及分类 JSP 视频教学课程. JSP2.2 目录 1. 内置对象简介 1. 内置对象简介 2. 内置对象分类 2. 内置对象分类 3. 内置对象按功能区分 3. 内置对象按功能区分 4. 内置对象作用范围 4. 内置对象作用范围.
Advertisements

数据结构的引入. 通讯录管理 社团机构管理 校园导航管理 通讯录管理 社团机构管理 校园导航管理.
高校教师、高级项目经理 任铄 QQ : 第一章 操作系统引论 1.1 操作系统的目标和作用 1.2 操作系统的发展过程 1.3 操作系统的基本特性 1.4 操作系统的主要功能 1.5 OS 结构设计.
《操作系统原理》 期末考试说明 2011 年 2 月 -5 月. 教材和参考书 教材 讲义 操作系统原理 ver4. 华中科技大学出版社.
阻塞操作. 在 linux 里,一个等待队列由一个 wait_queue_head_t 类型的结构来描述 等待队列的初始化: static wait_queue_head_t testqueue; init_waitqueue_head(&testqueue);
Linux 系统. 操作系统发展需求 1 没有操作系统 2 简单批处理操作系统 3 多道程序设计的批处理 4 多道程序设计的分时操作系统 5 多处理机并行系统 6 网络操作系统 7 分布式操作系统.
LSF系统介绍 张焕杰 中国科学技术大学网络信息中心
广东省高新技术企业认定工作培训 关于专项审计报告的说明与解释.
计算机操作系统 期末复习二.
Chapter Two Process Management.
总复习 级一本各专业.
实用操作系统概念 张惠娟 副教授 1.
第三章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度
第三章 处理机调度与死锁 本章主要理解进程调度和死锁的基本概念,熟悉进程调度的各种算法及适用范围,了解产生死锁的原因和必要条件,掌握如何预防、避免、检测、解除死锁的各种方法,特别是银行家算法。 重、难点: 进程调度算法 产生死锁的原因和必要条件 银行家算法.
时政发布 制作:宋虹雷.
计算机基础知识 丁家营镇九年制学校 徐中先.
第5节 磁盘 磁盘的结构 磁盘的地址 磁盘访问的优化 磁盘使用过程 举例.
陈香兰 助教:陈博、李春华 Spring 2009 嵌入式操作系统 陈香兰 助教:陈博、李春华 Spring 2009.
社會學(一) 空中大學花蓮中心 鍾燕菁
Kvm异步缺页中断 浙江大学计算机体系结构实验室 徐浩.
LSF系统介绍 张焕杰 中国科学技术大学网络信息中心
中国科学技术大学计算机系 陈香兰 2013Fall 第六讲 死锁及其处理 中国科学技术大学计算机系 陈香兰 2013Fall.
存储系统.
SOA – Experiment 3: Web Services Composition Challenge
Jul 2014 HEAT部署Hadoop集群
辅导课程六.
网络常用常用命令 课件制作人:谢希仁.
临界区软件互斥软件实现算法.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
Windows网络操作系统管理 ——Windows Server 2008 R2.
第十章 IDL访问数据库 10.1 数据库与数据库访问 1、数据库 数据库中数据的组织由低到高分为四级:字段、记录、表、数据库四种。
动态规划(Dynamic Programming)
临界区软件互斥软件实现算法 主讲教师:夏莹杰
CPU结构和功能.
第4章 非线性规划 4.5 约束最优化方法 2019/4/6 山东大学 软件学院.
何勉 新浪微博: Scrum框架及其背后的原则 原始图片 何勉 新浪微博:
解决变化问题的自底向上 流程建模方法 严志民 徐玮.
内容摘要 ■ 课程概述 ■ 教学安排 ■ 什么是操作系统? ■ 为什么学习操作系统? ■ 如何学习操作系统? ■ 操作系统实例
C语言程序设计 主讲教师:陆幼利.
EBNF与操作语义 请用扩展的 BNF 描述 javascript语言里语句的结构;并用操作语义的方法描述对应的语义规则
微机系统的组成.
青少年常見犯法行為.
浙江大学医学院公共技术平台 实验仪器预约管理系统系列培训 医学院公共技术平台 丁巧灵
工业机器人知识要点解析 (ABB机器人) 主讲人:王老师
计算机网络与网页制作 Chapter 07:Dreamweaver CS5入门
<编程达人入门课程> 本节内容 内存的使用 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群: ,
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
信号量(Semaphore).
第4章 Excel电子表格制作软件 4.4 函数(一).
iSIGHT 基本培训 使用 Excel的栅栏问题
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
本节内容 线性地址的管理 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第八章 总线技术 8.1 概述 8.2 局部总线 8.3 系统总线 8.4 通信总线.
本节内容 文件系统 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
第八章 死锁 死锁的基本概念 死锁的解决方案 (预防,避免,检测及解除) 资源分配图.
系统权限管理概要 用 户 访问权限 对 象 用户和组 全局权限 类别 每个用户可以属于多个用户组 用户组可以与AD安全组同步 系统预置用户组
资源分配与调度 第5章 资源分配与调度.
临界区问题的硬件指令解决方案 (Synchronization Hardware)
OpenStack vs CloudStack
GIS基本功能 数据存储 与管理 数据采集 数据处理 与编辑 空间查询 空间查询 GIS能做什么? 与分析 叠加分析 缓冲区分析 网络分析
Google的云计算 分布式锁服务Chubby.
死 锁 Deadlock.
基于列存储的RDF数据管理 朱敏
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
本节内容 动态链接库 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 进程 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
FVX1100介绍 法视特(上海)图像科技有限公司 施 俊.
入侵检测技术 大连理工大学软件学院 毕玲.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
Presentation transcript:

资源分配与调度 第5章 资源分配与调度

资源分配与调度——主要内容 资源管理概述 资源分配的机构和策略 死锁 1

资源分配与调度——资源管理概述 资源管理概述

1. 资源管理功能 (1) 资源数据结构的描述 (2) 确定资源的分配原则 (调度原则) (3) 实施资源分配 (4) 存取控制和安全保护 资源分配与调度——资源管理概述 1. 资源管理功能 (1) 资源数据结构的描述 包含资源的物理名、逻辑名、类型、地址、分配状态等 信息。 (2) 确定资源的分配原则 (调度原则) 决定资源应分给谁,何时分配,分配多少等问题。 (3) 实施资源分配 执行资源分配;资源收回工作。 (4) 存取控制和安全保护 对资源的存取进行控制并对资源实施安全保护措施。 2

2. 资源资源的静态分配和动态分配 (1) 资源的静态分配 (2) 资源的动态分配 资源分配与调度——资源管理概述 2. 资源资源的静态分配和动态分配 (1) 资源的静态分配 系统对作业一级采用资源静态分配方法。 系统在调度作业时,根据作业所需资源进行分配;并在作 业运行完毕 时,收回所分配的全部资源。这种分配通常称 为资源的静态分配。 (2) 资源的动态分配 系统对进程一级采用资源动态分配方法。 系统在进程运行中,根据进程提出的资源需求,进行资源 的动态分配和回收。这种分配通常称为资源的动态分配。 3

3. 虚拟资源 (1) 操作系统对资源区分二种不同的概念 (2) 目的 资源分配与调度——资源管理概述 物理资源 (实资源) 3. 虚拟资源 (1) 操作系统对资源区分二种不同的概念 物理资源 (实资源) 虚拟资源 (逻辑资源) (2) 目的 方便用户使用 资源可动态分配,提高资源利用率 4

(3) 计算机系统中的物理资源与虚拟资源分析 资源分配与调度——资源管理概述 (3) 计算机系统中的物理资源与虚拟资源分析 资源类别 物理资源 虚拟(逻辑) 映射 处理机 CPU 存储器 主存 设备 外部设备 信息 文件物理结构 进程 进程调度 虚存 (程序地址空间) 地址映射 逻辑设备 虚拟设备 设备分配 动态映射 磁盘空间分配 文件目录查找 文件逻辑结构 5

资源分配与调度——资源分配机构和策略 资源分配结构和策略

1. 资源分配的机构 (1) 资源描述器 资源分配与调度——资源分配机构和策略 ① 资源描述器定义 描述描述各类资源的最小分配单位的数 1. 资源分配的机构 20KB 52KB 66KB 130KB 230KB 256KB1 主存 程序4 程序1 程序3 OS (1) 资源描述器 ① 资源描述器定义 描述描述各类资源的最小分配单位的数 据结构称为资源描述器 rd。 如:主存分区分配方法中,最小分配单 位为主存分区。 ② 资源描述器内容 资源名、资源类型、最小分配单位的大 小、地址、分配标志、描述器链接信息、 存取权限、密级、存取时间 内存分布状况图 6

描述某类资源的请求者、可用资源和该类资源分配程序等 必要信息的数据结构。 ② 资源信息块内容 资源分配与调度——资源分配机构和策略 (2) 资源信息块 ① 资源信息块定义 描述某类资源的请求者、可用资源和该类资源分配程序等 必要信息的数据结构。 ② 资源信息块内容 请求者队列 可利用资源队列 资源分配程序 等待队列头指针 可利用资源队列头指针 资源分配程序入口地址 资源信息块示意图 7

(3) 资源信息块例 资源分配与调度——资源分配机构和策略 中央处理机资源信息块内容  PCB1 PCB2 PCBk 进程调度程序 ready_q_start 可用处理机信息 scheduler_addr CPU 中央处理机资源信息块示意图 8

2. 资源分配策略 (1) 常用的资源分配策略 资源分配与调度——资源分配机构和策略 ① 先请求先服务 每一个新产生的请求均排在队尾; 2. 资源分配策略 (1) 常用的资源分配策略 ① 先请求先服务 每一个新产生的请求均排在队尾; 当资源可用时,取队首元素,并满足其需要。 排序原则:按请求的先后次序排序。  表头 按请求的先后次序 先 后 按自然顺序排列的资源请求队列 9

每一个新产生的请求,按其优先级的高低插到相应的 位置; 当资源可用时,取队首元素,并满足其需要。 排序原则:按优先级的高低排序。 资源分配与调度——资源分配机构和策略 ② 优先调度 对每一个进程指定一个优先级; 每一个新产生的请求,按其优先级的高低插到相应的 位置; 当资源可用时,取队首元素,并满足其需要。 排序原则:按优先级的高低排序。  表头 按按优先级的高低排序 高 低 按优先级高低排列的资源请求队列 10

当有大量I/O请求时,降低完成这些I/O服务的总时间。 资源分配与调度——资源分配机构和策略 ③ 针对设备特性的调度策略 ⅰ 调度的目标 当有大量I/O请求时,降低完成这些I/O服务的总时间。 ⅱ 例:讨论对磁盘访问的调度,有如下5个请求。 柱面号 盘面号 块号 5 2 1 5 3 8 5 3 5 40 6 3 2 7 7 11

总是选取与当前移动臂前进方向上最近的那个I/O请求, 使移臂距离最短。 资源分配与调度——资源分配机构和策略 ⅲ 移臂调度 总是选取与当前移动臂前进方向上最近的那个I/O请求, 使移臂距离最短。 对磁盘访问的5个请求,按移臂调度应作如下调整。 柱面号 盘面号 块号 2 7 7 5 2 1 5 3 8 5 3 5 40 6 3 12

总是选取与当前读写头最近的那个I/O请求,使旋转圈 数最少。 资源分配与调度——资源分配机构和策略 ⅳ 旋转调度 总是选取与当前读写头最近的那个I/O请求,使旋转圈 数最少。 对磁盘访问的5个请求,再按旋转调度应作如下调整。 柱面号 盘面号 块号 2 7 7 5 2 1 5 3 5 5 3 8 40 6 3 13

资源分配与调度——死锁 死锁

1. 什么是死锁 (1) 死锁的例 资源分配与调度——死锁 设备共享 进程 p1、p2共享一台打印机和一台输入机 1. 什么是死锁 (1) 死锁的例 设备共享 进程 p1、p2共享一台打印机和一台输入机 时刻 t1:进程 p1 —— 占用打印机, 进程 p2 —— 占用输入机; 时刻 t2:进程 p1 —— 又请求输入机, 进程 p2 —— 又请求打印机。 时刻t2后,系统出现僵持局面,即出现了死锁现象。 14

(2) 用信号灯的P、V操作描述死锁 资源分配与调度——死锁 设进程p1与进程p2共享一台打印机(r1) 和一台输入机(r2), 信号灯设置—— s1:表示r1可用,初值为1 s2:表示r2可用,初值为1 讨论两种资源请求序列,哪种情况可能产生互相死等的 局面。 程序描述如下: 15

资源分配与调度——死锁 程序描述1 程序描述2     p(s1); p(s2); p(s1); p(s2); 程序描述1 程序描述2 进程p1 进程p2 进程p1 进程p2     p(s1); p(s2); p(s1); p(s2); 占用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); 程序描述2,有可能出现死锁。 16

2. 死锁的起因和条件 (3) 什么是死锁 在两个或多个并发进程中,如果每个进程持有某种资源而 (1) 引起死锁的原因 资源分配与调度——死锁 (3) 什么是死锁 在两个或多个并发进程中,如果每个进程持有某种资源而 又都等待着别的进程释放它或它们现在保持着的资源,否 则就不能向前推进。此时,称这一组进程产生了死锁。 2. 死锁的起因和条件 (1) 引起死锁的原因 ① 系统资源不足 ② 进程推进顺序非法 17

(2) 死锁图解 资源分配与调度——死锁 N A1 B1 C1 D1 A2 B2 C2 D2 P1进程 P2进程 • 死锁图解 A1 B1 C1 D1 A2 B2 C2 D2 P1进程 P2进程 • 死锁图解 A1: p1 request (r1) B1: p1 request (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) 18

(3) 产生死锁的必要条件 资源分配与调度——死锁 ① 互斥条件 涉及的资源是非共享的,即为临界资源。 ② 不剥夺条件 进程所获得的资源在未使用完毕之前,不能被其他进程强 行夺走。 ③ 部分分配 进程每次申请它所需要的一部分资源。在等待一新资源的 同时,进程继续占用已分配到的资源。 ④ 环路条件 存在一种进程的循环链,链中的每一个进程已获得的资 源同时被链中下一个进程所请求。 19

3. 系统状态分析 (1) 初始状态描述 资源分配与调度——死锁 假定一个系统包括n个进程和m类资源,表示如下 3. 系统状态分析 (1) 初始状态描述 假定一个系统包括n个进程和m类资源,表示如下 ① 一组确定的进程集合,记作: p={p1,p2,…,pi,…,pn} ② 一组不同类型的资源集合,记作: r={r1,r2,…,rj,…,rm} ③ 矢量w说明各类可利用资源的总的数目 w={w1,w2,…,wj,…,wm} 21

(2) 资源请求矩阵 资源分配与调度——死锁 在时刻 t 资源请求矩阵,表示如下 dij 表示进程pi还需要j类资源的数目 d(t) = 22

(3) 资源分配矩阵 资源分配与调度——死锁 在时刻 t 资源分配矩阵,表示如下 aij 表示进程pi已占有j类资源的数目 a(t) = aij 表示进程pi已占有j类资源的数目 什么情况下系统是安全的? 当进程请求某类资源时,进程对该类资源的需求量小于 当前时刻系统所拥有的该类资源的数目,那么满足进程 的这次请求,系统是安全的。 23

4. 解决死锁问题的策略 资源分配与调度——死锁 破坏产生死锁的四个必要条件之一 解决死锁的策略 采用静态资源分配方法——预防死锁。 4. 解决死锁问题的策略 破坏产生死锁的四个必要条件之一 解决死锁的策略 采用静态资源分配方法——预防死锁。 采用有控资源分配方法——避免死锁 死锁的检测与忽略 24

5. 死锁的预防 (1) 静态预防死锁的方法 在作业调度时为选中的作业分配它所需要的所有资源,当 (2) 动态预防死锁的方法 资源分配与调度——死锁 5. 死锁的预防 (1) 静态预防死锁的方法 在作业调度时为选中的作业分配它所需要的所有资源,当 资源一旦分配给该作业后,在其整个运行期间这些资源为 它独占。 (2) 动态预防死锁的方法 ① 有序资源分配法 系统中所有资源都给定一个唯一的编号,所有分配请求必 须以上升的次序进行。当遵守上升次序的规则时,若资源 可用,则予以分配;否则,请求者等待。 25

申请者事先说明对各类资源的最大需求量。在进程活动 期间动态申请某类资源时,由系统审查现有该类资源的 资源分配与调度——死锁 ② 银行家算法 申请者事先说明对各类资源的最大需求量。在进程活动 期间动态申请某类资源时,由系统审查现有该类资源的 数目是否能满足当前进程的最大需求量,如能满足就予 以分配,否则拒绝。 26

系统拥有某类资源10个,现有进程P、Q、R共享该类资 源,它们申请该类资源的最大需求量如下。 资源分配与调度——死锁 ③ 银行家算法例 系统拥有某类资源10个,现有进程P、Q、R共享该类资 源,它们申请该类资源的最大需求量如下。 进程 最大需求量 已占有资源 P 8 4 Q 4 2 R 9 2 现申请资源个数 1 当这些进程动态申请资源时,按银行家算法应如何分 配,能保证不发生死锁。 27

资源分配与调度——小结 第5章 资源分配与调度 小结

资源分配与调度——小结 资源管理功能 资源分配策略 死锁 先请求先服务 优先调度 针对设备特性的调度 定义 举例 引起死锁的原因 先请求先服务 优先调度 针对设备特性的调度 死锁 定义 举例 引起死锁的原因 产生死锁的必要条件 死锁预防 死锁避免 有序资源分配方法 银行家算法 28