当前位置:首页 >> 数学 >>

操作系统原理期末考试试题A卷(2008)


南开大学信息技术科学学院本科生 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 分)

第 1 页,共 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

第 2 页,共 14 页

得 分 二、编程计算题(本题共四小题,共计 45 分,必做) 草稿区

? 请在下面的表格中指定答题顺序,在对应的分值下列明题号。每格只许列出一个题号,否则做无效处理。 ? 必须写明所有题目的题号,如果填写不完全,视为不指定答题顺序。 ? 如填写内容无效或者不填写表格,则按照默认的题面分值评分 第一题(15 分) 第二题(12 分) 第三题(10 分) 第四题(8 分)

6. CPU 利用率分析计算:CPU 利用率是指单位时间内,CPU 运行进程指令时间所占的比例。CPU 利用率是评估 进程/线程调度机制的重要性能参数之一。在某操作系统环境下,通过监测发现,在被 I/O 阻塞之前,平均每个 进程的运行时间为 T,一次进程切换的时间开销为 S,该操作系统采用时间片长度为 Q 的轮转调度策略,请给出 以下各种情况下,CPU 利用率的计算公式: 1)Q = ∞; 2) Q > T; 3) S < Q < T; 4) Q = S; 5) Q 趋近于 0; (本题默认分值:8 分) 1,
T , 因为时间片无限长,所以只有在发生 I/O 阻塞时才会出现进程调度, 当进程运行了 T 时间后,调度会用去 S 时间。 分) (2 T ?S
Q ,时间片有限,则还需要考虑时间片轮转调度的时间。在进程运行完时间片后,会发生一次调度, Q ? ?Q / T ? * S ? ?

2,

而每运行 T 时间,又会发生一次调度, 因为 I/O 而发生的调度占主导地位。 分) (2

3,

T ,与上面的情况类似,时间片轮转调度占主导地位。 分) (2 T ? ?T / Q ? * S ? ?

4,50%,时间片与调度时间相同,因而进程执行的时间与调度的时间是一样的。 分) (2 5,0,时间片趋近于 0,几乎所有的时间都在调度。 分) (2

第 3 页,共 14 页

草稿区 7. 进程同步互斥问题解决:有 N 名毕业生赴甲、乙两家公司求职,有的毕业生仅向其中一家公司求职,有的毕业生同时 向两家公司求职。甲、乙两家公司在一座写字楼内办公,共用一间接待室进行面试,两家公司各派出一位人事主管负 责面试应聘者,每位人事主管每次仅面试 1 人。甲公司拟录用 L 位员工,乙公司拟录用 M 位员工,一旦录取完毕就不 再面试后面的应聘者。所有的应聘者排成一队在接待室门外等候,甲、乙两家公司的人事主管经协商后按严格轮转的 方式使用接待室,每位人事主管面试 K 位应聘者后,将接待室转交给另一位人事主管使用。 请分析以上需求,并利用信号量机制和 P、V 操作设计一个你认为合理有效的实施策略,实现要求如下: 1) 请列出你在解决本问题时所做出的假设条件。 分) (2 2) 编写调度管理进程和两位人事主管进程的控制流程(使用伪代码)(6 分) 。 3) 请简要分析你所实现的策略的公平性。 (2 分) 答: 答案可能还有问题 1)假设采用以下“面试策略” : 1. 对人力资源经理而言,其工作流程如下: ? 如果尚未录取足够的人数,则继续在面试等待队列中选择下一个合适的毕业生,并将轮转片数减一。 ? 如果没有应聘本公司的毕业生,则人力资源经理进入“睡眠”状态。 ? 如果已经录取了足够的毕业生,则人力资源经理结束工作。 ? 如果轮转片数为 0,则人力资源经理进入“睡眠”状态。 (本题默认分值:15 分)

2. 对等待面试的毕业生而言,其工作流程如下: ? 假定面试等待队列有 100 个坐位,如果队列已满,则无法进入等待队列。 (类似于“理发师睡眠”问题中的顾客) 。 ? 如果面试人员应聘的公司已经录取足够的人数,则直接结束。 ? 如果还有等待坐位,而且应聘的公司尚未录满,则可以进入等待队列,并将状态标识为“等待面试” 。

