os5资源分配与调度.ppt

Click to edit Title Slide,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,资源分配与调度,资源分配与调度,资源管理概述,资源分配的机构和策略,死锁,1,资源分配与调度,主要内容,2,1.,资源管理功能,资源数据结构的描述,包含资源的物理名、逻辑名、类型、地址、分配状态等信息。,确定资源的分配原则,(,调度原则,),决定资源应分给谁，何时分配，分配多少等问题。,实施资源分配,执行资源分配；资源收回工作。,存取控制和安全保护,对资源的存取进行控制并对资源实施安全保护措施。,资源分配与调度,资源管理概述,3,2.,资源资源的静态分配和动态分配,资源的静态分配,系统对作业一级采用资源静态分配方法。,系统在调度作业时，根据作业所需资源进行分配；并在作,业运行完毕 时，收回所分配的全部资源。这种分配通常称,为资源的静态分配。,资源的动态分配,系统对进程一级采用资源动态分配方法。,系统在进程运行中，根据进程提出的资源需求，进行资源,的动态分配和回收。这种分配通常称为资源的动态分配。,资源分配与调度,资源管理概述,4,3.,虚拟,资源,操作系统对资源区分二种不同的概念,物理资源,(,实资源,),虚拟资源,(,逻辑资源,),目的,方便用户使用,资源可动态分配提高资源利用率,资源分配与调度,资源管理概述,计算机系统中的物理资源与虚拟资源分析,资源类别 物理资源 虚拟,(,逻辑,),映射,处理机,CPU,存储器 主存,设备 外部设备,信息 文件物理结构,操作系统采用的技术,5,程序地址空间,逻辑设备名,进程调度,地址映射,设备分配,动态映射,磁盘空间分配,文件目录查找,进程,虚存,虚拟设备,文件逻辑结构,6,资源描述器,资源描述器定义,描述描述各类资源的最小分配单位的数,据结构称为资源描述器,rd,。,如：主存分区分配方法中，最小分配单,位,主存分区,资源描述器内容,资源名、资源类型、最小分配单位的大,小、地址、分配标志、描述器链接信息、,存取权限密级、存取时间,资源分配与调度,资源分配机构和策略,1.,资源分配的机构,20KB,0,52KB,66KB,130KB,230KB,256KB,1,主存,作业,4,作业,1,作业,3,OS,7,资源信息块,资源信息块定义,描述某类资源的请求者、可用资源和该类资源分配程,序等必要信息的数据结构。,资源信息块内容,请求者队列,可利用资源队列,资源分配程序,等待队列头指针,可利用资源队列头指针,资源分配程序入口地址,资源分配与调度,资源分配机构和策略,8,资源信息块例,中央处理机资源信息块内容,pcb,1,pcb,2,pcb,k,进程调度程序,ready-q-start,可用处理机信息,scheduler-,addr,cpu,资源分配与调度,资源分配机构和策略,9,2.,资源分配策略,常用的资源分配策略,先请求先服务,每一个新产生的请求均排在队尾；,当资源可用时，取队首元素，并满足其需要。,排序原则,：按请求的先后次序排序。,资源分配与调度,资源分配机构和策略,表头,按请求的先后次序,先,后,按自然顺序排列的队列,10,优先调度,对每一个进程指定一个优先级；,每一个新产生的请求，按其优先级的高低插到相应的位置；,当资源可用时，取队首元素，并满足其需要。,排序原则,：按优先级的高低排序。,资源分配与调度,资源分配机构和策略,表头,按按优先级的高低排序,高,低,按优先级高低排列的就绪队列,11,针对设备特性的调度策略,调度的目标,当有大量,I/O,请求时，降低完成这些,I/O,服务的总时间。,资源分配与调度,资源分配机构和策略,例：,对磁盘访问有如下,5,个请求,柱面号 盘面号 块号,5 2 1,5 3 8,5 3 5,40 6 3,2 7 7,12,针对设备特性的调度策略,移臂调度,总是选取与当前移动臂前进方向上最近的那个,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,死锁的例,设备共享,进程,p,1,、,p,2,共享一台打印机和一台输入机,时刻,t,1,：进程,p,1,占用打印机，,进程,p,2,占用输入机；,时刻,t,2,：进程,p,1,又请求,输入机，,进程,p,2,又请求打印机。,资源分配与调度,死锁,1.,什么是死锁,15,用信号灯的,P,、,V,操作描述死锁,设进程,p,1,与进程,p,2,共享一台打印机,(r,1,),和一台输入机,(r,2,),，,用信号灯的,p,、,v,操作表示资源的申请和释放。,信号灯设置,s,1,：表示,r,1,可用，初值为,1,s,2,：表示,r,2,可用，初值为,1,讨论两种资源请求序列，哪种情况可能产生互相死等的,局面。,资源分配与调度,死锁,16,用信号灯的,P,、,V,操作描述死锁,进程,p,1,进程,p,2,进程,p,1,进程,p,2,p(s,1,),；,p(s,2,),；,p(s,1,),；,p(s,2,),；,占用,r,1,占用,r,2,占用,r,1,占用,r,2,v(s,1,),；,v(s,2,),；,p(s,2,),；,p(s,1,),；,又占用,r,2,又,占用,r,1,p(s,2,)p(s,1,),；,占用,r,2,占用,r,1,v(s,1,),；,v(s,2,),；,v(s,2,),；,v(s,1,),；,v(s,2,),；,v(s,1,),；,资源分配与调度,死锁,17,什么是死锁,在两个或多个并发进程中，如果每个进程持有某种,资源而又都等待着别的进程释放它或它们现在保持,着的资源，否则就不能向前推进。此时，称这一组,进程产生了死锁。,资源分配与调度,死锁,2.,死锁的起因和条件,引起死锁的原因,系统资源不足,进程推进顺序非法,18,资源分配与调度,死锁,死锁图解,N,0,A,1,B,1,C,1,D,1,A2,B2,C,2,D,2,P,1,进程,P,2,进程,A1,：,p,1,request(r,1,)B,1,：,p,1,request(r,2,)C,1,：,p,1,release(r,1,)D,1,：,p,1,release(r,2,),A,2,：,p,2,request(r,2,)B,2,：,p,2,request(r,1,)C,2,：,p,2,release(r,2,)D,2,：,p,2,release(r,1,),19,资源分配与调度,死锁,互斥条件,涉及的资源是非共享的，即为临界资源。,不剥夺条件,进程所获得的资源在未使用完毕之前，不能被其,他进程强行夺走。,产生死锁的必要条件,20,资源分配与调度,死锁,部分分配,进程每次申请它所需要的一部分资源。在等待一新,资源的同时，进程继续占用已分配到的资源。,环路条件,存在一种进程的循环链，链中的每一个进程已获得,的资源同时被链中下一个进程所请求。,21,资源分配与调度,死锁,3.,系统状态分析,初始状态描述,假定一个系统包括,n,个进程和,m,类资源，表示如下,一组确定的进程集合，记作：,p=p,1,，,p,2,，,，,p,i,，,，,p,n,一组不同类型的资源集合，记作：,r=r,1,，,r,2,，,，,r,j,，,，,r,m,矢量,w,说明各类可利用资源的总的数目,w=w,1,，,w,2,，,，,w,j,，,，,w,m,22,资源分配与调度,死锁,资源请求矩阵,在时刻,t,资源请求矩阵，表示如下,d(t,)=,d,ij,表示进程,p,i,还需要,j,类资源的数目,23,资源分配与调度,死锁,资源分配矩阵,在时刻,t,资源分配矩阵，表示如下,a(t,)=,a,ij,表示进程,p,i,已占有,j,类资源的数目,什么情况下系统安全的？,当进程请求某类资源时，进程对该类资源的需求量,小于当前时刻系统所拥有的该类资源的数目，那么,满足进程的这次请求，系统是安全的。,24,资源分配与调度,死锁,4.,解决死锁问题的策略,破坏产生死锁的四个必要条件之一,解决死锁的策略,采用静态资源分配方法,预防死锁。,采用有控资源分配方法,避免死锁,死锁的检测与忽略,25,资源分配与调度,死锁,5.,死锁的预防,静态预防死锁的方法,在作业调度时为选中的作业分配它所需要的所有资,源，当资源一旦分配给该作业后，在其整个运行期,间这些资源为它独占。,动态预防死锁的方法,有序资源分配法,系统中所有资源都给定一个唯一的编号，所有分配请,求必须以上升的次序进行。当遵守上升次序的规则,时，若资源可用，则予以分配；否则，请求者等待。,26,资源分配与调度,死锁,银行家算法,申请者事先说明对各类资源的最大需求量。在进程活,动期间动态申请某类资源时，由系统审查系统现有该,类资源的数目是否能满足当前进程的最大需求量，如,能满足就予以分配，否则拒绝。,27,资源分配与调度,死锁,银行家算法例,系统拥有某类资源,10,个，,现有进程,P,、,Q,、,R,共享该类资源，,它们申请该类资源的最大需求量如下。,进程 最大需求量 已占有资源,P 8 4,Q 4 2,R 9 2,现申请资源个数,1,1,1,当这些进程动态申请资源时，按银行家算法应如何分配，能保证不发生死锁。,28,资源管理功能,资源分配策略,先请求先服务 优先调度 针对设备特性的调度,死锁,定义 举例,引起死锁的原因,产生死锁的必要条件,死锁预防,死锁避免,有序资源分配方法,银行家算法,资源分配与调度,小结,