信号量与PV操作PPT课件

主要内容 同步与同步机制信号量及其操作信号量的应用哲学家进餐问题生产者 消费者问题读者 写者问题理发师问题 3 3信号量与PV操作 1 3 1 1同步与同步机制 著名的生产者 消费者问题是计算机操作系统中并发进程内在关系的一种抽象 是典型的进程同步问题 在操作系统中 生产者进程可以是计算进程 发送进程 而消费者进程可以是打印进程 接收进程等等 解决好生产者 消费者问题就解决好了一类并发进程的同步问题 生产者 消费者问题表述 有n个生产者和m个消费者 连接在k个单位缓冲区的有界环形缓冲池上 故又叫有界缓冲问题 其中pi和cj都是并发进程 只要缓冲区未满 生产者进程pi所生产的产品就可以放入缓冲区 只要缓冲区非空 消费者进程cj就可以从缓冲区取走并消耗产品 2 3 intk typedefanyitemitem item类型nextp nextc item itembuffer k intin 0 out 0 counter 0 4 processproducer void while TRUE produceaniteminnextp if counter k sleep producer buffer in nextp in in 1 k counter if counter 1 wakeup consumer 5 processconsumer void while TRUE if counter 0 sleep consumer nextc buffer out out out 1 k counter if counter k 1 wakeup producer consumetheiteminnextc 6 生产者和消费者单独运行都是正确的 但是 如果并发执行 交替执行 就会产生错误 结果不唯一永远等待出现错误结果的原因在于各个进程访问缓冲区的速率不同 要得到正确结果 需要调整并发进程的速度 这需要通过在进程间交换信号或消息来调整相互速率 达到进程协调运行的目的 这种协调过程称为进程同步 操作系统实现进程同步的机制称为同步机制 它通常由同步原语组成 常用的同步机制有 信号量与PV操作 管程和消息传递 7 3 3 2信号量与PV操作 1 前节种种方法解决临界区调度问题的缺点1 对不能进入临界区的进程 采用忙式等待测试法 浪费CPU时间 2 将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性 加重了用户编程负担 3 这些方案只能解决进程竞争 不能解决进程协作问题 2 信号量同步机制的提出1965年荷兰计算机科学家E W Dijkstra提出了新的同步工具 信号量和P V操作 他将交通管制中多种颜色的信号灯管理交通的方法引入操作系统 让两个或多个进程通过特殊变量展开交互 一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值 这种特殊变量就是信号量 Semaphore 8 进程可以使用P V两个特殊操作来发送和接收信号 如果协作进程的相应信号仍未送到 则进程被挂起直到信号送达为止 注意 这里的 挂起 并不是第二章里的被对换到硬盘上 而是转入等待状态 操作系统中 信号量是用来表示物理资源的实体 用一个结构性变量表示 有两个分量 一个是信号量的值 另一个是指向信号量的队列的指针 除赋初值外 信号量仅能由同步原语P和V对其进行操作 没有任何其他方法可以检查和操作信号量 原语是操作系统内核中执行时不可中断的过程 即原子操作 Dijkstra发明了两个信号量操作原语 P操作原语和V操作原语 荷兰语中 测试 Proberen 和 增量 Verhogen 的头字母 常用的其他符号有 wait和signal up和down sleep和wakeup等 利用信号量和P V操作既可以解决并发进程的竞争问题 又可以解决并发进程的协作问题 9 信号量的分类信号量按其用途分为2种 公用信号量 初值常常为1 用来实现进程间的互斥 相关进程均可对其执行P V操作 私有信号量 初值常常为可用资源数 多用来实现进程同步 拥有该信号量的一类进程可以对其执行P操作 而另一类进程可以对其执行V操作 多用于并发进程的同步 信号量按照取值可以分为两种 二元信号量 仅允许取0和1 主要用于解决进程互斥 一般信号量 计数信号量 允许取任意整数值 主要用于解决进程同步问题 10 一般信号量数据类型 s是结构性变量 其中成员value为整型变量 系统初始化时为其赋初值 成员list为等待使用此类资源的进程队列的头指针 P s 将s的成员value的值减一 若结果小于0 则执行P操作的进程被阻塞 并且进入s的成员list指向的队列 否则 执行P操作的进程继续执行 2 V s 将s的成员value的值加一 如果结果小于等于0 则执行V操作的进程从s的成员list指向的队列中唤醒一个进程 使其转变为就绪态 随后自己继续执行 如果结果大于0 则执行V操作的进程继续执行 11 结构型信号量和PV操作的实现 typdefstructsemaphore intvalue structpcb list voidP semaphore 12 其中W s list 和R s list 是操作系统的基本系统调用 W s list 表示把调用它的进程置成等待信号量s状态 并移入s信号量队列 同时释放CPU 转向进程调度 R s list 表示释放一个等待s信号量的进程 转换成就绪态并且移入就绪队列 执行该操作的进程继续执行 时间片未到期 或者转向进程调度 时间片已到期 进程从队列中移出时的次序按照FCFS算法 被阻塞的时间越长的进程越优先出队 一避免饥饿现象 13 结构型信号量与PV操作的关系 推论1 若信号量s value为正值 则该值等于在封锁进程之前对信号量s可施行的P操作数 亦等于s所代表的实际还可以使用的物理资源数推论2 若信号量s value为负值 则其绝对值等于登记排列在该信号量s队列之中等待的进程个数 亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数推论3 通常 P操作意味着请求一个资源 V操作意味着释放一个资源 在一定条件下 P操作代表挂起进程操作 而V操作代表唤醒被挂起进程的操作 14 记录型信号量与PV操作的注意事项 P操作信号量的值减一如果满足if条件 执行了P操作的进程会挂起 P操作语句之后的语句都不会再执行 被挂起的进程 除非另一个进程调用V 来唤醒它 否则永远不会执行 V操作信号量的值加一如果满足if条件 执行V操作的进程会去唤醒另一个正在等待的进程 被挂起的进程 执行V操作的进程不会自愿停止 V操作后面的语句会接着执行被唤醒的进程只是进入了就绪队列 并不一定有机会马上被执行被唤醒的进程 从挂起点接着执行 也就是P操作之后的语句 15 2二元信号量 设s为一个结构型数据结构 其中一个为value 它仅能取值0和1 另一个分量为信号量队列头指针listtypedefstructbinary semaphore intvalue structpcb list voidBP binary semaphore 可以证明 二元信号量与其他结构信号量具有一样的表达能力 16 3 3 3信号量实现进程互斥 semaphoremutex mutex 1 cobegin processPi i 1 2 n P mutex 临界区 V mutex coend 17 信号量解决机票问题 18 哲学家吃通心面问题 有五个哲学家围坐在一圆桌旁 桌中央有一盘通心面 每人面前有一只空盘于 每两人之间放一把叉子 每个哲学家思考 饥饿 然后吃通心面 为了吃面 每个哲学家必须获得两把叉子 且每人只能直接从自己左边或右边去取叉子 19 哲学家吃通心面问题示意图 4 0 0 1 4 3 1 2 3 2 哲学家 叉子 20 哲学家吃通心面问题 semaphorefork 5 for inti i 5 i fork i 1 cobeginprocessPhilosopher i i 0 1 2 3 4 while true think P fork i P fork i 1 5 eat V fork i V fork i 1 5 coend 21 上述算法能够实现进程的互斥 同步 但是 它可能发生死锁 如果每一个哲学家依次拿起右边 或者左边 的叉子 结果就会出现每一个人都拿到一把叉子 而都等待第二把叉子的现象 解决死锁问题的方案 至多允许4位哲学家吃面 奇数号哲学家先拿左边的叉子 偶数号哲学家先拿右边的叉子 规定每一个哲学家都必须拿到两把叉子才能吃面 否则一把也不拿 即当拿不到第二把叉子时 即放弃已拿到的第一把 注意 实现该方案需要修改信号量和PV操作的定义 22 生产者消费者问题 生产者和消费者共享缓冲区缓冲区中有空时 生产者可放入产品 不许放重 否则等待缓冲区中有产品时 消费者可取出产品 不许取重 否则等待 一个生产者 一个消费者共享一个缓冲区 一个生产者 一个消费者共享多个缓冲区 多个生产者 多个消费者共享多个缓冲区 多个生产者 多个消费者共享一个缓冲区 多个生产者 一个消费者共享多个缓冲区 一个生产者 多个消费者共享多个缓冲区 23 一个生产者一个消费者共享一个缓冲区 intB semaphforeempty 可以使用的空缓冲区数目semaphorefull 缓冲区内可以使用的产品的数目empty 1 初始缓冲区内允许放入一件产品full 0 初始缓冲区内没有产品 24 cobeginprocessproducer while true produce P empty append toB V full coend processconsumer while true P full take fromB V empty 25 过程分析 情况一 Producer P empty empty 0 进入临界区 Consumer P full full 1 挂起 Producer V full full 0 唤醒consumer Consumer 临界区语句 进入临界区 26 过程分析 情况二 Consumer P full full 1 挂起 Producer P empty empty 0 临界区 V full full 0 唤醒消费者 Consumer 临界区语句 V empty empty 1 Producer 27 一个生产者一个消费者共享多个缓冲区 前面的例子里生产者和消费者共享的是一个缓冲区 实际上 他们也可以共享多个缓冲区 为了实现协调 必须增加一个信号量 mutex信号量 初值1 使进程互斥地访问缓冲区empty信号量 初值k 保证生产者不向满的缓冲区存full信号量 初值0 保证消费者不从空的缓冲区取 28 m个消费者和n个生产者共享多个缓冲区 intB k semaphoreempty empty k semaphorefull full 0 semaphoremutex mutex 1 intin 0 intout 0 29 cobeginprocessproducer i while true produce P empty P mutex append toB in in in 1 k V mutex V full coend processconsumer j while true P full P mutex take fromB out out in 1 k V mutex V empty consume 30 实例分析 情况一 producer在临界区中 consumer加入 producer i P empty empty k 1 P mutex mutex 0 临界区consumer i P full full 1 挂起producer i V mutex mutex 1 V full full 0 唤醒consomer i comsumer i P mutex mutex 0 临界区 V mutex mutex 1 V empty empty k 31 实例分析 情况二 consumer先启动 consumer i P full full 1 挂起producer i P empty empty k 1 P mutex mutex 0 临界区 V mutex mutex 1 V full full 0 comsumer i P mutex mutex 0 临界区 V mutex mutex 1 V empty empty k 32 P操作的次序 如果有多个P操作 必须注意它们之间的顺序一般来说 用于互斥的信号量上的P操作应该在后面 V操作的次序无关紧要 讨论 如果在生产者进程中将P mutex 和P empty 交换则若缓冲区已满 empty 0 full k mutex 1 则producer P mutex mutex 0 P empty empty 1 挂起consumer P full full k 1 P mutex mutex 1 挂起 33 读者写者问题 有两组并发进程 读者和写者 共享一个文件F 要求 允许多个读者同时执行读操作任一写者在完成写操作之前不允许其它读者或写者工作写者执行写操作前 应让已有的写者和读者全部退出 34 单纯使用信号量不能解决问题 需要引入计数器readcount对读进程计数 mutex代表对计数器操作的互斥信号量 writelock表示是否允许写的信号量 intreadcount 0 semaphorewriteblock mutex writeblock 1 mutex 1 35 cobeginprocessreader i P mutex readcount if readcount 1 P writeblock V mutex 读文件 P mutex readcount if readcount 0 V writeblock V mutex 36 processwriter j P writeblock 写文件 V writeblock coend 37 本算法中 读者是优先的 当存在读者时 写者将被延迟 而且只要有一个读者活跃 随后的读者都被允许访问文件 从而导致写者长时间等待 并可能出现写者饥饿的现象 解决的方案 增加信号量修改程序 可以得到写者具有优先权的方案 确保当一个写者进程想要访问文件时 不允许新的读者进程访问 读者 写者锁 允许多名读者同时以只读方式存取有锁保护的对象 或者一位写者以写方式存取有锁保护的对象 当一名或多名读者已经上锁后 此时形成读锁 写者将不能访问有读锁保护的对象 当锁被请求者用于写操作时 形成写锁 其他进程的读写操作必须等待 38 写者优先的算法 增加一个信号量s 用于在写进程到来之后封锁后来的读进程 cobeginprocessreader i P s P mutex readcount if readcount 1 P writeblock V mutex V s 读文件 P mutex 39 readcount if readcount 0 V writeblock V mutex processwriter j P s P writeblock 写文件 V writeblock V s coend 40 读者 写者锁 允许多名读者同时以只读方式存取有锁保护的对象 或者一位写者以写方式存取有锁保护的对象 当一名或多名读者已经上锁后 此时形成读锁 写者将不能访问有读锁保护的对象 当锁被请求者用于写操作时 形成写锁 其他进程的读写操作必须等待 41 理发师问题 理发店有一位理发师 一把理发椅和n把供等候理发的顾客坐的椅子如果没有顾客 理发师便在理发椅上睡觉当一个顾客到来时 它必须叫醒理发师如果理发师正在理发时又有顾客来到 则如果有空椅子可坐 他们就坐下来等待 否则就离开 42 intwaiting 0 等候理发的顾客数intCHAIRS n 为顾客准备的椅子数semaphorecustomers barbers mutex customers 0 barb