资源预览内容
第1页 / 共66页
第2页 / 共66页
第3页 / 共66页
第4页 / 共66页
第5页 / 共66页
第6页 / 共66页
第7页 / 共66页
第8页 / 共66页
第9页 / 共66页
第10页 / 共66页
亲,该文档总共66页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
Chap 6 Chap 6 进程同步进程同步6.2Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005内容内容n背景n临界区问题n信号量n经典同步问题n管程n同步实例n原子事务n总结6.3Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005背景背景n对共享数据的并发访问可能导致数据的不一致性.n要保持数据的一致性,就需要一种保证并发进程的正确执行顺序的机制.n第4章中解决有界缓冲区问题的共享内存方法在同一时刻最多允许存放n-1个产品,所有n个缓冲区都被使用的解法不是简单的。l假设通过增加一个变量counter来修改这一算法,初始化为0,每次向缓冲区增加一个新项时,counter递增;每次从缓冲区中移去一项时,counter递减。6.4Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005nShared data#define BUFFER_SIZE 10typedef struct . . . item;item bufferBUFFER_SIZE;int in = 0;int out = 0;int counter = 0;有界缓冲区有界缓冲区6.5Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n生产者进程item nextProduced;while (1) while (counter = BUFFER_SIZE); /* do nothing */bufferin = nextProduced;in = (in + 1) % BUFFER_SIZE;counter+;有界缓冲区有界缓冲区enterenter()()6.6Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n消费者进程item nextConsumed;while (1) while (counter = 0); /* do nothing */nextConsumed = bufferout;out = (out + 1) % BUFFER_SIZE;counter-; 有界缓冲区有界缓冲区removeremove()()6.7Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n下列语句必须被原子性地执行counter+;counter-;n原子操作意味着一个操作在整个执行期间没有中断。有界缓冲区有界缓冲区6.8Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n语句 “count+”可按如下方式以机器语言实现: register1 = counterregister1 = register1 + 1counter = register1n语句“count-”可按如下方式来实现:register2 = counterregister2 = register2 1counter = register2有界缓冲区有界缓冲区6.9Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n如果生产者和消费者试图并发地更新缓冲区,汇编语言语句可能交叉执行。n交叉取决于生产者和消费者进程是如何被调度的。有界缓冲区有界缓冲区6.10Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n假设counter初值为5. 一种语句的交叉形式如下:producer: register1 = counter (register1 = 5)producer: register1 = register1 + 1 (register1 = 6)consumer: register2 = counter (register2 = 5)consumer: register2 = register2 1 (register2 = 4)producer: counter = register1 (counter = 6)consumer: counter = register2 (counter = 4)ncount 的值可以是4或6,而正确结果应是5。有界缓冲区有界缓冲区6.11Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n竞争条件: 多个进程并发访问和操作同一数据的情况。共享数据的最终结果取决于最后操作的进程。n为了防止上述竞争条件,并发进程必须同步。竞争条件竞争条件Race ConditionRace Condition6.12Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005临界资源和临界区临界资源和临界区ncritical resource(临界资源)系统中某些资源一次只允许一个进程使用,称这样的资源为临界资源或互斥资源或共享变量。nCritical-Section(临界区)涉及到临界资源的代码段叫临界区。6.13Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005解决临界区问题解决临界区问题1. 互斥(Mutual Exclusion )。假定进程Pi在其临界区内执行,其他任何进程将被排斥在自己的临界区之外.2. 有空让进(Progress )。临界区虽没有进程执行,但有些进程需要进入临界区,不能无限期地延长下一个要进入临界区进程的等待时间.3.有限等待(Bounded Waiting) 。在一个进程提出进入临界区的请求和该请求得到答复的时间内,其他进程进入临界区前的等待时间必须是有限的.假定每个进程都以非零的的速率执行.没有任何关于这n个进程相对执行速率的假定.6.14Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005同步机制应遵循的准则同步机制应遵循的准则n空闲则入:其他进程均不处于临界区;n忙则等待:已有进程处于其临界区;n有限等待:等待进入临界区的进程不能死等;n让权等待:不能进入临界区的进程,应释放CPU(如转换到阻塞状态)6.15Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n只有2个进程, P0 和 P1nPi进程的通用结构do 进入区critical section退出区reminder section while (1);n进程可以共享一些公共变量来同步它们的行为。解决问题的初始尝试解决问题的初始尝试6.16Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n共享变量: lint turn;初始 turn = 0lturn = i Pi 能进入临界区lj = 1-in进程 Pido while (turn != i) ;临界区turn = j;剩余区 while (1);n满足互斥条件,但不满足有空让进算法算法1 16.17Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n共享变量lboolean flag2;初始 flag 0 = flag 1 = false.lflag i = true Pi 准备进入临界区n进程 Pido flagi := true;while (flagj) ;critical sectionflag i = false;remainder section while (1);n满足互斥,但不满足有空让进需求。算法算法2 26.18Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n合并算法 1和 2的共享变量.n进程 Pido flag i:= true;turn = j;while (flag j and turn = j) ;critical sectionflag i = false;remainder section while (1);n满足三个需求;解决了两个进程的临界区问题。算法算法3 36.19Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n在进入临界区前,每个进程接收一个号码。具有最小号码的进程进入临界区。n如果进程Pi和Pj接收到同样的号码,如果i j ,则Pi先得到服务,否则Pj先得到服务。n这种号码方案总是以递增序列产生号码;如: 1,2,3,3,3,3,4,5.多进程临界区问题:面包店算法面包店算法6.20Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n定义如下符合,按字典顺序 (ticket #, process id #)l若a c ,(a,b) (c, d) ,或若 a = c 和b dlmax (a0, an-1) 是数字 k, 从而 k ai ,对 i = 0, , n 1n共享数据:boolean choosingn;int numbern; 这些数据结构分别被初始化为false和0 面包店算法面包店算法6.21Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005do choosingi = true;numberi = max(number0, number1, , number n 1)+1;choosingi = false;for (j = 0; j n; j+) while (choosingj) ; while (numberj != 0) & (numberj,j numberi,i) ;critical sectionnumberi = 0;remainder section while (1);面包店算法面包店算法6.22Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005n原子地检查和修改
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号