《操作系统进程互斥及同步-互斥优秀PPT.ppt》由会员分享，可在线阅读，更多相关《操作系统进程互斥及同步-互斥优秀PPT.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4.4 进程之间的约束关系进程之间的约束关系l程序并发执行的相互制约程序并发执行的相互制约l间接的相互制约关系间接的相互制约关系 资源共享（竞争资源共享（竞争资源系统）资源系统）l干脆的相互制约关系干脆的相互制约关系 公共变量（进程公共变量（进程协作）协作）341.1.进程互斥的概念进程互斥的概念进程互斥的概念进程互斥的概念l l临界资源临界资源临界资源临界资源 l l例例例例1 1 1 1：x x x x代表某航班机座号，代表某航班机座号，代表某航班机座号，代表某航班机座号，p p p p1 1 1 1和和和和p p p p2 2 2 2两个售票进两个售票进两个售票进两个售票进程，售票工作是
2、对变量程，售票工作是对变量程，售票工作是对变量程，售票工作是对变量x x x x加加加加1 1 1 1。这两个进程在一。这两个进程在一。这两个进程在一。这两个进程在一个处理机个处理机个处理机个处理机C C C C上并发执行，分别具有内部寄存器上并发执行，分别具有内部寄存器上并发执行，分别具有内部寄存器上并发执行，分别具有内部寄存器r r r r1 1 1 1和和和和r r r r2 2 2 2。35l l例例例例2 2：两个进程共享一个变量：两个进程共享一个变量：两个进程共享一个变量：两个进程共享一个变量x x 两个进程共享一个变量两个进程共享一个变量两个进程共享一个变量两个进程共享一个变量x
3、 x时，时，时，时，两种可能的执行次序：两种可能的执行次序：两种可能的执行次序：两种可能的执行次序：A A：p p1 1：r r1 1:=x:=x；r r1 1:=r:=r1 1+1+1；x:=r x:=r1 1 ；p p2 2：r r2 2:=x:=x；r r2 2:=r:=r2 2+1+1；x:=r x:=r2 2 ；设设设设x x的初值为的初值为的初值为的初值为1010，两种状况下的执行结果：，两种状况下的执行结果：，两种状况下的执行结果：，两种状况下的执行结果：状况状况状况状况A A：x=10+2 x=10+2 状况状况状况状况B B：x=10+1 x=10+1 B B：p p1 1：
4、r r1 1:=x:=x；r r1 1:=r:=r1 1+1+1；x:=r x:=r1 1 ；p p2 2：r r2 2:=x:=x；r r2 2:=r:=r2 2+1+1；x:=r x:=r2 2 ；36 l一次仅允许一个进程运用的资源称为临界资源。一次仅允许一个进程运用的资源称为临界资源。l 硬件：如输入机、打印机、磁带机等硬件：如输入机、打印机、磁带机等l 软件：如公用变量、数据、表格、队列等软件：如公用变量、数据、表格、队列等l每个进程中访问临界资源的那段程序称为临界区。每个进程中访问临界资源的那段程序称为临界区。x:=x+1;csa 进程进程A进程进程B x:=x+1;csb 37l
5、 l互斥互斥互斥互斥 l l在操作系统中，当某一进程正在访问某一存储区域时，在操作系统中，当某一进程正在访问某一存储区域时，在操作系统中，当某一进程正在访问某一存储区域时，在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就不允许其他进程来读出或者修改存储区的内容，否则，就不允许其他进程来读出或者修改存储区的内容，否则，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约就会发生后果无法估计的错误。进程间的这种相互制约就会发生后果无法估计的错误。进程间的这种相互制约就会发生后果无法估计的错误。进程间的
6、这种相互制约关系称为互斥。关系称为互斥。关系称为互斥。关系称为互斥。x:=x+1;csa 进程进程A进程进程B x:=x+1;csb 间接制约l由共享公有资源而造成的对并发进程执行由共享公有资源而造成的对并发进程执行速度的间接制约。速度的间接制约。l受间接制约的类中各程序段在执行依次上受间接制约的类中各程序段在执行依次上是随意的。是随意的。l间接制约的几个进程是互斥关系间接制约的几个进程是互斥关系运用临界区应遵守的原则l各进程享有独立，同等的竞争共享资源的各进程享有独立，同等的竞争共享资源的权利。权利。l某个进程不在临界区，不阻挡其他进程进某个进程不在临界区，不阻挡其他进程进入入l排它性，只能
7、有一个进程进入临界区排它性，只能有一个进程进入临界区l有限等待，某个进程申请运用临界区后，有限等待，某个进程申请运用临界区后，必需在有限的时间内离开。必需在有限的时间内离开。382.2.进程同步的概念进程同步的概念进程同步的概念进程同步的概念什么是进程同步什么是进程同步什么是进程同步什么是进程同步 并发进程在一些关键点上可能须要相互等待与互并发进程在一些关键点上可能须要相互等待与互并发进程在一些关键点上可能须要相互等待与互并发进程在一些关键点上可能须要相互等待与互通消息，通消息，通消息，通消息，这种相互制约的等待与互通消息称为进程同步。这种相互制约的等待与互通消息称为进程同步。这种相互制约的等
8、待与互通消息称为进程同步。这种相互制约的等待与互通消息称为进程同步。l l进程同步的例进程同步的例进程同步的例进程同步的例 l l病员就诊病员就诊病员就诊病员就诊 看病活动：看病活动：要病人去要病人去化验；化验；等等化验结果；化验结果；继续诊病；继续诊病；化验活动：化验活动：需要进行化验需要进行化验?进行进行化验；化验；开出化验结果；开出化验结果；39l l共享缓冲区的计算进程与打印进程的同步共享缓冲区的计算进程与打印进程的同步共享缓冲区的计算进程与打印进程的同步共享缓冲区的计算进程与打印进程的同步 计算进程计算进程计算进程计算进程 cp cp和打印进程和打印进程和打印进程和打印进程 iop
9、iop公用一个单缓冲公用一个单缓冲公用一个单缓冲公用一个单缓冲 缓冲区缓冲区bufiop cp10干脆制约干脆制约一一组组在在异异步步环环境境下下的的并并发发进进程程，各各自自的的执执行行结结果果互互为为对对方方的的执执行行条条件件，从从而而限限制制各各进进程程的的执执行行速速度度的的过过程程称称为为并发进程间的干脆制约。并发进程间的干脆制约。干脆制约的进程之间是同步关系干脆制约的进程之间是同步关系4.5同步机构同步机构l操作系统供应的同步机构如下两种：l锁和上锁、开锁操作l信号灯和PV操作401.1.锁和上锁、开锁操作锁和上锁、开锁操作锁和上锁、开锁操作锁和上锁、开锁操作l l什么是锁什么是
10、锁什么是锁什么是锁用变量用变量用变量用变量w w w w代表某种资源的状态，代表某种资源的状态，代表某种资源的状态，代表某种资源的状态，w w w w称为称为称为称为“锁锁锁锁”。l l上锁操作和开锁操作上锁操作和开锁操作上锁操作和开锁操作上锁操作和开锁操作 l l检测检测检测检测w w的值的值的值的值(是是是是0 0还是还是还是还是1)1)；l l假如假如假如假如w w的值为的值为的值为的值为1 1，接着检测；，接着检测；，接着检测；，接着检测；l l假如假如假如假如w w的值为的值为的值为的值为0 0，将锁位置，将锁位置，将锁位置，将锁位置1(1(表示占用资源表示占用资源表示占用资源表示占
11、用资源)，进入临，进入临，进入临，进入临界区执行。界区执行。界区执行。界区执行。(此为上锁操作此为上锁操作此为上锁操作此为上锁操作)l l临界资源运用完毕，将锁位置临界资源运用完毕，将锁位置临界资源运用完毕，将锁位置临界资源运用完毕，将锁位置0 0。(此为开锁操作此为开锁操作此为开锁操作此为开锁操作)42l上锁原语上锁原语l l算法算法算法算法 lock lock 输入：锁变量输入：锁变量输入：锁变量输入：锁变量w w 输出：无输出：无输出：无输出：无 testtest：if(w if(w为为为为1)*1)*测试锁位的值测试锁位的值测试锁位的值测试锁位的值*goto test goto tes
12、t；else w=1 else w=1；*上锁上锁上锁上锁*不断的测不断的测试锁的状试锁的状态，耗费态，耗费CPUCPU时间时间开锁原语开锁原语算法算法 unlock 输入：锁变量输入：锁变量w 输出：无输出：无 w=0；*开锁开锁*432.2.信号灯和信号灯和信号灯和信号灯和P P、V V操作操作操作操作什么是信号灯什么是信号灯什么是信号灯什么是信号灯信号灯是一个确定的二元组信号灯是一个确定的二元组信号灯是一个确定的二元组信号灯是一个确定的二元组(s(s，q)q)，s s是一个具有非负是一个具有非负是一个具有非负是一个具有非负初值的整型变量，初值的整型变量，初值的整型变量，初值的整型变量，q
13、 q是一个初始状态为空的队列。是一个初始状态为空的队列。是一个初始状态为空的队列。是一个初始状态为空的队列。操作系统利用信号灯的状态对并发进程和共享资源操作系统利用信号灯的状态对并发进程和共享资源操作系统利用信号灯的状态对并发进程和共享资源操作系统利用信号灯的状态对并发进程和共享资源进行限制和管理。进行限制和管理。进行限制和管理。进行限制和管理。信号灯信号灯是整型变量。信号灯是整型变量。变量值变量值 0 时，表示绿灯，进程执行；时，表示绿灯，进程执行；变量值变量值 0 时，表示红灯，进程停止执行。时，表示红灯，进程停止执行。留意：创建信号灯时，应精确说明信号灯留意：创建信号灯时，应精确说明信号
14、灯 s 的意义和初值的意义和初值(这个初值这个初值 绝不能为负值绝不能为负值)。44lP 操作操作lP 操作的定义操作的定义 l 对信号灯对信号灯s的的 p操作记为操作记为 p(s)。p(s)是是一个不行分割的原语操作，即取信号灯一个不行分割的原语操作，即取信号灯值减值减1，若相减结果为负，则调用，若相减结果为负，则调用p(s)的的进程被阻，并插入到该信号灯的等待队进程被阻，并插入到该信号灯的等待队列中，否则可以接着执行。列中，否则可以接着执行。P 操作的实现操作的实现 入入 口口 S-1 S S0?转进程调度转进程调度返回返回 入信号灯等待队列入信号灯等待队列 置置“等待状态等待状态”00
15、0 045lV 操作操作lV V 操作的定义操作的定义 l对信号灯对信号灯s s的的 v v操作记为操作记为 v(s)v(s)。v(s)v(s)是一个不行分割的原语操作，即取信号是一个不行分割的原语操作，即取信号灯值加灯值加1 1，若相加结果大于零，进程接着，若相加结果大于零，进程接着执行，否则，要帮助唤醒在信号灯等待执行，否则，要帮助唤醒在信号灯等待队列上的一个进程。队列上的一个进程。V 操作的实现操作的实现 入入 口口 S+1 S 从信号灯的等待队列中取出首元素从信号灯的等待队列中取出首元素 入就绪队列入就绪队列 置置“就就绪绪状状态态”返回返回 S0?0 0PV操作是通过原语实现的操作是
16、通过原语实现的4.6 进程互斥的实现进程互斥的实现461.1.用用用用上锁原语和开锁原语实现进程互斥上锁原语和开锁原语实现进程互斥上锁原语和开锁原语实现进程互斥上锁原语和开锁原语实现进程互斥l l框图描述框图描述框图描述框图描述 上锁原语上锁原语进入临界区进入临界区csa 进程进程 pa开锁原语开锁原语上锁原语上锁原语进入临界区进入临界区csb 进程进程 pb开锁原语开锁原语47l l程序描述程序描述程序描述程序描述 程序程序程序程序 task1 task1 main()main()int w=1 int w=1；*互斥锁互斥锁互斥锁互斥锁*cobegin cobegin p pa a()()
17、；p pb b()()；coend coend 47l l程序描述程序描述程序描述程序描述p pa a()()lock(w)lock(w)；cs csa a ；unlock(w)unlock(w)；p pb b()()lock(w)lock(w)；cs csb b ；unlock(w)unlock(w)；482.2.用用用用信号灯的信号灯的信号灯的信号灯的P P、V V操作实现互斥操作实现互斥操作实现互斥操作实现互斥l l框图描述框图描述框图描述框图描述 设：设：设：设：mutexmutex为互斥信号灯，初值为为互斥信号灯，初值为为互斥信号灯，初值为为互斥信号灯，初值为1 1。p(mutex)
18、进入临界区进入临界区csa 进程进程 pa v(mutex)p(mutex)进入临界区进入临界区csb 进程进程 pb v(mutex)49程序程序程序程序 task2 task2 main()main()int mutex=1 int mutex=1；*互斥信号灯互斥信号灯互斥信号灯互斥信号灯*cobegin cobegin p pa a()()；p pb b()()；coend coend l程序描述程序描述程序描述p pa a()p()pb b()()p(mutex)p(mutex)；p(mutex)p(mutex)；cs csa a ；cs csb b ；v(mutex)v(mutex
19、)；v(mutex)v(mutex)；信号灯可能的取值信号灯可能的取值两个并发进程，一个共享资源，互斥信号灯的值两个并发进程，一个共享资源，互斥信号灯的值仅取仅取1 1、0 0和和1 1三个值。三个值。mutex=1 mutex=1 表示没有进程进入临界区；表示没有进程进入临界区；mutex=0 mutex=0 表示有一个进程进入临界区；表示有一个进程进入临界区；mutex=mutex=1 1 表示一个进程进入临界区，表示一个进程进入临界区，另一个另一个进程等待进入。进程等待进入。50l互斥举例互斥举例1：x代表某航班机座号，代表某航班机座号，pa和和pb两个售票两个售票进程，售票工作是对变量
20、进程，售票工作是对变量x加加1。试用。试用信号灯的信号灯的P、V操作实现这两个进程的操作实现这两个进程的互斥。互斥。设：设：mutexmutex为互斥信号灯，初值为为互斥信号灯，初值为1 1。pa()pb()p(mutex)；p(mutex)；x:=x+1；x:=x+1；v(mutex)；v(mutex)；32先先找找到到共共享享的的临临界界资资源源和临界区；和临界区；再再针针对对每每个个临临界界区区运运用用mutexmutex的的P P、V V操操作作将将临临界区括起来。界区括起来。互斥举例互斥举例2 233信号量可能的取值范围信号量可能的取值范围假假设设有有N N个个并并发发进进程程共共用
21、用一一台台打打印印机机，设设互斥信号量互斥信号量mutexmutex的初值为的初值为1 1，则：，则：J信号量信号量mutexmutex代表什么？代表什么？Jmutexmutex的取值范围为多少？的取值范围为多少？Jmutexmutex的值分别代表什么含义？的值分别代表什么含义？34N N N N个并发进程，互斥信号量个并发进程，互斥信号量个并发进程，互斥信号量个并发进程，互斥信号量mutexmutexmutexmutex的的的的初值为初值为初值为初值为1 1 1 1：mutexmutexmutexmutex的取值范围为：的取值范围为：的取值范围为：的取值范围为：1 1 1 1-(N-1)-(
22、N-1)-(N-1)-(N-1)1 1 1 1：表表表表示示示示没没没没有有有有进进进进程程程程进进进进入入入入临临临临界界界界区区区区。有有有有一一一一个个个个资资资资源源源源，无无无无进程等待；进程等待；进程等待；进程等待；0 0 0 0：表表表表示示示示有有有有1 1 1 1个个个个进进进进程程程程进进进进入入入入临临临临界界界界区区区区。无无无无资资资资源源源源，无无无无进进进进程程程程等待；等待；等待；等待；-i-i-i-i：表表表表示示示示1 1 1 1个个个个进进进进程程程程进进进进入入入入临临临临界界界界区区区区。无无无无资资资资源源源源，且且且且有有有有i i i i(i=N
23、)(i=N)(i=N)(i0X0X0X0（有票吗）？（有票吗）？（有票吗）？（有票吗）？假如有，假如有，假如有，假如有，XN XN XN XN（票够吗）？（票够吗）？（票够吗）？（票够吗）？假如够，则出票（打印票据）；假如够，则出票（打印票据）；假如够，则出票（打印票据）；假如够，则出票（打印票据）；X X X XX X X XN N N N（修改剩余票数）；（修改剩余票数）；（修改剩余票数）；（修改剩余票数）；将将将将X X X X回写到数据库中；回写到数据库中；回写到数据库中；回写到数据库中；P P（mutexmutex）;V V（mutexmutex）;l互斥问题举例4l某车站售票厅有2
24、0个窗口，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可马上进入，否则需在厅外等待。若把一个购票者看作一个进程，请用P、V操作管理这些并发进程，要求如下：l在主函数中给出信号量的定义和初值。l给出一个购票者进程的算法。l给出当购票者最多不超过n(设n20)个时，信号量可能的变更范围。36主函数算法：主函数算法：主函数算法：主函数算法：main()main()main()main()int mutex=20;int mutex=20;int mutex=20;int mutex=20;cobegincobegincobegincobeginP1();Pi();Pn();P1();Pi();Pn();P1();Pi();Pn();P1();Pi();Pn();coendcoendcoendcoend 购票者购票者购票者购票者i i i i的算法：的算法：的算法：的算法：Pi()Pi()Pi()Pi()P(mutex);P(mutex);P(mutex);P(mutex);购票；购票；购票；购票；V(mutex);V(mutex);V(mutex);V(mutex);算法描述算法描述算法描述算法描述38思索：思索：n n个并发进程，共享个并发进程，共享mm个共享资源：个共享资源：mutexmutex的取值范围为？的取值范围为？