操作系统原理课件.ppt

1,第三章 进程管理,3.1 进程概述 3.2 进程控制块 3.3 调度 3.4 UNIX系统的进程调度 3.5 进程控制 3.6 进程的创建和图像改换 3.7 线程 3.8 Linux进程管理,2,3.1 进程概述,程序的执行有两种方式：顺序执行和并发执行。顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统；现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率。,3,程序：是一个在时间上严格有序的指令集合。程序规定了完成某一任务时，计算机所需做的各种操作，以及这些操作的执行时间。程序的顺序执行：具有独立功能的程序独占CPU直至得到最终结果的过程。,程序,4,程序顺序执行时的特征,（1）顺序性：（执行的顺序性）由于内存中每次只有一道程序，因此各个程序是按次序执行的，即执行完一个以后，再执行下一个。（2）封闭性：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定（3）可再现性：结果的再现性，初始条件相同则结果相同。,5,程序的并发执行及其特征,1.程序的并发执行,6,程序并发执行时的特征,间断(异步)性：执行的顺序性被打破，“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系；失去封闭性：资源的独占性被打破，共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。失去可再现性：失去封闭性 失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。,7,不加控制的并发执行所带来的影响,例：为了了解某单行道的交通流量，在路口安放一个监视器，功能是有车通过该路段时，就向计算机发送一个信号。程序A功能：接收到监视器信号时，就在计数单元COUNT上加1；程序B功能：每个半个小时，打印COUNT的值，然后清零。,程序A：While(1)A1:收到监视器信号；A2:COUNT=COUNT+1;,程序B：While(1)B1:延迟半小时；B2:打印COUNT的值;B3:COUNT=0;,A1A2B1B2A1A2B3,8,3.1.1 进程的概念,程序本身完全是个静态的概念（程序是完成某个功能的指令的集合），而系统及其中的各个程序实际上是处于不断变化的状态，程序的概念反映不了这种动态性；其次，程序概念也反映不了系统中的并行特性。综上所述，静态的程序概念已不敷使用，需要引用一个新的概念“进程”。,9,进程的概念,进程是程序处于一个执行环境中在一个数据集上的运行过程，它是系统进行资源分配和调度的一个可并发执行的独立单位。,10,进程的特征,（1）动态性 进程的实质是程序的一次执行过程，因此，动态性是进程的最基本特征。动态性还表现为：“它由创建而产生，由调度而执行，由撤消而消亡”。可见，进程有一定的生命期，而程序只是一组有序指令的集合，并存放于某种介质上，本身并无运动的含义，因此是静态的。（2）并发性 这是指多个进程能在一段时间内同时运行，并发性是进程的重要特征。引入进程的目的也正是为了使其程序能和其他进程的程序并发执行，而程序（没有建立进程）是不能并发执行的（由于程序不反映执行过程）。,11,进程的特征,（3）独立性 这是指进程是一个能独立运行、独立分配资源和独立调度的基本单位，凡未建立进程的程序，都不能作为一个独立的单位参加运行。只有进程有资格向系统提出申请资源并获得系统提供的服务。（4）异步性 这是指进程按各自独立的、不可预知的速度向前推进，或说进程按异步方式运行。（5）结构性 为使进程能独立运行，应为之配置一个称为“进程控制块”的数据结构，简称PCB。,12,进程和程序的联系与区别：,（1）联系。程序是构成进程的组成部分之一，一个进程的运行目标是执行它所对应的程序，如果没有程序，进程就失去了其实际存在的意义。,13,进程和程序的联系与区别：,（2）区别。进程是程序的一次动态执行活动，而程序是进程运行的静态描述文本。一个进程可以执行一个或多个程序，反之，同一程序也可被多个进程同时执行。程序是一种软件资源，它可以长期保存，而进程是一次执行过程，它是暂时存在的、动态地产生和中止的。,14,特权指令、管态、目态,特权指令：只能由操作系统使用的指令。非特权指令：大家（用户和操作系统）都能使用的指令。用户执行状态，又称用户态，目态（目标程序态），进程的用户程序段执行时，该程序处于用户态。用户态时不可直接访问受保护的OS代码；系统执行状态，又称系统态，核心态，管态（管理程序态），进程的系统程序执行时，该进程处于系统态。核心态时可以执行OS代码，可以访问全部进程空间。,15,3.1.2 进程的组成,进程是在一个上下文的执行环境中执行的，这个执行环境称为进程的映像，或称图像。它包括处理机中各通用寄存器的值、进程的内存映像、打开文件的状态和进程占用资源的信息等很多部分。进程映像的关键部分是存储器映像。进程存储器映像由以下几部分组成：进程控制块、进程执行的程序（code）、进程执行时所用的数据、进程执行时使用的工作区,16,进程的组成,17,1.进程控制块,进程控制块PCB（ProcessControlBlock）是系统用于查询和控制进程运行的档案，它描述进程的特征，记载进程的历史，决定进程的命运。由于PCB较大，一些系统将其分割成两部分：一部分是进程基本控制块，这部分记录不管进程是否在执行，操作系统都需要访问的进程控制信息，因此，进程基本控制块要常驻内存；另一部分是进程扩充控制块，当进程不处于执行状态时，操作系统就不会访问这部分信息，扩充控制块能对换到盘交换区中。,18,2.共享正文段,用高级语言编写的程序一般是可重入的“纯代码”，也即是它可以被多个进程并发地执行的。共享正文段不限于包括程序，还可包括不可修改的常数。用户用C语言所编的程序经编译后产生的代码也是作为共享正文段装入内存的,19,3.数据区,进程执行时用到的数据，如C程序中的外部变量和静态变量；如进程执行的程序为非共享程序（如用汇编语言编写，可以在执行时修改执行的代码和其中夹带的数据），则也可构成数据区的一部分。,20,4.工作区,进程在核心态运行时的工作区为核心栈；在用户态下运行时的工作区为用户栈；在调用核心的函数或用户函数时，两种栈分别用于传递参数、存放返回地址、保护现场以及为局部动态变量提供存储空间。此外，核心栈还可用于保护中断现场，用户栈还用于向主程序（main函数）传递命令行参数等。,21,3.1.3 进程的状态及其变化,进程具有生存期，它有一个创建、活动及消亡的过程。进程在其活动期间可以因外部和内部的原因进入“睡眠”阶段。“睡眠”的进程会被“唤醒”而继续先前的活动。为了完成一组特定的任务，进程也可采用“克隆”技术，生成一个或多个子进程，互相配合地工作。进程在其整个生存期间可处于不同的状态，有一些不同的特征,22,就绪(Ready)状态：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行)。“万事俱备，只欠东风”。位于“就绪队列”中。2)执行状态(Running)：进程占有了包括CPU在内的全部资源，并在CPU上运行。3)阻塞状态(Blocked)：也称等待态、睡眠态、封锁态、挂起态等。指进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）。处于阻塞态的进程位于阻塞队列中。,23,运行Running,就绪Ready,阻塞Blocked,Dispatch,Timeout,Event,Wait,Event,Occurs,基本状态间的转换,24,在实际的操作系统中，为了管理和调度的便利，还将进程的状态进一步细分，例如，UNIX系统V定义了10种进程的状态：#define SSLEEP 1 睡眠状态#define SWAIT 2 等待状态，该状态已被废弃#define SRUN 3 执行状态或就绪状态#define SIDL 4 创建子进程状态#define SZOMB 5 等待善后处理状态#define SSTOP 6 进程处于被跟踪的暂停状态#define SXBRK 7 因数据段扩展时未满足的换出状态#define SXSTK 8 因栈段扩展时未满足的换出状态#define SXFRK 9 创建子进程时内存不够，父进程锁定在内存的状态#define SXTXT 10 因正文段扩展未满足而被换出的状态,25,3.2 进程控制块,为了掌握进程的运行状况和便于管理和控制进程的运行，操作系统为每一个进程设置了一个数据结构进程控制块（PCB）。进程控制块是进程的控制结构，包含了进程的描述信息、控制信息和资源信息以及现场保护区。,26,1.进程控制块的作用,进程控制块是由OS维护的用来记录进程相关信息和管理进程设置的一个专门的数据结构。进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。PCB是进程动态特性的集中反映。系统通过PCB感知进程的存在，通过PCB中所包含的各项变量的变化，掌握进程的状态以达到控制进程活动的目的；,27,PCB随进程的创建而填写，随进程的撤消而释放；系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的PCB结构常驻内存；系统将所有PCB组织成若干个队列，存放在操作系统中专门开辟的PCB区内。,28,2.进程控制块中的信息,1)进程标识符 进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：(1)内部标识符。在所有的操作系统中，都为每一个进 程赋予一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。(2)外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。,29,2)处理机状态 处理机状态信息主要是由处理机的各种寄存器中的内容组成的。通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有 832 个通用寄存器，在RISC结构的计算机中可超过 100 个；指令计数器，其中存放了要访问的下一条指令的地址；程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。,30,3)进程调度信息 在PCB中还存放一些与进程调度和进程对换有关的信息，包括：进程状态，指明进程的当前状态，作为进程调度和对换时的依据；进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。,31,4)进程控制信息 程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。,32,PCB的存放,有些系统将进程控制块分成两个部分：一部分是进程无论处于什么状态，系统都可能要查询和处理的 PCB 成员，这部分就要常驻内存；另一部分是进程不在执行时系统就不需要访问的 PCB成员，在内存紧张时可以将它们换到盘交换区，以为其他进程腾出宝贵的内存空间。在UNIX中，常驻内存的进程PCB部分是proc结构；在UNIX中，非常驻内存的 PCB 部分是进程扩充控制块 user 结构；,33,3.进程控制块的组织方式,早期的UNIX系统将进程的proc结构组成一个顺序存放的线性表，系统中可以存在的最大进程数受表的大小的限制（如50个）。当要对处于某种状态的进程控制或调度时，就要扫描整个proc表，这大大地降低了系统的效率。系统 V 用链式方式组织 PCB 队列，不同状态的进程链接成就绪队列、阻塞队列等不同的队列。为了便于系统的调度和控制，对于就绪状态进程，还可以将其分成优先级不同的几个就绪队列。对于阻塞进程，可根据原因不同，组成若干个队列。,34,35,3.3 调度,3.3.1 调度概述,1.高级调度(High Scheduling),又称为作业调度或长程调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。因此有时也把作业调度称为接纳调度。在每次执行作业调度时，都须做出以下两个决定。1)接纳多少个作业，取决于多道程序度。2)接纳哪些作业，取决于调度算法,36,2.中级调度(Intermediate-Level Scheduling),又称中程调度，它决定处于交换区中的就绪进程中哪一个可以调入内存，以便直接参与对CPU的竞争。在内存资源紧张时，为了将进程调入内存，必须将内存中处于阻塞状态的进程调至交换区，以便为调入进程腾出空间。这相当于使处于内存中的进程和处于盘交换区中的进程交换了位置，故中级调度又称为“对换调度”。中级调度是为了缓解内存资源的紧张状态，在多道程序范畴内实现进程动态覆盖和进程级的虚拟存储器技术。一个进程在其运行期间可能需要经过多次中级调度。,37,3.低级调度(Low Level Scheduling)（进程调度或短程调度）,它决定驻在内存中的哪一个就绪进程可以占用CPU，使其获得实实在在的执行权力，故低级调度又可称处理机调度或分派调度。低级调度执行频度很高，调度算法也比较复杂，是操作系统中最活跃、最重要的调度程序，对系统的性能影响也最大。,38,39,3.3.2 进程调度策略,进程调度策略是指在什么情况下用什么方式，在内存中的就绪进程之间进行切换和分配处理机。进程切换的方式有两种：一种是不可剥夺（或不可抢占）方式，即一个进程在获得处理机后，除非因运行结束或进入了阻塞状态等原因自己放弃处理机，否则就可以一直运行下去，不会被其他进程抢占处理机；另一种是可剥夺方式，即在某些条件下系统可以强制剥夺正在运行中进程使用处理机的权利，将其分配给系统中另一个合适的就绪进程,40,在设计一个调度算法时，应考虑以下的因素。针对不同的系统应当考虑不同的设计目标。如对于批处理系统应当以提高计算机系统的运行效率、取得最大的作业吞吐量和减少作业平均周转时间为主要目标；对于交互式分时系统，应当以能及时响应用户的请求为主要目标；对于实时系统，应当能对紧急事件做出及时处理和安全可靠为头等重要的考虑因素。调度算法应能充分使用系统中各种类型的资源，使多个设备能并行地工作,41,应当既能在某一原则下公平地对待系统中的各个进程，使它们能均衡地使用处理机，也能考虑不同类型进程具有不同的优先权利，在一定程度下满足用户对优先级的要求，但也不能造成某些低优先权的进程可能无限期地推迟任务完成的时间。合理的系统开销,42,3.3.3 进程调度算法,在OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法。目前存在的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但也有些调度算法既可用于作业调度，也可用于进程调度。,43,1.先来先服务调度算法（FCFS-First Come First Serve）,按照作业进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业。优点：实现简单、公平缺点：没考虑资源利用率和作业的特殊性，对短作业不公平。,44,先来先服务调度算法,带权周转时间周转时间/请求服务时间,45,短作业(进程)优先调度算法,短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。,46,47,SJ(P)F调度算法也存在不容忽视的缺点：(1)该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。(2)该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。(3)由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。,48,2.时间片轮转法 在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。,49,时间片轮转法比较适合于交互式的分时系统，对于用户输入的每一条命令，系统能保证在一个不太长的时间内对此做出响应。时间片轮转法是剥夺式调度算法，因此系统需要花费额外开销用于各个就绪进程间的切换。系统的效率与时间片大小的设置有关。如时间片设置过大，系统与用户间的交互性就差，会招致用户的埋怨；如时间片设置太小，进程间切换过分频繁，系统开销就增大。,50,为了适应不同进程的运行特点，在系统中可设置时间片大小不同的n个队列，如时间片长度可分为10ms、50ms和200ms等。调度程序可将运行时间短、交互性强或I/O繁忙的进程安排在时间片小的队列，这样可以提高系统的响应速度和减少周转时间而对于需要连续占用处理机的进程可安排在时间片长的队列中，这样可减少进程切换的开销。一个进程处于哪一个时间片的队列，可以在运行时根据它的先前运行状况加以调整。,51,3.优先级调度算法,为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权（FPF）调度算法。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业，装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程。,52,对于优先权调度算法，其关键在于：它是使用静态优先权、还是动态优先权，以及如何确定进程的优先权。1)静态优先权 静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，07或0255中的某一整数，又把该整数称为优先数。只是具体用法各异：有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相反。,53,确定进程优先权的依据有如下几个方面：系统进程执行和完成的是系统功能，应当赋予它们比用户进程高的优先级。短作业的进程可以赋予较高的优先级，这样可减少作业的平均等待时间，提高系统的吞吐量。I/O繁忙的进程只要求较短的处理机时间，让该类进程优先获得CPU。根据用户作业的申请，系统可以分配一些进程较高的优先级，一般这意味着要提高收费标准。静态优先权法也很适合于实时系统，因为在实时系统中计算机所处理的所有事件是预知的，故其优先级可根据事件的紧迫程度事先设定,54,2)动态优先权 动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。,55,4.多级反馈队列调度算法,多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。优点：为提高系统吞吐量和缩短平均周转时间而照顾短进程为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程不必估计进程的执行时间，动态调节,56,4.多级反馈队列调度算法,(1)应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列的时间片长一倍。,57,58,(2)当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。,59,(3)仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。,60,特点短进程优先处理。因此运行时间短的进程在经过前面几个队列之后便已经执行完，而这些队列中的进程被优先调度。设备资源利用率高。因为与设备打交道的进程可能经常会由于下面原因而进入等待状态：所申请的资源被占用，启动了I/O传输。当等待事件发生时，它将进入第一级就绪队列，尽快获得处理机并使用资源。系统开销小.因为运行时间长的进程最后进入低优先级的队列，这些队列的时间片较长，因而进程的调度频率较低。但是，如果高优先级的队列一直不为空，则低优先级队列的进程可能长时间得不到运行机会，可能会发生“饿死”现象。因此，允许采用某种原则将低优先级队列的进程移到高优先级队列中,61,3.4 UNIX系统的进程调度,3.4.1 进程的切换调度算法1.UNIX的切换调度策略 UNIX 系统的切换调度采用动态优先权算法，其主要工作是在一个适当的时机，选择一个优先权最高，也即优先数p_pri最小的就绪进程，使其占用处理机。,62,UNIX 系统中的每一个进程在其运行期间可以处于两种状态，即用户态和核心态。系统对在用户态下运行的进程，可以根据优先数的大小，对它们进行切换调度。对在核心态下运行的进程，除非它们完成了所要执行的操作系统功能，即将返回用户态下运行，或它们因为某些原因（如申请资源得不到满足）而进入睡眠状态，或为了同步的需要而自愿暂停执行，否则是不会对它们进行切换调度的，也即UNIX核心从本质上来说，是不可重入的,63,2.优先数的计算,与运行状态相对应，UNIX 对进程优先数的处理也有两种方法。对用户态的进程，内核程序在适当时机用下列公式计算进程的优先数：p_pri=p_cpu/2+p_nice+PUSER+NZEROp_cpu 是进程占用处理机的量度，内核程序在每次时钟中断（每秒 50 次或 100 次）中，使当前执行进程的p_cpu加1，但最多加到80；每一秒钟使所有就绪状态的进程的p_cpu衰减一半，即p_cpu=p_cpu/2。,64,p_nice 是用户可以通过系统调用 nice（int priority）设置的进程优先数偏置值。用户可设置的偏置值范围为020（有的系统为039），只有超级用户能将p_nice置成负值，以提高进程的优先权。PUSER 和 NZERO 是两个常量，用于分界不同类型的优先数,65,3.优先数的设置,正在核心态运行的进程，其优先数对调度是不起作用的，因为它不会被强迫剥夺占用处理机的权利。只有当它因等待系统资源等原因进入睡眠状态时，系统才根据等待事件的轻重缓急程度分配给其一个相应的优先数。只有当它被唤醒之后，才以设置的优先数参与竞争处理机，并在核心态下继续运行下去。,66,核心态进程根据被设置优先数的大小，可分为可中断和不可中断两类优先级。若进程在可中断的优先级上睡眠，当一个软中断信号（软中断的概念将在下一章叙述）到达时，它就被唤醒，进入就绪队列，以便执行软中断处理程序。若进程在不可中断的优先级上睡眠，它在收到软中断信号后，继续睡眠，以保证它能优先处理所等待的事件,67,68,4.进程切换调度的时机,进程自愿放弃处理机而引起的切换调度，属于这一类的主要有以下几种情况：进程完成了预定任务而进入了SZOMB（等待善后处理）状态；进程因等待某种资源进入了睡眠状态；进程因同步或互斥的需要，暂停执行，放弃了处理机,69,系统发现了可能更适合占用处理机的进程，设置了强迫调度标志runrun。属于该类的主要情况有：在唤醒睡眠进程时，发现该进程的优先数小于现运行进程；进程由系统调用返回用户态时，重新计算自己的优先数，发现自己的优先数上升了，要选择可能更合适的进程运行；在时钟中断程序中每一秒对所有优先数大于（PUSER-NZERO）的进程（一般原先在用户态下运行）重新计算优先数，通常总要设置runrun标志。在runrun标志设置后，进行强迫调度的具体时机是在中断或陷入处理末尾。,70,3.4.2 切换调度程序,实施进程切换调度的程序是swtch，其主要任务是：保存现运行进程的现场信息；在就绪队列中选择一个在内存且优先数 p_pri 最小的进程，以使其占用处理机，如找不到这样的进程，计算机就空转等待；为新选中的进程恢复现场,71,3.4.3 进程的对换调度,为了使更多的进程能进入系统，以使切换调度程序能选择更合适的进程占用处理机，以充分利用系统中的各种资源，UNIX 在磁盘开辟一块空间进程图像的交换区，作为内存的逻辑扩充。UNIX 系统中的 0号进程的主要任务就是按照换入换出算法在内存和磁盘交换区之间传输进程的图像。,72,习题,1.若是在单批道处理系统中，已知进入时间和所需计算的时间。忽略作业调度所花的时间。当第一个作业进入系统后就开始调度。作业 进入时间 所需计算时间1 8：00 2小时2 8：30 30分钟3 9：00 六分钟4 9：3012分钟（1）将分别采用先来先服务和短作业优先的调度算法时，各个作业的开始时间，完成时间，周转时间分别计算。（2）分别求出在这两种算法之下的平均周转时间。,73,解答：（1）先来先服务调度算法：由于当第一个作业进入系统后就开始调度，所以作业1到达后，因为作业队列中没有其它作业，所有立刻得到调度了。,平均周转时间（1201209678）/4103.5分钟,74,短作业优先调度算法：,平均周转时间（1201386648）/493分钟,75,3.5 进程的控制,一个进程可能由于某种原因进入挂起、阻塞或睡眠状态。常见的原因有以下几种。请求系统服务或请求分配资源时得不到满足，进程暂时不能继续执行下去。同步等待I/O的完成。进程间互相配合共同完成一个任务时。在利用消息实现进程间控制时，一进程在等待某一进程发消息时，也进入了阻塞状态。进程将自己挂起或进程将自己某个子进程挂起。,3.5.1 进程的挂起,76,3.进程的唤醒,当引起进程阻塞的原因消除后，核心就可将阻塞进程唤醒。唤醒的方法是根据睡眠原因先算出对应的阻塞队列。由于不同的原因可能挂在同一个队列中，因此在唤醒因某一原因进入睡眠的进程时，在对应的hash队列中还要核查睡眠原因。但由于采用了数量众多的hash队列，每个队列的长度一般都非常短，故大大减少了搜索的时间。,77,由于可能有多个进程因同一原因而阻塞，一般的算法是核心将这些进程全部唤醒。唤醒一个进程并不意味着该进程马上可以占用处理机，而是仅将它排到就绪队列中，使其有被调度的资格。因此，由于同一原因而唤醒的进程将先竞争处理机，从而才可获得有关的资源。如其中有一个获得等待的资源后，其他竞争相同资源的进程一旦获得处理机，还得再转入阻塞状态。,78,3.6 进程的创建和图像改换,3.6.1 进程的创建1.进程创建的目的 在批处理系统中，当部分作业已经运行完毕，退出了系统，操作系统准备运行下一个批作业时，它要创建一个进程，读入作业控制命令，以输入作业和控制作业的运行。分时系统中的用户在终端上登录时，操作系统需要创建一个进程，为用户建立交互命令的环境，接收、分析并执行用户输入的命令。,79,在执行批处理命令时，系统要产生一个进程分析并处理批命令，对于批处理文件中的每一条命令，也要创造一个子进程来执行该命令。当用户程序需要获得系统服务时，操作系统要创建一个新进程，代表用户程序的利益，完成一种系统的功能。用户程序为了并发执行的需要，可以在运行时创建一系列的进程，各实现一个功能，并互相合作，完成总任务。,80,2.创建进程的主要步骤,为新进程分配惟一的进程标识数。接着为新进程分配进程控制块的空间，在进程表中加入新项。为新进程分配进程各部分映像所需的内存空间，因此操作系统必须知道新进程的程序、数据和用户栈的大小。系统也能根据进程的类型为之分配默认的值，或在作业递交时根据用户的要求来分配。如果一个进程由另一进程产生，父进程会将创建子进程所需的存储要求传送给操作系统。如新进程共享已存在内存空间，就建立适当的链接信息。,81,初始化进程控制块，如进程标识数、父进程标识数、程序计数器、系统栈指针、进程的状态等，根据进程的性质或默认值初始化进程的控制信息。进程的运行状态一般初始化为就绪状态或就绪挂起。除非进程显式申请较高的优先级，否则优先级设置为较低的级别。子进程复制父进程扩充控制块。这意味着子进程将共享父进程的全部打开文件、信号处理方式等。子进程复制了父进程的数据区、核心栈和用户栈，这意味着父子进程程序执行的当前位置、状态、数据区、变量的当前值都是相同的。但随着父、子进程的各自独立执行，子进程的映像将会与父进程有明显的差异。,82,如何使父子进程完成不同的任务？,由上可知，当一个子进程刚创建完成，它与父进程共享执行代码，且起始执行位置相同，数据区与栈段也相同。UNIX 采用了在调用创建子进程的系统调用后，使父子进程具有不同的返回值，这样就可以采用判断语句，使父子进程可以执行不同的程序段，以便完成不同的任务。在执行系统调用fork后，父进程得到的返回值是所创建子进程的标识数，而子进程的返回值为0。,83,main()int pid;printf(Before forkn);while(pid=fork()=-1);if(pid)printf(It is parent process:PID=%dn,getpid();printf Produced childs PID=%dn,pid);elseprintf(It is child process:PID=%dn,getpid();printf(It is parent or child process:PID=%dn,getpid();,84,3.7 线 程,本节讨论一些与进程管理有关的新概念，这些概念出现在一些现代的操作系统中。如更深入地思考一下，可以发现进程实际上包括了两种不同的独立概念：一是与资源的所有权有关，二是与执行有关。这种区别已经导致了操作系统结构的发展，出现了线程这种形式的结构单元。,85,3.7.1 进程和线程,在进程的概述一节中谈到进程包含了下列两个特征。资源拥有单位：进程的虚址空间用于驻留进程的图像，进程可以分配到主存和控制其他的系统资源，如I/O通道、I/O设备和文件等。调度单位：进程是可以并发执行的独立单元，它具有各种状态和调度优先级，是操作系统进行调度的一个实体。,86,换言之，由于进程是一个资源的拥有者，因而在创建、撤销和切换中，系统必须为之付出较大的时空开销。正因如此，在系统中所设置的进程，其数目不宜过多，进程切换的频率也不宜过高，这也就限制了并发程度的进一步提高。若能将进程的上述两个属性分开，由操作系统分开处理，亦即对于作为调度和分派的基本单位，不同时作为拥有资源的单位，以做到“轻装上阵”；而对于拥有资源的基本单位，又不对之进行频繁的切换。正是在这种思想的指导下，形成了线程概念。,87,3.7.2 多线程,多线程指的是操作系统支持在单个进程中执行多个线程的能力。,88,在多线程环境中，进程被定义为保护单位和资源分配单位。在一个进程内部可以有一至多个线程，每一个线程具有如下特征：线程的执行状态（运行、就绪等）；当不处于执行状态时保存的线程上下文环境，可以把线程看成是进程内一个独立的程序计数器的运转；一个执行栈；存取所属进程内的主存和其他资源，在本进程的范围内与所有线程共享这些资源,线程描述,89,90,采用线程机制的优点,（1）首先用于创建和撤销线程的开销比创建和撤销进程的系统开销（CPU时间）要少的多。（2）CPU在线程之间切换的开销也远比进程之间切换的开销小。因为切换的线程都在同一地址空间内，只需修改线程控制表或队列，不涉及地址空间和其它工作。（3）线程机制也增加了通讯的有效性。如果是在进程之间通信，往往要求内核的参与，以提供通讯机制和保护机制。而线程间通信是在同一进程的地址空间内，共享主存和文件，所以非常简单，无需内核参与。（4）方便和简化了用户的程序结构工作。,91,注意：,调度和分派是基于线程的，因此涉及到执行的大多数状态信息是以线程级数据结构维护的。可是，对于一些影响一个进程中所有线程的动作，操作系统必须在进程级管理。例如，挂起涉及到换出主存空间，由于进程中所有的线程共享相同的地址空间，所有的线程必须同时进入挂起状态。同样，进程的终止也终止了该进程中的所有线程。,92,某系统的进程状态变迁图如图所示（设该系统采用剥夺调度方式），请说明：1）一个进程发生1、2、3、4、5变迁的原因是什么？2）下述因果变迁是否会发生，如果有可能发生在什么情况下发生？A）2导致1 B）3导致2 C）4导致5 D）4导致2 E）3导致5,习题,93,习题,2、(1)在什么条件下，一个进程的解封(BlockedReady)会立即引起一个进程的被调度(ReadyRunning)？(2)有人曾描述过这样一种情形：在单处理机分时系统下，分配给进程A的时间片到达后，系统进行且化，结果调度到的进程仍然是A。有可能出现这种情形吗？说明理由。,94,3.有4个进程P1，P2，P3，P4，它们进入就绪队列的先后次序为P1，P2，P3，P4，它们的优先级和需要的处理机时间如表所示。假定这四个进程执行过程中不会发生等待事件，忽略进程调度等所花费的时间，从某个时刻开始进程调度，请写出分别采用“先来先服务”、“非抢占式优先级”（固定优先级），“时间片轮转”（时间片大小为5）调度算法中进程的执行次序。计算各个进程在就绪队列中的等待时间以及平均等待时间。,95,1）先来先服务算法进程的执行顺序P1、P2、P3、P4；进程P1等待时间为0；进程P2等待时间为8；进程P3等待时间为8614；进程P4等待时间为862236；平均等待时间为（0+8+14+36）/414.52）优先级算法进程的执行顺序P3、P4、P1、P2；进程P1等待时间为4+2226；进程P2等待时间为22+4+834；进程P3等待时间为0；进程P4等待时间为22；平均等待时间为（26+34+0+22）/420.5,96,3）时间片轮转算法进程的执行顺序P1、P2、