N计算机操作系统教程第二章 c

1、 计算机操作系统教程计算机操作系统教程 -Linux实例分析程骅程骅信息科学与工程学院信息科学与工程学院 进程概念进程概念1.进程控制进程控制2.进程调度进程调度3.进程同步与互斥进程同步与互斥4.进程通讯进程通讯5.线程线程6.第第 2 2 章章 进程管理进程管理 2.1 2.1 进程概念进程概念2.1.12.1.1程序的顺序执行程序的顺序执行(1) 顺序性 ：程序顺序执行时，其执行过程可看作一系列严格按程序规定的状态转移过程。(2) 封闭性 ：程序执行得到的最终结果由给定的初始条件决定，不受外界因素的影响。(3) 可再现性 ：只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结

2、果。 在某个程序段执行完之前，其它程序段只在某个程序段执行完之前，其它程序段只能等待。这种程序的执行方式，我们成为程序能等待。这种程序的执行方式，我们成为程序的顺序执行。的顺序执行。程序的顺序执行具有如下特点：程序的顺序执行具有如下特点：进程管理的主要功能进程管理的主要功能: : 进程控制进程控制: :其基本功能为创建和撤销进程以其基本功能为创建和撤销进程以及控制进程的状态转换。及控制进程的状态转换。 进程同步进程同步: :是指系统对并发执行的进程进行是指系统对并发执行的进程进行协调。协调。 进程调度进程调度: :是指按照一定算法，从进程就绪是指按照一定算法，从进程就绪队列中选出一个进程，分配

3、处理机给它，队列中选出一个进程，分配处理机给它，并为该进程设置运行现场，使之投入运行。并为该进程设置运行现场，使之投入运行。 进程通信进程通信: :运行时，相互合作的进程间进程运行时，相互合作的进程间进程的信息交换称为进程通信。的信息交换称为进程通信。并发执行，是为了增强计算机系统的处理能力和提高资源利用率所采取的一种同时操作技术。第一种是多道程序系统的程序执行环境变化所引起的多道程序的并发执行。第二种并发执行是在某道程序的几个程序段中，包含着一部分可以同时执行或顺序颠倒执行的代码。 read (a) read (b) ； 它们既可以同时执行，也可颠倒次序执行。2.1.22.1.2程序的并发执

4、行及其特征程序的并发执行及其特征图图3.1 3.1 堆栈的取数和存数过程堆栈的取数和存数过程 如果并发执行的程序段不按照如果并发执行的程序段不按照特定的规则特定的规则和方法和方法进行资源共享和竞争，则其执行结果将进行资源共享和竞争，则其执行结果将不可避免地不可避免地失去失去封闭性和可再现性。封闭性和可再现性。程序的并发执行程序的并发执行例：设有堆栈 S，栈指针 top，栈中存放内存中相应数据块地址。procedure procedure getaddr(top)getaddr(top)beginbeginlocal rlocal rr (top)r (top)top top-1top top-

5、1return(r)return(r)endendprocedure procedure reloaddr(blk)reloaddr(blk) beginbegin top top+1top top+1(top) blk(top) blkendend程序的并发执行程序的并发执行 另外，如果改变程序段另外，如果改变程序段 getaddr 和和 reladdr 的执行顺序或执行速度，又可得到不的执行顺序或执行速度，又可得到不同的执行结果。同的执行结果。 这这说明了如下问题说明了如下问题：在某些情况下，程：在某些情况下，程序的并发执行使得其执行结果不再具有封闭性序的并发执行使得其执行结果不再具有封闭

6、性和可再现性，且可能造成程序出现错误。和可再现性，且可能造成程序出现错误。 上例中的程序段并发执行出现错误结果是上例中的程序段并发执行出现错误结果是由于两程序段共由于两程序段共享资源堆栈享资源堆栈S，从而使得执行，从而使得执行结果受执行速度影响。结果受执行速度影响。 为了使得在并发执行时不出现错误结果，必为了使得在并发执行时不出现错误结果，必须采取某些措施来须采取某些措施来制约、控制制约、控制各并发程序段的执各并发程序段的执行速度。这在操作系统程序设计中尤其重要，因行速度。这在操作系统程序设计中尤其重要，因为操作系统为操作系统用户随机性用户随机性与与各道程序逻辑独立各道程序逻辑独立的特的特点将

7、使得每个用户程序所使用的软、硬件资源都点将使得每个用户程序所使用的软、硬件资源都受到其他并发程序的共享和竞争，从而得到非预受到其他并发程序的共享和竞争，从而得到非预料的或不正确的结果。料的或不正确的结果。 由于程序的顺序性、静态性以及孤立性，用由于程序的顺序性、静态性以及孤立性，用程序段作为描述其执行过程和共享资源的基本单程序段作为描述其执行过程和共享资源的基本单位既增加操作系统设计和实现的复杂性，也无法位既增加操作系统设计和实现的复杂性，也无法反映操作系统所应该具有的程序段执行的并发性反映操作系统所应该具有的程序段执行的并发性、用户随机性，以及资源共享等特征。、用户随机性，以及资源共享等特征

8、。 为了控制和协调各程序段执行过程中的软、为了控制和协调各程序段执行过程中的软、硬件资源的共享和竞争，需要有一个能描述程序硬件资源的共享和竞争，需要有一个能描述程序的执行过程且能用来共享资源的基本单位。的执行过程且能用来共享资源的基本单位。 这个基本单位被称为这个基本单位被称为进程进程（或任务）。（或任务）。程序的并发执行及其特性程序的并发执行及其特性特点：特点：1.1.失去封闭性及失去可再现性失去封闭性及失去可再现性2.2.程序与计算不再一一对应程序与计算不再一一对应3.3.并发程序在执行期间可以互相制约并发程序在执行期间可以互相制约 一组程序共存于系统中，它们在执行时间上一组程序共存于系统

