软件技术处理器管理.ppt

《软件技术处理器管理.ppt》由会员分享，可在线阅读，更多相关《软件技术处理器管理.ppt（90页珍藏版）》请在三一文库上搜索。

1、第八章 处理器管理,本章基本内容与要求,基本内容 作业的概念 进程的概念 进程状态及进程控制 处理机调度 进程的同步和互斥 死锁问题 要求 掌握进程的概念及作用 掌握进程的控制与调度方法 掌握进程的同步与互斥、P、V操作 掌握死锁的概念和死锁的解决方法,第一节 作业的概念,一、作业的定义 二、作业的组成 三、作业的状态,一、作业的定义,作业是用户在一次算题过程中或一个事务处理中要求计算机系统所做的工作的集合。,二、作业的组成,作业由程序、数据和作业说明书组成 。,作业控制块JCB,作业被收容到外存后，系统为每个作业建立一个JCB，它详细记录作业的有关信息,作业队列,(Job Control B

2、lock),三、作业的状态,1）提交状态 用户向机房提交作业或通过终端键盘将作业输入，其作业所处的状态为提交状态。 2）收容状态 作业的全部信息已输入外存储器中并建立JCB表，等待运行，又称后备状态。 3）执行状态 作业被调度程序选中后就给它分配必要的资源，并按照作业步的顺序，依次为每个作业步建立对应的主进程，然后将其提交给进程管理模块，由进程调度程序管理并调度执行。 4）完成状态 作业执行完毕或出错而中途停止，释放其占用的全部资源，准备退出系统。,提交,作业,收容,执行,完成,外存,内存,设备管理,作业管理,区分配,作业的生命期,作业从进入计算机系统到运行结束、退出系统的整个过程分成四个阶段

3、,第二节 进程的概念,一、引入进程概念的原因 二、进程定义 三、进程与程序的区别 四、作业和进程的关系,单道程序系统下的程序执行具有顺序性、资源独占性（封闭性）、确定性（可再现性）特点。 多道程序系统中程序执行出现新特点：相互制约性、随机性、资源共享、与速度有关性。因而： 用程序这个静态的概念来申请使用系统资源已经不合适； 一个程序段或程序，可能对应多个“计算”，程序与“计算”已不具有一一对应关系。,一、引入进程概念的原因,进程是一个可并发执行的程序在一个数据集上的一次执行过程。它是系统分配资源的基本单位。,进程是由程序、数据集和进程控制块三部分组成。,二、进程定义,进程控制块 PCB (Pr

4、ocess Control Block),是进程的档案，记录各进程执行情况。 是进程存在的标志 进程与PCB是一一对应的,三、进程与程序的区别,1）进程是一个动态的概念，是执行程序的动态过程。而程序是一个静态的概念，是进程运行的静态文本。 2）进程能真实地描述并发执行，且具有并发性，而程序没有。 3）一个进程可以执行一个或多个程序。反之，同一程序也可能由多个进程同时执行。 4）程序可以作为一种软件资源长期保持，而进程则是程序的一次执行过程，它不具有存储性。,四、作业与进程的关系,（1）作业是用户向计算机提交任务的任务实体，而进程是完成用户任务的执行实体； （2）一个作业可由多个进程组成，且必须

