Chapter2b.ppt

操作系统及应用,Processes and Threads,2009年 秋季,Outline,Processes Threads Interprocess communication Classical IPC problems Scheduling,进程间通信,需要解决三个问题 第一，一个进程如何把信息传递给另一个进程。 第二，确认在关键活动中两个或更多的进程不会把事情搞乱。 例如，两个进程都试图取得1MB的内存 第三个问题与正确的顺序有关 例如，如果进程A产生数据，而进程B打印数据，那么B在打印之前必须等待，直到A已经产生了一些数据。,竞争条件,两个进程同时想访问共享内存,定义：两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件（race condition）。,临界区 (1),临界资源：一段时间内只允许一个进程访问的资源 把对临界资源(如：共享内存)进行访问的程序片段称作临界区(critical region或critical section)。 以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作，称作互斥(mutual exclusion)。 对于一个好的互斥的解决方案必须满足的四个条件 任何两个进程不能同时处于其临界区 不应对CPU的速度和数量做任何假设 临界区外运行的进程不得阻塞其他进程 不得使进程无限期等待进入临界区,临界区(2),使用临界区实现互斥,Mutual Exclusion with Busy Waiting (1)忙等待的互斥,禁止中断 使每个进程在刚刚进入临界区后立即禁止所有中断，并在就要离开之前再打开中断。 对操作系统本身是一项很有用的技术，对用户进程则不是一种合适的通用互斥机制。 锁变量 设立一个共享(锁)变量，其初值为0。当一个进程想进入临界区时，它首先测试该锁，如果该锁的值是0，则该进程将其设置为1并进入临界区。若该锁的值已经为1，则该进程将等待直到其值变为0。 是否能实现互斥？,Mutual Exclusion with Busy Waiting (2),临界区问题的一种解法 (a) 进程 0 (b) 进程 1,严格轮换法,设立一个整型变量，用于记录轮到哪个进程进入临界区，并检查或更新共享内存。如为0时，进程0进入临界区；为1时，进程1进入临界区 连续测试一个变量直到某个值出现为止，称为忙等待(busy waiting) 问题？(考虑一个进程比另一个进程慢很多的情况),Mutual Exclusion with Busy Waiting (3),Peterson解法 是一个不需严格轮换的软件互斥算法 设立一个整型变量turn作为进入临界区的标志，同时设立一个数组interested来表示轮到的进程是否希望进入临界区。 只有当轮到了某进程，而其他进程不希望进入临界区时，该进程才能进入，否则，将等待。 在使用共享变量之前,各个进程使用其进程号0或1作为参数来调用enter_region, 该调用在需要时将使进程等待,直到能安全地进入临界区 在完成对共享变量的访问之后,进程将调用leave_region,表示操作已完成, 若其他进程希望进入临界区,则现在就可以进入.,Mutual Exclusion with Busy Waiting (4),Peterson解法,Mutual Exclusion with Busy Waiting (5),TSL指令 是一种需要硬件支持的方案. 使用了测试并加锁指令TSL RX, LOCK, 它将一个内存字LOCK读到寄存器RX中, 然后在该内存地址上存一个非0值. 使用共享变量lock来协调对共享内存的访问。当lock为0时，任何进程都可以使用TSL指令将其设置为1，并读写共享内存。当操作结束时，进程用一条普通的move指令将lock的值重新设置为0。,Sleep and Wakeup(1) 休眠与唤醒,Peterson解法和TSL指令都是正确的,但是它们都有忙等待的缺点, 浪费CPU时间. 在无法进入临界区时, 采用阻塞而不是忙等待的方法: 使用通信原语sleep和wakeup Sleep 是一个将引起调用进程阻塞的系统调用,即被挂起,直到另外一个进程将其唤醒. Wakeup调用有一个参数,即要唤醒的进程.,Sleep and Wakeup(2),生产者-消费者问题(也称为有界缓存区问题) 问题描述:两组进程共享一个公共的固定大小的缓存区, 其中一组是生产者, 将信息放入缓存区;另一组是消费者, 从缓存区中取出信息. 当缓存区已满, 生产者还想放入新的数据项时,生产者休眠, 待消费者取走数据项后再唤醒它; 当缓存区已空,消费者还想从中取数据时, 消费者休眠,待生产者放入数据项后再唤醒它.,N-1,Sleep and Wakeup(3),含有严重竞争条件的生产者-消费者问题,设立一个变量count跟踪缓存区中的数据项数. 如果缓存区的大小为N, 则生产者代码检查count是否达到N, 若是, 则生产者休眠; 否则生产者向缓存区中放入一个数据项并增加 count的值; 消费者首先测试 count是否为0, 若是,则休眠; 否则从中取走一个数据项, 并递减count的值; 每个进程同时也检查另一个进程是否应该被唤醒, 若是, 则唤醒之.,Semaphores(1) 信号量,由E.W.Dijkstra在1965年提出.是一种新的变量类型 取值可以为0(表示没有保存下来的唤醒操作)或者正整数(表示有一个或多个唤醒操作) 对信号量设立两种操作：down(或P) 和up(或V) 对一信号量执行 down操作, 则是检查其值是否大于0. 若大于0, 则其值减1并继续; 若其值为0, 则进程将休眠. 检查数值, 修改变量值以及可能发生的休眠操作均作为单一的, 不可分割的原子操作完成. Up操作对信号量的值增1，唤醒一个在该信号量上休眠的进程。不会有进程因执行up而阻塞.信号量的值增1和唤醒一个进程同样也是不可分割的。,Semaphores(2),实现进程互斥,down(mutex);,up(mutex);,Semaphores(3),提问： 1. mutex的取值范围？,down(mutex);,up(mutex);,up(mutex);,up(mutex);,down(mutex);,down(mutex);,Semaphore mutex=1;,Semaphores(4),实现进程同步,down(s);,up(s);,Semaphores(5),down(s);,up(s);,执行时两种可能性： 在进程B还没有送数据之前，进程A先执行了down(s),结果会怎样？ 进程B的up(s)操作已经完成,进程A才执行了down(s),结果会怎样？,答： 进程A执行down(s), 会使自己进入阻塞状态，直至进程B送数据后执行up(s),才能将它唤醒 若进程B的up(s)操作已经完成, 进程A才执行了down(s), 则进程A不会阻塞。它可以顺利地取到数据，完成下面的操作。,Semaphore s=0;,Semaphores(6),用信号量解决生产者和消费者问题,Semaphores(7),用信号量解决生产者和消费者问题,Semaphores(8),桌上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中；一个儿子专等吃盘子里的香蕉，而一个女儿专等吃盘子里的苹果。请用信号量解决此问题。 分析： 父亲、母亲、儿子和女儿共用一个盘子，盘子一次只能放一个水果。 当盘子为空时，父亲和母亲均可以试着将一个水果放入盘中，但一次只能有一个人成功放入水果。 若放入盘子中的是香蕉，则允许儿子吃，女儿必须等待 若放入盘子中的是苹果，则允许女儿吃，儿子必须等待,Semaphores(9),设置信号量dish, 表示盘子是否为空，初值为1 设置信号量 apple，表示盘中是否有苹果，初值为0 信号量banana,表示盘中是否有香蕉，初值为0,Father() while (true) down(dish); put apple into dish; up(apple) ,daughter() while (true) down(apple); take apple from dish; up(dish); eating apple ,mother() ? Son() ? ,Mutexes(互斥信号量),如果不需要信号量的计数能力，可以使用信号量的一种简化版本，称为互斥信号量 Mutex是一个可以处于两态之一的变量：加锁和解锁 Mutex 使用两个过程：当一个线程（或进程）需要访问临界区时，它调用mutex_lock，如果该信号量当前是解锁的，此调用成功，调用线程可自由进入临界区；如果该互斥信号量已经加锁，调用线程被阻塞，直到在临界区中的线程完成并调用mutex_unlock.,Monitors (1) 管程,使用信号量要非常小心，否则很容易导致死锁 Hoare等人提出了一种高级同步原语，称为管程 一个管程是一个由过程、变量及数据结构等组成的集合，它们组成一个特殊的模块或软件包 进程可在需要的时候调用管程中的过程，但它们不能在管程之外声明的过程中直接访问管程内的数据结构 任意时刻管程中只能有一个活跃进程，使管程能有效地完成互斥,Monitors (2),当一个管程过程无法继续运行时，它会在条件变量上执行wait操作，该操作导致调用进程自身阻塞. 进程可以通过对其伙伴正在等待的一个条件变量执行signal操作，以唤醒该伙伴进程 条件变量不是计数器，也不能象信号量那样累积信号供以后使用。所以wait操作必须在signal操作之前。,互斥与同步,Monitors (3),说明： 条件变量x：表示等待原因,Monitors (4),用管程实现的生产者-消费者问题的解法框架,管程定义,进程调用,Message Passing（1）消息传递,Message Passing（2）,消息传递使用两条原语：send和receive Send(destination,down(forki+1%N);,up(forki);,up(forki+1%N);,Dining Philosophers (4),解决办法 至多只允许四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐 仅当哲学家的左右两只筷子都可用时，才允许他拿起筷子进餐 ,Dining Philosophers (5),办法2的一种实现方法 使用一个数组state跟踪每一个哲学家是在进餐、思考还是饥饿 一个哲学家只有在两个邻居都没有进餐时，才允许进入到进餐状态 使用一个信号量数组，每个信号量对应一位哲学家，在所需的叉子被占用时，想进餐的哲学家就被阻塞 当被占用的叉子被释放时，可能唤醒被阻塞的哲学家 每个哲学家想进餐时，运行philosopher进程,Dining Philosophers (5),哲学家就餐问题的一种解法 (part 1),Dining Philosophers (6),哲学家就餐问题的一种解法 (part 2),The Readers and Writers Problem（1）读者-写者问题,问题描述： 一个数据对象可被多个进程共享。其中有的进程要求读，另一些进程要求写或修改。把要求读的进程称为“读者”进程，其它进程称为“写者”进程。允许多个读者进程同时读共享的数据对象，但不允许写者进程与其它写者进程或读者进程同时访问共享的数据对象。,The Readers and Writers Problem（2）,db,The Readers and Writers Problem（3）,rc,rc,rc.,mutex,The Readers and Writers Problem(4),读者/写者问题的一种解法,The Sleeping Barber Problem (1)睡眠理发师问题,问题描述: 理发店有一位理发师,一把理发椅和n把供等候理发的顾客坐的椅子. 如果没有顾客,理发师便在理发椅子上睡觉,当一个顾客到来时,他必须先叫醒理发师. 如果理发师正在理发时又有顾客到来,如果有空椅子,顾客就坐下来等候;如果没有空椅子,顾客就离开. 要求为理发师和顾客各自编一段程序来描述他们的行为,要求不能进入竞争条件.,The Sleeping Barber Problem (2),分析 进程分为两类: 理发师进程和顾客进程 资源 顾客进程的资源: 理发师, 供顾客等候时坐的椅子 理发师进程的资源: 顾客 互斥 设立计数器waiting 跟踪当前正在等待理发的顾客数 设立信号量mutex实现对waiting 的互斥访问 同步: 只有顾客到来, 理发师才能理发, 设立信号量customers,实现理发师进程与顾客进程的同步 只有理发师空闲, 顾客才能被理发, 设立信号量barbers, 实现顾客进程与理发师进程的同步,The Sleeping Barber Problem (3),睡眠理发师问题的一种解法,