第二章-进程-管理资料课件

l 现代现代OS的的重要特性重要特性:程序的程序的并发性并发性和资源的和资源的共享性共享性。l现代现代OS是是围绕进程和线程围绕进程和线程进行设计和构造的。进行设计和构造的。lOS 必须必须交替执行交替执行多个进程，使处理器的利用多个进程，使处理器的利用率最大。率最大。lOS OS 必须必须按照特定的策略按照特定的策略给进程给进程分配资源分配资源，同，同时避免时避免死锁死锁。lOS OS 可以支持进程间的可以支持进程间的通信通信和用户和用户创建创建进程。进程。本章主要内容本章主要内容1.进程的概念进程的概念2.进程的描述进程的描述：PCB、状态、状态、3.进程的控制进程的控制：创建、撤消、阻塞、唤醒：创建、撤消、阻塞、唤醒4.进程调度进程调度：分配：分配CPU给某一进程给某一进程5.线程的引入：线程的引入：6.进程的低级通信进程的低级通信：互斥、同步、：互斥、同步、P/V操作、管程操作、管程7.进程的高级通信进程的高级通信：消息传递：消息传递8.死锁死锁：多进程竞争有限资源：多进程竞争有限资源1.1.程序的顺序执行程序的顺序执行 程序的顺序执行：程序的顺序执行：在任何时刻，机器只执行一个操作，只有在前一个操作执行完后，才能执行后继操作。例例 作业i的输入操作、计算操作和打印操作分别用Ii、Ci、Pi表示。则顺序执行过程为：2.1 2.1 进程的引入及其概念进程的引入及其概念I1I2I3P1C1P2P3C2C3程序顺序执行的特点：程序顺序执行的特点：l顺序性顺序性：在任何时刻，机器只执行一个操作，只有在任何时刻，机器只执行一个操作，只有在前一个操作完成后，才进行下一个操作。在前一个操作完成后，才进行下一个操作。l封闭性封闭性：程序在运行时：程序在运行时独占全机资源独占全机资源。因此，这些。因此，这些资源的状态资源的状态只能由运行的这个程序决定和改变。不只能由运行的这个程序决定和改变。不受外界因素影响。受外界因素影响。l可再现性可再现性：程序执行时，只要初始条件相同，无论：程序执行时，只要初始条件相同，无论程序连续运行，或断断续续地运行，程序的执行结程序连续运行，或断断续续地运行，程序的执行结果与其执行速度无关，其最终结果不变。果与其执行速度无关，其最终结果不变。l优优点点：由由于于顺顺序序程程序序的的封封闭闭性性和和可可再再现现性，为程序员性，为程序员调试程序调试程序带来了很大方便。带来了很大方便。l缺缺点点：由由于于资资源源的的独独占占性性，使使得得系系统统资资源源利用率非常低利用率非常低。2.2.程序的并发执行程序的并发执行 程序的并发执行程序的并发执行：是指若干个程序（或程序段）：是指若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的，一个程序（或程序段）的行在时间上是重叠的，一个程序（或程序段）的执行尚未结束，另一个程序（或程序段）的执行执行尚未结束，另一个程序（或程序段）的执行已经开始。已经开始。l以资源的以资源的共享共享为条件为条件l提高了系统提高了系统资源利用率资源利用率、系统、系统吞吐量吞吐量。例例例例 在下面的在下面的有向无环图有向无环图中，作业中，作业i i的输入操作、的输入操作、计算操作和打印操作分别用计算操作和打印操作分别用I Ii i、C Ci i、P Pi i表示。虽然表示。虽然同一作业中的输入操作、计算操作和打印操作必须同一作业中的输入操作、计算操作和打印操作必须顺序执行，但对一批作业而言，情况就不同了。顺序执行，但对一批作业而言，情况就不同了。I1I2I3I4P1C1P2P3C2C3P4C4并发执行并发执行程序并发执行的特征：程序并发执行的特征：(1,2,3)(1)失去了程序的封闭性和可再现性失去了程序的封闭性和可再现性 程序在并发执行时，多个程序共共享享系系统统中中的的各各种种资资源源，因而这些资源的状状态态将由多个程序来改改变变，致使程序的运行失去了封闭性；由于失去了封闭性，也将导致失去其可再现性。例例 有两个循环程序有两个循环程序A A和和B B，共享一个变量共享一个变量N N。A A每执行每执行一次时都要做一次时都要做 N=N+1N=N+1；B B每执行一次时都要做每执行一次时都要做 print(N),N=0print(N),N=0。并以不同的速度运行。这样，可能。并以不同的速度运行。这样，可能出项下述三种情况（假设某时刻变量出项下述三种情况（假设某时刻变量N N的值为的值为n n）。）。lN=N+1N=N+1,print(N),N=0,print(N),N=0：N N分别为分别为 n+1,n+1,0n+1,n+1,0。lPrint(N),Print(N),N=N+1N=N+1,N=0,N=0：N N分别为分别为 n,n+1,0n,n+1,0。lPrint(N),N=0,Print(N),N=0,N=N+1N=N+1：N N分别为分别为 n,0,1n,0,1 。其计算结果与并发程序的其计算结果与并发程序的执行速度执行速度有关，从而失去有关，从而失去了可再现性了可再现性y=balance;if(y=100)y=y-100;balance=y;x=balance;if(x=100)x=x-100;balance=x;Balance=1000ATM1:ATM2:Balance=?银行自动取款机例银行自动取款机例(2)并行执行的程序间产生了相互制约关系并行执行的程序间产生了相互制约关系 因因共享资源共享资源或或协调完成同一任务协调完成同一任务，使得并发程序使得并发程序之间发生了相互制约关系。之间发生了相互制约关系。例例 系系统统中中并并发发执执行行的的程程序序段段A和和B在在运运行行过过程程中中都都希希望望使使用用打打印印机机输输出出计计算算结结果果，若若系系统统只只有有一一台台打打印印机机，分分得得打打印印机机的的程程序序段段(假假设设A得得到到)可可以以继继续续运运行行，而而没没有有得得到到打打印印机机的的程程序序段段B就就不不得得不不暂暂停停，等等到到有有可可用用打打印印机机时时才才能能继继续续执执行行。我我们们称称这这种种制约关系为制约关系为间接关系间接关系。(3)(3)程序与程序与CPUCPU执行的活动之间不再一一对应执行的活动之间不再一一对应l程程序序：是是完完成成某某一一特特定定功功能能的的指指令令序序列列，是是静静态态的的概概念；念；lCPUCPU执执行行的的活活动动：是是一一个个动动态态概概念念，它它是是程程序序的的执执行行过程。过程。例例 在在分分时时系系统统中中，多多个个用用户户都都调调用用C C编编译译对对自自己己的的源源程程序序进进行行编编译译，实实际际系系统统只只保保留留一一个个编编译译程程序序，多多个个用用户户通通过过共共享享执执行行它它完完成成各各自自源源程程序序的的编编译译工工作作。这这样样，系系统统虽虽然然只只保保留留一一个个编编译译程程序序，但但CPUCPU现现正正在在为为多个用户执行编译多个用户执行编译。由由于于并并发发程程序序的的上上述述这这些些特特点点，使使得得系系统统中中的的活活动动以以及及各各种种活活动动之之间间的的相相互互关关系系非非常常复复杂杂。因因此此，“程程序序”这这个个静静态态的的概概念念已已不不能能如如实实地地反反映映系系统统中中的的活活动动情情况况。为此，现代操作系统引入了为此，现代操作系统引入了进程进程的概念。的概念。3.3.进程的概念进程的概念(1)(1)进程定义进程定义 (2)一一个个具具有有一一定定独独立立功功能能的的程程序序对对某某个个数数据据集集在在处处理理机机上的一次执行过程和分配资源的基本单位。上的一次执行过程和分配资源的基本单位。l 进程这个概念是为了描述系统中各进程这个概念是为了描述系统中各并发活动并发活动而引入的。而引入的。l “进进程程”(processprocess)这这一一术术语语，在在6060年年代代初初期期，首首先先在在美美国国的的麻麻省省理理工工学学院院的的MULTICSMULTICS系系统统和和IBMIBM公公司司的的CTSS/360CTSS/360系系统统中中引引入入的的。只只是是IBM/360IBM/360使使用用了了另另一一个个术术语语任任务务(task)task)，但两者的实际含义是相同的。但两者的实际含义是相同的。l进程是程序的一次执行。进程是程序的一次执行。l进程是可以和其它计算并行执行的计算。进程是可以和其它计算并行执行的计算。l进程是一个程序与其使用的数据在处理机上顺序执进程是一个程序与其使用的数据在处理机上顺序执行时发生的行时发生的活动活动。l进程是程序在一个数据集合上的进程是程序在一个数据集合上的运行过程运行过程。l进程是系统进行进程是系统进行资源分配和调度资源分配和调度的一个的一个独立单位独立单位。l进程是进程是可以和其他程序并行执行的可以和其他程序并行执行的程序的一次执行程序的一次执行lOSOS设置进程是设置进程是为了描述程序的动态执行过程为了描述程序的动态执行过程.l 进程的内涵进程的内涵2 2、进程的特征（、进程的特征（5 5个）个）（1 1）动态性：动态性：进程进程是程序的一次执行，它是一个是程序的一次执行，它是一个动态动态的的概念，是临时的，有生命期的，表现在它由创建而产生，概念，是临时的，有生命期的，表现在它由创建而产生，完成任务后被撤消。完成任务后被撤消。程序程序是完成某个特定功能的指令的是完成某个特定功能的指令的有序序列，它是一个有序序列，它是一个静态静态的概念。的概念。程序程序可以作为一种软可以作为一种软件资源长期保存。件资源长期保存。进程进程是把程序作为它的运行实体，没是把程序作为它的运行实体，没有程序，也就没有进程。有程序，也就没有进程。我们把程序看成是一个菜谱，而进程则是按照菜谱进行我们把程序看成是一个菜谱，而进程则是按照菜谱进行烹调的过程。烹调的过程。（2 2）并发性：并发性：多个进程实体，同存于内存中，能在一多个进程实体，同存于内存中，能在一段时间内同时执行；程序是不能并发执行的。段时间内同时执行；程序是不能并发执行的。（3 3）独立性：）独立性：进程是系统进行资源分配和调度的一个进程是系统进行资源分配和调度的一个独立单位独立单位；程序则不是。；程序则不是。例例 以多用户进程共享一个编译程序为例，为多个以多用户进程共享一个编译程序为例，为多个用户执行编译时，显然用户执行编译时，显然CPUCPU的分配是以进程为单位的分配是以进程为单位，而不是以程序为单位。因为主存只有一个编译程序，而不是以程序为单位。因为主存只有一个编译程序，但几个用户的源程序都得到编译。但几个用户的源程序都得到编译。（4）异异步步性性：进进程程以以各各自自独独立立的的、不不可可预预知知的的速速度度向向前前推推进进；或或者者说说，进进程程按按异异步步方方式式运运行行。正正是是这这一一特特征征，将将导导致致程程序序执执行行的的不不可可再再现现性性。因因此此，在在OS中中必必须须采采取取措措施施来来保保证证各各程程序序之之间间能能协协调调运运行行。进程间可以相互作用。进程间可以相互作用。（5）结结构构特特性性：为为了了描描述述和和记记录录进进程程的的运运行行变变化化过过程程，并并使使之之能能正正确确运运行行，应应为为每每个个进进程程配配置置一一个个进进程程控控制制块块。这这样样，从从结结构构上上看看，每每个个进进程程是是由由程程序序段、数据段和进程控制块段、数据段和进程控制块三部分组成。三部分组成。进程与程序的区别进程与程序的区别l进程是动态的，程序是静态的进程是动态的，程序是静态的：程序是有序代码的集合；进：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件，是静态和可以复制的。通常对应着文件，是静态和可以复制的。l进程是暂时的，程序是永久的进程是暂时的，程序是永久的：进程是一个状态变化的过程，：进程是一个状态变化的过程，动态地被创建，执行后消亡；程序可长久保存。动态地被创建，执行后消亡；程序可长久保存。l进程与程序的组成不同进程与程序的组成不同：进程的组成包括程序、数据和进程：进程的组成包括程序、数据和进程控制块（即进程状态信息）。控制块（即进程状态信息）。l进程具有并发特征进程具有并发特征（独立性和异步性）（独立性和异步性）；而程序没有。；而程序没有。l进程与程序的对应关系进程与程序的对应关系：通过多次执行，一个程序可对应多：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。个进程；通过调用关系，一个进程可包括多个程序。作业与进程的区别作业与进程的区别l作业是用户向计算机提交任务的实体，被提交后作业是用户向计算机提交任务的实体，被提交后进入外存的作业等待队列。而进程是完成用户任进入外存的作业等待队列。而进程是完成用户任务的执行实体，被创建后，总有相应部分常驻内务的执行实体，被创建后，总有相应部分常驻内存；存；l一个作业至少由一个进程来执行完成，反之不然；一个作业至少由一个进程来执行完成，反之不然；l作业的概念主要用于批处理操作系统；而进程的作业的概念主要用于批处理操作系统；而进程的概念几乎用于所有的多道系统中。概念几乎用于所有的多道系统中。4.OS的控制结构的控制结构lOS为了管理进程和资源，必须掌握关于为了管理进程和资源，必须掌握关于每个进程和资源每个进程和资源当前状态当前状态的信息。的信息。lOS构造并维护它所管理的每个实体的构造并维护它所管理的每个实体的信息表信息表。共分四种。共分四种不同类型的表。不同类型的表。1.存储器存储器-存储表存储表2.I/O设备设备-I/O表表3.文件文件-文件表文件表4.进程进程-基本进程表基本进程表l存储表存储表：用于跟踪：用于跟踪主存储器主存储器和辅助（虚拟）存储器。保留和辅助（虚拟）存储器。保留在在辅存辅存中的进程使用某种类型的中的进程使用某种类型的虚拟存储虚拟存储或简单的或简单的交换机交换机制制。lI/O表表：用于管理计算机系统中的：用于管理计算机系统中的I/O设备设备和和通道通道。是否已分。是否已分配给某个进程？配给某个进程？l文件表文件表：提供关于文件是否存在、文件在辅存中的位置、：提供关于文件是否存在、文件在辅存中的位置、当前状态和其它属性的信息。当前状态和其它属性的信息。l进程表进程表：用于管理进程。在：用于管理进程。在UNIX系统系统V里，里，进程控制块进程控制块中中的的基本控制块基本控制块占有进程表占有进程表(proc)中的一项。中的一项。2.2 2.2 进程的描述进程的描述1.进程控制块进程控制块 PCBPCB（Process Control Block）OS在管理和控制进程时必须知道什么？在管理和控制进程时必须知道什么？1.它必须知道有哪些进程及他们的位置。它必须知道有哪些进程及他们的位置。2.它必须知道在管理时所必需的进程属性它必须知道在管理时所必需的进程属性l进程控制块进程控制块：与每个进程相关联的：与每个进程相关联的所有所有OS用于控制进程用于控制进程的的属性的集合属性的集合。lPCB是进程是进程存在存在系统中的系统中的唯一标识唯一标识。l进程映像进程映像(进程实体进程实体)：用户程序、用户数据、系统栈和用户程序、用户数据、系统栈和进程控制块。进程控制块。操作系统为了管理进程和资源，必须掌握关于每个进程操作系统为了管理进程和资源，必须掌握关于每个进程和资源当前状态的信息和资源当前状态的信息进程映像进程映像(进程实体进程实体)组成组成l用户程序用户程序：将被执行的程序。：将被执行的程序。l用户数据用户数据：用户空间中的可修改部分。可以：用户空间中的可修改部分。可以包包括括程序数据、程序数据、用户栈用户栈区域和可修改的程序。区域和可修改的程序。l系统栈系统栈：每个进程有一个或多个系统栈，用于：每个进程有一个或多个系统栈，用于保存参数、过程调用地址和系统调用地址。保存参数、过程调用地址和系统调用地址。lPCB：OS控制进程所需要的数据。控制进程所需要的数据。进程空间l任一进程都有自己的地址空间，称为进任一进程都有自己的地址空间，称为进程空间，由程空间，由用户空间用户空间和和系统空间系统空间组成。组成。l用户程序在用户空间执行，只能执行普用户程序在用户空间执行，只能执行普通指令，称处于通指令，称处于用户态用户态；操作系统内核；操作系统内核在系统空间执行，可执行所有指令，称在系统空间执行，可执行所有指令，称处于处于系统态（核心态、管理态）系统态（核心态、管理态）。PCB中的基本信息中的基本信息l进程标识符进程标识符：用于唯一地标识一个进程。：用于唯一地标识一个进程。外部标识符：外部标识符：由创建者提供，通常是由字母、数由创建者提供，通常是由字母、数字所组成，往往是由用户访问进程时使用，便于字所组成，往往是由用户访问进程时使用，便于记忆。如计算进程、打印进程、发送进程、接收记忆。如计算进程、打印进程、发送进程、接收进程等。进程等。内部标识符：内部标识符：OSOS为每一个进程赋予了一个唯一的为每一个进程赋予了一个唯一的整数，作为内部标识。父进程标识符、子进程标整数，作为内部标识。父进程标识符、子进程标识符、用户标识符。识符、用户标识符。l进程的状态进程的状态：说明进程目前所处的状态，进程可能的状：说明进程目前所处的状态，进程可能的状态在下一节描述。态在下一节描述。lCPUCPU现场保护区现场保护区：当进程由于某种原因不能继续运行时，：当进程由于某种原因不能继续运行时，要将其要将其CPUCPU运行的现场信息保存起来，以便下次继续运运行的现场信息保存起来，以便下次继续运行。通常，行。通常，CPUCPU的现场信息包括：的现场信息包括：程序计数器程序计数器(PC)(PC)、工、工作寄存器、程序状态字作寄存器、程序状态字等。等。lCPUCPU的的调调度度信信息息：包包括括进进程程优优先先级级、进进程程所所在在各各种种队队列列的指针。的指针。l进进程程要要执执行行的的程程序序在在主主存存和和外外存存起起始始地地址址，及及存存取取保保护护信息。信息。l进进程程使使用用的的资资源源信信息息：包包括括分分配配给给进进程程的的I/OI/O设设备备、正正在在执执行行的的I/OI/O请请求求信信息息、当当前前进进程程正正打打开开的的文文件件等。等。l记记帐帐信信息息：包包括括CPUCPU占占用用量量，实实际际所所用用时时间间量量，帐帐号等。号等。l进进程程之之间间的的家家族族关关系系：在在进进程程的的树树型型结结构构系系统统（如如UNIXUNIX）中中，进进程程之之间间存存在在着着家家族族关关系系。创创建建进进程程的的进程称为父进程，被创建进程称为子进程。进程称为父进程，被创建进程称为子进程。l进程的连接指针：进程的连接指针：将相同状态的进程连接在一起。将相同状态的进程连接在一起。PCBPCB表表l系统把所有系统把所有PCBPCB组织在一起，并把它们放组织在一起，并把它们放在内存的固定区域，就构成了在内存的固定区域，就构成了PCBPCB表表lPCBPCB表的大小决定了系统中最多可同时存表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度在的进程个数，称为系统的并发度l可以根据进程的不同状态进行组织可以根据进程的不同状态进行组织进程上下文进程上下文进程上下文是对进程执行活动全过程的静态描述。进程上下文是对进程执行活动全过程的静态描述。进程上下文由进程的用户地址空间内容（正文段、进程上下文由进程的用户地址空间内容（正文段、数据集等）、硬件寄存器内容及与该进程相关的核心数据集等）、硬件寄存器内容及与该进程相关的核心数据结构组成。数据结构组成。一个进程的执行是在该进程的上下文中执行的，当一个进程的执行是在该进程的上下文中执行的，当系统调度新进程占用处理机时，新老进程的上下文将系统调度新进程占用处理机时，新老进程的上下文将进行切换。进行切换。三种三种基本状态。基本状态。进程执行时的进程执行时的间断性间断性，决定了进程可能具有多，决定了进程可能具有多种状态。种状态。(1)(1)运行态运行态(running)(running)：正在：正在CPUCPU上执行的进程所处状态为运行上执行的进程所处状态为运行状态。单状态。单CPUCPU系统只有一个进程处于运行状态；多系统只有一个进程处于运行状态；多CPUCPU系统系统可能有多个进程处于执行状态。可能有多个进程处于执行状态。(2)(2)阻塞态阻塞态(blocked)(blocked)：又称：又称等待态等待态。当一个进程因等待某个条。当一个进程因等待某个条件发生而不能运行时处于阻塞态。处于阻塞态的进程在逻件发生而不能运行时处于阻塞态。处于阻塞态的进程在逻辑上是不能运行的，即使辑上是不能运行的，即使CPUCPU空闲，它也不能占用空闲，它也不能占用CPUCPU。2.进程的状态进程的状态 (3)(3)就绪态就绪态(ready)(ready)：已分配到除：已分配到除CPUCPU之外的所有之外的所有必要的资源后，只要能再获得必要的资源后，只要能再获得CPUCPU，便可立即执，便可立即执行。多个处于就绪状态的进程排成一个或多个队行。多个处于就绪状态的进程排成一个或多个队列列-就绪队列。就绪队列。这三种状态的相互转换如下图所示：这三种状态的相互转换如下图所示：运行态运行态就绪态就绪态阻塞态阻塞态时间片用完时间片用完进程调度进程调度等待某个等待某个事件发生事件发生某个事件已经发生某个事件已经发生图图2.2 2.2 进程的状态及其转换进程的状态及其转换l就绪态就绪态-运行态运行态：处于就绪态的某进程被处于就绪态的某进程被进程调度程序进程调度程序的的执行选中时。执行选中时。l运行态运行态-阻塞态阻塞态：是由运行进程是由运行进程自己主动改变自己主动改变的。的。例例 一个正在运行的进程启动了某一外围设备后，等待该外围一个正在运行的进程启动了某一外围设备后，等待该外围设备传输完成时，使自己由运行态变为阻塞态。设备传输完成时，使自己由运行态变为阻塞态。l阻塞态阻塞态-就绪态就绪态：是由是由外界事件引起外界事件引起的。的。例例 上面所述上面所述的外围设备传输已经完成时，请求中断，由的外围设备传输已经完成时，请求中断，由I/OI/O中断处理中断处理程序程序把因等待这一把因等待这一I/OI/O完成而阻塞的进程变为就绪态。完成而阻塞的进程变为就绪态。由进程状态转换图可以看出：由进程状态转换图可以看出：l运行态运行态-就绪态：就绪态：处于运行态的处于运行态的进程被剥夺进程被剥夺CPUCPU时。时。例例 采用时间片轮转法调度时，当前运行进程用采用时间片轮转法调度时，当前运行进程用完分给它的时间片后，将由运行态变为就绪态完分给它的时间片后，将由运行态变为就绪态；或采用优先级调度时，若有更高优先级的进程变或采用优先级调度时，若有更高优先级的进程变为就绪态，当前进程被迫放弃为就绪态，当前进程被迫放弃CPUCPU，使自己由运行，使自己由运行态变为就绪态，之后转进程调度。态变为就绪态，之后转进程调度。l由于系统、进程自身和外界的原因，可能由于系统、进程自身和外界的原因，可能使一个使一个进程多次反复地经历三个基本状态的转换进程多次反复地经历三个基本状态的转换，才能，才能最终达到完成而撤消。最终达到完成而撤消。(4)(4)创建态：创建态：刚刚建立，还未送入就绪队列的状态。刚创刚刚建立，还未送入就绪队列的状态。刚创建，并为它分配资源。建，并为它分配资源。(5)(5)终止状态：终止状态：已正常结束或异常结束，但尚未撤消时。已正常结束或异常结束，但尚未撤消时。暂留在系统中，以便其它进程去收集该进程的有关信息。暂留在系统中，以便其它进程去收集该进程的有关信息。创建态创建态就绪态就绪态：OS准备好再准备好再接纳接纳一个进程时，把一个进一个进程时，把一个进程从新建状态转换到就绪状态。大多数系统程从新建状态转换到就绪状态。大多数系统基于基于现有的现有的进程数进程数或分配给现有进程的或分配给现有进程的虚存数量虚存数量设置一些限制，以设置一些限制，以确保不会因为确保不会因为活跃进程活跃进程的数量过多而导致系统的性能下的数量过多而导致系统的性能下降。降。图图2.3 进程的五种状态进程的五种状态创建态创建态运行态运行态阻塞态阻塞态终止态终止态进程调度进程调度被抢占被抢占事件完成事件完成等待事件等待事件进程完成进程完成就绪态就绪态Fork()接纳接纳进程的七种状态进程的七种状态将主存中某个进程的一部分或全部移到磁盘的挂起队列中将主存中某个进程的一部分或全部移到磁盘的挂起队列中 PCBPCB是是系系统统对对进进程程进进行行统统一一管管理理的的依依据据。一一个个系系统统可可有有几几十十个个、几几百百个个PCBPCB。为为了了便便于于系系统统查查找找，目目前前常常用用的的组组织织方方式式如下：如下：（1）线性）线性方式方式：3.进程队列进程队列 图图2-4 PCB线性队列示意图线性队列示意图 （2）链链接接方方式式：把把具具有有相相同同状状态态的的PCBPCB，用用其其中中的的连连接接字，链接成一个队列。字，链接成一个队列。每每一一个个队队列列有有一一个个专专用用队队列列指指针针指指出出该该队队列列中中第第一一个个进进程程PCBPCB所所在在位位置置。这这样样就就形形成成了了就就绪绪队队列列、阻阻塞塞队队列列。处处于于就就绪绪态态的的进进程程可可按按照照某某种种策策略略排排成成多多个个就就绪绪队队列列。处处于于阻阻塞塞态态的的进进程程又又可可以以根根据据阻阻塞塞的的原原因因不不同同组组织织成成多多个个阻阻塞塞队队列列。例例 等等待待磁磁盘盘I/OI/O队队列列，等等待待磁磁带带I/OI/O队列等。队列等。图图2-5 PCB链接队列示意图链接队列示意图(2)(2)索索引引方方式式：系统根据进程的状态，建立几张索引表，并把索引表在内存的首地址记录于内存中一些专用单元。图图2-6 PCB索引结构示意图索引结构示意图2.3 2.3 进程的控制进程的控制l进程控制进程控制：指系统使用一些具有特定功能的：指系统使用一些具有特定功能的程程序段序段来来创建、撤消创建、撤消进程以及完成进程进程以及完成进程各状态间各状态间转换转换。l原语原语：是原子操作。一个操作中的所有动作，：是原子操作。一个操作中的所有动作，要么全做，要么全不做，不允许中断。不可分要么全做，要么全不做，不允许中断。不可分割的操作。用于进程控制的割的操作。用于进程控制的程序段程序段。l用于进程控制的用于进程控制的原语原语有：有：创建原语；撤消原语；创建原语；撤消原语；阻塞原语；唤醒原语阻塞原语；唤醒原语等。等。为了防止为了防止OS及关键数据如及关键数据如PCB等，受到破坏等，受到破坏，通常处理机，通常处理机有两种执行状态：有两种执行状态：l系统态系统态：核心态（管态）。具有较高的特权，能执行一切：核心态（管态）。具有较高的特权，能执行一切指令，访问所有寄存器和存储区。指令，访问所有寄存器和存储区。l用户态用户态：目态，具有较低特权，只能执行规定的指令，访：目态，具有较低特权，只能执行规定的指令，访问指定的寄存器和存储区。问指定的寄存器和存储区。用户程序用户程序：运行在用户态，不能去执行：运行在用户态，不能去执行OS指令和访问指令和访问OS区域。区域。OS内核内核：运行在系统态。：运行在系统态。进程控制进程控制：是由：是由OS内核实内核实现的。现的。(1)(1)创建进程的时机创建进程的时机l用户登录用户登录：在分时系统中，用户在终端键入登录命：在分时系统中，用户在终端键入登录命令后，系统将为该终端用户建立一进程，并把它插令后，系统将为该终端用户建立一进程，并把它插入就绪队列。入就绪队列。l提供服务提供服务：当运行中的用户程序提出某种：当运行中的用户程序提出某种请求请求后，后，系统系统将专门创建一个进程来提供用户所需要的服务。将专门创建一个进程来提供用户所需要的服务。如如 用户程序请求文件打印，用户程序请求文件打印，OSOS将为之创建一个打将为之创建一个打印进程，打印进程和用户进程可并发执行。印进程，打印进程和用户进程可并发执行。1.1.创建原语创建原语（UNIX系统用系统用fork()）l作业调度作业调度：在批处理系统中，将作业装入内存：在批处理系统中，将作业装入内存时，为它分配必要的资源，系统并立即为它创时，为它分配必要的资源，系统并立即为它创建进程，再插入就绪队列。建进程，再插入就绪队列。l应用请求应用请求：基于应用进程的需要，由它：基于应用进程的需要，由它自己创自己创建一个新进程（子进程）建一个新进程（子进程），可并发执行。，可并发执行。如如某应用程序需要：从键盘读入数据（建立某应用程序需要：从键盘读入数据（建立键盘输入进程）、处理数据、以表格形式在屏键盘输入进程）、处理数据、以表格形式在屏幕上显示结果（表格输出进程）。幕上显示结果（表格输出进程）。一旦一旦OS发现了要求创建新进程的事件后，便调动进程创建原发现了要求创建新进程的事件后，便调动进程创建原语，步骤如下：语，步骤如下：l申请空白申请空白PCB，分配唯一的数字标识符。，分配唯一的数字标识符。l为新进程分配资源为新进程分配资源。为其程序和数据，以及用户栈分配必。为其程序和数据，以及用户栈分配必要的内存空间。要的内存空间。l初始化进程控制块初始化进程控制块。把调用者提供的参数：进程名、进程。把调用者提供的参数：进程名、进程优先级、实体所在主存的起始地址、所需的资源清单、记优先级、实体所在主存的起始地址、所需的资源清单、记帐信息及进程家族关系等填入帐信息及进程家族关系等填入PCB结构中。结构中。l将新进程插入就绪队列将新进程插入就绪队列。(2)进程的创建进程的创建 入口入口查查PCB链表链表有空有空PCB？PCB（I）入进程家族或进程链）入进程家族或进程链PCB(I)入就绪队列入就绪队列将有关参数填入将有关参数填入PCB（I）相应项）相应项取空表取空表PCB(I)返回返回创建失败创建失败无无创建原语流程图创建原语流程图有有撤消撤消：是指撤消进程存在的标志：是指撤消进程存在的标志(PCB)(PCB)。(1)(1)进程终止的时机进程终止的时机l正常结束正常结束：进程运行完，将产生一个中断，通知：进程运行完，将产生一个中断，通知OSOS进程已运行完毕。进程已运行完毕。l异异常常结结束束：进进程程运运行行期期间间，出出现现某某些些错错误误或或故故障障，而而迫迫使使进进程程终终止止。故障中断。故障中断。l外界干预外界干预：l 操作员或操作员或OSOS干预。如发生死锁。干预。如发生死锁。l 父进程请求。父进程父进程请求。父进程有权有权终止子进程。终止子进程。l 父进程终止。此时，父进程终止。此时，OSOS将其子进程终止。将其子进程终止。2.2.撤消原语撤消原语l根根据据被被终终止止进进程程的的标标识识符符，从从PCB集集合合中中检检索索出出该该进进程程的的PCB，从中，从中读出读出其其状态状态。l若若正处于执行状态正处于执行状态，则终止。，则终止。l若有若有子孙进程子孙进程，也须终止，以防成为不可控的。，也须终止，以防成为不可控的。l将其将其全部资源全部资源或归还其父进程或归还系统。或归还其父进程或归还系统。l将其将其PCBPCB从所在队列中从所在队列中移出移出，等待其它程序来搜集信息。，等待其它程序来搜集信息。(2)进程终止的过程进程终止的过程 入口入口返回返回查进程链表或进程家族查进程链表或进程家族有此有此PCB吗？吗？该该PCB有子进程吗？有子进程吗？释放该进程所占有的资源释放该进程所占有的资源释放该释放该PCB结构本身结构本身出错处理出错处理有有无无有有无无(1)(1)引起进程的阻塞和唤醒的事件引起进程的阻塞和唤醒的事件请请求求系系统统服服务务，暂暂得得不不到到满满足足。例例 一一进进程程请请求求打打印印机机，无无，被阻塞，由释放打印机者将其唤醒。被阻塞，由释放打印机者将其唤醒。l启动某种操作启动某种操作。例例 进程启动某进程启动某I/OI/O操作。操作。l新新数数据据尚尚未未到到达达。相相互互合合作作的的进进程程，一一个个须须等等待待另另一一个个提供的数据后才能运行。提供的数据后才能运行。l无无新新工工作作可可做做。例例 发发送送进进程程，无无新新的的发发送送请请求求时时，边边将自己阻塞起来。将自己阻塞起来。3.3.进程的阻塞和唤醒进程的阻塞和唤醒无法运行的进程无法运行的进程自己调用阻塞原语阻塞自己自己调用阻塞原语阻塞自己。l中断中断CPU.CPU.l将其运行现场保存在其将其运行现场保存在其PCBPCB的的CPUCPU现场保护区。现场保护区。l置状态为阻塞态。置状态为阻塞态。l插入相应事件的等待队列插入相应事件的等待队列(阻塞队列阻塞队列)中。中。l转进程调度。转进程调度。(2)(2)阻塞过程阻塞过程被阻塞进程被阻塞进程所期待的事件出现所期待的事件出现了，则由了，则由有关进程有关进程调用唤醒原调用唤醒原语将其唤醒。语将其唤醒。l把被阻塞进程从阻塞队列中移出。把被阻塞进程从阻塞队列中移出。l将其将其PCB的现行状态改为就绪状态。的现行状态改为就绪状态。l插入就绪队列中。插入就绪队列中。(4)阻塞原语和唤醒原语是一对作用刚好相反的原语。阻塞原语和唤醒原语是一对作用刚好相反的原语。若若在某进程中调用了阻塞原语，则须在另一相关进程调用在某进程中调用了阻塞原语，则须在另一相关进程调用唤醒原语，唤醒原语，否则，被阻塞进程会长久地处于阻塞状态，无否则，被阻塞进程会长久地处于阻塞状态，无机会运行。机会运行。(3)唤醒过程唤醒过程入口入口保存当前进程的CPU现场从等待队列中摘下被唤醒进程置该进程的状态被阻塞进程入等待队列转进程调度将被唤醒进程置为就绪状态将被唤醒进程送入就绪队列转进程调度返回阻塞原语唤醒原语(1)(1)挂起状态的引入挂起状态的引入l用用户户的的需需要要：用用户户在在自自己己的的程程序序运运行行期期间间，发发现现有有问问题题时时，希希望望暂暂时使自己的进程静止下来。把这种静止状态称为时使自己的进程静止下来。把这种静止状态称为挂起状态挂起状态。执行状态执行状态暂停执行；暂停执行；就绪状态就绪状态-暂不接受调度。暂不接受调度。l父进程的需要父进程的需要：考查和修改子进程或协调子进程间的活动时。：考查和修改子进程或协调子进程间的活动时。l交换的需要交换的需要：内存不够，从内存换至外存。：内存不够，从内存换至外存。l负荷调整的需要负荷调整的需要：实时系统工作负荷较重。：实时系统工作负荷较重。4.4.挂起和解挂挂起和解挂(激活激活)(2)进程的挂起过程进程的挂起过程运行态运行态静止就绪静止就绪活动就绪活动就绪静止就绪静止就绪活动阻塞活动阻塞静止阻塞静止阻塞(3)解挂（激活）过程解挂（激活）过程 发生激活进程的事件，系统调用发生激活进程的事件，系统调用激活原语激活原语将指定的进程激活。将指定的进程激活。静止就绪静止就绪活动就绪活动就绪 静止阻塞静止阻塞活动阻塞活动阻塞 若在外存处于静止就绪，则从外存调入内存，活动就绪。若在外存处于静止就绪，则从外存调入内存，活动就绪。2.4 2.4 进程调度进程调度l 用户进程数往往超过处理机数。用户进程数往往超过处理机数。l 操作系统还要建立若干个系统进程操作系统还要建立若干个系统进程。l 进进程程调调度度程程序序完完成成分分配配处处理理机机的的任任务务。将将处处理理机机动动态地分配给系统中的各个就绪进程，使之执行。态地分配给系统中的各个就绪进程，使之执行。l多多级级调调度度：一一个个作作业业从从提提交交到到执执行行，通通常常都都要要经经过过多级调度，如多级调度，如作业调度、进程调度和交换调度作业调度、进程调度和交换调度等。等。l系系统统运运行行性性能能：在在很很大大程程度度上上取取决决于于调调度度。如如吞吞吐吐量大小、周转时间长短、响应及时性。量大小、周转时间长短、响应及时性。1.1.作作业业调调度度：又又称称宏宏观观调调度度或或高高级级调调度度。把把外外存存上上处处于于后后备备队队列列中中的的作作业业调调入入内内存存，并并为为之之创创建建进进程程、分分配配必必要要的的资资源源，然然后后再再将将新新创创建建的的进进程程排排在在就就绪绪队队列列上上，准准备备执执行行。用用于于批批处理系统处理系统。在分时和实时系统，通常无须作业调度。在分时和实时系统，通常无须作业调度。2.2.进进程程调调度度：又又成成微微观观调调度度或或低低级级调调度度。按按照照某某种种策策略略和和方方法法选选取取一一个个处处于于就就绪绪状状态态的的进进程程，将将处处理理机机分分配配给给它它。运运行行频频率很高，一般几十毫秒要运行一次。率很高，一般几十毫秒要运行一次。3.3.交交换换调调度度：又又称称中中级级调调度度。按按照照某某种种策策略略，将将处处于于外外存存交交换换区区中中的的重重又又具具备备运运行行条条件件的的就就绪绪进进程程调调入入内内存存，或或将将处处于于内内存存就就绪绪状状态态或或内内存存阻阻塞塞状状态态的的进进程程交交换换到到外外存存交交换换区区。它它主主要涉及内存管理与扩充。要涉及内存管理与扩充。进程调度进程调度：就是系统按照某种算法把：就是系统按照某种算法把CPUCPU分配给某一就绪进程。分配给某一就绪进程。进程调度程序进程调度程序：完成进程调度工作的程序。：完成进程调度工作的程序。(1)(1)记录系统中各进程的执行状况记录系统中各进程的执行状况 管理管理系统中各进程的系统中各进程的进程控制块进程控制块，将进程的状态变化及资源，将进程的状态变化及资源需求情况及时地记录到需求情况及时地记录到PCBPCB中。中。进进程程调调度度程程序序就就是是通通过过PCBPCB变变化化来来准准确确地地掌掌握握系系统统中中所所有有进进程程的的执执行行情情况况和和状状态态特特征征的的。当当需需要要时时，从从就就绪绪队队列列中中选选出出一一个进程占有个进程占有CPUCPU。1.进程调度的功能进程调度的功能(2)(2)选择进程真正占有选择进程真正占有CPUCPUl按按照照系系统统规规定定的的调调度度策策略略从从就就绪绪队队列列中中选选择择一一个个进程占有进程占有CPU执行。执行。l进程调度依据的算法是与系统的设计目标相一致。进程调度依据的算法是与系统的设计目标相一致。q对对于于批批处处理理系系统统常常采采用用短短作作业业的的进进程程优优先先，以以减少各作业的周转时间。减少各作业的周转时间。q对于分时系统，更多地采用对于分时系统，更多地采用时间片轮转时间片轮转。(3)(3)进行进程上下文的切换进行进程上下文的切换 当进程调度选中一个进程占有当进程调度选中一个进程占有CPU时，进程调度时，进程调度程序要做的主要工作则是进行进程上下文切换：程序要做的主要工作则是进行进程上下文切换：l将正在执行进程的上下文保留在该进程的将正在执行进程的上下文保留在该进程的PCB中，中，以便以后该进程恢复执行。以便以后该进程恢复执行。l将刚选中进程的运行现场恢复起来，并将将刚选中进程的运行现场恢复起来，并将CPU的的控制权交给被选中进程，使其执行。控制权交给被选中进程，使其执行。(1)(1)进程调度方式进程调度方式 非抢先方式非抢先方式(Non preemptive mode)(Non preemptive mode)一一旦旦把把CPUCPU分分配配给给某某一一进进程程后后,便便让让它它一一直直运运行行下下去去，直直到到进进程程完完成成或或发发生生某某事事件件而而不不能能运运行行时时，才将才将CPUCPU分给其它进程。分给其它进程。l该方式通常用在该方式通常用在批处理系统批处理系统中。中。l主要优点是主要优点是简单、系统开销小。简单、系统开销小。2.2.进程调度的方式和调度时机进程调度的方式和调度时机 抢先方式抢先方式(Preemptive mode)(Preemptive mode)允许调度程序基于某种策略（优先级策略、时允许调度程序基于某种策略（优先级策略、时间片策略等）剥夺现行进程的间片策略等）剥夺现行进程的CPUCPU给其它进程。给其它进程。l 该方式通常用在该方式通常用在分时系统分时系统和和实时系统实时系统中，以中，以便及时响应各进程的请求。便及时响应各进程的请求。是指什么情况下引起进程调度程序工作。是指什么情况下引起进程调度程序工作。（1 1）现行进程完成或错误终止；）现行进程完成或错误终止；（2 2）现行进程提出）现行进程提出I/OI/O请求，等待请求，等待I/OI/O完成时，转进程调度；完成时，转进程调度；（3 3）在分时系统，按照时间片轮转，分给进程的时间片用完）在分时系统，按照时间片轮转，分给进程的时间片用完时；时；（4 4）优先级调度时，有更高优先级进程变为就绪时；）优先级调度时，有更高优先级进程变为就绪时；（5 5）在进程通讯中，执行中的进程执行了某种原语操作，如在进程通讯中，执行中的进程执行了某种原语操作，如P操作、阻塞原语和唤醒原语时，都可能引起进程调度。操作、阻塞原语和唤醒原语时，都可能引起进程调度。(2)(2)进程调度的时机进程调度的时机3.3.进程调度算法进程调度算法 所采用的进程调度算法是与整个系统的设计目标所采用的进程调度算法是与整个系统的设计目标相一致的。相一致的。在批处理系统中，系统的设计目标是增加系统在批处理系统中，系统的设计目标是增加系统吞吐量和提高系统资源的利用率吞吐量和提高系统资源的利用率;分时系统则保证每个分时用户能容忍的响应时分时系统则保证每个分时用户能容忍的响应时间。间。因此，进程调度通常采用如下一些算法。因此，进程调度通常采用如下一些算法。(1)(1)优先级优先级调度法调度法当发生进程调度时，将当发生进程调度时，将CPUCPU分配给就绪队列中分配给就绪队列中优先级最高的优先级最高的进程进程。l静态优先级静态优先级：在进程创建时确定的，运行时保持不变。：在进程创建时确定的，运行时保持不变。通通常赋予系统进程较高优先级；申请资源量少的赋予较高优常赋予系统进程较高优先级；申请资源量少的赋予较高优先级。先级。优点是简单。优点是简单。l动动态态优优先先级级：原原优优先先级级可可随随进进程程的的推推进进而而改改变变，以以便便获获得得更好的调度性能。更好的调度性能。通通常常根根据据进进程程占占用用CPU时时间间的的长长短短或或等等待待CPU时时间间的的长长短短动动态态调调整整。（如如，UNIX系系统统进进程程优优先先级级正正是是采采用用这这种种方方法实现的。占用法实现的。占用CPU时间长的优先级低。）时间长的优先级低。）(2)(2)轮转法轮转法(Round Robin)(Round Robin)通常用在通常用在分时系统分时系统，它轮流地调度系统中所有就绪进程。它轮流地调度系统中所有就绪进程。l实现：利用一个定时时钟，使之实现：利用一个定时时钟，使之定时地发出中断定时地发出中断。时钟时钟中断处理程序中断处理程序在设置新的时钟常量后，即转入在设置新的时钟常量后，即转入进程调度进程调度程序程序，选择一个新的进程占用，选择一个新的进程占用CPUCPU。l时间片长短的确定原则：既要保证系统各个用户进程时间片长短的确定原则：既要保证系统各个用户进程及及时时地得到地得到响应响应，又不要由于时间片，又不要由于时间片太短太短而增加调度的开而增加调度的开销，降低系统的效率。销，降低系统的效率。(3)(3)前后台法前后台法 用在用在批处理批处理和和分时分时相结合的系统中。相结合的系统中。l将分时用户作业放在将分时用户作业放在前台前台，把批处理作业放在，把批处理作业放在后台后台。l系系统统对对前前台台作作业业按按照照时时间间片片轮轮转转法法进进行行调调度度，仅仅当当前前台台无无作业时，才把处理机分配给后台作业的进程。作业时，才把处理机分配给后台作业的进程。l后台进程通常按后台进程通常按先来先服务方式先来先服务方式运行。运行。l这这样样既既能能使使分分时时用用户户进进程程得得到到及及时时响响应应，又又提提高高了了系系统统资资源的利用率源的利用率。(4)(4)多级反馈队列轮转法多级反馈队列轮转法就绪进程的种类：就绪进程的种类：刚刚被创建的进程等待进程调度；刚刚被创建的进程等待进程调度；已经被调度执行过，但还没有执行完，等待下一次调度；已经被调度执行过，但还没有执行完，等待下一次调度；正正在在执执行行的的进进程程还还未未用用完完时时间间片片，因因请请求求I/OI/O，等等待待I/OI/O完完成成被被迫迫放放弃弃CPUCPU，当当等等待待原原因因解解除除后后，进进入入就就绪绪队队列列等等待待运行。运行。系系统统通通常常设设置置多多个个就就绪绪队队列列，且且进进程程在在其其生生命命期期内内可可能能在在多多队列中存在。队列中存在。就绪队列就绪队列1就绪队列就绪队列2就绪队列就绪队列3就绪队列就绪队列ns1s2s3sn至至CPU至至CPU至至CPU至至CPU（时间片：（时间片：s1s2s3)l各各个个队队列列赋赋予予不不同同的的优优先先权权，第第一一个个队队列列的的优优先先权权最最高高，其其余队列的优先权逐个降低。余队列的优先权逐个降低。l各个队列中进程执行各个队列中进程执行时间片的大小时间片的大小也不相同。也不相同。l刚刚创创建建的的进进程程和和因因请请求求I/OI/O未未用用完完时时间间片片的的进进程程排排在在最最高高优优先先级级队队列列，在在这这个个队队列列中中运运行行2323个个时时间间片片未未完完成成的的进进程程排排到下一个到下一个较低优先级队列较低优先级队列。l调调度度时时，总总是是先先调调度度优优先先级级高高的的队队列列。仅仅当当该该队队列列空空时时，才才调调度度次次高高优优先先级级队队列列，以以此此类类推推，第第n n个个队队列列进进程程被被调调度度时时，必须是前必须是前n-1n-1个队列为空。个队列为空。l既既能能使使分分时时用用户户作作业业得得到到满满意意的的响响应应时时间间，又又能能使使批批处处理理用用户的作业户的作业获得较合理的周转时间。获得较合理的周转时间。(5)(5)时钟驱动法：时钟驱动法：系统使用一个硬件定时器，这系统使用一个硬件定时器，这个定时器被周期性地进行设置，时间到期后，系统个定时器被周期性地进行设置，时间到期后，系统启动要执行的任务。（用在实时系统中）启动要执行的任务。（用在实时系统中）(6)(6)加权轮转法加权轮转法：每次轮转时，各个进程获得处理每次轮转时，各个进程获得处理机的时间就是它具有的权值长度。（用在高速开关机的时间就是它具有的权值长度。（用在高速开关网的实时控制中）网的实时控制中）(1)(1)线程的概念线程的概念引引入入进进程程的的目目的的：为为了了使使多多个个程程序序并并发发执执行行，以以改改善善资资源源利利用率用率及提高系统及提高系统吞吐量吞吐量。l进进程程的的两两个个基基本本属属性性：进进程程是是一一个个可可拥拥有有资资源源的的独独立立单单位位；进程同时又是一个进程同时又是一个可以独立调度和分派可以独立调度和分派的基本单位。的基本单位。l进进程程数数目目不不宜宜过过多多，进进程程切切换换的的频频率率也也不不宜宜过过高高。进进程程是是一一个个资资源源拥拥有有者者，因因而而在在进进程程的的创创建建、撤撤消消和和切切换换中中，系系统统必必须须为为了了付付出出较较大大的的时时空空开开销销。因因而而限限制制了了并并发发程程度度的的进一步提高。进一步提高。2.5 线程的引入（线程的引入（thread)l线线程程的的引引入入，则则是是减减少少程程序序并并发发执执行行时时系系统统付付出出的的时时空空开开销销，使使操操作作系系统统更更加加有有效效。试试图图提提高高系系统统内内程程序序并并发发执执行行程程度度和和提提高高系系统统吞吞吐量吐量l线程是线程是8080年代引入的。年代引入的。lMS-DOSMS-DOS是是一一种种支支持持单单用用户户进进程程和和单单线线程程的的OSOS；UNIXUNIX支支持持多多用用户户进进程程，但但只只支支持持每每个个进进程程一一个个线线程程；支支持持多多线线程程的的多多进进程程