操作系统原理 第2章 进程管理.ppt

1、第2章 进程管理,学习目标: 掌握进程的定义和特征，掌握进程各种状态之间的转换。 了解进程控制原语操作的意义。 掌握进程互斥与同步的概念，并能用信号量机制实现进程的互斥与同步。 掌握进程调度的原则及相关算法。 了解进程通信的意义及方式。 掌握死锁的定义，产生原因及必要条件，掌握如何预防死锁和避免死锁。 掌握线程的概念及其状态转换。 掌握Linux中的进程管理。,2.1 进程的基本概念 2.2 进程控制 2.3 进程的互斥与同步 2.4 进程的调度 2.5 进程通信 2.6 死锁 2.7 线程 2.8 Linux中的进程管理,第2章 进程管理,2.1 进程的基本概念,2.1.1 程序的顺序执行和

2、并发执行 2.1.2 进程的定义与特征 2.1.3 进程的状态及其转换,2.1.1 程序的顺序执行和并发执行,1.程序的顺序执行,图2.1 程序的顺序执行,在多道程序设计出现以前，程序的最大特性是“顺序性”，即程序的顺序执行。一个程序通常由若干个程序段组成，它们必须按照某种先后次序执行，前一个操作执行完后，才能执行后继操作，这种计算过程即程序的顺序执行过程。 程序顺序执行时的特性： (1) 顺序性 (2) 封闭性 (3) 可再现性,2. 多道程序设计的引入,显然，如果每台计算机在任一时刻只处理一个具有独立功能的程序，那么操作系统的设计和功能都将变得非常简单，因为在这样的系统中不存在资源共享和程

3、序的并发执行以及用户执行的随机性问题。但是，在很多情况下，需要计算机能够同时处理多个具有独立功能的程序，批处理系统、分时系统、实时系统以及网络与分布式系统等都是这样的系统。这样的执行环境具有下述3个特点。,(1) 独立性。在多道环境下执行的每道程序都是逻辑上独立的，它们之间不存在逻辑上的制约关系，也就是说，如果有充分的资源保证，则每道程序都可以独立执行。 (2) 随机性。在多道程序环境下，特别是在多用户环境下，程序和数据的输入与执行的开始时间都是随机的。输入与程序执行开始时间的随机性形成了操作系统必须同时处理多道程序的客观要求。 (3) 资源共享。任何一个计算机系统中的软、硬件资源都是有限的，

4、一般来说，多道环境下执行程序的道数总是要超过计算机系统中CPU的个数，单CPU系统更是如此。显然，受CPU个数的限制，由随机性引起的需同时执行的多道程序只能共享系统中已有的CPU。同理，输入输出设备有限将导致这些设备被共享，内存有限将导致内存被共享等。,3. 程序的并发执行,图2.2 程序的并发执行,程序的并发执行提高了系统的吞吐量，也产生了一些与顺序执行不同的新特点： 制约性 失去封闭性 不可再现性,2.1.2 进程的定义与特征,1.进程的定义 进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，它是系统进行资源分配和调度的一个独立单位。,2.进程的特征,动态性 并发性 独立性

5、异步性 结构特征,3. 进程的结构,进程由程序段、数据段和进程控制块(PCB)这3个部分组成 程序段是进程中能被进程调度程序在CPU上执行的程序代码段，通过程序段的执行可以实现程序的特定功能。 数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行后产生的中间或最终结果数据。,进程控制块,进程控制块是进程实体的一部分，是操作系统中重要的记录型数据结构，其中存放了操作系统所需的、用于描述进程情况和控制进程运行所需的全部信息。 当系统创建一个新进程时，系统为某个程序(包含数据段)设置一个PCB，用于进行控制和管理，进程执行完成时，系统收回其PCB，进程随之消亡。系统根据PCB感知相应进程