3. 对于调度管理进程而言,必须提供以下功能: ? 提供最靠前的一位面试甲公司和一位面试乙公司的毕业生 ? 将面试不合格,但申请了两家公司的学生放入等待队列的末尾 2) 信号量及其他数据结构: 1. 面试队列数据结构设计: EMPLOYEE employeeList[A]; //面试等待队列
第 4 页,共 14 页

EMPLOYEE ACompanyList[L];

//甲公司录用的人员列表

EMPLOYEE BCompanyList[M]; //乙公司录用的人员列表 2.信号量数据类型定义: typedef int semph; //信号量数据类型定义

semph receptionMutex = 1; //实现互斥使用接待室的信号量 semph queueMutex = 1; //实现互斥访问面试候选队列

int usANum = 0, usBNum = 0; //记录甲乙两家公司已经录取的人数 int usListNum = 0; //记录等待队列中的面试者人数
employeeQueue; //面试候选队列,长度为 K

本方案包括三个进程:甲公司人力资源经理进程、乙公司人力资源经理进程、调度管理进程。
Void ProcessAcompany() { While(true) { P(receptionMutex); //获得接待室 Int times = K; //获得轮转片数 While(times != 0) { If(usANum >= L) //如果已录取人数超过或等于 L,则进程退出 { V(receptionMutex);//释放接待室 Return; } P(queueMutex); //访问面试候选人 If(employeeQueue == NULL) { V(queueMutex); //释放面试候选人访问 第 5 页,共 14 页 //如果没有面试候选人,则退出当前轮转片

break; } GetEmployee(employeeQueue); //从候选队列中选择第一个候选人进入接待室

V(queueMutex); //释放面试候选人访问 AInterview(); //甲公司面试 times--;//时间片减一 if (bInterviewResult) {//决定录取当前人员 usANum++; //已录取人数加 1 } setEmployeeState(); //设置刚应聘完毕业生的录取状态 } V(receptionMutex);//释放接待室 } } Void ProcessBcompany() { While(true) { P(receptionMutex); //获得接待室 Int times = K; //获得轮转片数 While(times != 0) { If(usBNum >= M) //如果已录取人数超过或等于 M,则进程退出 { V(mutex1); Return; } 第 6 页,共 14 页 //释放接待室

P(queueMutex); //访问面试候选人 If(employeeQueue == NULL) { V(queueMutex); //释放面试候选人访问 break; } GetEmployee(employeeQueue); //从候选队列中选择第一个候选人进入接待室 //如果没有面试候选人,则退出当前轮转片

V(queueMutex); //释放面试候选人访问 BInterview(); //乙公司面试 times--;//时间片减一 if(bInterviewResult) {//决定录取当前人员 usBNum++; //已录取人数加 1 } setEmployeeState(); //设置刚应聘完毕业生的录取状态 } V(mutex1); } } //释放接待室

Void Process Management() { While(true) { If(employeeQueue == NULL) //若面试候选队列为空则从等待队列中取出 K 放到面试候选人位置上 { P(queueMutex); //获得面试候选人队列 GetInterviewingCompany(); //获得正在面试的公司 SetEmployeeQueue(); //从等待队伍中按顺寻提取 K 个该公司的应聘者 V(queueMutex); //释放面试候选人队列 } 第 7 页,共 14 页

if(bEmployeeComeout) //如果有人面试出来 { if(haveOtherWish) //若其还有其它的面试公司则将其插入到等待队伍末端 { insert(employeeList); } } if(employeeCome) //若有新的应聘者到来,将其插入到等待队尾 { insert(employeeList); } } }

3)公平性: ? 甲乙两公司按严格轮转方式使用接待室。 ? 管理进程只选取符合求职意向的学生去见人事主管,保证每个人事主管在使用接待室内都能面试 K 名有意向的学生。 ? 具有双重面试意向的学生,在面试不合格后,被放入等待面试队列的末尾,保证与其它学生的公平性。 ? 虽然排在前面的学生可能因为求职意向不同,而晚于排在其后的不同求职意向的学生面试,但这是公平的,因为轮到他时他不能参加面试,但是他会比排在他之后的具 有相同求职意向的学生先面试。

第 8 页,共 14 页

草稿区 8. 内存管理机制分析计算:假设一个计算机中某个进程共有 4 个页帧,其装入时间、上次访问时间、和当前每个页面的 R 位和 M 位如下表所示(时间以时钟滴答为单位) 。该进程共有 6 个页面,未来的页面访问字符串为 421053241302, 请回答以下问题: 1) 使用 NRU 算法将置换哪个页面?2)使用 FIFO 算法将置换哪个页面?3)使用 LRU 算法将置换哪个页面? 4) 使用第二次机会算法将置换哪个页面?5)从当前时刻开始至进程运行结束,哪种算法的页面失效次数最少? (本题默认分值:12 分)
页面 0 1 2 3 装入时间 126 230 140 110 上次访问时间 280 265 270 285 R位 1 0 0 1 M位 0 1 0 1

