chap4 进程的同步与通信.pptVIP

第四章 进程的同步与通信 并发的原理 进程间互斥的实现 信号量 信号量实现互斥 生产者/消费者问题 读者/写者问题 信号量的实现 管程 消息传递 并发问题 进程间的通信 资源的共享与竞争 多个进程的同步 处理器时间的分配 并发是所有问题的基础，也是操作系统设计的基础。 并发环境 多个应用程序 多道程序设计 结构化应用程序 应用程序可以被设计成一组并发进程 操作系统结构 操作系统被设计成一组进程或线程 并发带来的难题 共享全局资源充满危险 对分配资源难以进行最优化的管理 程序设计错误难以定位 例题：代码框架 double balance; //共享变量 Process P1 Process P2 ... ... balance balance = balance+amount; = balance-amount; ... ... 例题：进程机器码 例题：并发执行 操作系统关注的问题 保持对活跃进程的跟踪 —— PCB 分配与回收资源 处理器时间 存储器 文件 I/O设备 保护数据与资源 进程的执行结果与其它并发运行进程执行的速度无关 进程间的交互 进程间相互不知道对方的存在 OS需要知道他们对资源的竞争情况 进程间接知道对方的存在 访问共享对象，表现出合作行为 进程直接知道对方的存在 通过进程ID相互通信，合作完成活动 进程间竞争资源 互斥 临界资源：一次只允许一个进程使用的资源 临界区：使用临界资源的代码 例：打印机 死锁 饥饿 进程间的共享合作 写操作必须保证互斥 临界区用于保护数据的一致性 死锁 饥饿 进程间的通信合作 通过传递消息进行合作 这类合作不需要互斥 可能存在死锁 每个进程都在等待对方进程的消息 可能存在饥饿 两个进程间互发消息，但其它进程均等待消息 支持互斥需满足的要求 空闲让进 忙则等待 有限等待 让权等待 驻留有限 互斥的实现 软件方法 硬件支持 操作系统或程序设计语言支持 软件方法（算法一） 该算法设置了一个公用整型变量turn，用于指示被允许进入临界区的进程编号，既若ture=0，表示允许Pi进程进入临界区。该算法可确保每次只允许一个进入临界区。但采用强制两个进程轮流进入临界区，很容易造成资源利用不充分。 软件方法（算法一） 软件方法（算法二） 在每一个进程访问临界区资源之前，先去查看一下临界资源是否正被访问，若正被访问，该进程需等待，否则才进入自己的临界区。为此设置了一个数据 flag[0,1]，如第i个元素值为false表示Pi进程未进入临界区，值为true表示Pi进程进入临界区。 软件方法（算法二） 软件方法（算法三） 算法3采用先设置自己标志后再检测对方状态标志，它的程序如下，但也可能出现二个进程先后同时设置后再分别检测对方状态标志，造成对方都不能进入临界区，无限期等待。 软件方法（算法三） 软件方法(Peterson算法) 该算法组合了算法1和算法3，为了防止二进程进入临界区而无限期等待，又设置变量turn，表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置turn标志，不允许另一个进程进入，这时再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当二个进程同时要求进入临界区时，只允许一个进程进入临界区。 软件方法的缺点 忙等待 实现过于复杂，需要高的编程技巧 屏蔽中断实现互斥 TS指令 boolean testset (int i) { if (i == 0) { i = 1; return true; } else { return false; } } TS指令实现互斥 机器指令方法的优点 适用于单处理器或多处理器上任何数目的进程 简单且易于证明 可用于支持多个临界区 机器指令方法的缺点 使用了忙-等待，消耗处理器时间 可能饥饿 可能死锁 信号量 一个用于传递信号的特殊变量s 该变量上可执行P操作和V操作 s被初始化为一个非负数 P(s)：使信号量减1，若值为负数，则阻塞进程 V(s)：使信号量加1，若值小于或等于零，则唤醒被阻塞进程 P、V操作不可中断 用队列来保存在信号量上等待的进程 信号量的定义 struct semaphore{ int count; queueType queue; } 信号量原语的定义 信号量解决互斥问题 互斥信号量的取值范围 若2个进程共享一个临界资源，信号量的取值范围是： 信号量值的解释 s.count的初值代表系统中某类资源的总数 s.count ≥0 s.count是可以执行P(s)而不需要挂起的进程数 s.count 0 s.count是挂起在s.queue队列中的进程