并发性：互斥和同步课件（精品）

《并发性：互斥和同步课件（精品）》由会员分享，可在线阅读，更多相关《并发性：互斥和同步课件（精品）（88页珍藏版）》请在金锄头文库上搜索。

1、问题：1、如何协调多个进程对系统资源、如内存 空间、外部设备等的资源和共享？ 2、如何解决多个进程因为竞争资源而出现的执行 结果异常 ，甚至系统不稳定，失效等问题？ 3、进程同时申请文件打印，如何有效分配打印机？ 同步协调，对相关进程在执行次序上进行协调，使 并发执行 的进程之间有效共享资源和相互合作，使程序的执行 具有可再现性。第8章 并发性：互斥和同步例1：o银行的联网储蓄业务允许储户同时使用存折和储 蓄卡对同一账户进行存取款操作，如果某储户同 时办理两笔存款业务（分别存入1000元和2000 元）o从系统的角度看，有两个进程将同时对账户的余 额进行操作，如果两个进程同时读出账户的余额 （

2、假设为5000元），那么两个进程执行完的结果 分别为6000元（5000+1000）、7000（ 5000+2000）元分析及措施o最后，储蓄余额可能为6000或者7000，都是不 正确的。o原因是：两个进程同时修改同一个数据，而没有 进行有效控制。o正确地方法：如果有多个进程同时对同一数据进 行修改时，系统必须控制一次仅允许一个进程完 成读数据、修改数据两件事，才允许其他进程对 同一数据的读和修改操作。8.5.2 信箱通信8.1 互斥和同步 8.1.1 互斥和临界区 8.1.2 同步 8.2 实现互斥的方法讨论8.2.1 实现互斥的硬件方法 8.2.2 实现互斥的软件方法8.3 信号量与P、

3、V操作 8.3.1 信号量与P、V操作定义 8.3.2 用P、V操作实现互斥 8.3.3 用P、V操作实现同步8.3.4 用P、V操作实现资源分配 8.3.5 管程8.4 互斥、同步的样例分析 8.4.1 读者-写者问题 8.4.2 哲学家就餐问题 8.4.3 理发师理发问题8.5 高级进程通信 8.5.1 消息缓冲通信本章目录某用户编写进程p1用于存款，进程p2用于取款。它们都访问变量balance表 示的余额：p1用于增加balance，p2用于减少balance。p1和p2的几条汇编指令代码框 架如下（其中x1、x2分别是p1和p2的临时变量）： p1的代码框架： p2的代码框架： lo

4、ad R1, balance load R1, balance load R2, x1 load R2, x2 add R1, R2 sub R1, R2 store R1, balance store R1, balance 8.1 互斥和同步 o8.1.1 互斥和临界区 进程间的间接制约关系 1.如上例，系统中有这样的一类资源，哪个进程先用它、哪个进程后用它没有什么 关系，但不能同时使用。即在一个进程使用时，另一个进程不能使用，否则会导致错误 。这种由于使用具有“排他性”资源、而对进程的执行产生影响，使它们间产生了的关系 ，就是进程间所谓的“间接制约”关系。 .例8-1 ：p2读balan

5、ce的值（应该和p1读出的值一 样）到R1，读x2的值到R2，然后计算（在寄存器R1里的）balance和（在寄存器R2里 的）x2的差，并将这个差值（在寄存器R1里）回存到变量balance； p1中断时，运行现场寄存器（R1、R2） 里的值被保存到PCB1中； P1的执行： load R1, balance load R2, x1add R1, R2 store R1, balance 时钟中断P2的执行： load R1, balance load R2, x2 sub R1, R2 store R1, balance 时钟中断. 代码单独执行时，都会正确地工 作。关键是如果两个进程在系

