第二章__进程管理

1、S1:a := x+y;S2: b := a-5;S3: c := b+1;S2必须在必须在S1后执行后执行;S3在在S2后执行后执行 是指程序执行时，必须是指程序执行时，必须按某种先后顺序执行，仅当按某种先后顺序执行，仅当前一操作（程序段）执行完前一操作（程序段）执行完后，才能执行后继操作。后，才能执行后继操作。又如又如: 程序中有输入、计算、打印操作程序中有输入、计算、打印操作I1C1p1I2C2p2 I：输入操作，：输入操作，C：计算操作，：计算操作，P：打印操作：打印操作 顺序性顺序性封闭性封闭性可再现性可再现性程序一旦开始执程序一旦开始执行，其计算结果行，其计算结果不受外界因素的不受

2、外界因素的影响。影响。处理机的操处理机的操作严格按照作严格按照程序所规定程序所规定的顺序执行。的顺序执行。程序执行的结果与它程序执行的结果与它的执行速度无关的执行速度无关(即与即与时间无关时间无关)，而只与初，而只与初始条件有关。始条件有关。 前驱图前驱图 是一个有向无循环图是一个有向无循环图DAG(Directed Acyclic Graph) ，描述进程之间执行的前后关系。，描述进程之间执行的前后关系。结结 点：点：描述一个程序段或进程或一条语句描述一个程序段或进程或一条语句有向边：有向边：表示结点之间存在的前趋关系。记表示结点之间存在的前趋关系。记 为为“”前趋关系表示前趋关系表示: =

3、(Pi, Pj ) | Pi must complete before Pj may start 如果如果(Pi, Pj) ,可写成可写成Pi Pj，称称Pi是是Pj的的直接直接前趋前趋,而称而称Pj是是Pi的的直接后继。直接后继。初始结点初始结点: 没有前趋的结点。没有前趋的结点。终止结点终止结点: 没有后继的结点。没有后继的结点。存在前趋关系：存在前趋关系：P1P2,P1P3,P1P4,P2P5,P3P5,P4P6,P5P7,P6P7 或或P= P1,P2,P3,P4,P5,P6,P7=(P1,P2)(P1,P3 )( P1,P4 )( P2,P5 )( P3,P5 )( P4,P6 )(

4、 P5,P7 )( P6,P7)P2I1C1p1I2C2p2分析分析Ii Ci Pi对一个作业的输入、计算和对一个作业的输入、计算和打印操作，必须顺序执行打印操作，必须顺序执行对一批程序进行处理时，对一批程序进行处理时，可使它们并发执行。可使它们并发执行。Pi Ii+1输入设备、打印机、中央处理机是三个物理输入设备、打印机、中央处理机是三个物理部件。它们可以同时操作。部件。它们可以同时操作。一、程序并发执行一、程序并发执行 一、程序并发执行一、程序并发执行 IiIi+1CiCi+1PiPi+1相相互互合合作作资源共享资源共享I2I3I4I1C1C2C3C4P1P2P3IiCiPiI Ii+1i

5、+1、C Ci i、P Pi-1i-1并发执行并发执行相互制约相互制约执行执行暂停暂停执行执行间断性间断性失去封失去封闭性闭性不可再现性不可再现性 程序与计算结程序与计算结果不再一一对应果不再一一对应举例：举例：运行速度不同，设运行速度不同，设N=n1、 N:=N+1 Print（N） N:=0N值分别为值分别为n+1，n+1，02、Print（N） N:=0 N:=N+1 N值分别为值分别为n，0，13、 Print（N） N:=N+1 N:=0 N值分别为值分别为n，n+1，0 程序程序A:N:=N+1程序程序B:Print (N)N:=0N失去失去可再现性可再现性计算结果与并发程序执行的

6、速度有关计算结果与并发程序执行的速度有关R(P1)W(P2)R(P2)W(P1)W(P1)W(P2)= 程程序序P1和和P2若满足若满足能并发执行能并发执行且具有可再现性且具有可再现性读集读集写集写集R（Pi）=a1,a2,am 程序程序P i在执行期间所需在执行期间所需参考的所有变量的集合。参考的所有变量的集合。W（Pi）=b1,b2,bn 程序程序P i在执行期间要改在执行期间要改变的所有变量的集合。变的所有变量的集合。C=a-bW=c+1R（C:=a-b）= a，b W（C:=a-b）=cR（W:=c+1）=c W（W:=c+1）=w请问请问S1和和S2, S1和和S3, S2和和S3,

7、 S3和和S4能否并发执行？能否并发执行？现有四条语句：现有四条语句：S1: a=X+Y S2: b=Z+1S3: C=a-b S4: w=c+1R(S1)W(S2)R(S2)W(S1)W(S1)W(S2)=x，ybzaab= R(S3)W(S1)R(S1)W(S3)W(S3)W(S1)=a，bax，ycca=aS1和和S2可以可以并发执行并发执行 S1和和S3不能并不能并发执行发执行 同理同理S2和和S3不能并发执行不能并发执行,因为因为R(S3)W(S2)=bS3和和S4不能并发执行，因为不能并发执行，因为R(S4)W(S3)=cS1:a=X+Y S2: b=Z+1 S3:c=a-b S4

