第二章-进程线程管理课件.ppt

1、第二章第二章 进程线程管理进程线程管理23本章内容本章内容2.1 进程的基本概念进程的基本概念2.2 进程控制进程控制2.3 进程同步进程同步2.4 进程通信进程通信2.5 线程线程42.1 进程的基本概念进程的基本概念2.1.1 程序执行过程程序执行过程1前趋图前趋图52.1进程的基本概念进程的基本概念2顺序执行及其特征顺序执行及其特征 程序顺序执行具有如下特征。程序顺序执行具有如下特征。（1）顺序性。处理机的操作严格按照程序所规定的顺序执行）顺序性。处理机的操作严格按照程序所规定的顺序执行,每每一操作必须在上一操作结束之后才能开始。一操作必须在上一操作结束之后才能开始。（2）封闭性。程序在

2、封闭环境下运行，独占系统所有资源。即）封闭性。程序在封闭环境下运行，独占系统所有资源。即程序一旦开始运行，其执行结果不受其它程序和外界因素影响。程序一旦开始运行，其执行结果不受其它程序和外界因素影响。（3）可再现性。只要程序执行时的初始条件和执行环境相同）可再现性。只要程序执行时的初始条件和执行环境相同,程程序重复执行时获得完全相同结果。序重复执行时获得完全相同结果。62.1进程的基本概念进程的基本概念3并发执行及其特征并发执行及其特征 72.1 进程的基本概念进程的基本概念 并发执行的多个程序的特征：并发执行的多个程序的特征：（1 1）间断性。程序在执行过程中，由于等待资源或及）间断性。程序

3、在执行过程中，由于等待资源或及其它程序协作完成任务，每个程序的执行过程往往不其它程序协作完成任务，每个程序的执行过程往往不是是“一气呵成一气呵成”，而是呈现出，而是呈现出“执行暂停执行执行暂停执行”的间断性活动规律。的间断性活动规律。（2 2）失去封闭性。程序并发执行时）失去封闭性。程序并发执行时,多个程序共享系多个程序共享系统资源统资源,系统资源的状态将由多个程序改变。即一个程系统资源的状态将由多个程序改变。即一个程序在运行时，其运行环境会受其它程序的影响，失去序在运行时，其运行环境会受其它程序的影响，失去了顺序执行的封闭性。了顺序执行的封闭性。82.1 进程的基本概念进程的基本概念 （3）

4、相互作用和制约性。并发执行程序既有相互独立）相互作用和制约性。并发执行程序既有相互独立的一面，表现为每个程序为用户提供特定的功能，它的一面，表现为每个程序为用户提供特定的功能，它们之间相互独立；也有时也会直接或间接制约的一面。们之间相互独立；也有时也会直接或间接制约的一面。（4）不可再现性。程序并发执行时）不可再现性。程序并发执行时,由于失去了封闭性由于失去了封闭性,导致其失去可再现性。即使初始条件相同，程序多次导致其失去可再现性。即使初始条件相同，程序多次执行的结果也可能不同。执行的结果也可能不同。92.1 进程的基本概念进程的基本概念例例1：有两个循环程序：有两个循环程序A和和B，它们共享

5、一个变量，它们共享一个变量N。程序。程序A每执行一次时，都要做每执行一次时，都要做N =N+1操作；操作；程序程序B每执行一次时，每执行一次时，都要执行都要执行Print(N)操作，然操作，然后再将后再将N置成置成“0”。程序。程序A和和B以不同的速度运行以不同的速度运行。(1)N =N+1在在Print(N)和和N =0之前，此时得到的之前，此时得到的N值分别为值分别为n+1,n+1,0。(2)N =N+1在在Print(N)和和N =0之后，此时得到的之后，此时得到的N值分别为值分别为n,0,1。(3)N =N+1在在Print(N)和和N =0之间，此时得到的之间，此时得到的N值分别为值

6、分别为n,n+1,0。102.1 进程的基本概念进程的基本概念例例2：假设某飞机定票系统在：假设某飞机定票系统在t0时刻有时刻有A、B、C、D四个终端程序同时都要对机票库中的某航班当前四个终端程序同时都要对机票库中的某航班当前剩余票数剩余票数X进行操作。如果每个终端程序的当前进行操作。如果每个终端程序的当前定票需求为定票需求为N，并对共享变量，并对共享变量X进行如下操作：进行如下操作：在机票数据库中取出当前剩余票数在机票数据库中取出当前剩余票数X；判断判断X0（有票吗）？（有票吗）？如果有，如果有，XN（票够吗）？（票够吗）？如果够，则出票（打印票据）；如果够，则出票（打印票据）；XXN（修改