6、的存在，故PCB是进程存在的惟一标志。,进程控制块的组成,进程标识符 处理机状态信息 进程调度信息 进程控制信息,4. 进程和程序的区别,进程是一个动态概念，程序则是一个静态概念。 进程是程序的一次执行过程，因而有生命过程，是一个动态生存的暂存性资源；而程序是永久性的软件资源。 一个进程在工作中对应一个应用程序，当多个进程共享内存中的一个程序副本时，一个程序可以有多个进程在工作。 进程由操作系统核心在内部进行分配和调度：程序在操作系统管理下，由系统调用执行。,2.1.3 进程的状态及其转换,图2.5 进程状态之间的转换,进程的基本状态,1. 就绪状态 当进程已获得除处理机以外的所有资源(处理机

7、被系统中的其他进程占用)，一旦分到了处理机即可立即执行时，则其处于就绪状态。 2. 执行状态 当一个进程获得必要的资源，并占有处理机(在处理机上运行)时，则其处于执行状态。 3. 阻塞状态 进程在执行过程中，由于发生某个事件而暂时无法执行下去时，就处于阻塞状态。,2.2 进 程 控 制,原语是由若干条机器指令构成的、用于完成某一特定功能的一段程序。 进程控制原语包括进程创建原语、进程撤销原语及进程阻塞与唤醒原语等。,1. 进程创建,进程创建由创建原语实现，主要有以下两种创建方式。 (1) 由系统程序模块统一创建。例如在批处理系统中，由操作系统的作业调度程序为用户作业创建相应的进程，以完成用户作

8、业所要求的功能。 (2) 由父进程创建。如果一个进程创建了另一个进程，则前者称为父进程，后者称为子进程。例如在层次结构的系统中，父进程创建子进程以完成并行工作。,2. 进程撤销,进程的撤销主要由以下几种情况引起： (1) 该进程已完成所要求的功能而正常终止。 (2) 由于某种错误导致非正常终止。 (3) 祖先进程要求撤销某个子进程。,3. 进程阻塞,阻塞原语的作用是将进程由执行状态转变为阻塞状态，其主要功能如下： （1）使进程让出处理机。 （2）把进程运行的CPU现场送至该进程PCB的现场保护区。 （3）把该进程的状态置为等待态，并插入到相应的等待队列中。 （4）调用系统的进程调度程序，选择下

9、一个进程占用处理机。,4. 进程唤醒,唤醒原语的作用是将进程由阻塞状态转变为就绪状态，其主要功能如下： （1） 从相应的等待队列中查找等待该事件的等待进程。 （2） 把该进程从等待队列中摘除，将其置为就绪态并插入到就绪队列中去。,2.3 进程的互斥与同步,2.3.1 互斥的定义 2.3.2 同步的定义 2.3.3 信号量机制 2.3.4 用P、V操作实现进程的互斥 2.3.5 用P、V操作实现进程的同步,2.3.1 互斥的定义,在计算机中有许多资源一次只能允许一个进程使用。如果有多个进程同时去使用这类资源就会引起激烈的竞争，即互斥。 我们把那些某段时间内只允许一个进程使用的资源称为临界资源。,

10、临界资源的访问必须遵循的准则：,(1) 当临界资源空闲时，允许一个(仅一个)请求进入临界区的进程立即进入其临界区，以有效地利用临界资源，且不至于使多个进程因相互阻塞而使彼此都不能进入临界区。 (2) 进程在临界区内停留有限的时间，对于要求访问临界资源的进程，应能在有限时间内进入自己的临界区，以免陷入“死等”状态。 (3) 当进程不能进入临界区时，应立即释放处理机，以免进程“忙等”。,注意： 大多数具有独占性的硬件设备和共享的文件都可可能称为临界资源； 有几个进程共同使用的变量、数据、表格、队列及内存工作区等也是临界资源。,2.3.2 同步的定义,把这种进程间为了完成一个共同的目标，必须互相合作

11、的协同工作关系、有前后次序的直接制约关系称为进程的同步。,进程的同步与互斥的不同之处：,(1) 互斥的各个进程在各自单独执行时都可以得到正确的运行结果，但是当它们在临界区内交叉执行时就可能出现问题。而同步的各个进程，如果各自单独执行将不会完成作业的特定任务，只有当它们互相配合、共同协调推进时才能得到正确的运行结果。 (2) 互斥的进程只要求它们不能同时进入临界区，而不需规定进程进入临界区的顺序。但同步的进程的协调关系是建立在它们之间执行顺序的基础上，所以，各个进程必须按照严格的先后次序执行。 (3) 一般情况下，互斥的进程并不知道对方的存在。而同步的进程不仅知道其他进程的存在，还要通过与其他进

