OS讲义-第五章.doc

第五章 并发性：互斥和同步 什么是进程并发 操作系统中引入并发程序设计技术后，一个程序未执行完，另一个程序就可以开始运行，一个程序也可以在不同的数据集上多次运行。因此，操作系统引进进程来刻画这种状态。 进程执行的并发性：一组进程的执行在时间上是重叠的。也就说一个进程执行的第一条指令是在另外一个进程执行的最后一条指令之前开始的。 例如：有两个进程A(a1、a2、a3)和B(b1、b2、b3)并发执行 。每一个进程的执行还是顺序的，但两个进程可能是交叉执行的。 从宏观上看，并发性反映一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态， 从微观上看，任一时刻仅有一个进程在处理器上运行。 并发的实质是一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。 影响进程执行速度的因素—— 其他进程的活动 OS处理中断的方式 OS的调度策略 存在的问题—— 全局资源的共享充满危险 OS对资源分配的管理难以达到最优 定位程序设计错误非常困难（不可再现性） 进程交互 相关术语：临界资源，临界区，互斥，死锁，饥饿 进程中的资源竞争—— 特点： –每个进程不知道其他进程的存在 –两个或更多进程在各自的执行过程中需要访问相同的资源（I/O设备、存储器、CPU、时钟等） –进程之间没有信息交换 相互间产生的影响： –执行结果不会受影响 –执行时间受影响 竞争引发的控制问题：互斥；死锁；饥饿 进程间通过共享的合作—— 特点： –没有意识到其他进程的存在，但知道要维护数据完整性 –共享变量、文件或数据库等 相互间产生的影响： –执行结果可能会受影响 –执行时间受影响 共享引发的控制问题：互斥；死锁；饥饿；数据的一致性 进程间通过通信的合作—— 特点： –进程直接知道合作伙伴 –采用消息传送的方式通信（发送/接收消息） 相互间产生的影响： –执行结果可能会受影响 –执行时间受影响 引发的控制问题：死锁；饥饿 互斥机制要求—— 空闲让进：一次只允许一个进程进入临界区 忙则等待：任何时候，处于临界区的进程不得多与一个 有限等待：进入临界区的进程要在有限的时间内退出。 让权等待：当进程不能进入临界区，应该立即释放处理机，防止进程忙等待 互斥机制实现方法—— 软件方法（附录A）：如 Dekker算法、Peterson 算法 硬件方法 OS或程序设计语言的支持：信号量、管程、消息传递 进程互斥的尝试 第一种：双标志法：先检查，后修改 对进程P1 和P2 分别用标志insidel 和inside2与其相连，当该进程在它的临界区内时其值为真（true），不在临界区时其值为假（false）。P1(P2)要进入它的临界区前先测试inside2(insidel)以确保当前无进程在临界区，然后，把insidel(inside2)置成true，以封锁进程P2(P1)进入临界区，直至P1(P2)退出临界区，再将相应标志置成false。 不满足“无空等待” 第二种：双标志法：先修改，后检查 延迟P1(P2)对inside2(insidel)的测试，而先置insidel(inside2)为true 以封锁P2(P1)。不满足“空闲让进” 硬件实现互斥 关中断—— 进入临界区前关中断，退出临界区后开中断 缺点：滥用中断权利，可能造成严重后果；程序被限制只能交替执行，处理器利用率降低；不适合多处理器； testset指令—— exchange指令—— 机器指令的优点：适合于单处理器以及共享内存的多处理器；简单且易于证明；支持多临界区； 缺点：使用忙等待；可能饥饿；可能死锁。 信号量 定义—— 一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(semaphore)，复杂的进程合作需求都可以通过适当的信号结构得到满足。在操作系统中，用以表示物理资源的实体。 分类—— 信号量按其用途分为 公用信号量：联系一组并发进程，相关的进程均可在此信号量上执行P和V操作。初值常常为1，用于实现进程互斥 私有信号量：联系一组并发进程，仅允许此信号量拥有的进程执行P操作，而其他相关进程可在其上施行V 操作。初值常常为0或正整数，多用于并发进程同步。 信号量按其取值分为 二元信号量：仅允许取值为0 和1，主要用于解决进程互斥问题。 一般信号量：允许取值为非负整数，主要用于解决进程同步问题。 按结构类型分为： 整型信号量： 记录型信号量：设s为一个记录型数据结构，一个分量为整型量value,另一个为与信号量相关的队列queue, P和V操作原语定义： P(s)；将信号量s减去l，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态。 V(s)：将信号量s加1，若结果不大于0，则