操作系统2002进程管理

1、 多道程序设计 进程的概念 进程的描述 进程的控制 进程的调度 线程的基本概念一、多道程序设计什么是多道程序设计？ 让多个计算问题同时装入计算机系统的主存储器并发执行，这种设计技术称为“多道程序设计”，这种计算机系统称为“多道程序设计系统”或“多道系统”并发活动 “多道程序设计”导致多个相互独立的程序同时在系统中运行，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等符。 要解决这些问题，用程序的概念已经不能描述程序在系统中运行的状态，必须引人新的概念进程。为什么要采用多道程序设计？程序的顺序执行一个程序由

2、若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。例如： 输入一批数据处理数据打印处理结果时间输入机处理器打印机t1 t2 t3 t4 t5 t6程序顺序执行的特点1.1.顺序性顺序性 处理机的操作，严格按照程序所规定的顺序执行。每个操作必须在下一个操作开始之前结束，即只有前一操作结束后，才能执行后继操作。 2.2.封闭性封闭性 程序一旦开始执行，就独占全机资源，其计算结果不受外界的影响。当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。3.3.可再现性可再现性 程序执行的结果与初始条件有关，而与执行时间无关。只要程序的初始

3、条件相同，它的执行结果是相同的，即只要程序执行时的环境和初始条件相同，当程序多次重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行。都将获得相同的结果。例： 在系统中有n个作业，每个作业都有三个处理步骤 ， 输 入 数 据 、 处 理 、 输 出 ， 即 Ii, Ci, Pi (i=1,2,3,.,n)。程序并发执行 这些作业在系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。例如: I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2,I3与P1是可以同时执行的。 若干个程序段同时在系统中运行，这些

4、程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。 P Q R 并发执行区 时间时间输入机输入机处理器处理器打印机打印机磁带机磁带机t1 t2 t3 t4 t5 t6J1J2J1J2J1J1J2J1J1J2J2采用多道程序设计应注意的问题 可能延长程序执行时间 并行工作道数与系统效率不成比例 程序的并发执行与顺序执行的比较一、失去了程序的封闭性一、失去了程序的封闭性 若一个程序的执行可改变另一个程序的变量，则程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度，在这种情况下就失去了程序的封闭性。

5、二、程序与计算不再一一对应二、程序与计算不再一一对应 在程序顺序执行时，一个程序总是对应一个具体的计算，但在程序的并发执行时，可能有多用户共享使用同一个程序，但处理（计算）的对象却是不同的，例如，在多用户环境下，可能同时有多个用户调用C语言的编译程序，这就是典型的一个程序对应多个用户源程序的情况。三、程序并发执行的相互制约三、程序并发执行的相互制约 在多道程序设计的环境下，程序是并发执行的。即系统中有多道程序在“同时”执行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的，也有间接的。程序并发执行时的特征： 间断性

6、程序在并发执行时，由于它们共享资源或为完成同一项任务而租互合作，致使在井发程序之间形成了相互制约的关系。例如：如果I、C、P是三个相互合作的程序。当计算程序C完成了上一批数据的计算后，如果输入程序I尚未完成下一批数据的输入，则计算程序就无法进一步进行处理，致使计算程序暂停运行。一旦使计算程序暂停的因素消失后（如输入程序已完成了下一批数据的输入后），计算程序便可恢复执行。这样的相互制约将导致井发程序具有“执行一暂停执行一执行”这种间断性的活动规律。 失去封闭性 程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。这样，某程序在执行时

7、，必然受到其他程序的影响。 不可再现性 程序再并发执行时，由于失去的并发性，也将导致失去可再现性。 例如：下述两个循环程序A和B，它们共享一个变量n。程序A每循环一次都要对n做如下n := n + 1 操作：程序B每循环一次打印n 的值，再将n置0。具体的程序为：程序ABegin Repeat n := N + 1; Until false End程序BBegin Repeat print (n) ; n := 0 ; Until false End 假定某一时刻，n 的值为N。程序 A 的 n:= N + 1 和程序B的 print（n）和 n := 0 如果有下述关系： .之前，则打印的结

8、果为N+1； .之后，则打印的结果为N； .中间，则打印的结果为N； 在多道进程设计的系统中，对多道并行执行的程序来说，一个程序的执行还可能受到另一个程序的约束，所以，程序的执行实际上是走走停停的。为了能正确地反映程序的活动规律和状态变化（程序的执行情况），要引进一个新的概念-进程，以便从变化的角度动态地研究程序的执行。二、进程的概念 进程的概念是操作系统中最基本、最重要的概念。它是在多道程序系统出现后，为了刻划系统内部出现的情况，描述系统内部各作业的活动规律而引进的一个新的概念。 进程（PROCESS）这个名词最早是六十年代初期，在麻省理工学院的MULTICS系统和IBM公司CTSS/360