12、程的通信来达到相互的协调。,2.3.3 信号量机制,1. 记录型信号量 记录型信号量S是一个记录型的数据结构，它包含两个数据项：一个是计算值域value，另一个是等待信号量的进程等待队列的首指针L。 其中S.value是一个具有非负初值的整形变量，表示系统中某类资源的数目。 大于0时，表示系统中当前可用资源的数目； 小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。,2. P、V操作的定义,信号量的初值可以由系统根据资源情况和使用需要来确定。在初始条件下信号量的指针项可以置为0，表示队列为空。信号量在使用过程中其值是可变的，但仅能由P、V操作来改变，P、V操作原语都应作为一个整体实

13、施，不允许分割或相互穿插执行。也就是说，P、V操作各自都好像对应一条指令，需要不间断地做下去，否则会造成混乱。为了保证这一点，在单CPU系统中通常是在封锁中断的条件下执行P、V操作。即P、V操作均为原语。设信号量为S，对S的P操作记为P(S)，对它的V操作记为V(S)。,P(S)原语操作,(1) S.value减1。 (2) 若S.value减1后仍大于或等于0，则进程继续执行。 (3) 若S.value减1后小于0，则该进程将被阻塞，进入与该信号量对应的等待队列L中，然后转进程调度。,图2.6 P(S)原语操作功能图,V(S)原语操作,(1) S.value加1。 (2) 若S.value加

14、1后结果大于0，则进程继续执行。 (3) 若S.value加1后结果小于或者等于0，则从该信号量的等待队列L中唤醒头一个等待进程，然后再返回原进程继续执行或转进程调度。,图2.7 V(S)原语操作功能图,2.3.4 用P、V操作实现进程的互斥,利用P、V原语操作和信号量实现进程通信是很方便的，它的使用方式基本上可分成三种：第一种用法是用于实现进入临界区的互斥，这时信号量的初值往往是1；第二种用法是用于实现进程间的简单同步，信号量初值可以是0；第三种用法是用于实现进程间的计数同步，信号量初值通常是大于0的整数。,2.3.5 用P、V操作实现进程的同步,先确定等待进程与被等待进程，然后找到两进程间

15、发生联系的相关程序段，设置信号量并赋予初值，最后在等待方进程的相关程序段之前设置好信号量的P操作，在被等待方进程的相关段之后设置好信号量的V操作。, 生产者消费者问题,使用P、V操作同时实现进程互斥和同步的经典实例是生产者消费者问题。设生产者进程不断地生产产品，消费者进程不断地消费产品。生产者进程和消费者进程通过一个有界的缓冲区联系起来。,图2.8 生产者消费者问题,2.4 进程的调度,多道程序环境下，进程数目往往多于处理机数目，以致引起处理机的争用。处理机是系统中最重要的资源，为提高处理机的利用率和改善系统的性能，需要由进程调度程序实现对多个进程的合理调度。由于进程调度程序的执行频率很高，因

16、此被常驻于内存。进程调度程序是操作系统内核的重要组成部分。,1. 调度的类型 (1) 作业调度。又称宏观调度或高级调度。 (2) 进程调度。又称微观调度或低级调度 (3) 交换调度。又称中级调度。 2. 进程调度方式 （1）剥夺方式 （2）非剥夺方式,剥夺方式,剥夺方式也称抢占方式，其含义是根据某种原则，强行剥夺已分配给该进程的处理机资源，并将其分配给其他进程。剥夺的原则： 优先权原则 短进程优先原则 时间片原则 强制性剥夺,非剥夺方式,当某进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，也不允许强行剥夺已经分配给该进程的处理机；正在执行的进程继续执行，直到该进程完成，或发