9、中，它们在执行时间上是重叠的。是重叠的。 （1 1）直接制约）直接制约（2 2）间接制约）间接制约 并行：并行： 同一时刻，两个事物均处于活动状态同一时刻，两个事物均处于活动状态2.1.32.1.3并行与并发概念的差别并行与并发概念的差别并发：并发： 宏观上存在并行特征，微观上存在顺序性。宏观上存在并行特征，微观上存在顺序性。同一时刻，只有一个事物处于活动状态同一时刻，只有一个事物处于活动状态. .2.1.4 进程概念及其特性进程概念及其特性v顺序程序顺序程序 顺序性顺序性 封闭性封闭性 可再现性可再现性 v并发程序并发程序 间断间断(异步异步)性性 失去封闭性失去封闭性 失去可再现性失去可再

10、现性程程 程程 程程序序 序序 序序并发执行的条件：达到封闭性和可再现性并发执行的条件：达到封闭性和可再现性进程的概念进程的概念 程序在处理机上执行时所发生的活动（程序在处理机上执行时所发生的活动（Dijkstra） 是一个容器，该容器用以聚集相关资源（是一个容器，该容器用以聚集相关资源（A. S. Tanenbaum） 是具有独立功能的程序关于某个数据集合上的一次运是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位行活动，是系统进行资源分配和调度的独立单位动态性动态性：进程是程序的一次执行，有着：进程是程序的一次执行，有着“创建创建”、“活动活动”、“暂

11、停暂停”、“撤消撤消”等过程，具有等过程，具有一定的生命期，是动态地产生、变化和消亡的。一定的生命期，是动态地产生、变化和消亡的。并发性并发性：进程之间的动作在时间上可以重叠，即：进程之间的动作在时间上可以重叠，即系统中有若干进程都已经系统中有若干进程都已经“开始开始”但又没有但又没有“结结果果”，称这些进程为并发进程。，称这些进程为并发进程。独立性独立性：进程是系统调度和资源分配的独立单位：进程是系统调度和资源分配的独立单位，它具有相对独立的功能，拥有自己独立的进程，它具有相对独立的功能，拥有自己独立的进程控制块控制块PCB。进程的特性进程的特性异步性异步性：各个并发进程按照各自独立的、：各

12、个并发进程按照各自独立的、不可预知的速度向前推进。不可预知的速度向前推进。交互性交互性：并发进程之间具有直接或间接的：并发进程之间具有直接或间接的关系，在运行过程中需要进行必要的交互关系，在运行过程中需要进行必要的交互（同步、互斥和数据通信等），以完成特定（同步、互斥和数据通信等），以完成特定的任务。的任务。 作业是用户需要计算机完成某项任务时要求计算机作业是用户需要计算机完成某项任务时要求计算机所作工作的集合。进程是已提交完毕程序的执行过程的所作工作的集合。进程是已提交完毕程序的执行过程的描述，是资源分配的基本单位。区别与关系：描述，是资源分配的基本单位。区别与关系：(1) 作业是用户向计算

13、机提交任务的作业是用户向计算机提交任务的任务实体任务实体。在用户。在用户向计算机提交作业之后，系统将它放入外存中的作业等向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的待队列中等待执行。而进程则是完成用户任务的执行实执行实体体，是向系统申请分配资源的基本单位。任一进程，只，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中。要它被创建，总有相应的部分存在于内存中。(2) 一个作业可由多个进程组成。且必须至少由一个进一个作业可由多个进程组成。且必须至少由一个进程组成，但反过来不成立。程组成，但反过来不成立。(3) 作业的概

14、念主要用在批处理系统中。而进程的概念作业的概念主要用在批处理系统中。而进程的概念则用在几乎所有的多道系统中。则用在几乎所有的多道系统中。作业和进程的关系作业和进程的关系v程序是静态的，进程是动态的程序是静态的，进程是动态的v进程是一个能独立运行的单位进程是一个能独立运行的单位 v 程序和进程无一一对应关系程序和进程无一一对应关系v进程与程序的组成不同，进程程序数据进程与程序的组成不同，进程程序数据PCBv进程的存在是暂时的，程序的存在是永久的进程的存在是暂时的，程序的存在是永久的v一个程序可以对应多个进程，一个进程可以包含一个程序可以对应多个进程，一个进程可以包含多个程序多个程序程序与进程之间

15、的区别程序与进程之间的区别 2.1.52.1.5 进程的组成进程的组成 1.程序程序:完成独立功能的指令集合。完成独立功能的指令集合。 2.数据数据:程序运行所作用的对象。程序运行所作用的对象。 3.进程控制块进程控制块(PCB):进程控制块是进程存进程控制块是进程存在的唯一标志。在的唯一标志。 PCB PCB包含一个进程的描述信息、控制信息及资源信息包含一个进程的描述信息、控制信息及资源信息，有些系统中还有进程调度等待所使用的，有些系统中还有进程调度等待所使用的现场保护区现场保护区。 PCB PCB 集中反映一个进程的动态特征。在进程并发执行集中反映一个进程的动态特征。在进程并发执行时，由于

