操作系统习题课PPT课件

《操作系统习题课PPT课件》由会员分享，可在线阅读，更多相关《操作系统习题课PPT课件（35页珍藏版）》请在金锄头文库上搜索。

1、 操作系统原理习题课 作业存在的问题习题讲解 作业存在的问题 部分同学的作业明显是应付 抄袭别人作业前2次作业基本没有大的问题第3 4次作业 CPU调度 进程同步 问题比较多 第3次作业中练习一90 的同学都做错了 CPU调度习题 一个具有两道作业的批处理系统 作业调度采用短作业优先的调度算法 进程调度采用以优先数为基础的抢占式调度算法 如下表的作业序列 表中所有作业优先数即为进程优先数 数值越小优先级越高 要求 1 列出所有作业进入内存时间及结束时间 2 计算平均周转时间作业名到达时间估计运算时间优先数A10 0040分5B10 2030分3C10 3050分4D10 5020分6 10 0

2、0A作业到达 作业A调入内存 进程调度程序调度A运行10 20B作业到达 作业B调入内存 抢占进程A的处理机 A回到就绪队列 A还需运行20分钟10 30C作业到达 在后备队列中等待10 50B运行30分钟后结束运行 D作业到达 后备队列中有C D两个作业等待调度 根据短作业优先原则 D调入内存 内存中 A在就绪队列上已等待了30分钟 A的优先级高于D A运行 D就绪 此时C在后备队列中已等待了20分钟并继续等待 11 10A运行结束 C装入内存 C的优先权高于D C运行 D继续等待 此时D已等待了20分钟 12 00C运行结束 D运行12 20D运行结束 作业名进入内存时间结束时间A10 0

3、011 10B10 2010 50C11 1012 00D10 5012 20各作业的周转时间为 A 70B 30C 90D 90平均周转时间为 70 30 90 90 4 70 一个四道作业的操作系统中 设在一段时间内先后到达6个作业 它们的提交时间和运行时间见下表 作业号提交时间运行时间 JOB1JOB2JOB3JOB4JOB5JOB6 8 008 208 258 308 358 40 60352025510 系统采用SJF算法 作业被调度进入运行后不再退出 但当一作业进入运行时 可以调整运行的优先次序 1分别给出上述6个作业的执行时间次序2计算作业的平均周转时间 CPU调度习题 解析 四

4、道的系统 作业调度最多可选择四道作业进入内存 以进程的形式运行 进程调度采用可抢占的短作业优先调度原则 8 00J1到达 无竞争者 进入内存 8 20J1运行20分钟 剩余40分钟 J2到达 运行时间为35分钟 小于J1 取代J1运行 8 25J1剩余40分钟 J2剩余30分钟 J3到达 运行时间为20分钟 取代J2运行 8 30J1剩余40分钟 J2剩余30分钟 J3剩余15分钟 J4到达 运行时间为25分钟 J3继续运行 8 35J3剩余10分钟 J5到达 运行时间为5分钟 尽管最短 但内存已经有四道作业 因此 J5不可进入内存 J3继续运行 08 40J3剩余5分钟 J6到达 同理不可以

5、进入内存 J3继续运行 08 45J3运行结束 离开主存 J5最短 进入内存 08 50J5结束 离开 J6进入 运行时间为10分钟 为最短 开始运行 09 00J6结束 离开 J1剩余40分钟 J2剩余30分钟 J4剩余25分钟 J4最短 开始运行 09 25J4结束 离开 J2最短 开始运行 09 55J2结束 J1运行 10 35J1结束 每道作业的周转时间 结束时间 提交时间J1 8 00 10 35周转时间155分钟J2 8 20 09 55周转时间95分钟J3 8 25 08 45周转时间20分钟J4 8 30 09 25周转时间55分钟J5 8 35 08 50周转时间15分钟J

6、6 8 40 09 00周转时间20分钟平均周转时间 360 6 60分钟 进程同步练习题 并发进程之间有哪几种制约关系 同步与互斥有何区别 答 进程之间的制约关系有两种 间接制约和直接制约 间接制约是由于共享系统资源而导致的制约关系 两个进程之间的同步需要另外的系统进程协调 直接制约是指两个进程在逻辑上有某种关系 两个进程之间的同步通过使用信号量等机制相互制约 而无需通过操作系统的其他进程来协调 例如 两个进程要同时使用同一个打印机 需要通过操作系统的专门进程来协调 这是间接制约 又如 两个进程同时要访问一个共享变量 可以通过使用信号量的方式解决 这是直接制约 续上页 所谓进程同步是指进程之

7、间存在的一种时序上的等待关系 所谓进程互斥是指进程之间存在的 种竞争关系 例如 进程A等待进程B发送给它的消息 这是A与B同步 它们之间没有竞争关系 只有一种时序上的等待关系 又如 进程A要修改共享变量X 进程B此时也要对x进行修改 为了保证x的结果正确 则A和B需要互斥访问x 所以 A和B此时存在一种对x的竞争关系 有一阅览室 共有100个座位 读者进入时必须先在一张登记表上登记 该表为每一座位列一表目 包括座号和读者姓名 读者离开时要消掉登记内容 试用P v操作描述读者进程的同步结构 解析 定义信号量以及相应变量mutex semaphore 互斥信号量full semaphore 同步信

