05操作系统原理_庞丽萍_第五章资源分配与调度

1(一)资源管理概述(二)资源分配的机构和策略(三)死锁概念第五章资源分配与调度2(一)资源管理概述一.资源管理功能1.资源数据结构的描述构造资源分配所需的数据结构，应包含该资源的物理名、逻辑名、类型、地址、分配状态等信息。2.确定资源的分配原则(调度原则)决定资源应分给谁，何时分配，分配多少等问题。3.实施资源分配分配或收回资源4.存取控制和安全保护对资源的存取进行控制并对资源实施安全保护措施。3二.资源的静态分配和动态分配1.资源的静态分配系统对作业一级采用资源静态分配方法。系统在调度作业时，根据作业所需资源进行分配；并在作业运行完毕时，收回所分配的全部资源。这种分配通常称为资源的静态分配。2.资源的动态分配系统对进程一级采用资源动态分配方法。系统在进程运行中，根据进程提出的资源需求，进行资源的动态分配和回收。这种分配通常称为资源的动态分配。4三.虚拟资源1.操作系统对资源区分二种不同的概念•物理资源(实资源)•虚拟资源(逻辑资源)2.目的•方便用户使用•资源可动态分配，提高资源利用率5(二)资源分配的机构和策略一.资源分配机构1.资源描述器(1)什么是资源描述器描述各类资源的最小分配单位的数据结构称为资源描述器rd(resourcedescriptor)。如：主存最小分配单位：在分区分配中——主存分区磁盘最小分配单位：磁盘面中的一个扇区6(2)资源描述器的内容资源名资源类型最小分配单位的大小最小分配单位的地址分配标志描述器链接信息存取权限密级最后一次存取时间记账信息72.资源信息块(1)什么是资源信息块描述某类资源的请求者、可用资源和该类资源分配程序等必要信息的数据结构。(2)资源信息块的内容等待队列头指针可利用资源队列头指针资源分配程序入口地址请求者队列可利用资源队列资源分配程序8资源信息块的内容等待队列头指针可利用资源队列头指针资源分配程序入口地址┅pcb1pcb2pcbkrd1rd2rdn资源分配程序┅9(3)中央处理机资源信息块ready-q-start可用处理机信息scheduler-addr┅pcb1pcb2pcbkcpucpu-rib进程调度程序10二.资源分配策略1.常用的资源分配策略(1)先请求先服务(FIFO(FirstInFirstOut)策略)排序原则：按请求的先后次序排序。每一个新产生的请求均排在队尾，而当资源可用时，资源分配程序则从队列中选取第一个请求，并满足其需要。┅表头按请求的先后次序先后按自然顺序排列的队列11(2)优先调度在优先调度策略下，对于每一个进程要指定一个优先级，优先级反映了进程要求处理的紧迫程度。排序原则：按优先级的高低排序。每一个新产生的请求，按其优先级的高低插到相应的位置上。而当资源可用时，选取队列中第一个请求，并满足其需要。┅表头按优先级的高低排序高低按优先级高低排列的就绪队列122.针对设备特性的调度调度的目标：当有大量I/O请求时，降低完成这些I/O服务的总时间。(1)例对磁盘访问有如下5个请求：柱面号盘面号块号521538535406327713(2)移臂调度总是选取与当前移动臂前进方向上最近的那个I/O请求，使移臂距离最短。对磁盘访问的5个请求应作如下调度：柱面号盘面号块号277521538535406314(3)旋转调度总是选取与当前读写头最近的那个I/O请求，使旋转圈数最少。对磁盘访问的5个请求应作如下调度：柱面号盘面号块号277521535538406315(三)死锁概念一.什么是死锁1.死锁的例(1)设备共享进程p1、p2共享一台打印机和一台光标记阅读机时刻t1，进程p1——占用打印机进程p2——占用光标记阅读机。时刻t2，进程p1——又请求光标记阅读机进程p2——又请求打印机16(2)用信号灯的P、V操作描述死锁设进程A与进程B共享一台打印机(R1)和一台光标记阅读机(R2)。用信号灯的P、V操作表示资源的申请和释放。信号灯设置——s1：表示R1可用，初值为1。s2：表示R2可用，初值为1。讨论两种资源请求序列，哪种情况可能产生互相死等的局面。17进程A进程BA进程进程B┆┆┆┆p(s1)；p(s2)；p(s1)；p(s2)；占用R1占用R2占用R1占用R2v(s1)；v(s2)；p(s2)；p(s1)；┆┆又占用R2又占用R1p(s2)；p(s1)；┆┆占用R2占用R1v(s1)；v(s2)；v(s2)；v(s1)；┆┆┆┆v(s2)；v(s1)；┆┆┆┆182.什么是死锁在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，称这一组进程产生了死锁。二.死锁的起因和条件1.引起死锁的原因系统资源不足；进程推进顺序非法。192.死锁图解N0A1B1C1D1A2B2C2D2P1进程P2进程•A1：p1request(r1)A2：p2request(r2)B1：p1request(r2)B2：p2request(r1)C1：p1release(r1)C2：p2release(r2)D1：p1release(r2)D2：p2release(r1)203.产生死锁的必要条件(1)互斥条件涉及的资源是非共享的，即为临界资源。(2)不剥夺条件进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。(3)部分分配进程每次申请它所需要的一部分资源。在等待一新资源的同时，进程继续占用已分配到的资源。(4)环路条件存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所请求。21三.解决死锁问题的策略破坏产生死锁的四个必要条件之一1.解决死锁的策略采用静态资源分配方法——预防死锁采用有控资源分配方法——避免死锁死锁的检测与恢复22四.死锁的预防1.静态预防死锁的方法在作业调度时为选中的作业分配它所需要的所有资源，当资源一旦分配给该作业后，在其整个运行期间这些资源为它独占。2.动态预防死锁的方法(1)有序资源分配法系统中所有资源都给定一个唯一的编号，所有分配请求必须以上升的次序进行。当遵守上升次序的规则时，若资源可用，则予以分配；否则，请求者等待。23(2)银行家算法申请者事先说明对各类资源的最大需求量。在进程活动期间动态申请某类资源时，由系统审查系统现有该类资源的数目是否能满足当前进程的最大需求量，如能满足就予以分配，否则拒绝。例：系统拥有某类资源10个。现有进程P、Q、R共享该类资源。它们申请该类资源的最大需求量如下，当这些进程动态申请资源时，按银行家算法应如何分配，能保证不发生死锁。进程最大需求量已占有资源P84Q42R9224第五章小结一.资源管理功能二.常用的资源分配策略先请求先服务优先调度针对设备特性的调度三.死锁1.定义举例2.引起死锁的原因3.产生死锁的必要条件4.死锁预防5.死锁避免：有序资源分配方法银行家算法