7、剩余票数）；（修改剩余票数）；将将X回写到数据库中；回写到数据库中；112.1.2 进程的定义和特征进程的定义和特征 1.为何引入进程为何引入进程 从程序并发执行角度和系统资源共享角度从程序并发执行角度和系统资源共享角度分析一下引入进程的必要性。分析一下引入进程的必要性。（1）程序并发）程序并发执行执行角度角度（2）系统资源共享角度）系统资源共享角度122.1.2 进程的定义和特征进程的定义和特征 2.进程的定义进程的定义v进程是一个可并发执行的具有独立功能的程进程是一个可并发执行的具有独立功能的程序在某个数据集合的一次执行过程，它也是序在某个数据集合的一次执行过程，它也是操作系统进行资源分配

8、和保护的基本单位。操作系统进行资源分配和保护的基本单位。v为了更好的描述和管理并发执行的多个进程为了更好的描述和管理并发执行的多个进程，操作系统中为每个进程配置了一个进程控，操作系统中为每个进程配置了一个进程控制块制块PCB（Process Control Block）。）。132.1.2 进程的定义和特征进程的定义和特征 3.进程的构成进程的构成v进程包括程序，数据和进程包括程序，数据和PCB142.1.2 进程的定义和特征进程的定义和特征 4.进程的上下文进程的上下文v进程的物理实体和支持进程运行的环境合称为进程进程的物理实体和支持进程运行的环境合称为进程上下文（上下文（Process C

9、ontext）。进程在进程上下文中）。进程在进程上下文中执行。进程上下文包括用户级上下文、系统级上下执行。进程上下文包括用户级上下文、系统级上下文和寄存器上下文。文和寄存器上下文。v当一个进程被系统调度而占用处理机时，发生进程当一个进程被系统调度而占用处理机时，发生进程切换，切换的内容主要是进程上下文。切换，切换的内容主要是进程上下文。152.1.2 进程的定义和特征进程的定义和特征 5.进程的特征进程的特征v进程具有如下特征：进程具有如下特征：（1）动态性）动态性（2）共享性）共享性（3）并发性）并发性（4）独立性）独立性（5）异步性）异步性162.1.2 进程的定义和特征进程的定义和特征6

10、.进程和程序的区别进程和程序的区别 进程和程序的最大区别就是进程是程序的一次执行过程，它是进程和程序的最大区别就是进程是程序的一次执行过程，它是一个动态概念。程序是一个静态概念。一个动态概念。程序是一个静态概念。进程能够并发执行。进程能够并发执行。进程是资源分配和独立运行的基本单位，而程序不是。进程是资源分配和独立运行的基本单位，而程序不是。进程由含有代码和数据的用户地址空间、进程控制块和执行栈进程由含有代码和数据的用户地址空间、进程控制块和执行栈区等部分组成，而程序只是静态代码。区等部分组成，而程序只是静态代码。进程和程序之间是多对多的关系。一个程序可被多个进程共用进程和程序之间是多对多的关

11、系。一个程序可被多个进程共用，一个进程在其活动中又可调用若干个程序。，一个进程在其活动中又可调用若干个程序。172.1.3 进程状态和进程转换进程状态和进程转换1.进程的进程的3种基本状态种基本状态v进程执行时的间断性决定了进程可能具有多种状进程执行时的间断性决定了进程可能具有多种状态。事实上，运行中的进程可能具有以下三种态。事实上，运行中的进程可能具有以下三种基基本本状态。状态。182.1.3 进程状态和进程转换进程状态和进程转换1)就绪就绪(Ready)状态状态v当进程已分配到除当进程已分配到除CPU以外的所有必要资源后，以外的所有必要资源后，只要再获得只要再获得CPU，便可立即执行，进程

12、这时的状，便可立即执行，进程这时的状态称为就绪状态。在一个系统中处于就绪状态的态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称进程可能有多个，通常将它们排成一个队列，称为就绪队列。为就绪队列。2)执行状态执行状态v进程已获得进程已获得CPU，其程序正在执行。在单处理机，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态；系统中，只有一个进程处于执行状态；在多处理在多处理机系统中，则有多个进程处于执行状态。机系统中，则有多个进程处于执行状态。192.1.3 进程状态和进程转换进程状态和进程转换3)阻塞状态阻塞状态v正在执行的进程由于发生某事件而暂时无法

