操作系统原理期末考试试题A卷参考答案及评分标准Word格式文档下载.docx
- 文档编号:6731445
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:27
- 大小:37.28KB
操作系统原理期末考试试题A卷参考答案及评分标准Word格式文档下载.docx
《操作系统原理期末考试试题A卷参考答案及评分标准Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《操作系统原理期末考试试题A卷参考答案及评分标准Word格式文档下载.docx(27页珍藏版)》请在冰点文库上搜索。
DMA:
DMA控制器控制内存与I/O设备之间的数据传递,不经过处理器(2分)
5.在操作系统环境下,“文件”的定义是什么?
请列出文件在磁盘中存储时空间分配的三种模式。
答:
“文件”是一个抽象的机制,它提供在磁盘上保存和读取信息的方式。
(3分)
空间分配模式有连续分配,链表式分配以及i节点方式。
二、编程计算题(本题共四小题,共计45分,必做)草稿区
✧请在下面的表格中指定答题顺序,在对应的分值下列明题号。
每格只许列出一个题号,否则做无效处理。
✧必须写明所有题目的题号,如果填写不完全,视为不指定答题顺序。
✧如填写内容无效或者不填写表格,则按照默认的题面分值评分
第一题(15分)
第二题(12分)
第三题(10分)
第四题(8分)
6.CPU利用率分析计算:
CPU利用率是指单位时间内,CPU运行进程指令时间所占的比例。
CPU利用率是评估
进程/线程调度机制的重要性能参数之一。
在某操作系统环境下,通过监测发现,在被I/O阻塞之前,平均每个
进程的运行时间为T,一次进程切换的时间开销为S,该操作系统采用时间片长度为Q的轮转调度策略,请给出
以下各种情况下,CPU利用率的计算公式:
1)Q=∞;
2)Q>
T;
3)S<
Q<
4)Q=S;
5)Q趋近于0;
(本题默认分值:
8分)
1,
因为时间片无限长,所以只有在发生I/O阻塞时才会出现进程调度,当进程运行了T时间后,调度会用去S时间。
2,
,时间片有限,则还需要考虑时间片轮转调度的时间。
在进程运行完时间片后,会发生一次调度,
而每运行T时间,又会发生一次调度,因为I/O而发生的调度占主导地位。
3,
,与上面的情况类似,时间片轮转调度占主导地位。
4,50%,时间片与调度时间相同,因而进程执行的时间与调度的时间是一样的。
5,0,时间片趋近于0,几乎所有的时间都在调度。
7.进程同步互斥问题解决:
有N名毕业生赴甲、乙两家公司求职,有的毕业生仅向其中一家公司求职,有的毕业生同时
向两家公司求职。
甲、乙两家公司在一座写字楼内办公,共用一间接待室进行面试,两家公司各派出一位人事主管负
责面试应聘者,每位人事主管每次仅面试1人。
甲公司拟录用L位员工,乙公司拟录用M位员工,一旦录取完毕就不
再面试后面的应聘者。
所有的应聘者排成一队在接待室门外等候,甲、乙两家公司的人事主管经协商后按严格轮转的
方式使用接待室,每位人事主管面试K位应聘者后,将接待室转交给另一位人事主管使用。
请分析以上需求,并利用信号量机制和P、V操作设计一个你认为合理有效的实施策略,实现要求如下:
1)请列出你在解决本问题时所做出的假设条件。
2)编写调度管理进程和两位人事主管进程的控制流程(使用伪代码)。
(6分)
3)请简要分析你所实现的策略的公平性。
(2分)(本题默认分值:
15分)
答:
答案可能还有问题
1)假设采用以下“面试策略”:
1.对人力资源经理而言,其工作流程如下:
●如果尚未录取足够的人数,则继续在面试等待队列中选择下一个合适的毕业生,并将轮转片数减一。
●如果没有应聘本公司的毕业生,则人力资源经理进入“睡眠”状态。
●如果已经录取了足够的毕业生,则人力资源经理结束工作。
●如果轮转片数为0,则人力资源经理进入“睡眠”状态。
2.对等待面试的毕业生而言,其工作流程如下:
●假定面试等待队列有100个坐位,如果队列已满,则无法进入等待队列。
(类似于“理发师睡眠”问题中的顾客)。
●如果面试人员应聘的公司已经录取足够的人数,则直接结束。
●如果还有等待坐位,而且应聘的公司尚未录满,则可以进入等待队列,并将状态标识为“等待面试”。
3.对于调度管理进程而言,必须提供以下功能:
●提供最靠前的一位面试甲公司和一位面试乙公司的毕业生
●将面试不合格,但申请了两家公司的学生放入等待队列的末尾
2)信号量及其他数据结构:
1.面试队列数据结构设计:
EMPLOYEEemployeeList[A];
//面试等待队列
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);
//释放面试候选人访问
break;
GetEmployee(employeeQueue);
//从候选队列中选择第一个候选人进入接待室
V(queueMutex);
AInterview();
//甲公司面试
times--;
//时间片减一
if(bInterviewResult)
{//决定录取当前人员
usANum++;
//已录取人数加1
}
setEmployeeState();
//设置刚应聘完毕业生的录取状态
V(receptionMutex);
VoidProcessBcompany()
If(usBNum>
=M)//如果已录取人数超过或等于M,则进程退出
V(mutex1);
BInterview();
//乙公司面试
if(bInterviewResult)
usBNum++;
V(mutex1);
VoidProcessManagement()
If(employeeQueue==NULL)//若面试候选队列为空则从等待队列中取出K放到面试候选人位置上
P(queueMutex);
//获得面试候选人队列
GetInterviewingCompany();
//获得正在面试的公司
SetEmployeeQueue();
//从等待队伍中按顺寻提取K个该公司的应聘者
//释放面试候选人队列
if(bEmployeeComeout)//如果有人面试出来
{
if(haveOtherWish)//若其还有其它的面试公司则将其插入到等待队伍末端
{
insert(employeeList);
if(employeeCome)//若有新的应聘者到来,将其插入到等待队尾
insert(employeeList);
3)公平性:
Ø
甲乙两公司按严格轮转方式使用接待室。
管理进程只选取符合求职意向的学生去见人事主管,保证每个人事主管在使用接待室内都能面试K名有意向的学生。
具有双重面试意向的学生,在面试不合格后,被放入等待面试队列的末尾,保证与其它学生的公平性。
虽然排在前面的学生可能因为求职意向不同,而晚于排在其后的不同求职意向的学生面试,但这是公平的,因为轮到他时他不能参加面试,但是他会比排在他之后的具有相同求职意向的学生先面试。
8.内存管理机制分析计算:
假设一个计算机中某个进程共有4个页帧,其装入时间、上次访问时间、和当前每个页面的
R位和M位如下表所示(时间以时钟滴答为单位)。
该进程共有6个页面,未来的页面访问字符串为421053241302,
请回答以下问题:
1)使用NRU算法将置换哪个页面?
2)使用FIFO算法将置换哪个页面?
3)使用LRU算法将置换哪个页面?
4)使用第二次机会算法将置换哪个页面?
5)从当前时刻开始至进程运行结束,哪种算法的页面失效次数最少?
(本题默认分值:
12分)
页面
装入时间
上次访问时间
R位
M位
126
280
1
230
265
2
140
270
3
110
285
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.设备管理计算分析题:
设备管理负责提供计算机最为重要的输入和输出功能,以打印机为例,需要为其建立完整的
I/O软件体系才能提供高效率的打印服务。
一个典型的文本打印页面包含50行,每行80个字符,设想一台打印机的
机械装置可以支持每分钟打印6个页面,打印机驱动程序采用中断驱动的方式运行。
每次中断服务的时间为50微秒,
打印机驱动程序整理并发送数据的时间为80微秒,数据传递给打印机寄存器的时间可忽略不计,请回答以下问题:
1)请简述中断驱动I/O的基本原理(提示:
用文字或图形方式进行步骤说明)
2)打印机的数据寄存器最小需要多少字节才能满足最快打印速度的需要?
3)打印驱动程序的CPU利用率为多少?
(本题默认分值:
10分)
1)(4分)
●特殊的内核进程发送数据到设备端口
●进程休眠,处理器调度其它进程
●当设备数据缓冲区为空时,设备发送中断给处理器
●进程被唤醒,并发送剩下的数据
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。
三、系统分析题(本题共三小题,共计25分,选做2题,多做题目不得分)
✧
第二题(10分)
10.在使用计算机的过程中,我们经常会使用Ctrl+C去结束一个正在运行的进程的执行。
如在windows的命令行模式中,
执行ping,在输出结束前输入Ctrl+C,得到如下图所示的输出。
请根据你对操作系统的了解,回答
以下问题
1)请简要阐述从输入Ctrl+C到看到屏幕输出之间,操作系统内部都进行了哪些处理操作。
2)请简要描述在你看来一种可行的Ctrl+C实现方式。
(提示:
给出关键步骤和流程即可)(本题默认分值:
答:
1)(5分)
1.键盘中断,用户敲击键盘产生键盘中断。
2.调度Shell。
操作系统在处理完键盘中断后,唤醒等待用户输入的Shell进程。
3.进程间通信。
Shell将接收到的Ctrl+C的信息传递给ping进程,完成一次进程间通信
4.退出ping进程,刷新输入输出缓冲区,释放各种资源
5.系统调度其它进程
2)(5分)使用信号机制来实现
1.Shell接收Ctrl+C字符串,并向ping进程发送kill信号
2.内核将ping进程的信号位图的kill位置1
3.内核查看ping进程的信号位图,执行处理kill信号的代码,即进程退出
11.在文件系统中,操作系统内核会从磁盘中读一些磁盘块到内存中,比如超级块,位图块,数据块等。
由于物理内存空
间有限,如果磁盘块长期占用内存,会造成系统资源的浪费。
如果不在内存中保存磁盘块,又会产生很多I/O操作。
一种解决方法是在内存中申请一定大小的BufferCache,操作系统要对磁盘块进行读写时,首先查询该磁盘块是否在
BufferCache中,如果不在,则从磁盘中读入该块到BufferCache中。
如果在,则直接对相应的BufferCache单元进行
操作,并在必要时同步BufferCache与磁盘中的数据。
请简要设计这种BufferCache机制的实现方法。
提示:
先设定文件系统的逻辑结构描述形式,并考虑数据同步进程的运行时机与性能保障(本题默认分值:
1.(2分)预分配一定数量的内存空间做为BufferCache。
BufferCache分为Header以及数据单元,
其中Header负责管理Cache,数据单元与文件系统块一样大小。
为提高查询速度,使用Hash将BufferCache分组,某个文件系统块只能出现在一个分组中,而且只能出现一次。
空闲Buffer也通过一个双向链表链接起来,使用LRU算法替换Buffer。
2.(3分)Header的数据结构如下:
StructHeader{
Intblkno;
//文件系统块号
Intstatus;
//状态
StructHeader*hprev;
//Hash分组中的前一个Buffer
StructHeader*hnext;
//hash分组中的后一个Buffer
StructHeader*fprev;
//空闲链表中的前一个Buffer
StructHeader*fnext;
//空闲链表中的后一个Buffer
状态如下
1)忙或空闲。
当前Buffer正在使用或未被使用
2)数据有效
3)Delayed-write。
数据被修改,在被其它块使用前,写回数据。
如果同一个块下次被请求,则可以减少一次I/O
4)有其它进程正在等待该Buffer。
3.(3分)BufferCache的分配:
1)根据块号通过Hash函数查询BufferCache,查询结果有以下几种情况:
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)进程之间竞争决定谁将占有空闲块
12.在32位计算机中,最大能使用的内存大小是4G,这在普通的PC上不会有问题。
但是,服务器上会有成千上万个进
程,4G内存就不够用了。
为此,Intel处理器引进了物理地址扩展(PAE)技术,通过将地址线扩展到36根,将能支
持的内存大小增加到64G。
在使用PAE后,虚拟地址空间会不会有变化?
如果有变化,变成多少?
操作系统是否需要
修改,如果需要,那么应该怎么修改?
与原来4G的情况相比,改善在哪里?
1),(4分)虚拟地址空间不会变化,仍然为4G,因为地址寄存器的大小仍然为32位,寻址方式并没有改变
2),(3分)操作系统需要修改。
因为物理地址空间比虚拟地址空间要大,变成64G,而一个页目录能映射的空间只有4G,
因而操作系统需要使用多个不同的页目录,或者一个页目录里有多套不同的页表,使用相同的线性地址空间去
访问不同的物理内存区域。
因为内存中存在了2^24个4K物理页,因而页目录项和页表项至少要使用36位来表示,
事实上,Intel处理器使用了64位,所以一个页目录或页表就只包括512项。
3),(3分)对于用户进程来说,因为不能修改页目录和页表,所以能使用的物理地址空间仍然只有4G,
但内核可以使用整个64G空间,因而能同时支持更大数量的进程,满足服务器的需要。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 原理 期末考试 试题 参考答案 评分标准