9、操作系统中引入的。直至目前关于进程的定义及其名称均不统一。在少数系统中把进程称为任务（TASK）。 对进程的定义有如下几种：（1）进程是程序的一次执行；（2）进程是程序在一个数据集合上的运行过程，是 系统进行资源分配和调度的一个独立单位；（3）进程可定义为一个数据结构及其能在其上进行 操作的一个程序；（4）进程是一个程序及其数据在处理机上顺序执行 时所发生的活动；（5）进程是可以与别的计算并发执行的计算。进程具有的五大特征：（1）动态性动态性 进程的实质是程序的一次执行过程。因此， 动态特性是进程最重要的特征。（2）并发性并发性 没有为之建立进程的程序是不能并发执行的 ，仅当为之建立一个进程后

10、，才能参加并发执行。（3）独立性独立性 进程不是随便一个拿来的程序，它是一个能 独立运行的程序的化身。它同其它的这样的独立单位 去竞争系统资源和处理机。（4）异步性异步性 由于进程间共享资源和协同合作时带来了相 互制约关系，造成进程执行的间断性。（5）结构特征结构特征 为了控制和管理进程，系统为每个进程设 立一个进程控制块一PCB。这样，从结构上看， 每个 进程都是由相应的代码段、数据段和一个PCB三者组成。进程和程序之间一般认为有如下区别：。（1）进程是程序的执行。故进程属于动态概念。而 程序是一组指令的有序集合，是静态的概念；（2）进程既然是程序的执行，或者说是“一次运行活 动”。因而它是

11、有生命过程的，从投入运行到运 行完成。（3）进程是程序的执行，因此进程的组成应包括程 序和数据。除此之外，进程的组成中还包括记 录进程状态信息的“进程控制块”；（4）一个程序可能对应多个进程。（5）一个进程可以包含多个程序。1、系统进程 系统进程起着资源管理和控制的作用。 或者：执行操作系统核心代码的进程。2、用户进程 执行用户程序的进程。在系统中同时有多个进程存在，但归纳起来有两大类：系统进程与用户进程的区别：1、系统进程被分配一个初始的资源集合，这些资源可以为它独占，也能以最高优先权的资格使用。用户进程通过系统服务请求的手段竞争使用系统资源；2、用户进程不能直接做I/O操作，而系统进程可以

12、做显示的、直接的I/O操作。3、系统进程在管态下活动，而用户进程则在用户态（目态）下活动。另一种分类：计算进程，I/O进程等注意：在UNIX系统中没有这样对进程进行分类。三、进程的描述进程控制块： 为了标识进程，记录各个进程执行时的情况，操作系统为每个进程都设置一个“进程控制快”。进程控制块的英文名称的缩写为PCB。 进程控制快是进程实体的一部分，是操作系统中最重要的记录型数据结构之一。PCB中记录了操作系统所需要的、用来描述进程状态及控制进程运行所必需的全部信息。进程控制快的作用，是使一个在多道程序环境下不能独立运行的程序（及其所含的数据），成为一个能独立运行的基本单位，一个能与其他进程并发

13、执行的进程。一般情况下，进程控制块应包含四类信息进程名进程名进程状态进程状态等待原因等待原因进程程序存放位置进程程序存放位置进程数据存放位置进程数据存放位置通用寄存器内容通用寄存器内容控制寄存器内容控制寄存器内容程序状态字寄存器内容程序状态字寄存器内容进程优先数进程优先数队列指针队列指针说明信息说明信息标识信息标识信息现场信息现场信息管理信息管理信息存放进程的管理和控制信息的数据结构称为进程控制块。它是进程管理和控制的最重要的数据结构，在创建时，建立PCB，并伴随进程运行的全过程，直到进程撤消而撤消。PCB就象我们的户口。进程控制块 PCB (Process Control Block)1、进

14、程标识符 name 每个进程都必须有一个唯一的标识符，可以是字符串，也可以是一个数字。UNIX系统中就是一个整型数。在进程创建时由系统赋予。2、进程当前状态 status 说明进程当前所处的状态。 为了管理的方便，系统设计时会将相同的状态的进程组成一个队列，如就绪进程队列，等待进程则要根据等待的事件组成多个等待队列，如等待打印机队列、等待磁盘I/O完成队列等等。3、当前队列指针 next 登记与本进程处于同一队列的下一个进程的PCB的地址。 4、总链指针 all-q-next5、执行程序开始地址 start-addr6、进程优先级 priority 进程的优先级反映进程的紧迫程序，通常由用户指