16、资源共享，带来各进程之间的相互制约。时，由于资源共享，带来各进程之间的相互制约。 显然，为了反映这些制约关系和资源共享关系，在创显然，为了反映这些制约关系和资源共享关系，在创建一个进程时，应首先建一个进程时，应首先创建创建其其 PCBPCB，然后才能根据，然后才能根据PCB PCB 中中信息对进程实施有效的管理和控制。当一个进程完成其功信息对进程实施有效的管理和控制。当一个进程完成其功能之后，系统则能之后，系统则释放释放PCBPCB，进程也随之消亡。，进程也随之消亡。 一般来说，根据操作系统的要求不同，进程的一般来说，根据操作系统的要求不同，进程的 PCBPCB所所包含的内容会多少有所不同。包

17、含的内容会多少有所不同。进程控制块进程控制块 PCBPCB进程的表示和状态转换进程的表示和状态转换v进程控制块进程控制块PCB（Process Control Block） 系统为了管理进程设置的一个专门的数据结构，用系统为了管理进程设置的一个专门的数据结构，用来记录进程的外部特征，描述进程的变化过程来记录进程的外部特征，描述进程的变化过程 进程的组成：进程的组成： program+data+PCB PCB是是系统感知进程存在的唯一标志系统感知进程存在的唯一标志，进程与进程与PCB是一一对应的是一一对应的(a) 进程控制块；进程控制块； (b) 数据段；数据段； (c) 程序段程序段 (a)

18、(b) (c)PCB的内容的内容v进程描述信息：进程描述信息： 进程标识符进程标识符(process ID)，唯一，通常是一个整数，唯一，通常是一个整数 进程名，通常基于可执行文件名（不唯一）进程名，通常基于可执行文件名（不唯一） 用户标识符用户标识符(user ID)；进程组关系；进程组关系v进程控制信息：进程控制信息： 当前状态当前状态 优先级优先级(priority) 代码执行入口地址代码执行入口地址 程序的外存地址程序的外存地址 运行统计信息（执行时间、页面调度）运行统计信息（执行时间、页面调度） 进程间同步和通信；阻塞原因进程间同步和通信；阻塞原因v所拥有的资源和使用情况：所拥有的资

19、源和使用情况： 虚拟地址空间的现状虚拟地址空间的现状 打开文件列表打开文件列表vCPU现场保护结构现场保护结构：寄存器值：寄存器值(1) 描述信息 进程名或进程标识号； 用户名或用户标识号 家族关系(2) 控制信息 进程当前状态：进程在活动期间可分为就绪态、执行态和等待状态。 进程优先级：进程优先级是选取进程占有处理机的重要依据。与进程优先级有关的PCB表项有：a. 占有CPU时间；b. 进程优先级偏移；c.占据内存时间进程控制块进程控制块 PCBPCB 程序开始地址； 各种计时信息：给出进程占有和利用资源的有关情况。； 通信信息：通信信息用来说明该进程在执行过程中与别的进程所发生的信息交换情

20、况。(3) 资源管理信息 PCB 中包含最多的是资源管理信息，包括有关存储器的信息、使用输入输出设备的信息、有关文件系统的信息等。这些信息有： 占用内存大小及其管理用数据结构指针，例如后述内存管理中所用到的进程页表指针等。进程控制块进程控制块 PCBPCB 在某些复杂系统中，还有对换或覆盖用的有关信息，如对换程序段长度，对换外存地址等。这些信息在进程申请、释放内存中使用。 共享程序段大小及起始地址。 输入输出设备的设备号，所要传送的数据长度、缓冲区地址、缓冲区长度及所用设备的有关数据结构指针等。这些信息在进程申请释放设备进行数据传输中使用。 指向文件系统的指针及有关标识等。进程可使用这些信息对

21、文件系统进行操作。进程控制块进程控制块 PCBPCB(4) CPU 现场保护结构 当前进程因等待某个事件而进入等待状态或因某种事件发生被中止在处理机上的执行时，为了以后该进程能在被打断处恢复执行，需要保护当前进程的 CPU现场（或称进程上下文）。PCB 中设有专门的 CPU现场保护结构，以存储退出执行时的进程现场数据。 进程控制块PCB 是系统感知进程存在的唯一实体。通过对PCB 的操作，系统为有关进程分配资源从而使得有关进程得以被调度执行；而完成进程所要求功能的程序段的有关地址，以及程序段在进程过程中因某种原因被停止执行后的现场信息也都在PCB 中。最后，当进程执行结束后，则通过释放PCB

22、来释放进程所占有的各种资源。进程控制块进程控制块 PCBPCB 由于PCB 中包含有较多的信息，因此，一个PCB表往往要占据较大的存储空间（一般占几百到几千个字节）。在有的系统中，为了减少 PCB对内存的占用量，只允许PCB中最常用的部分，如CPU现场保护、进程描述信息、控制信息等常驻内存。PCB 结构中的其他部分则存放于外存之中，待该进程将要执行时与其他数据一起装入内存。 近年来，面向对象技术已被用于操作系统设计。在面向对象的操作系统中，进程的描述将采用其他方式。进程控制块进程控制块 PCBPCBLinux中的进程描述参数中的进程描述参数 v1）包含了进程的描述信息和控制信息，v2）是进程的

23、动态特征的集中反映，v3）系统根据PCB而感知某一进程的存在。PCB是进程存在的唯一标志是进程存在的唯一标志？PCB表组织方式表组织方式vPCB表： 系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表 PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度v组织方式： 线性表结构 链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表：就绪链表、阻塞链表 索引表：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表：就绪索引表、阻塞索引表。1.1.线性表结构线性表结构2.1.6 PCB2.1.6 PCB的