8、:w=c+1R(S1)=x,yW(S1)=aR(S2)=z W(S2)=b R(S3)=a,b W(S3)=c R(S4)=c W( S4)=w 由上可知，程序并发执行时，产生了一由上可知，程序并发执行时，产生了一些新特征，致使一般的程序不能并发执行。些新特征，致使一般的程序不能并发执行。 为了使程序在多道程序环境下能并发执行，为了使程序在多道程序环境下能并发执行，并能对其控制和描述。并能对其控制和描述。引引入入 Multics（Multiplexed Information and Computing，多路信息和计算服务）操作系统，多路信息和计算服务）操作系统，其设计人员首次在操作系统环境中

9、使用了其设计人员首次在操作系统环境中使用了“进进程程”这个术语。这个术语。 （1 1） 进程是程序的一次执行；进程是程序的一次执行；（2 2） 进程可定义为一个数据结构及能在进程可定义为一个数据结构及能在其上进行操作的一个程序；其上进行操作的一个程序；（3 3） 进程是一个程序及其数据在处理机进程是一个程序及其数据在处理机上顺序执行时所发生的活动。上顺序执行时所发生的活动。 可并发执行的程序在一个数据集合可并发执行的程序在一个数据集合上的运行过程。上的运行过程。姚明姚明做蛋糕的食谱做蛋糕的食谱原料：面粉、鸡蛋等原料：面粉、鸡蛋等阅读食谱阅读食谱取原料取原料进程一进程一为女儿做为女儿做蛋糕蛋糕儿

10、子摔伤儿子摔伤记录照食谱做到哪儿记录照食谱做到哪儿（保存进程一的当前（保存进程一的当前状态状态）进程二进程二实施医疗救治实施医疗救治（优先处理进程）（优先处理进程）急救手册急救手册（程序）（程序）程序程序输入数据输入数据输出输出进程切换进程切换CPU进程切换进程切换动态动态性性并发性并发性独立独立性性异步异步性性结构结构特性特性 结构特征：结构特征：动态性：动态性：并发性：并发性：独立性：独立性：异步性：异步性：进程实体是由程序段、数据段及进程控制块进程实体是由程序段、数据段及进程控制块三部分组成，有人把这三部分统称为三部分组成，有人把这三部分统称为“进程进程映像映像”。进程是程序的一次执行进

11、程是程序的一次执行 多个进程实体，同存在于内存中，轮流占有多个进程实体，同存在于内存中，轮流占有处理机和各种资源，走走停停交叉运行。处理机和各种资源，走走停停交叉运行。 进程是进行资源分配和调度运行的基本单位。进程是进行资源分配和调度运行的基本单位。 这是指进程按各自独立的、不可预知的速度这是指进程按各自独立的、不可预知的速度向前推进，或者说进程按异步方式运行向前推进，或者说进程按异步方式运行 最基本特最基本特征征（1）程序程序是为了完成某项工作时需要计算机是为了完成某项工作时需要计算机执行的执行的指令的集合指令的集合，是，是静态的概念静态的概念；而；而进程进程是是程序的执行程序的执行，是，是

12、动态的概念动态的概念。（2）程序程序是是永远存在永远存在的，的，进程进程则则有生存期有生存期，它的存在是暂时的。它的存在是暂时的。（3）进程进程是一个是一个独立调度独立调度并能和其它进程并能和其它进程并并发运行的单位发运行的单位，而，而程序和程序段程序和程序段则则不能不能作为作为一个独立调度运行的单位，也一个独立调度运行的单位，也不能并发执行不能并发执行。（1）一个程序可以对应多个进程。一个程序可以对应多个进程。当同一个当同一个程序运行在不同的数据集时，就构成不同的程序运行在不同的数据集时，就构成不同的进程。比如：用户用电子邮件程序发不同的进程。比如：用户用电子邮件程序发不同的Email;同一

13、用户能用编辑器程序编辑不同的同一用户能用编辑器程序编辑不同的文件。文件。（2）一个进程可以对应多个程序。一个进程可以对应多个程序。 主程序主程序可以调用其它子程序，但至少对应一个程序。可以调用其它子程序，但至少对应一个程序。在多道程序系统中，由于多个进程并发执行，对有限的在多道程序系统中，由于多个进程并发执行，对有限的系统资源进行争夺，尤其是对处理机的竞争更为激烈，系统资源进行争夺，尤其是对处理机的竞争更为激烈，导致它们的状态不断变化。进程的动态性质是由其状态导致它们的状态不断变化。进程的动态性质是由其状态变化决定的。如果一个事物始终处于一种状态，那么变化决定的。如果一个事物始终处于一种状态，

14、那么它就不再是活动的，就没有生命力了。它就不再是活动的，就没有生命力了。1) 就绪状态就绪状态 2) 执行状态执行状态 3) 阻塞状态，又称等待状态阻塞状态，又称等待状态 就绪就绪执行执行阻塞阻塞12341.进程因等待进程因等待I/O而阻塞而阻塞2.时间片到时间片到3.进程调度进程调度4.I/O完成完成即使即使CPU无事无事可做，也不能可做，也不能执行执行1、新（创建）状态、新（创建）状态 这是一个进程刚刚建立，但还未将它这是一个进程刚刚建立，但还未将它 送入就绪队列时的状态。送入就绪队列时的状态。2、终止状态、终止状态 当一个进程已经正常结束或异常结束，当一个进程已经正常结束或异常结束， O

15、S已将它从执行状态中移出，但尚未已将它从执行状态中移出，但尚未 将它撤消时的状态。将它撤消时的状态。OS创建新进程创建新进程分为两步分为两步已结束的进程已结束的进程退出系统分为退出系统分为两步两步创建创建就绪就绪执行执行终止终止阻塞阻塞接纳接纳进程调度进程调度时间片到时间片到释放释放I/O中断或中断或等待某事件等待某事件I/O完成或完成或事件发生事件发生进程的五种状态进程的五种状态a、终端用户的需求、终端用户的需求 正在执行：暂停正在执行：暂停 就绪状态：暂不接受调度就绪状态：暂不接受调度1)、引入挂起状态的原因、引入挂起状态的原因静止状态静止状态b、 父进程的需求父进程的需求c、 OS的需要

16、的需要d、 对换的需要对换的需要e、 负荷调节的需要负荷调节的需要活动就绪活动就绪执行执行静止就绪静止就绪静止阻塞静止阻塞活动阻塞活动阻塞挂起挂起激活激活挂起挂起请求请求I/O挂起挂起激活激活I/O完成完成I/O完成完成调度调度1、活动就绪、活动就绪静止就绪静止就绪2、活动阻塞、活动阻塞静止阻塞静止阻塞3、静止就绪、静止就绪活动就绪活动就绪4、静止阻塞、静止阻塞活动阻塞活动阻塞 l 静止就绪、静止阻塞：该进程都不可能被调度静止就绪、静止阻塞：该进程都不可能被调度而执行。而执行。l 处于静止阻塞状态的进程，其阻塞条件与挂起处于静止阻塞状态的进程，其阻塞条件与挂起条件无关。当进程等待的事件出现后，

17、该进程条件无关。当进程等待的事件出现后，该进程从静止阻塞转换为静止就绪。从静止阻塞转换为静止就绪。l 进程可以由其自身挂起，也可由用户或进程可以由其自身挂起，也可由用户或OS等将等将之挂起。被挂起的进程是只能被显式方式来激之挂起。被挂起的进程是只能被显式方式来激活，以便从挂起状态中解脱出来。活，以便从挂起状态中解脱出来。l(1) 可运行状态（可运行状态（TASK_RUNNING）：进程正在运）：进程正在运行或处于就绪，只要得到行或处于就绪，只要得到CPU就可以立即投入运行的就就可以立即投入运行的就绪态。可运行状态进程组成的队列（绪态。可运行状态进程组成的队列（RUN_QUEUE）。）。l(2)

18、 等待状态：进程正在等待某个事件发生或等待某等待状态：进程正在等待某个事件发生或等待某种资源的状态。种资源的状态。Linux进程有两种等待状态：可中断的等进程有两种等待状态：可中断的等待状态（待状态（TASK_INTERRUPTIBLE）和不可中断等待状）和不可中断等待状态（态（TASK_UNINTERRUPTIBLE）。）。l(3) 暂停状态（暂停状态（TASK_STOPPED）：此时进程暂时）：此时进程暂时停止运行，接受某种处理。停止运行，接受某种处理。l(4) 僵死状态（僵死状态（TASK_ZOMBIE）：表示进程结束）：表示进程结束但尚未消亡的一种状态。但尚未消亡的一种状态。 作用：是

19、使一个在多道环境下不能独立运行的作用：是使一个在多道环境下不能独立运行的程序成为一个能独立运行的基本单位，一个能与其程序成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。它进程并发执行的进程。 OS根据根据PCB来对并发执行的进程进行控制和管来对并发执行的进程进行控制和管理。理。 1、进程控制块的作用、进程控制块的作用PCB 应应该常驻内该常驻内存存(1)进程标识符信息：进程标识符信息： 每个进程都必须有一个唯一的标识符每个进程都必须有一个唯一的标识符, 用于唯一标用于唯一标识一个进程识一个进程 外部标识符外部标识符: 便于用户使用便于用户使用内部标识符内部标识符: 便于系统使用便

20、于系统使用(2) 处理机状态信息处理机状态信息由处理机的各种寄存由处理机的各种寄存器中的内容组成器中的内容组成l通用寄存器通用寄存器l指令计数器指令计数器l程序状态字程序状态字PSWl用户栈指针用户栈指针(3) 进程调度信息进程调度信息u 进程的当前进程的当前状态状态u 进程的优先级进程的优先级u 进程调度所需的其它信息进程调度所需的其它信息 如进程已等待如进程已等待CPUCPU的时间总和、进程已执的时间总和、进程已执行的时间总和等；行的时间总和等；u 事件事件 是指进程由执行状态转变为是指进程由执行状态转变为阻塞状态所阻塞状态所等等待发生的事件，即待发生的事件，即阻塞阻塞原因。原因。程序和数