答: 1)(2 分)假设每四次页访问清除 R 位和 M 位,替换时不改变页面队列顺序,当 R 位和 M 位相同时,替换排在前面的页。 , 初始页面排列按装入时间为 3,0,2,1。则,页面置换顺序列为:2,1,0,3,4,2,1,0,5,2,4 2)(2 分)3,0,2,1,4,5 , 3)(2 分)1,0,3,4,2,1,0,5,2,4 , 4)(2 分)2,1,3,4,2,1,0,5,2,4 , 5)(2 分)NRU 算法不确定,在其它三种算法中,FIFO 失效次数最少 ,

第 9 页,共 14 页

草稿区 9. 设备管理计算分析题:设备管理负责提供计算机最为重要的输入和输出功能,以打印机为例,需要为其建立完整的 I/O 软件体系才能提供高效率的打印服务。一个典型的文本打印页面包含 50 行,每行 80 个字符,设想一台打印机的 机械装置可以支持每分钟打印 6 个页面,打印机驱动程序采用中断驱动的方式运行。每次中断服务的时间为 50 微秒, 打印机驱动程序整理并发送数据的时间为 80 微秒,数据传递给打印机寄存器的时间可忽略不计,请回答以下问题: 1) 请简述中断驱动 I/O 的基本原理(提示:用文字或图形方式进行步骤说明) 2) 打印机的数据寄存器最小需要多少字节才能满足最快打印速度的需要? 3) 打印驱动程序的 CPU 利用率为多少? 答:1) 分) (4 ? ? ? ? 特殊的内核进程发送数据到设备端口 进程休眠,处理器调度其它进程 当设备数据缓冲区为空时,设备发送中断给处理器 进程被唤醒,并发送剩下的数据 (本题默认分值:10 分)

2) 分) (4 ,52。处理打印机数据寄存器大小的数据需要 50 + 80 = 130 微秒的时间,最快打印速度是 6 * 50 * 80 字符每分钟, 也就是 400 字符每秒,因而打印机的数据寄存器最小需要 400 * 130 / 1000 = 52 字节。 3)(2 分)80/130。一次打印任务需要用去 50 + 80 = 130 微秒的时间,而中断驱动程序整理并发送数据需要 80 微秒, , 因而打印驱动程序的 CPU 利用率是 80/130。

第 10 页,共 14 页

草稿区

得 分 三、系统分析题(本题共三小题,共计 25 分,选做 2 题,多做题目不得分) ? ? 请在下面的表格中指定答题顺序,在对应的分值下列明题号。每格只许列出一个题号,否则做无效处理。 ? 必须写明所有题目的题号,如果填写不完全,视为不指定答题顺序。 ? 如填写内容无效或者不填写表格,则按照默认的题面分值评分 第一题(15 分) 第二题(10 分)