24、组织方式的组织方式 PCBPCB链表队列链表队列PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901执行指针就绪队列指针阻塞队列指针空闲队列指针2.1.6 PCB2.1.6 PCB的组织方式的组织方式 执行指针就绪索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就绪表指针阻塞表指针按索引方式组织按索引方式组织PCB2.1.6 PCB2.1.6 PCB的组织方式的组织方式 进程上下文进程上下文上文：已执行过的进程指令和数据在相关寄存器与堆栈中的内容。正文：正在执行的进程指令和数据在相关寄存器与堆栈中的内容。下文：待执行的进程指令和数据在

25、相关寄存器与堆栈中的内容。 进程上下文实际上是进程执行活动全过程的静态描述。具体地说，进程上下文包括计算机系统中与执行该进程有关的各种寄存器的值、程序段在经过编译之后形成的机器指令代码集（或称正文段）、数据集及各种堆栈值和PCB结构。这里，有关寄存器和栈区的内容是重要的。进程上下文进程上下文进程上下文结构进程上下文结构 进程的系统级上下文又分为静态部分与动态部分。这里的动态部分不是指程序的执行，而是指在进入和退出不同的上下文层次时，系统为各层上下文中相关联的寄存器值所保存和恢复的记录。 系统级上下文的静态部分包括PCB 结构、将进程虚地址空间映射到物理空间用的有关表格和核心栈。 系统级上下文的

26、动态部分是与寄存器上下文相关联的。其变化规则满足先进后出的堆栈方式，每个上下文层次在栈中各占一项。进程上下文进程上下文进程上下文进程上下文UNIX System UNIX System 进程上下文组成进程上下文组成 任一进程，都有一个自己的地址空间，把该空间称为进程空间或虚空间。进程空间的大小只与处理机的位数有关。例如，一个16位长处理机的进程空间大小为216，而32位长处理机的进程空间大小为232。程序的执行都在进程空间内进行。用户程序、进程的各种控制表格等都按一定的结构排列在进程空间中。另外，在UNIX以及Linux等操作系统中，进程空间还被划分为用户空间和系统空间两大部分。 进程空间进程

27、空间进程空间进程空间 在进程空间被划分为两大部分后，用户程序在用户空间内执行，而操作系统内核程序则在进程的系统空间内执行。 另外，为了防止用户程序访问系统空间，造成访问出错，计算机系统还通过程序状态寄存器等设置不同的执行模式，即用户模式和系统模式来进行保护。人们也把用户执行模式和系统执行模式分别称为用户态和系统态。进程空间进程空间1.1.进程的状态进程的状态2.1.72.1.7进程的状态及其变迁进程的状态及其变迁 运行状态（运行状态（RunningRunning） ，进程占有，进程占有CPUCPU，并在，并在CPUCPU上上运行；运行； 就绪状态（就绪状态（ReadyReady），一个进程已经

28、具备运行条件，一个进程已经具备运行条件，但由于无但由于无CPUCPU暂时不能运行的状态（当调度给其暂时不能运行的状态（当调度给其CPUCPU时，立即可以运行）；时，立即可以运行）； 等待状态（阻塞状态，等待状态（阻塞状态，BlockedBlocked），阻塞态、封锁，阻塞态、封锁态、睡眠态，指进程因等待某种事件的发生而暂时态、睡眠态，指进程因等待某种事件的发生而暂时不能运行的状态（即使不能运行的状态（即使CPUCPU空闲，该进程也不可运空闲，该进程也不可运行）。行）。进程状态转换进程状态转换就绪运行运行就绪运行等待等待就绪五状态进程五状态进程v增加： 创建状态(New)：进程刚创建，但还不能运

29、行如：分配和建立PCB表项、建立资源表格并分配资源，加载程序并建立地址空间表。 结束状态(Exit)：进程已结束运行，回收除PCB之外的其他资源，并让其他进程从PCB中收集有关信息。创建创建就绪状态就绪状态执行状态执行状态等待状态等待状态终止终止调度程序调度程序等待某事件等待某事件的发生的发生等待的事件发生等待的事件发生五状态进程转换图五状态进程转换图AdmitRunningNewExitReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseCreatel创建新进程Createl提交（收容）Admitl调度运行(Dispatch)l释放(R

30、elease)n超时（超时（TimeoutTimeout）n事件等待（事件等待（Event WaitEvent Wait）n事件出现（事件出现（Event OccursEvent Occurs）挂起进程模型挂起进程模型v挂起（Suspend）：一些低优先级进程可能等待较长时间而被对换至外存，为运行进程提供足够内存。 阻塞挂起（Blocked, suspend） ：进程在外存并等待某事件的出现； 就绪挂起（Ready, suspend）：进程在外存，但只要进入内存，即可运行；OSLec345七状态进程转换图七状态进程转换图挂起（挂起（SuspendSuspend）：把一个进程从内存转到外存：把一

31、个进程从内存转到外存激活（激活（ActivateActivate）：把一个进程从外存转到内存：把一个进程从外存转到内存2.2 2.2 进程控制进程控制 v进程控制机构v进程创建v进程撤消v进程阻塞v进程唤醒v进程挂起与激活进程控制机构进程控制机构 进程控制是指系统使用具有特定功能的程序来创建进程、撤销进程以及完成进程状态间的转换。v负责控制进程从创建到撤消的自动执行与协调；vOS内核常驻内存；v进程管理模块：由相关的原语组成。2.2.1 原语原语操作（Atomic Operation） ： 操作系统内核中由若干条指令构成用于完成特定功能的小过程。 原语过程在执行时是不可分割的，可以看成是机器指

