操作系统学习第二章

第二章进程管理在多道程序批处理系统和分时系统中，程序并不能独立运行，作为资源分配和独立运行的基本单位是进程。本章主要内容1.进程的概念2.进程的描述：PCB、状态、3.进程的控制：创建、撤消、阻塞、唤醒…4.进程的低级通信：互斥、同步、P/V操作5.进程的高级通信：消息传递6.进程的调度：分配CPU给某一进程7.死锁：多进程竞争有限资源一、程序的顺序执行程序的顺序执行：在任何时刻，机器只执行一个操作，只有在前一个操作执行完后，才能执行后继操作。[例]作业i的输入操作、计算操作和打印操作分别用Ii、Ci、Pi表示。则顺序执行过程为：2.1进程的引入和概念I1I2I3P1C1P2P3C2C3程序顺序执行的特点：顺序性：在任何时刻，机器只执行一个操作，只有在前一个操作完成后，才进行下一个操作。封闭性：程序在运行时独占全机资源。因此，这些资源的状态只能由运行的这个程序决定和改变。不受外界因素影响。可再现性：程序执行时，只要初始条件相同，无论程序连续运行，或断断续续地运行，程序的执行结果与其执行速度无关，其最终结果不变。1.优点：由于顺序程序的封闭性和可再现性，为程序员调试程序带来了很大方便。2.缺点：由于资源的独占性，使得系统资源利用率非常低。二、程序的并发执行程序的并发执行：是指若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的，一个程序（或程序段）的执行尚未结束，另一个程序（或程序段）的执行已经开始。以资源的共享为条件提高了系统资源利用率、系统吞吐量。[例]在下面的有向无环图中，作业i的输入操作、计算操作和打印操作分别用Ii、Ci、Pi表示。虽然同一作业中的输入、计算和打印操作必须顺序执行，但对一批作业而言，情况就不同了。I1I2I3I4P1C1P2P3C2C3P4C4并发执行并发执行程序并发执行的特征：(1,2,3)1.失去了程序的封闭性和可再现性程序在并发执行时，多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性；由于失去了封闭性，也将导致失去其可再现性。(1)失去了程序的封闭性和可再现性程序的并行执行，使得系统中的资源的状态由并行执行的多道程序决定。举例说明：假如系统中有两道程序A和B，这两个程序都正在打印机上输出。程序输出完成后将打印机释放。假定系统用变量N来记录打印机的可用数量。假定N的当前值为1，也即还有一台空闲。当A、B程序释放打印机后，系统的打印机数量为3台(即N=3)。但由于两个程序并发执行，各程序执行释放操作是随机的，有可能使得N的值结果不正确。下面是两个程序释放打印机的操作：intN=1;programA:programB:beginbeginexecuteprogramA；executeprogramB；释放打印机：N=N+1；释放打印机：N=N+1；…………end；end；“N=N+1”的操作分解成机器指令为：取N到寄存器A；A+1→A；存A到N；由于程序A和B都以各自独立的速度向前推进，故程序A执行N=N+1的操作与程序B执行N=N+1操作是随机的。而这两个程序执行N的序列可用表描述如下：时间T0T1T2T3T4T5程序AN-A1A1+1-A1A1-N程序BN-A2A2+1-A2A2-NN的值112223(a)顺序执行时间T0T1T2T3T4T5程序AN-A1A1+1-A1A1-N程序BN-A2A2+1-A2A2-NN的值111122(b)交叉执行时间T0T1T2T3T4T5程序AN-A1A1+1-A1A1-N程序BN-A2A2+1-A2A2-NN的值111122(c)交叉执行若系统只有一台打印机，分得打印机的程序段(假设A得到)可以继续运行，而没有得到打印机的程序段B就不得不暂停执行，等到有可用打印机时才能继续执行。我们称这种制约关系为间接关系。还有一种直接制约关系，是各并发执行的程序段之间需要协调共同完成同一个任务而引起的。例如：typea.c|more或dir|sort；这两条命令就需要两个程序通过管道实现两者之间协作完成用户希望的工作。在并发环境下程序的执行是间断性的：执行——停——执行2.并行执行的程序间产生了相互制约关系因共享资源或协调完成同一任务，使得并发程序之间发生了相互制约关系。[例]系统中并发执行的程序段A和B在运行过程中都希望使用打印机输出计算结果，若系统只有一台打印机，分得打印机的程序段(假设A得到)可以继续运行，而没有得到打印机的程序段B就不得不暂停，等到有可用打印机时才能继续执行。我们称这种制约关系为间接关系。还有一种直接制约关系，是各并发执行的程序段之间需要协调共同完成同一个任务而引起的。例如：typea.c|more或dir|sort；这两条命令就需要两个程序通过管道实现两者之间协作完成用户希望的工作。在并发环境下程序的执行是间断性的：执行——停——执行3.程序与CPU执行的活动之间不再一一对应程序：是完成某一特定功能的指令序列，是静态的概念；CPU执行的活动：是一个动态概念，它是程序的执行过程。[例]在分时系统中，多个用户都调用C编译对自己的源程序进行编译，实际系统只保留一个编译程序，多个用户通过共享执行它完成各自源程序的编译工作。这样，系统虽然只保留一个编译程序，但CPU现正在为多个用户执行编译。由于并发程序的上述这些特点，使得系统中的活动以及各种活动之间的相互关系非常复杂。因此，“程序”这个静态的概念已不能如实地反映系统中的活动情况。为此，现代操作系统引入了进程的概念。三、进程的概念1、进程定义进程这个概念是为了描述系统中各并发活动而引入的。“进程”(process)这一术语，在60年代初期，首先在美国的麻省理工学院的MULTICS系统和IBM公司的CTSS/360系统中引入的。只是IBM/360使用了另一个术语——任务(task)，但两者的实际含义是相同的。进程的定义进程是程序的一次执行。进程是可以和其它计算并行执行的计算。进程是一个程序与其使用的数据在处理机上顺序执行时发生的活动。进程是程序在一个数据集合上的运行过程。进程是系统进行资源分配和调度的一个独立单位。2、进程与程序的联系和区别(5个)（1）动态性：进程是程序的一次执行，它是一个动态的概念，是临时的，有生命期的，表现在它由创建而产生，完成任务后被撤消。程序是完成某个特定功能的指令的有序序列，它是一个静态的概念。程序可以作为一种软件资源长期保存。进程是把程序作为它的运行实体，没有程序，也就没有进程。我们把程序看成是一个菜谱，而进程则是按照菜谱进行烹调的过程。（2）并发性：多个进程实体，同存于内存中，能在一段时间内同时执行；程序是不能并发执行的。（3）独立性：进程是系统进行资源分配和调度的一个独立单位；程序则不是。[例]以多用户进程共享一个编译程序为例，为多个用户执行编译时，显然CPU的分配是以进程为单位，而不是以程序为单位。因为主存只有一个编译程序，但几个用户的源程序都得到编译。（4）异步性：进程以各自独立的、不可预知的速度向前推进；或者说，进程按异步方式运行。正是这一特征，将导致程序执行的不可再现性。因此，在OS中必须采取措施来保证各程序之间能协调运行。（5）结构特性：为了描述和记录进程的运行变化过程，并使之能正确运行，应为每个进程配置一个进程控制块。这样，从结构上看，每个进程是由程序段、数据段和进程控制块三部分组成。四、OS的控制结构OS为了管理进程和资源，必须掌握关于每个进程和资源当前状态的信息。OS构造并维护它所管理的每个实体的信息表。共分四种不同类型的表。1.存储器----存储表2.I/O设备----I/O表3.文件----文件表4.进程----基本进程表存储表：用于跟踪主存储器和辅助（虚拟）存储器。保留在辅存中的进程使用某种类型的虚拟存储或简单的交换机制。I/O表：用于管理计算机系统中的I/O设备和通道。是否已分配给某个进程？文件表：提供关于文件是否存在、文件在辅存中的位置、当前状态和其它属性的信息。进程表：用于管理进程。进程控制块中的基本控制块占有进程表(proc[])中的一项。2.2进程的描述一、进程控制块PCB（ProcessControlBlock）OS在管理和控制进程时必须知道什么？1.它必须知道进程的位置。2.它必须知道在管理时所必需的进程属性进程控制块：与每个进程相关联的所有OS用于控制进程的属性的集合。进程映像(进程实体)：用户程序、用户数据、系统栈和进程控制块。PCB是进程存在系统中的唯一标识。进程映像(进程实体)用户程序：将被执行的程序。用户数据：用户空间中的可修改部分。可以包括程序数据、用户栈区域和可修改的程序。系统栈：每个进程有一个或多个系统栈，用于保存参数、过程调用地址和系统调用地址。PCB：OS控制进程所需要的数据。PCB中的基本信息进程标识符：用于唯一地标识一个进程。外部标识符：由创建者提供，通常是由字母、数字所组成，往往是由用户访问进程时使用，便于记忆。如计算进程、打印进程、发送进程、接收进程等。内部标识符：OS为每一个进程赋予了一个唯一的整数，作为内部标识。父进程标识符、子进程标识符、用户标识符。进程的状态：说明进程目前所处的状态，进程可能的状态在下一节描述。CPU现场保护区：当进程由于某种原因不能继续运行时，要将其CPU运行的现场信息保存起来，以便下次继续运行。通常，CPU的现场信息包括：程序计数器(PC)、工作寄存器、程序状态字等。CPU的调度信息：包括进程优先级、进程所在各种队列的指针。进程要执行的程序在主存和外存起始地址，及存取保护信息。进程使用的资源信息：包括分配给进程的I/O设备、正在执行的I/O请求信息、当前进程正打开的文件等。记帐信息：包括CPU占用量，实际所用时间量，帐号等。进程之间的家族关系在进程的树型结构系统（如UNIX系统）中，进程之间存在着家族关系。创建进程的进程称为父进程，被创建进程称为子进程。二、进程的状态1、三种基本状态。进程执行时的间断性，决定了进程可能具有多种状态。(1)运行态(running)：正在CPU上执行的进程所处状态为运行状态。单CPU系统只有一个进程处于运行状态；多CPU系统可能有多个进程处于执行状态。(2)阻塞态(blocked)：又称等待态。当一个进程因等待某个条件发生而不能运行时处于阻塞态。处于阻塞态的进程在逻辑上是不能运行的，即使CPU空闲，它也不能占用CPU。(3)就绪态(ready)：已分配到除CPU之外的所有必要的资源后，只要能再获得CPU，便可立即执行。多个处于就绪状态的进程排成一个或多个队列—--就绪队列。这三种状态的相互转换如下图所示：运行态就绪态阻塞态等待某个事件发生某个事件已经发生图2.2进程的状态及其转换由进程状态转换图可以看出：就绪态--运行态：处于就绪态的某进程被进程调度程序的执行选中时。运行态--阻塞态：是由运行进程自己主动改变的。[例]一个正在运行的进程启动了某一外围设备后，等待该外围设备传输完成时，使自己由运行态变为阻塞态。阻塞态--就绪态：是由外界事件引起的。[例]上面所述的外围设备传输已经完成时，请求中断，由I/O中断处理程序把因等待这一I/O完成而阻塞的进程变为就绪态。运行态--就绪态：处于运行态的进程被剥夺CPU时。[例]采用时间片轮转法调度时，当前运行进程用完分给它的时间片后，将由运行态变为就绪态；或采用优先级调度时，若有更高优先级的进程变为就绪态，当前进程被迫放弃CPU，使自己由运行态变为就绪态，之后转进程调度。由于系统、进程自身和外界的原因，可能使一个进程多次反复地经历三个基本状态的转换，才能最终达到完成而撤消。2、新状态和终止状态新状态（创建态）：刚刚建立，还未送入就绪队列的状态。刚创建，并为它分配资源。终止状态：已正常结束或异常结束，但尚未撤消时。暂留在系统中，以便其它进程去收集该进程的有关信息。创建态—就绪态：OS准备好再接纳一个进程时，把一个