5、至少有一个进程； （3）作业的概念主要用在批处理系统中，而进程的概念则几乎用在所有多道系统中。,第三节 进程状态及进程控制,一、进程状态 二、进程控制,一、进程状态,运行,就绪,等待,选中,等待事件发生 (如I/O请求),等待结束 如等到I/O资源,落选 (时间到）,作业调度,进程调度,就绪：获得了除CPU之外的全部资源。 运行：被调度程序选中，使用CPU。（获得全部资源） 等待（阻塞）：等待某个事件的发生或受到某种制约 。,进程队列,系统经常把处于相同状态的进程链接在一起，称“进程队列“ 就绪队列：由若干就绪进程按一定次序链接起来的队列。 等待队列：把等待资源或等待某些事件的进程排列的队列

6、由于进程控制块能标志进程的存在和动态刻画进程的特性，因此，进程队列可以用进程控制块的连接来形成。,【思考题】,1. 有没有这样的状态转换，为什么？ 等待运行； 就绪等待,进程状态,作业的生命期,提交,作业,收容,执行,完成,运行,就绪,阻塞,二、进程控制,通过原语实现。原语是由若干机器指令构成的完成某种特定功能的程序段，其执行过程具有不可分割性。 创建原语 阻塞原语 运行态阻塞态 唤醒原语 阻塞态就绪态 撤销原语,第四节 处理器调度,一、高级调度（作业调度、宏观调度） 二、中级调度（交互调度） 三、低级调度（进程调度、微观调度）,进程状态,一、高级调度（作业调度）,1、功能 按照一定的调度算法

7、对外存上处于后备状态的作业进行选择； 给选中的作业分配内存、输入输出设备等必要的资源，并建立相应的进程； 作业运行完毕时，回收该作业占用的资源，输出必要的信息，撤销该作业的JCB与相应的进程。,2、调度时机 设m为系统支持的在主机上运行的最大作业数，n为在主机上运行的当前作业数。若nm，且存在后备作业，则启动作业调度。 当一作业运行终止而被撤消后，若存在后备作业，则立即启动作业调度。 在分时系统中，当一用户在某终端上通过交互会话被核准其注册的登录作业名及其口令后，立即启动调度。,一、高级调度（作业调度）,作业调度原则 依照什么原则选择作业进入内存运行,满足系统设计目标的要求 批处理：提高CPU

8、使用率 分时：响应时间在可以忍受的范围内 实时：保证及时响应 尽量提高系统的作业吞吐量，即运行尽量多的作业 尽量使处理机和外设都处于“忙”的状态，提高资源利用率 尽量做到公平合理地对待所有作业，提高用户满意度,3、常用的调度算法 先来先服务法FCFS：将用户作业按提交的顺序排成队列。 最短作业优先法SF：选择估计运行时间短的作业投入运行。 最高优先级法HPF：优先级高者优先调度。 最高响应比优先法HRN：同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入运行。 优先级 = 1+等待时间/要求运行时间,一、高级调度（作业调度）,二、中级调度,主要任务是按照给定的

9、原则和策略，将处于外存交换区中的那些重新具备运行条件的就绪进程调入内存，或将内存中处于阻塞状态的进程交换到外存交换区。,三、低级调度（进程调度）,1、功能 记录系统中所有进程的执行情况； 按照某种调度算法从就绪进程队列中挑选一个进程，将它移出就绪队列并置成执行态； 进行进程上下文切换，启动CPU执行该进程； 当进程需要放弃使用CPU时，收回CPU，将CPU有关寄存器的内容送入该进程的进程控制块内的相应单元，从而使该进程让出CPU。,进程状态,三、低级调度（进程调度）,2、调度时机 进程被阻塞 时间片到 有更高优先级的进程要占用CPU,三、低级调度（进程调度）,3、常用的调度算法 先来先服务法F

10、CFS：将就绪进程按进入就绪状态的先后排成队列。 时间片轮转法RR：将所有就绪进程按先进先出原则排序，每个进程一次执行一个时间片。 最高优先级法HPF：优先级高者优先被调度。 多级反馈轮转法：就绪进程按优先级排队；每队有不同的时间片；进程在当前队列执行一个时间片后，若没有执行完则进入下一级队列末尾；高优先级队列优先执行。,一级轮转队列 时间片 0.02秒,二级轮转队列 时间片 0.2秒,三级轮转队列 时间片 2秒,进程1,进程2,进程3,进程2,进程3,进程4,进程5,进程2,进程3,进程5,结束,结束,回想一下,作业的概念 作业的定义、组成、 JCB、状态 进程的概念 进程的定义、PCB、进

11、程与程序 进程状态及进程控制 进程状态及转换、进程队列、进程控制 处理机调度 高级调度、低级调度、调度算法,多道程序并发出现的问题,进程的同步与互斥 死锁,第五节 进程的同步和互斥,一、相关概念 二、信号量和P、V原语 三、用P，V原语实现进程互斥 四、用P，V原语操作实现简单同步 五、P，V原语在进程同步/互斥问题中的应用,一、相关概念,临界资源：一次只允许一个进程使用的资源。 临界区：在每个进程中，访问临界资源的那段程序称为临界区。,一、相关概念,间接制约与互斥：由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称并发进程间的间接制约。并发进程之间的间接制约关系称为进程的

12、互斥。,例,人行道地段互斥,例,X=COUNT X=X+1 COUNT=X,Y=COUNT Y=Y+1 COUNT=Y,临界区,进 程 A,进 程 B, , , , ,若进程A与B对公共变量COUNT进行互斥操作，最终实现COUNT增加2。,临界区,一、相关概念,直接制约与同步：,电子邮件信箱,发送进程 A,接收进程 B,当信箱满时，发送进程只有等待接收进程取走信件，当信箱空时，接收进程必须等待发送进程发送信件。,一、相关概念,直接制约与同步：一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的直接制约。进程因直接制约而进行互相合作、互相

13、等待并按一定速度执行的过程称为进程间的同步。 具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态,同步互斥问题的解决方法 P-V操作原语 荷兰计算机科学家迪克斯特拉(Dijkstra)发明,对每一个临界资源设置一个信号量，初始化后，只能通过P操作和V操作来访问信号量,P(Passeren)荷兰语“通过“ V(Vrijgeven)荷兰语“释放“,人行道地段互斥,二、信号量和P，V原语,1.信号量S：是一个整型变量 S0时，表示该类临界资源的可用个数。 S0时，表示等待使用该类临界资源的进程个数。 信号量只能通过P操作和V操

14、作来访问。,P操作记为 P(S)，其中S为一信号量，其执行顺序完成以下两个动作： （1） S=S1，表示申请使用一个资源； （2） 若S0，表示系统中有资源可用，现进程可继续执行。 （3） 若S0，表示系统中没有可用资源，则置该进程阻塞状 态，到S信号量 的队列中去等待，直到其他进程在S上执 行V操作释放它为止。,2. P原语,S0时，表示该类临界资源的可用个数。 S0时，表示等待使用该类临界资源的进程个数。,进程状态,V操作记为 V(S)，其中S为一信号量，其执行顺序完成以下两个动作： （1） S=S+1，表示释放一个资源； （2） 若S0，表示系统中没有等待该资源的进程，现进程可继续执行。

15、 (3) 若S0，表示系统中有等待该资源的进程，则唤醒S信号量队列中的第一个进程，使其插入到就绪队列，继续执行现进程。,3 .V原语,S0时，表示该类临界资源的可用个数。 S0时，表示等待使用该类临界资源的进程个数。,进程状态,三、用P，V原语实现进程互斥,Y=COUNT Y=Y+1 COUNT=Y,临界区,V(S),P(S),进程B,X=COUNT X=X+1 COUNT=X,临界区,V(S),P(S),进程A,S=1,实现进程互斥,P操作,V操作,A: X=COUNT; B: Y=COUNT; A: X=X+1; COUNT=X; B: Y=Y+1; COUNT=Y;,进程P1 L1:P(

16、s) 获取信息 ,进程P2 产生信息 L2:V(s) ,同步条件,S=0,同步点,四、用P，V原语操作实现简单同步,1.用P，V操作描述前趋关系,五、P、V原语在进程同步/互斥问题中的应用,int f2=0,f3=0,f4=0,f5=0,f6=0; main() cobegin P1();P2();P3();P4();P5(); P6(); coend ,P1() . v(f2);v(f3); P2() p(f2); . v(f4);v(f5); P3() p(f3); . v(f6); ,P4() p(f4); . v(f6); P5() p(f5); . v(f6); P6() p(f6)

17、; p(f6); p(f6) .; ,五、P、V原语在进程同步/互斥问题中的应用,2.生产者消费者问题,同步问题： 1.只要缓冲池未满，生产者便可将消息送入缓冲池，否则等待。 2.只要缓冲池未空，消费者便可从缓冲池中取走一个消息，否则等待。,互斥问题： 1.生产者与生产者之间、消费者与消费者之间互斥访问缓冲池。 2.生产者和消费者之间互斥访问缓冲池。,生产者与消费者之间的同步与互斥问题,互斥信号量S：初值为1，表示没有进程进入临界区。 计数信号量S0：初值为0，表示产品数目。 计数信号量Sn：初值为n，表示缓冲区中空位置个数。,为实现生产者与消费者的同步与互斥，设三个信号量：,同步互斥算法：,

18、互斥信号量S=1，互斥信号量。 计数信号量S0=0，表示产品数目。 计数信号量Sn=n，表示缓冲区中空位置个数,采用时间片轮转法：,Sn=n,t=0,S0=0,S=1,同步互斥算法：,采用时间片轮转法：,Sn=n-1,t=1,S0=0,S=1,互斥信号量S=1，互斥信号量。 计数信号量S0=0，表示产品数目。 计数信号量Sn=n，表示缓冲区中空位置个数,同步互斥算法：,采用时间片轮转法：,Sn=n-1,t=2,S0= -1,S=1,阻塞,互斥信号量S=1，互斥信号量。 计数信号量S0=0，表示产品数目。 计数信号量Sn=n，表示缓冲区中空位置个数,同步互斥算法：,采用时间片轮转法：,Sn=n-

19、1,t=3,S0= -1,S=0,阻塞,互斥信号量S=1，互斥信号量。 计数信号量S0=0，表示产品数目。 计数信号量Sn=n，表示缓冲区中空位置个数,同步互斥算法：,采用时间片轮转法：,Sn=n-1,t=4,S0=0,S=0,阻塞,互斥信号量S=1，互斥信号量。 计数信号量S0=0，表示产品数目。 计数信号量Sn=n，表示缓冲区中空位置个数,同步互斥算法：,采用时间片轮转法：,Sn=n-1,t=5,S0=0,S= -1,阻塞,互斥信号量S=1，互斥信号量。 计数信号量S0=0，表示产品数目。 计数信号量Sn=n，表示缓冲区中空位置个数,同步互斥算法：,采用时间片轮转法：,Sn=n-1,t=6

20、,S0=0,S=0,阻塞,互斥信号量S=1，互斥信号量。 计数信号量S0=0，表示产品数目。 计数信号量Sn=n，表示缓冲区中空位置个数,同步互斥算法：,采用时间片轮转法：,Sn=n,t=7,S0=0,S=0,互斥信号量S=1，互斥信号量。 计数信号量S0=0，表示产品数目。 计数信号量Sn=n，表示缓冲区中空位置个数,同步互斥算法：,采用时间片轮转法：,Sn=n-1,t=8,S0=0,S=0,互斥信号量S=1，互斥信号量。 计数信号量S0=0，表示产品数目。 计数信号量Sn=n，表示缓冲区中空位置个数,同步互斥算法：,采用时间片轮转法：,Sn=n-1,t=9,S0=0,S=1,以此循环往复,

21、互斥信号量S=1，互斥信号量。 计数信号量S0=0，表示产品数目。 计数信号量Sn=n，表示缓冲区中空位置个数,练习,在用信号量实现对临界资源的互斥访问时，若信号量的初值是2，当前值是-1，表示有 个进程等待使用该资源。,答案：1,设有三个进程互斥地使用两台打印机，则用P、V操作管理时信号量S的可能取值为_。,答案： -1，0，1，2,练习：,当有n个并发进程共享某个临界资源时，互斥信号量的取值范围是 。 A -11 B -1(n-1) C - (n-1) 1 D - (n-1) (n-1),答案:C,第六节 死锁问题,一、死锁的概念 二、死锁产生的原因 三、死锁产生的必要条件 四、死锁的排除

22、方法,一、死锁的概念,日常生活中的死锁,在计算机系统中的死锁,死锁是指两个或多个进程无休止地等候着永远不会出现的事件而发生的一种状态 。,二、死锁产生的原因,系统资源不足 进程推进的顺序不当,进程1 进程2 申请R1 申请R2 申请R2 申请R1 释放R1 释放R2 释放R2 释放R1,三、死锁产生的必要条件,所涉及的资源是非共享的（互斥条件） 进程在等待新资源时,继续占用已分配的资源（请求和保持条件） 一个进程占有的资源不能被别的进程强行攻占（不剥夺条件） 前一个进程获得的资源正是后一个进程所请求的,从而形成一个进程的循环链（环路等待条件）,四、死锁的排除方法,预防 避免 检测和恢复,四、死

23、锁的排除方法,1. 死锁的预防 在系统运行之前就采取措施，即在系统设计时确定资源分配算法，消除发生死锁的任何可能性。 只要破坏任一必要条件，死锁就不会产生 打破第二条：采用资源一次性分配策略 。 每个进程必须一次性申请它所要求的资源。 打破第三条：采用资源暂时释放策略 。 申请不到资源，则释放全部资源。 打破第四条：采取资源顺序使用法 。 系统中的所有资源都赋予唯一的编号，每个进程只能按编号的升序申请资源。即对于同一个进程来说，它一旦申请了一个编号为i的资源，就不允许再申请其编号在i前面的资源,1输入机，2打印机，3穿孔机，4磁带机，5磁盘,2. 死锁的避免 允许死锁产生的四个必要条件存在，当

24、系统有可能产生死锁时，小心地避免。,通常采用的方法是安全状态机制，只要系统不进入不安全状态，就不会发生死锁。避免死锁就是要使系统不进入不安全状态。 常用的避免死锁算法是Dijkstra的银行家算法。,四、死锁的排除方法,银行家算法,“银行家贷款问题“:设有一银行，将固定数量的共享资金提供给一定数量的客户借用，银行提出如下规定: (1) 每个客户必须预先提出自己的最大借款额，这个最大借款额不能超过银行的共享资金总数。 (2) 每个客户可以分期借款，每次只能借一万元。 (3) 银行对于客户的借款要求，要么立即满足，要么让其等待一段有限的时间。 (4) 客户借款数达到其预先提出的最大借款额后，必须在

25、有限的时间内一次性完成对银行的还款。,安全状态,如果银行在某一时间内能够使所有的客户在有限的时间内借走并且还清借款，则称银行处于安全状态。 “银行家算法“就是用于决定是否立即贷款给客户，以确保银行处于 安全状态。,银行家算法,例：某银行资金总数10万元，甲、乙、丙申请贷款总数分别为8、3、9万元,银行家算法,我们把银行换成操作系统，共享资金换成资源，借款客户换成请求资源 的进程，于是发现完全可以借助于“银行家算法“的原理安全地分配资源。,关于“避免死锁”的讨论,优点：允许死锁的必要条件存在，比预防死锁的条件放松了，资源利用率提高 要求资源数量固定不变，难以做到！ 要求用户数量固定不变，难以做到

26、！ 只能保证有限时间内得到满足！ 要求用户事先说明其最大的资源需求，困难！,3. 死锁的检测 允许死锁的产生，每隔一段时间进行检测，若存在死锁，则即决之。 可以通过化简资源分配图解决。,四、死锁的排除方法,资源分配图表示系统运行中某一时刻进程占有的资源以及需要的资源情况。,P2,P1,R2,R1,请求边 P1请求一个资源R2,分配边 已分配给P2一个R2资源,一类资源及个数,进程,化简算法: 从资源分配图中找到既不阻塞又不孤立的进程Pi。表明Pi可以获得所需的资源运行到终点，最后释放其占有的资源。也即相当于在图上消去Pi的所有请求边和分配边，成为孤立结点。 进程Pi释放的资源可能唤醒某些因等待

27、该资源而阻塞的进程Pj，Pj运行完毕又释放其占有的资源，成为孤立结点。 实施上述一系列简化步骤后，若能消去图中所有的边，则称该图是可以完全化简的;否则为不可完全化简的。,P2,P1,R2,R1,P1已得到两个R1资源现请求一个资源R2 能分配,P2,P1,R2,R1,消去P1的所有请求边和分配边，成为孤立结点。,P2,P1,R2,R1,释放其占有的资源R1, 唤醒P2,P2,P1,R2,R1,死锁定理：系统在某一特定状态下死锁的充要条件是：当且仅当某一状态下的资源分配图是不可完全化简的。,4. 死锁的解除 允许死锁的产生，每隔一段时间进行检测，若存在死锁，则即决之。 撤销进程。按某种次序强行从

28、系统中撤销一个或多个卷入死锁的进程，收回它们的资源，直到有足够的资源可供其他进程执行完毕。 挂起进程。使用挂起/激活机构挂起一些进程，暂时剥夺它们占有的资源，以解除死锁，待以后条件满足后再激活被挂起的进程。,四、死锁的排除方法,解决死锁方法,预防：在系统运行之前就采取措施，严格防止死锁的产生。方法为：破坏死锁产生的四个必要条件之一。 一次性分配资源。 申请不到资源，则释放全部资源。 资源编号，从低到高申请。 避免：允许死锁产生的四个必要条件存在，当系统有可能产生死锁时，小心地避免。 银行家算法。 检测和恢复：允许死锁的产生，每隔一段时间进行检测，若存在死锁，则即决之。 化简资源分配图。 撤销进

29、程。按某种次序强行从系统中撤销一个或多个卷入死锁的进程，收回它们的资源，直到有足够的资源可供其他进程执行完毕。 挂起进程。使用挂起/激活机构挂起一些进程，暂时剥夺它们占有的资源，以解除死锁，待以后条件满足后再激活被挂起的进程。,练习：,有相同的5个资源被4个进程共享，且每个进程最多需两个这样的资源就可以运行完毕。 试问系统是否会由于对于这种资源的竞争产生死锁？,练习：,计算机系统中共有N个进程,就绪进程最多有_,等待进程最多有_.,答案:N-1; N,回想一下,多道程序并行出现的问题 进程的同步与互斥 概念、解决同步互斥的软件工具（ P-V操作）、生产者消费者问题 死锁 产生死锁的原因、必要条件、解决死锁方法,作业,P174 9-10,