10. 在使用计算机的过程中,我们经常会使用 Ctrl + C 去结束一个正在运行的进程的执行。如在 windows 的命令行模式中, 执行 ping www.nankai.edu.cn,在输出结束前输入 Ctrl + C,得到如下图所示的输出。请根据你对操作系统的了解,回答 以下问题 1) 请简要阐述从输入 Ctrl + C 到看到屏幕输出之间,操作系统内部都进行了哪些处理操作。 2) 请简要描述在你看来一种可行的 Ctrl+C 实现方式。 (提示:给出关键步骤和流程即可) (本题默认分值:15 分) 答:1) 分) (5 1. 2. 3. 4. 5. 键盘中断,用户敲击键盘产生键盘中断。 调度 Shell。操作系统在处理完键盘中断后,唤醒等待用户输入的 Shell 进程。 进程间通信。Shell 将接收到的 Ctrl + C 的信息传递给 ping 进程,完成一次进程间通信 退出 ping 进程,刷新输入输出缓冲区,释放各种资源 系统调度其它进程

2) 分)使用信号机制来实现 (5 1. 2. 3. Shell 接收 Ctrl + C 字符串,并向 ping 进程发送 kill 信号 内核将 ping 进程的信号位图的 kill 位置 1 内核查看 ping 进程的信号位图,执行处理 kill 信号的代码,即进程退出

第 11 页,共 14 页

草稿区 11. 在文件系统中,操作系统内核会从磁盘中读一些磁盘块到内存中,比如超级块,位图块,数据块等。由于物理内存空 间有限,如果磁盘块长期占用内存,会造成系统资源的浪费。如果不在内存中保存磁盘块,又会产生很多 I/O 操作。 一种解决方法是在内存中申请一定大小的 Buffer Cache,操作系统要对磁盘块进行读写时,首先查询该磁盘块是否在 Buffer Cache 中,如果不在,则从磁盘中读入该块到 Buffer Cache 中。如果在,则直接对相应的 Buffer Cache 单元进行 操作,并在必要时同步 Buffer Cache 与磁盘中的数据。请简要设计这种 Buffer Cache 机制的实现方法。 提示:先设定文件系统的逻辑结构描述形式,并考虑数据同步进程的运行时机与性能保障(本题默认分值:15 分) 答: 1. (2 分)预分配一定数量的内存空间做为 Buffer Cache。Buffer Cache 分为 Header 以及数据单元,

其中 Header 负责管理 Cache,数据单元与文件系统块一样大小。 为提高查询速度,使用 Hash 将 Buffer Cache 分组,某个文件系统块只能出现在一个分组中,而且只能出现一次。 空闲 Buffer 也通过一个双向链表链接起来,使用 LRU 算法替换 Buffer。 2. (3 分)Header 的数据结构如下: Struct Header{ Int blkno; // 文件系统块号 Int status; // 状态 Struct Header* hprev; // Hash 分组中的前一个 Buffer Struct Header* hnext; // hash 分组中的后一个 Buffer Struct Header* fprev; // 空闲链表中的前一个 Buffer Struct Header* fnext; // 空闲链表中的后一个 Buffer } 状态如下 1) 忙或空闲。当前 Buffer 正在使用或未被使用 2) 数据有效 3) Delayed-write。数据被修改,在被其它块使用前,写回数据。如果同一个块下次被请求,则可以减少一次 I/O 4) 有其它进程正在等待该 Buffer。 3. (3 分)Buffer Cache 的分配:
第 12 页,共 14 页

1) 根据块号通过 Hash 函数查询 Buffer Cache,查询结果有以下几种情况: a) 如果该块的 Cache 存在于 Hash 分组中,并且状态为空闲。 b) 如果 Cache 不在 Hash 分组中,则从空闲链表中分配一个。 c) 如果在分配空闲 Cache 时,发现 Cache 的状态为 delayed-write,则异步方式将数据写回磁盘,并重新申请 空闲 Cache。 d) 如果空闲链表为空,则将进程休眠,并放入等待队列 e) 如果块的 Cache 在 Hash 分组中,但是状态为忙,表示有其它进程正在使用,则休眠,并放入等待队列。 2) 在得到一个空闲 Cache 后,将其从空闲链表中删除 a) 如果该 Cache 是属于同一个块的,则将状态置为忙 b) 如果该 Cache 属于同一个 Hash 组,则设置其块号与状态 c) 如果该 Cache 属于其它 Hash 组,则将其从其它 Hash 组中删除,并插入到块所在的组中,设置块号与状态 d) 如果该 Cache 不属于任何 Hash 组,则将其插入到块所在的组中,设置块号与状态 4. (2 分)释放 Cache。 1) 如果 Cache 的数据有效,且没有老化,将其放入空闲链表尾,否则放入开头 2) 激活等待队列里的进程 3) 进程之间竞争决定谁将占有空闲块

第 13 页,共 14 页

