操作系统作业答案

习题一习题一 1 举例说明为什么对并发执行的程序不加控制会产生与执行时间有关的错误 举例说明为什么对并发执行的程序不加控制会产生与执行时间有关的错误 解 程序在并发执行时由于资源是共享的 而且常常资源数少于程序对这些资源的需求数 致使这些并发执行的 程序之间因为竞争资源导致存在间接制约关系 这种间接制约使得并发执行的程序具有随机性 异步性 即 执 行 暂停 执行 它们何时启动 何时停止是未知的 例如 飞机售票系统 堆栈的存数与取数过程等 示例说 明略 2 程序并发执行为什么会失去顺序执行时的封闭性和可再现性 程序并发执行为什么会失去顺序执行时的封闭性和可再现性 解 所谓 封闭性 是指程序执行得到的最终结果由给定的初始条件决定 不受外界因素的影响 在程序并发执行时 由于资源共享 导致这些资源的状态将由多个程序来改变 又由于存在程序执行的随机性 所以程序的运行失去 封闭性 由于失去了封闭性 也将导致其失去可再现性 即虽然它们执行时的环境和初始条件相同 但得到的结 果却可能各不相同 习题二习题二 1 试用加锁的方法解决飞机售票系统的问题 试用加锁的方法解决飞机售票系统的问题 例 民航售票系统 例 民航售票系统 n 个售票处个售票处 2 用机器指令 用机器指令 testAndset 解决飞机售票系统中任一进程的算法 解决飞机售票系统中任一进程的算法 习题三习题三 1 进程在做 进程在做 P V 操作时对自己和其他进程有何影响 操作时对自己和其他进程有何影响 进程在信号量上执行 P 操作后 若信号量的值为正 当前进程继续执行 若信号量的值为负 当前进程变为等待 状态 放弃处理机 其它进程则有机会获得 CPU 进程在信号量上执行 V 操作后 不会对自己有任何影响 但当信号量的值不大于 0 时 需要唤醒在该信号量 上所对应的等待队列中的进程 2 设课程的前驱 后继关系如下 若每修一门课程看作进程 设课程的前驱 后继关系如下 若每修一门课程看作进程 Px x 1 6 试用 试用 P V 操作算法描述这种前驱与后操作算法描述这种前驱与后 继关系 继关系 答 Semaphore S1 S2 S3 S4 S5 S6 0 Begin Cobegin P1 P2 P3 P4 P5 P6 coend end P1 P2 P3 Begin begin begin 修计算机导论 P S1 P S2 V S1 修高级语言程序设计 修计算机组成原理 V S2 V S3 V S4 End End End P4 P5 P6 Begin begin begin P S3 P S4 P S5 修数据结构 修 86 汇编语言 P S6 V S5 V S6 修操作系统 End End End 习题四习题四 1 有三个进程 有三个进程 R W1 W2 进程 进程 R 从输入设备上读数据送缓冲区从输入设备上读数据送缓冲区 B 若是奇数由 若是奇数由 W1 进程从进程从 B 取数输出 取数输出 若是偶数则由若是偶数则由 W2 进程从进程从 B 取数输出 设缓冲区取数输出 设缓冲区 B 只有一个单元 试用信号量机制设计实现算法 只有一个单元 试用信号量机制设计实现算法 1 se sf1 sf2 semaphore se 1 sf1 sf2 0 R W1 W2 并发执行 Process R process W1 process W2 repeat repeat repeat 读数 P sf1 P sf2 P se 从 B 中取数 从 B 中取数 送数到 B V se V se if B mod 2 0 then until false until false V sf1 else V sf2 until false 2 设有一台计算机 挂有一台输入机和一台打印机 现在从输入机上把数据输入到缓冲区 设有一台计算机 挂有一台输入机和一台打印机 现在从输入机上把数据输入到缓冲区 B 中 处理程序处理中 处理程序处理 后再把结果送到缓冲区后再把结果送到缓冲区 B 中 中 设 设 B 只能放只能放 1 个数据 然后在打印机上输出 问个数据 然后在打印机上输出 问 1 系统可设哪些进程来完成这一任务 系统可设哪些进程来完成这一任务 2 这些进程之间有什么样的制约关系 这些进程之间有什么样的制约关系 3 用 用 PV 操作写出这些进程的同步算法操作写出这些进程的同步算法 答 1 输入进程 处理进程 输出进程 2 处理进程不能在输入进程之前执行 输出进程不能在处理进程之前执行 输入进程在未得到处理进程 输出进程 的消息前不能运行 3 输入 处理 输出 进程并发执行 Semaphore s1 s2 s3 S1 1 S2 S3 0 process 输入 process 处理 process 输出 L1 读数 L2 P S2 L3 P S3 P S1 从 B 取数处理后再送 B 从 B 取数输出 送数到 B V S3 V S1 V S2 Goto L2 Goto L3 Goto L1 习题五习题五 1 设系统中有 设系统中有 M 个资源 个资源 N 个进程 每个进程都要求个进程 每个进程都要求 K 个资源 若个资源 若 M 5 N 5 K 2 问 问 1 如何分配会导致死锁 如何分配会导致死锁 2 要不死锁应该如何分配 要不死锁应该如何分配 如果对每个进程平均分配 1 个资源 则系统中的可用资源为 0 而每个进程都还需要 1 个资源 才能向前 推进 因此 系统发生死锁 只要保证有 1 个进程能获得 2 个资源 则它在有限的时间内就可以运行完成并释放资源 这样系统就不会 死锁 例如 先给 4 个进程各分配 1 个资源 让它们先运行 通过安全性算法测试可以知道第 5 个进程的 资源申请将被拒绝 再把最后 1 个资源分配给这 4 个进程中的 1 个即可 2 假设甲 乙 丙三个并发进程间的 假设甲 乙 丙三个并发进程间的 PV 操作同步算法如下所示操作同步算法如下所示 信号量信号量 S1 S2 S3 的初值都为的初值都为 1 问这些算法在 问这些算法在 什么情况下发生死锁什么情况下发生死锁 如何防止死锁 如何防止死锁 甲 乙 丙 L1 P S1 L2 P S2 L3 P S3 P S2 P S3 P S1 V S2 V S3 V S1 V S1 V S2 V S3 goto L1 goto L2 goto L3 答 甲 P S1 后暂停 乙 P S2 后暂停 丙 P S3 后暂停 采用按序分配 丙改为 P S1 P S3 也可以改甲或乙进程的 P V 操作次序 以限制进程的并发执行 习题六习题六 1 设有设有 5 个哲学家 共享一张放有五把椅子的桌子 每人分得一把椅子 但是 桌子上总共只有个哲学家 共享一张放有五把椅子的桌子 每人分得一把椅子 但是 桌子上总共只有 5 支筷子 在每人支筷子 在每人 两边分开各放一支 哲学家们在肚子饥饿时才试图分两次从两边拾起筷子就餐 两边分开各放一支 哲学家们在肚子饥饿时才试图分两次从两边拾起筷子就餐 条件 条件 1 只有拿到两支筷子时 哲学家才能吃饭 只有拿到两支筷子时 哲学家才能吃饭 2 如果筷子已在他人手上 则该哲学家必须等待到他人吃完之后才能拿到筷子 如果筷子已在他人手上 则该哲学家必须等待到他人吃完之后才能拿到筷子 3 任一哲学家在自己未拿到两支筷子吃饭之前 决不放下自己手中的筷子 任一哲学家在自己未拿到两支筷子吃饭之前 决不放下自己手中的筷子 试试 1 描述一个保证不会出现两个邻座同时要求吃饭的通信算法 描述一个保证不会出现两个邻座同时要求吃饭的通信算法 2 描述一个既没有两邻座同时吃饭 又没有人饿死 永远拿不到筷子 的算法 描述一个既没有两邻座同时吃饭 又没有人饿死 永远拿不到筷子 的算法 3 在什么情况下 在什么情况下 5 个哲学家全部吃不上饭 个哲学家全部吃不上饭 答 使用非对称解决 即奇数号的哲学家先拿起他左边的筷子 接着拿起他右边的筷子 而偶数号的哲学家先拿 起他右边的筷子 接着再拿他左边的筷子 1 设信号量 c 0 c 4 初始值均为 1 分别表示 i 号筷子被拿 i 0 1 2 3 4 send i 第 i 个哲学家要吃饭 begin think P c i P c i 1 mod 5 eat V c i 1 mod 5 V c i End 该过程能保证两邻座不同时吃饭 但会出现 5 个哲学家一人拿一只筷子 谁也吃不上饭的死锁情况 2 解决的思路 让奇数号的哲学家先取右手边的筷子 让偶数号的哲学家先取左手边的筷子 这样 任何一个哲学家 拿到一只筷子之后 就已经阻止了他邻座的一个哲学家吃饭的企图 除非某个哲学家一直吃下去 否则不会有人会饿死 send i 第 i 个哲学家要吃饭 Begin think If i mod 2 0 then P c i P c i 1 mod 5 eat V c i c i 1 mod 5 else P c i 1 mod 5 P c i Eat V c i 1 mod 5 V c i End 3 非对称解决 并发主程序略 Program diningphilosophers Var chopstick array 0 4 of semaphore 1 i integer Procedure philosopher i integer Begin Repeat Think If i mod 2 0 then Begin P chopstick i P chopstick i 1 mod 5 吃面 V chopstick i 1 mod 5 V chopstick i End Else Begin P chopstick i 1 mod 5 P chopstick i 吃面 V chopstick i 1 mod 5 V chopstick i End Forever End 习题七习题七 1 某程序在虚拟 逻辑 地址 某程序在虚拟 逻辑 地址 100 处有一条取数指令处有一条取数指令 LOAD 1 500 而而 500 单元存放数据单元存放数据 51888 若程序分配到的 若程序分配到的 内存地址为内存地址为 5000 试画出下列方式下的该指令及数据的物理地址和变换过程 试画出下列方式下的该指令及数据的物理地址和变换过程 1 静态重定位 静态重定位 2 动态重定位 动态重定位 2 若一个虚拟地址空间占 若一个虚拟地址空间占 8 页 每个页大小为页 每个页大小为 1024 需要映射到 需要映射到 32 个内存块上 试问 个内存块上 试问 1 虚拟地址要用多少位表示 虚拟地址要用多少位表示 2 物理地址要用多少位表示 物理地址要用多少位表示 答 1 逻辑地址需要的位数 8 1024 23 210 213 所以需要 13 位 2 物理地址需要的位数 32 1024 25 210 215 所以需要 15 位 习题八习题八 1 在页式存储管理系统中某个时刻某个进程的页表如下 设地址结构为 在页式存储管理系统中某个时刻某个进程的页表如下 设地址结构为 32 位 页号占据位 页号占据 22 位 试把逻辑地址位 试把逻辑地址 0A5CH 转换成物理地址 以十六进制表示 转换成物理地址 以十六进制表示 2 在静态页式下 内存总量为 在静态页式下 内存总量为 65536 字节 每个存储块为字节 每个存储块为 4KB 一程序代码段长 一程序代码段长 32768 字节字节 数据段长数据段长 16386 字节 字节 堆栈段长堆栈段长 15870 字节 规定不允许一个块内包含两个段的内容 请问能为该程序分配空间吗 如果块长为字节 规定不允许一个块内包含两个段的内容 请问能为该程序分配空间吗 如果块长为 512 字字 节呢 节呢 答 答 习题九习题九 1 在某页式虚拟存储系统中 页面大小为在某页式虚拟存储系统中 页面大小为 100 个单元 某作业占有内存块数个单元 某作业占有内存块数 m 2 若它的访问虚存逻辑地址序列 若它的访问虚存逻辑地址序列 为 为 55 135 96 227 42 156 330 169 11 252 253 假设各个内存块初始为空 试问 假设各个内存块初始为空 试问 1 按 按 OPT 置换算法画图表示页面置换过程并求缺页中断率置换算法画图表示页面置换过程并求缺页中断率 f 2 按 按 FIFO 置换算法画图表示页面置换过程并求缺页中断率置换算法画图表示页面置换过程并求缺页中断率 f 3 按 按