第8章处理器管理

1、第8章处理器管理本章基本内容与要求基本内容作业的概念进程的概念进程状态及进程控制处理机调度进程的同步和互斥死锁问题要求掌握进程的概念及作用掌握进程的控制与调度方法掌握进程的同步与互斥、P、V操作掌握死锁的概念和死锁的解决方法 8.1 作业的概念一、作业的定义作业是用户在一次算题过程中或一个事务处理中要求计算机系统所做的工作的集合。二、作业的组成作业由程序、数据和作业说明书组成 。三、作业的状态1）提交状态2）收容状态 3）执行状态 4）完成状态8.2 进程的概念一、程序的顺序执行 二、程序并发执行与资源共享 三、并发执行的特征 四、进程的引入和描述五、进程的状态及其变迁六、进程的组成8.2 进

2、程的概念一、程序的顺序执行程序：一个在时间上按严格次序，前后相继的操作序列。体现的是程序员要求的顺序步骤。顺序执行：一个具有独立功能的程序独占处理机直至得到最终结果的过程。1.例：S1： a=x+y S2： b=a-5 S3： c=b+12. 特点：顺序性：上一条指令执行结束是下一条指令开始的充要条件。封闭性：由于资源独占，执行结果取决于程序本身，由给定初始条件决定，不受外界影响。可再现性：同一数据集上重复执行同一程序，结果相同，与执行速度无关。OIC S1S2S3二、程序并发执行和资源共享1.并发执行：逻辑上独立的一组程序在执行时间上相互重叠在多处理机的情况下，若干个程序在各自处理机上运行，

3、其执行的时间是重叠的；在单处理机的情况下，这些并发程序按给定的时间片交替地在处理机上执行为了提高系统处理能力和资源利用率而采取的一种在某一时段同时操作的技术。并发：几道程序分时地运行在同一个处理机(CPU)上；并行：几道程序同时在不同的处理机(CPU)上执行。8.2 进程的概念二、程序并发执行和资源共享2.例：输入程序、计算程序、打印程序之间，存在有IiCiPi的前趋关系，但不存在PiIi+1关系，这样他们可以并发执行。二、程序并发执行和资源共享S1: a:=x+2S2: b:=y+4S3: z:=a+bS4: w:=z+9三、并发执行的特征1. 资源的争夺与共享多个并发程序申请同一资源资源动

4、态分配，资源状态由多道程序活动共同决定程序运行不再具有封闭性和可再现性2.并发执行的程序之间的相互约束性共享计算机的资源而相互制约互相通信协作完成同一任务,相互依赖相互制约活动规律（间断性）：执行暂停执行8.2 进程的概念8.2 进程的概念3. 特性间断性：程序具有“执行-暂停-执行”规律；失去封闭性：系统资源的状态由多个程序决定，因此，程序的执行受其它程序的影响。不可再现性：执行结果与并发程序的相对速度有关。结论：程序的概念已无法描述多道环境中程序动态执行过程中的并发活动引入一个新的概念来描述，这就是进程四、进程的引入和描述1. 进程：程序在并发环境中的执行过程。是系统进行资源分配和调度的一

5、个独立基本单位和实体进程是程序的一次执行进程是可以和别的计算并发执行的计算进程可以定义为一个数据结构，能在其上进行操作进程是一个程序及其数据在处理机上顺序执行时所发生的活动。进程是程序在一个数据集合上允许过程，是系统资源分配和调度的一个独立单位。可并发执行的程序在一个数据集合上的执行过程。8.2 进程的概念四、进程的引入和描述2.进程与程序间的区别和联系1）区别：程序：是一组有序的指令，是一种静态的概念；(剧本)进程：是一次运行的活动，是动态的概念 (演出) 一个进程可以执行一个或多个程序反之一个程序也可能被多个进程执行程序可作为一种资源，以文件的形式长期保存；而进程只是一次执行过程，具有生命

6、期2）联系进程不能脱离具体程序而虚设程序规定了相应进程所要完成的动作四、进程的引入和描述3. 进程的基本特征1)动态性程序的一次执行过程，具有生命期由系统创建并独立的执行，执行过程中可能被暂时挂起，条件满足时又继续执行，直至完成而被撤销。2)并发性不同进程的动作在时间上可以重叠;由于共享资源，进程间相互约束。3)独立性程序和数据集合的实体；系统分配资源,处理机调度运行的基本单位；各进程间相互独立4)异步性各进程按各自独立的，不可预知的速度异步向前推进。五、进程的状态及其变迁进程的基本状态运行态：指进程已获得处理机，其程序正在执行。进程数CPU数就绪态：当进程已分配到除CPU以外的所有必要资源，

7、一旦获得CPU，便可立即执行。等待（封锁）态：进程因等待某个事件的发生而暂停执行创建状态：一个进程刚建立，还未进入就绪态。终止状态：一个进程已经正常或异常结束，被移除就绪队列但尚未撤销。8.2 进程的概念计算机软件技术基础进程管理五、进程的状态及其变迁2. 进程状态转换就绪执行等待进程调度时间片到等待事件发生事件发生获得资源提交撤消完成六、进程的组成组成： 程序、数据集合、PCB统称为进程映象。程序：描述进程所要完成的功能；数据集合：程序运行所需数据和工作区；PCB：描述进程的外部特征以及与其它进程的通信关系的数据结构。系统定义的一种数据结构，是进程存在的唯一标志。描述和记录进程执行的情况和状