32、令的延伸。一般用屏蔽中断来实现 OS内核中的进程管理模块进程控制原语：进程控制原语：I. 进程创建原语进程创建原语II. 进程撤消原语进程撤消原语III.进程状态转换原语进程状态转换原语1.1.进程的创建进程的创建进程创建主要功能进程创建主要功能2.2.2 2.2.2 进程控制原语进程控制原语（1 1）申请一个空闲的）申请一个空闲的PCBPCB（2 2）为新进程分配资源）为新进程分配资源（3 3）将新进程的）将新进程的PCBPCB初始化初始化（4 4）将新进程加到就绪队列中）将新进程加到就绪队列中 何时创建：何时创建：用户登录、用户登录、 作业调度、提供服务、应用请求作业调度、提供服务、应用请

33、求1. 进程创建 (1) 由系统程序模块统一创建，例如在批处理系统中，由操作系统的作业调度程序为用户作业创建相应的进程以完成用户作业所要求的功能。(2) 由父进程创建，例如在层次结构的系统中，父进程创建子进程以完成并行工作。 由系统统一创建的进程之间的关系是平等的，它们之间一般不存在资源继承关系。而在父进程创建的进程之间则存在隶属关系，且互相构成树型结构的家族关系。属于某个家族的一个进程可以继承其父进程所拥有的资源。无论是哪一种方式创建进程，在系统生成时，都必须由操作系统创建一部分承担系统资源分配和管理工作的系统进程。进程创建与撤消进程创建与撤消 无论是系统创建方式还是父进程创建方式，都必须调

34、用创建原语来实现。 创建原语扫描系统的PCB 链表，在找到空PCB表之后，填入调用者提供的有关参数，最后形成代表进程的PCB结构。这些参数包括：进程名、进程优先级0 、进程正文段起始地址0 、资源清单0等。进程创建与撤消进程创建与撤消进程创建原语进程创建原语进程创建进程创建（Creat( )）v 进程之间的关系： 父、子进程与祖先进程：PCB中标识 继承归还资源、“父”创建“子”、父撤子消引起创建进程的事件引起创建进程的事件l用户登录、作业调度、提供服务、应用请求用户登录、作业调度、提供服务、应用请求进程创建的过程进程创建的过程l申请空白申请空白PCB、为新进程分配资源、初始化、为新进程分配资

35、源、初始化PCB、插入就绪进程队列、插入就绪进程队列PDPBPEPCPFPAPIPHPGPJPKPLPMPNHD就绪队列指针就绪队列指针PCB0 4PCB1 PCB2PCB3PCB4 12PCB5 0PCB6PCB7 8PCB8 11PCB9PCB10PCB11 25PCB12 5空空PCB队列指针队列指针RAM程序程序+数据数据PCB7 0PCB5 7以下几种情况导致进程被撤消：(1) 该进程已完成所要求的功能而正常终止。(2) 由于某种错误导致非正常终止。(3) 祖先进程要求撤消某个子进程/外界干预。 无论哪一种情况导致进程被撤消，进程都必须释放它所占用的各种资源和PCB 结构本身，以利于

36、资源的有效利用。另外，当一个祖先进程撤消某个子进程时，还需审查该子进程是否还有自己的子孙进程，若有的话，还需撤消其子孙进程的 PCB结构和释放它们所占有的资源。2. 进程撤消进程撤消 撤消原语首先检查 PCB进程链或进程家族，寻找所要撤消的进程是否存在。如果找到了所要撤消的进程的 PCB结构，则撤消原语释放该进程所占有的资源之后，把对应的 PCB 结构从进程链或进程家族中摘下并返回给 PCB 空队列。如果被撤消的进程有自己的子进程，则撤消原语先撤消其子进程的 PCB 结构并释放子进程所占用的资源之后，再撤消当前进程的 PCB 结构和释放其资源。进程撤消（进程撤消（Terminat( )）v引起

37、进程终止（Termination）的事件正常结束：执行到最后的结束指令、中断异常结束：出现错误或因故障而被迫终止外界干扰：进程应外界的请求而终止运行v进程撤消的过程检索进程状态、结束并置调度标志、撤销其所有的子进程、归还资源、移出队列一个进程可以向其父进程申请撤消自己；也可以因父进程的被撤销而被同时撤消。PDPBPEPCPFPAPIPHPGPJPKPLPMPNT_RQT()主要功能：主要功能：从系统的从系统的PCBPCB表中找到指定进程的表中找到指定进程的PCBPCB。回收该进程所占用的全部资源。回收该进程所占用的全部资源。若该进程还有子孙进程，回收它们所占有的全若该进程还有子孙进程，回收它们

38、所占有的全部资源。部资源。释放被终止进程的释放被终止进程的PCB,PCB,并从原来队列中摘走。并从原来队列中摘走。 2. 2. 撤销进程撤销进程主要功能是：主要功能是： 3. 3. 更换进程映像更换进程映像 释放子进程原来程序和数据所占用内存空间。释放子进程原来程序和数据所占用内存空间。从磁盘上找出子进程所要执行的程序和数据通从磁盘上找出子进程所要执行的程序和数据通常以可执行文件的形式存放）。常以可执行文件的形式存放）。分配内存空间，装入新的程序和数据。分配内存空间，装入新的程序和数据。 为子进程建立初始的运行环境为子进程建立初始的运行环境 主要是对各个寄存器初始化主要是对各个寄存器初始化,