17、生某个事件而进入完成或阻塞状态时，才把处理机分配给更为重要或紧迫的进程。,3.进程调度算法,进程调度程序在选择就绪进程投入运行时，可能会发现有多个进程同时处于就绪状态。因此，应按一定的原则选择一个进程，以便把CPU分配给它，这个原则就是进程调度算法。 对于不同的系统及系统目标，应采用不同的调度算法。,(1) 先来先服务(FCFS)调度算法,种最简单的调度算法，即按照进程进入就绪队列的先后次序分配处理机。非剥夺调度方式，一旦一个进程占有处理机，就一直运行下去，直到该进程完成其工作或因等待某个事件而不能继续执行时才释放处理机。 优点:具有一定的公平性，并且实现也比较容易， 缺点：实际上是不公平的，

18、比较有利于长进程，不利于短进程。,(2) 短进程优先(SPF)调度算法,短进程优先调度算法，是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或因等待某事件发生而放弃处理机时，再重新调度。 优点：平均周转时间比FCFS有改善 缺点： （1）对长进程非常不利 （2）紧迫进程不能及时处理 （3）执行时间的估计值不准确,(3) 高优先级优先(HPF)调度算法,考虑到系统中的紧迫进程能得到优先处理，引入了高优先级优先调度算法，处理机总是分配给就绪进程队列中优先级最高的进程。为了加速进程调度，进程就绪队列按优先级由高到低排列，调度时，只要把处理机分配给队首进程

19、即可。HPF进程调度可以是剥夺式或非剥夺式的。,在采用高优先级优先调度算法的系统中，进程的优先级对进程的调度至关重要，因为优先级的高低将直接影响到就绪进程被调度执行的次序。进程的优先级可采用静态优先级和动态优先级两种，优先级可由用户自定或由系统确定。 静态优先级在创建进程时确定，确定后在整个进程运行期间不再改变。 动态优先级指在创建进程时，根据系统资源的使用情况和进程的当前特点确定一个优先权，在进程运行过程中再根据情况的变化调整优先权。,(4) 时间片轮转调度(RR)算法,这种调度算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择队列中的第一个进程执行，且仅能执行

20、一个时间片。使用完一个时间片后，即使进程未完成运行，也必须剥夺该进程的运行并送到就绪队列末尾，重新把处理机分配给就绪队列中新的队首进程。这样，就绪队列中的所有进程在一给定时间内均可获得一个时间片的处理机执行时间。,(5) 多级反馈队列调度算法,图2.9 多级反馈队列示意图, 系统按优先级设置n个就绪进程队列，第一级队列的优先级最高，其余队列的优先级逐个降低，第N级队列的优先级最低。 每个就绪队列对应有一个时间片Si(i=1,2,3,n)，且有S1S2S3Sn。 除第n个队列按RR法调度外，其余各个队列均按FCFS调度。, 当一个新进程被建立后首先进入第一队列末尾，按FCFS原则排队等待调度。当

21、轮到该进程执行时，如能在时间片S1内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二个队列的末尾，同样地按FCFS原则等待调度执行；如果它在第二个队列中运行一个时间片S2后仍未完成，再将它转入第三个队列末尾，按FCFS原则排队等待调度执行。如此下去，当一个长进程从第一个队列降到第N队列后，在第N队列中便采用RR法调度运行。, 由于第一级队列的优先级最高，其余队列的优先级逐个降低，第N级队列的优先级最低，所以仅当第一个队列空闲时，调度程序才调度第二个队列的进程运行；一般仅当1(i-1)队列均空时，才会调度第i个队列中的进程运行。如果处理机正在为第i队列中的某进

22、程服务时，又有新进程进入优先级较高的队列(第1(i-1)中任何一个队列)，则此时新进程将剥夺正在运行进程的处理机，调度程序把正在运行进程送回第i个队列末尾，重新把处理机分配给优先级较高的队列中的新进程。,2.5 进 程 通 信,通常把使用信号量实现进程互斥与同步这种仅在进程间交换控制信息的通信机制称为低级通信机制。 通常把进程之间可以进行大量数据交换的通信机制称为高级通信机制。 高级通信机制是由操作系统提供的通信原语和有关数据结构组成的。高级通信方式可分为3大类：共享存储器系统、消息传递系统以及管道通信系统。,共享存储器系统为了传送大量数据，在存储器中划出一块共享存储区，诸进程可通过对共享存储