8、号量table array0 n 1ofitem Procedurereader beginP full P mutex Register name table V mutex Reading P mutex Delet name table V mutex V full end beginSeminitsal mutex 1 full 100 CobeginReader Reader coendend 有一个理发店 有几张椅子和一个理发师 当没有顾客时 理发师睡觉 当有顾客到来时 若发现理发师在睡觉 则唤醒理发师为其理发 如果顾客到来时 理发师正忙着理发 则顾客坐在椅子上等待 如果已没有空闲

9、椅子 则顾客离开 用P V操作描述理发师和顾客之间的制约关系 varmutex customers barbers semaphore waiting chairs integer procedurebarber beginwhile true beginp customers p mutex waiting waiting 1 v mutex cuthair v barbers endend procedurecustomer beginp mutex if waiting chairs thenbeginwaiting waiting 1 v customers v mutex p bar

10、bers get haircut endelsebeginv mutex endend beginseminitial mutex 1 barbers 0 customers 0 waiting 0 chairs 10 cobeginbarber customer customer coendend 把学生和监考老师都看作进程 学生有N人 教师1人 考场门口每次只能进出一个人 进考场原则是先来先进 当N个学生都进入考场后 教师才能发卷子 学生交卷后可以离开考场 教师要等收上来全部卷子并封装卷子后才能离开考场 问题 问共需设置几个进程 试用P V操作解决上述问题中的同步和互斥关系 解析 定义一个

11、共享变量StudentCounter N定义三个信号量 M1 1 实现对StudentCounter的互斥问 M2 1 表示学生是否到齐了 教师是否可以发试卷 M3 1 表示试卷是否收齐了 教师是否可以离开共需设置二个进程 学生进程 教师进程 学生 P M1 StudentCounter StudentCounter 1 IfStudentCounter 0V M2 V M1 答题 P M1 StudentCounter StudentCounter 1 IfStudentCounter NV M3 交试卷 离开考场 V M1 教师 P M2 发试卷 巡视考场 收试卷 P M3 离开 流水线问

12、题某流水线有4个并发工序P1 P2 P3 P4 他们执行情况如下 P1先执行 P1结束后 P2 P3同时开始执行 P2 P3都结束后 P1才能继续下一次执行 同时P4开始执行 试用PV操作实现他们之间的同步 解析 SA12 SB12 SA13 SB13 SB24 SB34 SemophoreSA12 SA13 1 SB12 SB13 SB24 SB34 0 ProcessPCBeginP SB13 执行P3V SB34 V SA13 End PC ProcessPBBeginP SB12 执行P2V SB24 V SA12 End PB ProcessPDBeginP SB24 P SB34

13、执行P4End PD ProcessPABeginP SA12 P SA13 执行P1V SB13 V SB12 End PA 某数据库有一个写进程 N个读进程 他们之间读写操作的互斥要求是 1 写进程正在写该数据库时 不能有其他进程读该数据库 2 读进程之间不互斥 可以同时读该数据库 3 如果有若干进程正在读该数据库 一个写进程正在等待写 则随后欲读的进程也不能读该数据库 需等待写进程先写 解法一 Rc 0 wc 0 共享变量Mutex 1 wr 1 互斥信号量READER Whilewc 1doskip 若有写进程请求 则后续读不响应P mutex Rc Rc 1 IfRc 1thenP

14、wr 若是第一个读进程 则要看有无写进程V mutex READINGP mutex Rc rc 1 Ifrc 0thenV wr 若所有读进程都执行完 可以让其它进程读写V mutex WRITER Wc 1 P wr WRITING Wc 0 V wr 解法二 另外设置一个信号量w 1 用于写进程到达后封锁后续读进程READER P w P mutex Rc rc 1 Ifrc 1thenP wr 若是第一个读进程 则要看有无写进程V mutex V w READINGP mutex Rc rc 1 Ifrc 0thenV wr 若所有读进程都执行完 可以让其它进程读写V mutex WR

15、ITER P w P wr WRITING V wr V w 隧道问题 一座山中有一条隧道 规定每次只允许一辆车过隧道 现在山南 山北都有车要过隧道 如果把每个过隧道者看作一个进程 为保证安全 请用PV操作实现正确管理 beginS semaphore S 1 cobeginprocess S N i i 1 2 beginP S 过隧道 V S end process N S i i 1 2 beginP S 过隧道 V S end 设在公共汽车上 司机和售票员的活动分别如下 司机的活动 启动车辆 正常行车 到站停车 售票员的活动 关车门 售票 开车门 问题 在汽车不停地到站 停车以及行驶的

16、过程中 司机和售票员之间的活动有什么同步关系 解答 首先分析两个进程之间的同步关系 汽车行驶过程中 司机活动与售票员活动之间的同步关系为 售票员关车门后 向司机发开车信号司机接到开车信号后起动车辆在汽车正常行驶过程中售票员售票到站时司机停车售票员在车停后开车门让乘客下车定义两个信号量s1 表示是否允许司机起动车辆 s2 表示是否允许售票员开门 初值为0 请将以下描述这两个活动的PV操作补充完整 Semaphores1 0 Semaphores2 0 main cobegindriver conductor Coend driver while 1 p s1 启动车辆 正常行车 到站停车 conductor while 1 关车门 售票 p s2 开车门 上下乘客 s1 表示是否允许司机起动车辆 s2 表示是否允许售票员开门 Semaphores1 0 Semaphores2 0 main cobegindriver conductor Coend driver while 1 p s1 启动车辆 正常行车 到站停车 v s2 conductor while 1 关车门 v s1 售票