操作系统还行的课件os006

1、Operating SystemSynchronization OutlineConcept of Synchronization 同步概念Mutual Exclusion & Critical Section 互斥&临界区Implementation of Mutual Exclusion 互斥的实现What we have learnedUp till now, weve studied the concepts of Processes and Threads我们已经介绍进程和线程的概念We have seen OS kernel as a manager of variant appl

2、ication tasks with the pool of Processes and Threads我们把操作系统内核通过若干的进程和线程结构来维护和管理在计算机系统上运转的一个个应用任务Each Process is treated as an independent individual, while each thread is seen as an individual unit of code execution现在，我们还是把每个进程看作是一个独立的资源实体，而将每一个线程是看作一个个独立的代码执行单位However, it is very unlikely that ever

3、y task is totally independent from the other ones但是，在实际的应用环境中，任意两个计算任务都是完全独立的可能几乎是没有的It is very common that they may interact with each other in some specific ways任务之间存在交互是再常见不过的事情比方说，上课，整个学校可以看作是一个大的操作系统，其主要的任务是为上课这个进程（Process）分配教室、老师、学生等，在2013-03-14, 上午8:00-11:25，B202教室是我们占领的如何与进程概念的对应呢？上课自习打盹这时候，

4、除了这一个进程，其他进程是不可以在这里进行的所以，关上门这里是，若干个都要用到教室这一资源的进程之间有冲突，而B202教室在同一时段最多只能由一个进程占用= 互斥关系饭店吃饭，服务员视为一个服务进程S, 顾客视为一个进程C，那么服务员必须首先把菜单交给顾客，顾客才能够进行点菜（先后关系1）顾客点好菜后，服务员才能够招呼厨房做菜（先后关系2）= 同步关系Now, Lets get back to track, and talk about the OS现在还是回到操作系统的框架下来讨论上述两个问题Exclusion(互斥）Example: Two process, have a shared v

5、ariable x例如：两个进程，有一个共享变量xP1: if(x=100) x-=100; P2: if(x100) x-=100; 可以想像为从银行取钱The Problem进程P1if(x=100);进程P2If(x=100) 进程P1 X-=100;进程P2 X-=100;The case of synchronization同步的情形P1: clear obstacle obstacle_cleared=trueP2: encounter the obstacle while(obstacle_encounter=false) ; drive onobstacle_cleared =

6、 false临界资源的概念When referring to “Mutual Exclusion”, we must first talk about resource讨论“互斥”这个概念的时候，不可避免地要说到“临界资源”这个问题Mutual Exclusion happens due to a certain kind of resources , which is called exclusive resource互斥是由一类资源引发，我们把这类资源称之为临界资源What is Exclusive Resource?何谓临界资源？ 多个进程争用同一个共享资源任何时刻，最多只能有一个进程在

7、使用该资源Examples of Exclusive Resources临界资源实例 一些独占设备，如打印机、磁带机等 共享的数据：变量、表格、链表等Critical Section(临界区)Critical Section is a code segment that can modify a shared data临界区 = 一段可能对某个共享的数据进行修改的一段代码What happens in a Critical Section?（临界区内会发生怎样的事情？）Modify a shared variable(修改某个共享变量)Update a table(更新一个表)Write to

8、 a file(把数据写回一个文件)The behavior of Critical Section（临界区的特征）When one process is in the critical section, there can be no other process to be able to get in the critical section当有一个进程在临界区内执行的时候，任何其他的进程都不可以再进入临界区执行(如果多个进程在同时竞争进入同一个临界区，那么它们之间属于“互斥”关系)Pseudo code for Critical SectionNormally, the access t

9、o the Critical Section can be described using the following pseudo code:通常，对于临界区的访问可以通过以下的伪代码进行描述：repeat 进入区； 临界区； 退出区； 剩余区；until false;拿一个独占房子的例子来类比说明一下各个区的代码的用处repeat 检查房间，如果无人，进房间， 锁门 占用房间这一资源，做任何事 打开门，出去 在房间外做一些事情until false;Definition of Mutual ExclusionDefinition of Mutual Exclusion互斥的定义一组并发进程

10、中的一个或多个程序段，因共享某一共有资源而导致他们必须以一个不允许交叉执行的单位执行进程A: do_something() print(DocA) do_something() print(DocB)进程B: do_something() print(DocC) do_something() print(DocD)标出来的print函数都属于临界区代码，进程A和进程B的print调用代码之间必须互斥执行OutlineConcept of SynchronizationMutual Exclusion & Critical SectionImplementation of Mutual Excl

11、usionAfter the discussion of the concept of Mutual Exclusion, lets now think about the implementation method of the mutual exclusion mechanism讨论完互斥的概念及其定义之后，让我们再来看一看互斥机制的实现方法Here, you need to think of Critical Section in more detail, in order to understand the implementation details of Mutual Exclus

12、ion Mechanism必须再深入考虑一下临界区的特点，才能更好地理解“互斥”机制的实现方法Mutual ExclusionTo implement the mutual exclusion mechanism = write correct critical section code实现互斥机制，也就是说如何写出正确的临界区代码The three requirements for Critical Section(临界区的三大要求)最基本的要求：互斥前进：空闲让进有限等待：要控制进程从作出进入临界区选择到请求被允许的过程中，其他进程被允许进入该临界区的次数（避免进程等待时间过长）The C

13、ritical-Section Problem: Solution由竞争各方平等协商引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：software approaches （用编程解决，但常常忙等待）Hardware approaches （当一个进程进入临界区，就屏蔽所有中断）Semaphores 信号量Monitors 管程software approaches平等互斥基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志其中的主要问题是设置什么标志和如何检查标志实现临界区的方法1. 两进程解法(P0,P1)（1）让两个

14、进程共享一个普通整数变量turn，其初值为0(或1)If turn=i , then Pi允许在Critical Section内执行do while(turn!=i); turn = j; 剩余区while(1);进程Pi的结构其中j=1-iTurn=0, 并且p1就绪要进入临界区尽管P0此时有可能处于剩余区，P1也必须等待（违背了空闲让进的精神）（2）算法2：用数组boolean flag2来替代共享变量turn算法1的问题在于它没有记住每个进程状态的足够信息在P0实际不处于临界区执行时，也有可能阻碍P1进入临界区do flag i =true; while(flag j ); 临界区 f

15、lag i =false; 设置flagi为真，表示Pi准备进入临界区检查Pj是否也准备进入临界区如果Pj准备进入，Pi等待如果Pj不准备进入，Pi进入临界区表明Pi已经退出临界区进程Pi的结构（其中j=1-i）算法（2）中存在问题要始终记得，P0、P1是并发执行的两个进程我们来看一下下面这个执行顺序T0: P0置flag0=trueT1:P1置flag1=true结果会怎样？OK, 大家都进不去了，也都无法再往下推进执行即使互换设置flagi与检查flag j的语句，问题也得不到解决do flag i=true while(flagj); 临界区 flag i=false; 进程Pi的结构（

16、其中j=1-i）算法3：在进程P0，P1之间设置两个共享变量Boolean flag2;Int turn;do flagi=true turn = j while(flag j & turn=j); 临界区 flagi=false; Turn的值设置为j，表示如果进程Pj希望进入临界区，那么它能够进入同时Pj也可能会设置turn=i，但是最终保留的turn值会是1个证明算法3满足临界区的要求1.互斥只有当flagj=false，或turn=i时，Pi才能进入临界区当flag0=flag1=true时，P0,P1的循环条件肯定只能有一个被满足2.前进条件满足（空闲让进）可以证明，只要P0不被允许

17、进入，那么P1必定可以进入；反之依然3.有限等待条件满足Pi最多等待Pj一次之后即可进入临界区解决多线程同步的面包店算法该算法的基本思想源于顾客在面包店中购买面包时的排队原理。顾客在进入面包店前, 首先抓一个号, 然后按照号码由小到大的次序依次进入面包店购买面包. 这里, 面包店发放的号码是由小到大的, 但是两个或两个以上的顾客却有可能得到相同的号码(使所抓号码不同需要互斥), 如果多个顾客抓到相同的号码, 则规定按照顾客名字的字典次序进行排序, 这里假定顾客是没有重名的. 在计算机系统中, 顾客就相当于进程, 每个进程有一个唯一的标识, 我们用P的下面加一个下标来表示. 例如: 对于 Pi和

18、Pj, 如果有ij, 则先为Pi服务, 即Pi先进入临界区.解决多线程同步的面包店算法该算法的实现需要如下两个数据结构:int choosingn；int numbern；前者表示进程是否正在抓号，正在抓号的进程choosingi为1，否则为0, 其初值均为0. 后者用来记录各个进程所抓到的号码, 如numberi为0, 则进程Pi没有抓号, 如numberi不为0, 则其正整数值为进程Pi所抓到的号码, 其初值均为0. 为了方便起见, 我们定义下述表记法: (a,b)(c,d) 如果 ac or (a=c and b等待叫号do choosingi=1; numberi=max(number

19、0,numbern-1)+1; choosingi=0; for(j=0;jn;j+) while(choosing j); /waituntilthreadjreceivesitsnumber while(number j!=0) &(number j,j)(number i,i);/waituntilthreadswithsmallernumbers /orwiththesamenumber,butwithhigher /priority,finishtheirwork 临界区 numberi=0; 剩余区while(1);当numberinumberj, 结果为true;当numberj

20、=numberi，且ji，结果为trueSynchronization hardware(同步硬件)You can see that correct software solution for mutual exclusion is very time-consuming(costly)你可以看到，对互斥的正确软件实现算法（面包店算法）是非常耗时的 Modern hardware provide many simple hardware instructions, which can used to effectively solve the Critical Section Problem现

21、代的计算机系统都会提供简单的硬件指令，使用这些指令能够有效地解决临界区问题互斥的加锁实现解决思想设定监控变量（lock），通过其值变化控制进程操作进程AWhile(lock != 0) NULL;lock 1;Critical_region();lock 0；进程BWhile(lock != 0) NULL; lock = 1;Critical_region();lock = 0;lock 0互斥问题的最难解决的问题是判断进入临界区，同时设置本进程已经进入临界区的状态，这两个操作之间可能存在时间窗比如，对互斥最直观的实现方式是如下的加锁方式锁变量的缺陷示例进程AWhile(lock != 0)

22、;进程BWhile(lock != 0); lock 0进程Alock 1;Critical_Region();进程Block = 1;Critical_Region();发生进程调度，互斥的进程开始运行发生进程调度，A并不知道B也进入临界区发生进程调度，B并不知道A也进入临界区在检查临界区是否被上锁（while循环），以及获准进入后上锁(lock=1)之间存在一个时间窗硬件的解决思路保证While(lock!=0)与lock=1之间没有其他指令插进来While(lock!=0);Lock=1;InstX这两条指令合成一块，有个名词称呼它，唤作：原子操作（Atomic Operation）硬件

23、提供一个TestAndSet指令，来实现上述原子指令的功能使用TestAndSet来处理上述临界区问题，得到lock 0do while(TestAndSet(lock); 临界区 lock=false; boolean TestAndSet(boolean *target)boolean rv = *target;*target = true;return rv;Critical Section can be protected by a lock临界区是可以通过锁来保护的使用TestAndSet指令的互斥实现do while(TestAndSet(lock); 临界区 lock = fal

24、se; 剩余区；while(1);满足临界区条件(1)和(2):互斥-空闲让进不满足临界区条件（3）：非有限等待改进算法do waitingi = true key = true; while(waitingi&key) key=TestAndSet(lock); waitingi=false; 临界区 j=(i+1)%n; while(j!=i & !waitingj) j = (j+1)%n; if(j=i) lock = false; else waitingj = false; 剩余区while(1);表示进程Pi处于等待获取锁的状态如果进程Pi抢到了锁，记录key=false进程Pj处于等待获取锁的状态do waitingi = true key = true; while(waitingi&key) key=TestAndSet(lock); waitingi=false; 临界区 j=(i+1)%n; while(j!=i & !waitingj) j = (j+1)%n; if(j=i) lock = false; else waitingj = false; 剩余区while(1);临界区条件1：互斥 第一个进入的进程Pi要等执行了TestAndSet之后才能进入，这时Pi的key=false,其他进程key=true