进程同步.ppt

《进程同步.ppt》由会员分享，可在线阅读，更多相关《进程同步.ppt（109页珍藏版）》请在三一办公上搜索。

1、进程同步,四川大学软件学院 左劼,背景,并发(concurrent)地访问共享数据可能会引起数据不一致(inconsistency)维护数据的一致性需要某种机制保证协作进程有序地执行很多基于共享内存的解决方案都存在竞争条件(race condition),有限缓冲区问题,public class BoundedBuffer public void enter(Object item).public Object remove().private volatile int count=0;private int in=0;private int out=0;private Object buff

2、er=new ObjectBUFFER_SIZE;,enter()方法,public void enter(Object item)while(count=BUFFER_SIZE);+count;bufferin=item;in=(in+1)%BUFFER_SIZE;,remove()Method,public Object remove()while(count=0);-count;Object item=bufferout;out=(out+1)%BUFFER_SIZE;return item;,问题,当生产者和消费者并发地执行的时候，他们可能不能得到正确的结果！例如：如果count=5，

3、那么执行+count和-count后，count的值可能是4、5或者6！原因:共享变量count被两个线程并发地访问并修改了,分析,共享变量count的修改:语句+count 会被实现为下面的机器代码:register1=countregister1=register1+1count=register1语句-count 会被实现为下面的机器代码:register2=countregister2=register2 1count=register2注意：这里的register1和register2是本地寄存器,分析,如果生产者和消费者试图并发地更新缓冲区，那么底层的机器代码可能会交错地执行具体如

4、何交错，和两个进程如何被调度有关,一个例子(假设count=5),T0:生产者:r1=count(r1=5)T1:生产者:r1=r1+1(r1=6)T2:消费者:r2=count(register2=5)T3:消费者:r2=r2 1(r2=4)T4:生产者:count=r1(count=6)T5:消费者:count=r2(count=4)于是 count=4如果交换 T4 和 T5，那么 count=6但是，正确的结果应该是 count=5,竞争条件,多个进程并发地访问和操作共享数据且执行结果和访问发生的特定顺序有关，称为竞争条件同步为了避免竞争条件，并发的进程需要同步，以保证同时只有一个进程

5、操纵共享变量原子操作 一个操作在执行过程中不会被打断为了避免竞争条件，一些语句应该被原子化地执行,临界区问题(critical section),假设有n个进程竞争使用一些共享数据每个进程有一个特殊的代码段，称为临界区。在临界区中执行访问、操纵共享数据的动作必须保证，进程的临界区地执行是互斥的，即当一个进程在临界区内，其他的进程就不允许进入到临界区中,解决临界区问题,互斥：当一个进程在临界区内，其他的进程就不允许进入到临界区中有空让进：如果没有其他的进程在临界区内执行，并且有进程希望进入临界区，那么选择谁能下一个进入临界区的工作不能无限推迟有限等待：在一个进程做出进入其临界区的请求到该请求被允

6、许期间，其它进程被允许进入其临界区的次数存在一个上限,注意,假设每一个进 程的执行速度不为0不能对n个进程的线对速度做假设基本机器指令的执行是原子的如果两个机器指令在两个不同的CPU上并发执行，结果相当于以不确定的顺序顺序执行的结果,临界区的两进程解法,讨论临界区问题用于两个进程的算法两个进程标为P0和P1为方便起见，当用Pi表示一个进程的时候，用Pj表示另外一个进程，即j=1-i,临界区的两进程解法,public class Worker extends Thread public Worker(int i,MutualExclusion s)id=i;shared=s;public voi

7、d run().private int id;private MutualExclusion shared;,run()方法,public void run()while(true)/enter critical section shared.enter(id);./leave critical section shared.leave(id);,MutualExclusion 类,public abstract class MutualExclusion public static void criticalSection()/simulate the critical section pu

8、blic static void nonCriticalSection()/simulate the non-critical section public abstract void enter(int t);public abstract void leave(int t);public static final int TURN_0=0;public static final int TURN_1=1;,测试每一种算法,public class TestAlgorithm public static void main(String args)MutualExclusion alg=ne

9、w Algorithm_1();Worker first=new Worker(0,alg);Worker second=new Worker(1,alg);first.start();second.start();,算法0 一个最容易想到的算法,public class Algorithm_0 extends MutualExclusion public Algorithm_0()flag=false;public void enter(int t)while(flag)Thread.yield();flag=true;public void leave(int t)flag=false;p

