操作系统进程互斥及同步互斥

《操作系统进程互斥及同步互斥》由会员分享，可在线阅读，更多相关《操作系统进程互斥及同步互斥（38页珍藏版）》请在金锄头文库上搜索。

1、4.4 进程之间的约束关系进程之间的约束关系l程序并发执行的相互制约程序并发执行的相互制约间接的相互制约关系间接的相互制约关系 资源共享（竞争资资源共享（竞争资源系统）源系统）直接的相互制约关系直接的相互制约关系 公共变量（进程协公共变量（进程协作）作）341. 1. 进程互斥的概念进程互斥的概念进程互斥的概念进程互斥的概念l l临界资源临界资源临界资源临界资源 l例例1 1：x x代表某航班机座号，代表某航班机座号，p p1 1和和p p2 2两个售票进两个售票进程，售票工作是对变量程，售票工作是对变量x x加加1 1。这两个进程在一。这两个进程在一个处理机个处理机C C上并发执行，分别具有

2、内部寄存器上并发执行，分别具有内部寄存器r r1 1和和r r2 2。 35l例例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

3、:= r2+1； x := r2 ；36 l一次仅允许一个进程使用的资源称为一次仅允许一个进程使用的资源称为临界资源临界资源。 硬件：如输入机、打印机、磁带机等硬件：如输入机、打印机、磁带机等 软件：如公用变量、数据、表格、队列等软件：如公用变量、数据、表格、队列等l每个进程中访问临界资源的那段程序称为每个进程中访问临界资源的那段程序称为临界区临界区。 x := x+1; csa 进程进程A进程进程B x := x+1; csb 37l l互斥互斥互斥互斥 l在操作系统中，当某一进程正在访问某一存储区域时，在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内

4、容，否则，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约就会发生后果无法估计的错误。进程间的这种相互制约关系称为互斥。关系称为互斥。 x := x+1; csa 进程进程A进程进程B x := x+1; csb 间接制约l由共享公有资源而造成的对并发进程执行由共享公有资源而造成的对并发进程执行速度的速度的间接制约间接制约。l受间接制约的类中各程序段在执行顺序上受间接制约的类中各程序段在执行顺序上是是任意任意的。的。l间接制约的几个进程是互斥关系间接制约的几个进程是互斥关系使用临界区应遵守的原则l各进程享有独立，平等的竞争共享资源的各进程享有独

5、立，平等的竞争共享资源的权利。权利。l某个进程不在临界区，不阻止其他进程进某个进程不在临界区，不阻止其他进程进入入l排它性，只能有一个进程进入临界区排它性，只能有一个进程进入临界区l有限等待，某个进程申请使用临界区后，有限等待，某个进程申请使用临界区后，必须在有限的时间内离开。必须在有限的时间内离开。382. 2. 进程同步的概念进程同步的概念进程同步的概念进程同步的概念l l什么是进程同步什么是进程同步什么是进程同步什么是进程同步 并发进程在一些关键点上可能需要互相等待与互通消息，并发进程在一些关键点上可能需要互相等待与互通消息， 这种相互制约的等待与互通消息称为进程同步。这种相互制约的等待

6、与互通消息称为进程同步。 l l进程同步的例进程同步的例进程同步的例进程同步的例 l病员就诊病员就诊 看病活动：看病活动： 要病人去要病人去化验；化验； 等等化验结果；化验结果； 继续诊病；继续诊病；化验活动：化验活动： 需要进行化验需要进行化验 ? 进行进行化验；化验； 开出化验结果；开出化验结果； 39l共享缓冲区的计算进程与打印进程的同步共享缓冲区的计算进程与打印进程的同步 计算进程计算进程 cp和打印进程和打印进程 iop公用一个单缓冲公用一个单缓冲 缓冲区缓冲区bufiop cp10直接制约直接制约一一组组在在异异步步环环境境下下的的并并发发进进程程，各各自自的的执执行行结结果果互互

7、为为对对方方的的执执行行条条件件，从从而而限限制制各各进进程程的的执执行行速速度度的的过过程程称称为为并发进程间的并发进程间的直接制约直接制约。直接制约的进程之间是同步关系直接制约的进程之间是同步关系4.5同步机构同步机构l操作系统提供的同步机构如下两种：l l锁和上锁、开锁操作锁和上锁、开锁操作锁和上锁、开锁操作锁和上锁、开锁操作l l信号灯和信号灯和信号灯和信号灯和PVPV操作操作操作操作401. 1. 锁和上锁、开锁操作锁和上锁、开锁操作锁和上锁、开锁操作锁和上锁、开锁操作l l什么是锁什么是锁什么是锁什么是锁用变量用变量w w代表某种资源的状态，代表某种资源的状态，w w称为称为“锁锁