21、据的地址程序和数据的地址： 是指进程的程序和数据所在的内存或外存（首）地是指进程的程序和数据所在的内存或外存（首）地址，以便再调度到该进程执行时，能从址，以便再调度到该进程执行时，能从PCB中找到其程中找到其程序和数据；序和数据；实现进程同步和通信相关信息实现进程同步和通信相关信息： 如消息队列指针、信号量等；如消息队列指针、信号量等；资源清单资源清单： 包括进程所需全部资源、已经分得的资源。包括进程所需全部资源、已经分得的资源。链接指针链接指针： 给出了本进程给出了本进程PCB所在队列中的下一个进程的所在队列中的下一个进程的PCB首地址。首地址。(4) 进程控制信息进程控制信息(1). 链接

22、方式链接方式 索引表索引表就绪队列就绪队列等待队列等待队列 1等待队列等待队列 2PCB 1PCB 2PCB 3PCB 4PCB 5PCB 6PCB 7PCB n PCB表表处理机的处理机的执行状态执行状态用户态用户态系统态系统态特特权权执行执行指令指令访问寄访问寄存器和存器和存储器存储器较高较高 所有所有 所有所有较低较低 规定规定 指定的指定的 OS内核内核用户程序用户程序处理机在处理机在系统程序系统程序中执行中执行处理机在用户处理机在用户程序中执行程序中执行 进进程图是程图是用于描用于描述进程述进程家族关家族关系的有系的有向树。向树。 ABCDEFGHI子进程子进程父父进进程程祖祖父父进

23、进程程祖先进程祖先进程（1） 用户登录：分时系统用户登录：分时系统 ( 2 ) 作业调度：批处理系统作业调度：批处理系统 ( 3 ) 提供服务提供服务 由由OS创建，以向用户提供服务创建，以向用户提供服务( 如：打印文件如：打印文件) ( 4 ) 应用请求应用请求 一个用户程序可创建成多个进程一个用户程序可创建成多个进程（1） 申请空白申请空白PCB：申请唯一的数字标识符。：申请唯一的数字标识符。（2） 为新进程分配资源：为程序、数据、用户栈为新进程分配资源：为程序、数据、用户栈分配必要的空间。分配必要的空间。（3） 初始化进程控制块：标识信息、处理机状态初始化进程控制块：标识信息、处理机状态

24、信息、处理机控制信息。信息、处理机控制信息。（4） 将新进程插入就绪队列将新进程插入就绪队列 #define TRUE 1 while(TRUE) type_prompt(); /*在屏幕上显示提示信息在屏幕上显示提示信息 */ read_command(command,parameters); /*从终端读取输入从终端读取输入*/ if (fork()!=0) /*创建子进程创建子进程*/ /*父进程父进程,pid0*/ waitpid(-1,status,0）; /*等待子进程退出等待子进程退出*/ else /*child code ,pid=0*/ execve(command,par

25、ameters,0); /*执行命令执行命令*/ 一个简化的一个简化的shellcp主函数：主函数：main(argc, argv, envp) argc:为命令行参数个数，为命令行参数个数，3； argv:字符串数组字符串数组 argv0为为“cp”, argv1命令行中执行程序名后的第一个字命令行中执行程序名后的第一个字符串符串; argv2 为执行程序名后的第二个字符串为执行程序名后的第二个字符串; envp: 字符串数组。字符串数组。 envp 的每一个元素都包含的每一个元素都包含name=value，用来将各种环境信息传递程序。用来将各种环境信息传递程序。 shell解析读入命令行解

26、析读入命令行 Linux系统运行的第一个进程系统运行的第一个进程Init是在内核引导并完成基本是在内核引导并完成基本的初始化后就有了，这个进程是所有进程的总根，所有其他的的初始化后就有了，这个进程是所有进程的总根，所有其他的进程和内核线程都由这个原始进程或其子孙进程所创建。进程和内核线程都由这个原始进程或其子孙进程所创建。 在在Linux 中，创建新进程的方法是中，创建新进程的方法是fork和和clone。 Linux将进程的创建与目标的执行分成两步：将进程的创建与目标的执行分成两步： 第一步：从已存在的第一步：从已存在的“父进程父进程”复制出一个复制出一个“子进程子进程”，复制出来的子进程有

27、自己的复制出来的子进程有自己的task_struct结构核系统空间堆栈，结构核系统空间堆栈，但与父进程共享其他所有的资源。比如：打开的文件，打开文但与父进程共享其他所有的资源。比如：打开的文件，打开文件的读写指针等。件的读写指针等。 第二步：执行目标程序。创建新进程一般要让新进程执行第二步：执行目标程序。创建新进程一般要让新进程执行新的目标程序。复制完成后，子进程要与父进程分道扬镳，新的目标程序。复制完成后，子进程要与父进程分道扬镳，Linux提供了一个系统调用提供了一个系统调用execve,让一个进程执行以文件形式让一个进程执行以文件形式存在的一个可执行程序的映象。存在的一个可执行程序的映象

28、。 fork系统调用的作用是复制一个进程。当一个进程调用它，完成后就出系统调用的作用是复制一个进程。当一个进程调用它，完成后就出现两个几乎一模一样的进程。现两个几乎一模一样的进程。 命令行下运行应用程序，新的进程也是由命令行下运行应用程序，新的进程也是由shell调用调用fork制造出来的。制造出来的。 /* fork_test.c */#include /标准输入输出头文件，里面包含了标准输入输出函数的声明标准输入输出头文件，里面包含了标准输入输出函数的声明 #inlcude /提供通用的文件、目录、程序及进程操作的函数提供通用的文件、目录、程序及进程操作的函数 main()pid_t pi