39、,返回到用户态返回到用户态, ,运行该进程的程序。运行该进程的程序。 进程的创建原语和撤消原语完成了进程从无到有，从存在到消亡的变化。被创建后的进程最初处于就绪状态，然后经调度程序选中后进入执行状态。 这里主要介绍实现进程的执行状态到等待状态，又由等待状态到就绪状态转换的两种原语，即阻塞原语与唤醒原语。 阻塞原语在一个进程期待某一事件发生，但发现条件尚不具备时，被该进程调用来阻塞自己。阻塞原语在阻塞一个进程时，由于该进程正处于执行状态，故应先中断处理机和保存该进程的CPU现场。然后将被阻塞进程置“阻塞”状态后插入等待队列中，再转进程调度程序选择新的就绪进程投入运行。进程的阻塞与唤醒进程的阻塞与

40、唤醒进程阻塞的基本过程进程阻塞的基本过程v找到相应进程的PCB；v如果该进程为执行状态，则保护其现场，将其状态改变为等待状态，停止运行，并把该PCB插入到相应的等待队列中去；v若为就绪状态，则将其状态修改为等待状态，把它移出就绪队列，并插入到等待队列中去。 当等待队列中的进程所等待的事件发生时，等待该事件的所有进程都将被唤醒。 唤醒一个进程有两种方法：系统进程唤醒、由事件发生进程唤醒。 当由系统进程唤醒等待进程时，系统进程统一控制事件的发生并将“事件发生”这一消息通知等待进程。从而使得该进程因等待事件已发生而进入就绪队列。由事件发生进程唤醒时，事件发生进程和被唤醒进程之间是合作关系。因此，唤醒

41、原语既可被系统进程调用，也可被事件发生进程调用。称调用唤醒原语的进程为唤醒进程。进程的阻塞与唤醒进程的阻塞与唤醒进程的状态转换原语进程的状态转换原语唤醒唤醒进程因等待某事件的发生而处于等待状态，当等待事件发生后，就要用唤醒原语将其唤醒。唤醒原语的基本操作：在等待队列中找到相应进程的PCB，将其从等待队列中移出；置其状态为就绪状态，然后把该PCB插入就绪队列中；等待调度程序调度。 主要功能：主要功能：把进程从相应的等待队列中摘下；把进程从相应的等待队列中摘下；将现行状态改为就绪态，然后把该进程插入到将现行状态改为就绪态，然后把该进程插入到就绪队列中；就绪队列中；如果被唤醒进程比运行进程有更高的优

42、先级，如果被唤醒进程比运行进程有更高的优先级，则设置重新调度标志。则设置重新调度标志。 5. 5. 唤醒进程唤醒进程 2.3.1 2.3.1 进程调度的基本概念进程调度的基本概念 进程调度，它协调和控制各进程对进程调度，它协调和控制各进程对CPUCPU的使的使用，按照一定的调度原则和某种调度算法从就用，按照一定的调度原则和某种调度算法从就绪队列中选择一个进程，把绪队列中选择一个进程，把CPUCPU分配给该进程运分配给该进程运行。行。 2.3 2.3 进程调度进程调度 1.1.记录当前进程的情况。记录当前进程的情况。 如进程名、指令计数器、状态寄存器如进程名、指令计数器、状态寄存器 及所有通用寄

43、存器等现场信息。及所有通用寄存器等现场信息。2.2.根据一定的调度算法，从就绪队列中根据一定的调度算法，从就绪队列中 选择一个进程获得处理机。选择一个进程获得处理机。3.3.进程上下文切换进程上下文切换2.3.2 2.3.2 进程调度的功能进程调度的功能 1.1.可剥夺调度方式可剥夺调度方式 2.3.3 2.3.3 进程调度方式进程调度方式 该方式规定，当一个进程正在运行时，系该方式规定，当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。机，将之分配给其它进程。剥夺原则有：剥夺原则有：(1)(1)优先权原则。优先权高

44、的进程可以剥夺优优先权原则。优先权高的进程可以剥夺优先权低的进程而运行；先权低的进程而运行；(2)(2)短进程优先原则。短进程到达后可以剥夺短进程优先原则。短进程到达后可以剥夺长进程的运行；长进程的运行；(3)(3)时间片原则。一个时间片用完后重新调度时间片原则。一个时间片用完后重新调度。 下面我们仍以上述三个进程的情况为例下面我们仍以上述三个进程的情况为例，说明基于时间片原则的剥夺调度方式。，说明基于时间片原则的剥夺调度方式。由下图可以看出，由下图可以看出，P1P1、P2P2、P3P3的周转时间的周转时间分别为分别为2626、1010、6 6个单位时间，而平均周转个单位时间，而平均周转时间就

45、由剥夺方式的时间就由剥夺方式的231/2231/2，降低为，降低为1414个单个单位时间。位时间。 该方式规定，分派程序一旦把处理机分配给该方式规定，分派程序一旦把处理机分配给某进程后便给它一直运行下去，直到进程完成或某进程后便给它一直运行下去，直到进程完成或发生某事件发生某事件(如提出如提出I/O请求请求)而阻塞时，才把处理而阻塞时，才把处理机分配给另一进程。这种调度发生的优点是简单、机分配给另一进程。这种调度发生的优点是简单、系统开销小、貌似公正。但却可能导致系统性能系统开销小、貌似公正。但却可能导致系统性能的恶化，表现为：的恶化，表现为：(1)一个紧急任务到达时，不能立即投入运行，以一个

