浙江大学计算机专业考博试题计算机软件及应用it计算机专业资料.doc

2000年春季浙江大学计算机考博试题操作系统一、 非抢占式系统和抢占式操作系统的区别，实时OS为何要采用抢占式系统？二、 按缺页率大小排列下述算法1、 LRU 2、FIFO 3、SECOND CHANGE 4、OPTIMAL 顺序算法Belady异常1OPTIMALNo2LRUNo3SECOND CHANGEYes4FIFOYes三、 进程进入就绪队列后的等待时间+运行时间=周转时间，现有三个进程：进程进入队列时间（s）执行时间（s）P108P20.44P3111、 对非抢占式系统，若采用最短任务优先，请计算三个进程的平均周转时间。采用最短任务优先算法时，进程运行情况如下：进程进入队列时间（s）开始时间（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，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：搜索整个有效空间，找出满足条件的存储块中，最大的一个，返回。（采用这种策略，是考虑到，被选中的存储块割去所申请的长度后，留下的部分还相对较大，比BEST-FIT算法留下的部分更有用）250K作业装到600K内存分区412K作业装到500K内存分区523K作业暂时等待342K作业装到400K内存分区五、 若一个系统有4个同样的资源，可供三个进程共享，每个进程最多占用2个资源，根据进程死锁的四个条件，说明此系统不会产生死锁。答：如果系统发生死锁，必然是系统中的3个进程都占用了1个资源，然后申请另外1个资源。因为系统中共有4个资源，必然会有一个进程得到2个资源，则这个进程不再需要更多的资源，它必然会执行完，然后释放所有的资源，这样就不会导致死锁。六、 某个操作系统共支持5000个用户，若通过对用户的权限和文件属性的控制来实现只有其中4990个用户可以访问文件DEVLIST，可以采用两种控制策略，请比较其区别。答：在UNIX中有两种控制策略可以实现：1、 建立一张包含所有4990个用户名字的存取控制表；2、 把所有4990个用户放入一个组中，并设置这个组的存取权限。由于这些用户组受到系统限制，这个方案不一定总能实现比UNIX方案更有效的保护方案：规定所有的用户都能存取文件信息，除非他们的名字出现在没有存取权限的存取控制表中。据此，可以把余下的10个用户的名字放入该存取控制表中，但是他们没有给予任何存取权限。体系结构一、1、写出三条计算机设计的定量定理。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指令才能访问存储器。这种结构完成上述操作需如下指令：指令格式： 操作指令：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 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）数据竞争：由指令间数据相关而引起。某条指令的执行依赖于前面指令的执行结果，而指令的流水重叠操作使当前指令对数据使用时间提前了，而此时前面指令的执行结果还没有完成。（3）控制竞争：由指令指针PC值的改变而引起。流水线中出现条件转移及其它要改变PC指针的指令都将改变流水线中的后继指令。2、写出有停顿周期的流水线系统的性能公式。流水线停顿(stall)：若 i 指令引起竞争，在 I 指令之前进入流水线的指令继续执行，而在 I 指令之后进入流水线或尚未进入流水线的指令停下来等待竞争消除。CPIun CPIunSpeedup = - = - CPIp 1+流水线stall周期四、1、什么是ILP？2、ILP的必要性和实现技术。1、指令之间可重叠执行性称为指令级并行性（Instruction Parallelism-ILP)2、要提高计算机的性能，就要进一步降低CPI，就必须挖掘指令间存在的不相关性和并行处理能力。为此，我们必须拓宽现有的流水线思想，采取一些新的更高的技术，充分增加和利用指令间的并行性。实现技术主要有：循环展开、超标量流水线、超级流水线、超长指令字和软件流水、路径调度等。五、某cache容量为8KBytes，块大小为32Bytes，字节为64Bits，地址长度为32Bits，对于直接映像系统，请分别写出构成地址的索引（INDEX）、标志（TAG）和块地址的长度。六、说明并行计算面临的两大障碍。并行计算面临的两大障碍：1、在程序中可利用的并行性有限；2、通信代价过高。计算理论一、1、根据图灵机理论，说明现代计算机系统的理论基础。图灵机装置由下面几个部分组成：一个无限长的纸带，一个读写头，内部状态，还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。图灵机只要根据每一时刻读写头读到的信息和当前的内部状态进行查表可以确定它下一时刻的内部状态和输出动作了。图灵机在理论上能模拟现代数字计算机的一切运算，可视为现代数字计算机的数学模型。实际上，一切可计算函数都等价于图灵机可计算函数，而图灵机可计算函数类又等价于一般递归函数类。2、说明按乔姆斯基分类，语言、语法、自动机的关系。二、定义停机谓词H(X,Y)如下：三、1、证明递归集都是递归可枚举集。  2、举例属于递归可枚举集但不是递归集的集合，并证明之。递归可枚举集: 可数集合S被称为递归可枚举的, 如果存在生成S的元素的算法. 等价定义:可数集合S被称为递归可枚举的, 如果有一个图灵机, 在给定S的一个元素作为输入的时候总是停机, 并在给定的输入不属于S的时候永不停机.递归集: 可数集合S被称为递归的, 如果存在能够在有限步骤内判定任意给定元素是否属于S的算法.四、1、证明L=（a，b）*|a，b的个数相同为上下文无关语言。 选取字符串，s=uvxyz1）当v和y都只含有一种符号时，这时字符串不可能含有个数相同的a、b。2）当v或者y含有一种以上符号时， 2、并证明其不是正则的。2000年秋季浙江大学计算机试题操作系统 1、产生死锁的必要条件。 产生死锁的必要条件如下：（1）互斥条件：进程所竞争的资源必须被互斥使用。（2）占有并等待条件：当前已拥有的进程，仍能申请新的资源；而且，当该进程因新的资源被其他进程占用而阻塞时，它对自己已获得的资源仍保持不放。（3）非抢占条件：进程已获得的资源，只能在使用完时自行释放。（4）循环等待条件：存在一个至少包含两个进程的循环等待链，链中的每个进程都正在等待下一个进程所占有的资源。解决死锁问题常用的措施有如下几种：（1）死锁的预防：通过事先破坏死锁产生的必要条件来防止死锁的发生。（2）死锁的避免：在进程申请资源时，通过安全性检查以决定是否可以分配相应资源，避免系统进入不安全状态，防止死锁的发生。（3）死锁的检测与解除：系统通过死锁检测程序来判断是否有进程已进入死锁状态，如果有，则通过撤销某些死锁进程或者剥夺某些进程的资源来解除死锁现象。2、写出生产者和消费者的互斥程序（书上的例子）。 生产者-消费者问题（producer-consumer）是最著名的进程同步问题，常用于检测进程同步机制。它描述了一组生产者与一组消费者，它们共享一个有界缓冲池，生产者向池中投入消息，消费者从中取得消息。生产者-消费者问题实际上是相互合作进程关系的一种抽象。例如，在输入时，输入进程是生产者，计算进程是消费者；在输出时，计算进程是生产者，打印进程是消费者。因此，该问题具有很大实用价值。假定缓冲池中具有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:beginrepeat . . . 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）在每个程序中用于实现互斥的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、微内核的优点，列举微内核操作系统的特点和实例。微内核技术的主要优点：（1）统一的接口，在用户态和核心态之间无需进程识别；（2）可伸缩性好，能适应硬件更新和应用变化；（3）可移植性好，所有与具体机器特征相关的代码，全部隔离在微内核中，如果操作系统要移植到不同的硬件平台上，只需修改微内核中极少代码即可；（4）实时性好，微内核可以方便地支持实时处理；（5）安全可靠性高，微内核将安全性作为系统内部特性来进行设计，对外仅使用少量应用编程接口；（6）支持分布式系统，支持多处理器的体系结构和高度并行的应用程序；（7）真正面向对象的操作系统。由于操作系统核心常驻内存，而微内核结构精简了操作系统的核心功能，内核规模比较小，一些功能都移到了外存上，所以微内核结构十分适合嵌入式的专用系统，对于通用性较广的系统，将使CPU的通信开销增大，从而影响到计算机的运行速度。7、什么叫系统调用？编写一段包含系统调用的程序，完成如下工作：打开一个文件，向文件中添加一个字符串，关闭该文件。 系统调用是操作系统提供给编程人员的唯一接口。利用系统调用，编程人员在源程序中动态请求和释放系统资源，调用系统中已有的功能来完成那些与机器硬件部分相关的工作以及控制程序的执行速度等。系统调用如同一个黑匣子，对使用者屏蔽了具体操作动作，只是提供了有关功能。有关文件系统的系统调用是用户经常使用的，包括文件的创建（create）、打开(open)、读(read)、写(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中读n<=512字节入buf*/write(fd3,buf,n); /*将buf中n个字节写入fd3*/write(fd3,&ch,1); /*将换行符号写入fd3*/while(n=read(fd2,buf,512)>0) /*从fd2中读n<=512字节入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、画出集中式共享存储和分布式存储的结构图，并给出通信方式。 Ieyx|qh* 集中式共享存储器多处理器结构图：分布存储器多处理器结构图：通信方式：1、shared memory2、message passing计算理论2001年浙江大学春季计算机试题操作系统1、逻辑地址空间为32位，物理地址空间为24位，页大小为64K。计算理论原始递归函数的三个基本函数：2001年浙江大学秋季计算机试题操作系统1、 关于分页虚拟内存地址转换2、 为什么要引入“进程状态”，画出进程状态转换图。3、 块设备和字符设备的特点和区别。 4、 打开的文件，它的文件标识，保存在系统什么地方？为什么？体系结构1、 CPUtime公式及其理解，如何减少CPUtime？ CPU时间的计算公式：CPUtime = *I*CPI :时钟周期，取决于硬件工艺和计算机组成； CPI:指令的平均时钟周期数，与计算机组成和指令系统有关； I:程序指令数，取决于机器指令系统和编译技术。2、 一段循环相关性分析。3、 DLX机器一段代码的数据竞争，结构竞争分析及其解决方法。4、 并行处理的两个障碍是什么？并行处理的两个障碍是：（1）在程序中可利用的并行性有限；（2）通信代价过高。5、 关于cache直接映射的实现细节。直接映射：主存中的每个信息块只能对应Cache中的一个特定块。计算理论1、a,b上递归枚举语言是否可数？证明。2、 L=a,b,c数目相同的语言是否CFL（上下文无关语言），证明。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、 什么叫系统调用？编写一段包含系统调用的程序，完成如下工作：打开一个文件，向文件中添加一个字符串，关闭该文件。3、 谈谈你对操作系统的设计和通用性的看法。4、 列举微内核操作系统的特点和实例。体系结构1、 CPU time的计算公式及减少它的措施。 CPU时间的计算公式：CPUtime = *I*CPI :时钟周期，取决于硬件工艺和计算机组成； CPI:指令的平均时钟周期数，与计算机组成和指令系统有关； I:程序指令数，取决于机器指令系统和编译技术。2、说明集中式多处理器和分布式多处理器体系结构的通信模型。（1）共享存储器通信模型对应与统一地址空间组织，因为这一统一的地址空间可用作隐含的数据通信机制，即直接用load、store共享变量即可。（2）消息传递模型：对应于多重地址空间组织。这里处理器获得数据通信需要显式地通过传递消息来进行。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的转置的连接。2003年浙江大学秋季计算机试题操作系统体系结构1、 写出计算机设计的三个原理计算机设计的定量定理：（1）Amdahl定律；（2）高频事件高速处理；（3）局部性原理2、 CPUtime公式，及如何减少CPUtime？ CPU时间的计算公式：CPUtime = *I*CPI :时钟周期，取决于硬件工艺和计算机组成； CPI:指令的平均时钟周期数，与计算机组成和指令系统有关； I:程序指令数，取决于机器指令系统和编译技术。3、 画出分布式多处理器的体系结构，并说明它的两种存储器体系及其对应的通信机制。分布式多处理器的体系结构如下：分布式存储器结构模型：1、Distributed shared 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）永久对象：是指生存期可以超越程序的执行时间而长期存在的对象。（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; I<100; I = I + 1) A I = B I + C I ; /* S1 */B I = A I + D I ; /* S2 */A I + 1 = A I + E I ; /* S3 */2.1请分析指令间的相关性（输出相关、反相关、真相关），并且注明该相关是否循环传递（Loop-carried）。指令间的相关性分类：1、 数据相关数据相关（也叫真数据相关），如果下面的条件之一成立，则指令j数据相关于指令i：（1）指令i产生的结果为j引用；（2）指令j数据相关于指令k，而指令k数据相关于指令i。2、 名字相关当两条指令使用同一个寄存器或是同一个内存地址时，即发生了名字昂管，有名字相关的指令之间不存在数据流。对于指令i和j，它们之间可能存在名字相关有两种类型：（1）反相关，指令j写一个寄存器或一个内存单元，而指令i则去读该寄存器或内存单元，且i的执行在前。此时必须保证指令原来的顺序不变，以确保i能读到正确的值。（2）输出相关，指令i和j对同一个寄存器或内存地址执行写操作，这种操作顺序必须正确，使最后写入的值由j决定。3、 控制相关控制相关决定了跟分支指令有关的指令的执行顺序，即非分支指令只能在该执行的时候才能执行。数据冲突可以按照指令中读写访问的顺序分为三类：（1）写读冲突（RAW）：如果j想在i写之前去读数据，读出来的将是旧值。这是最常见发生的一种冲突，对应于真数据相关，要保证执行结果的正确就必须保证j在i之后读取数据。（2）写写冲突（WAW）：当j在i写入数据之前写同一个单元（寄存器或内存地址）时就会发生写写冲突。如果写操作以错误的顺序执行，会导致指令结束后的操作数是错误的，在这里操作数本应是j写入的值，但如果j先写，则指令结束后操作数结果为i写入的值。这种冲突对应于输出相关。（3）读写冲突（WAR）：当j先于i改写了i的操作数，则i读的时候将读入一个错误的值。这种冲突是由反相关引起的。2.2该循环是否可以并行？如果不是，请重写该循环使之成为并行的。3、举例转移延迟调度的三种策略及其条件与何时有效。4、流水线概念，流水线加速比，流水线三类竞争的产生与解决。流水线技术就是指令重叠执行技术，达到加快运算速度的目的由于存在三种流水线竞争：结构竞争、数据竞争、控制竞争，导致流水线性能降低，不能运作在理想的重叠状态，需要插入停顿周期，从而使流水线性能降低。1、结构竞争：资源冲突（不支持某些指令组合）；2、数据竞争：后续指令的执行依赖于前面指令的执行结果；3、控制竞争：因转移或修改PC引起的竞争。5、CPU时间的计算公式，如何减小CPU时间。 CPU时间的计算公式：CPUtime = *I*CPI :时钟周期，取决于硬件工艺和计算机组成； CPI:指令的平均时钟周期数，与计算机组成和指令系统有关； I:程序指令数，取决于机器指令系统和编译技术。计算理论面向对象1、 UML的各种图及用途。2、 顺序图与活动图的特点。3、 服务的详细说明方法。4、 电梯运行的状态图。5、 图书销售管理系统建模，并给出付款的Use Case。6、 OOA产生的系统模型的组成。7、 OOA文档的组成。OOA文档的组成：（1）需求模型：定义了系统的需求；（2）基本模型：是OOA结果的核心；（3）辅助模型：用于加强模型表示；（4）模型规约：是对模型语义的详细定义与解释。2004年浙江大学秋季计算机试题操作系统1、 关于临界区、页面置换算法、银行家算法是属于死锁避免、分段存储管理等。2、 谈谈对嵌入式操作系统（与一般的通用操作系统的区别）的看法。3、假如一个单级目录结构允许任意长度的文件名，能否用它来模拟树型目录结构，如果能，请说明如何模拟并指明两者的一一对应关系；如果不能，请说明理由。体系结构1、谈谈硬件投机技术与重构序寄存器的作用，并谈谈它与tomasulo技术的区别。硬件投机技术的作用：（1）便于扩大投机指令的范围例如，程序很难在编译时明确存储器访问的地址，而基于硬件的投机技术是在程序动态执行时确定访问存储器地址的，因而有利于扩大投机指令的范围；（2）在硬件转移预测上实现的基于硬件投机技术比在软件转移预测上实现的基于编译投机的效率更高。因为硬件转移预测的正确率要高于静态转移预测。（3）基于硬件的投机能保证完全精确的中断处理模式，即使是投机产生中断也是一样。其理由将进一步介绍；（4）基于硬件的投机不需要补偿或纪录代码；（5）采用动态调度的基于硬件投机技术在体系结构的不同实现方案中可以不用不同的编译器就能保证其性能。基于编译的投机和调度通常在体系结构的不同实现机种中，要求对代码序列作适当调整才能确保其性能不变，通常老的程序代码的性能会低一些。重构序缓存的作用：（1）相当于一个额外虚拟寄存器，相当于Tomasulo算法中的保存站、Load buffer和store buffer等的功能。（注意，在基于Tomasulo的投机硬件中，取消了Store buffer部件)。（2）重组缓存在指令完成操作之后直到交付之前这段时间里保存该指令的结果，作为其它指令操作数的源，类似于Tomasulo算法中保留站作用。不同之处在于：Tomasulo算法中在Write Result这一拍中就可以更新register file,而这里只能等到进入Commit节拍才能更新register file。1、 关于性能加速比的问题。2、 记分牌动态调度技术的有关填写各记分牌状态的大题。（书上画的三张基本表）在动态调度流水线中，指令在发射阶段都是顺序的（顺序发射），但在第二个阶段（读操作数）却可以停顿或提前执行，即进入乱序执行阶段。记分板机制正是在资源部件充足，没有数据相关存在的前提下，允许指令乱序执行的一种技术。其命名取自于CDC6600，正是该机器引入了记分板机制。采用记分板机制的目的，是在没有资源冲突的前提下，使每一条指令尽可能早执行，以保持每一个时钟周期执行一条指令的速率，即当某条将要执行的指令被停顿时，其他没有相关于任何执行着或被停顿指令的指令应能够接着发射并执行。每条指令在执行过程中经历4个阶段：（1）发射（Issue）：如果指令所用的功能部件正好空闲且没有其他活动的指令与它抢用同一个目标寄存器，那么记分板就把指令发射至该功能部件并更新自己内部的数据结构。通过确保无其他活动的功能部件与其争用同一个目标寄存器，可以杜绝写写冲突的出现。如果存在资源冲突或写写冲突，必须停止发射任何后继指令，直至冲突解除。（2）读操作数（Read）：记分板监视源操作数的可用情况，如果没有以前发射了的活动指令去写该操作数，或是存放该操作数的寄存器此刻正被某个活动的功能部件写入，那么源操作数是可用的。一旦源操作数可用，记分板便会通知相应功能部件读取该操作数并开始执行。通过这种方法，记分板解决了写读冲突。（3）执行：功能部件在得到操作数之后即开始执行。当执行结束，结果产生之后，便会通知记分板。（4）写回结果：一旦记分板知道功能部件已经执行完成，就会检查是否有读写冲突；若有读写冲突则停顿完成的指令。记分板由3部分构成：（1）指令状态表：指示出指令所处的是4个阶段中的哪一个。（2）功能部件状态表：指出功能部件的状态，每一个功能部件对应有9个字段：Busy：指示功能部件是否正在使用；Op：使用该部件的操作符（如“加”或“减”）；Fi：目标寄存器；Fj，Fk：源寄存器；Qj，Qk：产生源寄存器Fj，Fk的功能部件；Rj，Rk：标志Fj，Fk是否准备好的标志位。（3）寄存器结果状态表：指出哪一个功能部件将写入这个寄存器，如果没有指令写这个寄存器，则这个字段置为空。计算理论1、（1）构造上下文无关文法来生成语言L1=ambncp：m不等于n且m、n、p>1，L2= ambncp：n不等于p且m、n、p>1 （2）证明语言a，b，c* -(L1UL2)不是上下文无关的。