10、rivate volatile boolean flag;,算法0分析,算法0不能保证互斥访问当P0和P1几乎同时希望进入临界区的时候，如果调度合适，他们都会看到flag标志为false，于是都会设置标志为true，然后进入临界区,算法1,public class Algorithm_1 extends MutualExclusion public Algorithm_1()turn=TURN_0;public void enter(int t)while(turn!=t)Thread.yield();public void leave(int t)turn=1-t;private volat

11、ile int turn;,算法1分析,如果turn=i，那么允许Pi进入临界区 满足互斥访问保证只有一个进程可以进入临界区但不满足有空让进需要进程满足严格的交替进入临界区如果 turn=0 并且 P1 准备进入临界区，那么它并不能进入,算法2,public class Algorithm_2 extends MutualExclusion public Algorithm_2()flag0=false;flag1=false;public void enter(int t)int other=1-t;flagt=true;while(flagother=true)Thread.yield()

12、;public void leave(int t)flagt=false;private volatile boolean flag=new boolean2;,算法2分析,提供了充分的进程状态信息如果 flagi=true，表示 Pi 准备进入临界区满足互斥访问，但没有满足有空让进例如：P0 设置 flag0=true，恰好在 while 循环之前，发生上下文切换，P1 设置 flag1=true，于是 P0 和 P1 都要永远等待，没有哪个进程可以进入临界区,算法3,public class Algorithm_3 extends MutualExclusion public Algori

13、thm_3()flag0=false;flag1=false;turn=TURN_0;public void enter(int t).public void leave(int t).private volatile int turn;private volatile boolean flag=new boolean2;,public void enter(int t)int other=1-t;flagt=true;turn=other;while(flagother=true),算法3分析,Pi 设置 flagi=true，表示 Pi 希望进入临界区Pi 设置 turn=j，表示 Pi

14、希望应该轮到 Pj 进入临界区符合所有的三个要求，解决了两进程的临界区问题当 flagj=false(表示 Pj 不希望进入临界区)或者 turn!=j(例如 turn=i，表示仅仅允许 Pi 进入临界区)，于是 Pi 可以进入临界区先修改 turn 值的进程得到访问临界区的权利,同步硬件,仅仅通过软件实现的同步程序非常复杂，也容易出错，通过硬件功能的帮助，可以比较容易地实现符合要求的同步程序如何实现原子的硬件指令？单处理器环境中只要简单禁止中断就可以了但是在多处理环境中，就没有这么简单，禁止中断的工作需要传播到所有的处理器，需要处理器同步，导致效率降低,可用于同步的两条指令,许多系统提供了特

15、殊的可原子化执行的硬件指令用于实现进程同步检查和修改一个存储单元的内容test-and-set指令交换两个存储单元的内容swap指令,同步硬件结构示意代码 数据结构,HardwareData Class:public class HardwareData public HardwareData(boolean v)data=v;public boolean get()return data;public void set(boolean v)data=v;private boolean data;,test-and-set指令示意代码,public class HardwareSolution

