第六章 进程间互斥、同步与通信(操作系统原理).ppt

第六章进程间互斥 同步与通信 授课教师 付勇智fuyongzhi 西南林学院基础部数理教研室 问题纲要 间接制约和直接制约是什么 什么是临界区 什么是信号量 什么是同步 互斥 如何应用信号量实现同步和互斥 信号量在Windows编程中是如何实现的 进程并发运行所带来的问题 由于系统资源的共享性 并发进程的执行结果失去了封闭性和可再现性 满足Bernstein条件的并发进程能够保持封闭性 但是Bernstein条件限制太过严格 不符合大多数实际环境的需要 因而 OS需要寻求一种机制 满足进程间共享资源的需要 进程间通信IPC 在两个或多个进程间传递信息或共享数据的机制 称之为进程间通信 Inter ProcessCommunication UNIX操作系统中的管道技术 Pipe 就是一种IPC在IPC的过程中 主要要解决两类问题 互斥和同步 互斥的需要 voidSendPrint 1if in 1 N out 2exit 0 3else4in in 1 N 5file in printfile 6return ProcessA SendPrint ProcessB SendPrint 临界区 CriticalSection 临界资源 一次仅允许一个进程使用的资源称为临界资源 临界区 进程中对于临界资源访问的程序段称为临界区 间接制约 由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象 称为由共享公有资源造成的并发进程执行速度的间接制约 简称间接制约 互斥 一组并发进程中的一个或多个程序段 因共享某一公有资源而导致他们不能同时进入临界区称为互斥 互斥 MutualExclusion 互斥方案应满足的4个条件 任何两个进程不能同时处于临界区不应对CPU的数目和速度做任何假设临界区外的进程不得阻塞其他进程不得使进程在临界区外无休止地等待 互斥的实现方案 关中断锁变量严格轮换法Peterson方案TSL硬件指令 Intel平台为BTS指令 信号量管程消息传递 关中断 处理机的调度都是由中断所引起的 主要是定时器中断 如果进入临界区前将所有外部中断屏蔽 则在运行临界区时将不会响应所有外部中断事件 也就不可能发生进程切换 待进程执行完临界区后再开中断 缺点 交由用户进程管理中断的开关是非常不安全的 一旦用户程序关中断后忘记打开 则整个系统将无法响应外部事件而崩溃 另外 在多处理器系统中 关中断也仅屏蔽本处理器的中断响应 对其他处理器中运行的进程无法屏蔽 因而通常中断屏蔽都由OS进行管理 由OS使用它来保证一些核心操作的不可中断性 锁变量 intlock 0 初始情况下没有进程进入临界区Processi while lock 1 当其他进程在临界区工作时 忙等待lock 1 设置锁变量 防止其他进程进入critical section 进行临界区相关操作lock 0 退出临界区后解锁 使其他进程可以进入non critical section 严格轮转法 Peterson方案 TSL指令 测试与设置指令 IntelCPU中对应的TSL指令汇编指令码为BTS 信号量 semaphore 信号量使E W Dijkstra在1965年提出的一种方法 他建议引入一个新的变量类型 称作信号量 信号量是一个整数 其值可以为0或某个正整数 分别表示不可进入临界区以及能够进入的进程数目 信号量 是一个仅能由同步原语对其进行操作的整型变量 原语 原子操作 操作过程不可中断 必须以一个整体进行执行地系统基本操作对于信号量操作的原语只有两个 UP和DOWN DOWN原语 P操作 1 若信号量S大于0 则将S减1 P操作返回 该进程继续执行 2 若信号量S等于0 则将进程挂入S的等待队列 将进程设置为阻塞状态 并转调度程序 P原语 S 0 S S 1 返回 调用进程进入等待队列 转进程调度 是 否 UP原语 V操作 1 若信号量S的等待队列中有等待进程 则取队首进程 将其置为就绪状态并返回 2 否则信号量S加1 并放回 V原语 是否有等待进程 S S 1 返回 取队首进程置为就绪态 否 是 生产者 消费者问题 问题描述 两个进程共享一个公共的固定大小的缓冲区 其中的一个 生产者 将信息放入缓冲区 另一个 消费者 从缓冲区中取出信息 当缓冲区已满 而此时生产者还想向其中放入一个新的信息则让生产者睡眠 待消费者从缓冲区取走一个或多个信息时再唤醒它 当消费者试图从缓冲区中取信息而发现缓冲区为空时 它就睡眠 直到生产者向其中放入一些消息再将其唤醒 生产者过程 消费者过程 直接制约与同步 一组在异步环境下的并发进程 各自的执行结果互为对方的执行条件 从而限制各进程的执行速度的过程称为并发进程间的直接制约 异步环境下的一组并发进程 因直接制约而互相发送消息而进行相互合作 相互等待 使得各进程按一定的速度执行的过程称为进程间的同步 生产者 消费者问题信号量定义 defineN100semaphoremutex 1 互斥信号量semaphoreempty N 开始时候可用的消息缓冲区数为Nsemaphorefull 0 开始时候可用的消息为0 生产者进程 voidproducer intitem while true produce item 增加一个可用消息 消费者进程 voidconsumer intitem while true down full 获得一可用消息down mutex 互斥访问消息缓冲区get item 增加一个空缓冲区 哲学家进餐问题 五个哲学家围坐在一张圆桌周围 每个哲学家面前都有一盘通心粉 由于通心粉很滑 所以要两把叉子才能夹住 相邻两盘子之间有一把叉子 餐具摆放如右图所示 哲学家生活的过程 哲学家的生活包括两种活动 即吃饭和思考 当一个哲学家觉得饿时 他就试图分两次去取他左边和右边的叉子 每次得到一把 并且不分次序 如果成功的获得两把叉子 他就开始吃饭 吃完以后放下叉子继续思考 问题 为每一个哲学家写一段程序来描述其行为 要求不能死锁 不正确解法 defineN5voidphilosopher inti while true think take fork i take fork i 1 N eat put fork i put fork i 1 N 低效率的互斥可行解法 defineN5semaphormutex 1 voidphilosopher inti while true think down mutex take fork i take fork i 1 N eat put fork i put fork i 1 N up mutex 经典解法 defineN5 defineLEFT i 1 N defineRIGHT i 1 N defineTHINKING0 defineHUNGRY1 defineEATING2intstate N semaphoremutex 1semaphores N 0 0 0 哲学家过程 voidphilosopher inti while true think take forks i eat put forks i voidtest i if state i HUNGRY 哲学家的两个主要动作 voidtake forks inti down voidput forks inti down mutex state i THINKING test LEFT test RIGHT up mutex 读者 写者问题 设想一个飞机订票系统 其中有许多竞争的进程试图读写其中的数据 多个进程同时读是可以接受的 但一个进程正在更新数据库 则所有其他进程都不能访问数据库 即使读操作也不行 问题 如何对读者和写者编写线程 semaphoremutex 1 semaphoredb 1 intrc 0 voidreader while true down mutex rc 1 if rc 1 down db up mutex read data base down mutex rc rc 1 if rc 0 up db up mutex use data read 写者过程 voidwriter while true think up data down db write data base up db 理发师睡觉问题 理发店里有一位理发师 一把理发椅和n把供等候理发顾客坐的椅子 如果没有顾客 则理发师便在理发椅上睡觉 当一个顾客到来时 他必须叫醒理发师 如果一个顾客到来时理发师正在理发 则如果有空椅子可以坐 他们就坐下来等待 如果没有空椅子 他们就离开 问题 为理发师和顾客各编写一段程序 描述他们的行为 要求不能带有竞争条件 信号量定义 defineCHAIRS5 椅子数目semaphorecustomers 0 顾客数目semaphorebarbers 0 等候顾客的理发师数目semaphoremutex 1 等待队列互斥信号量intwaiting 0 等待队列 voidbarber while true down customers down mutex waiting up barbers up mutex cut hair voidcustomer down mutex if waiting CHAIRS waiting up customers up mutex down barbers get haircut elseup mutex 司机 售票员问题 一辆公共汽车上有一名司机和一名售票员 司机的工作是不停的循环执行如下步骤 开车 正常行车 到站停车 售票员的工作是不停的执行如下工作 开车门 等候乘客上车 关车门 售票 售票员必须等车到站停车后才能开车门 司机也必须等售票员关车门以后才能开车问题 试写两段程序 分别描述司机和售票员的工作过程 司机 售票员问题 售票员 司机 semaphoredriving 0 semaphoredoor 1 voiddriver while true down driving 开车 正常行车 到站停车 up door voidticket seller while true down door 开门 等待乘客上车 关门 up driving 售票 两学校交通问题 在南开大学和天津大学之间有一条弯曲的小路 其中从S到T一段路每次只允许一辆自行车通过 但中间有一个小的 安全岛 M 可供两辆自行车在从两端进入小路的情况下错车使用 如下图所示 试设计一个算法使来往的自行车均可顺利通过 学校交通图示 M 天津大学 南开大学 S K T L semaphoreS2T 1 semaphoreT2S 1 semaphoreSK 1 semaphoreTL 1 semaphoreM 2 voidbikeS2T down S2T down SK go S K down M get in M up SK down TL up M go L T up TL up S2T voidbikeT2S down T2S down TL go T L down M get in M up TL down SK up M go K S up SK up T2S Windows中的IPC实现 信号量的创建HANDLECreateSemaphore LPSECURITY ATTRIBUTESlpSemaphoreAttributes SDLONGlInitialCount initialcountLONGlMaximumCount maximumcountLPCTSTRlpName objectname DOWN操作 DWORDWaitForSingleObject HANDLEhHandle handletoobjectDWORDdwMilliseconds time outinterval UP操作 BOOLReleaseSemaphore HANDLEhSemaphore handletosemaphoreLONGlReleaseCount countincrementamountLPLONGlpPreviousCount previouscount 示例 打开窗口数目的限制 功能 通过一个循环 打开五个窗口 但同一时刻最多只能有三个窗口打开 试用DOWN UP操作先编写程序完成以上要求semaphorecount 3 OpenAction DOWN count DrawWindow while WindowState Close UP count Windows平台实现 include stdafx h HANDLEhSemaphore LONGcMax 3 DWORDWINAPIthread func LPVOIDlpParam LONGcPreviousCount charoutinfo 20 WaitForSingleObject hSemaphore INFINITE MessageBox NULL ThreadMessage MB OK ReleaseSemaphore hSe