操作系统PV操作习题

一 用一 用 P V 操作描述前趋关系 操作描述前趋关系 P1 P2 P3 P4 P5 P6 为一组合作进程 其前趋图如图为一组合作进程 其前趋图如图 2 3 所示 试用所示 试用 P V 操作描述这操作描述这 6 个进程的同步 个进程的同步 p23 图图 2 3 说明任务启动后说明任务启动后 P1 先执行 当它结束后先执行 当它结束后 P2 P3 可以开始执行 可以开始执行 P2 完成后完成后 P4 P5 可以开始执行 仅当可以开始执行 仅当 P3 P4 P5 都执行完后 都执行完后 P6 才能开始执行 为了确保这一才能开始执行 为了确保这一 执行顺序 设置执行顺序 设置 5 个同步信号量个同步信号量 n 摄 摄 f3 f4 g 分别表分别表 示进程示进程 P1 P2 P3 P4 P5 是否执行完成 其初值均为是否执行完成 其初值均为 0 这 这 6 个进程的同步描述如下 个进程的同步描述如下 图图 2 3 描述进程执行先后次序的前趋图描述进程执行先后次序的前趋图 int f1 0 表示进程表示进程 P1 是否执行完成是否执行完成 int f2 0 表示进程表示进程 P2 是否执行完成是否执行完成 int f3 0 表示进程表示进程 P3 是否执行完成是否执行完成 int f4 0 表示进程表示进程 P4 是否执行完成是否执行完成 int f5 0 表示进程表示进程 P5 是否执行完成是否执行完成 main cobegin P1 P2 P3 P4 P5 P6 coend P1 v f1 v f1 P2 p f1 v f2 v f2 P3 p f1 v f3 P4 p f2 v f4 P5 p f2 v f5 P6 p f3 p f4 p f5 二 生产者二 生产者 消费者问题消费者问题 p25 生产者生产者 消费者问题是最著名的进程同步问题 它描述了消费者问题是最著名的进程同步问题 它描述了 一组生产者向一组消费者提供产品 它们共享一个有界缓一组生产者向一组消费者提供产品 它们共享一个有界缓 冲区 生产者向其中投放产品 消费者从中取得产品 生冲区 生产者向其中投放产品 消费者从中取得产品 生 产者产者 消费者问题是许多相互合作进程的一种抽象 例如 消费者问题是许多相互合作进程的一种抽象 例如 在输入时 输入进程是生产者 计算进程是消费者在输入时 输入进程是生产者 计算进程是消费者 在输出在输出 时 计算进程是生产者 打印进程是消费者 因此 该问时 计算进程是生产者 打印进程是消费者 因此 该问 题具有很大实用价值 题具有很大实用价值 我们把一个长度为我们把一个长度为 n 的有界缓冲区的有界缓冲区 n 0 与一群生产者进与一群生产者进 程程 P P Pm 和一群消费者进程和一群消费者进程 C C Ck 联系起来 如图联系起来 如图 2 4 所示 假定这些生产者和消费者是互所示 假定这些生产者和消费者是互 相等效的 只要缓冲区未满 生产者就可以把产品送入缓相等效的 只要缓冲区未满 生产者就可以把产品送入缓 冲区 类似地 只要缓冲区未空 消费者便可以从缓冲区冲区 类似地 只要缓冲区未空 消费者便可以从缓冲区 中取走物品并消耗它 生产者和消费者的同步关系将禁止中取走物品并消耗它 生产者和消费者的同步关系将禁止 生产者向满的缓冲区输送产品 也禁止消费者从空的缓冲生产者向满的缓冲区输送产品 也禁止消费者从空的缓冲 区中提取物品 区中提取物品 图图 2 4 生产者生产者 消费者问题消费者问题 为解决这一类生产者为解决这一类生产者 消费者问题 应该设置两个同步信消费者问题 应该设置两个同步信 号量 一个说明空缓冲单元的号量 一个说明空缓冲单元的 数目 用数目 用 empty 表示 其初值为有界缓冲区的大小表示 其初值为有界缓冲区的大小 n 另 另 一个说明满缓冲单元的数目 用一个说明满缓冲单元的数目 用 full 表示 其初值为表示 其初值为 0 在本例中有 在本例中有 P P Pm 个生个生 产者和产者和 C C Ck 个消费者 它们在执行生产活动个消费者 它们在执行生产活动 和消费活动中要对有界缓冲区进行操作 由于有界缓冲区和消费活动中要对有界缓冲区进行操作 由于有界缓冲区 是一个临界资源 必须互斥使用 所以 另外还需设置一是一个临界资源 必须互斥使用 所以 另外还需设置一 个互斥信号量个互斥信号量 mutex 其初值为 其初值为 1 生产者 生产者 消费者问题的消费者问题的 同步描述如下 同步描述如下 int full O 满缓冲单元的数目满缓冲单元的数目 int empty n 空缓冲单元的数目空缓冲单元的数目 int mutex 1 对有界缓冲区进行操作的互斥信号量对有界缓冲区进行操作的互斥信号量 main cobegin produceri i 1 2 m j l 2 k consumerj coend produceri i 1 2 m while 生产未完成生产未完成 生产一个产品生产一个产品 p empty p mutex 送一个产品到有界缓冲区送一个产品到有界缓冲区 v mutex v full consumerj j 1 2 k while 还要继续消费还要继续消费 p full p mutex 从有界缓冲区中取产品从有界缓冲区中取产品 v mutex v empty 消费一个产品消费一个产品 三 在操作系统中 进程是一个具有一定独立功能的程序三 在操作系统中 进程是一个具有一定独立功能的程序 在某个数据集上的一次在某个数据集上的一次 A 等待活动 等待活动 B 运行活动 运行活动 C 单独操作 单独操作 D 关联操作 关联操作 答 答 B 四 多道程序环境下 操作系统分配资源以四 多道程序环境下 操作系统分配资源以 为基本单位 为基本单位 A 程序 程序 B 指令 指令 C 进程进程 D 作业 作业 答 答 C 五 对于两个并发进程 设互斥信号量为五 对于两个并发进程 设互斥信号量为 mutex 若 若 mutex O 则 则 A 表示没有进程进入临界区表示没有进程进入临界区 B 表示有一个进程进入临界区表示有一个进程进入临界区 C 表示有一个进程进入临界区 另一个进程等待进入表示有一个进程进入临界区 另一个进程等待进入 D 表示有两个进程进入临界区表示有两个进程进入临界区 答 答 B 六 两个进程合作完成一个任务 在并发执行中 一个进六 两个进程合作完成一个任务 在并发执行中 一个进 程要等待其合作伙伴发来消程要等待其合作伙伴发来消 息 或者建立某个条件后再向前执行 这种制约性合作息 或者建立某个条件后再向前执行 这种制约性合作 关系被称为进程的 关系被称为进程的 A 同步同步 B 互斥 互斥 C 调度调度 D 执行 执行 答 答 A 七 为了进行进程协调 进程之间应当具有一定的联系 七 为了进行进程协调 进程之间应当具有一定的联系 这种联系通常采用进程间交换数据的方式进行 这种方式这种联系通常采用进程间交换数据的方式进行 这种方式 称为 称为 A 进程互斥进程互斥 B 进程同步 进程同步 C 进程制约进程制约 D 进程 进程 通信通信 答 答 D 八 在测量控制系统中 数据采集任务把所采集的数据送八 在测量控制系统中 数据采集任务把所采集的数据送 入一单缓冲区入一单缓冲区 计算任务从该单缓冲区中取出数据进行计计算任务从该单缓冲区中取出数据进行计 算 试写出利用信号量机制实现两者共享单缓冲区的同算 试写出利用信号量机制实现两者共享单缓冲区的同 步算法 步算法 P33 分析及相关知识分析及相关知识 在本题中采集任务与计算任务共用一个在本题中采集任务与计算任务共用一个 单缓冲区 当采集单缓冲区 当采集 任务采集到一个数据后 只有当缓冲任务采集到一个数据后 只有当缓冲 区为空时才能将数据送入缓冲区中存放 否则应等待缓冲区为空时才能将数据送入缓冲区中存放 否则应等待缓冲 区腾空区腾空 当缓冲区中有数据时 计算任务才能从缓冲区中取当缓冲区中有数据时 计算任务才能从缓冲区中取 出数据进行计算 否则也应等待 出数据进行计算 否则也应等待 本题实际上是一个生产者本题实际上是一个生产者 消费者问题 将生产者消费者问题 将生产者 消消 费者问题抽象出来 以另外费者问题抽象出来 以另外 一种形式描述是一种常见的一种形式描述是一种常见的 试题形式 只要对生产者试题形式 只要对生产者 消费者问题有了深入的理消费者问题有了深入的理 解 解 就不难解决此类试题 就不难解决此类试题 解解 在本题中 应设置两个信号量在本题中 应设置两个信号量 Sf Se 信号量 信号量 Sf 表示表示 缓冲区中是否有可供打印的计算结果 其初值为缓冲区中是否有可供打印的计算结果 其初值为 0 信号量信号量 Se 用于表示缓冲区有无空位置存放新的信息 其初值为用于表示缓冲区有无空位置存放新的信息 其初值为 1 本题的同步描述如下 本题的同步描述如下 int Se l int Sf 0 main cobegin get compute coend get while 采集工作未完成采集工作未完成 采集一个数据 采集一个数据 p Se 将数据送入缓冲区中将数据送入缓冲区中 v Sf compute while 计算工作未完成计算工作未完成 p Sf 从缓冲区中取出数据从缓冲区中取出数据 v Se 进行数据计算进行数据计算 九 图九 图 2 7 给出了四个进程合作完成某一任务的前趋图 给出了四个进程合作完成某一任务的前趋图 试说明这四个进程间的同步关系 并用试说明这四个进程间的同步关系 并用 P V 操作描述它 操作描述它 P35 图图 2 7 四个合作进程的前趋图四个合作进程的前趋图 解 图解 图 2 7 说明任务启动后说明任务启动后 S1 先执行 当先执行 当 S1 结束后 结束后 S2 S3 可以开始执行 可以开始执行 S2 S3 完成后 完成后 S4 才能开始执行 为了确保这一执行顺序 设三才能开始执行 为了确保这一执行顺序 设三 个同步信号量个同步信号量 b2 b3 b4 分别分别 表示进程表示进程 S2 S3 S4 是否可以开始执行 其初值均为是否可以开始执行 其初值均为 0 这四个进程的同步描述如下 这四个进程的同步描述如下 int b2 0 表示进程表示进程 S2 是否可以开始执行是否可以开始执行 int b3 0 表示进程表示进程 S3 是否可以开始执行是否可以开始执行 int b4 0 表示进程表示进程 S4 是否可以开始执行是否可以开始执行 main cobegin S1 S2 S3 S4 coend S1 v b2 v b3 S2 p b2 v b4 S3 p b3 v b4 S4 p b4 p b4 因在因在 S2 及及 S3 完成时均对完成时均对 b4 做了做了 v 操作 操作 因此这里要用两个因此这里要用两个 p 操作操作 十 桌上有一空盘 允许存放一只水果 爸爸可向盘中放十 桌上有一空盘 允许存放一只水果 爸爸可向盘中放 苹果 也可向盘中放桔子 儿子专等吃盘中的桔子 女儿苹果 也可向盘中放桔子 儿子专等吃盘中的桔子 女儿 专等吃盘中的苹果 规定当盘空时一次只能放一只水果供专等吃盘中的苹果 规定当盘空时一次只能放一只水果供 吃者取用 请用吃者取用 请用 P V 原语实现爸爸 儿子 女儿三个并原语实现爸爸 儿子 女儿三个并 发进程的同步 发进程的同步 P37 分析及相关知识分析及相关知识 在本题中 爸爸 儿子 女儿共用一个在本题中 爸爸 儿子 女儿共用一个 盘子 且盘中一次只能放一个水果 当盘子为空时 爸爸盘子 且盘中一次只能放一个水果 当盘子为空时 爸爸 可将一个水果放入果盘中 若放入果盘中的是桔子 则允可将一个水果放入果盘中 若放入果盘中的是桔子 则允 许儿子吃 女儿必须等待许儿子吃 女儿必须等待 若放入果盘中的是苹果 则允若放入果盘中的是苹果 则允 许女儿吃 儿子必须等待 本题实际上是生产者许女儿吃 儿子必须等待 本题实际上是生产者 消费者消费者 问题的一种变形 这里 生产者放入缓冲区的产品有两类 问题的一种变形 这里 生产者放入缓冲区的产品有两类 消费者也有两类 每类消费者只消费其中固定的一类产品 消费者也有两类 每类消费者只消费其中固定的一类产品 解 在本题中 应设置三个信号量解 在本题中 应设置三个信号量 S So Sa 信号量 信号量 S 表示盘子是否为空 其初值表示盘子是否为空 其初值 为为 1 信号量信号量 So 表示盘中是否有桔子 其初值为表示盘中是否有桔子 其初值为 0 信号量信号量 Sa 表示盘中是否有苹果 其初表示盘中是否有苹果 其初 值为值为 0 同步描述如下 同步描述如下 int S 1 int Sa O int So O main cobegin father son daughter coend father while 1 p S 将水果放入盘中将水果放入盘中 if 放入的是桔子放入的是桔子 v So else v Sa son while 1 p So 从盘中取出桔子从盘中取出桔子 v S 吃桔子吃桔子 dau shter while 1 p Sa 从盘中取出苹果从盘中取出苹果 v S 吃苹果吃苹果 答答 十一 十一 华中理工大学华中理工大学 1999 年试题年试题 设公共汽车上 司机和设公共汽车上 司机和 售票员的活动分别是 售票员的活动分别是 p41 司机的活动 司机的活动 启动车辆 启动车辆 正常行车正常行车 到站停车到站停车 售票员的活动 售票员的活动 关车门关车门 售票 售票 开车门开车门 在汽车不断地到站 停车 行驶过程中 这两个活动有在汽车不断地到站 停车 行驶过程中 这两个活动有 什么同步关系什么同步关系 用信号量和用信号量和 P V 操作实现它们的同步 操作实现它们的同步 解解 在汽车行驶过程中 司机活动与售票员活动之间的同在汽车行驶过程中 司机活动与售票员活动之间的同 步关系为 售票员关车门后 步关系为 售票员关车门后 向司机发开车信号 司机向司机发开车信号 司机 接到开车信号后启动车辆 在汽车正常行驶过程中售票员接到开车信号后启动车辆 在汽车正常行驶过程中售票员 售票 到站时司机停车 售票员在车停后开车门让乘客上售票 到站时司机停车 售票员在车停后开车门让乘客上 下车 因此司机启动车辆的动作必须与售票员关车门的动下车 因此司机启动车辆的动作必须与售票员关车门的动 作取得同步作取得同步 售票员开车门的动作也必须与司机停车取得同售票员开车门的动作也必须与司机停车取得同 步 步 在本题中 应设置两个信号量 在本题中 应设置两个信号量 s1 s2 s1 表示是否允表示是否允 许司机启动汽车 其初值为许司机启动汽车 其初值为 0 s2 表示是否允许售票员开表示是否允许售票员开 门 其初值为门 其初值为 0 用 用 P V 原语描述如下 原语描述如下 int s1 O int s2 O main cobegin driver busman coend driver while 1 p s1 启动车辆启动车辆 正常行车正常行车 到站停车到站停车 v s2 busman while 1 关车门关车门 v s1 售票售票 p s2 开车门开车门 上下乘客上下乘客 用用 P V 操作来控制现实生活中的操作流程是一类常见操作来控制现实生活中的操作流程是一类常见 的试题 这类试题要求解题者的试题 这类试题要求解题者 能将生活中的控制流程用形式化的方式表达出来 能将生活中的控制流程用形式化的方式表达出来 十二 设有一个发送者进程和一个接收者进程 其流程图十二 设有一个发送者进程和一个接收者进程 其流程图 如图如图 2 10 所示 所示 s 是用于实现进程同步的信号量 是用于实现进程同步的信号量 mutex 是用于实现进程互斥的信号量 试问流程图中的是用于实现进程互斥的信号量 试问流程图中的 A B C D 四框中应填写什么四框中应填写什么 假定缓冲区有无限多个 假定缓冲区有无限多个 s 和和 mutex 的初值应为多少的初值应为多少 p42 分析及相关知识分析及相关知识 由图由图 2 10 可以看出 发送者进程与接可以看出 发送者进程与接 收者进程之间的同步关系是 发送者进程生成的信息送入收者进程之间的同步关系是 发送者进程生成的信息送入 消息链中 接收者进程从消息链中接收信息消息链中 接收者进程从消息链中接收信息 由于发送者进由于发送者进 程产生一个消息并链入消息链后用程产生一个消息并链入消息链后用 V 操作增加消息计数并操作增加消息计数并 唤醒接收者进程 这表示发送者进程和接收者进程是通过唤醒接收者进程 这表示发送者进程和接收者进程是通过 信号量信号量 s 实现同步的 因此接收者进程应该在取信息之前先实现同步的 因此接收者进程应该在取信息之前先 使用一个使用一个 P 操作来查看消息链上是否有消息 若无消 息操作来查看消息链上是否有消息 若无消 息 则阻塞自己则阻塞自己 另外 发送者和接收者对消息链的访问应使用另外 发送者和接收者对消息链的访问应使用 信号量进行互斥 即在访问前使用信号量进行互斥 即在访问前使用 P 操作 在访问后使用操作 在访问后使用 V 操作 操作 图图 2 10 发送者及接收者工作流程图发送者及接收者工作流程图 解 由上述分析可知 解 由上述分析可知 A B C D 四框应分别填入 四框应分别填入 A 框框 P mutex B 框框 V mutex C 框框 P s D 框框 P mutex 开始时 消息链上没有可供接收的信息 所以开始时 消息链上没有可供接收的信息 所以 s 的初值为的初值为 0 互互 斥信号量斥信号量 mutex 的初值应为的初值应为 1 十三 十三 北京大学北京大学 1990 年试题年试题 p46 写出写出 P V 操作的定义 操作的定义 有三个进程有三个进程 PA PB 和和 PC 合作解决文件打印问题 合作解决文件打印问题 PA 将文件记录从磁盘读入主存将文件记录从磁盘读入主存 的缓冲区的缓冲区 1 每执行一次读一个记录 每执行一次读一个记录 PB 将缓冲区将缓冲区 1 的内的内 容复制到缓冲区容复制到缓冲区 2 每执行一次 每执行一次 复制一个记录 复制一个记录 PC 将缓冲区将缓冲区 2 的内容打印出来 每执行的内容打印出来 每执行 一次打印一个记录 缓冲区的大小等于一个记录大小 请一次打印一个记录 缓冲区的大小等于一个记录大小 请 用用 P V 操作来保证文件的正确打印 操作来保证文件的正确打印 分析及相关知识分析及相关知识 信号量是一个确定的二元组信号量是一个确定的二元组 s q 其 其 中中 s 是一个具有非负初值的整型变量 是一个具有非负初值的整型变量 q 是一个与是一个与 s 相关联相关联 的初始状态为空的队列 整型变量的初始状态为空的队列 整型变量 s 表示系统中某类资源的表示系统中某类资源的 数目 当其值大于数目 当其值大于 0 时 表示系统中当前可用资源的数目时 表示系统中当前可用资源的数目 当其值小于当其值小于 0 时 其绝对值表示系统中因请求谊类资源而时 其绝对值表示系统中因请求谊类资源而 被阻塞的进程数目 除信号量的初值外 信号量的值仅能被阻塞的进程数目 除信号量的初值外 信号量的值仅能 由由 P 操作和操作和 V 操作改变 操作改变 解 解 P V 操作是两条原语 它们的定义如下 操作是两条原语 它们的定义如下 P 操作操作 P 操作记为操作记为 P S 其中 其中 S 为一信号量 它执行为一信号量 它执行 时主要完成下述动作 时主要完成下述动作 S S 1 若若 S 0 则进程继续运行 则进程继续运行 若若 S0 则进程继续执行 则进程继续执行 若若 S 0 则从信号量等待队列中移出队首进程 使其变 则从信号量等待队列中移出队首进程 使其变 为就绪状态 为就绪状态 在本题中 进程在本题中 进程 PA PB PC 之间的关系为 之间的关系为 PA 与与 pB 共用一个单缓冲区 而共用一个单缓冲区 而 PB 又与又与 PC 共用一个单缓冲区 其合作方式可用图共用一个单缓冲区 其合作方式可用图 2 12 表示 当缓冲区表示 当缓冲区 1 为空时 进程为空时 进程 PA 可将一个记录读入其中可将一个记录读入其中 若若 缓冲区缓冲区 1 中有数据且缓冲区中有数据且缓冲区 2 为空 则进程为空 则进程 PB 可将记录从可将记录从 缓冲区缓冲区 1 复制到缓冲区复制到缓冲区 2 中中 若缓冲区若缓冲区 2 中有数据 则进程中有数据 则进程 PC 可以打印记录 在其他条件可以打印记录 在其他条件 下 相应进程必须等待 下 相应进程必须等待 事实上 这是一个生产者事实上 这是一个生产者 消费者问题 消费者问题 图图 2 12 进程间的合作方式进程间的合作方式 为遵循这一同步规则 应设置四个信号量为遵循这一同步规则 应设置四个信号量 emptyl empty2 full1 full2 信号量 信号量 emptyl 及及 empty2 分别表示缓冲区分别表示缓冲区 1 及缓冲区及缓冲区 2 是否为空 其初值是否为空 其初值 为为 1 信号量信号量 full1 及及 full2 分别表示缓冲区分别表示缓冲区 1 及缓冲区及缓冲区 2 是是 否有记录可供处理 其初值为否有记录可供处理 其初值为 0 其同步描述如下 其同步描述如下 int emptyl l int empty2 l int fulll O int full2 O main cobegin PA PB PC coend PA while 1 从磁盘读一个记录 从磁盘读一个记录 p emptyl 将记录存入缓冲区将记录存入缓冲区 1 v fulll PB while 1 p fulll 从缓冲区从缓冲区 1 中取出记录中取出记录 v emptyl p empty2 将记录存入缓冲区将记录存入缓冲区 2 v full2 PC while 1 p full2 从缓冲区从缓冲区 2 中取出记录中取出记录 v empty2 打印记录打印记录 本题也是一个典型的生产者 消费者问题 其中的难点本题也是一个典型的生产者 消费者问题 其中的难点 在于在于 PB 既是既是 个生产者又是一个消费者 个生产者又是一个消费者 十四 设有十四 设有 8 个程序个程序 progl prog2 prog8 它们在并 它们在并 发系统中执行时有如图发系统中执行时有如图 2 13 所示的制约关系 试用所示的制约关系 试用 P V 操作实现这些程序间的同步 操作实现这些程序间的同步 P48 解 由图解 由图 2 13 表明开始时 表明开始时 progl 及及 prog2 先执行 当先执行 当 progl 和和 prog2 都执行完后 都执行完后 prog3 prog4 prog5 才可以开始执行 才可以开始执行 prog3 完成后 完成后 prog6 才才 能开始执行 能开始执行 prog5 完成后 完成后 prog7 才能开始执行 才能开始执行 prog6 prog4 prog7 都结束后 都结束后 prog8 才可以开始执行 为了确保这一执行顺序 设才可以开始执行 为了确保这一执行顺序 设 7 个同步信个同步信 号量号量 f1 f7 分别表示程序分别表示程序 progl prog7 是否执行是否执行 完 其初值均为完 其初值均为 0 这 这 8 个进程的同步描述如下 个进程的同步描述如下 int fi 0 表示程序表示程序 progl 是否执行完是否执行完 int f2 0 int f3 0 int f4 O int f5 0 int f6 0 int f7 0 main cobegin progl prog2 prog3 prog4 prog5 prog6 prog7 prog8 coend progl v f1 v f1 v f1 prog2 v f2 v f2 v f2 prog3 p f1 p f2 v f3 prog4 p f1 p f2 v f4 prog5 p f1 p f2 v f5 prog6 p f3 v f6 prog7 p f5 v f7 prog8 p f4 p f6 p f7 十五 十五 北京大学北京大学 1991 年试题年试题 有一个仓库 可以存放有一个仓库 可以存放 A 和和 B 两种产品 但要求 两种产品 但要求 1 每次只能存入一种产品每次只能存入一种产品 A 或或 B p50 2 N A 产品数量一产品数量一 B 产品数量产品数量 M 其中 其中 N 和和 M 是正整数 试用是正整数 试用 P V 操作描述产品操作描述产品 A 与产品与产品 B 韵入库过程 韵入库过程 分析及相关知识分析及相关知识 本题给出的第一个条件是临界资源的访本题给出的第一个条件是临界资源的访 问控制 可用一个互斥信号量解决该问题 第二个条件可问控制 可用一个互斥信号量解决该问题 第二个条件可 以分解为 以分解为 N A 产品数量一产品数量一 B 产品数量产品数量 A 产品数量一产品数量一 B 产品数量产品数量 M 也就是说 也就是说 A 产品的数量不能比产品的数量不能比 B 产品的数量少产品的数量少 N 个以个以 上 上 A 产品的数量不能比产品的数量不能比 B 产品的数量多产品的数量多 M 个以上 个以上 解解 在本题中 我们可以设置两个信号量来控制在本题中 我们可以设置两个信号量来控制 A B 产产 品的存放数量 品的存放数量 sa 表示当前表示当前 允许允许 A 产品比产品比 B 产品多入产品多入 库的数量 即在当前库存量和库的数量 即在当前库存量和 B 产品不入库的情况下 还产品不入库的情况下 还 可以允可以允 许许 sa 个个 A 产品入库产品入库 sb 表示当前允许表示当前允许 B 产品比产品比 A 产品多入库的数量 即在当前库存量和产品多入库的数量 即在当前库存量和 A 产品不入库产品不入库 的情况下 还可以允许的情况下 还可以允许 sb 个个 B 产品入库 初始时 产品入库 初始时 sa 为为 M 一一 1 sb 为为 N 一一 1 当往库中存放入一个当往库中存放入一个 A 产品时 则允许存入产品时 则允许存入 B 产品的数产品的数 量也增加量也增加 1 当往库中存放入一个当往库中存放入一个 B 产品时 则允许存入产品时 则允许存入 A 产品的数量也增加产品的数量也增加 1 产品产品 A B 的入库过程描述如下 的入库过程描述如下 int mutex 1 互斥信号量互斥信号量 int sa M 1 int sb N 1 main while 1 取一个产品取一个产品 if 取的是取的是 A 产品产品 p sa p mutex 将产品入库将产品入库 v mutex v sb else 取的产品是取的产品是 B p sb p mutex 将产品入库将产品入库 v mutex v pa 从本题的解法可以看出 当有比较复杂条件出现时 可从本题的解法可以看出 当有比较复杂条件出现时 可 以把复杂条件分解成一组简单条件 这样就能很容易地写以把复杂条件分解成一组简单条件 这样就能很容易地写 出对应的程序流程了 出对应的程序流程了 十六 十六 南开大学南开大学 1997 年试题年试题 在南开大学和天津大学之间在南开大学和天津大学之间 有一条弯曲的小路 其中从有一条弯曲的小路 其中从 S 到到 T 一段路每次只允许一一段路每次只允许一 辆自行车通过 但其中有一个小的安全岛辆自行车通过 但其中有一个小的安全岛 M 同时允许两同时允许两 辆自行车停留辆自行车停留 可供两辆自行车已从两端进入小路情况 可供两辆自行车已从两端进入小路情况 下错车使用 如图下错车使用 如图 2 14 所示 试设计一个算法使来往所示 试设计一个算法使来往 的自行车均可顺利通过 的自行车均可顺利通过 p53 错错 分析及相关知识分析及相关知识 在本题中 需要控制路段在本题中 需要控制路段 T 到到 L 路段 路段 S 到到 K 及安全岛及安全岛 M 的使用 路段的使用 路段 T 到到 L 及路段及路段 S 到到 K 同同 时只允许一辆自行车通过 而安全岛时只允许一辆自行车通过 而安全岛 M 允许两辆自行车使允许两辆自行车使 用 因此可以用三个信号量来管理它们 另一方面 同一用 因此可以用三个信号量来管理它们 另一方面 同一 方向上的自行车最多只能有一辆通过这段路方向上的自行车最多只能有一辆通过这段路 两个方向上有两个方向上有 两辆两辆 因此还应该用两个信号量来控制 因此还应该用两个信号量来控制 解 在本题中 应设置解 在本题中 应设置 5 个信号量个信号量 ST TS K L M 信号量 信号量 ST 表示是否允许自行表示是否允许自行 车从南开大学去天津大学 其初值为车从南开大学去天津大学 其初值为 1 信号量信号量 TS 表示是否表示是否 允许自行车从天津大学去南开允许自行车从天津大学去南开 大学 其初值为大学 其初值为 1 信号量信号量 K 表示是否允许自行车通过路段表示是否允许自行车通过路段 S 到到 K 其初值为 其初值为 1 信号量信号量 L 表示是否允许自行车通过路表示是否允许自行车通过路 段段 T 到到 L 其初值为 其初值为 1 信号量信号量 M 表示安全岛上还可停放自表示安全岛上还可停放自 行车的数目 其初值为行车的数目 其初值为 2 其控制过程描述如下 其控制过程描述如下 int ST 1 int TS 1 int K 1 int L 1 int M 2 totian 从南开大学去天津大学从南开大学去天津大学 p ST p K 从从 S 走到走到 K p M 进入安全岛进入安全岛 v K p L 从从 L 走到走到 T v M v L v ST tonan 从天津大学去南开大学从天津大学去南开大学 p TS p L 从从 T 走到走到 L p M 进入安全岛进入安全岛 v L p K 从从 K 走到走到 S v M v K v TS 另一题另一题 在南开大学和天津大学之间有一条弯曲的在南开大学和天津大学之间有一条弯曲的 小路 其中从小路 其中从 S 到到 T 一段路每次只允许一辆自行车通过 一段路每次只允许一辆自行车通过 但中间有一个小的但中间有一个小的 安全岛安全岛 M 同时允许两辆自行车停留同时允许两辆自行车停留 可供两辆自行车已从两端进入小路情况下错车使用 如图可供两辆自行车已从两端进入小路情况下错车使用 如图 3 28 所示 试设计一个算法使来往的自行车均可顺利通过 所示 试设计一个算法使来往的自行车均可顺利通过 L3 46 p129 正确正确 解答解答 由于小路中间的安全岛由于小路中间的安全岛 M 仅允许两辆自行车停留 本应仅允许两辆自行车停留 本应 该作为临界资源而设置信号量 该作为临界资源而设置信号量 但仔细分析可以发现 在任何时刻进入小路的自行车最多但仔细分析可以发现 在任何时刻进入小路的自行车最多 不会超过两辆不会超过两辆 南开和天大方向各一辆南开和天大方向各一辆 因此 无需为安全 因此 无需为安全 岛岛 M 设置信号量 在路口设置信号量 在路口 S 处 南开出发的若干自行车应处 南开出发的若干自行车应 进行进入小路权的争夺 以决定谁能够进入小路进行进入小路权的争夺 以决定谁能够进入小路 SK 段 为段 为 此 设置信号量此 设置信号量 S 初值为初值为 1 来控制南来控制南 开路口资源的争夺 同理 设置信号量开路口资源的争夺 同理 设置信号量 T 初值为初值为 1 来控制来控制 天大路口资源的争夺 此外 天大路口资源的争夺 此外 小路小路 SK 段仅允许一辆自行车通过 所以设置信号量段仅允许一辆自行车通过 所以设置信号量 SK 初初 值为值为 1 来进行控制 而对于来进行控制 而对于 LT 段则设置信号量段则设置信号量 LT 初值为初值为 1 进行控制 进行控制 begin S 1 T 1 SK 1 LT 1 cobegin 进程进程 i i 为南开方向的自行车 为南开方向的自行车 i 1 2 begin P S 与其他南开方向的自行车争夺路口与其他南开方向的自行车争夺路口 S 的使用权的使用权 P SK 同对面同对面 天大天大 来的自行车争夺来的自行车争夺 SK 路路 段的使用权段的使用权 通过通过 SK 路段 路段 进入安全岛进入安全岛 M V SK 一旦进入安全岛一旦进入安全岛 M 便可释放路段便可释放路段 SK 的使用权的使用权 P LT 同对面同对面 天大天大 来的自行车争夺来的自行车争夺 LT 路段路段 的使用权的使用权 通过通过 LT 路段 路段 V LT 已通过已通过 LT 路段 释放路段路段 释放路段 LT 的使的使 用权用权 V S 已经通过小路 则允许在路口已经通过小路 则允许在路口 S 等待的自等待的自 行车争夺再次进入行车争夺再次进入 S 的的 使用权使用权 end 进程进程 j j 为天大方向的自行车 为天大方向的自行车 j 1 2 begin P T 与其他天大方向的自行车争夺路口与其他天大方向的自行车争夺路口 T 的使用权的使用权 P LT 同对面同对面 南开南开 来的白行车争夺来的白行车争夺 LT 路路 段的使用权段的使用权 通过通过 LT 路段 路段 进入安全岛进入安全岛 M V LT 旦进入安全岛旦进入安全岛 M 便可释放路段便可释放路段 LT 的使用权的使用权 P SK 同对面同对面 南开南开 来的自行车争夺来的自行车争夺 SK 路段的使用权路段的使用权 通过通过 SK 路段 路段 V SK 已通过已通过 SK 路段 释放路段路段 释放路段 SK 的的 使用权使用权 V T 已经通过小路 则允许在路口已经通过小路 则允许在路口 T 等待等待 的臼行车争夺再次进的臼行车争夺再次进 入入 T 的使用权的使用权 end coend end 注意 如果在进程注意 如果在进程 i 进入安全岛进入安全岛 M 后 在释放路段后 在释放路段 SK 的的 同时释放了路口同时释放了路口 S 而此时进程 而此时进程 i 也进入安全岛 同样在释放路段也进入安全岛 同样在释放路段 LT 的同时释放路口的同时释放路口 T 那么 南开 天大方向将各有一自行车又进入路段那么 南开 天大方向将各有一自行车又进入路段 SK 和和 路段路段 LT 这使得在安全岛 这使得在安全岛 M 中的两辆自行车都无法继续中的两辆自行车都无法继续 前进 而在前进 而在 SK 路段和路段和 LT 路段的路段的 自行车也无法进入安自行车也无法进入安 全岛全岛 M 从而造成死锁 因此 进程 从而造成死锁 因此 进程 i 在进入安全岛在进入安全岛 M 后后 是为对面是为对面 天大天大 来的自行车释放路段来的自行车释放路段 SK 的使用权 而进的使用权 而进 程程 j 在进入安全岛在进入安全岛 M 后也是为对面后也是为对面 南开南开 来的自行车释放来的自行车释放 路段路段 LT 的使用权 的使用权 十七 十七 中国科学院软件研究所中国科学院软件研究所 1995 年试题年试题 多个进程共享多个进程共享 一个文件 其中只读文件的一个文件 其中只读文件的 称为读者 只写文件的称为写者 读者可以同时读 但称为读者 只写文件的称为写者 读者可以同时读 但 写者只能独立写 请 写者只能独立写 请 说明进程间的相互制约关系 应设置哪些信号量说明进程间的相互制约关系 应设置哪些信号量 用用 P V 操作写出其同步算法 操作写出其同步算法 修改上述的同步算法 使得它对写者优先 即一旦有修改上述的同步算法 使得它对写者优先 即一旦有 写者到达 后续的读者必须等写者到达 后续的读者必须等 待 而无论是否有读者在待 而无论是否有读者在 读文件 读文件 解 本题前两问是经典读者写者问题 第三问对读者写解 本题前两问是经典读者写者问题 第三问对读者写 者问题加了一些限制 即使算者问题加了一些限制 即使算 法对写者优先 法对写者优先 进程间的相互制约关系有三类 一是读者之间允许同进程间的相互制约关系有三类 一是读者之间允许同 时读时读 二是读者与写者之间须二是读者与写者之间须 互斥互斥 三是写者之间须互斥 三是写者之间须互斥 为了解决读者 写者之间的同步 应设置两个信号量和为了解决读者 写者之间的同步 应设置两个信号量和 一个共享变量一个共享变量 读互斥信号量读互斥信号量 rmutex 用于使读者互斥地 用于使读者互斥地 访问共享变量访问共享变量 count 其初值为 其初值为 1 写互斥信号量写互斥信号量 wmutex 用于实现写者与读者的互斥及写者与写者的互斥 其初值用于实现写者与读者的互斥及写者与写者的互斥 其初值 为为 1 共享变量共享变量 count 用于记录当前正在读文件的读者数目 用于记录当前正在读文件的读者数目 初值为初值为 0 进程间的控制算法如下所示 进程间的控制算法如下所示 int rmutex l int wmutcx l int count 0 main cobegin reader writer coend reader while 1 p rmutex if count 0 p wmutex 当第一个读者读文件当第一个读者读文件 时 阻止写者写时 阻止写者写 count v rmutex 读文件读文件 p rmutex count if coun v wmutex 当最后一个读者读完文当最后一个读者读完文 件时 允许写者写件时 允许写者写 v rmutex writer while 1 p wmutex 写文件写文件 v wmutex 为了提高写者的优先级 增加一个信号量为了提高写者的优先级 增加一个信号量 s 用于在 用于在 写进程到达后封锁后续的读者 写进程到达后封锁后续的读者 其控制流程如下 其控制流程如下 int rmutex 1 int wmutex l int count 0 int s 1 main cobegin reader writer coend reader while 1 p s p rmutex if coun 0 p wmutex 当第一个读者读文件当第一个读者读文件 时 阻止写者写时 阻止写者写 count v rmutex v s 读文件读文件 p rmutex count if count 0 v wmutex 当最后一个读者读完当最后一个读者读完 文件时 允许写者写文件时 允许写者写 v rmutex writer while 1 p s p wmutex 写文件写文件 v wmutex v S 十八 既考虑作业等待时间 又考虑作业执行时间的调度十八 既考虑作业等待时间 又考虑作业执行时间的调度 算法是 算法是 A 响应比高者优先响应比高者优先 B 短作业优先 短作业优先 p91 C 优先级调度 优先级调度 D 先来先服务 先来先服务 答 答 A 十九 是指从作业提交给系统到作业完成的十九 是指从作业提交给系统到作业完成的 时间间隔 时间间隔 p91 A 周转时间 周转时间 B 响应时间 响应时间 C 等待时间等待时间 D 运行时间 运行时间 答 答 A 二十 作业从进入后备队列到被调度程序选中的时间间隔二十 作业从进入后备队列到被调度程序选中的时间间隔 称为 称为 p91 A 周转时间 周转时间 B 响应时间 响应时间 C 等待时间等待时间 D 触发时间 触发时间 答 答 C 二十一 假设下述四个作业同时到达 当使用最高优先数二十一 假设下述四个作业同时到达 当使用最高优先数 优先调度算法时 作业的平均周转时间为 小时 优先调度算法时 作业的平均周转时间为 小时 P91 作业作业 所需运行时间所需运行时间 优先数优先数 1 2 4 2 5 9 3 8 1 4 3 8 A 4 5 B 10 5 C 4 75 D 10 25 答 答 D 二十二 系统在 发生从目态到管态的转换 二十二 系统在 发生从目态到管态的转换 P92 A 发出发出 P 操作时操作时 B 发出 发出 V 操作时操作时 C 执行系统调用时 执行系统调用时 D 执行置程序状态字时执行置程序状态字时 答 答 C 二十三 操作系统为用户提供两个接口 一个是二十三 操作系统为用户提供两个接口 一个是 用户利用它来组织和控制作业的执行或管理 用户利用它来组织和控制作业的执行或管理 计算机系统 另一个是 计算机系统 另一个是 编程人员使用它们来 编程人员使用它们来 请求操作系统提供服务 请求操作系统提供服务 p92 答 答 命令接口命令接口 程序接口程序接口 二十四 设有一组作业 它们的提交时间及运行时间如下 二十四 设有一组作业 它们的提交时间及运行时间如下 p93 作业号作业号 提交时间提交时间 运行时间运行时间 分钟分钟 1 9 00 70 2 9 40 30 3 9 50 10 4 10 10 5 在单道方式下 采用短作业优先调度算法 作业的执行在单道方式下 采用短作业优先调度算法 作业的执行 顺序是 顺序是 答 答 1 4 3 2 二十五 设有二十五 设有 4 道作业 它们的提交时间及执行时间如下 道作业 它们的提交时间及执行时间如下 p93 作业号作业号 提交时间提交时间 执行时间执行时间 1 10 0 2 0 2 10 2 1 0 3 10 4 0 5 4 10 5 0 3 试计算在单道程序环境下 采用先来先服务调度算法和试计算在单道程序环境下 采用先来先服务调度算法和 最短作业优先调度算法时的平均周转时间和平均带权周转最短作业优先调度算法时的平均周转时间和平均带权周转 时间 并指出它们的调度顺序 时间 并指出它们的调度顺序 时间单位 小时 以十进时间单位 小时 以十进 制进行计算 制进行计算 解 若采用先来先服务调度算法 则其调度顺序为解 若采用先来先服务调度算法 则其调度顺序为 1 2 3 4 作业号作业号 提交时间提交时间 执行时间执行时间 开始时间开始时间 完成时间完成时间 周转时周转时 间间 带权周转时间带权周转时间 1 10 0 2 0 10 0 12 0 2 0 1 0 2 10 2 1 0 12 0 13 0 2 8 2 8 3 10 4 0 5 13 0 13 5 3 1 6 2 4 10 5 0 3 13 5 13 8 3 3 11 0 平均周转时间平均周转时间 T 2 0 2 8 3 1 3 3 4 2 8 平均带权周转时间平均带权周转时间 W 1 2 8 6 2 11 4 5 25 若采用短作业优先调度算法 则其调度顺序为若采用短作业优先调度算法 则其调度顺序为 1 4 3 2 作业号作业号 提交时间提交时间 执行时间执行时间 开始时间开始时间 完成时间完成时间 周转周转 时间时间 带权周转时间带权周转时间 1 10 0 2 0 10 0 12 0 2 0 1 0 4 10 5 0 3 12 0 12 3 1 8 6 0 3 10 4 0 5 12 3 12 8 2 4 4 8 2 10 2 1 0 12 8 13 8 3 6 3 6 平均周转时间平均周转时间 T 2 0 1 8 2 4 3 6 4 2 45 平均带权周转时间平均带权周转时间 W 1 6 4 8 3 6 4 3