8、态变化。便于系统控制和描述进程的活动过程。PCB程序数据集常驻内存8.2 进程的概念2. PCB的作用 OS是根据PCB来对并发进程执行的进程实施控制和管理。 (1)保存进程的ID、进程状态、优先级。 (2)现场保存与恢复 (3)OS根据PCB对进程实施调度。新进程：OS为该进程创建一个PCB结束： OS回收该进程的PCB。六、进程的组成3. PCB的内容包含的信息类型和数量随操作系统而不同一般分为调度信息和现场信息两个部分1）调度信息：描述进程的当前状况； 进程名、当前状态、优先级、资源清单、 家族关系、队列指针 等，供进程调度时使用。2）现场信息：刻划进程运行的情况进程在运行过程中会改变的

9、寄存器，如程序状态字，指针，地址寄存器。一旦进程的执行过程被中断，必须立即将中断时的内容记入现场信息。六、进程的组成4. PCB的物理组织方式PCB表：所有PCB按一定的方式组织起来的结构。1）顺序表：由OS预先分配空间，在内存中顺序地存放每个PCB。优点：简单易实现，不必进行复杂的申请/释放。缺点：限制了系统中同时存在的进程数；降低了调度效率（扫描整个表）；内存浪费（用户少）2）链接表：按不同状态进程的PCB形成不同单链表，各单链表内按FIFO运行；优点：进程数目可随机应变；缺点：算法复杂。六、进程的组成8.3 进程的同步和互斥一、相关概念二、信号量和P、V原语三、用P、V原语实现进程互斥

10、四、用P、V原语操作实现简单同步 五、P、V原语在进程同步/互斥问题中的应用 一、相关概念临界资源：一次只允许一个进程使用的资源。临界区：在每个进程中，访问临界资源的那段程序称为临界区。 直接制约与同步：一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的直接制约。进程因直接制约而进行互相合作、互相等待并按一定速度执行的过程称为进程间的同步。间接制约与互斥：由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称并发进程间的间接制约。并发进程之间的间接制约关系称为进程的互斥。例 X=COUNTX=X+1 COUNT=XY=C

11、OUNTY=Y+1 COUNT=Y临界区进 程 A进 程 B 若进程A与B对公共变量COUNT进行互斥操作，最终实现COUNT增加2。临界区A: X=COUNT;B: Y=COUNT;A: X=X+1; COUNT=X;B: Y=Y+1; COUNT=Y; 若A与B按右面顺序推进，结果COUNT只实现增加1。二、信号量和P，V原语 1.信号量S：是一个整型变量S0时，表示该类临界资源的可用个数。S0时，表示等待使用该类临界资源的进程个数。 信号量只能通过P操作和V操作来访问。2. P原语(1)信号量减1；(2)若信号量减1后仍大于或等于零，则进程继续执行。(3)若信号量减1后小于0，则该进程被

12、阻塞后进入与该信号相对应的等待队列中，然后转进程调度程序，调度另一个处于就绪状态的进程占用CPU。二、信号量和P，V原语 3. V原语(1)信号量加1；(2)若信号量相加结果大于零，说明没有其它进程等待使用该资源，则当前进程继续执行。(3)信号量相加结果小于或等于零，说明此时尚有其它进程等待使用该资源，则从该信号的等待队列中唤醒一个等待进程，然后再返回原进程继续执行或转进程调度。三、用P，V原语实现进程互斥 P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)Y=COUNTY=Y+1COUNT=Y临界区V(S)P(S)进程BX=CO

13、UNTX=X+1COUNT=X临界区V(S)P(S)进程AS=1 进程P1 L1:P(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;void main() cobegin P1();P2();P3();P4();P5(); coend P1() . v(f2);v(f3); P2() p(f2); . v(f4);v(f5); P3() p(f3); . v(f6); P4() p(f4); . v(f6);

14、P5() p(f5); . v(f6); P6() p(f6); 123NP1P2P3PmC1C2C3Cn有 界 缓 冲 池生产者消费者五、P、V原语在进程同步/互斥问题中的应用2.生产者消费者问题 同步条件：当有界缓冲区中至少有一个单元是满的时，消费者才能接收数据；当有界缓冲区中至少有一个单元是空的时，生产者才能发送数据 。互斥条件：有界缓冲区是临界资源，必须互斥使用 。设置信号量：互斥信号量Mutex：初值为1。 同步信号量Full ：初值为0。 同步信号量Empty ：初值为n。 生产者进程P1P(Empty )P(Mutex)缓冲区 产品V(Full)V(Mutex)消费者进程C1P(

15、Full)P(Mutex)取产品V(Empty )V(Mutex)8.4 处理器调度一、高级调度（作业调度、宏观调度）二、中级调度（交互调度）三、低级调度（进程调度、微观调度）四、三级调度之间的关系一、高级调度 1、功能 按照一定的调度算法对外存上处于后备状态的作业进行选择； 给选中的作业分配内存、输入输出设备等必要的资源，并建立相应的进程； 作业运行完毕时，回收该作业占用的资源，输出必要的信息，撤销该作业的JCB与相应的进程。 2、调度时机 设m为系统支持的在主机上运行的最大作业数，n为在主机上运行的当前作业数。若n后台)选择各队列合适的调度算法各队列间调度方式固定优先级的抢占式调度各队列间

16、按规定占用CPU时间比例调度4.性能分析:比前面任何算法都科学合理,但开销大。8.5 常用调度算法六、多级反馈队列调度算法思想：按照一定的原则，设置多个就绪队列，每个队列按FCFS原则排列，各队列之间的进程享有不同的优先级和时间片,但同一队列内优先级和时间片相同,一个进程在它执行结束之前，可能需要反复多次通过反馈循环执行。特点：允许作业（进程）在各队列间移动。8.5 常用调度算法六、多级反馈队列调度算法3. 实现1）置多个就绪队列,赋予不同的优先级和时间片2）当一个新进程进入内存后,首先将它放入第一队列末尾,按FCFS原则调度3）当进程在一个时间片结束时未完成,将其转入下一个队列末尾； 4）仅