16、 public static boolean testAndSet(HardwareData target)HardwareData temp=new HardwareData(target.get();target.set(true);return temp.get();,使用test-and-set指令实现互斥,HardwareData lock=new HardwareData(false);while(true)while(HardwareSolution.testAndSet(lock)Thread.yield();/do nothing/now in critical sectio

17、n code lock.set(false);/out of critical section,swap(交换)指令(示意代码),public static void swap(HardwareData a,HardwareData b)HardwareData temp=new HardwareData(a.get();a.set(b.get();b.set(temp.get();,使用swap指令实现互斥,HardwareData lock=new HardwareData(false);HardwareData key=new HardwareData(true);while(true)

18、key.set(true);do HardwareSolution.swap(lock,key);while(key.get()=true);/now in critical section code lock.set(false);/out of critical section,信号量(Semaphore),进程同步问题是一个大量存在的问题，应用中迫切需要一种通用的操作系统机制来简化进程同步的操作信号量就是其中的一种重要同步工具信号量是一个整数，除了初始化外，只能通过两个标准原子操作P和V来访问和修改(这两个操作也称为wait和signal),信号量的值,信号量的值是有实际意义的当信号量的

19、值大于0时，它表示，还可以无阻塞地执行多少次P操作当信号量的值小于0时，它的绝对值表示，有多少进程等待在该信号量的P操作上如果用一个信号量来同步共享资源，可以把信号量的初值设置为共享资源的数量,信号量上的操作,对于信号量S，操作P(S)、V(S)定义为：P(S)while(S=0);S-;V(S)S+;两个操作都是原子的,将信号量作为通用的同步工具,Semaphore S;/初始化为 1P(S);/临界区内部.V(S);,信号量中的忙等,P操作中，为了等待信号量的值变为正数，程序将进行连续的循环，这称为忙等，也称为自旋锁忙等白白浪费了CPU资源，而这些资源本来是可以被其他进程所使用的。所以，一

20、般来说，应该避免忙等，在等待的时候将CPU资源让给别的进程使用但忙等信号量也有其优点，因等待的时候不需要进行上下文切换，如果等待时间不长，可能效率还更高一些,避免信号量中的忙等,P(S)value-;if(value 0)add this process to list block V(S)value+;if(value=0)remove a process P from list wakeup(P);,使用信号量进行进程同步,public class FirstSemaphore public static void main(String args)Semaphore sem=new Se

21、maphore(1);Worker ws=new Worker5;for(int i=0;i 5;i+)wsi=new Worker(sem,i);for(int i=0;i 5;i+)wsi.start();,工作线程,public class Worker extends Thread public Worker(Semaphore s,int id)sem=s;this.id=id;public void run()while(true)sem.P();/in critical section sem.V();private Semaphore sem;private int id;,关

22、于信号量,block 和 wakeup 操作是操作系统以基本系统调用的方式提供的信号量必须被原子化地执行，没有两个进程可以同时执行针对同一个信号量的P、V操作单处理器:P、V操作期间禁止中断多处理器:硬件解决方法：使用test-and-set指令软件解决方法：前面讨论的复杂方法,死锁,死锁：两个或多个进程无限地等待一个事件，而这些事件只能由这些等待进程之一来产生假设 S 和 Q 是初始化为 1 的两个信号量 P0 P1 P(S);P(Q);P(Q);P(S);V(S);V(Q);V(Q);V(S);,饿死(饥饿),饿死 无限期的阻塞。一个进程的等待条件得到满足，但仍然可能无限期地在信号量的等待

23、队列中等待这是一种设计缺陷，当系统不忙的时候，不会发生，但是系统很忙的时候，有些进程虽然已经满足了执行的条件，但仍然一直等待,两种类型的信号量,计数信号量 信号量的值跨越一个不受限制的范围二进制信号量 信号量值只能是0或者1二进制信号量很容易用硬件实现可以使用二进制信号量来实现计数信号量,经典进程同步问题,有限缓冲区问题(生产者-消费者问题)Bounded Buffer Problem读者-写者问题Readers and Writers Problem哲学家进餐问题Dining-Philosophers Problem,有限缓冲区问题,有一个或者多个进程是生产者，持续不断地产生数据有一个或者多

24、个进程是消费者，持续不断地消耗数据两者通过一个有限大小的缓冲区交换数据,有限缓冲区问题,生产者,消费者,有限缓冲区,消费者,生产者,消费者,.,.,问题分析,首先，对数据结构的修改不能同时进行，否则可能对结构产生破坏当缓冲区满了，生产者应该停下来等待当缓冲区空了，消费者应该停下来如果有多个消费者，不能相互影响(取到同一个数据),有限缓冲区问题,public class BoundedBuffer public BoundedBuffer().public void enter(Object item).public Object remove().private static final in

25、t BUFFER_SIZE=2;private Semaphore mutex;private Semaphore empty;private Semaphore full;private int in,out;private Object buffer;,构造函数,public BoundedBuffer()count=0;in=0;out=0;buffer=new ObjectBUFFER_SIZE;mutex=new Semaphore(1);empty=new Semaphore(BUFFER_SIZE);full=new Semaphore(0);,enter()方法,public

26、void enter(Object item)empty.P();mutex.P();/add an item to the buffer bufferin=item;in=(in+1)%BUFFER_SIZE;mutex.V();full.V();,remove()方法,public Object remove()full.P();mutex.P();/remove an item from the buffer Object item=bufferout;out=(out+1)%BUFFER_SIZE;mutex.V();empty.V();return item;,第一类读者-写者问题,

27、没有读者会保持等待状态，除非已经有写者获得了访问共享数据的权限或者:读者不会仅仅因为有写者在等待而等待问题:写者饥饿,第二类读者-写者问题,一旦写者准备就绪，尽快满足写者的写请求或者：如果写者在等待访问共享数据，那么新的读者就不能开始新的共享读问题：读者饥饿,读者,public class Reader extends Thread public Reader(Database db)server=db;public void run()int c;while(true)c=server.startRead();/now reading the database c=server.endRea

28、d();private Database server;,写者,public class Writer extends Thread public Writer(Database db)server=db;public void run()while(true)server.startWrite();/now writing the database server.endWrite();private Database server;,共享数据,public class Database public Database().public int startRead().public int e

29、ndRead().public void startWrite().public void endWrite()./number of active readers private int readerCount;/controls access to readerCount private Semaphore mutex;/controls access to the database private Semaphore db;,Database构造函数,public Database()readerCount=0;mutex=new Semaphore(1);db=new Semaphor

30、e(1);,startRead()方法,public int startRead()mutex.P();+readerCount;/对第一个读者 if(readerCount=1)db.P();mutex.V();return readerCount;,endRead()方法,public int endRead()mutex.P();-readerCount;/最后一个读者 if(readerCount=0)db.V();mutex.V();return readerCount;,写者方法,public void startWrite()db.P();public void endWrite

31、()db.V();,哲学家进餐问题,最简单的解法,分别用一个信号量表示每一根筷子，都初始化为1Semaphore chopStick=new Semaphore 5;P操作：拿起对应的筷子V操作：放下对应的筷子,哲学家 i,while(true)/get left chopstick chopSticki.P();/get right chopstick chopStick(i+1)%5.P();/eat for awhile/return left chopstick chopSticki.V();/return right chopstick chopStick(i+1)%5.V();/t

32、hink for awhile,解法分析,解法存在死锁的可能性！当所有5位哲学家同时想吃东西的时候，他们都拿起左边的筷子，但这是右边已经没有筷子了，全都只有等待，而都不能进餐如何解决？,修正死锁问题,通过限制哲学家的行为来避免死锁只允许最多4位哲学家同时进餐只有左右两边的筷子同时得到满足，哲学家才能够取得着两根筷子进餐使用一个非对称的算法，比如，让奇数号数的哲学家先取左边的筷子，而偶数号数的哲学家先取右边的筷子,信号量的优缺点,信号量的优点提供了一种方便、有效的进程公布机制信号量的缺陷不正确的使用可能会导致错误的结果，并且这种错误很难发现和排除不正确的使用信号量还可能导致死锁,错误使用信号量的

33、例子,对于一个临界区问题，正确的代码应该是：mutex.P();criticalSection();mutex.V();如果代码不正确，将可能导致各种不同情况的错误,错误代码,P()和 V()操作的顺序错了mutex.V();criticalSection();mutex.P();临界区根本没有得到保护都写成了 P()mutex.P();criticalSection();mutex.P();将会发生死锁,管程(monitors),管程是一种提供线程安全的高层次的抽象管程是一种抽象的数据结构，封装了一些私有数据，并提供了一些公有方法管程确保一个时刻只有一个线程可以在管程内活动配合条件变量，可以

34、使用管程解决进程同步问题,管程模型,monitor monitor-name/variable declarations public entry p1().public entry p2().,管程,封装限制了线程直接对管程内部的直接访问管程阻止了对管程内定义的方法的并发访问，一个时间内只有个线程或进程可以访问管程内定义的方法于是程序员不需要显式地对同步编码,管程,条件变量(condition),条件变量代表了一种条件，在上面只能进行两个操作wait和signal条件变量只能存在于一个管程中，并且只能从管程内的方法对它进行访问当一个线程调用x.wait的时候，就会被挂起，直到被其他线程调用x

35、.signal而唤醒x.signal 唤醒一个在x上挂起的线程，如果没有线程在x上挂起，操作不产生影响(和信号量的V()操作比较，它永远都产生影响),当线程因调用x.wait被挂起，那么该线程释放对管程的控制，而被其他线程调用x.signal唤醒，则要继续拥有对管程的控制如果挂起的线程Q被线程P唤醒了，那么必须决定线程P或者Q有一方要等待，直到对方退出管程,带有条件变量的管程,哲学家进餐问题的解法,monitor diningPhilosophers int state=new int5;static final int THINKING=0;static final int HUNGRY=1

36、;static final int EATING=2;condition self=new condition5;public diningPhilosophers for(int i=0;i 5;i+)statei=THINKING;public entry pickUp(int i).public entry putDown(int i).private test(int i).,pickUp()方法,public entry pickUp(int i)statei=HUNGRY;test(i);if(statei!=EATING)selfi.wait;,putDown()方法,publi

37、c entry putDown(int i)statei=THINKING;/test left and right neighbors test(i+4)%5);test(i+1)%5);,test()方法,private test(int i)if(state(i+4)%5!=EATING),哲学家i,dp.Pickup(i);eat();dp.putDown(i);,另外一种管程解法,monitor diningPhilosophers condition eat=new condition5;boolean chopstick=new chopstick5;public entry p

38、ickUp(int i).public entry putDown(int i).,pickUp 方法,public pickUp(int i)while(!(chopsticki,putDown 方法,public putDown(int i)chopsticki=true;chopstick(i+1)%5=true;eat(i+4)%5.signal();eat(i+1)%5.signal();,Java 中的线程同步机制,Synchronized,wait(),notify()Multiple NotificationsBlock SynchronizationJava Semaphor

39、esJava MonitorsJava同步机制是从管程衍生而来的，可以看成是只有一个条件变量的管程,同步方法(synchronized),每一个对象都有一个相连的锁调用同步的方法(synchronized)需要获得对象的锁如果已经有其他的线程获得了锁，线程将等待当线程退出同步方法将释放锁,入口队列,wait和notify方法,仅仅使用同步方法并不能实现复杂的同步问题和管程中的条件变量类似，Java中引入了对象上的wait()和notify()方法，其功能分别对应条件变量的wait和signal方法应该注意，管程中wait、signal是作用在条件变量上的，而Java中的wait和notify是

40、作用在对象上的,wait()方法,当一个线程调用对象的wait()方法，将会发生以下事件：线程释放对象的锁线程状态被设置为阻塞线程被放置到对象的等待队列,入口队列和等待队列,notify()方法,当一个线程调用对象的notify()，将发生下列事件：从对象的等待队列中任意选定一个线程T将线程T移动到入口队列将线程T的线程状态设置为就绪T 可以再次竞争获得对象的锁,用Java实现生产者-消费者问题,class BoundedBuffer public static final int BUFFER_SIZE=5;public synchronized void enter(Object item

41、).public synchronized Object remove().private Object buffer=new ObjectBUFFER_SIZE;private int count=0;private int in=0,out=0;,enter(),public synchronized void enter(Object item)while(count=BUFFER_SIZE)try wait();catch(InterruptedException e)+count;bufferin=item;in=(in+1)%BUFFER_SIZE;notify();,remove

42、(),public synchronized Object remove()while(count=0)try wait();catch(InterruptedException e)-count;Object item=bufferout;out=(out+1)%BUFFER_SIZE;notify();return item;,多重notification,notify()从等待队列中任意选择一个线程，也许这个线程并不是期望被选中的notify()并不能够指定特定的线程notifyAll()把等待队列中的所有线程都移动到入口队列中，这样线程可以自己决定哪一个线程应该下一个进行处理当等待队列

43、中有多个线程时，notifyAll()提供了一种保守策略，效果不错,用Java同步机制解决读者-写者问题,public class Database public Database()readerCount=0;writing=false;public synchronized int startRead().public synchronized int endRead().public synchronized void startWrite().public synchronized void endWrite().private int readerCount;private bool

44、ean writing;,startRead()Method,public synchronized int startRead()while(writing=true)try wait();catch(InterruptedException e)+readerCount;return readerCount;,endRead()Method,public synchronized int endRead()-readerCount if(readerCount=0)db.notifyAll();return readerCount;,Writer Methods,public void s

45、tartWrite()while(readerCount 0|writing=true)try wait();catch(InterruptedException e)writing=true;public void endWrite()writing=false;notifyAll();,同步块,可以同步仅仅一个代码块而不是整个函数Object mutexLock=new Object();.public void someMethod()/non-critical section synchronized(mutexLock)/critical section/non-critical s

46、ection,用 Java 实现信号量,Java语言中并没有提供信号量类，但使用Java的同步机制可以实现信号量,Semaphore 类,public class Semaphore public Semaphore()value=0;public Semaphore(int v)value=v;public synchronized void P().public synchronized void V().private int value;,P()操作,public synchronized void P()while(value=0)try wait();catch(InterruptedException e)value-;,V()操作,public synchronized void V()+value;notify();,Solaris 2 同步机制,adaptive mutexcondition variablessemaphoresreader-writer locks,Windows NT 同步机制,mutexcritical sectionssemaphoresevent objects,作业,7.2,7.5,7.7,7.10,7.11,