8、” 。l l上锁操作和开锁操作上锁操作和开锁操作上锁操作和开锁操作上锁操作和开锁操作 l检测检测w的值的值 (是是0还是还是1)；l如果如果w的值为的值为1，继续检测；，继续检测；l如果如果w的值为的值为0，将锁位置，将锁位置1 (表示占用资源表示占用资源)，进入临，进入临界区执行。界区执行。 (此为上锁操作此为上锁操作)l临界资源使用完毕，将锁位置临界资源使用完毕，将锁位置0。 (此为开锁操作此为开锁操作) 42l上锁原语上锁原语l算法算法 lock 输入：锁变量输入：锁变量w 输出：无输出：无 test： if (w为为1) * 测试锁位的值测试锁位的值* goto test； else

9、w=1； *上锁上锁* 不断的测不断的测试锁的状试锁的状态，耗费态，耗费CPUCPU时间时间开锁原语开锁原语算法算法 unlock 输入：锁变量输入：锁变量w 输出：无输出：无 w=0；*开锁开锁* 432. 2. 信号灯和信号灯和P、V操作操作l什么是信号灯什么是信号灯信号灯是一个确定的二元组信号灯是一个确定的二元组(s，q)，s是一是一个具有非负初值的整型变量，个具有非负初值的整型变量，q是一个初始是一个初始状态为空的队列。操作系统利用信号灯的状态为空的队列。操作系统利用信号灯的状态对并发进程和共享资源进行控制和管状态对并发进程和共享资源进行控制和管理。理。 信号灯信号灯是整型变量。信号灯

10、是整型变量。 变量值变量值 0 0 时，表示绿灯，进程执行；时，表示绿灯，进程执行； 变量值变量值 0 0 时，表示红灯，进程停止执时，表示红灯，进程停止执行。行。 注意：创建信号灯时，应准确说明信号灯注意：创建信号灯时，应准确说明信号灯 s 的意义和初值的意义和初值 (这个这个初值初值 绝不能为负值绝不能为负值)。44lP 操作操作lP 操作的定义操作的定义 对信号灯对信号灯s的的 p操作记为操作记为 p(s)。p(s)是一是一个不可分割的原语操作，即取信号灯值个不可分割的原语操作，即取信号灯值减减1，若相减结果为负，则调用，若相减结果为负，则调用p(s)的进的进程被阻，并插入到该信号灯的等

11、待队列程被阻，并插入到该信号灯的等待队列中，否则可以继续执行。中，否则可以继续执行。P 操作的实现操作的实现 入入 口口 S-1 S S0 ?转进程调度转进程调度返回返回 入信号灯等待队列入信号灯等待队列 置置“等待状态等待状态”0 0 0 045lV 操作操作lV V 操作的定义操作的定义 对信号灯对信号灯s s的的 v v操作记为操作记为 v(sv(s) )。v(sv(s) )是是一个不可分割的原语操作，即取信号灯一个不可分割的原语操作，即取信号灯值加值加1 1，若相加结果大于零，进程继续执，若相加结果大于零，进程继续执行，否则，要帮助唤醒在信号灯等待队行，否则，要帮助唤醒在信号灯等待队列

12、上的一个进程。列上的一个进程。V 操作的实现操作的实现 入入 口口 S+ +1 S 从信号灯的等待队列中取出首元素从信号灯的等待队列中取出首元素 入就绪队列入就绪队列 置置“就就绪绪状状态态” 返回返回 S0 ?0 0PV操作是通过原语实现的操作是通过原语实现的4.6 进程互斥的实现进程互斥的实现461. 1. 用用用用上锁原语和开锁原语实现进程互斥上锁原语和开锁原语实现进程互斥上锁原语和开锁原语实现进程互斥上锁原语和开锁原语实现进程互斥l l框图描述框图描述框图描述框图描述 上锁原语上锁原语进入临界区进入临界区csa 进程进程 pa开锁原语开锁原语上锁原语上锁原语进入临界区进入临界区csb

13、进程进程 pb开锁原语开锁原语47l l程序描述程序描述程序描述程序描述 程序程序 task1 main( ) int w=1； * 互斥锁互斥锁 * cobegin pa( )； pb( )； coend 47l l程序描述程序描述程序描述程序描述pa( ) lock(w)； csa ； unlock(w)； pb( ) lock(w)； csb ； unlock(w)； 482. 2. 用用用用信号灯的信号灯的信号灯的信号灯的P P、V V操作实现互斥操作实现互斥操作实现互斥操作实现互斥l l框图描述框图描述框图描述框图描述 设：设：mutex为互斥信号灯，初值为为互斥信号灯，初值为1。p

14、(mutex)进入临界区进入临界区csa 进程进程 pa v(mutex)p(mutex)进入临界区进入临界区csb 进程进程 pb v(mutex)49程序程序 task2 main( ) int mutex=1； * 互斥信号灯互斥信号灯 * cobegin pa( )； pb( )； coend l程序描述程序描述程序描述pa( ) pb( ) p(mutex)； p(mutex)； csa ； csb ； v(mutex)； v(mutex)； 信号灯可能的取值信号灯可能的取值两个并发进程，一个共享资源，互斥信号灯的值两个并发进程，一个共享资源，互斥信号灯的值仅取仅取1 1、0 0和和

