操作系统 第2章 处理机管理

第2章处理机管理计算机系统中，最宝贵的资源是CPU。为了提高它的利用率，需要引入多道程序设计的概念。当内存储器中同时有多个程序存在时，如果不对人们熟悉的“程序”概念加以扩充，就无法刻画多个程序共同运行时系统呈现出的特征。因此，在本章将给出操作系统中的重要概念：“进程”。它将是在多道程序运行环境下，系统资源分配和独立运行的基本单位。本章着重讲述四个方面的内容：退出（1）进程概念的引入；（2）进程的组成与管理；（3）处理机的调度算法；（4）处理机的二级调度与作业管理。2.1进程2.2进程控制块2.3进程的调度与管理2.4作业调度2.1进程2.1.1多道程序设计所谓“程序”，是一个在时间上严格有序的指令集合。程序规定了完成某一任务时，计算机所需做的各种操作，以及这些操作的执行顺序。在没有引入多道程序设计的概念之前，只要一提到程序，就表明它独占使用系统中的一切资源，如处理机（指它里面的指令计数器、累加器、各种寄存器等）、内存储器、外部设备以及软件等，没有其他竞争者与它争夺与共享。在单道程序设计环境下，系统具有如下特点：（1）资源的独占性：任何时候，位于内存中的程序可以使用系统中的一切资源，不可能有其他程序与之竞争。（2）执行的顺序性：由于内存中每次只有一个程序，因此各个程序是按次序执行的，即做完一个以后，再做下一个。绝对不可能出现在一个程序运行过程中，又夹杂进另一个程序执行的现象存在。图2-1(a)对程序执行的顺序性做出了解释。假定有三个程序，每个程序都是前后占用CPU执行一段时间，中间要求打印输出。具体是：程序A所需时间为（4，2，3），程序B所需时间为（5，4，2），程序C所需时间为（3，3，4）。不难看出，总共需要30个时间单位，才能把它们执行完毕。从横坐标上看，在时间区间（4~6）、（14~18）以及（23~26）中，CPU为了等待打印结束，在那里空闲等待。（3）结果的再现性：只要执行环境和初始条件相同，重复执行一个程序，获得的结果总是一样的。在多道程序设计环境下，内存中允许有多个程序存在，它们轮流地使用着CPU。这时，上述的三个特点就都荡然无存了。“资源的独占性”被打破了。比如，内存不再只由一个程序占用，而是被分配给若干个程序使用；又比如，原来内存中的程序进行输入/输出时，CPU就只能空转，以等待输入/输出操作的完成。现在，当程序A等待输入/输出操作完成时，就可以把CPU分配给内存中的另一个可运行的程序B去使用。这样，CPU在运行程序B，外部设备在为程序A服务。图2-1(b)中的时间区间（4~6）正好是这种情况。“执行的顺序性”被打破了。从图2-1(b)中可以看出，时刻6程序A打印完毕，按说应该继续执行，但是CPU已经分配给了程序B，因此程序A只能等到时刻9在程序B请求打印时，才能重新获得CPU。这就是说，在程序A执行过程时，夹杂进了程序B的执行，打破了程序执行的顺序性，内存中多个程序的执行过程被交织在一起。从宏观上看，好几个程序都在运行着（比如，在时间区间4~12，程序A和程序B都在做着自己的事情；在时间区间12~17，程序B和程序C都在做着自己的事情）；而从微观上看，每个时刻CPU只能为一个程序服务，因此运行着的程序都是走走停停。总之，在多道程序设计环境下，各个程序的执行已经不再可能完全依照自己的执行次序执行了。“结果的再现性”被打破了。举例来说，为了了解某单行道的交通流量，在路口安放一个监视器，功能是有车通过该路段时，就向计算机发送一个信号。为计算机系统设计两个程序：程序A的功能是接收到监视器的信号时，就在计数单元COUNT上加1；程序B的功能是每隔半小时，将计数单元COUNT的值打印输出，然后清零。COUNT初始时为0，两个程序的描述如图2-2所示。因为现在是多道程序设计环境，程序A和程序B同时在内存。当然，内存中可能还会有其他的程序存在。由于执行的顺序性被打破了，这些程序的执行过程被交织在一起，没有任何规律可循。为了突出，单单挑出程序A和程序B来研究。在它们之间，不排除会有这样的执行顺序发生：A1A2B1B2A1A2B3，即在程序B做了B1和B2后，没有直接执行B3，而是中间插入了程序A的两个操作，这就出现了问题。假定系统在发生这一执行顺序前，情况一直正常，计数器COUNT里的值是9。现在由A1收到监视器发来的第10辆车通过的信息。于是由A2在COUNT上完成加1的操作，使得计数器COUNT取值为10。紧接着在B1延迟半小时后，由B2将COUNT中的10打印输出。这时又做A1，它此时收到的是第11辆车到达的信息，通过A2，COUNT里成为11。这时做B3，把COUNT清零。结果该系统把第11辆车漏掉了，少计算了一辆车。要重现这一情况是困难的，因为无法清楚何时会出现这种执行顺序，这恰好说明了结果再现性的不复存在。2.1.2进程的定义“进程（Process）”是现代操作系统设计中的一个基本概念，也是一个管理实体。它最早被用于美国麻省理工学院的MULTICS系统和IBM的CTSS/360系统，不过那里称其为“任务（Task）”，其实是两个等同的概念。由于要通过进程概念来描述多道程序设计系统中程序的并发活动，程序对资源的共享和竞争，而这一切又千变万化，具有极大的复杂性。因此迄今为止对这一概念还没有非常确切和统一的描述。有的人称“进程是任何一个处于执行的程序”；有的人称“进程是可以并行执行的计算部分”；有的人称“进程是具有一定独立功能的程序在某个数据集合上的一次运行活动”；也有的人称“进程是一个实体。当它执行一个任务时，将要分配和释放各种资源”。综合起来看，可以从如下3个方面来描述进程：（1）进程是程序的一次运行活动。（2）进程的运行活动是建立在某个数据集合之上的。（3）进程要在获得资源的基础上从事自己的运行活动。2.1.3进程的特征由于进程是程序的一次执行过程，因此程序是进程赖以存在的基础。没有程序，犹如无米之炊，是根本谈不上进程的。这就是说，进程与程序之间有一种必然的联系，但进程又不等同于程序，它们是两个完全不同的概念。进程的主要特征以及与程序的区别有如下几个方面。（1）“进程”是一个动态的概念。既然进程强调的是程序的一次“执行”过程，所以它是一个动态的概念；程序是一组有序指令的集合，在多道程序设计环境下，它不涉及“执行”，因此是一个静态的概念。可以这么来理解，一套电影拷贝相当于一个程序，它可以长期保存；该拷贝在电影院的一次放映，就相当于一个进程。（2）不同进程可以执行同一个程序。从进程的定义可知，区分进程的条件一是所执行的程序，二是数据集合，因此，即使多个进程执行同一个程序，只要它们运行在不同的数据集合上，那么它们就是不同的进程。例如，一个编译程序同时被多个用户调用，各个用户程序的源程序是编译程序的处理对象（即数据集合）。于是系统中形成了一个个不同的进程，它们都运行编译程序，只是每个加工的对象不同。由此可知，进程与程序之间，不存在一一对应的关系。（3）每一个进程都有自己的生命期。既然进程的本质是程序的一次执行过程，因此当系统要完成某一项工作时，它就“创建”一个进程，以便能去执行事先编写好的、完成该工作的那段程序。程序执行完毕，完成了预定的任务后，系统就“撤消”这个进程，收回它所占用的资源。一个进程创建后，系统就感知到它的存在；一个进程撤消后，系统就无法再感知到它。于是，从创建到撤消，这个时间段就是一个进程的“生命期”。（4）进程之间具有并发性。在一个系统中，同时会存在多个进程。于是与它们对应的多个程序同时在系统中运行，轮流占用CPU和各种资源。这正是多道程序设计的初衷，说明这些进程在系统中并发执行着。（5）进程间会相互制约。由于进程是系统中资源分配和运行调度的单位，因此在对资源共享和竞争中，必然会相互制约，影响了各自向前推进的速度。2.1.4进程的基本状态进程间由于共同协作和共享资源，导致生命期中的状态不断发生变化。比如一个进程在等待输入/输出的完成，这时它不能继续运行。另一种情形是一个进程是可以运行的，但由于操作系统把处理机分配给了别的进程使用，于是它也只能处于等待。只有当前占有CPU的进程，才真正在处于运行。于是，进程在其生命期内，可以处于下面3种基本状态之一。（1）运行状态：获得CPU的进程处于此状态，其对应的程序正在处理机上运行着。（2）阻塞状态：进程为了等待某种外部事件的发生（如等待输入/输出操作的完成，等待另一个进程发来消息），暂时无法运行。阻塞状态也称等待状态或挂起状态。（3）就绪状态：已具备运行所需的一切条件，只是由于别的进程占用处理机而暂时无法运行。一个进程的状态，可以随着自身的推进和外界环境的变化而变化，从而使其从一种状态变迁到另一种状态。图2-3是进程状态变迁图，箭头表示的是状态变迁的方向，旁边标识的文字是引起这种状态变迁的原因。从图2-3看出，一个正处于运行状态的进程，比如会由于提出输入/输出请求而使自己的状态变成为阻塞。由于这是进程自己提出的请求，“知道”到这里就会阻塞，以便等待输入/输出的完成，所以这属于进程自身推进过程中引起的状态变化。在输入/输出操作完成后，会使某个进程的状态由阻塞变为就绪。由于被阻塞的进程并不知道它的输入/输出请求何时能够完成，因此这属于由于外界环境的变化而引起的状态变化。处于就绪状态与阻塞状态的进程，虽然都“暂时无法运行”，但两者有着本质上的区别。前者已做好了运行的准备，只要获得CPU就可以投入运行；而后者要等待某事件（比如输入/输出）完成后才能继续运行，因此即使此时把CPU分配给它，它也无法运行。2.2进程控制块2.2.1进程的三个组成部分一个进程创建后，需要有自己对应的程序以及该程序运行时所需的数据，这是不言而喻的。但仅有程序和数据还不行，我们知道，进程在其生命期内是走走停停，停停走走的，暂时停下来以后，至少应该要有一个属于它专用的地方，来记录它暂停时的运行现场。否则，它再次被投入运行时，就无法从上次被打断的地方继续运行下去。因此，为了管理和控制进程，系统在创建每一个进程时，都为其开辟一个专用的存储区，用以随时记录它在系统中的动态特性。而当一个进程被撤消时，系统就收回分配给它的存储区。通常，把这一存储区称为该进程的“进程控制块”PCB（ProcessControlBlock）。由于PCB是随着进程的创建而建立，随着进程的撤消而取消的，因此系统是通过PCB来“感知”一个个进程的，PCB是进程存在的唯一标志。这样，在计算机系统内部，一个进程要由3个部分组成：程序、数据集合以及进程控制块PCB。图2-4表示了进程3个组成部分的可能关联情形。其中图2-4(a)表示程序和数据集合存放在一个连续存储区的情形；图2-4(b)表示程序和数据集合在不连续存储区的情形；图2-4(c)表示同一个程序运行在不同数据集合上时，形成两个进程的情形。2.2.2进程控制块（PCB）的内容随操作系统的不同，PCB的格式、大小以及内容也不尽相同。一般地，在PCB中大致应包含如图2-5所示的4方面的信息。表2-1是实时操作系统RTOS中PCB的具体构成，每个PCB占用22个字节的存储区，两个字节为一个字，各字的内容和作用如下：（1）TPC：随时记录该进程所对应的程序执行地址。最初它是程序的入口地址，随后是进程暂停时的断点地址。（2）TAC0~TAC3：该操作系统运行的主机共有4个工作寄存器AC0~AC3。进程程序暂停执行时，就将工作寄存器的当前内容保存在此，所以这4个字加上TPC就构成了进程PCB中的现场保护区。（3）TPRST：记录该进程运行过程中的状态变化和进程的优先数。（4）TDELAY：当要主动让进程推迟一段时间再执行时，在此存放所需要延迟的时间间隔。（5）TLNK：这是PCB的队列指针，里面总是存放队列中下一个进程的PCB地址。若该PCB位于队列尾，则TLNK=-1。（6）TUSP：该进程专用的堆栈指针，是进程程序运行时的工作区。（7）TELN：若本PCB不够使用时，可以开辟一个PCB扩展区，并用这个指针指向扩展区的起始地址。（8）TID：进程的标识，也就是该进