46、紧急任务到达时，不能立即投入运行，以至延误时机；至延误时机；(2)若干个后到的短作业，须等待长作业运行完毕，若干个后到的短作业，须等待长作业运行完毕，致使短作业的周转时间增加。致使短作业的周转时间增加。 2.非剥夺调度方式非剥夺调度方式 例如，有三个进程例如，有三个进程P1,P2,P3先后先后(但几乎但几乎在同时在同时)到达，它们分别需要到达，它们分别需要20、4和和2个单位个单位时间运行完毕。若它们就按时间运行完毕。若它们就按P1、P2、P3的顺的顺序执行且不可剥夺，则三进程各自的周转时序执行且不可剥夺，则三进程各自的周转时间分别为间分别为20、24和和26个单位时间，平均周转个单位时间，平

47、均周转时间是时间是231/2个单位时间。这种非剥夺发式对个单位时间。这种非剥夺发式对短作业短作业P3而言是不公平的。而言是不公平的。 响应时间：响应时间： 进程自进入就绪队列开始至进程进程自进入就绪队列开始至进程 占用占用CPUCPU之间的时间间隔之间的时间间隔周转时间：周转时间： 进程自进入就绪队列开始至进程进程自进入就绪队列开始至进程 结束之间的时间间隔结束之间的时间间隔CPUCPU吞吐量：单位时间内运行结束的进程个数吞吐量：单位时间内运行结束的进程个数2.3.4 2.3.4 进程调度的考量标准进程调度的考量标准 进程调度的原则进程调度的原则调度目标和原则： 在多道程序环境下，进程数目往往

48、多于处理机数目，致使它们争用处理机。这就要求系统能够按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能(吞吐量、响应时间)在很大程度上取决于进程调度性能的好坏，因而进程调度便成为系统设计的中心问题之一。调度目标和原则主要有以下几点：调度目标和原则主要有以下几点：1.公平性公平性(Fairness)：确保每个进程都能获得公确保每个进程都能获得公平的平的CPU时间片时间片2.高效性高效性(Efficiency)：使使CPU100的时间都的时间都在工作在工作3.响应时间响应时间(Re

49、sponseTime)：将交互用户的响将交互用户的响应时间减至最少应时间减至最少4.Turnaround：将批处理用户等待输出的时间将批处理用户等待输出的时间减至最少减至最少5.吞吐量：吞吐量：将每个小时处理的作业量提高至最将每个小时处理的作业量提高至最大大2.3.4 进程调度算法进程调度算法先进先出(FIFO)调度 优先数法时间片轮转法(RR)多队列反馈法最高响应比优先法 该算法总是把处理机分配给最先进入就该算法总是把处理机分配给最先进入就绪队列的进程，即就绪队列按进入的先后次绪队列的进程，即就绪队列按进入的先后次序排队，调度时，选就绪队列中的对首进程序排队，调度时，选就绪队列中的对首进程投

50、入执行。一个进程一旦分得了处理机，便投入执行。一个进程一旦分得了处理机，便一直执行下去，直到该进程完成或因发生某一直执行下去，直到该进程完成或因发生某事件而阻塞时，才释放处理机事件而阻塞时，才释放处理机。先进先出先进先出(FIFO)调度调度先来先服务（先来先服务（FCFS）v 主要用于作业调度，也可用于进程调度。v 用于作业调度： 每次从后备作业队列中选择最先进入的作业，将它们调入内存，为它们分配资源、创建进程，然后挂到就绪进程队列上。 有利于长作业，而不利于短作业。v 用于进程调度： 每次从就绪进程队列中选择最先进入的进程，为之分配处理机，使之投入运行。 直到运行完成进程才会让出处理机-非抢

51、占式。v 性能评价： 周转时间 = 完成时间 到达时间 带权周转时间 = 周转时间 / 服务（运行）时间进程编码到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99 短作业短作业 / 进程优先进程优先（SJ/PF）v 短作业优先（SJF） 从后备队列中选择估计运行时间最短的作业，调入内存运行。v 短进程优先（SPF） 从就绪队列中选出估计运行时间最短的进程，将处理机分配给它，使它立即执行。 直到运行完成进程才会让出处理机-非抢占式。v 缺点： 对长作业不利，有可能长期不被调度； 完全没

52、考虑作业的紧迫程度（某些特殊的）； 用户做出的估计时间带有很大的主观性。 进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8FJS完成时间4918613周转时间4816398带权周转时间1 2.673.11.52.252.1调度算法作业情况优先数法优先数法 按某种原则对就绪队列中的每个进程赋予一个优先级,进程调度时则根据进程的优先级确定选择顺序，即把处理机分配给就绪队列中优先级高的进程。（1）静态优先数法）静态优先数法 静态优先数法是指在进程创建时就赋给它一个优先数。进程在整个生命周期内其优先数

53、不再变化 。 确定进程的优先数的原则：确定进程的优先数的原则： 1）按照进程的类型确定 2）按照进程使用资源的类型和数量确定 3）按照进程长度确定，短作业优先于长作业 4）按用户要求，由用户高价购买作业优先权 （2）动态优先数法）动态优先数法 进程的生命期内根据进程特性的动态变化、各进程对处理机使用的轻重缓急修改其优先数。 优点优点: 防止有些进程长期垄断处理机 缺点缺点: 系统开销比较大 优先级（优先级（FPF）v 既能用于作业调度，也可用于进程调度。v 调度思想： 从队列中选择优先权最高的调度单元，装入内存或分配给处理机。 对进程调度而言，有非抢占式和抢占式两种。v 优先权 静态优先权、动