29、d; /此时仅有一个进程此时仅有一个进程,每个进程都有一个唯一的整数形式的进程标识符每个进程都有一个唯一的整数形式的进程标识符 pid=fork(); /此时已经有两个进程在同时运行此时已经有两个进程在同时运行if(pid0)printf(error in fork!);else if(pid=0)printf(I am the child process, my process ID is %dn,getpid();elseprintf(I am the parent process, my process ID is %dn,getpid();编译并运行：编译并运行： $gcc fork_

30、test.c -o fork_test $./fork_test 进入进入main ()的进程为父进程，执行系统调用的进程为父进程，执行系统调用fork()创建创建一个子进程，子进程复制出来后，和父进程一样接受内核的一个子进程，子进程复制出来后，和父进程一样接受内核的调度，并具有相同的返回地址。当副进程和子进程受调度继调度，并具有相同的返回地址。当副进程和子进程受调度继续运行而从内核空间返回时都返回到同一点上。续运行而从内核空间返回时都返回到同一点上。 子进程有一个不同于父进程的进程号子进程有一个不同于父进程的进程号pid，父进程和子，父进程和子进程从进程从fork()返回时具有的返回值不一样

31、。当子进程从返回时具有的返回值不一样。当子进程从fork()返回时，其返回值为返回时，其返回值为0；而父进程从；而父进程从fork()返回时的返回值为返回时的返回值为子进程的子进程的pid。运行结果：运行结果： I am the parent process, my process ID is 1991 I am the child process, my process ID is 1992 看这个程序的时候，头脑中必须首先了解一个概念：在语看这个程序的时候，头脑中必须首先了解一个概念：在语句句pid=fork()之前，只有一个进程在执行这段代码，但在这条语之前，只有一个进程在执行这段代码，

32、但在这条语句之后，就变成两个进程在执行了，这两个进程的代码部分完句之后，就变成两个进程在执行了，这两个进程的代码部分完全相同，将要执行的下一条语句都是全相同，将要执行的下一条语句都是if(pid=0)。 父子进程父子进程的区别除了进程标志符（的区别除了进程标志符（process ID）不同外，变量）不同外，变量pid的值也的值也不相同，不相同，pid存放的是存放的是fork的返回值。的返回值。fork调用的一个奇妙之处调用的一个奇妙之处就是它仅仅被调用一次，却能够返回两次，它可能有三种不同就是它仅仅被调用一次，却能够返回两次，它可能有三种不同的返回值：的返回值： 在父进程中，在父进程中，for

33、k返回新创建子进程的进程返回新创建子进程的进程ID； 在子进程中，在子进程中，fork返回返回0； 如果出现错误，如果出现错误，fork返回一个负值。返回一个负值。 fork出错可能有两种原因：（出错可能有两种原因：（1）当前的进程数已经达到了系统规定的）当前的进程数已经达到了系统规定的上限，这时上限，这时errno的值被设置为的值被设置为EAGAIN。（。（2）系统内存不足，这时）系统内存不足，这时errno的的值被设置为值被设置为ENOMEM。 由于子进程和父进程一样接受内核调度，而每次系统调度由于子进程和父进程一样接受内核调度，而每次系统调度都由可能引起调度，所以二者返回的次序是不定的。

34、都由可能引起调度，所以二者返回的次序是不定的。(1). 正常结束正常结束 (2). 异常结束异常结束 (3). 外界干预外界干预 1、引起进程终止的事件、引起进程终止的事件 2、进程的终止过程、进程的终止过程 调用进程终止原语终止指定进程。调用进程终止原语终止指定进程。 (1) 根据被终止进程的标识符，从根据被终止进程的标识符，从PCB集合集合中检索出该进程的中检索出该进程的PCB，从中读出该进程，从中读出该进程的状态。的状态。(2) 若被终止进程正处于执行状态，应立即若被终止进程正处于执行状态，应立即终止该进程的执行，置调度标志为真，用终止该进程的执行，置调度标志为真，用于指示该进程被终止后

35、应重新进行调度。于指示该进程被终止后应重新进行调度。(3) 若该进程有子孙进程，应将其所有子孙若该进程有子孙进程，应将其所有子孙进程予以终止，以防他们成为不可控的进进程予以终止，以防他们成为不可控的进程。程。(4) 将被终止进程所拥有的全部资源，或归将被终止进程所拥有的全部资源，或归还其父进程，或归还系统。还其父进程，或归还系统。(5) 将被终止进程的将被终止进程的PCB从所在队列或链表从所在队列或链表中移出，等待其他程序搜索信息。中移出，等待其他程序搜索信息。(1)、请求系统服务、请求系统服务 (2)、启动某种操作、启动某种操作 (3)、新数据尚未到达、新数据尚未到达 (4)、无新工作可做、

36、无新工作可做 1、引起进程阻塞和唤醒的事件、引起进程阻塞和唤醒的事件 3、进程唤醒过程、进程唤醒过程： 实现进程从执行状态到阻塞状态的转换实现进程从执行状态到阻塞状态的转换。 实现进程从阻塞状态到就绪状态的转换。实现进程从阻塞状态到就绪状态的转换。进程自身的一种进程自身的一种主动行动主动行动由相互合作的进由相互合作的进程或相关的进程程或相关的进程调用阻塞原语调用阻塞原语1、挂起过程、挂起过程2、激活过程、激活过程 原语原语(primitive)：由若干条指令构成的：由若干条指令构成的“原子操作原子操作(atomic operation)”过程，作为一个整体而过程，作为一个整体而不可分割不可分割

37、要么要么全都完成，要么全都不做。原语是操作系统核心的一个组成全都完成，要么全都不做。原语是操作系统核心的一个组成部分，它必须在核心态下执行，并且常驻内存。部分，它必须在核心态下执行，并且常驻内存。 原语和系统调用的区别：原语有不可中断性，通过在其原语和系统调用的区别：原语有不可中断性，通过在其执行过程中关闭中断实现的，且一般由系统进程调用。许多执行过程中关闭中断实现的，且一般由系统进程调用。许多系统调用都可在用户态下运行的系统进程完成，而不一定要系统调用都可在用户态下运行的系统进程完成，而不一定要在核心态下完成。在核心态下完成。(1)间接相互制约关系间接相互制约关系 资源共享关系资源共享关系(

38、2)直接相互制约关系直接相互制约关系 相互合作关系相互合作关系 诸进程应互斥地诸进程应互斥地访问访问临界资源临界资源。 是指一次仅允许一是指一次仅允许一个进程使用的资源。个进程使用的资源。 在多道程序环境下，各进程并发执行，并以各自独立的在多道程序环境下，各进程并发执行，并以各自独立的速度向前推进。但由于资源共享和进程合作，因而产生速度向前推进。但由于资源共享和进程合作，因而产生了进程之间的相互制约。了进程之间的相互制约。 保证各进程协调运行的机制，称为保证各进程协调运行的机制，称为同步机制同步机制。 同一时间内只允许一个进程访问的资源同一时间内只允许一个进程访问的资源称称临界资源临界资源，许

39、多物理设备，以及数据都是，许多物理设备，以及数据都是临界资源，它们只能临界资源，它们只能互斥互斥地被共享。地被共享。 以某种手段确保当一个进程在使用一个共享变量或文以某种手段确保当一个进程在使用一个共享变量或文件时，其它进程不能做同样的操作。件时，其它进程不能做同样的操作。a := a -1 print (a)a := a +1 print (a)P1互斥互斥P2互斥互斥If a 0then a := a +1else a:= a-1P3互斥互斥 进程的互斥进程的互斥（间接作用）（间接作用）程 序 段1程 序 段2程 序 段n共 享 变 量消费者消费者生产者生产者问题描述：问题描述： 一群生产

40、者进程在生产产品，并将这些产品提一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程和消费者供给消费者进程去消费。为使生产者进程和消费者进程能并发执行，在两者之间设置了一个具有进程能并发执行，在两者之间设置了一个具有n个个缓冲区的缓冲池。生产者进程将它所生产的产品放缓冲区的缓冲池。生产者进程将它所生产的产品放入缓冲池，消费者进程可以从缓冲池中取走产品去入缓冲池，消费者进程可以从缓冲池中取走产品去消费。消费。只要缓冲区未满，生产者生产的产品就可投只要缓冲区未满，生产者生产的产品就可投入缓冲池；类似地，只要缓冲池不空，消费者进程入缓冲池；类似地，只要缓冲池不空，消费者进程就

41、可从缓冲池取走并消耗产品。就可从缓冲池取走并消耗产品。同步：同步： 不允许消费者进程到空缓冲区去取产品；不允许消费者进程到空缓冲区去取产品； 不允许生产者进程向一个已装满产品且尚未被取走的不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。缓冲区中投放产品。 数据结构及其数据关系数据结构及其数据关系数组数组buffer：表示表示n个（个（0，1，n-1）缓冲区的缓冲池；）缓冲区的缓冲池；输入指针输入指针in：指示下一个可投放消息的缓冲区；指示下一个可投放消息的缓冲区；输出指针输出指针out：指示下一个可获取消息的缓冲区。指示下一个可获取消息的缓冲区。输入指针输入指针+1：in= （

42、in+1）mod n；输出指针输出指针+1： out=（out+1）mod n；当（当（in+1）mod n= out时时：表示缓冲池满：表示缓冲池满;当当in= out：表示缓冲池空。表示缓冲池空。整型变量整型变量counter：初值为初值为0。 生产者投放一个消息生产者投放一个消息counter+1； 消费者进程从中取走一个消息时，消费者进程从中取走一个消息时，counter-1。 Var n:integer;Type item=;Var buffer=array0,1,n-1 of item;In, out:0,1, n-1;Counter:0,1, n;Producer : repea

43、t produce an item in nextp; while counter=n do no-op; bufferin:=nextp; in:=(in+1) mod n; counter:=counter+1; until false;缓冲池满，缓冲池满，空操作，重空操作，重复测试复测试局部变量，局部变量，暂存刚生产暂存刚生产出的消息出的消息生产者进程往缓冲生产者进程往缓冲区投放消息，输入区投放消息，输入指针加指针加1缓 冲 区 消缓 冲 区 消息个数加息个数加1consumer: repeat while counter=0 do no-op; nextc :=bufferout; o

44、ut:=(out+1) mod n; counter:=counter-1; consume the item in nextc; until false;缓冲池空，空缓冲池空，空操作，重复测操作，重复测试试局部变量存放要消局部变量存放要消费的消息费的消息消费一消息，消费一消息，输出指针加输出指针加1消费者消费一消费者消费一消息消息这两个操作在用机器语言实现时常可用下面形式描述：这两个操作在用机器语言实现时常可用下面形式描述： register 1:=counter; register 1:=register 1+1; counter:=register 1; register 2:=coun

45、ter;register 2:=register 2-1;counter:=register 2;共享变量共享变量counter生产者进程生产者进程消费者进程消费者进程+1-1register 1=5register 1=6register 2=5register 2=4counter=6counter=4 程序的执行不具有可再现性。程序的执行不具有可再现性。 解决问题的关键解决问题的关键: 把变量把变量counter作为作为临界临界资源资源处理处理 。register 1:=counter; register 1:=register 1+1;register 2:=counter; regi

46、ster 2:=register 2-1;counter:=register 1; counter:=register 2; 我们把每个进程中访问临界资源的那段代码我们把每个进程中访问临界资源的那段代码(一段程序一段程序)称为称为临界区临界区。 若能保证诸进程互斥地进入自己的临界区，便若能保证诸进程互斥地进入自己的临界区，便可实现它们对临界资源的互斥访问。可实现它们对临界资源的互斥访问。 所谓所谓互斥互斥，就是一组并发进程中的一个或多个，就是一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一程序段，因共享某一公有资源而导致它们必须以一个个不允许交叉执行不允许交叉执行的单位执

47、行，即的单位执行，即不允许两个以上不允许两个以上的共享该资源的并发进程的共享该资源的并发进程同时进入临界区同时进入临界区。repeat entry section critical section exit section remainder sectionuntil false;进入区进入区临界区临界区退出区退出区剩余区剩余区4、同步机制应遵循的准则、同步机制应遵循的准则 (1)、空闲让进、空闲让进:当无进程在临界区时，任何有权使当无进程在临界区时，任何有权使用互斥区的进程可进入用互斥区的进程可进入(2)、忙则等待、忙则等待:不允许两个以上的进程同时进入临不允许两个以上的进程同时进入临界区界

48、区 (3)、有限等待、有限等待:任何进入临界区的要求应在有限的任何进入临界区的要求应在有限的时间内得到满足时间内得到满足(4)、让权等待、让权等待 :处于等待状态的进程应放弃占用处于等待状态的进程应放弃占用CPUCPU，以使其他进程有机会得到以使其他进程有机会得到CPUCPU的使用权的使用权两个进程两个进程Pi和和Pj共享一个临界资源共享一个临界资源R 。使使Pi和和Pj互斥访问资源互斥访问资源R的一般性描述：的一般性描述：Beginparbegin Pi; Pj;parendendRepeat while turnI do no_op; turn:=j;remainder sectionUn

49、til false;公用整型变量，表示被允许公用整型变量，表示被允许进入临界区的进程的编号。进入临界区的进程的编号。针对进程针对进程Pi能确保每次只允许一个能确保每次只允许一个进程进入临界区进程进入临界区Pi退出临界区将退出临界区将turn置置为为j，允许，允许Pj进入临界区；进入临界区；但但Pj不想进去，如果不想进去，如果Pi想访问临界区，无法进想访问临界区，无法进入。入。 while turnI do no_op;critical section 1. 不能保证实现不能保证实现“空闲让进空闲让进”的准则的准则1 2. 采取强制的方法让采取强制的方法让Pi和和Pj轮流访问临界资源，完全不考虑

50、它们的实轮流访问临界资源，完全不考虑它们的实际需要。际需要。初值为初值为false,表示进程未进表示进程未进入临界区；若入临界区；若flagI=true,表示表示Pi正在临界区内。正在临界区内。Var flag:array0,1,n of boolean Repeat while flagj do no_op;Flagi:=true;critical section Flagi:=false;remainder sectionUntil false;算法算法2解决了解决了“有空让进有空让进”违背违背“忙则等待忙则等待”、互斥的原、互斥的原则则Pi进入进入While发现发现Flagj=false

51、Pj进入进入While发现发现Flagi=falsePj置置 Flagj=true进入临界区进入临界区Pi 置置Flagi=true进入临界区进入临界区算法算法2的问题的问题 1. 不能保证实现不能保证实现“忙则等待忙则等待”的准则的准则, 不能保证互斥。不能保证互斥。 2. 当进程当进程Pi观察到观察到Pj的标志为的标志为false后，便将自己的标志由后，便将自己的标志由false改为改为true需一极短的时间，而在此期间，它仍表现为需一极短的时间，而在此期间，它仍表现为false而被而被Pj所观察到。所观察到。算法算法3Repeat while flagj do no_op;critica

52、l section Flagi:=false;remainder sectionUntil false;Flagi:=true;可以有效地防可以有效地防止两个进程同止两个进程同时进入临界区。时进入临界区。当当Pi和和Pj几乎是在同时想进入几乎是在同时想进入临界区，而分别把自己的标临界区，而分别把自己的标志置为志置为true，又都立即去检，又都立即去检查对方的标志，因而都发现查对方的标志，因而都发现对方也要进入临界区，于是对方也要进入临界区，于是双方都在谦让，造成死锁。双方都在谦让，造成死锁。算法算法3的问题的问题 1. 违背违背“有空让进有空让进”的准则的准则 2. 违背违背“有限等待有限等待

53、”的准则的准则Peterson算法算法Repeatcritical section Flagi:=false;remainder sectionUntil false;Flagi:=true; turn:=j;while (flagj and turn:=j) do no_op;软件解法的缺点：软件解法的缺点： 1. 1. 忙等待忙等待 2. 2. 实现过于复杂，需要高的编程技巧实现过于复杂，需要高的编程技巧硬件解法：硬件解法： 提供专门的硬件指令，允许对一个字的内容进行提供专门的硬件指令，允许对一个字的内容进行检测和修正，或交换两个字的内容检测和修正，或交换两个字的内容目的：解决共享变量的目

54、的：解决共享变量的完整性和正确性完整性和正确性 简单、有效，特别简单、有效，特别适用于多处理机适用于多处理机缺点：忙等待缺点：忙等待 boolean testset (int &i) boolean testset (int &i) if (i=0) if (i=0) i = 1; i = 1; return true; return true; else else return false;false; const int n= /const int n= /* *进程数进程数* */ /int bolt;int bolt;Void p(int i)Void p(int i)

55、 while(true) while(true) while(!testset(bolt) while(!testset(bolt) / /* *什么也不做什么也不做* */;/; / /* *临界区临界区* */ / bolt = 0; = 0; / /* *其余部分其余部分* */ / void mainvoid main（）（） bolt=0bolt=0； parbegin(p(1),p(2),p(n);parbegin(p(1),p(2),p(n); void exchange(int &register, int &memory)int temp;temp = mem

56、ory;memory = register;register = temp;/*使用指令的互斥进程使用指令的互斥进程* /const int n= /*进程数进程数*/int bolt;Void p(int i) int key;while(true) key=1; while(key!=0) exchange(key,bolt); /*临界区临界区*/ exchange(key,bolt); /*其余部分其余部分*/ void main（）（） bolt=0； parbegin(p(1),p(2),p(n); Intel x86 CPU在低层同步中使用在低层同步中使用XCHG指令。指令。en

57、ter_region: enter_region: MOVEREGISTER,#1|MOVEREGISTER,#1|在寄存器中放一个在寄存器中放一个1 1 XCHGREGISTER,LOCK|XCHGREGISTER,LOCK|交换寄存器与锁变量的内容交换寄存器与锁变量的内容 CMPREGISTER,#0|CMPREGISTER,#0|锁是零吗？锁是零吗？ JNEenter_region|JNEenter_region|若不是零，说明锁已被设置，因此循环若不是零，说明锁已被设置，因此循环 RET|RET|返回调用者，进入临界区返回调用者，进入临界区 leave_region: leave_re

58、gion: MOVELOCK,#0|MOVELOCK,#0|在锁中存入在锁中存入0 0 RET|RET|返回调用者返回调用者 进入临界区前执行：进入临界区前执行： 执行执行“关中断关中断”指令指令离开临界区后执行：离开临界区后执行： 执行执行“开中断开中断”指令指令l简单，有效简单，有效l较高的代价，限制较高的代价，限制CPUCPU并发能力（临界区小）并发能力（临界区小）l不适应多处理器不适应多处理器 1965年，由荷年，由荷兰学者兰学者Dijkstra提出提出（P、V分别是荷兰语分别是荷兰语的的test(proberen)和和increment(verhogen)一种卓有成效的进程同一种卓有

59、成效的进程同步机制。步机制。 最初提出的是二最初提出的是二元信号量（互斥）元信号量（互斥）, 推广到一般信号量推广到一般信号量（多值）（同步）。（多值）（同步）。Edsger W. Dijkstra 信号灯信号灯状态变化状态变化交通管理交通管理 在操作系统中，信号量是表示资源的物理实在操作系统中，信号量是表示资源的物理实体，是一个与队列有关的整型变量。操作系统利体，是一个与队列有关的整型变量。操作系统利用它的状态，实现对进程和资源进行管理。用它的状态，实现对进程和资源进行管理。 wait(s)：while S0 do no op P操作操作 S:=S-1; signal(s)： S:=S+1;

60、 V操作操作 必须置一次且只能置一次初值，初值不能为负必须置一次且只能置一次初值，初值不能为负数。数。 值的改变只能通过执行值的改变只能通过执行wait 、 signal操作。操作。一个用于表示资源数目一个用于表示资源数目的整型量的整型量S 原语：原语：primitive or atomic action 是由若干多机器指令构成的完成某种特定功能是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性的一段程序，具有不可分割性 即原语的执行必须是连续的，在执行过程中不即原语的执行必须是连续的，在执行过程中不允许被中断允许被中断 实现：开关中断实现：开关中断 wait(s)和和signal(s)是两个原子操作，因是