第二章_进程与并发控制(2)

1、2.1 前趋图和程序执行前趋图和程序执行2.2 进程的描述进程的描述2.3 进程控制进程控制2.4 进程同步进程同步2.5 经典进程的同步问题经典进程的同步问题2.6 进程通信进程通信2.7 线程的基本概念线程的基本概念2.8 线程的实现线程的实现2.1.1 前趋图前趋图 前趋图前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)“”。 =(P

2、i, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可写成PiPj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。 每个结点还具有一个重量每个结点还具有一个重量(Weight)，用于表示该结点，用于表示该结点所含有的程序量或结点的执行时间。所含有的程序量或结点的执行时间。 IiCiPi和和S1S2S3 图图 2-2 前趋图前趋图 P1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九个结点的前趋图(b) 具有循环的前趋图对于图 2-2(a)所示的前趋图， 存在下述前趋关系： P1P2, P1P3, P1P4, P2P5,

3、P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9或表示为： P=P1, P2, P3, P4, P5, P6, P7, P8, P9= (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9) 应当注意，但在图2-2(b)中却有着下述的前趋关系：S2S3, S3S2 1程序的顺序执行程序的顺序执行例子：S1：a： x+y；S2：b： a-5；S3：c： b+1；2 2程序顺序执行时的特征程序顺序执行时的特

4、征（1 1）顺序性）顺序性：处理机的操作严格按照程序所：处理机的操作严格按照程序所规定的顺序执行。规定的顺序执行。（2 2）封闭性）封闭性：程序运行时独占全机资源，程：程序运行时独占全机资源，程序一旦开始执行，其执行结果不受外界因序一旦开始执行，其执行结果不受外界因素影响。素影响。（3 3）可再现性）可再现性：只要程序执行时的环境和初：只要程序执行时的环境和初始条件相同，都将获得相同的结果。始条件相同，都将获得相同的结果。（不论它是从头到尾不停顿地执行，还是（不论它是从头到尾不停顿地执行，还是“停停走走停停走走”地执行）地执行）2.1.3 程序的并发执行程序的并发执行1. 程序的并发执行程序的

5、并发执行 图 2-3 并发执行时的前趋图 P1P2P3P4I1I2I3I4C1C2C3C4一个作业由输入程序、计算程序、打印程序组成。一个作业由输入程序、计算程序、打印程序组成。在该例中存在下述前趋关系：在该例中存在下述前趋关系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1而而Ii+1和和Ci及及Pi-1是重迭的，亦即在是重迭的，亦即在Pi-1和和Ci以及以及Ii+1之间，可之间，可以并发执行以并发执行。 对于具有下述四条语句的程序段：对于具有下述四条语句的程序段： S1: a =x+2 S2: b =y+4 S3: c =a+b S4: d =c+b 图 2-4 四条语

6、句的前趋关系S1S2S3S42. 程序并发执行时的特征程序并发执行时的特征 间断性间断性程序并发执行是，由于共享系统资源，这些程序程序并发执行是，由于共享系统资源，这些程序形成相互制约的关系，具有形成相互制约的关系，具有“执行执行-暂停暂停-执行执行”特征。特征。2) 失去封闭性失去封闭性 程序并发执行时，多个程序共享系统资源，因而程序并发执行时，多个程序共享系统资源，因而这些资源的状态将由多个程序来改变，从而导致这些资源的状态将由多个程序来改变，从而导致程序的运行失去封闭性。程序的运行失去封闭性。3) 不可再现性不可再现性 程序并发执行，由于失去了封闭性，从而也失去程序并发执行，由于失去了封

7、闭性，从而也失去了可再现性。了可再现性。 例如，有两个循环程序例如，有两个循环程序A和和B，它们共享一个变，它们共享一个变量量N。程序。程序A每执行一次时，都要做每执行一次时，都要做N =N+1操操作；程序作；程序B每执行一次时，每执行一次时， 都要执行都要执行Print(N)操操作，然后再将作，然后再将N置成置成“0”。程序。程序A和和B以不同的速以不同的速度运行。度运行。 2. 程序并发执行时的特征程序并发执行时的特征 1、N=N+1，在，在Print（N）和）和N=0之前执行，之前执行， 即执行次序：即执行次序： N=N+1 n+1 Print（N） n+1 N=0 02、N=N+1，在

8、，在Print和和N=0之后执行，之后执行， 即执行次序：即执行次序： Print（N） n N=0 0 N=N+1 13、N=N+1，在，在Print和和N=0之间执行，之间执行， 即执行次序：即执行次序： Print（N） n N=N+1 n+1N=0 0彩彩色色的的为为执执行行结结果果，各各不不相相同同作业1 在Linux操作系统中实现上页中例子，运行多次，每次的结果有什么不同？2.2.1 进程的定义和特征进程的定义和特征 1. 典型的进程定义有：典型的进程定义有：（1）进程是程序的一次执行。）进程是程序的一次执行。（2）进程是一个）进程是一个程序程序及其数据在处理机上顺及其数据在处理机

