浙江大学计算机专业考博试题计算机软件及应用it计算机专业资料.doc
《浙江大学计算机专业考博试题计算机软件及应用it计算机专业资料.doc》由会员分享,可在线阅读,更多相关《浙江大学计算机专业考博试题计算机软件及应用it计算机专业资料.doc(128页珍藏版)》请在三一办公上搜索。
1、2000年春季浙江大学计算机考博试题操作系统一、 非抢占式系统和抢占式操作系统的区别,实时OS为何要采用抢占式系统?二、 按缺页率大小排列下述算法1、 LRU 2、FIFO 3、SECOND CHANGE 4、OPTIMAL 顺序算法Belady异常1OPTIMALNo2LRUNo3SECOND CHANGEYes4FIFOYes三、 进程进入就绪队列后的等待时间+运行时间=周转时间,现有三个进程:进程进入队列时间(s)执行时间(s)P108P20.44P3111、 对非抢占式系统,若采用最短任务优先,请计算三个进程的平均周转时间。采用最短任务优先算法时,进程运行情况如下:进程进入队列时间(s
2、)开始时间(s)执行时间(s)结束时间(s)周转时间(s)P100888P20.4941312.6P318198三个进程的平均周转时间=(8+12.6+8)/3=9.53(s)注意:带权周转时间=周转时间/运行时间2、 若CPU空等1s后再执行进程,请计算三个进程的平均周转时间。进程进入队列时间(s)开始时间(s)执行时间(s)结束时间(s)周转时间(s)P10681414P20.42465.4P311121三个进程的平均周转时间=(14+5.4+1)/3=6.8(s)四、 有三个作业对空间要求分别为250K,412K,523K,342K,现内存分区大小为200K,300K,400K,500K
3、,600K,若分别采用FIRST-FIT,BEST-FIT和WORST-FIT分配结果如何?1、FIRST-FIT:从头到尾搜索整个有效空间,找到第1个满足条件的存储块时,即返回。250K作业装到300K内存分区412K作业装到500K内存分区523K作业装到600K内存分区342K作业装到400K内存分区2、BEST-FIT:搜索整个有效空间,找出满足条件的存储块中,最小的一个,返回。250K作业装到300K内存分区412K作业装到500K内存分区523K作业装到600K内存分区342K作业装到400K内存分区3、WORST-FIT:搜索整个有效空间,找出满足条件的存储块中,最大的一个,返回
4、。(采用这种策略,是考虑到,被选中的存储块割去所申请的长度后,留下的部分还相对较大,比BEST-FIT算法留下的部分更有用)250K作业装到600K内存分区412K作业装到500K内存分区523K作业暂时等待342K作业装到400K内存分区五、 若一个系统有4个同样的资源,可供三个进程共享,每个进程最多占用2个资源,根据进程死锁的四个条件,说明此系统不会产生死锁。答:如果系统发生死锁,必然是系统中的3个进程都占用了1个资源,然后申请另外1个资源。因为系统中共有4个资源,必然会有一个进程得到2个资源,则这个进程不再需要更多的资源,它必然会执行完,然后释放所有的资源,这样就不会导致死锁。六、 某个
5、操作系统共支持5000个用户,若通过对用户的权限和文件属性的控制来实现只有其中4990个用户可以访问文件DEVLIST,可以采用两种控制策略,请比较其区别。答:在UNIX中有两种控制策略可以实现:1、 建立一张包含所有4990个用户名字的存取控制表;2、 把所有4990个用户放入一个组中,并设置这个组的存取权限。由于这些用户组受到系统限制,这个方案不一定总能实现比UNIX方案更有效的保护方案:规定所有的用户都能存取文件信息,除非他们的名字出现在没有存取权限的存取控制表中。据此,可以把余下的10个用户的名字放入该存取控制表中,但是他们没有给予任何存取权限。体系结构一、1、写出三条计算机设计的定量
6、定理。2、若CACHE速度比内存高10倍,若内存利用率是90%,请问系统的加速比为多少?1、计算机设计的定量定理:(1)Amdahl定律;(2)高频事件高速处理;(3)局部性原理2、系统加速比=1/(1-10%)+10%/10)=9.09二、CPU的操作数有三种存储方式,是区别不同体系计算机的重要标志。1、是哪三种存储方式?2、对于C=A+B,请写出三种方式的实现程序。CPU的操作数有三种存储方式:1、堆栈结构操作数是隐含在栈顶,首先要用压栈指令将操作数从内存压入栈顶,运算结果也在栈顶,要用退栈指令弹回内存。根据这种结构,只有PUSH和POP指令才能访问存储器。这种结构完成上述操作需如下指令:
7、指令格式: 操作指令:PUSH A存储器操作数 PUSH APUSH B存储器操作数 PUSH BADD ADDPOP C存储器操作数 POP C2、累加器结构有一个操作数是隐含在累加器中而另一个是在存储器中的,总操作数只有两个,完成上述运算只要三条指令。指令格式: 操作指令:LOAD A存储器操作数 LOAD AADD B存储器操作数 ADD BATORE C存储器操作数 STORE C3、寄存器结构。根据操作数的位置有两种情况,第一是ALU运算的操作数都在寄存器中的L/S结构;另一种情况操作数部分在寄存器,部分在存储器中。(1)指令格式: 操作指令:LOAD R1 A存储器操作数 LOAD
8、 R1,ALOAD R2 B存储器操作数 LOAD R2,BADD R3 R1 R2 ADD R3,R1,R2STORE R3 C存储器操作数 STORE R3,C(2)指令格式: 操作指令:LOAD R1 A存储器操作数 LOAD R1,AADD R1 B存储器操作数 ADD R1,BSTORE R1 C存储器操作数 STORE R1,C三、1、流水线中结构、数据、控制竞争产生的原因。(1)结构竞争:由资源冲突引起。当多条指令进入流水线后,硬件不能支持所有可能的指令组合形式同时重叠执行。(2)数据竞争:由指令间数据相关而引起。某条指令的执行依赖于前面指令的执行结果,而指令的流水重叠操作使当前
9、指令对数据使用时间提前了,而此时前面指令的执行结果还没有完成。(3)控制竞争:由指令指针PC值的改变而引起。流水线中出现条件转移及其它要改变PC指针的指令都将改变流水线中的后继指令。2、写出有停顿周期的流水线系统的性能公式。流水线停顿(stall):若 i 指令引起竞争,在 I 指令之前进入流水线的指令继续执行,而在 I 指令之后进入流水线或尚未进入流水线的指令停下来等待竞争消除。CPIun CPIunSpeedup = - = - CPIp 1+流水线stall周期四、1、什么是ILP?2、ILP的必要性和实现技术。1、指令之间可重叠执行性称为指令级并行性(Instruction Paral
10、lelism-ILP)2、要提高计算机的性能,就要进一步降低CPI,就必须挖掘指令间存在的不相关性和并行处理能力。为此,我们必须拓宽现有的流水线思想,采取一些新的更高的技术,充分增加和利用指令间的并行性。实现技术主要有:循环展开、超标量流水线、超级流水线、超长指令字和软件流水、路径调度等。五、某cache容量为8KBytes,块大小为32Bytes,字节为64Bits,地址长度为32Bits,对于直接映像系统,请分别写出构成地址的索引(INDEX)、标志(TAG)和块地址的长度。六、说明并行计算面临的两大障碍。并行计算面临的两大障碍:1、在程序中可利用的并行性有限;2、通信代价过高。计算理论一
11、、1、根据图灵机理论,说明现代计算机系统的理论基础。图灵机装置由下面几个部分组成:一个无限长的纸带,一个读写头,内部状态,还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。图灵机只要根据每一时刻读写头读到的信息和当前的内部状态进行查表可以确定它下一时刻的内部状态和输出动作了。图灵机在理论上能模拟现代数字计算机的一切运算,可视为现代数字计算机的数学模型。实际上,一切可计算函数都等价于图灵机可计算函数,而图灵机可计算函数类又等价于一般递归函数类。2、说明按乔姆斯基分类,语言、语法、自动机的关系。二、定义停机谓词H(X,Y)如下:三、1、证明递归集都是递
12、归可枚举集。 2、举例属于递归可枚举集但不是递归集的集合,并证明之。递归可枚举集: 可数集合S被称为递归可枚举的, 如果存在生成S的元素的算法. 等价定义:可数集合S被称为递归可枚举的, 如果有一个图灵机, 在给定S的一个元素作为输入的时候总是停机, 并在给定的输入不属于S的时候永不停机.递归集: 可数集合S被称为递归的, 如果存在能够在有限步骤内判定任意给定元素是否属于S的算法.四、1、证明L=(a,b)*|a,b的个数相同为上下文无关语言。选取字符串,s=uvxyz1)当v和y都只含有一种符号时,这时字符串不可能含有个数相同的a、b。2)当v或者y含有一种以上符号时, 2、并证明其不是正则
13、的。2000年秋季浙江大学计算机试题操作系统1、产生死锁的必要条件。产生死锁的必要条件如下:(1)互斥条件:进程所竞争的资源必须被互斥使用。(2)占有并等待条件:当前已拥有的进程,仍能申请新的资源;而且,当该进程因新的资源被其他进程占用而阻塞时,它对自己已获得的资源仍保持不放。(3)非抢占条件:进程已获得的资源,只能在使用完时自行释放。(4)循环等待条件:存在一个至少包含两个进程的循环等待链,链中的每个进程都正在等待下一个进程所占有的资源。解决死锁问题常用的措施有如下几种:(1)死锁的预防:通过事先破坏死锁产生的必要条件来防止死锁的发生。(2)死锁的避免:在进程申请资源时,通过安全性检查以决定
14、是否可以分配相应资源,避免系统进入不安全状态,防止死锁的发生。(3)死锁的检测与解除:系统通过死锁检测程序来判断是否有进程已进入死锁状态,如果有,则通过撤销某些死锁进程或者剥夺某些进程的资源来解除死锁现象。2、写出生产者和消费者的互斥程序(书上的例子)。生产者-消费者问题(producer-consumer)是最著名的进程同步问题,常用于检测进程同步机制。它描述了一组生产者与一组消费者,它们共享一个有界缓冲池,生产者向池中投入消息,消费者从中取得消息。生产者-消费者问题实际上是相互合作进程关系的一种抽象。例如,在输入时,输入进程是生产者,计算进程是消费者;在输出时,计算进程是生产者,打印进程是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 浙江大学 计算机专业 试题 计算机软件 应用 it 资料
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-3432847.html