计算机操作系统教程--核心与设计原理习题5答案.pdf

习题 5 答案 习题习题 5 5 1 何谓与时间有关的错误 举例说明之 答 并发进程的执行实际上是进程活动的某种交叉 某些交叉次序可能得到错误结 果 由于具体交叉的形成与进程的推进速度有关 而速度是时间的函数 因而将这种错 误称为与时间有关的错误 例子略 5 2 什么是临界资源 什么是临界区 答 一次仅允许一个进程使用的资源称为临界资源 在每个进程中 访问临界资源 的那段程序称为临界区 5 3 试分析临界区的大小与系统并发性之间的关系 答 关于同一组变量的临界区是不能并发执行的代码 临界区越大 并发性越差 因而编写并发程序应尽量缩小临界区域范围 5 4 为何开关中断进程互斥方法仅在单 CPU 系统中是有效的 答 关中断方法不适用于多 CPU 系统 因为关中断只能保证 CPU 不由一个进程切换 到另外一个进程 从而防止多个进程并发地进入公共临界区域 但即使关中断后 不同 进程仍可以在不同 CPU 上并行执行关于同一组共享变量的临界区代码 5 5 进程的互斥和同步有什么异同点 答 进程的同步和互斥是指进程在推进时的相互制约关系 进程同步源于进程合作 是进程间共同完成一项任务是直接发生相互作用的关系 是进程之间的直接制约关系 进程互斥源于对临界资源的竞争 是进程之间的间接制约 关系 5 6 试说明进程互斥 同步和通信三者之间的关系 答 进程的同步和互斥是指进程在推进时的相互制约关系 已经在上题中给出了详 细的解答 由于进程间存在制约关系 为了保证进程的正确运行以及相互合作进程间的信息交 换 就需要进程之间进行通信 进程通信是指进程间的信息交换 分为高级通信和低级 通信 高级通信以较高的效率传送大批数据 进程之间的互斥与同步也是一种通信 由 于交换的信息量很小 因此这种进程通信称为低级进程通信 5 7 同步机构应遵循哪些基本准则 答 a 空闲让进 b 忙则等待 c 有限等待 d 让权等待 5 8 试从物理概念上说明信号量 P V 操作的含义 答 P S 表示申请一个资源 S value 0 表示有资源可用 其值为资源的数目 S value 0 表示无资源可用 S value 0 则 S value 表示 S 等待队列中的进程个数 V S 表示释放一个资源 信号量的初值应该大于等于 0 5 9 由 V 操作唤醒的进程是否一定能够直接进入运行状态 举例说明之 答 否 一般来说 唤醒是将进程状态由等待状态变成就绪状态 而就绪进程何时 获得处理机则是由系统的处理机调度策略确定的 如果采用抢占式优先级调度算法 并 且被唤醒的进程是当前系统中优先级最高的进程 那么该进程将被调度执行 其状态变 成运行态 如果该进程不是系统中优先级最高的进程或系统采用其它调度算法 那么该 进程不会被调度执行 其状态将维持在就绪态 5 10 我们为某临界区设置一把锁 W 当 W 1 时 表示关锁 W 0 时 表示锁打开 试写 出开锁原语和关锁原语 并利用它们去实现互斥 答 开锁原语 void unlock W W 0 关锁原语 void lock W while W 1 W 1 利用开关锁原语实现互斥 semaphore W 0 main cobegin Pn 并发的进程 P1 P2 Pn lock W 临界区 unlock W 其余部分 coend 5 11 试写出相应的程序来描述图 5 8 所示的前趋图 答 a 设 6 个同步信号量f1 f2 f3 f4 f5 f6 分别表示进程S1 S2 S3 S4 S5 S6是 否执行完成 其初值均为 0 这 7 个进程的同步描述如下 主程序如下 semaphore fl f2 f3 f4 f5 f6 0 main cobegin S1 S2 S3 S5 S3 S6 S7 S2 S4 S1 S1 S3 S2 S4S5S6S7 S8 a b 图 5 8 前趋图 S4 S5 S6 S7 coend 语句形式如下 d S2 1 void S3 1 各个进程的 void S1 voi V f1 V f1 P f V f2 V f2 P f V f3 v 4 2 voi 2 v 6 3 void S7 4 oid S P f V f4 d S5 P f V f5 oid S P f V f6 P f P f5 P f6 另一种做法 f2 f3 f4 f5 f6 f7 f8 分别表示进程S2 S3 S4 S5 S6 S7 主 如下 2 2 void S3 3 void S4 4 b 设 7 个同步信号量 S8是否可以开始执行 其初值均为 0 semaphore f2 f3 f4 f5 f6 f7 f8 0 程序 略 类似 a 这 8 个进程的语句形式 void S1 void S V f2 V f3 P f V f4 V f5 P f V f6 V f7 P f V f8 void S5 5 void S6 6 v 7 7 void S8 8 P f V f8 P f V f8 oid S P f V f8 P f P f8 P f8 P f8 12 在生产者一消费者问题中 如果缺少了 V full 或 V empty 对执行结果会有 可以不断地往缓冲池送消息 如果缓冲池满 会覆盖原有数据 造成数 据混 5 何影响 答 生产者 乱 而消费者始终因 P full 操作将消费进程直接送入进程链表进行等待 无法访 问缓冲池 造成无限等待 5 13 在生产者一消费者问题中 如果将两个 P 操作即 P full 和 P mutex 互换位置 样的 5 14什么要引入条件变量 种 为了区别它们 引 入了 为两个信号灯变量 下列八组 P V 操作哪些可以同时进行 哪些不能 P S1 P S2 2 P S1 V S2 答 能同时进行的及不同信号量 属于关 于不 用信号灯与 PV 操作给出解法 冲区 next product t to buffer in in 消费者活动 t from buffer out out 17 试用信号灯与 PV 操作实现司机与售票员之间的同步问题 设公共汽车上有一个司 售票员的活动 P2 或者是将 V full 和 V mutex 互换位置 结果会如何 答 a 容易造成死锁 b 从逻辑上来说应该是一 画图说明管程由哪几部分组成 为 答 图略 因为调用 wait 原语后 使进程等待的原因有多 条件变量 5 15 设 S1 和 S2 同时进行 为什么 1 3 V S1 P S2 4 V S1 V S2 5 P S1 P S1 6 P S2 V S2 7 V S1 P S1 8 V S2 V S2 包括 1 2 3 4 这些操作涉 同组共享变量的临界区 不能同时进行的包括 5 6 7 8 这些操作涉 及相同的信号量 属于关于同一组共享变量的临界区 5 16 对于生产者 消费者问题 假设缓冲区是无界的 试 答 由于是无界缓冲区 所以生产者不会因得不到缓冲区而被阻塞 不需要对空缓 进行管理 可以去掉在有界缓冲区中用来管理空缓冲区的信号量及其 PV 操作 Semaphore mutex in 1 Semaphore mutex out 1 Semaphore empty 0 int in 0 out 0 生产者活动 while 1 produce P mutex in Add the produc in V mutex V empty while 1 P empty P mutex out Take the produc out V mutex 5 机和一个售票员 其活动如下图所示 司机的活动 P1 While 1 启动车辆 正常行车 到站停车 While 1 关车门 售票 开车门 为了安全起见 显然要求 1 关车门后方能启动车辆 2 到站停车后方能开车门 答 量 open 表示是否允许售票员开车门 初始状态是车停在始发站 车门开着 等待乘客 上车 票员的活动 P2 while 1 5 18 考虑一只有一个理发师 只顾客等待理发的椅子 如果没 有顾客 则理发师睡觉 如果有一顾客进入理发店发现理发师在睡觉 则把他叫醒 Cust觉时顾客进来需要唤醒理发师为 其理客之间 客数 并用作阻塞理发师进程 初值为 0 顾客进程 初值为 0 客数 为顾客准备的椅子数 tex 1 E 理完一人 还有顾客吗 cutomers 若无顾客 理发师睡眠 个顾客理发 进程互斥 f waiting chairs 定义两个信号量 一个信号量 start 表示是否允许司机启动车辆 另一个信号 因此 两个信号量的初值都是 0 semaphore start 0 semaphore open 0 司机的活动 P1 while 1 P start 启动车辆 正常行车 到站停车 V open 售 关车门 V start 售票 P open 开车门 个理发店 有 N 张可供 试用信号量设计一个协调理发师和顾客的程序 答 题目中要求描述理发师和顾客的行为 因此需要两类进程 Barber 和 omer 分别描述理发师和顾客的行为 当理发师睡 发 当有顾客时理发师为其理发 没有的时候理发师睡觉 因此理发师和顾 是同步的关系 由于每次理发师只能为一个人理发 且可供等侯的椅子有限只有 n 个 即理发师和椅子是临界资源 所以顾客之间是互斥的关系 引入 3 个信号量和一个控制变量 1 控制变量 waiting 记录等候理发的顾客数 初值均为 0 2 信号量 customers 记录等候理发的顾 3 信号量 barbers 记录正在等候顾客的理发师数 并用作阻塞 4 信号量 mutex 用于互斥 初值为 1 PV 操作代码如下 int waiting 0 等候理发的顾 int chairs n semaphore customers 0 barbers 0 mu barber while TRU P P mutex 进程互斥 waiting waiting 1 等候顾客数少一个 V barbers 理发师去为一 V mutex 开放临界区 cut hair 正在理发 customer P mutex i waiting waiting 1 等候顾客数加 1 必要的话唤醒理发师 神 理发 mutex 人满了 走吧 点 适用于哪些场合 进程通信根据交换信息量的多少分为高级通信和低级通信 低级通信一般只传 信 则要 己的地址空间中 不需要时则把它取消 其效率低 通信对用户不透 则可弥补这些缺陷 用户可直 接利 sume 两个信箱的 了数据时 它将数据作为消 息发 信箱 mayproduce lbox mayconsume V customers V mutex 开放临界区 P barbers 无理发师 顾客坐着养 get haircut 一个顾客坐下 else V 5 19 进程之间有哪些基本的通信方式 它们分别有什么特 答 送一个或几个字节的信息 以达到控制进程执行速度的作用 如 PV 操作 高级通 传送大量数据 目的不是为了控制进程的执行速度 而是为了交换信息 高级进程通信方式有很多种 大致可归并为三类 共享存储器 管道文件和消息传 递 共享存储器 在内存种分配一片空间作为共享存储区 需要进行通信的进程把它附 加到自 管道文件 它是连接两个命令的一个打开文件 一个命令向该文件中写入数据 为 写者 另一个命令从该文件中读出数据 为读者 消息传递 它以消息为单位在进程间进行数据交换 5 20 试比较进程间的低级通信工具与高级通信工具 答 用户用低级通信工具实现进程通信很不方便 因为 明 所有的操作都必须由程序员来实现 而高级通信工具 用操作系统所提供的一组通信命令 高效地传送大量的数据 5 21 试用信箱通信方式解决生产者 消费者问题 答 在本题解决方案中 使用了两个信箱 mayproduce 和 maycon 大小均为 N 即其中最多可以存放 N 条消息 当生产者生产 送到信箱 mayconsume 只要该信箱中有一条消息 消费者就可以开始消费 信箱 mayproduce 最初填满了空消息 空消息的条数等于信箱的容量与 mayconsume 信箱中消 息条数之差 其作用类似于用信号量机制解决生产者一消费者问题中的 empty 当生产 者向消费者发送一条消息时 mayproduce 信箱中的消息条数减少 mayconsume 信箱中 的消息条数增加 当消费者接收一条消息时 mayconsume 信箱中的消息条数减少 而 mayproduce 信箱中的消息条数增加 系统中的消息总条数保持不变 const int capacity N N 为信箱容量 null 这里 为空消息 int i main 主程序 create mailbox mayproduce 创建 create mai for i 1 i capacity i send mayproduce null cobegin producer consumer co pr 生产者进程 息类型 ayproduce pmsg 等待空消息 msg produce 生产一条消息 coner 消费者进程 ile true yconsume cmsg onsume cmsg 取出一条消息供消费 5 22消息传递通信方式下 发送进程和接收进程在通信过程中可以采用哪3种同步方式 接收进程 将接收到的数据存入 S 为例 说明 当接可能各是 多少 M 10 MTOQ 接收进 eSfromP 答 1 发送进程阻塞 接收进程阻塞 送进程不阻塞 接收进程阻塞 2 在Q 都必须等到对方执行完标号为 L1 的语 句后才可以 X 只能为 11 来得及向 Q 发出 第 2 end oducer message pmsg message