6、统中并 发地运行，就可能会发生灾难性的错 误。比如如果两个进程的执行有如图 所示的顺序。 . 这时，p1在执行到指令：“load R2, x1”后， 被时钟中断。随后调度到p2执行。在这个特定的 运行情景下，会发生下面的动作序列： (1)(2)(3) 又由于时钟中断，使p1最终得到执行，依据PCB1恢复寄存器R1和R2后，计算 （在寄存器R1里的）balance与（在寄存器R2里的）x1的和，但因为balance还是p2执 行前被保存在寄存器R1里的旧值，因此计算时并没有考虑到p2已经把它改变了； (4) 最后的结局是balance里面的值没有正确反映出用户存、取款的情况。 . 进程间因资源共

7、享（这里的资源体现为是一个公共变量）而产生间接制约关系时， 它们随意的并发执行顺序不可能保证运行结果的正确。 互斥：如果有一个进程在临界区内执行，欲进入临界区的其他进程只能在临界 区外等待进入。 2. 互斥和临界区 例8-1中的进程p1和p2之所以会出问题，不在于它们个体的行为，它们 的个体行为都是没有问题的（p1和p2的程序编写是正确的），问题在于“共 享”，在于大家都要竞争使用这种共享的资源。 .计算机中，凡涉及共享变量、共享内存区、共享队列（如就绪队列）、共享文件 及共享任何资源的情况时，都有可能引发类似的问题。既要允许进程共享资源，又要阻 止错误的发生，唯一的办法是保证进程“互斥”地使

8、用资源，即确保当一个进程在使用一 个共享资源时，其他进程不能同时去使用。 . 进程程序中，涉及访问共享资源的程序段，称为“临界区（CS）”，只能排他使用 的资源称为“临界资源”。 为了保证在临界资源上操作的正确性，需遵循下面的3个要求： .(1)(2) 有空让进：如果没有进程在临界区、且有进程希望进入临界区，那么应该立即 允许其中的一个进程进入临界区。 (3) 有限等待：进入临界区的进程，应在有限时间内完成并立即离开临界区，以便 能够让其他的进程有机会进入临界区。 请求进入临界区的代码段，称为“进入区”，任务是判定是否有进程在临界区里。 如果有，则等待进入；否则才能允许进入临界区;如果可以进入

9、则必须设置临界区使用 标志，阻止它后来的进程进入临界区，后来的进程通过查看临界区的使用标志，知道自 己不能进入临界区，就进入阻塞队列将自己阻塞 。 .如图所示，给出了临界区互斥时进程的行为。进程A在时刻T1进入临界 区。稍后，在时刻T2进程B试图进入临界区。但是由于进程A已经在临界区 内，因此进程B被阻挡不得进入，直到时刻T3进程A离开临界区，进程B才 被允许进入临界区，并在时刻T4离开临界区。 进程A：进程B：A进入临界区A离开临界区B试图进 入临界区B进入 临界区B离开 临界区T1T2T3T4时间B被阻塞.因此，如果进程程序中有临界区，那么其设计应该包括如下的三个部分： (1)(2)(3)

10、请求退出临界区代码段，称为“退出区”，任务是修改临界区使用标志，判定是否 有进程在等待进入临界区。如果有，就要唤醒它们，给予进入的机会。 其他代码段。 返回目录可把一个访问临界资源的循环进程描述如下：repeatcritical section;remainder section;until false; entry sectionexit section访问临界资源的代码叫做临界区，进入临界区之前的 检查临界资源状态的代码区域叫做进入区，退出临 界区之后，修改临界区访问标志的叫做退出区。GET：负责从文件F中按照顺序 读出记录，送到输入缓冲区R； o8.1.2 同步 1.为保证任务的顺利进行

11、，有时必须协调进程相互间使用资源的顺序：在 一些进程没有使用该资源前，另一些进程不能使用该资源。即必须保证一些进程先使 用资源，另一些进程才能使用该资源，否则进程的执行就要出现问题。这种由于进程 间使用资源次序而产生的制约，就是进程间的所谓“直接制约”关系。 进程间的直接制约关系 .例8-2 ： 编写复制n个记录的程序，它把文件F中的记录依次先读到输入缓冲区R，再 从R拷贝到输出缓冲区T，最后写到文件G中。假定R和T的大小正好存放一个记录，如 图所示。 记录1记录2记录nGETCOPYPUT文件F记录1记录2记录n文件G输入缓冲区R输出缓冲区T解： 可编写三个进程GET、COPY、 PUT互相