15、1 1三个值。三个值。mutex=1 mutex=1 表示没有进程进入临界区；表示没有进程进入临界区；mutex=0mutex=0 表示有一个进程进入临界区；表示有一个进程进入临界区；mutexmutex= =1 1 表示一个进程进入临界区，表示一个进程进入临界区， 另一个另一个进程等待进入。进程等待进入。 50l互斥举例互斥举例1： x代表某航班机座号，代表某航班机座号，pa和和pb两个售票两个售票进程，售票工作是对变量进程，售票工作是对变量x加加1。试用。试用信号灯的信号灯的P、V操作实现这两个进程的操作实现这两个进程的互斥。互斥。 设：设：mutexmutex为互斥信号灯，初值为为互斥信

16、号灯，初值为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个个并并发发进进程程共共用用一一台台打打印印机机，设设互斥信号量互斥信号量mutexmutex的初值为的初值为1 1，则：，则：J信号量信号量mutexmutex代表什么？代

17、表什么？Jmutexmutex的取值范围为多少？的取值范围为多少？Jmutexmutex的值分别代表什么含义？的值分别代表什么含义？34N N N N个并发进程，互斥信号量个并发进程，互斥信号量个并发进程，互斥信号量个并发进程，互斥信号量mutexmutexmutexmutex的的的的初值为初值为初值为初值为1 1 1 1：mutexmutexmutexmutex的取值范围为：的取值范围为：的取值范围为：的取值范围为：1 1 1 1-(N-1)-(N-1)-(N-1)-(N-1)1 1 1 1：表表表表示示示示没没没没有有有有进进进进程程程程进进进进入入入入临临临临界界界界区区区区。有有有有一

18、一一一个个个个资资资资源源源源，无无无无进进进进程等待；程等待；程等待；程等待；0 0 0 0：表表表表示示示示有有有有1 1 1 1个个个个进进进进程程程程进进进进入入入入临临临临界界界界区区区区。无无无无资资资资源源源源，无无无无进进进进程程程程等待；等待；等待；等待；-i-i-i-i：表表表表示示示示1 1 1 1个个个个进进进进程程程程进进进进入入入入临临临临界界界界区区区区。无无无无资资资资源源源源，且且且且有有有有i i i i (i=N)(i=N)(i=N)(i0X0X0X0（有票吗）？（有票吗）？（有票吗）？（有票吗）？l如果有，如果有，如果有，如果有， XNXNXNXN（票够

19、吗）？（票够吗）？（票够吗）？（票够吗）？l如果够，则出票（打印票据）；如果够，则出票（打印票据）；如果够，则出票（打印票据）；如果够，则出票（打印票据）；lX X X XX X X XN N N N（修改剩余票数）；（修改剩余票数）；（修改剩余票数）；（修改剩余票数）；l将将将将X X X X回写到数据库中；回写到数据库中；回写到数据库中；回写到数据库中；P P（mutexmutex）; ;V V（mutexmutex）; ;l互斥问题举例4l l某车站售票厅有某车站售票厅有某车站售票厅有某车站售票厅有2020个窗口，任何时刻最多可容纳个窗口，任何时刻最多可容纳个窗口，任何时刻最多可容纳个窗

20、口，任何时刻最多可容纳2020名购票者进入，当售票厅中少于名购票者进入，当售票厅中少于名购票者进入，当售票厅中少于名购票者进入，当售票厅中少于2020名购票者时，则厅名购票者时，则厅名购票者时，则厅名购票者时，则厅外的购票者可立即进入，否则需在厅外等待。若把一外的购票者可立即进入，否则需在厅外等待。若把一外的购票者可立即进入，否则需在厅外等待。若把一外的购票者可立即进入，否则需在厅外等待。若把一个购票者看作一个进程，请用个购票者看作一个进程，请用个购票者看作一个进程，请用个购票者看作一个进程，请用P P、V V操作管理这些并发操作管理这些并发操作管理这些并发操作管理这些并发进程，要求如下：进程

21、，要求如下：进程，要求如下：进程，要求如下：l l在主函数中给出信号量的定义和初值。在主函数中给出信号量的定义和初值。在主函数中给出信号量的定义和初值。在主函数中给出信号量的定义和初值。l l给出一个购票者进程的算法。给出一个购票者进程的算法。给出一个购票者进程的算法。给出一个购票者进程的算法。l l给出当购票者最多不超过给出当购票者最多不超过给出当购票者最多不超过给出当购票者最多不超过n (n (设设设设n20)n20)个时，信个时，信个时，信个时，信号量可能的变化范围。号量可能的变化范围。号量可能的变化范围。号量可能的变化范围。36主函数算法：主函数算法：主函数算法：主函数算法：main(

22、)main()main()main() int mutex=20;int mutex=20;int mutex=20;int mutex=20;cobegincobegincobegincobeginP1(); P1(); P1(); P1(); Pi();Pi();Pi();Pi();Pn();Pn();Pn();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个并发进程，共享个并发进程，共享m m个共享资源：个共享资源：mutexmutex的取值范围为？的取值范围为？