进程互斥与同步互斥课件

4.4进程之间的约束关系程序并发执行的相互制约间接的相互制约关系——资源共享（竞争资源系统）直接的相互制约关系——公共变量（进程协作）4.4进程之间的约束关系程序并发执行的相互制约341.进程互斥的概念临界资源

例1：x代表某航班机座号，p1和p2两个售票进程，售票工作是对变量x加1。这两个进程在一个处理机C上并发执行，分别具有内部寄存器r1和r2。

341.进程互斥的概念例1：x代表某航班机座号，p1和p35例2：两个进程共享一个变量x两个进程共享一个变量x时，两种可能的执行次序：A：

p1：r1:=x；r1:=r1+1；x:=r1；p2：r2:=x；r2:=r2+1；x:=r2；设x的初值为10，两种情况下的执行结果：

情况A：x=10+2情况B：x=10+1

B：

p1：r1:=x；r1:=r1+1；x:=r1；p2：r2:=x；r2:=r2+1；x:=r2；35例2：两个进程共享一个变量x设x的初值为10，两种情况36

一次仅允许一个进程使用的资源称为临界资源。

硬件：如输入机、打印机、磁带机等软件：如公用变量、数据、表格、队列等每个进程中访问临界资源的那段程序称为临界区。x

:=x+1;csa{进程A进程Bx

:=x+1;csb{36一次仅允许一个进程使用的资源称为临界资源。37互斥

在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约关系称为互斥。

x

:=x+1;csa{进程A进程Bx

:=x+1;csb{37互斥在操作系统中，当某一进程正在访问某一间接制约

由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称为由共享公有资源而造成的对并发进程执行速度的间接制约。受间接制约的类中各程序段在执行顺序上是任意的。间接制约的几个进程是互斥关系间接制约

由于共享某一公有资源而引起的在临界区内不允许并发进使用临界区应遵守的原则

各进程享有独立，平等的竞争共享资源的权利。某个进程不在临界区，不阻止其他进程进入排它性，只能有一个进程进入临界区有限等待，某个进程申请使用临界区后，必须在有限的时间内离开。使用临界区应遵守的原则

各进程享有独立，平等的竞争共享资源的382.进程同步的概念什么是进程同步

并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息称为进程同步。

进程同步的例

病员就诊

看病活动：

要病人去化验；

等化验结果；

继续诊病；化验活动：

需要进行化验?

进行化验；

开出化验结果；

382.进程同步的概念进程同步的例病员就39共享缓冲区的计算进程与打印进程的同步

计算进程cp和打印进程iop公用一个单缓冲

缓冲区bufiopcpABCDABCD39共享缓冲区的计算进程与打印进程的同步缓冲区bufi10直接制约一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的直接制约。直接制约的进程之间是同步关系10直接制约4.5同步机构操作系统提供的同步机构如下两种：锁和上锁、开锁操作信号灯和PV操作4.5同步机构操作系统提供的同步机构如下两种：401.锁和上锁、开锁操作什么是锁

用变量w代表某种资源的状态，w称为“锁”。上锁操作和开锁操作

检测w的值(是0还是1)；如果w的值为1，继续检测；如果w的值为0，将锁位置1(表示占用资源)，进入临界区执行。(此为上锁操作)临界资源使用完毕，将锁位置0。

(此为开锁操作)

401.锁和上锁、开锁操作检测w的值(是0还是1)；42上锁原语算法lock 输入：锁变量w 输出：无 { test：if(w为1)∕*测试锁位的值*∕gototest；elsew=1；∕*上锁*∕ }

不断的测试锁的状态，耗费CPU时间42上锁原语不断的测试锁的状态，耗费CPU时间开锁原语

算法unlock输入：锁变量w输出：无{w=0；∕*开锁*∕}

开锁原语432.信号灯和P、V操作什么是信号灯信号灯是一个确定的二元组(s，q)，s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。操作系统利用信号灯的状态对并发进程和共享资源进行控制和管理。

432.信号灯和P、V操作信号灯信号灯是整型变量。

变量值≥0时，表示绿灯，进程执行；变量值0时，表示红灯，进程停止执行。

注意：创建信号灯时，应准确说明信号灯s的意义和初值(这个初值绝不能为负值)。信号灯信号灯是整型变量。44P操作P操作的定义

对信号灯s的p操作记为p(s)。p(s)是一个不可分割的原语操作，即取信号灯值减1，若相减结果为负，则调用p(s)的进程被阻，并插入到该信号灯的等待队列中，否则可以继续执行。44P操作P操作的定义P操作的实现入口S-1→SS≥0?转进程调度返回入信号灯等待队列置“等待状态”≥00P操作的实现入口S-1→S45V操作V操作的定义对信号灯s的v操作记为v(s)。v(s)是一个不可分割的原语操作，即取信号灯值加1，若相加结果大于零，进程继续执行，否则，要帮助唤醒在信号灯等待队列上的一个进程。45V操作V操作的定义V操作的实现入口S+1→S从信号灯的等待队列中取出首元素入就绪队列置“就绪状态”返回S≤0?>0V操作的实现入口S+1→SPV操作是通过原语实现的

PV操作是通过原语实现的

4.6进程互斥的实现4.6进程互斥的实现461.用上锁原语和开锁原语实现进程互斥框图描述上锁原语进入临界区csa

进程pa开锁原语上锁原语进入临界区csb

进程pb开锁原语461.用上锁原语和开锁原语实现进程互斥上锁原语进入临界47程序描述

程序task1main(){intw=1；∕*互斥锁*∕

cobeginpa()；pb()；coend

}

47程序描述47程序描述pa(){lock(w)；csa；unlock(w)；}pb(){lock(w)；csb；unlock(w)；}47程序描述pb()482.用信号灯的P、V操作实现互斥框图描述

设：mutex为互斥信号灯，初值为1。p(mutex)进入临界区csa

进程pav(mutex)p(mutex)进入临界区csb

进程pbv(mutex)482.用信号灯的P、V操作实现互斥p(mutex)进入临49程序task2main(){intmutex=1；∕*互斥信号灯*∕cobeginpa()；pb()；coend}

程序描述49程序task2程序描述程序描述pa()pb(){{p(mutex)；p(mutex)；csa；csb；v(mutex)；v(mutex)；

}}

程序描述pa()信号灯可能的取值

两个并发进程，一个共享资源，互斥信号灯的值仅取1、0和－1三个值。mutex=1表示没有进程进入临界区；mutex=0表示有一个进程进入临界区；mutex=－1表示一个进程进入临界区，另一个进程等待进入。

信号灯可能的取值

两个并发进程，一个共享资源，互斥信号灯的值50互斥举例1：

x代表某航班机座号，pa和pb两个售票进程，售票工作是对变量x加1。试用信号灯的P、V操作实现这两个进程的互斥。

50互斥举例1：设：mutex为互斥信号灯，初值为1。pa()pb(){{p(mutex)；p(mutex)；x:=x+1；x:=x+1；v(mutex)；v(mutex)；

}}设：mutex为互斥信号灯，初值为1。pa()32先找到共享的临界资源和临界区；再针对每个临界区使用mutex的P、V操作将临界区括起来。互斥举例232互斥举例233信号量可能的取值范围假设有N个并发进程共用一台打印机，设互斥信号量mutex的初值为1，则：信号量mutex代表什么？mutex的取值范围为多少？mutex的值分别代表什么含义？33信号量可能的取值范围34N个并发进程，互斥信号量mutex的初值为1：mutex的取值范围为：1～-(N-1)1：表示没有进程进入临界区。有一个资源，无进程等待；0：表示有1个进程进入临界区。无资源，无进程等待；-i：表示1个进程进入临界区。无资源，且有i(i<=N)个进程等待进入。34N个并发进程，互斥信号量mutex的初值为1：35互斥问题举例3对于飞机订票系统的例子，可以采用下列方法解决“与时间有关的错误”：针对临界资源机票数设置一个信号量mutex，初值为1。每个终端进程中的程序描述如下：在机票数据库中取出当前剩余票数X；判断X>0（有票吗）？如果有，X≥N（票够吗）？如果够，则出票（打印票据）；X＝X－N（修改剩余票数）；将X回写到数据库中；P（mutex）;V（mutex）;35互斥问题举例3P（mutex）;V（mutex）;互斥问题举例4某车站售票厅有20个窗口，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在厅外等待。若把一个购票者看作一个进程，请用P、V操作管理这些并发进程，要求如下：⑴．在主函数中给出信号量的定义和初值。⑵．给出一个购票者进程的算法。⑶．给出当购票者最多不超过n(设n>20)个时，信号量可能的变化范围。36互斥问题举例436⑴．主函数算法：main(){ intmutex=20; cobegin P1();…Pi();…Pn(); coend}⑵．购票者i的算法：Pi(){ P(mutex); 购票； V(mutex);}算法描述⑴．主函数算法：⑵．购票者i的算法：算法描述38思考：n个并发进程，共享m个共享资源：mutex的取值范围为？38思考：4.4进程之间的约束关系程序并发执行的相互制约间接的相互制约关系——资源共享（竞争资源系统）直接的相互制约关系——公共变量（进程协作）4.4进程之间的约束关系程序并发执行的相互制约341.进程互斥的概念临界资源

例1：x代表某航班机座号，p1和p2两个售票进程，售票工作是对变量x加1。这两个进程在一个处理机C上并发执行，分别具有内部寄存器r1和r2。

341.进程互斥的概念例1：x代表某航班机座号，p1和p35例2：两个进程共享一个变量x两个进程共享一个变量x时，两种可能的执行次序：A：

p1：r1:=x；r1:=r1+1；x:=r1；p2：r2:=x；r2:=r2+1；x:=r2；设x的初值为10，两种情况下的执行结果：

情况A：x=10+2情况B：x=10+1

B：

p1：r1:=x；r1:=r1+1；x:=r1；p2：r2:=x；r2:=r2+1；x:=r2；35例2：两个进程共享一个变量x设x的初值为10，两种情况36

一次仅允许一个进程使用的资源称为临界资源。

硬件：如输入机、打印机、磁带机等软件：如公用变量、数据、表格、队列等每个进程中访问临界资源的那段程序称为临界区。x

:=x+1;csa{进程A进程Bx

:=x+1;csb{36一次仅允许一个进程使用的资源称为临界资源。37互斥

在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约关系称为互斥。

x

:=x+1;csa{进程A进程Bx

:=x+1;csb{37互斥在操作系统中，当某一进程正在访问某一间接制约

由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称为由共享公有资源而造成的对并发进程执行速度的间接制约。受间接制约的类中各程序段在执行顺序上是任意的。间接制约的几个进程是互斥关系间接制约

由于共享某一公有资源而引起的在临界区内不允许并发进使用临界区应遵守的原则

各进程享有独立，平等的竞争共享资源的权利。某个进程不在临界区，不阻止其他进程进入排它性，只能有一个进程进入临界区有限等待，某个进程申请使用临界区后，必须在有限的时间内离开。使用临界区应遵守的原则

各进程享有独立，平等的竞争共享资源的382.进程同步的概念什么是进程同步

并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息称为进程同步。

进程同步的例

病员就诊

看病活动：

要病人去化验；

等化验结果；

继续诊病；化验活动：

需要进行化验?

进行化验；

开出化验结果；

382.进程同步的概念进程同步的例病员就39共享缓冲区的计算进程与打印进程的同步

计算进程cp和打印进程iop公用一个单缓冲

缓冲区bufiopcpABCDABCD39共享缓冲区的计算进程与打印进程的同步缓冲区bufi48直接制约一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的直接制约。直接制约的进程之间是同步关系10直接制约4.5同步机构操作系统提供的同步机构如下两种：锁和上锁、开锁操作信号灯和PV操作4.5同步机构操作系统提供的同步机构如下两种：401.锁和上锁、开锁操作什么是锁

用变量w代表某种资源的状态，w称为“锁”。上锁操作和开锁操作

检测w的值(是0还是1)；如果w的值为1，继续检测；如果w的值为0，将锁位置1(表示占用资源)，进入临界区执行。(此为上锁操作)临界资源使用完毕，将锁位置0。

(此为开锁操作)

401.锁和上锁、开锁操作检测w的值(是0还是1)；42上锁原语算法lock 输入：锁变量w 输出：无 { test：if(w为1)∕*测试锁位的值*∕gototest；elsew=1；∕*上锁*∕ }

不断的测试锁的状态，耗费CPU时间42上锁原语不断的测试锁的状态，耗费CPU时间开锁原语

算法unlock输入：锁变量w输出：无{w=0；∕*开锁*∕}

开锁原语432.信号灯和P、V操作什么是信号灯信号灯是一个确定的二元组(s，q)，s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。操作系统利用信号灯的状态对并发进程和共享资源进行控制和管理。

432.信号灯和P、V操作信号灯信号灯是整型变量。

变量值≥0时，表示绿灯，进程执行；变量值0时，表示红灯，进程停止执行。

注意：创建信号灯时，应准确说明信号灯s的意义和初值(这个初值绝不能为负值)。信号灯信号灯是整型变量。44P操作P操作的定义

对信号灯s的p操作记为p(s)。p(s)是一个不可分割的原语操作，即取信号灯值减1，若相减结果为负，则调用p(s)的进程被阻，并插入到该信号灯的等待队列中，否则可以继续执行。44P操作P操作的定义P操作的实现入口S-1→SS≥0?转进程调度返回入信号灯等待队列置“等待状态”≥00P操作的实现入口S-1→S45V操作V操作的定义对信号灯s的v操作记为v(s)。v(s)是一个不可分割的原语操作，即取信号灯值加1，若相加结果大于零，进程继续执行，否则，要帮助唤醒在信号灯等待队列上的一个进程。45V操作V操作的定义V操作的实现入口S+1→S从信号灯的等待队列中取出首元素入就绪队列置“就绪状态”返回S≤0?>0V操作的实现入口S+1→SPV操作是通过原语实现的

PV操作是通过原语实现的

4.6进程互斥的实现4.6进程互斥的实现461.用上锁原语和开锁原语实现进程互斥框图描述上锁原语进入临界区csa

进程pa开锁原语上锁原语进入临界区csb

进程pb开锁原语461.用上锁原语和开锁原语实现进程互斥上锁原语进入临界47程序描述

程序task1main(){intw=1；∕*互斥锁*∕

cobeginpa()；pb()；coend

}

47程序描述47程序描述pa(){lock(w)；csa；unlock(w)；}pb(){lock(w)；csb；unlock(w)；}47程序描述pb()482.用信号灯的P、V操作实现互斥框图描述

设：mutex为互斥信号灯，初值为1。p(mutex)进入临界区csa

进程pav(mutex)p(mutex)进入临界区csb

进程pbv(mutex)482.用信号灯的P、V操作实现互斥p(mutex)进入临49程序task2main(){intmutex=1；∕*互斥信号灯*∕cobeginpa()；pb()；coend}

程序描述49程序task2程序描述程序描述pa()pb(){{p(mutex)；p(mutex)；csa；csb；v(mutex)；v(mutex)；

}}

程序描述pa()信号灯可能的取值

两个并发进程，一个共享资源，互斥信号灯的值仅取1、0和－1三个值。mutex=1表示没有进程进入临界区；mutex=0表示有一个进程进入临界区；mutex=－1表示一个进程进入临界区，另一个进程等待进入。

信号灯可能的取值

两个并发进程，一个共享资源，互斥信号灯的值50互斥举例1：

x代表某航班机座号，pa和pb两个售票进程，售票工作是对变量x加1。试用信号灯的P、V操作实现这两个进程的互斥。

50互斥举例1：