13、继续正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状程的执行受到阻塞，把这种暂停状态称为阻塞状态，有时也称为等待状态或封锁状态。态，有时也称为等待状态或封锁状态。v致使进程阻塞的典型事件有：请求致使进程阻塞的典型事件有：请求I/O，申请缓冲，申请缓冲空间等。通常将这种处于阻塞状态的进程也排成空间等。通常将这种处于阻塞状态的进程也排成一个队列。有的系统则根据阻塞原因的不同而把一个队列。有的系统则根据阻塞原因的不同而把处于阻塞状态的进程排成多个队列。处于阻塞状态的进程排成多个队列

14、。202.1.3 进程状态和进程转换进程状态和进程转换执行执行 就绪就绪 阻塞阻塞时间片到时间片到进程调度进程调度I/O请求请求I/O完成完成212.1.3 进程状态和进程转换进程状态和进程转换2.创建和终止状态创建和终止状态 222.1.3 进程状态和进程转换进程状态和进程转换3.挂起挂起1)引入挂起的原因引入挂起的原因v在不少系统中进程只有上述三种状态，但在不少系统中进程只有上述三种状态，但在另一些系统中，又增加了一些新状态，在另一些系统中，又增加了一些新状态，最重要的是挂起状态。引入挂起状态的原最重要的是挂起状态。引入挂起状态的原因有：因有：(1)终端用户的请求终端用户的请求(2)父进程

15、请求父进程请求(3)负荷调节的需要负荷调节的需要(4)操作系统的需要操作系统的需要232.1.3 进程状态和进程转换进程状态和进程转换2)进程状态的转换进程状态的转换v在引入挂起状态后，又将增加从挂起状态在引入挂起状态后，又将增加从挂起状态(又称为又称为静止状态静止状态)到非挂起状态到非挂起状态(又称为活动状态又称为活动状态)的转换的转换；或者相反。此时把状态细分为：；或者相反。此时把状态细分为：运行态运行态 活动就绪、静止就绪活动就绪、静止就绪 活动阻塞、静止阻塞活动阻塞、静止阻塞v可有以下几种状态转换情况：可有以下几种状态转换情况：(1)活动就绪活动就绪静止就绪。当进程处于未被挂起的就绪状

16、静止就绪。当进程处于未被挂起的就绪状态时，称此为活动就绪状态，表示为态时，称此为活动就绪状态，表示为Readya。当用挂。当用挂起原语起原语Suspend将该进程挂起后，该进程便转变为静止将该进程挂起后，该进程便转变为静止就绪状态，表示为就绪状态，表示为Readys，处于，处于Readys状态的进程不状态的进程不再被调度执行。再被调度执行。242.1.3 进程状态和进程转换进程状态和进程转换(2)活动阻塞活动阻塞静止阻塞。当进程处于未被挂起的阻静止阻塞。当进程处于未被挂起的阻塞状态时，称它是处于活动阻塞状态，表示为塞状态时，称它是处于活动阻塞状态，表示为Blockeda。当用。当用Suspen

17、d原语将它挂起后，进程便原语将它挂起后，进程便转变为静止阻塞状态，表示为转变为静止阻塞状态，表示为Blockeds。处于该状。处于该状态的进程在其所期待的事件出现后，将从静止阻塞态的进程在其所期待的事件出现后，将从静止阻塞变为静止就绪。变为静止就绪。(3)静止就绪静止就绪活动就绪。处于活动就绪。处于Readys状态的进程，状态的进程，若用激活原语若用激活原语Active激活后，该进程将转变为激活后，该进程将转变为Readya状态。状态。(4)静止阻塞静止阻塞活动阻塞。处于活动阻塞。处于Blockeds状态的进程，状态的进程，若用激活原语若用激活原语Active激活后，该进程将转变为激活后，该进

18、程将转变为Blockeda状态。下图示出了具有挂起状态的进程状状态。下图示出了具有挂起状态的进程状态图。态图。252.1.3 进程状态和进程转换进程状态和进程转换3.挂起操作挂起操作 执行执行活动活动就绪就绪活动活动阻塞阻塞时间片到时间片到进程调度进程调度I/O请求请求I/O完成完成内存内存外存外存静止静止就绪就绪静止静止阻塞阻塞I/O完成完成挂起挂起挂起挂起激活激活激活激活262.1.4 进程控制块及其组织方式进程控制块及其组织方式 1.进程控制块的作用进程控制块的作用进程控制块的具体作用如下：进程控制块的具体作用如下：（1）PCB是进程在系统中存在的唯一标识。是进程在系统中存在的唯一标识。

