浙江大学计算机专业考博试题计算机软件及应用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）是最著名的进程同步问题，常用于检测进程同步机制。它描述了一组生产者与一组消费者，它们共享一个有界缓冲池，生产者向池中投入消息，消费者从中取得消息。生产者-消费者问题实际上是相互合作进程关系的一种抽象。例如，在输入时，输入进程是生产者，计算进程是消费者；在输出时，计算进程是生产者，打印进程是

15、消费者。因此，该问题具有很大实用价值。假定缓冲池中具有n个缓冲区，每个缓冲区存放一个消息，可利用互斥信号量mutex使诸进程对缓冲池实现互斥访问；利用资源信号量empty和full分别表示缓冲池中空缓冲区及满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从取走一个消息。生产者-消费者问题可描述如下：var mutex,empty,full:semaphore:=1,n,0; buffer:array0,n-1 of message; in,out:0,n-1:=0,0;begin parbegin producer:beg

16、inrepeat . . . producer a new message m; . . . P(empty); P(mutex); buffer(in):=m; in:=(in+1) mod n; V(mutex); V(full); until false end consumer:begin repeat P(full); P(mutex); m:=buffer(out); out:=(out+1) mod n; V(mutex); V(empty); consume message m; until false end parendend在生产者-消费者问题中应当注意：（1）在每个程序

17、中用于实现互斥的P(mutex)和V(mutex)必须成对出现。（2）对资源信号量empty和full的P、V操作同样需要成对出现，但它们分别处于不同的程序中，例如，P(empty)在计算进程中，而V(empty)则在打印进程中，计算进程因执行P(empty)而阻塞，则以后将由打印进程将它唤醒。（3）在每个程序中的P操作顺序不能颠倒，应先执行对资源信号量的P操作，然后再执行互斥信号量的P操作，否则可能引起进程死锁。3、写出可对文件和目录进行的操作。4、虚拟存储页面置换的几种算法。5、谈谈你对操作系统的设计和通用性的看法。6、举例说明cache在操作系统中的应用。6、微内核的优点，列举微内核操作

18、系统的特点和实例。微内核技术的主要优点：（1）统一的接口，在用户态和核心态之间无需进程识别；（2）可伸缩性好，能适应硬件更新和应用变化；（3）可移植性好，所有与具体机器特征相关的代码，全部隔离在微内核中，如果操作系统要移植到不同的硬件平台上，只需修改微内核中极少代码即可；（4）实时性好，微内核可以方便地支持实时处理；（5）安全可靠性高，微内核将安全性作为系统内部特性来进行设计，对外仅使用少量应用编程接口；（6）支持分布式系统，支持多处理器的体系结构和高度并行的应用程序；（7）真正面向对象的操作系统。由于操作系统核心常驻内存，而微内核结构精简了操作系统的核心功能，内核规模比较小，一些功能都移到了

19、外存上，所以微内核结构十分适合嵌入式的专用系统，对于通用性较广的系统，将使CPU的通信开销增大，从而影响到计算机的运行速度。7、什么叫系统调用？编写一段包含系统调用的程序，完成如下工作：打开一个文件，向文件中添加一个字符串，关闭该文件。 系统调用是操作系统提供给编程人员的唯一接口。利用系统调用，编程人员在源程序中动态请求和释放系统资源，调用系统中已有的功能来完成那些与机器硬件部分相关的工作以及控制程序的执行速度等。系统调用如同一个黑匣子，对使用者屏蔽了具体操作动作，只是提供了有关功能。有关文件系统的系统调用是用户经常使用的，包括文件的创建（create）、打开(open)、读(read)、写(

20、write)、关闭(close)等。下面是一个有关文件系统的系统调用的例子。main(argc,argv)int argc;char *argv;int fd1,fd2,fd3,n;char buf512,ch=n;fd1=open(argv1,0); /*打开argv1对应的文件，返回标识符fd1*/fd2=open(argv2,0); /*打开argv2对应的文件，返回标识符fd2*/fd1=create(argv3,0644); /*创建argv3对应的文件，返回标识符fd3*/while(n=read(fd1,buf,512)0) /*从fd1中读n0) /*从fd2中读n=512字节

21、入buf*/write(fd3,buf,n); /*将buf中n个字节写入fd3*/close(fd1); /*关闭文件*/close(fd2); /*关闭文件*/close(fd3); /*关闭文件*/体系结构1、 写出CPUtime公式，并给出如何减少CPUtime。 CPU时间的计算公式：CPUtime = *I*CPI :时钟周期，取决于硬件工艺和计算机组成； CPI:指令的平均时钟周期数，与计算机组成和指令系统有关； I:程序指令数，取决于机器指令系统和编译技术。2、 给出下列定义a、有哪几种数据竞争？b、什么是Load/Store机构？ 3、画出集中式共享存储和分布式存储的结构图，

22、并给出通信方式。 Ieyx|qh* 集中式共享存储器多处理器结构图：分布存储器多处理器结构图：通信方式：1、shared memory2、message passing计算理论2001年浙江大学春季计算机试题操作系统1、逻辑地址空间为32位，物理地址空间为24位，页大小为64K。计算理论原始递归函数的三个基本函数：2001年浙江大学秋季计算机试题操作系统1、 关于分页虚拟内存地址转换2、 为什么要引入“进程状态”，画出进程状态转换图。3、 块设备和字符设备的特点和区别。 4、 打开的文件，它的文件标识，保存在系统什么地方？为什么？体系结构1、 CPUtime公式及其理解，如何减少CPUtime

