3.3 处理器管理
中央处理器(CPU)是计算机系统中负责运算与控制的部件,调入内存中的作业只有占有了CPU才能运行。在单CPU的系统中,要实现多道程序并发运行,一定要合理地分配CPU,使得从宏观上看各个程序都在随着时间向前推进。在这一部分将讨论三个问题:
(1)当多个用户把各自的作业提交给计算机后,操作系统如何对它们进行调度管理。
(2)已进入内存中的作业,如何对它们合理地分配CPU。
(3)如何解决多道程序并发运行时出现的同步、互斥与死锁问题。
3.3.1 基本概念与术语
1. 作业
作业是用户交给计算机运行的程序、数据及说明。一个作业可以分解成若干个作业步。
2. 进程
当系统将某一个用户程序调入内存运行时,称为进程。这是由于多道程序环境下实现资源共享和程序并发运行的需要,它具有以下的基本特性:
(1)动态特性 进程是程序的一次执行过程,具有“创建—执行—撤消”的生存周期。
(2)并发特性 内存中众多进程不仅可随机地并发产生和消亡,同时可以并行地活动。
(3)独立性 进程在逻辑上是独立的,在获得必须的资源后,可以按照各自目的,以不可预知的速度向前推行。
(4)相互制约性 由于共享资源和进程之间某些协同动作,有些进程间会有相互制约的关系。
因此程序是一种静态的观点,进程则反映了操作系统动态活动的内在本质。
3. 管态、目态
(1)管态 此时系统只执行造作系统的特权指令,不允许执行用户指令。
(2)目态 系统处于用户执行状态。
3.3.2 作业调度
作业调度主要是实现对作业的组织、输入/输出、调度和运行控制。不同的操作系统对作业有不同的处理方式,主要分为批处理作业和交互方式处理作业两类。
1. 批处理作业的管理
在批处理系统中,由于用户不能直接与计算机交互,因此在进入计算机系统之前,除了要准备好源程序和初始数据外,还必须用该操作系统提供的作业控制语言来书写作业控制说明书,规定如何控制作业运行。
(1)作业状态及转换
一个作业在它的生命周期内要经过提交、收容、执行、完成四个阶段,每一个阶段称为作业的一种状态。
为了描述和管理系统内的作业,还必须为每道作业建立一个专门的数据结构,称为作业控制块(JCB)它包含了系统对作业进行管理所必需的信息,作业管理就是对作业各个阶段进行宏观控制。
(2)作业调度
在批处理系统中,作业调度程序按照某种调度策略从收容状态队列中选择某些作业进入内存。调度的关键是在于确定调度算法,以获得一个较好的作业搭配,使得系统资源得到高效的利用。
衡量算法的性能指标有:
·周转时间 作业从进入系统直到完成所经历的时间。
·平均周转时间 被测定作业数(n)的周转时间平均值。
·系统吞吐量 系统在单位时间内平均完成的作业数。
(3)调度算法
作业调度算法很多,这里介绍几种常用的算法:
·先来先服务(FCFS)
按作业到达系统的先后次序调度它们运行。
·短作业优先(SJF)
选择运行时间较短的作业先运行。这样可使作业流的平均周转时间取值最小,但对长作业不公平。
·最高响应比优先(HRF)
响应比=等待时间/运行时间
优先选择响应比最大的作业,他兼顾了短作业与等待时间长的作业。
·优先数法
按操作员或用户指定的作业优先级高的作业首先运行。
实际系统中往往采用几种算法的组合形式,以提高系统的整体效率。
2.交互式作业管理
在分时系统中,用户通过终端和系统提供的终端命令语言向系统提供作业。作业的提交方式是由用户动态地提交,即每完成一个作业步动作后,系统给出相应的回答信息,用户继续提交下一个作业步,知道作业全部完成。由于系统对终端用户提交的每一作业步必须加以识别并立即解释执行,因此系统不再设置作业的收容状态,也不存在作业调度等问题。
有些系统同时支持批处理和分时功能,则用户可以提供任意一种类型的作业,其中交互式作业称为“前台”作业,批处理作业称为“后台”作业。
3.3.3 进程调度
进程调度的任务是控制、协调进程对CPU的竞争,按照一定的调度算法,使某一个就绪的进程得到CPU,转成运行状态。
1. 进程的状态及转换
一个进程在它的生命期内有三种基本状态:
就绪 进程具备运行条件,但尚未占用CPU;
运行 进程正在占用CPU;
等待(阻塞) 进程由于等待某一事件不能享用CPU。
当进程处于运行状态时,它是微观意义下的运行,而不管进程处于何种状态,只要它已开始执行而尚未结束执行,都是宏观意义下的运行。
和作业管理相似,当作业一旦进入内存构成进程后,系统为每个进程建立一个进程控制块(PCB),记录有关该进程的固有信息以及动态信息。
2.进程控制
操作系统必须提供一组与进程控制有关的原语(系统调用)供用户编程时调用。
(1)创建进程 为调用者动态创建一个进程。
(2)撤消进程 停止该进程运行,释放它所占有的资源。
(3)挂起进程 把该进程暂时置为阻塞状态。
(4)激活进程 把该进程从阻塞态改为就绪态。
3.进程调度
按照一定的调度算法,使某一就绪进程得到CPU,转换成运行状态。衡量调度算法的指标主要有:
·CPU利用率 CPU处于忙状态的时间与开机运行总时间的比值。
·等待时间 指在就绪状态中进程的等待时间。
·响应时间 指在分时系统中,用户在终端上发一条命令直到系统作出回答所需的时间。
4.调度算法
进程调度算法有些和作业调度相似,如先来先服务(FCFS)、短进程优先(SPF)、优先级调度等。还有适用于分时系统的轮转调度法。
·先来先服务 按进入就绪队列先后次序获取CPU,这是一种不可抢占的方式。
·短进程优先 根据下一次所需时间的长短,从就绪队列中选择运行时间最短的进程首先占有CPU。
·优先级调度 按进程的优先级高低确定占有CPU的次序。
·轮转调度法 进程先按FIFO规则排成队列,每次从队首取出一个进程分配CPU,并规定执行完一个时间片后便被剥夺,并被送到队尾,如此反复。
实际系统会根据不同的系统目标,结合各种算法特点采用相应的调度算法。
3.3.4 多道程序并发运行出现的问题
1.进程的同步与互斥
进程的同步:完成同一任务的进程间,由于需要在某些位置上协调它们的工作而互相等待与相互交换信息所产生的制约。
进程的互斥:进程之间因相互竞争使用独占型资源而产生的制约。
(1)临界区问题
一次仅允许一个进程使用的资源称为临界资源,各个进程必须互斥地执行的那种程序段称为临界区。对临界区的调度原则为:当没有进程在临界区时,允许一个进程立即进入;若已有一进程在临界区内,则其他需进入的进程必须等待,且必须在有限的时间内得到满足。
(2)原语
原语本身不是一条机器指令,而是由若干条指令组成的程序段,它是机器指令的扩充。它在进程管理中能完成某些特定的功能,例如前面提到的进程控制原语,以及后面将提到的P.V操作等。原语是在管态下运行,因此在执行中一次完成不能被打断。
(3)P.V操作
用常规的程序来实现进程间的同步和互斥关系需要复杂的算法,因此引入P.V操作,P.V操作都是原语,在执行期间是不可分割的。
(4)用P.V操作实现进程之间的互斥和同步
·实现互斥:令S初值为1,进程A,B竞争临界区的程序,可以写成:
进程A 进程B
P(S) P(S)
临界区 临界区
V(S) V(S)
·实现同步:设S1初值为n,表示缓冲区中有n个位置等待装入信息;S2初值为0,表示缓冲区中无信息可取。
进程A 进程B
P(S1) P(S2)
把信息送入缓冲区 从缓冲区取走信息
V(S2) V(S1)
在练习题中将提供一些采用P.V操作解决同步与互斥的习题,希望能通过分析这些例子,对解决操作系统内的同步、互斥问题有所启发。
2.死锁
(1)死锁的定义和必要条件
·死锁的定义 在一个进程集合中,若每个进程都在等待某些时间的发生,而这些事件又必须由这个进程集合中的某些进程来产生,则称该进程集合处于死锁状态。
·产生死锁的四个必要条件
①互斥 系统中必须存在互斥使用的资源。
②占有等待 进程已分配到了某些资源,但还须等待另外的资源,而对已分配到的资源并不释放。
③非剥夺 在出现死锁的系统中,一定存在有不可剥夺的资源,即在该进程未主动释放之前,其他进程不可夺走该资源。
④循环等待 形成一个处于等待状态的进程集合{P0,P1,…,Pn},其中Pi等待的资源被P(i+1)占有,Pn等待的资源被P0占有。
(2)死锁的预防
只要使死锁产生的四个必要条件之一不成立,死锁就不会出现。
(3)死锁的避免
死锁的避免是在系统运行过程中小心地避免死锁的最终发生。最著名的是银行算法。
安全状态:安全状态是指如果存在一个由系统中所有进程构成的序列{P0,P1,…,Pn},如果对于其中每一个进程Pi(1≤i≤n),它以后要申请的资源数量不超过系统中当前剩余的资源数量与所有进程Pj(j≤i)当前占有的资源量之和,则该进程序列称为安全序列,此状态为安全状态,安全状态是没有死锁的状态,而不安全状态不一定是死锁状态。
银行家算法是对系统中每一个进程发出的资源申请命令加以动态检查,如果发现若分配资源后系统将进入不安全状态,则不予分配。
(4)死锁的检测与解除
死锁的检测通常采用化简资源分配图的方法,其过程为:
·在图中找一个进程Pi,Pi的请求边均能立即满足。
·将Pi与其相连的边全部删去,继续寻找请求边满足的进程进行化简。
如果化简后所有进程都成了孤立点,就称为完全化简,无死锁现象;反之称为不完全化简,非孤立点的进程处于死锁状态。
一旦发生死锁应立即排除,以确保系统正常运行,常采用资源剥夺法和撤消进程法。