《进程同步.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; priv
2、ate Object buffer = 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
3、item; ,问题,当生产者和消费者并发地执行的时候,他们可能不能得到正确的结果! 例如:如果count=5,那么执行+count和-count后,count的值可能是4、5或者6! 原因: 共享变量count被两个线程并发地访问并修改了,分析,共享变量count的修改: 语句 +count 会被实现为下面的机器代码: register1 = count register1 = register1 + 1 count = register1 语句 -count 会被实现为下面的机器代码: register2 = count register2 = register2 1 count = reg
4、ister2 注意:这里的register1和register2是本地寄存器,分析,如果生产者和消费者试图并发地更新缓冲区,那么底层的机器代码可能会交错地执行 具体如何交错,和两个进程如何被调度有关,一个例子(假设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 (
5、count = 4) 于是 count = 4 如果交换 T4 和 T5,那么 count = 6 但是,正确的结果应该是 count = 5,竞争条件,多个进程并发地访问和操作共享数据且执行结果和访问发生的特定顺序有关,称为竞争条件 同步 为了避免竞争条件,并发的进程需要同步,以保证同时只有一个进程操纵共享变量 原子操作 一个操作在执行过程中不会被打断 为了避免竞争条件,一些语句应该被原子化地执行,临界区问题(critical section),假设有n个进程竞争使用一些共享数据 每个进程有一个特殊的代码段,称为临界区。在临界区中执行访问、操纵共享数据的动作 必须保证,进程的临界区地执行是互
6、斥的,即当一个进程在临界区内,其他的进程就不允许进入到临界区中,解决临界区问题,互斥:当一个进程在临界区内,其他的进程就不允许进入到临界区中 有空让进:如果没有其他的进程在临界区内执行,并且有进程希望进入临界区,那么选择谁能下一个进入临界区的工作不能无限推迟 有限等待:在一个进程做出进入其临界区的请求到该请求被允许期间,其它进程被允许进入其临界区的次数存在一个上限,注意,假设每一个进 程的执行速度不为0 不能对n个进程的线对速度做假设 基本机器指令的执行是原子的 如果两个机器指令在两个不同的CPU上并发执行,结果相当于以不确定的顺序顺序执行的结果,临界区的两进程解法,讨论临界区问题用于两个进程
7、的算法 两个进程标为P0和P1 为方便起见,当用Pi表示一个进程的时候,用Pj表示另外一个进程,即j=1-i,临界区的两进程解法,public class Worker extends Thread public Worker(int i, MutualExclusion s) id = i; shared = s; public void run() . private int id; private MutualExclusion shared; ,run()方法,public void run() while (true) / enter critical section shared.
8、enter(id); / leave critical section shared.leave(id); ,MutualExclusion 类,public abstract class MutualExclusion public static void criticalSection() / simulate the critical section public static void nonCriticalSection() / simulate the non-critical section public abstract void enter(int t); public ab
9、stract 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 = new Algorithm_1(); Worker first = new Worker(0, alg); Worker second = new Worker(1, alg); first.start(); se
10、cond.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; private volatile boolean flag; ,算法0分析,算法0不能保证互斥访问 当P0和P1几乎同时希望进入临界区的时候,如果调度合适,他们
11、都会看到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 volatile int turn; ,算法1分析,如果turn=i,那么允许Pi进入临界区 满足互斥访问 保证只有一个进程可以进入
12、临界区 但不满足有空让进 需要进程满足严格的交替进入临界区 如果 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(); public void leave(int t) flagt =
13、 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 Algorithm_3() flag0 = f
14、alse; 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 希望进入临界区
15、 Pi 设置 turn = j,表示 Pi 希望应该轮到 Pj 进入临界区 符合所有的三个要求,解决了两进程的临界区问题 当 flagj = false (表示 Pj 不希望进入临界区) 或者 turn != j (例如 turn = i,表示仅仅允许 Pi 进入临界区),于是 Pi 可以进入临界区 先修改 turn 值的进程得到访问临界区的权利,同步硬件,仅仅通过软件实现的同步程序非常复杂,也容易出错,通过硬件功能的帮助,可以比较容易地实现符合要求的同步程序 如何实现原子的硬件指令? 单处理器环境中只要简单禁止中断就可以了 但是在多处理环境中,就没有这么简单,禁止中断的工作需要传播到所有的处
16、理器,需要处理器同步,导致效率降低,可用于同步的两条指令,许多系统提供了特殊的可原子化执行的硬件指令用于实现进程同步 检查和修改一个存储单元的内容 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 da
17、ta; ,test-and-set指令示意代码,public class HardwareSolution 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.
18、testAndSet(lock) Thread.yield(); / do nothing / now in critical section 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
19、 lock = new HardwareData(false); HardwareData key = new HardwareData(true); while (true) 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),进程同步问题是一个大量存在的问题,应用中迫切需要一种通用的操作系统机制来简化进程同步的操
20、作 信号量就是其中的一种重要同步工具 信号量是一个整数,除了初始化外,只能通过两个标准原子操作P和V来访问和修改 (这两个操作也称为wait和signal),信号量的值,信号量的值是有实际意义的 当信号量的值大于0时,它表示,还可以无阻塞地执行多少次P操作 当信号量的值小于0时,它的绝对值表示,有多少进程等待在该信号量的P操作上 如果用一个信号量来同步共享资源,可以把信号量的初值设置为共享资源的数量,信号量上的操作,对于信号量S,操作P(S)、V(S)定义为: P(S) while (S = 0) ; S-; V(S) S+; 两个操作都是原子的,将信号量作为通用的同步工具,Semaphore
21、 S; / 初始化为 1 P(S); / 临界区内部 V(S);,信号量中的忙等,P操作中,为了等待信号量的值变为正数,程序将进行连续的循环,这称为忙等,也称为自旋锁 忙等白白浪费了CPU资源,而这些资源本来是可以被其他进程所使用的。所以,一般来说,应该避免忙等,在等待的时候将CPU资源让给别的进程使用 但忙等信号量也有其优点,因等待的时候不需要进行上下文切换,如果等待时间不长,可能效率还更高一些,避免信号量中的忙等,P(S) value-; if (value 0) add this process to list block V(S) value+; if (value = 0) remo
22、ve a process P from list wakeup(P); ,使用信号量进行进程同步,public class FirstSemaphore public static void main(String args) Semaphore sem = new Semaphore(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 Thre
23、ad 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; ,关于信号量,block 和 wakeup 操作是操作系统以基本系统调用的方式提供的 信号量必须被原子化地执行,没有两个进程可以同时执行针对同一个信号量的P、V操作 单处理器: P、V操作期间禁止中断 多处理器: 硬件解决方法:使用test-and-set指
24、令 软件解决方法:前面讨论的复杂方法,死锁,死锁:两个或多个进程无限地等待一个事件,而这些事件只能由这些等待进程之一来产生 假设 S 和 Q 是初始化为 1 的两个信号量 P0 P1 P(S); P(Q); P(Q); P(S); V(S); V(Q); V(Q); V(S);,饿死(饥饿),饿死 无限期的阻塞。一个进程的等待条件得到满足,但仍然可能无限期地在信号量的等待队列中等待 这是一种设计缺陷,当系统不忙的时候,不会发生,但是系统很忙的时候,有些进程虽然已经满足了执行的条件,但仍然一直等待,两种类型的信号量,计数信号量 信号量的值跨越一个不受限制的范围 二进制信号量 信号量值只能是0或者
25、1 二进制信号量很容易用硬件实现 可以使用二进制信号量来实现计数信号量,经典进程同步问题,有限缓冲区问题(生产者-消费者问题) Bounded Buffer Problem 读者-写者问题 Readers and Writers Problem 哲学家进餐问题 Dining-Philosophers Problem,有限缓冲区问题,有一个或者多个进程是生产者,持续不断地产生数据 有一个或者多个进程是消费者,持续不断地消耗数据 两者通过一个有限大小的缓冲区交换数据,有限缓冲区问题,生产者,消费者,有限缓冲区,消费者,生产者,消费者,.,.,问题分析,首先,对数据结构的修改不能同时进行,否则可能对
26、结构产生破坏 当缓冲区满了,生产者应该停下来等待 当缓冲区空了,消费者应该停下来 如果有多个消费者,不能相互影响(取到同一个数据),有限缓冲区问题,public class BoundedBuffer public BoundedBuffer() . public void enter(Object item) . public Object remove() . private static final int BUFFER_SIZE = 2; private Semaphore mutex; private Semaphore empty; private Semaphore full;
27、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 void enter(Object item) empty.P(); mutex.P(); / add an item t
28、o 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; ,第一类读者-写者问题,没有读者会保持等待状态,除非已经有写者获得了访问共享数
29、据的权限 或者: 读者不会仅仅因为有写者在等待而等待 问题: 写者饥饿,第二类读者-写者问题,一旦写者准备就绪,尽快满足写者的写请求 或者:如果写者在等待访问共享数据,那么新的读者就不能开始新的共享读 问题:读者饥饿,读者,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.endRead(); pr
30、ivate 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() . pu
31、blic int endRead() . 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
32、Semaphore(1); db = new Semaphore(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; ,
33、写者方法,public void startWrite() db.P(); public void endWrite() db.V(); ,哲学家进餐问题,最简单的解法,分别用一个信号量表示每一根筷子,都初始化为1 Semaphore 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
34、 left chopstick chopSticki.V(); / return right chopstick chopStick(i + 1) % 5.V(); / think for awhile ,解法分析,解法存在死锁的可能性! 当所有5位哲学家同时想吃东西的时候,他们都拿起左边的筷子,但这是右边已经没有筷子了,全都只有等待,而都不能进餐 如何解决?,修正死锁问题,通过限制哲学家的行为来避免死锁 只允许最多4位哲学家同时进餐 只有左右两边的筷子同时得到满足,哲学家才能够取得着两根筷子进餐 使用一个非对称的算法,比如,让奇数号数的哲学家先取左边的筷子,而偶数号数的哲学家先取右边的筷子,
35、信号量的优缺点,信号量的优点 提供了一种方便、有效的进程公布机制 信号量的缺陷 不正确的使用可能会导致错误的结果,并且这种错误很难发现和排除 不正确的使用信号量还可能导致死锁,错误使用信号量的例子,对于一个临界区问题,正确的代码应该是: mutex.P(); criticalSection(); mutex.V(); 如果代码不正确,将可能导致各种不同情况的错误,错误代码,P() 和 V() 操作的顺序错了 mutex.V(); criticalSection(); mutex.P(); 临界区根本没有得到保护 都写成了 P() mutex.P(); criticalSection(); mu
36、tex.P(); 将会发生死锁,管程(monitors),管程是一种提供线程安全的高层次的抽象 管程是一种抽象的数据结构,封装了一些私有数据,并提供了一些公有方法 管程确保一个时刻只有一个线程可以在管程内活动 配合条件变量,可以使用管程解决进程同步问题,管程模型,monitor monitor-name / variable declarations public entry p1() . public entry p2() . ,管程,封装限制了线程直接对管程内部的直接访问 管程阻止了对管程内定义的方法的并发访问,一个时间内只有个线程或进程可以访问管程内定义的方法 于是程序员不需要显式地对同
37、步编码,管程,条件变量 (condition),条件变量代表了一种条件,在上面只能进行两个操作wait和signal 条件变量只能存在于一个管程中,并且只能从管程内的方法对它进行访问 当一个线程调用x.wait的时候,就会被挂起,直到被其他线程调用x.signal而唤醒 x.signal 唤醒一个在x上挂起的线程,如果没有线程在x上挂起,操作不产生影响(和信号量的V()操作比较,它永远都产生影响),当线程因调用x.wait被挂起,那么该线程释放对管程的控制,而被其他线程调用x.signal唤醒,则要继续拥有对管程的控制 如果挂起的线程Q被线程P唤醒了,那么必须决定线程P或者Q有一方要等待,直到
38、对方退出管程,带有条件变量的管程,哲学家进餐问题的解法,monitor diningPhilosophers int state = new int5; static final int THINKING = 0; static final int HUNGRY = 1; 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) . pu
39、blic entry putDown(int i) . private test(int i) . ,pickUp() 方法,public entry pickUp(int i) statei = HUNGRY; test(i); if (statei != EATING) selfi.wait; ,putDown() 方法,public entry putDown(int i) statei = THINKING; / test left and right neighbors test(i + 4) % 5); test(i + 1) % 5); ,test() 方法,private te
40、st(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 pickUp(int i) . public entry putDown(int i) . ,pickUp 方法,public pickUp(int i) while (!(chopsticki
41、 ,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 Notifications Block Synchronization Java Semaphores Java Monitors Java同步机制是从管程衍生而来的,可以看成是只有一个条件变量的管程,同步方法(synchronized),每一个对
42、象都有一个相连的锁 调用同步的方法(synchronized)需要获得对象的锁 如果已经有其他的线程获得了锁,线程将等待 当线程退出同步方法将释放锁,入口队列,wait和notify方法,仅仅使用同步方法并不能实现复杂的同步问题 和管程中的条件变量类似,Java中引入了对象上的wait()和notify()方法,其功能分别对应条件变量的wait和signal方法 应该注意,管程中wait、signal是作用在条件变量上的,而Java中的wait和notify是作用在对象上的,wait() 方法,当一个线程调用对象的wait()方法,将会发生以下事件: 线程释放对象的锁 线程状态被设置为阻塞 线
43、程被放置到对象的等待队列,入口队列和等待队列,notify() 方法,当一个线程调用对象的notify(),将发生下列事件: 从对象的等待队列中任意选定一个线程T 将线程T移动到入口队列 将线程T的线程状态设置为就绪 T 可以再次竞争获得对象的锁,用Java实现生产者-消费者问题,class BoundedBuffer public static final int BUFFER_SIZE = 5; public synchronized void enter(Object item) . public synchronized Object remove() . private Object
44、 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(),public synchroniz
45、ed 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()把等待队列中的所有线程都移动到入口队列中,这样线程可以自己决定哪一个线程应该下一个进行处理 当
46、等待队列中有多个线程时,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 reade
47、rCount; private boolean 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 startWrite() while (readerCount 0 | writing = true) try wait(); catch (InterruptedException e) writing = true; public void endWrite() writing = false; notifyAll(); ,同步块,可以同步仅仅一个代码块而不是整个函数
链接地址:https://www.31doc.com/p-3174695.html