23、？ CPU时间的计算公式：CPUtime = *I*CPI :时钟周期，取决于硬件工艺和计算机组成； CPI:指令的平均时钟周期数，与计算机组成和指令系统有关； I:程序指令数，取决于机器指令系统和编译技术。2、 一段循环相关性分析。3、 DLX机器一段代码的数据竞争，结构竞争分析及其解决方法。4、 并行处理的两个障碍是什么？并行处理的两个障碍是：（1）在程序中可利用的并行性有限；（2）通信代价过高。5、 关于cache直接映射的实现细节。直接映射：主存中的每个信息块只能对应Cache中的一个特定块。计算理论1、a,b上递归枚举语言是否可数？证明。2、 L=a,b,c数目相同的语言是否CFL（

24、上下文无关语言），证明。3、 被2，3整除的非负整数的十进制表示的集合是否正则。4、证明：若L是递归语言，则它的补 也是递归语言。证明：若Turing机M = ( K，s，y，n)能够判定L，则Turing机M = ( K，s，y，n)能够判定 。此处，除了M 反转两种特殊停机状态y和n的作用以外，M与M是相同的，即定义如下M（w) = y 当且仅当 M（w) = n ，因此M能够判定 。2002年浙江大学春季计算机试题操作系统1、 处理机调度、内存分配和资源分配三者结合，以打印机为例（银行家算法）。2、 什么叫系统调用？编写一段包含系统调用的程序，完成如下工作：打开一个文件，向文件中添加一个

25、字符串，关闭该文件。3、 谈谈你对操作系统的设计和通用性的看法。4、 列举微内核操作系统的特点和实例。体系结构1、 CPU time的计算公式及减少它的措施。 CPU时间的计算公式：CPUtime = *I*CPI :时钟周期，取决于硬件工艺和计算机组成； CPI:指令的平均时钟周期数，与计算机组成和指令系统有关； I:程序指令数，取决于机器指令系统和编译技术。2、说明集中式多处理器和分布式多处理器体系结构的通信模型。（1）共享存储器通信模型对应与统一地址空间组织，因为这一统一的地址空间可用作隐含的数据通信机制，即直接用load、store共享变量即可。（2）消息传递模型：对应于多重地址空间组

26、织。这里处理器获得数据通信需要显式地通过传递消息来进行。3、数据相关分析。4、简答：数据相关、Amdahl定理、Cache主存映射方式。计算理论1、 什么是计算？计算理论研究的内容和意义是什么？为什么要使用计算的抽象模型？2、 请写出一个正则表达式，描述下面的语言：在字母表0，1上，不包含00字串且以1结尾。1011 0113、 为什么说能被2或者3整除的语言是正则的？4、5、 一个succ(n+1)的组合Turing机描述，说出它的作用。6、 什么是Turing机的停机问题？它是可判定的么？为什么？7、 证明这个问题不可判定：一个Turing机半判定的语言等于这样的一个语言，这个预言是w和w

27、的转置的连接。2003年浙江大学秋季计算机试题操作系统体系结构1、 写出计算机设计的三个原理计算机设计的定量定理：（1）Amdahl定律；（2）高频事件高速处理；（3）局部性原理2、 CPUtime公式，及如何减少CPUtime？ CPU时间的计算公式：CPUtime = *I*CPI :时钟周期，取决于硬件工艺和计算机组成； CPI:指令的平均时钟周期数，与计算机组成和指令系统有关； I:程序指令数，取决于机器指令系统和编译技术。3、 画出分布式多处理器的体系结构，并说明它的两种存储器体系及其对应的通信机制。分布式多处理器的体系结构如下：分布式存储器结构模型：1、Distributed sh

28、ared memory：shared memory2、multiple computers：Message passing 计算理论1、 L=ambmca2nb2n:m,nN,m,n1（1）写出它的文法（2）写出它对应的确定性下推自动机2、 作出判定0n1n2n（n0）的图灵机。3、 用泵定理证明a(n+1)2不是上下文无关文法（a有一个上标为（n+1）的平方）4、 L为上下文无关文法，R为正则文法，判断L是R的子集是否可判定，并说明理由。面向对象1、 名词解释封装 永久对象 多态 继承（1）封装：就是把对象的属性和操作结合成一个独立的系统单位，并尽可能隐蔽对象的内部细节。（2）永久对象：是指

29、生存期可以超越程序的执行时间而长期存在的对象。（3）多态：在计算机语言学中，多态性的一般含义是一个命名在不同的语境下有不同的语义。在面向对象技术中，对象的多态性通常是指一般特殊结构中对象所体现的多态性，即在一般类中定义的属性或操作被特殊类继承之后，可以具有不同的数据类型或表现出不同的行为。（4）继承：特殊类拥有其一般类的全部属性与操作，称为特殊类对一般类的继承。2、 做出收款机的UseCase和交互图3、 判断一种OOA好坏的标准4、 说明OOA的过程5、 UML的作用及它所使用的图6、 做出一个监控系统的对象图2004年浙江大学春季计算机试题操作系统1、关于硬件、操作系统、实用程序、用户应用程序的层级关系图。2、剥夺式内核与非剥夺式内核的异同特点。体系结构1、8KBCache，块大小32B，采用直接映像，数据字为32位，地址为34位，问Block Offset，index，tag各为多少位？2、循环代码如下：For (I = 1; I1，L2= ambncp：n不等于p且m、n、p1 （2）证明语言a，b，c* -(L1UL2)不是上下文无关的。