9、上顺序序执行执行时所发生的活动。时所发生的活动。（3）进程是程序在一个数据集合上运行的过）进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独程，它是系统进行资源分配和调度的一个独立单位。立单位。2. 进程的结构进程的结构为使程序（含数据）能独立运行，应为之为使程序（含数据）能独立运行，应为之配置一进程控制块，即配置一进程控制块，即PCB；而由而由程序段、程序段、相关的相关的数据段和数据段和PCB三部分三部分便构成了进程实体。便构成了进程实体。所谓创建进程，实质上是创建进程实体中所谓创建进程，实质上是创建进程实体中的的PCB；而撤消进程，实质上是撤消进程；而撤消进程，实质上

10、是撤消进程的的PCB。 三个进程同时驻留内存三个进程交替执行 进程A 调度程序 进程B 调度程序 进程C3. 进程的特征进程的特征 1）动态性）动态性 进程的实质是进程实体的一次执行过程，进程的实质是进程实体的一次执行过程，因此，因此，动态性动态性是进程的是进程的最基本最基本的特征。的特征。动态性表现：动态性表现：“它由创建而产生，由调度它由创建而产生，由调度而执行，由撤消而消亡而执行，由撤消而消亡”。可见，进程实。可见，进程实体有一定的生命期。体有一定的生命期。程序是一组有序指令的集合，其本身并不程序是一组有序指令的集合，其本身并不具有运动的含义，因而是静态的。具有运动的含义，因而是静态的。

11、 2）并发性）并发性 这是指多个进程实体同存于内存中，且能这是指多个进程实体同存于内存中，且能在一段时间内同时运行。在一段时间内同时运行。 3）独立性）独立性 指进程实体是一个能独立运行、独立分配指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位；资源和独立接受调度的基本单位； 4）异步性）异步性 指进程按各自独立的、不可预知的速度向指进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行。前推进，或说进程实体按异步方式运行。1. 进程的三种基本状态：进程的三种基本状态：1）就绪（）就绪（Ready）状态：）状态：当进程已分配到除当进程已分配到除CPU以外的所有必要

12、资源后，只要再获得以外的所有必要资源后，只要再获得CPU，便可，便可立即执行。立即执行。 2）执行状态：）执行状态：进程已获得进程已获得CPU，其程序正在执行。，其程序正在执行。 3）阻塞状态：）阻塞状态：正在执行的进程由于发生某事件而正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停暂时无法继续执行时，便放弃处理机而处于暂停状态，把这种暂停状态称为阻塞状态，有时也称状态，把这种暂停状态称为阻塞状态，有时也称为等待状态。根据阻塞原因，系统中设置多个阻为等待状态。根据阻塞原因，系统中设置多个阻塞队列。塞队列。就绪态就绪态运行态运行态等待态等待态调度调度被高优先级任被高优先级

13、任务抢占或超时务抢占或超时I/OI/O请求请求就绪态就绪态运行态运行态阻塞态阻塞态就绪态就绪态运行态运行态I/O完成完成三种基本状态的思考三种基本状态的思考进程主动完成状态转换，还是被动完成？进程主动完成状态转换，还是被动完成？进程状态是否唯一？进程状态是否唯一？时间片用完是否是进程由执行变为就绪的唯一时间片用完是否是进程由执行变为就绪的唯一原因？原因？在单处理机系统中，是否可以有多个进程同时在单处理机系统中，是否可以有多个进程同时处于执行状态？处于执行状态？在多处理机系统中，是否可以有多个进程同时在多处理机系统中，是否可以有多个进程同时处于执行状态？处于执行状态？3. 创建状态和终止状态创建

14、状态和终止状态1）创建状态）创建状态如果进程所需资源尚不能得到满足，如无足够的如果进程所需资源尚不能得到满足，如无足够的内存空间，创建工作将无法完成，进程不能被调内存空间，创建工作将无法完成，进程不能被调度，此时的进程状态为创建状态。度，此时的进程状态为创建状态。2）终止状态）终止状态一个进程到达了自然结束点，或者出现了无法克一个进程到达了自然结束点，或者出现了无法克服的错误，或是被操作系统所终结，或是被其他服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。有终止权的进程所终结，它将进入终止状态。挂起状态挂起状态使执行的进程暂停执行使执行的进程暂停执行,静止下来

15、静止下来,我们把我们把这种静止状态称为挂起状态。这种静止状态称为挂起状态。（1）终端用户的请求。（用户发现程序运行有问题，）终端用户的请求。（用户发现程序运行有问题，将其暂停）将其暂停）（2）父进程请求。）父进程请求。(挂起子进程，协调子进程的活动挂起子进程，协调子进程的活动) （3）负荷调节的需要。当实时系统中的工作负荷较）负荷调节的需要。当实时系统中的工作负荷较重，把一些不重要的进程挂起，以保证系统能正常重，把一些不重要的进程挂起，以保证系统能正常运行。运行。（4）操作系统的需要。操作系统有时希望挂起某些）操作系统的需要。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账

16、。进程，以便检查运行中的资源使用情况或进行记账。 图2-6 具有挂起状态的进程状态图挂起状态的思考挂起状态的思考就绪就绪/挂起和就绪状态的区别？挂起和就绪状态的区别？就绪就绪/挂起状态是否可以直接进入执行状挂起状态是否可以直接进入执行状态态?挂起状态是否可以进入执行状态挂起状态是否可以进入执行状态?挂起进程是否可以自我激活？挂起进程是否可以自我激活？2.2.4 进程管理中的数据结构进程管理中的数据结构1.进程控制块的作用进程控制块的作用独立运行基本单位的标志。独立运行基本单位的标志。能实现间断性运行方式。（保护能实现间断性运行方式。（保护CPUCPU现场）现场）提供进程管理所需要的信息。（提供

17、进程管理所需要的信息。（OSOS通过通过PCBPCB对进程对进程实施控制和管理。）实施控制和管理。）提供进程调度所需要的信息。（提供进程状态、优提供进程调度所需要的信息。（提供进程状态、优先级等信息）先级等信息）实现与其它进程的同步与通信。（消息队列指针，实现与其它进程的同步与通信。（消息队列指针，信号量等）信号量等）进程控制块的内容进程控制块的内容进程标识符信息进程标识符信息处理器状态信息处理器状态信息进程调度信息进程调度信息进程控制信息进程控制信息2.1.5 进程控制块进程控制块 1 1）进程标识符）进程标识符 进程标识符用于惟一地标识一个进程。一个进程标识符用于惟一地标识一个进程。一个进

18、程通常有两种标识符：进程通常有两种标识符：（1 1）内部标识符。内部标识符。为每一个进程赋予一个惟一为每一个进程赋予一个惟一的数字标识符，通常是进程的序号的数字标识符，通常是进程的序号(Pid)(Pid)。设置内部标识符主要是为了方便操作系统设置内部标识符主要是为了方便操作系统使用。使用。（2 2）外部标识符。外部标识符。它由创建者提供它由创建者提供( (进程的名进程的名字字) )，通常是由字母、数字组成，往往是由，通常是由字母、数字组成，往往是由用户（进程）在访问该进程时使用。用户（进程）在访问该进程时使用。处理机状态信息主要是由处理机的各种寄存处理机状态信息主要是由处理机的各种寄存器中的内

19、容组成的。器中的内容组成的。通用寄存器，通用寄存器，又称为用户可视寄存器。又称为用户可视寄存器。指令计数器（指令计数器（PCPC），其中存放了要访问的下一，其中存放了要访问的下一条指令的地址。条指令的地址。程序状态字程序状态字PSWPSW，其中含有状态信息，如条件，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等码、执行方式、中断屏蔽标志等用户栈指针用户栈指针(SP)(SP)，用于存放系统调用参数及调，用于存放系统调用参数及调用地址。栈指针指向该栈的栈顶。用地址。栈指针指向该栈的栈顶。这些都是中断和进程切换时需要保护的内容！这些都是中断和进程切换时需要保护的内容！在在PCBPCB中还存放一

20、些与进程调度和进程切换中还存放一些与进程调度和进程切换有关的信息。有关的信息。进程状态。指明进程的当前状态。进程状态。指明进程的当前状态。在在LinuxLinux操作系统中在操作系统中在sched.hsched.h中定义了进程的中定义了进程的6 6个个状态：状态：可运行状态可运行状态(TASK-RUNING);可中断阻塞状态可中断阻塞状态(TASK-UBERRUPTIBLE)不可中断阻塞状态不可中断阻塞状态(TASK-UNINTERRUPTIBLE)僵死状态僵死状态(TASK-ZOMBLE)暂停态暂停态(TASK_STOPPED)交换态交换态(TASK_SWAPPING)进程优先级。进程优先级

21、。进程调度所需的其它信息。进程调度所需的其它信息。如：进程已等如：进程已等待待CPUCPU的时间总和、进程已执行的时间总和的时间总和、进程已执行的时间总和等；等；事件。事件。是指进程由执行状态转变为阻塞状是指进程由执行状态转变为阻塞状态所等待发生的事件，即态所等待发生的事件，即阻塞原因阻塞原因。程序和数据的地址程序和数据的地址，是指进程的程序和数据所在的，是指进程的程序和数据所在的内存或外存地址。内存或外存地址。进程同步和通信机制进程同步和通信机制，指实现进程同步和通信时必，指实现进程同步和通信时必需的机制，如消息队列指针、信号量等，他们可能需的机制，如消息队列指针、信号量等，他们可能全部或部

22、分的放在全部或部分的放在PCB中。中。资源清单资源清单。进程所需的全部资源及已经分配到该进。进程所需的全部资源及已经分配到该进程的资源的清单；程的资源的清单；链接指针链接指针。本进程所在队列的下一个进程的。本进程所在队列的下一个进程的PCB的的首地址。首地址。 Linux进程控制块进程控制块Linux的进程控制块为一个由结构task_struct所定义的数据结构，task_struct存放在/include/linux/sched.h中。struct task_struct.unsigned short uid; /为用户标识int pid; /为进程标识int processor; /标识用

23、户正在使用的CPU,以支持多处理机方式.volatile long state; /进程的状态，有6种状态long prority; /进程的优先级unsighed long rt_prority; /表示实时进程的优先级，对于普通进程无效long counter; /为进程动态优先级计数器，用于进程轮转调度算法unsigned long flags;unsigned long policy; /表示进程调度策略，其值为下列三种情况之一：SCHED_OTHER(值为值为0)对应普通进程，优先级轮转法对应普通进程，优先级轮转法(round robin)SCHED_FIFO(值为值为1)对应实时进

24、程，先来先服务算法；对应实时进程，先来先服务算法；SCHED_RR(值为值为2)对应实时进程，时间片轮转算法对应实时进程，时间片轮转算法.Struct task_struct *next_task, *prev_task; /为进程PCB双向链表的前后项指针Struct task_struct *next_run,*prev_run; /为就绪队列双向链表的前后项指针 Struct task_struct *p_opptr,*p_pptr,*p_cptr,*pysptr,*p_ptr; /指明进程家族间的关系，分别为指向祖父进程、父进程、子进程以及新老进程的指针 .;typedef struc

25、t os_tcb OS_STK *OSTCBStkPtr; /* Pointer to current top of stack*/#if OS_TASK_CREATE_EXT_EN 0 void *OSTCBExtPtr; /* Pointer to user definable data for TCB extension */ OS_STK *OSTCBStkBottom; /* Pointer to bottom of stack */ INT32U OSTCBStkSize; /* Size of task stack (in number of stack elements) */

26、 INT16U OSTCBOpt; /* Task options as passed by OSTaskCreateExt() */ INT16U OSTCBId; /* Task ID (0.65535) */#endif struct os_tcb *OSTCBNext;/* Pointer to next TCB in the TCB list */ struct os_tcb *OSTCBPrev;/* Pointer to previous TCB in the TCB list*/#if (OS_VERSION = 251) & (OS_FLAG_EN 0) &

27、(OS_MAX_FLAGS 0)#if OS_TASK_DEL_EN 0 OS_FLAG_NODE *OSTCBFlagNode; /* Pointer to event flag node*/#endif OS_FLAGS OSTCBFlagsRdy; /* Event flags that made task ready to run*/ 使使进进程就程就绪绪的事件的事件#endif INT16U OSTCBDly; /* Nbr ticks to delay task or, timeout waiting for event*/ INT8U OSTCBStat;/* Task stat

28、us */ INT8U OSTCBPrio;/* Task priority (0 = highest, 63 = lowest) */ OS_TCB; 1）链接方式）链接方式 把具有同一状态的把具有同一状态的PCB，用其中的链接字，用其中的链接字链接成一个队列。链接成一个队列。 链接方式PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901执行指针就绪队列指针阻塞队列指针空闲队列指针2）索引方式）索引方式 相同状态进程的相同状态进程的PCB组织在一张表格中，系组织在一张表格中，系统根据所有进程的状态建立几张索引表，系统根据所有进程的状态建立几张索引表，系统分

29、别记载各统分别记载各PCB表格的起始地址。表格的起始地址。 索引方式3）多级队列：）多级队列：按照进程状态不同分别组织按照进程状态不同分别组织PCB队列，同一队列，同一状态进程状态进程PCB按照优先级高低（或者到达的按照优先级高低（或者到达的先后顺序）用链接指针连接起来。先后顺序）用链接指针连接起来。Linux操作系统中采用操作系统中采用task_struct来表示进来表示进程控制块。程控制块。Linux操作系统最多允许操作系统最多允许512个进程，采用结个进程，采用结构指针数组来表示。构指针数组来表示。定义格式：定义格式： struct task_struct *taskNR_TASKS;

30、其中，其中， NR_TASKS=512作业 2：阅读Linux 3.0以上 版本的内核代码中进程控制块和进程调度的代码，然后回答下面的问题：Linux的进程控制块的组织方式是什么？请问它里面设定了那些进程状态，这些状态代表什么意义？状态之间如何转换？并画出状态转换图。进程控制进程控制创建一个新进程，终止进程创建一个新进程，终止进程进程运行中的状态转换。进程运行中的状态转换。进程控制一般是由进程控制一般是由OS内核中的一组原语来实内核中的一组原语来实现的。现的。 什么是原语？什么是原语？原语是由若干条指令组成的，用于完成一定原语是由若干条指令组成的，用于完成一定功能的一个过程。是功能的一个过程。

31、是“原子操作原子操作”，即一个，即一个操作中的所有动作要么全做，要么全不做，操作中的所有动作要么全做，要么全不做，换言之，是换言之，是一个不可分割的基本单位一个不可分割的基本单位，在执，在执行过程中行过程中不允许被中断不允许被中断。 1进程图（进程图（Process Graph）进程图是用于描述一个进程的家族关系的有向树。进程图是用于描述一个进程的家族关系的有向树。子进程可以继承父进程所拥有的资源。子进程可以继承父进程所拥有的资源。当子进程被撤消时，应将其从父进程那里获得的当子进程被撤消时，应将其从父进程那里获得的资源归还给父进程。资源归还给父进程。 在撤消父进程时，也必须同时撤消其所有的子进

32、在撤消父进程时，也必须同时撤消其所有的子进程。程。 进程图导致一个进程去创建另一个进程的典型事件，导致一个进程去创建另一个进程的典型事件，可有以下四类：可有以下四类：（1 1）用户登录用户登录。分时系统中，用户通过终端登录成。分时系统中，用户通过终端登录成功后，系统将为用户建立一个进程。功后，系统将为用户建立一个进程。（2 2）作业调度作业调度。将作业调入内存后，创建进程。将作业调入内存后，创建进程。（3 3）提供服务提供服务。例如：。例如：I/OI/O请求，打印进程等。请求，打印进程等。（4 4）应用请求应用请求。基于应用进程的需求，由它自己创。基于应用进程的需求，由它自己创建一个新进程，以

33、便使新进程以并发运行方式完建一个新进程，以便使新进程以并发运行方式完成特定任务。成特定任务。调用进程创建原语步骤：调用进程创建原语步骤：（1）申请空白）申请空白PCB。 （2）为新进程分配资源。）为新进程分配资源。（3）初始化进程控制块。）初始化进程控制块。初始化标识信息。初始化标识信息。初始化处理机状态信息。使程序计数器指向程初始化处理机状态信息。使程序计数器指向程序的入口地址，使栈指针指向栈顶；序的入口地址，使栈指针指向栈顶；初始化处理机控制信息：进程的状态、优先级。初始化处理机控制信息：进程的状态、优先级。 （4）将新进程插入就绪队列，）将新进程插入就绪队列，启动调度启动调度。UNIX用

34、用fork()函数创建进程函数创建进程Fork():复制父进程全部资源。复制父进程全部资源。Clone():有选择的复制父进程的资源。有选择的复制父进程的资源。(带参数带参数)Vfork()：创建一个线程。复制除：创建一个线程。复制除tast_struct和系统和系统空间堆栈外的所有资源。空间堆栈外的所有资源。这三个系统调用这三个系统调用都是通过调用都是通过调用do_fork()实现实现，只是，只是参数不同。参数不同。申请空白申请空白PCB详细阐述：详细阐述：Do_fork() alloc_task_struct(void) _get_free_pages()申请两个页面，申请两个页面，其中控

35、制块占用其中控制块占用1.5K，其余空间为，其余空间为进程的内核栈空间。进程的内核栈空间。子进程从子进程从fork返回时，返回值为返回时，返回值为0；父进程从父进程从fork()返回时，返回值为子进返回时，返回值为子进程的程的id时，非时，非0。等待子进程执行结束。等待子进程执行结束。通过系统调用使子进程执通过系统调用使子进程执行某段可执行程序。行某段可执行程序。作业3：将上页中的例子在Linux操作系统中运行，并得出执行结果，学会 wait4函数和fork函数的功能和使用方法。学习 Linux系统调用wait3，wait4，waitpid的 功能和使用方法，他们都是指定要等待子进程结束，他们

36、有何区别？编程练习这3个函数的 使用。引起进程终止的事件引起进程终止的事件 1）正常结束。）正常结束。2）异常结束：）异常结束：越界错误。越界错误。保护错。保护错。非法指令。非法指令。特权指令错。特权指令错。运行超时。运行超时。等待超时。等待超时。算术运算错、被算术运算错、被0 0除：除：I/OI/O故障。故障。3）外界干预）外界干预 外界干预并非指在本进程运行中出现了外界干预并非指在本进程运行中出现了异常事件，而是指异常事件，而是指进程因外界的请求而终止运行进程因外界的请求而终止运行。操作员或操作系统干预。操作员或操作系统干预。 由于某种原因，例如，发生了死锁，由操作员或由于某种原因，例如，

37、发生了死锁，由操作员或操作系统终止该进程；操作系统终止该进程；父进程请求终止该进程；父进程请求终止该进程；当父进程终止时，当父进程终止时，OSOS也将他的所有子孙进程终止。也将他的所有子孙进程终止。（1）根据被终止进程的）根据被终止进程的PID找到它的找到它的PCB，从中读，从中读出该进程的状态。出该进程的状态。（2）若被终止进程正处于执行状态，应立即终止该）若被终止进程正处于执行状态，应立即终止该进程的执行，进程的执行，重新进行调度重新进行调度。（3）若该进程还有子孙进程，立即）若该进程还有子孙进程，立即将其所有子孙进将其所有子孙进程终止程终止。（4）将被终止进程所拥有的全部资源，）将被终止

38、进程所拥有的全部资源，归还给其父归还给其父进程，或者归还给系统进程，或者归还给系统。（5）将被终止进程的）将被终止进程的PCB从所在队列中移出。从所在队列中移出。 Linux中，系统调用中，系统调用exit（）结束进程。（）结束进程。1正常退出正常退出a. 在在main()函数中执行函数中执行return 。b.调用调用exit()函数函数c.调用调用_exit()函数函数2异常退出异常退出a.调用调用abort函数函数b.进程收到某个信号，而该信号使程序终止。进程收到某个信号，而该信号使程序终止。课后学习：课后学习： exit()、 _exit()、 return的区别及的区别及各自的使用方

39、法。各自的使用方法。引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件1 1）向系统请求共享资源失败。）向系统请求共享资源失败。2 2）等待某种操作的完成：如）等待某种操作的完成：如I/OI/O操作时进程进入操作时进程进入阻塞状态，阻塞状态，I/OI/O完成后，被中断处理程序唤醒。完成后，被中断处理程序唤醒。3 3）新数据尚未到达。处理数据的进程）新数据尚未到达。处理数据的进程A A阻塞，输阻塞，输入数据的进程入数据的进程B B完成后去唤醒完成后去唤醒A A。 4 4）无新工作可做）无新工作可做, , 如此时使用如此时使用sleepsleep（）进入休（）进入休眠眠 正在执行的进程，当发现上述某

40、事件时，正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用由于无法继续执行，于是进程便通过调用阻塞原语阻塞原语block把自己阻塞；把自己阻塞； 把进程控制块中的现行状态由把进程控制块中的现行状态由“执行执行”改改为阻塞，并将为阻塞，并将PCB插入阻塞队列；插入阻塞队列； 转调度程序进行转调度程序进行重新调度重新调度，将处理机分配，将处理机分配给另一就绪进程，并进行切换。给另一就绪进程，并进行切换。 当被阻塞进程所期待的事件出现时，则由当被阻塞进程所期待的事件出现时，则由有关进程（比如，用完并释放了该有关进程（比如，用完并释放了该I/O设设备的进程）调用唤醒原语备的进程）

41、调用唤醒原语wakeup( )，将，将等待该事件的进程唤醒。等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将进程从等待该事件的阻塞队列中移出，将其其PCB中的现行中的现行状态由阻塞改为就绪状态由阻塞改为就绪，然，然后再将该后再将该PCB插入到就绪队列插入到就绪队列中。中。 进程的挂起：进程的挂起：当出现了引起进程挂起的事件时（当出现了引起进程挂起的事件时（比如，用户比如，用户进程请求将自己挂起，或父进程请求将自己的进程请求将自己挂起，或父进程请求将自己的某个子进程挂起某个子进程挂起），系统将利用挂起原语，系统将利

42、用挂起原语suspend( )suspend( )将将指定进程挂起指定进程挂起或处于阻塞状态的或处于阻塞状态的进程挂起进程挂起。挂起原语的执行过程是：挂起原语的执行过程是：1、首先检查被挂起进程的状态，、首先检查被挂起进程的状态，若处于若处于活动就绪状态，便将其改为静止就绪活动就绪状态，便将其改为静止就绪；对于对于活动阻塞状态的进程，则将之改为静止阻塞活动阻塞状态的进程，则将之改为静止阻塞；2、然后将被挂起进程的、然后将被挂起进程的PCB复制到指定的内存区复制到指定的内存区域。域。INT8U OSTaskSuspend (INT8U prio) BOOLEAN self; OS_TCB *pt

43、cb; OS_ENTER_CRITICAL(); if (prio = OS_PRIO_SELF) /* See if suspend SELF */ prio = OSTCBCur-OSTCBPrio; self = TRUE; else if (prio = OSTCBCur-OSTCBPrio) /* See if suspending self */ self = TRUE; else self = FALSE; /* No suspending another task */ ptcb = OSTCBPrioTblprio; if (ptcb = (OS_TCB *)0) /* Ta

44、sk to suspend must exist */ OS_EXIT_CRITICAL(); return (OS_TASK_SUSPEND_PRIO); if (OSRdyTblptcb-OSTCBY &= ptcb-OSTCBBitX) = 0 x00) /* Make task not ready */ OSRdyGrp &= ptcb-OSTCBBitY; ptcb-OSTCBStat |= OS_STAT_SUSPEND; /* Status of task is SUSPENDED */ OS_EXIT_CRITICAL(); if (self = TRUE) /

45、* Context switch only if SELF */ OS_Sched(); return (OS_NO_ERR);当发生激活进程的事件时，例如，父进程或用户当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，系统将利用激活原语进程请求激活指定进程，系统将利用激活原语active( )将指定进程激活。将指定进程激活。系统利用激活原语系统利用激活原语active( )将指定进程激活：将指定进程激活：激活原语检查该进程的现行状态，若是静止就激活原语检查该进程的现行状态，若是静止就绪绪，便将之改为活动就绪；便将之改为活动就绪；若为静止阻塞，便将之改为活动阻塞。若为静止阻塞，便

46、将之改为活动阻塞。INT8U OSTaskResume (INT8U prio) OS_TCB *ptcb; OS_ENTER_CRITICAL(); ptcb = OSTCBPrioTblprio; if (ptcb = (OS_TCB *)0) /* Task to suspend must exist */ OS_EXIT_CRITICAL(); return (OS_TASK_RESUME_PRIO); if (ptcb-OSTCBStat & OS_STAT_SUSPEND) != OS_STAT_RDY) /* Task must be suspended */ if (p

47、tcb-OSTCBStat &= OS_STAT_SUSPEND) = OS_STAT_RDY) & /* Remove suspension*/ (ptcb-OSTCBDly = 0) /* Must not be delayed */ OSRdyGrp |= ptcb-OSTCBBitY; /* Make task ready to run */ OSRdyTblptcb-OSTCBY |= ptcb-OSTCBBitX; OS_EXIT_CRITICAL(); OS_Sched(); else OS_EXIT_CRITICAL(); return (OS_NO_ERR);

48、 OS_EXIT_CRITICAL(); return (OS_TASK_NOT_SUSPENDED);时机：假如采用的是抢占调度策略，则每当时机：假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，都应检查是否要有新进程进入就绪队列时，都应检查是否要进行重新调度。进行重新调度。创建、终止（自己）、挂起（自己）、激活、创建、终止（自己）、挂起（自己）、激活、阻塞、唤醒都可能会产生新的调度。阻塞、唤醒都可能会产生新的调度。 2.4.1 进程同步的基本概念进程同步的基本概念进程同步机制的主要任务，是对多个相关进进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸程在执行

49、次序上进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享进程之间能按照一定的规则（或时序）共享系统资源，并能很好的相互合作，从而使程系统资源，并能很好的相互合作，从而使程序的执行具有可再现性。序的执行具有可再现性。1）间接相互制约关系）间接相互制约关系 并发执行的进程在使并发执行的进程在使用共享资源时的关系，资源的互斥。用共享资源时的关系，资源的互斥。2）直接相互制约关系）直接相互制约关系 多个进程为完成同一多个进程为完成同一项任务而相互合作的关系。项任务而相互合作的关系。例例2 生产者生产者-消费者消费者有一群生产者进程在生产产品，并将这些产品提供给有一群生产者进程在生产产品，并

50、将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有并发执行，在两者之间设置了一个具有n个缓冲区的个缓冲区的缓冲池：缓冲池：l生产者进程将它所生产的产品放入一个缓冲区中；生产者进程将它所生产的产品放入一个缓冲区中； l消费者进程可从一个缓冲区中取走产品去消费。消费者进程可从一个缓冲区中取走产品去消费。它们之间必须保持同步原则：它们之间必须保持同步原则：不允许消费者进程到一不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓

51、冲区中投放产品装满产品且尚未被取走的缓冲区中投放产品。 用一个数组来表示上述的具有用一个数组来表示上述的具有n个个(0，1，n-1)缓冲区的缓冲池。缓冲区的缓冲池。设置两个指针：设置两个指针：指针指针in：指示下一个可投放产品的缓冲区，每当：指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，生产者进程生产并投放一个产品后，in指针加指针加1, 即即in =(in+1)mod n ；指针指针out：指示下一个可从中获取产品的缓冲区，：指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，每当消费者进程取走一个产品后，out指针加指针加1，即即out =(out+1) m

52、od n 。当当(in+1) mod n=out时表示缓冲池满；而时表示缓冲池满；而in=out则则表示缓冲池空。表示缓冲池空。生产者和消费者两进程共享下面的变量：生产者和消费者两进程共享下面的变量：Var n, integer;type item=;var buffer:array0, 1, , n-1 of item;in, out: 0, 1, , n-1;counter: 0, 1, , n; / 缓冲区中产品的个数，初始值为缓冲区中产品的个数，初始值为0 0 1 2 3 4 5 6 7 8 n-1：被占用单元：被占用单元：空闲单元：空闲单元inoutproducer: repeat

53、produce an item in nextp; while counter=n do no-op;bufferin = nextp;in =(in+1) mod n;counter = counter+1;until false;consumer: repeat while counter=0 do no-op; nextc =bufferout; out =(out+1) mod n;counter =counter-1;consumer the item in nextc; until false; 若并发执行时，就会出现差错，问题就在于这两个进若并发执行时，就会出现差错，问题就在于这

54、两个进程共享变量程共享变量counter。生产者对它做加。生产者对它做加1操作，消费者操作，消费者对它做减对它做减1操作，这两个操作在用机器语言实现时，操作，这两个操作在用机器语言实现时， 常可用下面的形式描述：常可用下面的形式描述： 生产者生产者 消费者消费者 register 1 = counter; register 2 = counter; register1 = register 1+1; register 2 = register 2-1; counter = register 1; counter =register 2; 假设：假设：counter的当前值是的当前值是5。无论生

55、产者先执行，还是消费者先执行，结果都是无论生产者先执行，还是消费者先执行，结果都是5.但是，如果按下述顺序执行：但是，如果按下述顺序执行： register 1 =counter; (register 1=5) register 1 =register 1+1; (register 1=6) register 2 =counter; (register 2=5) register 2 =register 2-1; (register 2=4) counter =register 1; (counter=6) counter =register 2; (counter=4)Counter的值最终

56、为的值最终为4。问题的原因是什么？该怎么办？问题的原因是什么？该怎么办？将将counter作为作为临界资源临界资源处理，使生产者和消费者互斥的访处理，使生产者和消费者互斥的访问该变量。问该变量。临界区临界区(critical section) 可把一个访问临界资源的循环进程描述如下：可把一个访问临界资源的循环进程描述如下：repeat critical section; remainder section;until false; entry sectionexit section(1) 空闲让进。空闲让进。如果临界区空闲，则只要有进程如果临界区空闲，则只要有进程申请就立即让其进入。申请就立即

57、让其进入。(2) 忙则等待。忙则等待。每次每次仅允许一个仅允许一个进程处于临界区。进程处于临界区。(3) 有限等待。有限等待。进程只能在临界区内逗留有限时进程只能在临界区内逗留有限时间，不得使其他进程在临界区外无限期等待。间，不得使其他进程在临界区外无限期等待。(4) 让权等待。让权等待。进入临界区的进程不能在临界区进入临界区的进程不能在临界区内长时间阻塞等待某事件，必须在一定期限内退内长时间阻塞等待某事件，必须在一定期限内退出临界区。出临界区。当前信号量机制已经广泛地应用于单处理当前信号量机制已经广泛地应用于单处理机和多处理机以及计算机网络中。机和多处理机以及计算机网络中。按照信号量机制的发

58、展分为：按照信号量机制的发展分为：整形信号量整形信号量记录型信号量记录型信号量AND型信号量型信号量信号量集信号量集整型信号量整型信号量 :定义为一个整型量定义为一个整型量 ,仅能通过两仅能通过两个标准的原子操作个标准的原子操作 wait（S）和）和signal（S）来访问。又称为）来访问。又称为P、V操作。操作。 wait（S）：）： while S=0 do no-op S：=S-； signal（S）：）： S：=S+； 空操作1. 整型信号量整型信号量2记录型信号量记录型信号量 记录型信号量机制，则是一种记录型信号量机制，则是一种不存在不存在“忙等忙等”现象现象的的进程同步机制。进程同

59、步机制。记录型信号量的数据结构记录型信号量的数据结构: typedef strust int value； / value的初值表示系统中某类资源的数目，的初值表示系统中某类资源的数目， value的初始值的初始值1时，称为资源信号量，时，称为资源信号量， value的初始值的初始值=1时时，称为互斥信号量，称为互斥信号量 struct process_control_block *list；/信号量的信号量的阻塞队列阻塞队列 semaphore; wait（semaphore * S ） S-value-; if (S- value0) block（S-list）; /该该 signal(s

60、emaphore * S) S- valueS- value S- valueS- value S- valueS- value S- value S- value S- value Linux中使用信号量实现进程间对共享资源的中使用信号量实现进程间对共享资源的互斥访问，互斥访问，Down()和和Up函数对应于函数对应于P、V操作。操作。等待的进程数等待的进程数信号量的值信号量的值等待队列等待队列void OSSemPend (OS_EVENT *pevent, INT16U timeout, INT8U *err)if (pevent-OSEventCnt 0) /信号量值大于信号量值大于0，成功获得信号量并返回，成功获得信号量并返回pevent-OSEv