23、区进行读数据或写数据以实现通信。,1. 共享存储器系统,2.消息通信传递系统,(1) 直接通信方式 发送进程可将消息直接发送给接收进程，即将消息挂在接收进程的消息缓冲队列上，而接收进程可从自己的消息缓冲队列中取得消息。 (2) 间接通信方式 发送进程将消息发送到指定的信箱中，而接收进程从信箱中取得消息。这种通信方式又称信箱通信方式，被广泛地应用于计算机网络中。相应地，该消息传递系统被称为电子邮件系统。,3. 管道通信系统,所谓管道是指用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件，又称pipe文件。向管道提供输入的发送进程，以字符流方式将大量的数据送入管道，而接收进程从管道中接收

24、数据。由于发送进程和接收进程是利用管道进行通信的，故称为管道通信。,2.6 死锁,2.6.1 死锁的定义 2.6.2 产生死锁的原因和必要条件 2.6.3 死锁的防止与避免,2.6.1 死锁的定义,所谓死锁，是指各并发进程互相等待对方拥有的资源，且这些并发进程在得到对方的资源前不会释放自己拥有的资源，从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态。,2.6.2 产生死锁的原因和必要条件,1. 产生死锁的原因 (1) 竞争资源 (2) 进程推进顺序不当,2. 死锁产生的必要条件,互斥条件 不剥夺条件 部分分配条件 环路条件 只有同时具备上述4个必要条件，系统才会发生死

25、锁，只要上述条件之一不满足，系统就不会发生死锁。,2.6.3 死锁的防止与避免,1. 预防死锁 (1) 破坏互斥条件。 (2) 破坏不剥夺条件。 (3) 破坏部分分配条件。 (4) 破坏环路条件。,2. 避免死锁,死锁的避免不是严格限制产生死锁必要条件的存在，而是在资源的动态分配过程中，使用某种方法防止系统进入不安全状态，从而避免死锁的发生。 死锁避免算法是避免系统进入不安全状态的算法。,银行家算法(上),银行家算法的基本思想是：在安全状态下，系统在接到一个进程的资源请求后，先假定接受这一请求，把资源分配给它。然后在这一假定下，进行以下的判断过程。首先，系统用剩下的资源和每一个进程还需要的资源

26、数相比较，并记录下满足以下条件的进程：即系统把剩余的资源分配给它，满足它对资源的最大需求后它就能运行到底，然后系统可以把它所占用的全部资源收回，再用这更多的剩余资源与别的、还未完成的进程的还需资源数加以比较。,银行家算法（下）,在这样的“比较收回再比较”过程中依次记录下每一个满足条件的进程，直到找不出这样的进程为止。最后检查经过这一过程之后是否还有进程无法运行到结束，如果全部进程都能运行结束(即上述过程中已经记录完系统中的所有进程)，那就意味着可以实际实行这一资源分配，因为系统实行这一分配后仍然处于安全状态；如果存在不能运行结束的进程(即上述过程中并没有记录完系统中所有的进程)，则表明如果实际

27、实行这一分配后，将使系统将进入不安全状态，于是暂时不去接受这一资源申请，而让申请该资源的进程等待。,图2.13 银行家算法的基本思想,3. 检测和解除死锁,由于死锁产生的概率总是比较小的，所以在一些相对简单的系统中，为节省预防或避免死锁中所增加的系统开销，系统中允许出现死锁状态。在这种系统中，专门设置了一个检测机构，可以随时检测出死锁的发生，并能确定与死锁有关的进程和资源，然后采用适当的方法解除系统中的死锁状态。 常用的解除死锁的方法有两种：一是强制性地撤销一些死锁进程，并剥夺它们的资源给其他的进程；另一种是使用一个有效的挂起和解除挂起机构来挂起一些进程，以便从被挂起进程中剥夺一些资源，用来解

