《北京交通大学-923-2012-真题》由会员分享,可在线阅读,更多相关《北京交通大学-923-2012-真题(11页珍藏版)》请在金锄头文库上搜索。
1、梦想团队公益活动免费提供,一切需要付费的都不是真的,切记! 北京交通大学北京交通大学 2012 年硕士研究生入学考试试卷年硕士研究生入学考试试卷 科目代码:科目代码: 923 科目名称:科目名称: 操作系统原理操作系统原理 注意事项:答案一律写在答题纸上,写在试卷上的答案不予装订和评分注意事项:答案一律写在答题纸上,写在试卷上的答案不予装订和评分 一、 简题(本部分共一、 简题(本部分共 5 个小题,每个小题个小题,每个小题 10 分,共分,共 50 分)分) 1.方便性和有效性是设计操作系统的两个主要目标,以两种操作系统的技术为例,分别说明它们是如何实现这两个目标的 (一个实现方便性的例子,
2、 一个实现有效性的例子) 。 答题思路:方便性:操作系统提供了良好的用户接口,用户按需要输入命令,操作系统按命令去控制程序的执行; 用户也可以在程序中调用操作系统的功能模块完成相应服务, 而不必了解硬件的物理特性。 操作系统的有效性包含两个方面的含义,即提高系统资源利用率,提高系统吞吐量。 1有效地管理和分配硬件、软件资源,提高系统工作效率。2操作系统扩充硬件的功能,使硬件的功能发挥得更好.3操作系统使用户合理共享资源,防止各用户间的相互干扰.4操作系统合理地组织计算机的工作流程,使用户程序能顺利完成。2.主流微型计算机中分页存储系统中页面的大小通常设定为 1KB、2KB/4KB 等。如果页面
3、大小设置为更大或者更小,会带来哪些好处和问题?解析:我们都知道,页面大,页表小,节省页表空间,而且查找快,缺页中断发生的次数相对而言少一些。而且一次换页的时间长,页内碎片(属于内部碎片了)导致的浪费比较大。页表小的则刚好相反。 页表小了可以节省存储空间,减少内部碎片带来的浪费。进程调页的速度也比较快。等等。当然,王道有同学也给了一种说法。如下: 对于较大的页面,有以下的好处和问题: 1可以节省地址映射的存储空间;2使虚拟存储器的实现变得更加简单各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y
4、a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研梦想团队公益活动免费提供,一切需要付费的都不是真的,切记! 3主存与辅存之间传送较大页面比传送较小页面更有效。4联想存储器的项数优先, 对于同样的快表, 较大页面意味着可搞笑实现更多存储空间的地址转换,减少快表失效次数。较小页面的优点:是我们解法的一部分说法。 3.如果用于进程同步的信号量的 P、 V 操作不用原语实现, 会产生什么后果?举例说明。参考答案:看看我们 2010 年的真题里面,有这么一个:两段程序分别如下(其中,R 是寄存器,counter 为共享变量而且初始值为 1) :程序
5、 A R=counter; R=R+1; counter=R 程序 B R=counter; R=R-1; counter=R 这两个程序就是一个例子,要是不用原语实现,会有 0,1,2 三个结果。即没有试下互斥,结果具有不可再现性。4.磁盘长期使用后,读写磁盘中数据的速度就会变慢,而执行磁盘碎片整理程序后,速度就提高了,为什么?参考答案: 1文件磁盘存储不连续。 计算机系统经过一段时间的使用后, 由于文件修改、删除、新建等操作混合在一起产生的积累效应,许多文件在磁盘上的存储变得不连续。导致读写磁盘中的数据的速度变慢。2有效提高文件系统性能。这时,使用“磁盘碎片整理程序”整理磁盘碎片,可以有效
6、提高文件系统的性能。3磁盘是一个靠盘片的高速旋转进行读写的设备,当系统需要读写的数据连续存储在同一个磁道时,效率较高;当数据的存储不连续时,由于寻道开销,效率会有较大下降。用户在读写文件时,经常是顺序进行的(虽然系统支持随机存取) 。另外,即使再随机存取的情况下,文件的连续存储也有利于磁盘缓存系统的工作。5.虚拟内存的容量可以比物理内存大得多,但是访问速度和物理内存相近,为什么?虚拟内存的容量可以比物理内存大得多,但是访问速度和物理内存相近,为什么?各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o
7、 y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研3 分析:本题我们探索了很久,没有找到太好的答案。我们认为,解释成基于程序的局部性原理的预测,调入当前访问位置的附近区域内容。 因而,我们给出了一种解答方法。要是你的解答方法不同,请与我们一起讨论。呵呵。 。 。群体力量大,相信我们会有合理的大家认同的答案的。 虚拟存储器, 是指具有请求调入功能和置换功能, 能从逻辑上对内存容量加以扩充的一种存储器系统。并基于一定的调页算法,加上局部性原理等有效措施,使得即将要访问的内容以比较高的可能性提前被调入内存中,而无需等到要访问该内容了才去外存
8、调取,从而减少时间开销。其逻辑容量由内存容量和外存容量之和所决定,其运行速度接近于内存速度,而每位的成本却又接近于外存。 二、 计算论证题(本部分共二、 计算论证题(本部分共 5 个小题,每个小题个小题,每个小题 12 分,共分,共 60 分)分) 1.假设共有 5 个作业 J1、J2、J3、J4、J5,它们到达时刻分别是 0、2、2、5、6,服务时间分别是 3、10、5、6、2。采用高响应比优先调度算法,计算这些作业的平均周转时间和平均带权周转时间。参考答案: 1最开始达到的是 J1,此时系统的其他5 个作业还没有到达, 所以J1 开始投入执行。 在3 时执行完毕。此时,J2 等待了 1 秒
9、,J3 等待了 1 秒,J4、J5 还没有到达。响应比 =(等待时间+要求服务时间)/ 要求服务时间=1+等待时间/要求服务时间。J2 的响应比为 1+1/10=1.1。J3 的响应比 1+1/5=1.2。所以调度 J3 运行。 2J3 执行完毕,时间到了 8。J4、J5 此时都已经到达了。因而,剩下的 J2、J4、J5 的响应比如下:J2=1+6/10=1.6;J4=1+3/6=1.5;J5=1+2/2=2。所以,J5 被调度执行。 3J5 执行完毕,是在 10. 此时系统中仅剩两个作业 J2、J4。J2、J4 的响应比分别是 J2=1+8/10=1.8;J4=1+5/6=1.81。 所以,
10、调度 J4 执行。16 时执行完 J4,就轮到 J2 执行了。J2 在 26 时执行完毕。 综上,执行序列是 J1、J3、J5、J4、J2。 周转时间是作业从提交到完成的时间。 作业 J1 J2 J3 J4 J5 周转时间 3 24 6 11 4 平均周转时间=(3+24+6+11+4)/5=48/5=9.6 带权周转时间=周转时间/服务时间 所以平均带权周转时间=(3/3 + 24/10 +6/5 +11/6 +4/2)/5=1.72 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n
11、获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研4 2.某文件系统采用索引物理结构存放文件, 磁盘空间为 1000GB。 一个目录项可以存储 10 个盘块的地址,前 9 个为直接地址,最后一个为一级间址。若盘块的大小为 512B,则该文件系统最大能支持的文件大小是多少?参考答案:注意,磁盘是外存,不是内存,别混淆了。 一个目录项可以存储 10 个盘块,9 个直接地址支持的文件长度是9 512B = 4.5KB。而一个一级间址。题目指出,一个目录项可以存放 10 个盘块的地址,所以,一级间址可以存放 10 个目录项的地址。故而支持的最大文件长度为
12、 512B 9 + 10 512B=19 512B = 9.5KB 3.在请求分段存储系统中,每个段空间最大为 16KB。假定某个时段该用户的段表如下图所示。段号 起始地址 段长(B) 0 5K 3K 1 9K 600 2 12K 10K 3 试问: (1)逻辑地址 0xA92B 对应的物理地址是多少?解析这类题目,先看看段号(或请求分页系统的题目的页号)是否在内存中,若不在内存中,那么就是段故障了。若是在内存中,在看看段内地址(或者请求分页系统的题目对应的页内地址)有没有越界,要是越界了,发出越界中断。解析:转成二进制 1010 1001 0010 1011 ,前面两位表示段号,后面 14
13、位表示段内地址。那么,可以知道段号是 10B,也就是段号 2。段号 2 的起始地址为 12K,大小为 10KB。看看段内地址: 1010 1001 0010 1011 。 而第 2 段的最大段内地址是 10K, 利用快速写法写出 10K。就是 2 进制的 0010 10 00 0000 0000。可以看看,逻辑地址 0xA92B 的段内地址是1010 1001 0010 1011。可以看到该地址的段内地址部分(下划线部分)显然大于 10K。所以,越界了。(2)逻辑地址 0x071F 对应的物理地址是多少?解析:转换成 2 进制的 0000 0111 0001 1111。对应的段号是 0,起始地
14、址是 5K。接着看看块内地址部分有没有越界。 0000 0111 0001 1111 。 可以发现, 段内地址 1K2K 之间。 没有越界。 转换成物理地址,各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研5 计算一下如下: 0000 0111 0001 1111+ 0001 0100 0000 0000=0001 1011 0001 1111,换回 16 进制的 0x1B1F (3)逻辑
15、地址 0xE068 对应的物理地址是多少?解析:转换成 2 进制的 1110 0000 0110 1000。对应的段号是 3。但是段号是 3 的段并没有在内存中,所以发生了缺段中断了。 4.有一个请求页式虚拟存储系统。如果分配给某进程 3 个内存物理块,开始时内存中预装入第 1、2、3个页面,该进程的页面访问序列如下:1、2、4、2、6、2、1、5、6、1 (1)若采用最佳页面置换算法,缺页率为多少?解析:回顾一下最佳置换算法的概念,最佳置换算法是由 Belady 于 1966 年提出的一种理论上的算法。其所选择的被淘汰页面,将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。 页
16、面访问序列 1 2 4 2 6 2 1 5 6 1 内存页面 1 1 1 1 1 1 1 1 1 1 1 内存页面 2 2 2 2 2 2 2 5 5 5 内存页面 3 4 4 6 6 6 6 6 6 缺页 可以看到,发生了 5 次缺页。缺页率为 50%。 (2)若采用最近最少使用的页面置换算法 LRU,缺页率为多少?解析: 最近最少使用也叫做最近最久未使用算法。 注意 LRU 和 FIFO 是常考的页面置换算法, 一定得会,要不然可能就悲剧了! 页面访问序列 1 2 4 2 6 2 1 5 6 1 内存页面 1 1 1 1 1 6 6 6 5 5 5 内存页面 2 2 2 2 2 2 2 2
17、 6 6 内存页面 3 4 4 4 4 1 1 1 1 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研6 缺页 可以看到,发生了 7 次缺页,缺页率为 70%。 5.有 3 个进程 P1、P2、P3 总共需要资源的最大数目依次为、(均是互斥共享资源)。在 t 时刻 P1、P2、P3 正占用的资源数目依次是、;系统中资源 R1和 R2 的数量还各自剩余 3 个和 2 个;而且,进程 P1
18、正在申请 4 个资源 R1,2 个资源 R2;P2 正在申请 1 个资源 R1,1 个资源 R2;P3 正在申请 1 个资源 R1,2 个资源 R2。问:(1) 此刻系统是否处于安全状态?为什么?参考答案: 进程与资源情况 最大需求 A B 已获得的资源数 A B need A B P1 7 5 1 2 6 3 P2 3 3 1 1 2 2 P3 4 4 1 0 3 4 系统可用的 R1、R2 类资源=(3,2) 。P2 可以调度执行。执行完毕,系统可用的 R1、R2 类资源=(4,3) 。Need(P1)=(6,3),Need(P3)=(3,4)。系统已经无法继续执行了。所以系统并不安全。
19、(2) 此刻系统是否已经发生死锁?为什么? 解析:t 时刻虽然不安全,但是 P2 还是可以执行的。说明死锁还没有发生。这也说明了一个问题,不安全的状态不一定死锁。但是,死锁了,却一定是不安全状态。 三、 算法题(本部分共三个大题,第三、 算法题(本部分共三个大题,第 1、2 大题分别大题分别 14 分,第三大题分,第三大题 10 分,共计分,共计 40 分)分) 1.四个进程 P1 必须在 P2、P3 开始之前完成,P2、P3 必须在 P4 开始之前完成。而且 P2、P3 不能并发执行。试写出这四个进程的同步互斥算法。 (15 分)参考答案前趋图是一个常考的知识点,要会啊!交大好几年的真题里面
20、都有。连我本科上课的作业各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研7 也有,其实我本科没有布置过几次作业。 我们需要建立 4 个信号量 a,b,c,d, 然后一个供 P2、 P3 互斥的信号量 mutex。 所以画了下面的前趋图,两个进程之间的小箭头上的变量表示信号量。 Var a,b,c,d: semaphore:=0,0,0,0; /* 因为这几个信号量为 1 将唤醒其所在的箭头
21、后面的进程执行,而唤醒操作是由其所在的箭头前面的进程执行完了之后进行的。所以,初值设为 0。 */ mutex:semaphore:=1;/别搞成 0 了,要不然,两个进程都进行不下去了。互斥信号量一般初值为 1 begin parbegin P1:signal(a);signal(b);end; /* P1 执行完了,通知 P2、P3,告诉它们,它们可以开始了。 */ begin wait(a);wait(mutex);P2;signal(c);signal(mutex);end; /* P2 接到 P1 可以开始的通知,再捕获互斥信号量 mutex,就具备开始运行的条件了。执行完 P2,释
22、放互斥信号量 mutex,并通知 P4,我这边完成了。 */ begin wait(b);wait(mutex);P3;signal(d);signal(mutex);end; /* 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研8 P3 接到 P1 可以开始的通知,再捕获互斥信号量 mutex,就具备开始运行的条件了。执行完 P3,释放互斥信号量 mutex,并通知 P4,我这边完成了
23、。 */ begin wait(c); wait(d); P5; end; /* P4 等候 P2、P3 的“准许” ,接到 P2、P3 先后发出的“我执行完了,你可以开始了”的通知,具备开始运行的条件了。执行完 P4。进程序列就执行完毕了。 */ parend end 【注意】我注释成这样,是为了方便你们理解,你若是考研了也注释成这样,老师就傻眼了。你出了考场,告诉我你也注释成这样,那我就罪大了。所以,不要注释成这样,费时,老师也没时间看!【注意】我注释成这样,是为了方便你们理解,你若是考研了也注释成这样,老师就傻眼了。你出了考场,告诉我你也注释成这样,那我就罪大了。所以,不要注释成这样,费
24、时,老师也没时间看! 思考题 若是上面的程序中, wait(a);wait(mutex);P3;signal(c);signal(mutex);end; 与 wait(b);wait(mutex);P3;signal(d);signal(mutex);end; 中的 wait(a)和 wait(b)都放到 wait(mutex)的后面,这样行吗?为什么? 2.Alice 有一个私人邮箱 mbox,最多可以存放 N 封邮件。Alice 可以从该邮箱中读取邮件,且每读一封邮件该邮件就自动删除;其他用户都可以向该邮箱发送邮件。请设计 Alice 读邮件和其他用户发邮件操作的同步互斥算法。 (15 分
25、)参考答案:嗨,大家好,又轮到海哥的 PV 算法了。呵呵关于这类题型,我们就不吐槽了。就是读者写者问题的改编。所以,大家要特别注意读者写者问题了。道理明白越深,对我们越有好处。考研要是来一个,10 多分就有了。最多可以存放 N 封邮件,很像我们读者写者那样阅览室最多可以装 N 个人。 关于这个题目,开始读的时候,总觉得有点不清不楚的。也没有说互斥和同步在哪儿体现了。所以,我们补上了一句: Alice 读邮件的时候, 其他写者不让写。 其他写者给 Alice 发邮件的时候, Alice 不能读。就是互斥访问邮箱。当然,我们还定义了一下,比如说,一个人在给 Alice 发邮件的时候,其他人不能给各
26、个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研9 Alice 发邮件! 于是,从期末考试题目和解析第二章去找 Dtab 复制粘贴的干活: 解析:Var mutex,empty,mailcount:semaphore:=1,N,0; /*注意了,不要定义成下面这个! ! ! ! Writecount:integer:=0; 想象一下,若是我们这里也 P(Writecount)或者 V(Wri
27、tecount),写法对吗? 呵呵当然是不对的。PV 操作都是针对信号量的。一个整型的变量也 PV,这习惯不好啊! */ Begin Parbegin Reader:Begin /发邮件 repeat wait(empty); /* 给 Alice 发邮件之前,先看看人家的邮箱是不是满了。要是满了就得等,不然就白忙活了。 */ wait(mutex) ; /* 等待信号量,每个时刻,最多只能有一个人操作邮箱(我们假设是这样) */ 写邮件,写完了,给 Alice 发过去! Signal(mutex);/释放互斥信号 Signal(mailcount);/来信件了,Alice 的邮箱里多一封信
28、until false; End Reader: Begin/Alice 读邮件了 repeat 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研10 wait(mailcount);/有邮件,那么就申请互斥信号量,去读邮件 wait(mutex); /* 申请互斥信号量。注意,要是这一句和上面的 wait(mailcount)换一个位置,假如系统开始没有邮件,但是 Alice 申请到了
29、mutex 信号量。那么想给 Alice 发邮件就费劲了。弄到 empty 信号量很容易,但是死都弄不到互斥信号量啊! */ 读邮件, (读完系统自动删除) signal(empty); /* 系统删除邮件了,是不是要释放 empty 信号量啊?呵呵想想要是系统删除邮件,没有signal(empty), 那么 Alice 最多只能收到 N 封邮件, 之后给 Alice 发邮件的人就再也申请不到 empty信号量了。所以,这里要 signal(empty),千万别忘了。 */ signal(mutex) /写完了,释放写信号,若有人想写信给 Alice ,可以竞争 mutex 信号量,等待机会写
30、信了。 /其他写者可写 until false; End Parend End 【思考题】呵呵试着想想,要是可以同时有多个发给 Alice 信件的人,又该怎么写?【提示,这就很像期末考试 2004-2005 年的 Dtab 那个题了。呵呵很经典,要把握啊! 】 3.两个进程 P1、 P2 并发执行, 并用信号量 M1、 M2 分别实现对两个互斥共享资源 R1 和 R2 的互斥访问。这两个进程以什么次序执行会导致死锁?在不影响程序功能的情况下,请改写算法防止死锁,同时尽可能保持较高的资源利用率。 (10 分)程序如下:Var M1,M2:Semaphore=1,1;各个学校计算机/软件专业考研真
31、题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研11 begin parbegin P1 begin: wait(M1); access R1; wait(M2); access R1 and R2; signal(M1); signal(M2); end P2 begin: wait(M2); access R2; wait(M1); access R1; signal(M1); signal(M2); end pa
32、rend 参考答案: 1很明显,若进程 P1 执行 wait(M1)还没有 wait(M2)成功的时候,P2 若 wait(M2)成功,就死锁了。P1 在等待M2,P2 在等待 M1。2先让两个进程去争夺 M1,抢到 M1 的进程才给它抢 M2,这种方法解除了死锁,也保证了 P1、P2 两个进程谁先抢到 M1,都可以顺利得到 M2 而投入运行。目的就达到了。呵呵仰天大笑出门去,我辈岂是聪明人!笨的人习惯了,引以为豪啊!Var M1,M2:Semaphore=1,1; begin parbegin P1 begin: wait(M1); access R1; wait(M2); access R1 and R2; signal(M1); signal(M2); end P2 begin: wait(M1); wait(M2); access R2; access R1; signal(M1); signal(M2); end 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研