19、（2）保存）保存CPU现场信息。现场信息。（3）提供进程管理所需信息。）提供进程管理所需信息。（4）提供进程调度所需信息。）提供进程调度所需信息。（5）实现及其它进程的同步和通信。）实现及其它进程的同步和通信。272.1.4 进程控制块及其组织方式进程控制块及其组织方式 2.进程控制块的信息进程控制块的信息 进程控制块包含下述进程控制块包含下述4类类信信息：息：（1）进程标识信息进程标识信息。（2）进程说明信息。）进程说明信息。（3）处理机状态信息。）处理机状态信息。（4）进程的控制信息。）进程的控制信息。282.1.4 进程控制块及其组织方式进程控制块及其组织方式 3.进程控制块的组织方式进

20、程控制块的组织方式常用的常用的PCB组织方式有以下三种：组织方式有以下三种：（1）线性方式）线性方式（2）链接方式。）链接方式。292.1.4 进程控制块及其组织方式进程控制块及其组织方式 3.进程控制块的组织方式进程控制块的组织方式（3）索引方式）索引方式30重点回顾重点回顾v进程的定义和特征进程的定义和特征v进程状态进程状态 就绪就绪(Ready)(Ready)状态状态 执行状态执行状态 阻塞状态阻塞状态 挂起挂起31执行执行重点回顾重点回顾 就绪就绪 阻塞阻塞时间片到时间片到进程调度进程调度I/O请求请求I/O完成完成32重点回顾重点回顾执行执行活动活动就绪就绪活动活动阻塞阻塞时间片到时

21、间片到进程调度进程调度I/O请求请求I/O完成完成内存内存外存外存静止静止就绪就绪静止静止阻塞阻塞I/O完成完成挂起挂起挂起挂起激活激活激活激活332.2 进程控制进程控制2.2.1 进程创建进程创建系统中导致创建新进程的典型事件：系统中导致创建新进程的典型事件：操作系统初始化。当操作系统启动时，通常会创建若干进操作系统初始化。当操作系统启动时，通常会创建若干进程，特别是创建一些常驻系统进程。程，特别是创建一些常驻系统进程。作业调度。多道批处理系统中，当作业调度程序选中某个作业调度。多道批处理系统中，当作业调度程序选中某个作业时，将其装入内存，为其创建进程，并把创建好的进作业时，将其装入内存，

22、为其创建进程，并把创建好的进程插入到就绪进程队列。程插入到就绪进程队列。提供服务。当某一进程向操作系统提出某种服务请求时，提供服务。当某一进程向操作系统提出某种服务请求时，系统将专门创建一个进程来提供其所要求的服务。系统将专门创建一个进程来提供其所要求的服务。应用请求。当用户向系统提出某种应用请求时，系统为其应用请求。当用户向系统提出某种应用请求时，系统为其创建新进程。创建新进程。342.2.1 进程创建进程创建进程的创建进程的创建(Creation of Process)过程过程v一旦操作系统发现了要求创建新进程的事件后，一旦操作系统发现了要求创建新进程的事件后，便调用进程创建原语便调用进程

23、创建原语Creat()按下述步骤创建一个按下述步骤创建一个新进程。新进程。(1)申请空白申请空白PCB。为新进程申请获得惟一的数字标。为新进程申请获得惟一的数字标识符，并从识符，并从PCB集合中索取一个空白集合中索取一个空白PCB。(2)为新进程分配资源为新进程分配资源。为新进程的程序和数据，以。为新进程的程序和数据，以及用户栈分配必要的内存空间。及用户栈分配必要的内存空间。(3)初始化进程控制块初始化进程控制块。(4)将新将新进程插入就绪队列进程插入就绪队列，如果进程就绪队列能够，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。接纳新进程，便将新进程插入就绪队列。35入口入口图图 创

24、建原语流图创建原语流图362.2.2 进程执行及进程切换进程执行及进程切换v系统进行进程切换时通常进行如下工作：系统进行进程切换时通常进行如下工作：保存被中断进程的处理器现场信息；保存被中断进程的处理器现场信息；修改当前运行进程的修改当前运行进程的PCB，将运行状态改为其他，将运行状态改为其他状态，并把它插入到相应的状态，并把它插入到相应的PCB队列中；队列中；选择另一个进程运行，并修改该进程的选择另一个进程运行，并修改该进程的PCB，使，使其状态变为运行态；其状态变为运行态；将当前进程存储管理数据修改为新选进程的存储将当前进程存储管理数据修改为新选进程的存储管理数据；管理数据；恢复被选进程上

25、次切换出处理机时的处理机现场，恢复被选进程上次切换出处理机时的处理机现场，开始运行该进程。开始运行该进程。371、引起进程阻塞和唤醒的事件、引起进程阻塞和唤醒的事件请求系统服务：请求系统服务：正在执行的程序请求操作系统服务，但正在执行的程序请求操作系统服务，但是由于某种原因操作系统没有立即满足该进程的要求，是由于某种原因操作系统没有立即满足该进程的要求，该进程只能转变为阻塞状态来等待。该进程只能转变为阻塞状态来等待。启动某操作：启动某操作：当进程启动某种操作后，如果该进程必须当进程启动某种操作后，如果该进程必须在该操作完成之后才能继续执行，所有必须先使进程阻在该操作完成之后才能继续执行，所有必

26、须先使进程阻塞。塞。新数据尚未到达新数据尚未到达无新工作可做：无新工作可做：系统往往设置一些具有某特定功能的系系统往往设置一些具有某特定功能的系统进程，每当这种进程完成任务以后便把自己阻塞起来统进程，每当这种进程完成任务以后便把自己阻塞起来等待新任务的到来。（发送进程）等待新任务的到来。（发送进程）2.2.3 进程的阻塞及唤醒进程的阻塞及唤醒382、进程阻塞过程、进程阻塞过程 当有阻塞事件发生时，进程便调用阻塞原语当有阻塞事件发生时，进程便调用阻塞原语block()把把自己自己阻塞。进入阻塞。进入block后，应先立即停止执后，应先立即停止执行，把进程控制块中的执行状态改为阻塞状态，并行，把进

27、程控制块中的执行状态改为阻塞状态，并把它插入阻塞队列。把它插入阻塞队列。3、进程唤醒过程、进程唤醒过程 当阻塞进程所期待的事件出现时，则调用唤醒原当阻塞进程所期待的事件出现时，则调用唤醒原语语wakeup()，将等待事件的进程唤醒。，将等待事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞进程从唤醒原语执行的过程是：首先把被阻塞进程从等待该事件的阻塞队列中移出，将其等待该事件的阻塞队列中移出，将其PCB中的阻塞中的阻塞状态改为就绪状态，然后把该进程插入到就绪队列状态改为就绪状态，然后把该进程插入到就绪队列中。中。block()和和wakeup()是一对作用刚好相反的原是一对作用刚好相反的原语。

28、语。2.2.3 进程的阻塞及唤醒进程的阻塞及唤醒39入口入口图图 阻塞原语阻塞原语入口入口图图 唤醒原语唤醒原语402.2.4 进程挂起及激活进程挂起及激活1、进程的挂起、进程的挂起 当出现了引起进程挂起的事件时，比如，用户进程当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子请求将自己挂起，或父进程请求将自己的某个子进程挂起，系统将利用挂起原语进程挂起，系统将利用挂起原语suspend()将指定将指定进程或处于阻塞状态的进程挂起。进程或处于阻塞状态的进程挂起。v挂起原语的执行过程是：挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便首先

29、检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。对于活动阻塞状态的进程，则将之改为静止阻塞。最后，若被挂起的进程正在执行，则转向调度程序重新最后，若被挂起的进程正在执行，则转向调度程序重新调度。调度。412.2.4 进程挂起及激活进程挂起及激活2进程的激活过程进程的激活过程v当发生激活进程的事件时，例如，父进程或用户进当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就中已有足够的空间时，则可将在

30、外存上处于静止就绪状态的该进程换入内存。这时，系统将利用激活绪状态的该进程换入内存。这时，系统将利用激活原语原语active()将指定进程激活。将指定进程激活。v激活原语的执行过程是：激活原语的执行过程是：先将进程从外存调入内存，检查该进程的现行状态，若先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；是静止就绪，便将之改为活动就绪；若为静止阻塞，便将之改为活动阻塞。若为静止阻塞，便将之改为活动阻塞。422.2.5 进程撤销进程撤销1引起进程撤销的事件引起进程撤销的事件 正常结束正常结束：计算机系统中，都有一个表示进程已：计算机系统中，都有一个表示进程已经运行完成

31、的指示。（批处理，经运行完成的指示。（批处理，Holt。分时系统。分时系统中，中，Logs Off）异常结束：异常结束：越界错误、保护错、特权指令错、越界错误、保护错、特权指令错、非法指令错、非法指令错、运行超时、运行超时、等待超时、算术运算等待超时、算术运算错、错、I/O故障故障外界干预：外界干预：操作员或操作系统干预、父进程请求操作员或操作系统干预、父进程请求、父进程终止、父进程终止2进程的撤销过程进程的撤销过程43入口入口图图 终止原语流图终止原语流图442.3 进程同步进程同步2.3.1 进程同步的基本概念进程同步的基本概念1进程同步的两种制约关系进程同步的两种制约关系在多道程序环境下

32、，当程序并发执行时，由于资源共在多道程序环境下，当程序并发执行时，由于资源共享和进程合作，使同处于一个系统中的诸进程之间享和进程合作，使同处于一个系统中的诸进程之间可能存在着以下两种形式的制约关系。可能存在着以下两种形式的制约关系。(1)间接制约间接制约(进程互斥进程互斥)：源于资源共享。：源于资源共享。(2)直接制约直接制约(进程同步进程同步)：主要源于进程间的合作。：主要源于进程间的合作。重点重点452.3.1 进程同步的基本概念进程同步的基本概念 同步及互斥的比较同步及互斥的比较同步同步互斥互斥进程及进程之间有序合作进程及进程之间有序合作进程及进程之间共享临界资源进程及进程之间共享临界资

33、源相互清楚对方的存在及其作用相互清楚对方的存在及其作用，直接合作，直接合作不清楚对方的情况，只是共享不清楚对方的情况，只是共享同一临界资源同一临界资源 多个进程合作完成一个任务多个进程合作完成一个任务各个进程之间没有任何合作工各个进程之间没有任何合作工作作例如：发送消息进程和接受消例如：发送消息进程和接受消息进程之间；输入进程、计算息进程之间；输入进程、计算进程和输出进程之间等。进程和输出进程之间等。例如：共享打印机的若干进程例如：共享打印机的若干进程之间；共享同一全局变量的若之间；共享同一全局变量的若干进程之间等。干进程之间等。462.3.1 进程同步的基本概念进程同步的基本概念2临界资源及

34、临界区临界资源及临界区v临界资源临界资源也称独占资源，是指某段时间内只允许一也称独占资源，是指某段时间内只允许一个进程使用的资源。比如打印机等硬件资源，以及个进程使用的资源。比如打印机等硬件资源，以及只能互斥使用的变量、表格、队列等软件资源。只能互斥使用的变量、表格、队列等软件资源。v临界资源的使用只能采用临界资源的使用只能采用互斥方式互斥方式。当一个进程正。当一个进程正在使用某个临界资源且尚未使用完毕时，其它进程在使用某个临界资源且尚未使用完毕时，其它进程必须阻塞等待。只有当使用该资源的进程释放该资必须阻塞等待。只有当使用该资源的进程释放该资源时，其它进程才可使用。任何进程不能在其他进源时，

35、其它进程才可使用。任何进程不能在其他进程没有使用完临界资源时使用该资源，否则将会导程没有使用完临界资源时使用该资源，否则将会导致错误。致错误。v各个进程中访问临界资源的、必须互斥执行的程序各个进程中访问临界资源的、必须互斥执行的程序代码段称为代码段称为临界区临界区。472.3.1 进程同步的基本概念进程同步的基本概念2临界资源及临界区临界资源及临界区482.3.1 进程同步的基本概念进程同步的基本概念3同步机制应遵循的准则同步机制应遵循的准则 空闲让进。当无进程处于某临界资源对应的临界区时，表空闲让进。当无进程处于某临界资源对应的临界区时，表明该临界资源处于空闲状态，应充许一个请求进入临界区明

36、该临界资源处于空闲状态，应充许一个请求进入临界区的进程立即进入临界区。的进程立即进入临界区。忙则等待。当有进程已进入某临界资源对应的临界区时，忙则等待。当有进程已进入某临界资源对应的临界区时，表明该临界资源正在被使用，因而其它试图进入该临界资表明该临界资源正在被使用，因而其它试图进入该临界资源对应临界区的进程必须在进入区代码处等待。源对应临界区的进程必须在进入区代码处等待。有限等待。对要求访问临界资源的进程应保证其在有限时有限等待。对要求访问临界资源的进程应保证其在有限时间内能进入自己的临界区，以免陷入间内能进入自己的临界区，以免陷入“死等死等”状态。状态。让权等待。当进程不能进入自己的临界区

37、时，应立即阻塞让权等待。当进程不能进入自己的临界区时，应立即阻塞自己并释放处理机，以免进程陷入自己并释放处理机，以免进程陷入“忙等忙等”状态。状态。492.3.1 进程同步的基本概念进程同步的基本概念4实现临界区互斥的基本方法实现临界区互斥的基本方法（1）软件实现方法）软件实现方法v软件方法是指编程人员编写程序时在临界区前面软件方法是指编程人员编写程序时在临界区前面设置检查语句，检查如果有其他并发执行的进程设置检查语句，检查如果有其他并发执行的进程在临界区中，则不允许进程进入临界区，只能在在临界区中，则不允许进程进入临界区，只能在临界区外临界区外“忙等忙等”或阻塞。当其他进程退出临界或阻塞。当