28、除死锁。,2.7 线程,2.7.1 线程的引入 2.7.2 线程与进程的比较 2.7.3 线程的属性 2.7.4 线程的状态及其转换,2.7.1 线程的引入,如果说在操作系统中引入进程的目的是为了使多个程序并发执行，以改善资源利用率和提高系统吞吐量的话，那么，在操作系统中再引入线程，则是为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性。,2.7.2 线程与进程的比较,(1) 拥有资源 (2) 调度 (3) 并发性 (4) 系统开销 (5) 通信方面,2.7.3 线程的属性,线程有控制表。 线程共享所属进程的资源。 线程是处理机的独立调度单位，多个线程可以并发执行。 线程有动态

29、性。,2.7.4 线程的状态及其转换,1.线程的状态 (1) 就绪状态。 (2) 备用状态。 (3) 转换状态。 (4) 运行状态。 (5) 等待状态。 (6) 终止状态。,2.线程状态的转换,图2.14 线程的状态及其转换,2.8 Linux中的进程管理,2.8.1 Linux进程概述 2.8.2 Linux的进程控制 2.8.3 Linux的进程调度 2.8.4 Linux进程的同步和通信,2.8.1 Linux进程概述,1. 进程实体的组成 Linux进程由3部分组成：正文段、用户数据段和系统数据段。 （1) 正文段是只能读不能修改的指令代码，它允许系统中多个进程共享这一代码段。 （2）

30、用户数据段是进程执行时直接操作的所有数据(包括全部变量在内)，这些信息是可以被修改的。 （3）系统数据段存放着进程的控制信息，即进程控制块(PCB)，它存放了程序的运行环境。,2. 进程的状态,(1) 运行状态(task_running) 运行状态的进程是指正在运行的进程或者是处于等待调度程序将CPU分配给它的进程(即就绪状)。 (2) 等待状态 等待状态是指进程正在等待某个事件发生或等待某种资源时的状态。Linux系统的等待状态可以分为两种：可中断等待状态(task_interruptible)和不可中断等待状态(task_uninterruptible)。,(3) 暂停状态(task_st

31、opped) 暂停状态指进程暂时停止运行，接受某种处理。正在被调试的进程可能处于暂停状态。 (4) 僵死状态(task_zombie) 僵死状态表示进程结束但尚未消亡的一种状态。此时，进程已经结束运行并已释放大部分资源，但进程尚未释放其task_struct结构。,图2.15 Linux进程状态转换,3. 进程的结构,进程当前的状态。 调度信息。 进程标识符。 进程通信信息。 进程的家族关系。 时间和定时信息。 文件系统信息。 存储管理信息。 CPU现场信息。,2.8.2 Linux的进程控制,Linux中的进程控制是通过系统调度来实现的。 (1)进程的创建 fork( ) (2)进程的执行

32、exec( ) (3)进程的等待 wait( ) (4)进程的终止 exit( ),2.8.3 Linux的进程调度,Linux的run_queue队列中包含了系统中所有处于运行状态的进程(该队列包括正在执行的进程和可以执行的等待CPU资源的进程)，进程调度的任务就是在run_queue队列中选出一个进程在处理机上运行。进程调度策略决定了系统对资源，特别是CPU资源的分配策略，进程调度策略会对系统的性能产生直接的影响。 Linux将进程分为两类：普通进程和实时进程。普通进程没有特殊的响应要求，实时进程一般要求系统立即做出响应，要求实时进程总能优先于普通进程被执行。总的来说，Linux系统使用的

33、调度策略有：用于实时进程的先进先出算法(FIFO)和轮转算法(RR)，用于普通进程的基于优先级的轮转算法。实际上，Linux是将这些进程调度算法融合在一起使用。,和进程调度相关的信息（上）,(1) policy(策略)。是系统对该进程实施的调度策略。在Linux系统中，每个进程都可以有一个调度策略，这在它的task_struct结构中的policy属性中规定，如表2.8所示。进程的调度策略是从父进程那里继承来的，但可以通过特定的系统调用来改变。,表2.8 调度策略标志,和进程调度相关的信息（下）,(2) priority(优先级)。是系统为进程给定的静态优先级。此优先级不随时间的变化而改变，可以通过系统调用或renice命令修改。优先级实际是从进程开始运行算起的、允许进程的运行时间值，普通进程