15、定和系统设置。UNIX系统采用用户设置和系统计算相结合的方式确定进程的优先级。7、CPU现场保护区 cpustatus 当进程因某种原因不能继续占用CPU时（等待打印机），释放CPU，这时就要将CPU的各种状态信息保护起来，为将来再次得到处理机恢复CPU的各种状态，继续运行。例如，我们下课，这时我要记住这次讲到什么地方，下次课接着讲。8、通信信息 communication information 是指某个进程在运行的过程中要与其它进程进行通信，该区记录有关进程通信方面的信息。9、家族联系 process family 有的系统允许一个进程可创建自已的子进程，子进程还可以继续创建子子进程。一个

16、进程往往处在一个家族之中，就需要记录进程在家族中位置的信息。10、占有资源清单 own-resource 进程占用系统资源的情况，不同的系统的处理差别很大，UNIX系统中就没有此项。进程队列进程A进程B进程X队首指针。进程的状态 进程在它存在过程中，由于系统中各进程并行运行及相互制约的结果。使得它们的状态不断发生变化。 系统中不同的事件均可引起进程状态的变化。通常一个进程至少具有三种基本状态： （1）运行状态（又称为执行状态）：当一个进程正在处理机上运行时，称此进程处于运行状态； （2）就绪状态：一个进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态； （3）

17、等待状态（又称阻塞状态）：一个进程正在等待某一事件（如等待某种资源成为可用，等待输入输出完成或等待其它进程给它发来消息）发生而暂时停止运行。这时即使把处理机分配给该进程它也无法运行，则称此进程处于等待状态（或称阻塞状态）。进程在系统中，其状态变化的情况，可大致分为：（1）运行态 - 等待态（2）等待态 - 就绪态 （3）运行态 - 就绪态（4）就绪态 - 运行态 进程在执行过程中状态会不断发生变化，每个进程在执行过程中的任一时刻总是处于上述三种基本状态之一。进程状态的转换关系如图所示。 （1）运行态一等待态 处于运行状态的进程，在其运行过程中需要等待某一事件发生后，才能继续运行，于是该进程由运

18、行状态变为等待状态。例如，一个进程运行中启动了外围设备，它就变成等待外围设备传输信息的状态；进程在运行中申请资源（主存空间及外围设备等）得不到满足时变成等待资源状态；进程在运行中出现了故障（程序出错或主存储器读写错等）变成等待干预状态。（2）等待态 - 就绪态 处于等待状态的进程，若其等待的事件已经发生，于是进程由等待状态变为就绪状态。例如：外围设备工作结束后使等待外围设备传输信息的进程结束等待；等待的资源能得到满足时（另一进程归还了资源）则等待资源者就结束等待；故障排除后让等待干预的进程结束等待。任何一个结束等待的进程必须先变成就绪状态，待分配到处理器后才能运行，等待状态的进程不能直接转变为

19、运行状态。（3）运行态一就绪态 系统在进程用完了一个使用处理器的时间片后就会强迫该进程暂时让出处理器，当有更高优先权的进程要运行时也迫使正在运行的进程让出处理器。不是由于自身或外界原因成为等待状态的进程让出处理器时，它的状态就变成就绪状态。（4）就绪态一运行态 对等待分配处理器的进程，系统按某种选定的策略从处于就绪状态的进程中选择一个进程，让它占用处理器，这个被选中的进程的状态就从就绪态变成运行态。正在执行的进程也称为当前进程。 在一个实际的系统里，出于调度策略的考虑，往往把这三种基本状态进一步细分成若干更多的状态。例如，在UNIX操作系统中，进程的状态被分成六种。当然，状态被细分后，状态转换

20、关系相应地也要更复杂一些。 四、进程的控制 进程是有生命周期的，产生、运行、暂停、终止。对进程的这些操作叫进程控制。 进程控制的职责是对系统中全部进程实施有效的管理，它是处理机管理的部分（另一部分是进程调度），当系统允许多进程并发执行时，为了实现共享、协调并发进程的关系，处理机管理必须提供对进程实行有效的管理。为了防止操作系统及关键数据受到用户程序有意或无意的破坏，通常将处理机的执行状态分成系统态或用户态两种： 系统态：具有较高的特权，能执行一切指令，访问 所有的寄存器和内存 用户态：只能执行规定的命令，访问指定的寄存器 和内存。 通常，用户程序运行在用户态，因此它不能执行操作系统指令和访问操

