[工学]第4章_并发性：互斥和同步.pptVIP

第4章 并发性:互斥和同步 Outline 并发性引发的问题 进程的互斥机制 软件方法 硬件方法 OS或程序设计语言的支持 经典进程同步问题 并发环境 并发环境：进程的相对执行速度不可预测 是多道程序系统的基本特性 影响进程执行速度的因素: 其他进程的活动 OS处理中断的方式 OS的调度策略 存在的问题: 全局资源的共享充满危险 OS对资源分配的管理难以达到最优 定位程序设计错误非常困难（不可再现性） 一个与执行速度有关的错误 解决办法: 控制访问全局共享资源的代码！ 并发环境中OS关注的问题 跟踪每个进程, 知道它们的状态 为每个进程分配和回收各种资源 处理机 存储器 文件 I/O设备 保护进程拥有的数据和物理资源 保证进程的结果与相对执行速度无关 进程间的相互作用 间接作用 通过共享的竞争 通过共享的合作 直接作用 通过通信的合作 进程间通过共享的竞争 特点： 每个进程不知道其他进程的存在 两个或更多进程在各自的执行过程中需要访问相同的资源（I/O设备、存储器、CPU、时钟等） 进程之间没有信息交换 相互间产生的影响： 执行结果不会受影响 执行时间受影响 竞争引发的控制问题： 互斥 死锁 饥饿 与并发有关的术语 互斥 多个进程需要访问一个不可共享资源时, 任何时候只能有一个访问这个资源 临界资源 不可共享的资源 临界区 访问临界资源的那部分代码 与并发有关的术语 死锁 一组进程中，每个进程都无限等待该组进程中另一进程所占用的资源 饥饿 一组进程中，某个或某些进程无限等待该组进程中其他进程所占用的资源 进程间通过共享的合作 特点： 没有意识到其他进程的存在，但知道要维护数据完整性 共享变量、文件或数据库等 相互间产生的影响： 执行结果可能会受影响 执行时间受影响 共享引发的控制问题： 互斥 死锁 饥饿 数据的一致性 进程间通过通信的合作 特点： 进程直接知道合作伙伴 采用消息传送的方式通信（发送/接收消息） 相互间产生的影响：同“通过共享的合作” 引发的控制问题: 死锁 饥饿 互斥机制原理 互斥机制的要求 空闲让进 忙则等待 有限等待 让权等待（当进程不能进入临界区，应该立即释放处理机，防止进程忙等待） 互斥机制的实现 软件方法（附录A） 如 Dekker算法、Peterson 算法 硬件方法 OS或程序设计语言的支持 信号量 管程 消息传递 互斥:硬件的实现方法一、中断禁用（关中断） 原理 如果进程访问临界资源时（执行临界区代码）不被中断，就能保证互斥地访问 途径：使用关、开中断原语 缺点 限制了处理器交替执行各进程的能力 不能用于多处理器结构 二、专门的机器指令 适用范围（前提） 单处理器或共享主存多处理器结构 对同一存储单元的访问是互斥的 Dekker算法第二种尝试失败的原因 如果测 flag[1] 和置位 flag[0] 在一个指令周期完成就不会出错 Testset 指令(Test and Set---TS) 定义（逻辑） exchange指令 定义（逻辑） 用机器指令实现互斥 机器指令方法的优缺点 优点 适用于单处理器或共享主存多处理器系统，进程数目任意 简单且易于证明 可以使用多个变量支持多个临界区 缺点 忙等待 可能饥饿 可能死锁 OS或程序设计语言的支持 进程的同步 指系统中一些进程需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于阻塞状态，获得消息后被唤醒进入就绪态。 进程的同步机制 信号量 管程 消息传递 信号量 信号量机制(Dijkstra, 1965)：解决并发进程问题的第一个重要进展。需要OS支持。 基本原理 两个或多个进程可以通过简单的信号进行合作, 从而可以迫使一个进程在某指定位置停住, 直到它收到特定信号 通过使用适当的信号结构可以满足任何复杂的合作要求 信号量 信号量: 用于发信号的特殊数据结构,含一个整数变量 进程用 semSignal 原语通过信号量发送信号 进程用 semWait 原语通过信号量接收信号 对信号量的操作 对信号量的操作只有三种: 初始化: 通常将信号量的值初始化为非负整数 semWait操作/P操作/DOWN操作 使信号量的值减1 如果使信号量的值变成负数, 则执行wait的进程被阻塞 semSignal操作/V操作/UP操作 使信号量的值加1 如果信号量的值不是正数, 则使一个因执行wait操作被阻塞的进程解除阻塞 此外, 没有其他检查和修改信号量值的操作 信号量原语的定义 二元信号量 信号量的取值只能是0或1 和一般信号量具有相同表达力 强信号量与弱信号量 在一个信号量上等待的各个进程形成队列, 这些进程以什么顺序出队？ 强信号量 出队的顺序是FIFO（First I