54、态优先权。v 高响应比优先调度算法 动态优先权，与作业等待时间相关。 等待时间 + 要求服务时间优先权 = - 要求服务时间Rp 响应比： 等待时间 + 要求服务时间 响应时间 Rp = - = - 要求服务时间 要求服务时间该调度算法大大改进了FCFS和SJF算法的缺点。 3时间片轮转法时间片轮转法(RR)将系统中所有的就绪进程按照将系统中所有的就绪进程按照FCFS原则，排成一个队列。原则，排成一个队列。每次调度时将每次调度时将CPU分派给队首进程，让其执行一个时间分派给队首进程，让其执行一个时间片。片。（1）时间片大小的选择）时间片大小的选择QRN （Q 为时间片；为时间片；R 为响应时间

55、；为响应时间；N 为就绪进为就绪进程数）程数）（2）时间片大小的重要性）时间片大小的重要性 ）如果时间片过大，可使时间片轮转调度算法已退）如果时间片过大，可使时间片轮转调度算法已退化为化为FCFS调度算法，因而无法获得令用户满意的响应时调度算法，因而无法获得令用户满意的响应时间。间。 ）如果时间片取得太小，其处理机调度开销将会变）如果时间片取得太小，其处理机调度开销将会变得很大得很大 时间片轮转时间片轮转v特别适用于分时系统的可抢占方式的调度算法。v时间片： 大小：几ms 几百ms 与系统性能的关系v实现方法： 由计时器发出时钟中断，引起一次轮转调度。多级反馈队列多级反馈队列v前面所述调度算法

56、的局限性v多级反馈队列调度算法的思想 设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片； 新创建的进程挂到第一优先级的队列后，然后按 FCFS 原则排队等待调度。当轮到其执行时，如它能在时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列后，； 仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推；新进程可抢占低级进程的处理机。4.多队列反馈法多队列反馈法 把就绪进程按优先级排成多个队列，同队列的把就绪进程按优先级排成多个队列，同队列的进程具有相同的时间片。高优先级队列的时间片进程具有相同的时间片。高优先级队列的时间片比低优先级队列的小比低优先级队列的小

57、。多级反馈队列调度算法的性能 能较好地满足各种类型用户（进程）的需要。 终端（交互）型作业用户 短批处理作业用户 长批处理作业用户最高响应比优先法最高响应比优先法（HRN）vFCFS方式只考虑了每个作业的等待时间，未考虑执行时间，而SJF方式刚好相反，HRN调度策略同时考虑了每个作业的等待时间长短和估计需要的执行时间v响应比 R=(W+T)/T=1+W/Tv调度时选择R最大者投入执行 2.4.1 2.4.1 临界资源和临界区临界资源和临界区2.4 2.4 进程的同步与互斥进程的同步与互斥 1. 1. 临界资源临界资源 一次只允许一个进程使用的资源称一次只允许一个进程使用的资源称为临界资源。为临

58、界资源。 2. 2. 临界区临界区访问临界资源的程序区域称为临界区。访问临界资源的程序区域称为临界区。 合理的临界资源使用： 1 ） 一次只能允许一个进程进入空闲的临界区；2） 如已有进程进入临界区，其它进程必须等待；3） 进程在临界区应当限定时间；4） 无法进入临界区的进程，应当让出CPU。 2.4.2 2.4.2 进程的同步进程的同步 进程间为了完成一个共同的目标，必须互进程间为了完成一个共同的目标，必须互相合作的协同工作关系、有前后次序的直接制相合作的协同工作关系、有前后次序的直接制约关系称为进程的同步。约关系称为进程的同步。 例如：在数据库中，要将一组数据做汇总打印，既要在不同的库文件

59、中取出数据，又要将数据送入打印机中输出。那么，所负责作业的各个进程就要发生同步关系，否则将产生错误。 2.4.3 2.4.3 进程的互斥进程的互斥 多个进程因不能同时访问临界资源而产生多个进程因不能同时访问临界资源而产生的间接制约关系称为进程的互斥。的间接制约关系称为进程的互斥。 例如：两个都需要打印的进程A、B，同时请求打印，而打印机只有一台。给哪个进程使用？这两个进程就要产生互斥，否则，会发生混乱的结果。 用锁操作原语实现互斥用锁操作原语实现互斥 定义锁变量定义锁变量W w = 0，表示锁关表示锁关 w = 1，表示锁开，表示锁开关锁原语关锁原语 lock (w): while (w =

60、= 1) ; w = 1 ;开锁原语开锁原语 unlock (w): w = 0; 用锁操作原语实现互斥用锁操作原语实现互斥 锁操作的步骤：锁操作的步骤：1） 验锁：先检查锁的状态。如为闭状态，则验锁：先检查锁的状态。如为闭状态，则 等待其打开；如为已打开，将其关闭；等待其打开；如为已打开，将其关闭；2） 执行临界区程序；执行临界区程序；3） 开锁：将锁打开，退出临界区。开锁：将锁打开，退出临界区。模拟理解：这个过程尤如一个人一个进房间。模拟理解：这个过程尤如一个人一个进房间。若门是关着的，等门打开；若门是开着的，进去若门是关着的，等门打开；若门是开着的，进去后并关门；办完事情后开门（出来）。