21、作系统区域，所以操作系统得到了保护。操作系统运行在系统态。进程控制包括： 进程创建 进程撤消 进程阻塞 进程唤醒 这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系统也通过系统调用给用户提供进程控制的功能。教材上叫原语（一种特殊的系统调用）。在UNIX系统中进程控制的系统调用有： fork() 创建子进程 sleep() 进程睡眠 exit() 进程自已终止（自杀） wait() (父）等待子进程终止 wakeup() 进程唤醒1、进程的创建 进程之间的关系可以用进程图来描述。 子进程可以继承父进程所拥有的资源。撤消父进程时必须同时撤消其所有子进程。ABCDEEFG进程创建系统

22、调用：create(name,priority,start-addr)UNIX系统：fork()引起进程创建的事件用户登陆作业调度提供服务应用请求进程的创建过程申请空白PCB为新进程分配资源初始化进程控制块将新进程插入就绪队列2 2、进程的终止、进程的终止正常结束正常结束异常结束异常结束越界错误保护错特权指令错非法指令错运行超时等待超时算术运算错I/O故障外界干预外界干预操作员干预或操作系统干预父进程请求父进程终止 进程完成其任务，希望终止时，调用终止进程的系统调用（进程终止原语）终止进程。相当于一个人死亡后，家人要去派出所消户口。 在一般操作系统中进程终止的系统调用是：kill UNIX系统

23、中是exit()。 进程的终止过程进程的终止过程 根据被终止进程的标识符，从PCB集合中检索出 该进程的PCB，读出其状态信息。 若被终止进程正处于执行状态，应立即终止该进 程的执行，并设置调度标志为真。 若该进程还有子孙进程，应将其所有子孙进程予 以终止。 将该进程所拥有的所有资源，或者归还给父进程， 或者归还给系统。 将被终止进程从所在队列中移出。3 3、进程的阻塞与唤醒、进程的阻塞与唤醒引起进程阻塞与唤醒的事件请求系统服务启动某种操作新数据尚未到达无新工作可做进程的阻塞过程进程的阻塞过程 正在执行的进程，当出现上述某个事件时，由于无法继续执行，于是进程便通过调用阻塞原语把自己阻塞，可见，

24、进程的阻塞是进程自身的一种主动行为。进入阻塞过程后，由于进程此时还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为“阻塞”。并把它插入到阻塞队列（如系统中设置了因不同事件而阻塞的多个阻塞队列则应将改进程插入到具有相同事件的阻塞队列）。最后转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换。 进程从运行状态转换成阻塞状态是由进程挂起原语实现的，因此，调用进程挂起操作是在进程处于运行状态下执行的。它的执行将引起等待某事件的队列的改变. 例如，进程是因等待打印机而进入阻塞状态，则该进程将加入到等待打印机的队列。进程挂起系统调用的算法和队列变化如下。进程挂起的内部

25、调用形式（UNIX系统）： sleep(chan,pri) 其中：chan 进程挂起（睡眠）的原因； pri 进程被唤醒后的优先级 一般调用形式： susp(chan) 其中：chan 进程等待的原因进程的唤醒过程进程的唤醒过程 一个正在运行的进程会因等待某事件（例如，等待打印机）的发生，由运行状态转换成阻塞状态，当它等待的事件发生后，这个进程将由阻塞状态转换成就绪状态。这种转换由进程唤醒操作完成。 当被阻塞进程所期待的事件出现时，则由有关进程调用唤醒原语，将等待改事件的进程唤醒。唤醒原语的执行过程是：首先将被阻塞进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将

26、该进程插入到就绪队列中。 调用进程唤醒操作一般在中断处理、进程通信等过程中。例如，打印机完成中断处理程序， 在完成了打印完成的操作后，就去检查等待打印机的队列，若不为空，则调用进程唤醒操作，唤醒一个（或多个）等待打印机的进程。 进程唤醒原语的形式：wakeup(chan)其中：chan 唤醒进程阻塞的原因。算法：wakeup输入：chan:等待的事件（阻塞原因）输出：无 找到chan的等待队列的指针； for(该队列不为空） 从队列中移出一个进程； 置进程状态为“就绪”，并加入到就绪队列； 按此算法，是把等待在chan事件上的所有进程唤醒，类似于UNIX系统的处理方式。也有的系统只唤醒一个等待

27、chan事件的进程，若这样处理，等待队列就要按某种优先级排队。 进程唤醒操作会引起就绪队列和等待chan事件的等待队列发生变化。五、进程的调度 1 1、什么是进程调度、什么是进程调度 进程调度的职责就是根据一定的算法，从多个就绪进程中选择其一来占用CPU。 2 2、进程调度的方式、进程调度的方式 非抢占式（非剥夺方式）：就是某进程一旦占用了CPU，除非它自身的原因（如调用原语操作或等待某事件的发生）而自动放弃CPU，否则它将一直运行下去。 抢占式（剥夺方式）：某进程占用CPU的执行过程中，如果出现了一个优先级更高的就绪进程，则系统将强行中断正在执行的进程，而把CPU分配给具有更高优先级的就绪进

28、程。这种方式反映了进程的优先级特征。3 3、进程调度算法、进程调度算法v 优先数调度算法 该算法的基本思想是：系统为每个进程设置一个优先数（对应一个优先级），调度时从就绪队列中选择优先级最高的进程投入运行。静态优先数：按进程的重要程度为每个进程分配一个 优先级，该优先级在进程的整个运行过 程中不再改变。动态优先数：进程的优先数在其运行时可以改变 v 先来先服务调度算法 该算法按照进程进入就绪队列的先后次序来选择进程，使之占用CPUv 时间片轮转调度算法 所有就绪状态的进程按建立的先后顺序形成一个队列，从队列首部挑选一个进程，并分配一个时间片q，使其投入运行。当时间片到而进程的工作还未完成时，该

29、进程将会再次加入到就绪队列的队尾，等待下一轮的调度。这种方法也称为简单轮转法。 对时间片的讨论：假定，时间片为q，同时就绪的进程数为N，系统的响应时间为T，则它们之间有如下关系：NTq 可见，如果系统要求的响应速度高，即T要小，则 q 也会随之减少。或者说，时间片越小，则响应速度越高。但 q 的设定也有个下限，这个下限取决于系统进行进程切换时所需要的时间。假定进程切换需要的时间为，一般来说，q 的值要远远大于，比如与q的比为1/10。 作为简单轮转法的延伸，还有一种类似的方法，称为固定周期轮转法。其基本思想是：在保证系统的响应时间不变的前提下，动态设定时间片q的大小。T N qT N q3 3

30、0 0.13 30 0.13 6 0.53 6 0.5注意，每一轮调度中所得的q值大小，只在这一轮有效。 v 分级调度算法 系统将就绪进程按其优先级高低的不同，设置两级或多级队列，进程调度每次总是先从高优先级就绪队列中挑选进程，只有其队列为空时，才从较低优先级就绪队列中选取。每个队列中（同一优先级就绪进程）可按先来先服务或轮转法进行调度。 高优先级就绪队列中优先级就绪队列低优先级就绪队列CPU时间片完时间片完时间片完q = 50msq = 100msq = 500ms低优先低优先级就绪级就绪队列队列高优先高优先级就绪级就绪队列队列中优先中优先级就绪级就绪队列队列阻塞阻塞队列队列执行执行阻塞阻塞

31、队列队列阻塞阻塞队列队列q = 50msq = 500msq = 100ms时间片完时间片完I/O完成完成I/O完成完成I/O完成完成请求磁请求磁盘盘I/O请求终请求终端端I/O请求页请求页面面I/Ov 带反馈多级队列轮转法模型 考虑5个进程P1，P2，P3，P4，P5。规定进程的优先数越小，优先级越高。进程的创建时刻，运行时间和优先数在下面的表中： 进程创建时刻运行时间（ms）优先数P1033P2265P3441P4652P5824 试描述在采用各种不同调度算法时，各个进程的运行情况，并计算采用每种调度算法时的进程平均周转时间。忽略进程的调度和进程切换时间。 先来先服务调度算法进程的运行过程

32、如下：5101520P1P2P3P4P5算法进程名创建时刻结束时刻周转时间平均周转时间 先来先服务P1033 （3+7+9+12+12）/ 5 =8.6P2297P34139P461812P582012时间片轮转调度算法（固定时间片为1ms）进程的运行过程如下： 5101520P1P2P3P4P5 时间片轮转P1044 （4+16+13+14+7）/ 5 =10.8P221816P341713P462014P58157非强占式优先级调度算法进程的运行过程如下： 5101520P1P2P3P4P5 非强占式优先级P1033 （3+7+9+12+12）/ 5 =8.6P2297P34139P461812P582012强占式优先级调度算法进程的运行过程如下： 5101520P1P2P3P4P5 强占式优先级P1033 （3+18+4+7+7）/ 5 =7.8P222018P3484P46137P58157进程的切换（进程的调度时机）进程的切换（进程的调度时机） 通常，在下列情况下均会引起进程调度程序工作： （1）一个进程从运行状态变成了等待状态。 （2）一个进程从运行状态变成了就绪状态。 （3）一个进程从等待状态变成了就绪状态。 （4）一个进程完成工作后被撤消。