12、配合完成这一工作： (1)(2) COPY：负责把输入缓冲区R中 的记录拷贝到输出缓冲区T中； (3) PUT：负责从输出缓冲区T中读 出一个记录，然后依照顺序写入文件 G。 记录3记录4记录n文件F记录2记录1文件GRT记录1GETPUT记录1记录1文件GRT记录3记录4记录n文件F记录1记录4记录n文件F记录3记录1文件GRT记录1COPY记录1记录4记录n文件F记录3记录3文件GRT记录1123(2)(3)(1)(4)若不管GET、COPY、PUT的执行关系，那么可有六种执行可能：1）COPYPUTGET；2）COPYGETPUT；3）PUTCOPYGET4）PUTGETCOPY；5）G

13、ETCOPYPUT；6）GETPUTCOPY.对第六种情况的分析2. 同步 . 所谓“同步”，是指某进程执行到一点时，若有关进程已完成某种操作， 那么该进程就可运行下去；否则必须暂停下来，等待有关进程操作的完成， 然后才继续运行。暂停下来等待的那点，称为“同步点”；等待完成的操作， 称为“同步条件”。这时称该进程要与有关进程在同步点取得同步。 如图所示，给出了进程间同步时的行为。进程A执行到点X处时，要与进程B取得 同步；进程B执行到点Y处时，为进程A准备好了同步条件。为此，在进程A执行到点X时 ，若进程B还没有越过点Y，那么进程A就须在X处阻塞，等待进程B为准备好条件；若进 程A执行到点X前

14、，进程B已越过点Y，那么进程A就可不受阻挡地一直执行下去。 .进程A：进程B：X同步点同步条件Y. 日常生活中，有很多同步的例子。比如工业生产的流水线上，上一道工序是为下 一道工序做准备，在上一道工序的半成品没有到达之前，下一道工序的工人只能处于等 待状态而无所事事。又比如，接力赛跑中，只有在接力区里下一棒运动员接过上一棒运 动员递过来的接力棒，才能奋力奔跑，否则就是犯规。 返回目录o硬件方法o软件方法o信号量方法o管程方法o消息传递方法8.2 实现互斥的方法讨论 一些计算机中有专门指令，功能是将内存单元的内 容读到寄存器中，然后往该单元里写入一个非零值，且 读和写操作是不可分割（即在一个指令

15、周期内完成）。 这种指令称为“测试并上锁（TSL）”。格式是： TSL R , xo8.2.1 实现互斥的硬件方法 1. 中断禁止 所谓“中断禁止”，是指进程以禁止中断的方法，构成临界区的 进入区；以开中断的方法，构成临界区的退出区。 . .进程程序关中断开中断临界区 进入区临界区 退出区临界区由于禁止中断后，时钟中断和其他中断都遭封杀，就不会发生 CPU进行进程切换的事情。所以，通过中断禁止的办法，完全不必 担心别的进程会进入临界区。这时程序的结构如图所示。 . 禁止中断对于操作系统来说是实现互斥的一项很有用 的技术。在系统内核中，利用它来保证访问共享资源的安 全是方便的。 2. 专用机器指令 TSL指令工作流程xR (将单元x内容读入寄存器R)1x (将数值1写入单元x)结束开始不可分割.enter_section : TSL R, x /* 将x的值读入R后设置为1 */CMP R, #1 /* R中的值为1? */JNE enter_section /* R中的值为1, 转enter_section */exit_section:MOVE x, #0 /* 把x设置为0 */临界区代码进入区退出区程序中可利用TSL指令形成临界区的进入区，确保