第5章 并发性：互斥和同步

《第5章 并发性：互斥和同步》由会员分享，可在线阅读，更多相关《第5章 并发性：互斥和同步（54页珍藏版）》请在文档大全上搜索。

1、第5章 并发性：互斥和同步 主要内容 5.1 并发的原理 5.2 互斥：硬件的支持 5.3 信号量 5.4 管程 5.5 消息传递 5.6 读者/写者问题1与并发相关的关键术语 原子操作 保证指令序列要么作为一个组来执行，要么都不执行； 临界区 一段代码，在这段代码中进程将访问共享资源，当一个进程已经在这段代码中运行时，另外一个进程就不能在这段代码中执行； 死锁 两个或两个以上的进程因其中的每个进程都在等待其他进程做完某些事情而不能继续执行； 活锁 两个或两个以上进程为了响应其他进程中的变化而持续改变自己的状态但不做有用的工作；2与并发相关的关键术语 互斥 当一个进程在临界区访问共享资源时，其

2、他进程不能进入该临界区访问任何共享资源； 竞争条件 多个线程或进程在读写一个共享数据时，结果依赖于它们执行的相对时间； 饥饿 一个可运行的进程被调度程序无限期地忽略，不能被调度执行的情形。35.1 并发的原理1、基本概念 并发 单处理器多道程序设计系统中，进程交替执行； 并行 多处理器系统中，不仅可以交替执行进程，还可以重叠执行进程。 并发问题 并发进程的相对执行速度是不可预测的，取决于其他进程的活动、操作系统处理中断的方式以及操作系统的调度策略。 可能发生各种与时间有关的错误。4（结果不唯一）机票问题/飞机票售票问题 void T1( ) void T2( ) 按旅客订票要求找到Aj; 按旅

3、客订票要求找到Aj; int X1=Aj; int X2=Aj; if(X1=1) if(X2=1) X1-; X2-; Aj=X1; Aj=X2; 输出一张票; 输出一张票; else else 输出信息票已售完; 输出信息票已售完; 56T1T1、T2T2并发执行，可能出现如下交叉情况：并发执行，可能出现如下交叉情况：T1:X1=Aj; /X1=mT1:X1=Aj; /X1=mT2:X2=Aj; /X2=mT2:X2=Aj; /X2=mT2:X2-;Aj=X2;T2:X2-;Aj=X2;输出一张票输出一张票; /Aj=m-1; /Aj=m-1T1:X1-;Aj=X1;T1:X1-;Aj=X

4、1;输出一张票输出一张票; /Aj=m-1; /Aj=m-1同一张票卖给两位旅客（若只有一张余票）或者余同一张票卖给两位旅客（若只有一张余票）或者余票数不正确（若有多张余票）。票数不正确（若有多张余票）。（永远等待）主存管理问题申请和归还主存资源问题 int X=memory; /memory为初始主存容量 void borrow(int B) void return(int B) while(BX) X=X+B; 进程进入等待主存资源队列; 修改主存分配表; X=X-B ; 释放等主存资源进程; 修改主存分配表， 进程获得主存资源; 78若对若对borrowborrow和和returnret

5、urn的并发执行不加限制将会导致的并发执行不加限制将会导致错误，例如：错误，例如：Borrow:while(BX);Borrow:while(BX);Return:X=X+B;Return:X=X+B;修改主存分配表修改主存分配表;释放等待主存释放等待主存资源的进程资源的进程 ；此时，因为此时，因为borrowborrow还没有进入等待队列，因此，还没有进入等待队列，因此，returnreturn的释放操作是空操作，当的释放操作是空操作，当borrowborrow进入等待队进入等待队列时，可能没有进程再来归还，处于永远等待状态列时，可能没有进程再来归还，处于永远等待状态。2、操作系统关注的问题

6、 并发带来的设计和管理问题： 操作系统必须能跟踪不同的进程； 操作系统必须为每个活跃进程分配和释放各种资源； 操作系统必须保护每个进程的数据和物理资源； 一个进程的功能和执行结果必须与执行速度无关。93、进程的交互 进程间的资源竞争 互斥、死锁、饥饿 进程间通过共享合作 互斥、死锁、饥饿、数据一致性 进程间通过通信合作 死锁、饥饿104、互斥的要求 必须强制实施互斥； 一个在非临界区停止的进程不能干涉其他进程； 不允许出现需要访问临界区的进程被无限延迟的情况； 当没有进程在临界区时，任何需要进入临界区的进程必须能够立即进入； 对相关进程的执行速度和处理器的数目没有任何要求和限制； 一个进程驻留

7、在临界区中的时间必须是有限的。11解决互斥问题的方法 软件方法 由并发执行的进程担负解决问题的责任； 硬件方法 中断禁用 专用机器指令 操作系统或程序设计语言中提供某种级别的支持 信号量 管程 消息传递125.2 互斥：硬件的支持1、中断禁用 while (true) /* 禁用中断 */; /* 临界区 */; /* 启用中断 */; /* 其余部分 */; 问题： 代价非常高； 不能用于多处理器结构中。132、专用机器指令比较和交换指令int compare_and_swap (int *word, int testval, int newval)int oldval;oldval = *

8、word;if (oldval = testval) *word = newval;return oldval;14交换指令void exchange (int register, int memory)int temp;temp = memory;memory = register;register = temp;15互斥协议-比较和交换指令16互斥协议-交换指令17机器指令方法的优缺点 优点 适用于在单处理器或共享内存的多处理器上的任何数目的进程； 非常简单且易于证明； 可用于支持多个临界区，每个临界区可以用它自己的变量定义。 缺点 忙等待； 可能饥饿； 可能死锁。185.3 信号量 19

9、65年E.W.Dijkstra提出了新的同步工具-信号量。 基本原理 两个或多个进程通过简单的信号进行合作，一个进程被迫在某一位置停止，直到它接收到一个特定的信号。 任何复杂的合作需求都可以通过适当的信号结构得到满足。19信号量 信号量是一个与队列有关的整型变量。 可以初始化成非负数； semWait操作使信号量减1。若值为负数，则执行semWait的进程阻塞，否则继续执行； semSignal操作使信号量加1。若值小于或等于0，则被semWait操作阻塞的进程被解除阻塞。20信号量的值信号量的值(-2)(-2) 信号量队列指针信号量队列指针信号量原语的定义215.3.1 互斥22互斥的例子2

10、35.3.2 生产者/消费者问题 问题描述： 有一个或多个生产者生产某种类型的数据，并放置在缓冲区中； 有一个消费者从缓冲区中取数据，每次取一项； 系统保证避免对缓冲区的重复操作，即任何时候只有一个主体（生产者或消费者）可以访问缓冲区。 缓存已满时，生产者不能继续添加数据； 缓存已空时，消费者不能继续移走数据。241、无限缓冲区的生产者/消费者问题producer:while (true) /* produce item v */bin = v;in+; 25consumer:while (true) while (in = out) /*do nothing */;w = bout;out+

11、; /* consume item w */无限缓冲区26使用信号量解决无限缓冲区生产者/消费者问题27semaphore n=0,s=1;semaphore n=0,s=1;void producer()void producer() while (true) while (true) produce(); produce(); semWait(s); semWait(s); append(); append(); semSignal(s); semSignal(s); semSignal(n); semSignal(n); void consumer()void consumer() wh