操作系统习题课.pdf

操作系统习题课 四 操作系统习题课 四 赵俊峰赵俊峰 进程同步和互斥 一 进程同步和互斥 一 请用信号量解决以下的 独木桥 问题 同一方向的行人可连续过桥 当某一方向有 人过桥时 另一方向的行人必须等待 当某一方向无人过桥时 另一方向的行人可以 过桥 将独木桥的两个方向标记为A B 设置整型变量countA countB表示两个 方向已在独木桥的人数 初值为0 设置三个互斥信号量mutexA mutexB mutex mutexA mutexB 控制对countA countB操作 mutex 实现两个方向的行人对独木桥的互 斥使用 初值均为1 P mutexA If countA 0 P mutex countA countA 1 V mutexA 通过独木桥 P mutexA countA countA 1 if countA 0 V mutex V mutexA 初值 countA 0 mutexA mutex 1 A方向 方向 B方向类似方向类似 进程同步和互斥 一 进程同步和互斥 一 请用信号量解决以下的 独木桥 问题 同一方向的行人可连续过桥 当某一方向有 人过桥时 另一方向的行人必须等待 当某一方向无人过桥时 另一方向的行人可以 过桥 若上述独木桥仅允许最多6个行人在桥上 那 么应该如何解决 将独木桥的两个方向标记为A B 设置整型变量countA countB表示两个方向已 在独木桥的人数 初值为0 设置三个互斥信号量mutexA mutexB mutex mutexA mutexB 控制对countA countB操作 mutex 实现两个方向的行人对独木桥的互斥使用 初值均为1 maxcount 表示人数的计数 初值为6 P mutexA If countA 0 P mutex countA countA 1 V mutexA P maxcount 通过独木桥 V maxcount P mutexA countA countA 1 if countA 0 V mutex V mutexA 初值 countA 0 mutexA mutex 1 A方向 方向 B方向类似方向类似 问题 缺少过桥的文字说明 过桥行为缺失 问题 缺少过桥的文字说明 过桥行为缺失 GotoA代表从A方向来正在过桥或等待过 桥的人数 初始为0 GotoB代表从B方向来正在过桥或等待过 桥的人数 初始为0 Number代表还可以上桥的人数 等于6 Mutex A控制A Mutex B控制B Mutex 控制能否上桥 解法一 解法一 A进程 Repeat P Mutex A GotoA If GotoA 1 P Mutex V Mutex A P Number V Number 改变Count值 P Mutex A GotoA If GotoA 0 V Mutex Until False 同学的解答之一 将独木桥的两个方向标记为A B 设置整型变量countA countB表示两个方向准备上独木桥和 已经在独木桥上的人数 初值为0 设置四个互斥信号量mutexA mutexB maxcnt mutex 其中mutexA mutexB控制对countA countB操作 mutex实现两个方向的行人对独木桥的互斥使用 初值均为1 maxcnt表示对最 多6人上桥的限制信号量 初值为6 VAR mutex1 mutex2 mutex3 R W semaphore 三个互斥信号量 读信号量 写信号量 mutexA 1 mutexB 1 mutex 1 maxcnt 6 设初值 int countA 0 countB 0 A方向进程P REPEAT P mutexA if countA 0 P mutex countA countA 1 V mutexA P maxcnt 通过独木桥 V maxcnt P mutexA countA countA 1 if countA 0 V mutex V mutexA UNTIL false B方向进程Q REPEAT P mutexB if countB 0 P mutex countB countB 1 V mutexB P maxcnt 通过独木桥 V maxcnt P mutexB countB countB 1 if countB 0 V mutex V mutexB UNTIL false 向左的进程 P mutex1 互斥修改变量 left num left num 1 标记到 来 if left num 1 then P direction 第一个人要去争取本 方向通行 后面的人在这之前也都卡 在mutex1处 V mutex1 P weight 既然进程运行到这就意 味着该方向通行了 接下来就是按最 多六个人来排队了 过桥 V weight P mutex1 left num left num 1 标记离 开 if left num 0 then V direction 通行方向无人 放开 控制权 V mutex1 向右的进程 与向左不同即为mutex1 mutex2 left num right num P mutex2 互斥修改变量 right num right num 1 标记到来 if right num 1 then P direction 第一个人要去争取本方向 通行 后面的人在这之前也都卡在mutex2 处 V mutex2 P weight 既然进程运行到这就意味着 该方向通行了 接下来就是按最多六个人来 排队了 过桥 V weight P mutex2 right num right num 1 标记离开 if right num 0 then V direction 通行方向无人 放开控制 权 V mutex2 信息量信息量 mutex1 1 对向左人的互斥量 mutex2 1 对向右人的互斥量 direction 1 通行方向的互斥量 weight 6 桥能承载的人数 左右方向通用 变量 变量 left num 0 要向左去的人数 right num 0 要向右去的人数 同学的解答之二 进程同步和互斥 二 进程同步和互斥 二 桌上有一只盘子 每次只能放入一只水果 桌上有一只盘子 每次只能放入一只水果 爸爸专门向盘子放苹果 爸爸专门向盘子放苹果 apple 妈妈专门 妈妈专门 向盘子中放桔子 向盘子中放桔子 orange 一个儿子专等 一个儿子专等 吃盘子中的桔子 一个女儿专等吃盘子中的吃盘子中的桔子 一个女儿专等吃盘子中的 苹果 苹果 问题分析 两个生产者和两个消费者被连结到 仅能放一个产品的缓冲区上 生产者各自生产 不同的产品 消费者则各自取需要的产品消费 他们的消费方式不同 设置变量 plate integer sp semaphore 盘子里可以放几个水果 orange semaphore 盘子里有桔子 apple semaphore 盘子里有苹果 sp 1 orange 0 apple 0 父亲进程 父亲进程 Begin L1 削一个苹果削一个苹果 P sp 把苹果放入把苹果放入plate V apple Goto L1 End 问题解答 儿子进程 儿子进程 Begin L3 P orange 从从plate中取桔子中取桔子 V sp 吃桔子吃桔子 Goto L3 End sp 1 orange apple 0 母亲进程 母亲进程 Begin L2 剥一个桔子剥一个桔子 P sp 把桔子放入把桔子放入plate V orange Goto L2 End 女儿进程 女儿进程 Begin L4 P apple 从从plate中取苹果中取苹果 V sp 吃苹果吃苹果 Goto L4 End 进程同步和互斥 三 进程同步和互斥 三 桌上有一只盘子 最多可以容纳桌上有一只盘子 最多可以容纳2个水果 每个水果 每 次只能放入或取出一个水果 爸爸专门向盘次只能放入或取出一个水果 爸爸专门向盘 子放苹果 子放苹果 apple 妈妈专门向盘子中放桔 妈妈专门向盘子中放桔 子 子 orange 2个儿子专等吃盘子中的桔个儿子专等吃盘子中的桔 子 子 2个女儿专等吃盘子中的苹果 个女儿专等吃盘子中的苹果 设置变量 plate integer sp semaphore 盘子里可以放几个水果 orange semaphore 盘子里有桔子 apple semaphore 盘子里有苹果 mutex semaphore 互斥变量 sp 2 orange 0 apple 0 mutex 1 父亲进程 父亲进程 Begin L1 削一个苹果削一个苹果 P sp P mutex 把苹果放入把苹果放入plate V mutex V apple Goto L1 End 问题解答 儿子进程 儿子进程 Begin L3 P orange P mutex 从从plate中取桔子中取桔子 V mutex V sp 吃桔子吃桔子 Goto L3 End sp 2 orange apple 0 mutex 1 母亲进程 母亲进程 Begin L2 剥一个桔子剥一个桔子 P sp P mutex 把桔子放入把桔子放入plate V mutex V orange Goto L2 End 女儿进程 女儿进程 Begin L4 P apple P mutex 从从plate中取苹果中取苹果 V mutex V sp 吃苹果吃苹果 Goto L4 End 两个进程两个进程PA PB通过两个通过两个FIFO 先进先出 缓冲 先进先出 缓冲 区队列连接 如图 区队列连接 如图 PA从从Q2取消息 处理后往取消息 处理后往Q1发消息 发消息 PB从从Q1取取 消息 处理后往消息 处理后往Q2发消息 每个缓冲区长度等于传发消息 每个缓冲区长度等于传 送消息长度送消息长度 Q1队列长度为队列长度为n Q2队列长度为队列长度为m 假设开始时假设开始时Q1中装满了消息 试用中装满了消息 试用P V操作解决操作解决 上述进程间通讯问题上述进程间通讯问题 PBPA Q2 Q1 进程同步和互斥 三 进程同步和互斥 三 需要如下的信号量 S BuffNum Q1 0 S BuffNum Q2 m S MessageNum Q1 n S MessageNum Q2 0 进程PA while 1 P S MessageNum Q2 取消息 V S BuffNum Q2 处理消息 生成新的消息 P S BuffNum Q1 放消息到Q1 V S MessageNum Q1 进程PB while 1 P S MessageNum Q1 取消息 V S BuffNum Q1 处理消息 生成新的消息 P S BuffNum Q2 放消息到Q2 V S MessageNum Q2 在一栋学生公寓里 只有一间电话室 而且这间电话室非在一栋学生公寓里 只有一间电话室 而且这间电话室非 常小 每一次只能容纳一个人 公寓里既住着男生也住着常小 每一次只能容纳一个人 公寓里既住着男生也住着 女生 他们不得不分享这间电话室 因此 楼长制定了以女生 他们不得不分享这间电话室 因此 楼长制定了以 下的电话室使用规则 下的电话室使用规则 1 每一次只能有一个人在使用 每一次只能有一个人在使用 2 女生的优先级要高于男生 即如果同时有男生和女 女生的优先级要高于男生 即如果同时有男生和女 生在等待使用电话室 则女生优先 生在等待使用电话室 则女生优先 3 对于相同性别 对于相同性别 的人来说 采用先来先使用的原则 的人来说 采用先来先使用的原则 假设 假设 1 当一个男生想要使用电话室时 他会去执行一个函数 当一个男生想要使用电话室时 他会去执行一个函数 boy wants to use telephoneroom 当他离开电话室 当他离开电话室 时 也会去执行另外一个函数时 也会去执行另外一个函数 boy leaves telephoneroom 2 当一个女生想要使用电话室时 会去执行函数 当一个女生想要使用电话室时 会去执行函数 girl wants to use telephoneroom 当她离开时 当她离开时 也会也会 执行函数执行函数girl leaves telephoneroom 问题 请用信号量和问题 请用信号量和P V操作来实现这四个函数 初始状操作来实现这四个函数 初始状 态 电话室是空的 态 电话室是空的 进程同步和互斥 四 进程同步和互斥 四 信号量与其他变量的设置 信号量的定义 semaphore S mutex 互斥信号量 初值均为1 semaphore S boys 男生等待队列 初值为0 semaphore S girls 女生等待队列 初值为0 普通变量的定义 int boys waiting 0 正在等待的男生数 int girls waiting 0 正在等待的女生数 int using 0 当前是否有 人在使用电话室 void boy wants to use telephoneroom P S mutex if using 0 V S mutex else boys waiting V S mutex P S boys void boy leaves telephoneroom P S mutex if girls waiting 0 优先唤醒女生优先唤醒女生 girls waiting V S girls else if boys waiting 0 boys waiting V S boys else using 0 无人在等待无人在等待 V S mutex void girl wants to use telephoneroom P S mutex if using 0 using 1 V S mutex else girls waiting V S mutex P S girls void girl leaves telephoneroom P S mutex if girls waiting 0 优先唤醒女生优先唤醒女生 girls waiting V S girls else if boys waiting 0 boys waiting V S boys else using 0 无人在等待无人在等待 V S mutex 发送消息原语 Send R M Begin 根据R找接收进程 如果没找到出错返回 申请空缓冲区P s b P b mutex 摘空缓冲区 V b mutex 把消息从M处copy到空缓冲区 P b mutex 根据m q 把缓冲区挂到接收进程的消息链链尾 V b mutex V s syn END 消息缓冲通信 其中 s b 空缓冲区个数 初值 n b mutex 空缓冲区的互斥信号 量 初值为1 s syn 同步信号量 初值为0 用 于消息计数 进程同步和互斥 五 进程同步和互斥 五 消息缓冲通信 接收消息原语Receive S M Begin 根据S找发送进程 如果没找到出错返回 申请缓冲区消息P s syn P b mutex 将载有消息的缓冲区从消息链中取出 V b mutex 把消息从M处copy到receiver的信息空间 P b mutex 将缓冲区清空 V b mutex V s b End 其中 s b 空缓冲区个数 初 值 n b mutex 空缓冲区的 互斥信号量 初值为1 s syn 同步信号量 初 值为0 用于消息计数 进程同步和互斥 六 进程同步和互斥 六 一个快餐厅有4类职员 1 领班 接受顾 客点菜 2 厨师 准备顾客的饭菜 3 打包工 将做好的饭菜打包 4 出纳员 收款并提交食品 每个职员可被看作一个 进程 试用一种同步机制写出能让四类职员 正确并发运行的程序 var S1 S2 S3 S4 semaphore 领班 S1 厨师S2 打包工S3 出纳 员S4 S1 1 S2 S3 S4 0 进程同步和互斥 七 进程同步和互斥 七 某银行有人民币储蓄业务 由 n个柜员负 责 每个顾客进入银行后先取一个号 并 且等着叫号 当一个柜台人员空闲下来 就叫下一个号 试用P V操作正确编写柜台人员和顾客进 程的程序 Semaphore counter 柜台数 初值为n Semaphore waiting 当前等待的顾客数 初值为0 Semaphore mutex 互斥对顾客号数的访问 初值为1 Customer i int num P mutex num COSTOMER NUM V mutex V waiting 请求服务 P counter 等待叫号 接受服务 离开 P mutex COSTOMER NUM V mutex Clerk i While true P waiting 等待顾客 V counter 叫号 服务 P s s s 1 If s 0 Then 将本进程插入相应队列将本进程插入相应队列末尾末尾等待 等待 V s s s 1 If s 0 Then 从等待队列从等待队列队尾队尾取一个进程唤醒 取一个进程唤醒 插入就绪队列插入就绪队列 进程同步和互斥 八 进程同步和互斥 八 对对 P V 操作定义作以下修改操作定义作以下修改 问题 问题 1 这样定义 这样定义P V操作是否有问题 操作是否有问题 2 用这样的 用这样的P V操作实现操作实现N个进程竞争使用某个进程竞争使用某 一共享变量的互斥机制 一共享变量的互斥机制 不合理 先进后出 可能不合理 先进后出 可能 无限等待无限等待 思路 令等待队列中始终只有一个进程 思路 令等待队列中始终只有一个进程 将将 栈栈 变成变成 队列队列 进程间相互作用进程间相互作用 课程内容总结课程内容总结 进程 信号量及P V操作 每个信号量 s 除一个整数值整数值s value 计数 外 还有一个进程等待队列进程等待队列s queue 其中是 阻塞在该信号量的各个进程的标识 信号量只能通过初始化初始化和两个标准的原语两个标准的原语来 访问 作为OS核心代码执行 不受进程调度不受进程调度 的打断的打断 初始化初始化指定一个非负整数值 表示空闲资源总空闲资源总 数数 又称为 资源信号量 若为非负值表示 当前的空闲资源数当前的空闲资源数 若为负值其绝对值表示当当 前等待临界区的进程数前等待临界区的进程数 进程 信号量及P V操作 信号量 semaphore 是一个数据结构 定义如下 TYPE semaphore RECORD Value integer Queue Pointer PCB END 信号量说明 VAR S semaphore 利用信号量利用信号量S S的取值表示共享资源的使用情的取值表示共享资源的使用情 况 用它来指示协作进程之间交换的信息况 用它来指示协作进程之间交换的信息 进程 信号量及P V操作 P操作 P s 表示对信号量S实施的P操作 s Value s Value 1 表示申请一个资源 IF s Value 0 then 表示没有空闲资源 将该进程状态置为等待状态等待状态 阻塞该进程阻塞该进程 然后将该进程的进程的PCB插入相应的插入相应的S信号量等信号量等 待队列末尾待队列末尾 直至有其他进程在S上执行V 操作 进程 信号量及P V操作 V操作 V s 表示对信号量S实施的V操作 s Value s Value 1 表示释放一个资源 IF s Value 0S 0表示有S S个资源可用个资源可用 S 0S 0表示无资源可用无资源可用 S 0S 0则 S S 表示S S等待队列中的进程个数等待队列中的进程个数 P S P S 表示申请一个资源申请一个资源 V S V S 表示释放一个资源释放一个资源 信号量的初值应 该大于等于0 进程 信号量及P V操作 2 P V操作必须成对出现 有一个P操作就一定 有一个V操作 当为互斥互斥操作时 它们同处于同一进程同处于同一进程 当为同步同步操作时 则不在同一进程中不在同一进程中出现 如果P S1 和P S2 两个操作在一起 那么P操作 的顺序至关重要 一个同步一个同步P P操作与一个互斥操作与一个互斥P P操操 作在一起时作在一起