搜索
第1页，共14页南开大学信息技术科学学院本科生2008-2009年度第一学期操作系统原理课程期末试卷（A卷）专业▁▁▁▁▁年级▁▁▁▁▁姓名▁▁▁▁▁▁学号▁▁▁▁▁▁成绩▁▁▁▁▁一、简答题（本题共30分，每题6分，必做）草稿区1.请简述分时操作系统的基本特征（提示：简要描述每一个特征的含义）。虚拟，为每个进程分配虚拟的处理器和存储器，使得这些硬件设备好像被进程独占一样。（1.5分）并发，允许多个进程在一定时间内同时运行，但某一时刻只能有一个进程运行。（1.5分）共享，系统资源由各个进程共同使用。（1.5分）不确定，无法确定下一个执行的进程是谁。（1.5分）2.针对任何一种解决进程通信问题（互斥、同步）的方法和机制，判断其合理有效的标准是什么？答：1，任何两个进程不能同时进入临界区。（1.5分）2，不能对处理器的数量以及速度进行假设。（1.5分）3，不能因为处于临界区外的进程而阻塞其它进程。（1.5分）4，不能让某个进程永远等待进入临界区。（1.5分）得分第2页，共14页3.分页式虚拟存储管理和分段式虚拟存储管理的主要区别是什么？答：1，分页是一维，分段是二维。（2分）2，分页不利于代码段共享（2分）3，页式管理复杂，且占用较多额外资源（2分）草稿区4.请简述操作系统中驱动并控制I/O操作的三种不同方式（提示：对每一种方式进行简要说明）。答：程序控制I/O：也称轮询方式，CPU做所有的工作，不断的去查询设备的状态。（2分）中断：用户程序提出I/O请求后，在等待设备就绪的期间内，操作系统将其休眠，I/O设备以中断的形式通知其状态的改变，然后操作系统唤醒休眠的用户进程。（2分）DMA：DMA控制器控制内存与I/O设备之间的数据传递，不经过处理器（2分）5.在操作系统环境下，“文件”的定义是什么？请列出文件在磁盘中存储时空间分配的三种模式。答：“文件”是一个抽象的机制，它提供在磁盘上保存和读取信息的方式。（3分）空间分配模式有连续分配，链表式分配以及i节点方式。（3分）第3页，共14页二、编程计算题（本题共四小题，共计45分，必做）草稿区请在下面的表格中指定答题顺序，在对应的分值下列明题号。每格只许列出一个题号，否则做无效处理。必须写明所有题目的题号，如果填写不完全，视为不指定答题顺序。如填写内容无效或者不填写表格，则按照默认的题面分值评分第一题（15分）第二题（12分）第三题（10分）第四题（8分）6.CPU利用率分析计算：CPU利用率是指单位时间内，CPU运行进程指令时间所占的比例。CPU利用率是评估进程/线程调度机制的重要性能参数之一。在某操作系统环境下，通过监测发现，在被I/O阻塞之前，平均每个进程的运行时间为T，一次进程切换的时间开销为S，该操作系统采用时间片长度为Q的轮转调度策略，请给出以下各种情况下，CPU利用率的计算公式：1）Q=∞;2)QT;3)SQT;4)Q=S;5)Q趋近于0；（本题默认分值：8分）1，TTS,因为时间片无限长，所以只有在发生I/O阻塞时才会出现进程调度,当进程运行了T时间后，调度会用去S时间。（2分）2，/*QQQTS，时间片有限，则还需要考虑时间片轮转调度的时间。在进程运行完时间片后，会发生一次调度，而每运行T时间，又会发生一次调度，因为I/O而发生的调度占主导地位。（2分）3，/*TTTQS，与上面的情况类似，时间片轮转调度占主导地位。（2分）4，50%，时间片与调度时间相同，因而进程执行的时间与调度的时间是一样的。（2分）5，0，时间片趋近于0，几乎所有的时间都在调度。（2分）得分第4页，共14页草稿区7.进程同步互斥问题解决：有N名毕业生赴甲、乙两家公司求职，有的毕业生仅向其中一家公司求职，有的毕业生同时向两家公司求职。甲、乙两家公司在一座写字楼内办公，共用一间接待室进行面试，两家公司各派出一位人事主管负责面试应聘者，每位人事主管每次仅面试1人。甲公司拟录用L位员工，乙公司拟录用M位员工，一旦录取完毕就不再面试后面的应聘者。所有的应聘者排成一队在接待室门外等候，甲、乙两家公司的人事主管经协商后按严格轮转的方式使用接待室，每位人事主管面试K位应聘者后，将接待室转交给另一位人事主管使用。请分析以上需求，并利用信号量机制和P、V操作设计一个你认为合理有效的实施策略，实现要求如下：1）请列出你在解决本问题时所做出的假设条件。（2分）2）编写调度管理进程和两位人事主管进程的控制流程（使用伪代码）。（6分）3）请简要分析你所实现的策略的公平性。（2分）（本题默认分值：15分）答：答案可能还有问题1）假设采用以下“面试策略”：1.对人力资源经理而言，其工作流程如下：如果尚未录取足够的人数，则继续在面试等待队列中选择下一个合适的毕业生，并将轮转片数减一。如果没有应聘本公司的毕业生，则人力资源经理进入“睡眠”状态。如果已经录取了足够的毕业生，则人力资源经理结束工作。如果轮转片数为0，则人力资源经理进入“睡眠”状态。2.对等待面试的毕业生而言，其工作流程如下：假定面试等待队列有100个坐位，如果队列已满，则无法进入等待队列。（类似于“理发师睡眠”问题中的顾客）。如果面试人员应聘的公司已经录取足够的人数，则直接结束。如果还有等待坐位，而且应聘的公司尚未录满，则可以进入等待队列，并将状态标识为“等待面试”。3.对于调度管理进程而言，必须提供以下功能：提供最靠前的一位面试甲公司和一位面试乙公司的毕业生将面试不合格，但申请了两家公司的学生放入等待队列的末尾2)信号量及其他数据结构：1.面试队列数据结构设计：EMPLOYEEemployeeList[A];//面试等待队列第5页，共14页EMPLOYEEACompanyList[L];//甲公司录用的人员列表EMPLOYEEBCompanyList[M];//乙公司录用的人员列表2．信号量数据类型定义：typedefintsemph;//信号量数据类型定义semphreceptionMutex＝1;//实现互斥使用接待室的信号量semphqueueMutex=1;//实现互斥访问面试候选队列intusANum=0,usBNum=0;//记录甲乙两家公司已经录取的人数intusListNum=0;//记录等待队列中的面试者人数employeeQueue;//面试候选队列，长度为K本方案包括三个进程：甲公司人力资源经理进程、乙公司人力资源经理进程、调度管理进程。VoidProcessAcompany(){While(true){P(receptionMutex);//获得接待室Inttimes=K;//获得轮转片数While(times!=0){If(usANum=L)//如果已录取人数超过或等于L，则进程退出{V(receptionMutex);//释放接待室Return;}P(queueMutex);//访问面试候选人If(employeeQueue==NULL)//如果没有面试候选人，则退出当前轮转片{V(queueMutex);//释放面试候选人访问第6页，共14页break;}GetEmployee(employeeQueue);//从候选队列中选择第一个候选人进入接待室V(queueMutex);//释放面试候选人访问AInterview();//甲公司面试times--；//时间片减一if(bInterviewResult){//决定录取当前人员usANum++;//已录取人数加1}setEmployeeState();//设置刚应聘完毕业生的录取状态}V(receptionMutex);//释放接待室}}VoidProcessBcompany(){While(true){P(receptionMutex);//获得接待室Inttimes=K;//获得轮转片数While(times!=0){If(usBNum=M)//如果已录取人数超过或等于M，则进程退出{V(mutex1);//释放接待室Return;}第7页，共14页P(queueMutex);//访问面试候选人If(employeeQueue==NULL)//如果没有面试候选人，则退出当前轮转片{V(queueMutex);//释放面试候选人访问break;}GetEmployee(employeeQueue);//从候选队列中选择第一个候选人进入接待室V(queueMutex);//释放面试候选人访问BInterview();//乙公司面试times--；//时间片减一if(bInterviewResult){//决定录取当前人员usBNum++;//已录取人数加1}setEmployeeState();//设置刚应聘完毕业生的录取状态}V(mutex1);//释放接待室}}VoidProcessManagement(){While(true){If(employeeQueue==NULL)//若面试候选队列为空则从等待队列中取出K放到面试候选人位置上{P(queueMutex);//获得面试候选人队列GetInterviewingCompany();//获得正在面试的公司SetEmployeeQueue();//从等待队伍中按顺寻提取K个该公司的应聘者V(queueMutex);//释放面试候选人队列}第8页，共14页if(bEmployeeComeout)//如果有人面试出来{if(haveOtherWish)//若其还有其它的面试公司则将其插入到等待队伍末端{insert(employeeList);}}if(employeeCome)//若有新的应聘者到来，将其插入到等待队尾{insert(employeeList);}}}3）公平性：甲乙两公司按严格轮转方式使用接待室。管理进程只选取符合求职意向的学生去见人事主管，保证每个人事主管在使用接待室内都能面试K名有意向的学生。具有双重面试意向的学生，在面试不合格后，被放入等待面试队列的末尾，保证与其它学生的公平性。虽然排在前面的学生可能因为求职意向不同，而晚于排在其后的不同求职意向的学生面试，但这是公平的，因为轮到他时他不能参加面试，但是他会比排在他之后的具有相同求职意向的学生先面试。第9页，共14页草稿区8.内存管理机制分析计算：假设一个计算机中某个进程共有4个页帧，其装入时间、上次访问时间、和当前每个页面的R位和M位如下表所示（时间以时钟滴答为单位）。该进程共有6个页面，未来的页面访问字符串为421053241302，请回答以下问题：1）使用NRU算法将置换哪个页面？2）使用FIFO算法将置换哪个页面？3）使用LRU算法将置换哪个页面？4）使用第二次机会算法将置换哪个页面？5）从当前时刻开始至进程运行结束，哪种算法的页面失效次数最少？（本题默认分值：12分）页面装入时间上次访问时间R位M位012628010123026501214027000311028511答：1），（2分）假设每四次页访问清除R位和M位，替换时不改变页面队列顺序，当R位和M位相同时，替换排在前面的页。初始页面排列按装入时间为3,0,2,1。则，页面置换顺序列为：2，1，0，3，4，2，1，0，5，2，42），（2分）3，0，2，1，4，53），（2分）1，0，3，4，2，1，0，5，2，44），（2分）2，1，3，4，2，1，0，5，2，45），（2分）NRU算法不确定，在其它三种算法中，FIFO失效次数最少第10页，共14页草稿区9.设备管理计算分析题：设备管理负责提供计算机最为重要的输入和输出功能，以打印机为例，需要为其建立完整的I/O软件体系才能提供高效率的打印服务。一个典型的文本打印页面包含50行，每行80个字符，设想一台打印机的机械装置可以支持每分钟打印6个页面，打印机驱动程序采用中断驱动的方式运行。每次中断服务的时间为50微秒，打印机驱动程序整理并发送数据的时间为80微秒，数据传递给打印机寄存器的时间可忽略不计，请回答以下问题：1）请简述中断驱动I/O的基本原理（提示：用文字