《操作系统备课课件ch06》由会员分享，可在线阅读，更多相关《操作系统备课课件ch06（66页珍藏版）》请在金锄头文库上搜索。
1、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第
2、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 bufferBUFFE
3、R_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+;有界缓冲区有界缓冲区ente
4、renter（）（）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 2005Op
5、erating 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语句“coun
6、t-”可按如下方式来实现：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 Conce
7、pts 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: c
8、ounter = 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 2005Op
9、erating 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 )。假定进程P
10、i在其临界区内执行，其他任何进程将被排斥在自己的临界区之外.2. 有空让进(Progress )。临界区虽没有进程执行，但有些进程需要进入临界区，不能无限期地延长下一个要进入临界区进程的等待时间.3.有限等待(Bounded Waiting) 。在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区前的等待时间必须是有限的.假定每个进程都以非零的的速率执行.没有任何关于这n个进程相对执行速率的假定.6.14Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 8, 2005
11、同步机制应遵循的准则同步机制应遵循的准则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进程可以共享一些公共变量来同步它们的行为。解决
12、问题的初始尝试解决问题的初始尝试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 Concept
13、s 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
14、 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如果
15、进程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,
16、 , 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原子地检查和修改