草稿区 12. 在 32 位计算机中,最大能使用的内存大小是 4G,这在普通的 PC 上不会有问题。但是,服务器上会有成千上万个进 程,4G 内存就不够用了。为此,Intel 处理器引进了物理地址扩展(PAE)技术,通过将地址线扩展到 36 根,将能支 持的内存大小增加到 64G。在使用 PAE 后,虚拟地址空间会不会有变化?如果有变化,变成多少?操作系统是否需要 修改,如果需要,那么应该怎么修改?与原来 4G 的情况相比,改善在哪里? (本题默认分值:10 分) 答:1)(4 分)虚拟地址空间不会变化,仍然为 4G,因为地址寄存器的大小仍然为 32 位,寻址方式并没有改变 , 2)(3 分)操作系统需要修改。因为物理地址空间比虚拟地址空间要大,变成 64G,而一个页目录能映射的空间只有 4G, , 因而操作系统需要使用多个不同的页目录,或者一个页目录里有多套不同的页表,使用相同的线性地址空间去 访问不同的物理内存区域。 因为内存中存在了 2^24 个 4K 物理页,因而页目录项和页表项至少要使用 36 位来表示, 事实上,Intel 处理器使用了 64 位,所以一个页目录或页表就只包括 512 项。 3)(3 分)对于用户进程来说,因为不能修改页目录和页表,所以能使用的物理地址空间仍然只有 4G, , 但内核可以使用整个 64G 空间,因而能同时支持更大数量的进程,满足服务器的需要。

第 14 页,共 14 页


相关文章:
操作系统原理期末试卷(参考答案及评分标准)
操作系统原理期末试卷(参考答案及评分标准)_教育学_高等教育_教育专区。重庆大学...(10 分每题 1 分) 1、页表中的脏数据位(Dirty Bit)可以(B) (A) 用来...
操作系统原理期末试卷及答案
第1 页共 6 页 操作系统原理试卷 1 一、填空题(20 分) 1.在操作系统中,...(10 分) 五、以两个用户 A、B 共享同一文件 File1 为例,用图的方式说明...
2008秋操作系统本科试卷A
操作系统试题操作系统试题隐藏>> 2008 2009 第一学期) 2006 期末试卷(A) 黄石...(第一学期) 2006 年级 计算机科学与技术 专业 操作系统原理 本科 期末试卷(A)...
操作系统原理期末试卷(10套含答案)7
操作系统原理期末试题(一)一、单项选择题(每题 2 ...(16)3 2006~2007 学年第二学期期末考试 A 卷...缺页率为 10/16 丽水学院 2007-2008 学年第二...
操作系统 试题(A卷)
操作系统原理试题(A卷) 3页 免费 操作系统试题2008A卷 暂无评价 5页 免费...2010—2011 学年度第一学期期末考试 计算机系 操作系统 试题(A 卷) [适用班级...
2008秋操作系统本科试卷A (1)
2008 - 2009 学年度 (第一学期) 2006 年级 计算机科学与技术 专业 操作系统原理 本科 期末试卷(A) 一、单项选择题(本大题共 20 题,每题 1 分,共 20 分...
2010级网络《操作系统原理》-a卷
命题方式: 单独命题 佛山科学技术学院 2012~2013 学年第 一 学期 《操作系统原理》课程期期末考试试题(A 卷)专业、班级: 10 级网络 姓名: 题号得分一、单项...
湖北理工学院2010年度《操作系统原理》本科期末试卷(A)
湖北理工学院2010年度《操作系统原理》本科期末试卷(A)_理学_高等教育_教育专区。湖北理工学院操作系统原理期末试题2011 - 2012 学年度 (第一学期) 09 计科专业 ...
2007年秋操作系统原理试卷A
南阳理工学院 2007~2008 学年第一学期期末试卷操作系统原理》A一、单项选择(每项 1 分选择,计 20 分) 1.(⑴)不是批处理多道程序的性质。 A.“多道作...
操作系统原理试卷A
操作系统原理试卷A_工学_高等教育_教育专区。西北民族大学数学与计算机科学学院期末考试 操作系统原理试卷(A 卷) 专业: 学号: 总分 核分人 复查人 题号 题分 ...
更多相关标签: