第三章 OS经典习题值得收藏.doc

1、利用记录型信号量写出一个不会出现死锁的哲学家进餐问题的算法。（上课讲过） 2、桌上有1空盘，允许存放1个水果。爸爸向盘中放苹果，也可以向盘中放桔子。儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放1个水果供吃者取用。请用Wait()、Signal()原语实现爸爸、儿子、女儿三个并发进程的同步。 答：设置三个信号量S,So,Sa ,初值分别为1,0,0。分别表示可否向盘中放水果,可否取桔子,可否取苹果。 Father() { while(1) { p(S); 将水果放入盘中; if(是桔子)v(So); else v(Sa); } } Son() { while(1) { p(So) 取桔子 v(S); 吃桔子; } } Daughter() { while(1) { p(Sa) 取苹果 v(S); 吃苹果; } } 3、桌上有一只盘子，每次只能放入一个水果。爸爸专向盘中放苹果，妈妈专向盘中放桔子，一个女儿专等吃盘中的苹果，一个儿子专等吃盘中的桔子。试用P,V操作写出他们能同步的程序。（与2题类似，略） 4、题目不完整。 5、在一单道批处理系统中，一组作业的提交时间和运行时间如表所示。试计算以下3种作业调度算法的平均周转时间T和平均带权周转时间W。（西北大学 1998 （1）先来先服务； （2）短作业优先； （3）响应比高者优先。 表3-4 作业提交时间和运行时间表 作业 提交时间 运行时间 1 8.0 1.0 2 8.5 0.5 3 9.0 0.2 4 9.1 0.1 本题目中，多个任务先后在不同时刻到达且不要求等所以任务全部到达后才开始调度，也就是说，某个作业到达时，如果后备队列是空，则立即得到调度。 答： （1）先来先服务 作业 提交时间 运行时间 结束时间 周转时间 带权周转时间 1 8.0 1.0 9.0 1 1 2 8.5 0.5 9.5 1 2 3 9.0 0.2 9.7 0.7 3.5 4 9.1 0.1 9.8 0.7 7 平均周转时间=（1+1+0.7+0.7）/4=0.85 平均带权周转时间=（1+2+3.5+7）/4=3.375 （2）短作业优先 作业执行顺序为1-3-4-2 作业 提交时间 运行时间 结束时间 周转时间 带权周转时间 1 8.0 1.0 9.0 1 1 2 8.5 0.5 9.8 1.3 2.6 3 9.0 0.2 9.2 0.2 1 4 9.1 0.1 9.3 0.2 2 平均周转时间=（1+1.3+0.2+0.2）/4=0.675 平均带权周转时间=（1+2.6+1+2）/4=1.65 （3）响应比高者优先 作业1执行完，作业2和3等待，此时r2=1+（9-8.5）/0.5=2，r3=1+0/0.2=1，r2r3因此选择作业2运行。 作业2执行完，作业3和4等待，此时r3=1+（9.5-9）/0.2=3.5，r4=1+（9.5-9.1）/0.1=5，r4r3因此选择作业4运行。 作业的执行顺序为：1-2-4-3 作业 提交时间 运行时间 结束时间 周转时间 带权周转时间 1 8.0 1.0 9.0 1 1 2 8.5 0.5 9.5 1 2 3 9.0 0.2 9.8 0.8 4 4 9.1 0.1 9.6 0.5 5 平均周转时间=（1+1+0.8+0.5）/4=0.825 平均带权周转时间=（1+2+4+5）/4=3 6、某操作系统采用可变分区分配存储管理方法，用户区为512K，始址为0，用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的方案，且初始时用户区的512K空间空闲，对下述申请序列： 申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K，释放30K。 问： （1）采用首次适应算法，空闲分区有哪些空块(给出始址、大小)？ （2）采用最佳适应算法，空闲分区有哪些空块(给出始址、大小) ? （3）如再申请100K，针对（1）和（2）各有什么结果 （课上在黑板详细分析过，略） 7、对于如下表所示作业的段表（SMT），计算逻辑地址[0，430]，[2，88]，[4，112]，对应的主存地址（按十进制）。（其中方括号中的第一个元素为段号，第二个元素为段内地址） 段号 段长（容量） 主存起始地址 0 1 2 3 4 600 128 100 580 96 256 2300 112 1326 1952 答： [0，430]：430600(0号段长)，因此对应的主存地址256+430=686 [2，88] ：88100(2号