Chapter2b.ppt
《Chapter2b.ppt》由会员分享,可在线阅读,更多相关《Chapter2b.ppt(48页珍藏版)》请在三一文库上搜索。
1、操作系统及应用,Processes and Threads,2009年 秋季,Outline,Processes Threads Interprocess communication Classical IPC problems Scheduling,进程间通信,需要解决三个问题 第一,一个进程如何把信息传递给另一个进程。 第二,确认在关键活动中两个或更多的进程不会把事情搞乱。 例如,两个进程都试图取得1MB的内存 第三个问题与正确的顺序有关 例如,如果进程A产生数据,而进程B打印数据,那么B在打印之前必须等待,直到A已经产生了一些数据。,竞争条件,两个进程同时想访问共享内存,定义:两个或多个
2、进程读写某些共享数据,而最后的结果取决于进程运行的精确时序,称为竞争条件(race condition)。,临界区 (1),临界资源:一段时间内只允许一个进程访问的资源 把对临界资源(如:共享内存)进行访问的程序片段称作临界区(critical region或critical section)。 以某种手段确保当一个进程在使用一个共享变量或文件时,其他进程不能做同样的操作,称作互斥(mutual exclusion)。 对于一个好的互斥的解决方案必须满足的四个条件 任何两个进程不能同时处于其临界区 不应对CPU的速度和数量做任何假设 临界区外运行的进程不得阻塞其他进程 不得使进程无限期等待进入
3、临界区,临界区(2),使用临界区实现互斥,Mutual Exclusion with Busy Waiting (1)忙等待的互斥,禁止中断 使每个进程在刚刚进入临界区后立即禁止所有中断,并在就要离开之前再打开中断。 对操作系统本身是一项很有用的技术,对用户进程则不是一种合适的通用互斥机制。 锁变量 设立一个共享(锁)变量,其初值为0。当一个进程想进入临界区时,它首先测试该锁,如果该锁的值是0,则该进程将其设置为1并进入临界区。若该锁的值已经为1,则该进程将等待直到其值变为0。 是否能实现互斥?,Mutual Exclusion with Busy Waiting (2),临界区问题的一种解法
4、 (a) 进程 0 (b) 进程 1,严格轮换法,设立一个整型变量,用于记录轮到哪个进程进入临界区,并检查或更新共享内存。如为0时,进程0进入临界区;为1时,进程1进入临界区 连续测试一个变量直到某个值出现为止,称为忙等待(busy waiting) 问题?(考虑一个进程比另一个进程慢很多的情况),Mutual Exclusion with Busy Waiting (3),Peterson解法 是一个不需严格轮换的软件互斥算法 设立一个整型变量turn作为进入临界区的标志,同时设立一个数组interested来表示轮到的进程是否希望进入临界区。 只有当轮到了某进程,而其他进程不希望进入临界区
5、时,该进程才能进入,否则,将等待。 在使用共享变量之前,各个进程使用其进程号0或1作为参数来调用enter_region, 该调用在需要时将使进程等待,直到能安全地进入临界区 在完成对共享变量的访问之后,进程将调用leave_region,表示操作已完成, 若其他进程希望进入临界区,则现在就可以进入.,Mutual Exclusion with Busy Waiting (4),Peterson解法,Mutual Exclusion with Busy Waiting (5),TSL指令 是一种需要硬件支持的方案. 使用了测试并加锁指令TSL RX, LOCK, 它将一个内存字LOCK读到寄存
6、器RX中, 然后在该内存地址上存一个非0值. 使用共享变量lock来协调对共享内存的访问。当lock为0时,任何进程都可以使用TSL指令将其设置为1,并读写共享内存。当操作结束时,进程用一条普通的move指令将lock的值重新设置为0。,Sleep and Wakeup(1) 休眠与唤醒,Peterson解法和TSL指令都是正确的,但是它们都有忙等待的缺点, 浪费CPU时间. 在无法进入临界区时, 采用阻塞而不是忙等待的方法: 使用通信原语sleep和wakeup Sleep 是一个将引起调用进程阻塞的系统调用,即被挂起,直到另外一个进程将其唤醒. Wakeup调用有一个参数,即要唤醒的进程.
7、,Sleep and Wakeup(2),生产者-消费者问题(也称为有界缓存区问题) 问题描述:两组进程共享一个公共的固定大小的缓存区, 其中一组是生产者, 将信息放入缓存区;另一组是消费者, 从缓存区中取出信息. 当缓存区已满, 生产者还想放入新的数据项时,生产者休眠, 待消费者取走数据项后再唤醒它; 当缓存区已空,消费者还想从中取数据时, 消费者休眠,待生产者放入数据项后再唤醒它.,N-1,Sleep and Wakeup(3),含有严重竞争条件的生产者-消费者问题,设立一个变量count跟踪缓存区中的数据项数. 如果缓存区的大小为N, 则生产者代码检查count是否达到N, 若是, 则生
8、产者休眠; 否则生产者向缓存区中放入一个数据项并增加 count的值; 消费者首先测试 count是否为0, 若是,则休眠; 否则从中取走一个数据项, 并递减count的值; 每个进程同时也检查另一个进程是否应该被唤醒, 若是, 则唤醒之.,Semaphores(1) 信号量,由E.W.Dijkstra在1965年提出.是一种新的变量类型 取值可以为0(表示没有保存下来的唤醒操作)或者正整数(表示有一个或多个唤醒操作) 对信号量设立两种操作:down(或P) 和up(或V) 对一信号量执行 down操作, 则是检查其值是否大于0. 若大于0, 则其值减1并继续; 若其值为0, 则进程将休眠.
9、检查数值, 修改变量值以及可能发生的休眠操作均作为单一的, 不可分割的原子操作完成. 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),实现进程同步
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Chapter2b
链接地址:https://www.31doc.com/p-6222984.html