38、其他进程退出临界区后，进程能够进入临界区运行。区后，进程能够进入临界区运行。v常见的软件实现方法有：常见的软件实现方法有：Dekker算法和算法和Peterson算算法等。法等。（2）硬件实现方法）硬件实现方法502.3.1 进程同步的基本概念进程同步的基本概念4实现临界区互斥的基本方法实现临界区互斥的基本方法 中断禁用中断禁用为保证多个并发进程互斥使用临界资源，只需保证一个进程为保证多个并发进程互斥使用临界资源，只需保证一个进程在执行临界区代码时不被中断即可，这可通过系统内核为在执行临界区代码时不被中断即可，这可通过系统内核为启用和禁用中断而定义的原语来实现。启用和禁用中断而定义的原语来实现

39、。专用机器指令专用机器指令编程人员利用专用机器指令来实现临界区的互斥使用。在临编程人员利用专用机器指令来实现临界区的互斥使用。在临界区代码前通过硬件指令来检查某一全局变量是否有其他界区代码前通过硬件指令来检查某一全局变量是否有其他并发执行的进程在临界区中使用。若没有，则可进入临界并发执行的进程在临界区中使用。若没有，则可进入临界区；若有，则重复检查，处于区；若有，则重复检查，处于“忙等忙等”状态。当进程执行状态。当进程执行完临界区代码退出时，修改该全局变量，允许其他并发执完临界区代码退出时，修改该全局变量，允许其他并发执行的进程进入临界区执行。行的进程进入临界区执行。512.3.2 信号量机制

40、信号量机制1常见信号量分类常见信号量分类(1)整型信号量整型信号量v 最初由最初由Dijkstra把整型信号量定义为一个用于表示把整型信号量定义为一个用于表示资源数资源数目目的的整型量整型量S，它及一般整型量不同，除初始化外，仅能，它及一般整型量不同，除初始化外，仅能通过两个标准的原子操作通过两个标准的原子操作(Atomic Operation)P(S)和和V(S)来访问。来访问。P(S)和和V(S)操作可描述为：操作可描述为：v P(S)：while S=0 do noop；v S:=S-1；v V(S)：S:=S+1；v wait(S)和和signal(S)是两个原语，因此，它们在执行时是

41、是两个原语，因此，它们在执行时是不不可中断的可中断的。重点重点522.3.2 信号量机制信号量机制(2)记录型信号量记录型信号量v 在整型信号量机制中的在整型信号量机制中的P操作，只要是信号量操作，只要是信号量S0，就会不，就会不断地测试。断地测试。v 因此，该机制并未遵循因此，该机制并未遵循“让权等待让权等待”的准则，而是使进程的准则，而是使进程处于处于“忙等忙等”的状态。的状态。v 记录型信号量机制则是一种不存在记录型信号量机制则是一种不存在“忙等忙等”现象的进程同现象的进程同步机制。但在采取了步机制。但在采取了“让权等待让权等待”的策略后，又会出现多的策略后，又会出现多个进程等待访问同一

42、临界资源的情况。个进程等待访问同一临界资源的情况。v 为此，在记录型信号量机制中，除了需要一个用于代表资为此，在记录型信号量机制中，除了需要一个用于代表资源数目的整型变量源数目的整型变量value外，还应增加一个进程链表指针外，还应增加一个进程链表指针L，用于链接上述的所有等待进程。记录型信号量是由于它，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：数据项可描述为：532.3.2 信号量机制信号量机制v记录型信号量的记录型信号量的value值：用于表示资源数目值：用于表示资源数

43、目或请求使用某一资源的进程个数的整形量。或请求使用某一资源的进程个数的整形量。vS.value是及临界区内所使用的公用资源有关是及临界区内所使用的公用资源有关的信号量。的信号量。S.value0：可供并发进程使用的资源数：可供并发进程使用的资源数 S.value0：正在等待使用临界区的进程数：正在等待使用临界区的进程数v信号量的值除初始化外，只能通过信号量的值除初始化外，只能通过P、V原语原语来修改来修改542.3.2 信号量机制信号量机制vP(S)原语操作的主要动作是：原语操作的主要动作是：S.value-1；如果如果S.value-1以后以后仍大于等于零，则进程继续进行；仍大于等于零，则进

44、程继续进行；如果如果S.value-1以后以后小于零，则将该进程阻塞以后插入阻小于零，则将该进程阻塞以后插入阻塞队列，然后转进程调度。如下图所示塞队列，然后转进程调度。如下图所示vV(S)原语操作的主要动作是：原语操作的主要动作是：S.value+1；如果相加后结果大于零，则继续进行；如果相加后结果大于零，则继续进行；相加后结果小于等于零，则从该信号的等待队列中唤醒相加后结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后返回原进程继续执行或者转进程调一个等待进程，然后返回原进程继续执行或者转进程调度。如下图所示度。如下图所示55入口入口图图 P P原语操作功能原语操作功能入口入口图图

45、 V V原语操作功能原语操作功能2.3.2 信号量机制信号量机制56type semaphore=recordvalue:integer；L:list of process；end 相应地，相应地，P(S)和和V(S)操作可描述为：操作可描述为：procedure P(S)var S：semaphore；beginS.value:=S.value-1；if S.value0 then block(S.L)；end procedure V(S)var S:semaphore；beginS.value:=S.value+1；if S.value20)个时，信号量个时，信号量可能的变化范围。可能的变

46、化范围。(1)利用信号量实现进程互斥利用信号量实现进程互斥举例举例65 判断该问题是互斥问题还是同步问题：判断该问题是互斥问题还是同步问题：可以将该售票厅的每个窗口看作是一个临界资源为每个购票者可以将该售票厅的每个窗口看作是一个临界资源为每个购票者进程共享，每个购票者进程只能使用其中一个窗口。进程共享，每个购票者进程只能使用其中一个窗口。售票厅有售票厅有20个窗口，所以有个窗口，所以有20个同类的临界资源，一次可以允个同类的临界资源，一次可以允许许20个进程进入，并且先来者先进入。个进程进入，并且先来者先进入。由此可知：该问题满足互斥的由此可知：该问题满足互斥的2个必要条件（共享临界资源，共个

47、必要条件（共享临界资源，共享方式是先来者先进入），所以该问题是互斥问题。享方式是先来者先进入），所以该问题是互斥问题。根据互斥问题的解决方法设置信号量并赋初值：根据互斥问题的解决方法设置信号量并赋初值：设置一个信号量设置一个信号量mutex，初值为，初值为20。用信号量的用信号量的P、V操作将临界区括起来。操作将临界区括起来。问题分析问题分析66主函数算法：主函数算法：main()semaphore mutex=20;cobeginP1();Pi();Pn();coend购票者购票者i的算法：的算法：Pi()P(mutex);进入售票厅占有一个窗进入售票厅占有一个窗口购票；口购票；V(mute

48、x);算法描述算法描述67 信号量信号量mutex的的取值范围取值范围：(n20)mutex 20其其物理含义物理含义是：是：当当mutex=20时，表示售票厅内没有购票者进入，时，表示售票厅内没有购票者进入，20个窗口都是个窗口都是空闲的，表示可用资源个数；空闲的，表示可用资源个数；当当mutex=0时，表示售票厅内已经进入了时，表示售票厅内已经进入了20个购票者，每个窗个购票者，每个窗口都被分配，没有等待的购票者，可用资源为口都被分配，没有等待的购票者，可用资源为0；当当mutex=(n20)时，表示一共有时，表示一共有n个购票者，其中个购票者，其中20个购票个购票者已经进入厅内，分别占有

49、一个窗口，还有者已经进入厅内，分别占有一个窗口，还有n20个购票者个购票者在厅外等待，绝对值表示等待进程个数。在厅外等待，绝对值表示等待进程个数。结论结论：当当mutex0时其值表示可用资源个数；时其值表示可用资源个数；当当mutex0时其绝对值表示等待进程的个数。时其绝对值表示等待进程的个数。信号量讨论信号量讨论68(2)利用信号量实现前趋关系利用信号量实现前趋关系v还可利用信号量来描述程序或语句之间的前趋关还可利用信号量来描述程序或语句之间的前趋关系。系。v设有两个并发执行的进程设有两个并发执行的进程P1和和P2。P1中有语句中有语句S1；P2中有语句中有语句S2。我们希望在。我们希望在S

50、1执行后再执行执行后再执行S2。为实现这种前趋关系，我们只须使进程。为实现这种前趋关系，我们只须使进程P1和和P2共享一个公用信号量共享一个公用信号量S，并赋予其初值为，并赋予其初值为0，将，将V(S)操作放在语句操作放在语句S1后面；而在后面；而在S2语句前面插入语句前面插入P(S)操作，即操作，即在进程在进程P1中，用中，用S1；V(S)；在进程在进程P2中，用中，用P(S)；S2；69(2)利用信号量实现前趋关系利用信号量实现前趋关系v下图示出了一个前趋图，其中下图示出了一个前趋图，其中S1，S2，S3，S6是最简单的程序段是最简单的程序段(只有一条语句只有一条语句)。v为使各程序段能正