操作系统原理期末考试试题B卷(2009)_参考答案2

第1页，共15页南开大学信息技术科学学院本科生2009-2010年度第一学期操作系统原理课程期末试卷（B卷）专业▁▁▁▁▁年级▁▁▁▁▁姓名▁▁▁▁▁▁学号▁▁▁▁▁▁成绩▁▁▁▁▁一、简答题（本题共30分，每题6分，必做）草稿区1.请阐述“操作系统”和“进程”的定义。答案：操作系统是控制和管理计算机系统内各种硬件和软件资源、合理有效地组织计算机系统的工作，为用户提供一个使用方便可扩展的工作环境，从而起到连接计算机和用户的接口作用的最基本的系统软件。（3分，重点在于管理和人机接口）进程是运行中的程序，它包括输入，输出，程序映像和运行过程中各种状态信息的统称。（3分）2.请简要描述设计IPC问题解决方法时需要遵循的四个基本原则。答案：（每个1.5分）1)任何两个进程都不能同时处于其临界区；2)不应对CPU的速度和数量做任何假设；3)临界区外运行的进程不得阻塞其他进程；4)不得使进程无限期的等待进入临界区；得分第2页，共15页草稿区3.请列出并说明至少具有“虚拟内存管理”特点的内存管理方法体系。答案：程序、数据和堆栈的总大小可能超过可用的物理内存的大小。由操作系统把程序当前使用的那些部分保存在主存中，而把其他部分保存在磁盘上，并在需要时在内存和磁盘间交换程序的片段。4.请简述DMA的三种不同工作模式（提示：对每一种方式进行简要说明）。答案：（每个2分，其中名词1分，说明1分）1)周期窃取模式（单一传输模式）：每次只传输以单位的数据，之后让出总线控制权并申请下一次传输；2)块传输模式：持续获得总线控制权，连续传输一定量的数据；3)飞越模式：DMA控制发送设备直接向内存传输数据5.请描述“文件”的定义，并说明文件的三种物理结构。答案：“文件”是一个抽象的机制，它提供在磁盘上保存和读取信息的方式。（3分）空间分配模式有连续分配，链表式分配以及i节点方式。（3分）第3页，共15页二、编程计算题（本题共5小题，共计45分，选做4题，多做不得分）草稿区请在下面的表格中指定答题顺序，在对应的分值下列明题号。每格只许列出一个题号，否则做无效处理。下表中必须写明所有题目的题号，如果填写不完全，视为不指定答题顺序。如填写内容无效或者不填写表格，则按照默认的题面分值评分第一题（15分）第二题（12分）第三题（10分）第四题（8分）6.CPU利用率计算：有5个批处理作业A到E，他们几乎同时到达一个计算中心，估计他们的运行时间分别为10，5，3，4，8分钟，其优先级（由外部设定）分别为4、3、5、2、1，其中5为最高优先级。对于下列每种调度算法，计算其平均进程周转时间，可忽略进程切换的时间开销。1）时间片轮转法（假设每个作业均公平共享CPU时间）；2）优先级调度法；3）先来先服务（作业到达顺序为A、B、C、D、E）；（本题默认分值：8分，列出计算公式与计算结果即可）评分标准：执行顺序正确，1分；计算过程正确1到2分，结果1分。1)时间片轮转法：（4分）假设时间片为t，并且t为一个充分小的数值，以保证其能够被任何宏观时间整除。进程C运行完各个进程消耗的总时间=5*5*t*(3/t)进程D运行完各个进程消耗的总时间=5*5*t*(3/t)+4*4*t*(4/t-3/t)进程B运行完各个进程消耗的总时间=5*5*t*(3/t)+4*4*t*(4/t-3/t)+3*3*t*(5/t-4/t)进程E运行完各个进程消耗的总时间=5*5*t*(3/t)+4*4*t*(4/t-3/t)+3*3*t*(5/t-4/t)+2*2*t*(8/t-5/t)进程A运行完各个进程消耗的总时间=5*5*t*(3/t)+4*4*t*(4/t-3/t)+3*3*t*(5/t-4/t)+2*2*t*(8/t-5/t)+1*t*(10/t-8/t)得分第4页，共15页平均周转时间=进程A运行完各个进程消耗的总时间/5=114/5=22.82)优先级调度法：（3分）执行顺序为：CABDE作业CABDE等待时间03131822运行时间310548周转时间313182230平均周转时间=(3+13+18+22+30)/5=17.23)先来先服务：（3分）执行顺序为：ABCDE作业ABCDE等待时间010151822运行时间105348周转时间1015182230平均周转时间=(10+15+18+22+30)/5=19第5页，共15页草稿区7.进程同步互斥问题解决：消息机制是解决IPC问题的一种重要方法，它大大简化了使用信号量机制的代码复杂性和设计上的风险。请用消息机制来描述生产者-消费者问题的解决方法，并回答以下问题1）简要描述消息机制中Send和Receive原语的内部处理流程（根据你的想法来设定）2）请基于消息机制，用伪代码来描述生产者-消费者问题的解决方案。（本题默认分值：15分）答案：假设所有的消息都有同样的大小，建立一个类似于一块共享内存缓冲区的N个槽。消费者首先将N条空消息发送给生产者，当生产者向消费者传递一个数据项时，它取走一条空消息并送回一个填充了内容的消息；这样系统中总的消息数保持不变，所以消息都可以存放在事先确定数量的内存中。Send(dst,content){关中断//保证Send函数为原子操作；将content放入dst进程的消息缓冲区中；开中断//恢复被关闭的中断情况；Scheduler()//调用进程调度函数，恢复用户进程运行；}Receive(src,content){If(没有从src进程发送来的消息)等待src消息，睡眠；Scheduler()//调用进程调度函数，恢复用户进程运行；}#defineN100//缓冲区中的槽数目Producer流程：第6页，共15页{While(TRUE){Item=produce_item()//产生放入缓冲区中的产品Receive(consumer,&m)//等待消费者发送空缓冲区Bulid_message(&m,item)//建立一个待发送的消息Send(consumer,&m)//发送数据项给消费者}}Consumer流程：{For(I=0;IN;I++)send(producer,&m)//发送N个空缓冲区While(TRUE){Receive(producer,&m)//接收包含数据项的消息Item=extract_item(&m)//将数据项从消息中提取出来Send(producer,&m)//将空的缓冲区发送回生产者Consume_item(item)//处理（消费）数据}}第7页，共15页草稿区8.进程同步互斥问题解决：信号量是解决IPC问题的重要方法，请尝试使用信号量机制解决经典的哲学家就餐问题。1）简要描述你需要定义几个进程，需要定义几个信号量，其各自的内涵是什么？2）以伪代码形式描述哲学家就餐问题的信号量机制解法。（本题默认分值：15分）答案：需要为每个哲学家定义一个进程，设定哲学家数目为N，则需要N+1个信号量。#defineN//哲学家的数目#defineLEFT(i+N-1)%N//i的左邻居编号#defineRIGHT(i+1)%N//i的右邻居编号#defineTHINKING0//哲学家在思考状态#defineHUNGRY1//哲学家试图拿起叉子#defineEATING2//哲学家进餐状态Typedefintsemaphore//定义信号量Intstate[N]//数组用来跟踪记录每位哲学家的状态Semaphoremutex=1//临界区互斥Semaphores[N]//每个哲学家一个信号量Philosopher(inti){While(TRUE){Think()//哲学家在思考Take_forks(i)//哲学家i要求得到两把叉子或者被阻塞Eat()//进餐Put_forks(i)//哲学家i将两把叉子放回桌子}第8页，共15页}Take_forks(inti){Down(&mutex)//进入临界区State[i]=HUNGRY//记录哲学家i处于饥饿状态Test(i)//尝试获得两把叉子Up(&mutex)//离开临界区Down(&s[i])//如果得不到需要的叉子则阻塞}Put_forks(){Down(&mutex)//进入临界区State[i]=THINKING//哲学家已经就餐完毕Test(LEFT)//检查左边的邻居可否进餐Test(RIGHT)//检查邮编的邻居可否进餐Up(&mutex)//离开临界区}Test(){If(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){State[i]=EATING//开始进餐Up(&s[i])//解除阻塞在等待叉子上的哲学家i}}第9页，共15页草稿区9.死锁问题解决：死锁是对分时操作系统最为知名的一种问题，有很多种方法用来解决死锁问题，其中银行家算法是一种方便有效的死锁避免方法，尝试用银行家算法来回答以下问题：一个系统中有4个进程和5种可分配资源，当前分配资源和最大需求如下表所示：已分配资源最大需求量可用资源量进程A102111121200X11进程B2011022210进程C1101021310进程D1111011221在上表中，第三种资源的可用资源量未知，用X表示，请问，为保持当前状态为安全状态，X的最小值是多少？（本题默认分值：10分，请说明分析计算的思路，列出关键计算过程）答案：1)安全状态：即在当前的进程需求、资源总量和资源分配情况下，存在至少一个可使所有进程运行结束的序列的状态。（2分）2)检查当前的进程和资源量，发现：a)当前的4个进程中，只有D存在运行结束的可能性；b)进程A、B和C不可能立即运行完毕，必须等待；c)因此，第一个能够运行的进程为D，且：X=1；3)D运行结束后，可用资源量为(1,1,1+X,2,1)且X=1。（2分）4)再次检查A、B和C进程，发现：a)只有A可以运行;b)进程B和C需要等待第一类或第二类资源；c)此时，在X=1的条件下，A已经可以运行了。5)A运行完成后，可用资源量为(2,1,3+X,3,2)且X=1。（2分）6)再次检查B和C进程，发现：a)只有C可以运行;第10页，共15页b)进程B需要等待第二类资源；c)此时，在X=1的条件下，C已经可以运行了。（2分）7)C运行完成后，可用资源量为(3,2,3+X,4,2)，此时，B可以运行了，且不对X提出新的要求。8)因此，X的最小值为1。（2分）评分标准：初步分析：2分执行顺序：2分每个进程运行时对X的要求的分析：4分，每个进程1分最终结果：2分各部分的逻辑性和分析如果正确，可酌情给分，满分10分。第11页，共15页草稿区10.虚拟存储管理问题：页面失效次数和页面置换算法是评估分页存储管理系统的重要因素，假设一个进程有4个页帧和8个页面，页面编号为0~7，该进程的页面访问序列为0172327103，请回答以下问题：1）若使用LRU页面置换算法，请问会发生多少次页面失效？列出每次页面置换的结果；2）若使用工作集页面置换算法，请问比较合理的工作集大小是多少？列出对应的页面失效次数和置换结果；（本题默认分值：12分）答案：LRU方式：共7次。（5分，页面失效位置2分，物理页状态2分，结果1分）工作集方式：由于物理页帧有4页，因此，选择最近使用的4个页面组成工作集。使用局部性原理，进行预读取。共6次。0172327103物理页10000333300物理页2NULL111111111物理页3NULLNULL77777777物理页4NULLNULLNULL2222223页面失效是是是是是否否否是是0172327103物理页10000333300物理页21111111111物理页32277777777物理页43332222223页面失效是否是是是否否否是是第12页，共15页草稿区三、系统分析题（本题共3小题，共计25分，选做2题，多做题目不得分）请在下面的表格中指定答题顺序，在对应的分值下列明题号。每格只许列出一个题号，否则做无效处