算机系统结构实验指导书(正式版).doc

计 算 机 系 统 结 构湖南工业大学计算机与通信学院实验指导书目 录实验一 WinDLX模拟器与DLX指令的使用2一实验目的2二实验平台2三预备知识2四实验内容和步骤2五实验程序2六实验报告要求3实验二 流水线中的结构相关4一实验目的：4二实验平台4三预备知识4四实验内容和步骤4五实验程序5六实验报告要求5实验三 流水线中的数据相关6一 实验目的6二 实验平台6三 预备知识6四 实验内容和步骤6五 实验程序6六 实验报告要求7实验四 LRU页面置换算法模拟8一、实验目的8二、实验平台8三、预备知识8四、实验内容与步骤10五、实验程序11六 实验报告要求14附录：WinDLX 教程15实验一 WinDLX模拟器与DLX指令的使用1 实验目的1. 熟练掌握WinDLX模拟器的操作和使用，熟悉DLX指令集结构及其特点；2. 加深对计算机流水线基本概念的理解；3. 了解DLX基本流水线各段的功能以及基本操作；2 实验平台WinDLX模拟器3 预备知识1. WinDLXWinDLX模拟器是一个图形化、交互式的DLX流水线模拟器，能够演示DLX流水线是如何工作的。该模拟器可以装载DLX汇编语言程序（后缀为“.s”的文件），然后单步、设断点或是连续执行该程序。CPU的寄存器、流水线、I/O和存储器都可以用图形表示出来，以形象生动的方式描述DLX流水线的工作过程。模拟器还提供了对流水线操作的统计功能，便于对流水线进行性能分析。 有关WinDLX的详细介绍，见附录（WinDLX教程）。2. 熟悉WinDLX指令集和WinDLX源代码的编写4 实验内容和步骤用WinDLX模拟器执行求最大公倍数程序gcm.s分别以步进、连续、设置断点的方式运行程序，观察程序在流水线中的执行情况，观察CPU中寄存器和存储器的内容。熟练掌握WinDLX的操作和使用。注意：gcm.s中调用了input.s中的输入子程序。load程序时，要两个程序一起装入（都select后再点击load）。如：给出两组数6、3和6、1，分别在main+0x8(add r2, r1, r0)、gcm.loop（seg r3,r1,r2）和result+0xc(trap 0x0)设置断点，采用单步和连续混合执行的方法完成程序，注意中间过程和寄存器的变化情况，然后单击主菜单execute/display dlx-i/o,观察结果。3 2 1 5 实验程序实验源程序见文件gcm.s和input.s6 实验报告要求实验报告中应包含：实验目的、实验内容、实验步骤（要有程序清单并以注释的形式对定义的变量和使用的寄存器进行说明）、实验结果等内容。gcm.s;* WINDLX Ex.1: Greatest common measure *;* (c) 1991 G黱ther Raidl *;* Modified 1992 Maziar Khosravipour *;-; Program begins at symbol main; requires module INPUT; Read two positive integer numbers from stdin, calculate the gcm; and write the result to stdout;-.data;* Prompts for inputPrompt1:.asciiz First Number:Prompt2:.asciiz Second Number: ;* Data for printf-TrapPrintfFormat:.asciiz gcM=%dnn.align2PrintfPar:.wordPrintfFormatPrintfValue:.space4.text.globalmainmain:;* Read two positive integer numbers into R1 and R2addir1,r0,Prompt1jalInputUnsigned;read uns.-integer into R1addr2,r1,r0;R2 R2 ?bnezr3,r1Greaterr2Greater:;* subtract r1 from r2subr2,r2,r1jLoopr1Greater:;* subtract r2 from r1subr1,r1,r2jLoopResult: ;* Write the result (R1)swPrintfValue,r1addir14,r0,PrintfPartrap5;* endtrap0input.s;* WINDLX Ex.1: Read a positive integer number *;* (c) 1991 G黱ther Raidl *;* Modified 1992 Maziar Khosravipour *;-;Subprogram call by symbol InputUnsigned;expect the address of a zero-terminated prompt string in R1;returns the read value in R1;changes the contents of registers R1,R13,R14;-.data;* Data for Read-TrapReadBuffer:.space80ReadPar:.word0,ReadBuffer,80;* Data for Printf-TrapPrintfPar:.space4SaveR2:.space4SaveR3:.space4SaveR4:.space4SaveR5:.space4.text.globalInputUnsignedInputUnsigned:;* save register contentsswSaveR2,r2swSaveR3,r3swSaveR4,r4swSaveR5,r5;* PromptswPrintfPar,r1addir14,r0,PrintfPartrap5;* call Trap-3 to read lineaddir14,r0,ReadPartrap3;* determine valueaddir2,r0,ReadBufferaddir1,r0,0addir4,r0,10;Decimal systemLoop:;* reads digits to end of linelbur3,0(r2)seqir5,r3,10;LF - Exitbnezr5,Finishsubir3,r3,48;?multur1,r1,r4;Shift decimaladdr1,r1,r3addir2,r2,1 ;increment pointerjLoopFinish: ;* restore old register contentslwr2,SaveR2lwr3,SaveR3lwr4,SaveR4lwr5,SaveR5jrr31; Return实验二 流水线中的结构相关1 实验目的：1. 近一步熟悉DLX指令集结构及其特点； 2. 通过本实验，加深对结构相关的理解，了解结构相关对CPU性能的影响。2 实验平台WinDLX模拟器3 预备知识1. 进一步熟悉WinDLX指令集和WinDLX源代码的编写2. 复习和掌握教材中相应的内容（1）DLX基本流水线（2）流水线的结构相关与数据相关l 结构相关：当指令在重叠执行过程中，硬件资源满足不了指令重叠执行的要求，l 发生资源冲突时，将产生“结构相关”。4 实验内容和步骤1. 用WinDLX模拟器运行程序structure_d.s 。2. 通过模拟，找出存在结构相关的指令对以及导致结构相关的部件。1. LD F0, 0(R2) ADDD F2, F0, F2 ; 16)&0xFFFF ADDUI R2, R2, A&0xFFFF LHI R3, (B16)&0xFFFF ADDUI R3, R3, B&0xFFFF ADDU R4, R0, R3 loop: LD F0, 0(R2) LD F4, 0(R3) ADDD F0, F0, F4 ADDD F2, F0, F2 ; - A stall is found (an example of how to answer your questions) 取指令时和上一条冲突 ADDI R2, R2, #8 - A stall is found ADDI R3, R3, #8 - A stall is found SUB R5, R4, R2 - A stall is found BNEZ R5, loop TRAP #0 ; Exit 16) & 0xFFFF ADDUI R2, R2, A & 0xFFFF LHI R3, (B16)&0xFFFF ADDUI R3, R3, B&0xFFFF loop: LW R1, 0 (R2) ADD R1, R1, R3 SW 0(R2), R1 LW R5, 0 (R1) ADDI R5, R5, #10 ADDI R2, R2, #4 SUB R4, R3, R2 BNEZ R4, loop TRAP #0 A: .word 0, 4, 8, 12, 16, 20, 24, 28, 32, 36 B: .word 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 六 实验报告要求实验报告中应包含：实验目的、实验内容、实验步骤（要有程序清单并以注释的形式对定义的变量和使用的寄存器进行说明）、实验结果等内容。实验四 LRU页面置换算法模拟一、实验目的 1、了解内存分页管理策略2、掌握调页策略3、掌握一般常用的调度算法4、选取调度算法中的典型算法，模拟实现 二、实验平台 在Window系统的TC2.0环境下运行程序；通过从一般常用的调页算法中选取典型算法LRU，了解页面管理的相关细节，并用程序设计实现LRU。 三、预备知识分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。 一、调页策略 1)何时调入页面 如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页的效率更高效一些。但如果调入的一批页面中的大多数都未被访问，则又是低效的。可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那么，这种策略显然是很有吸引力的。但目前预调页的成功率仅为50%。且这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。 2)请求调页策略 当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由OS将其所需页面调入内存。由请示调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启用频率。 2、从何处调入页面 在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况： (1) 系统拥有足够的对换区空间，这时可以全部从对换区调入 所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。 (2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出时，以后需要时，再从对换区调入。 (3) UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都从文件区调入。而对于曾经运行过但又被换出的页面，由于被放在对换区，因此在下次时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。 3、页面调入过程 每当程序所要访问的页面未在内存时， 便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外在原物理 块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。 二、页面置换算法 在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。 常见置换算法 最佳置换算法(Optimal)： 它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 先进先出(FIFO)页面置换算法： 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 LRU置换算法：这是本次设计的重点。 CLOCK置换算法：a,简单CLOCK置换算法；b,改进型CLOCK算法。LRU算法是较好的一种算法，而由于LRU在硬件上要求较多，在实际应用中多采用LRU的近似算法。CLOCK算法就是用得较多的一种LRU近似算法。 最少使用(LFU:Least Frequently Used)置换算法：在采用该算法时，应为在内存中的每个页面设置一个移位寄存器骼来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面为淘汰页。 页面缓冲算法(PBA：Page Buffering Algorithm) 、最近最久未使用置换算法 LRU(Least Recently Used)置换算法的描述 FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 2、LRU置换算法的硬件支持 LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持： 1） 寄存器 为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为18。由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。 R 实 页 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 2) 栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。 四、实验内容与步骤 1、用C语言实现最近最久未使用（LRU）置换算法。2、分析评价（1）运行程序（2）分析结果五、实验程序#include #include #define M 4 #define N 17 #define Myprintf printf(|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n)/*表格控制*/ typedef struct page int num;/*记录页面号*/ int time;/*记录调入内存时间*/ Page;/* 页面逻辑结构，结构为方便算法实现设计*/ Page bM;/*内存单元数*/ int cMN;/*暂保存内存当前的状态：缓冲区*/ int queue100;/*记录调入队列*/ int K;/*调入队列计数变量*/ /*初始化内存单元、缓冲区*/ void Init(Page *b,int cMN) int i,j; for(i=0;iN;i+) bi.num=-1; bi.time=N-i-1; for(i=0;iM;i+) for(j=0;jN;j+) cij=-1; /*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/ int GetMax(Page *b) int i; int max=-1; int tag=0; for(i=0;imax) max=bi.time; tag=i; return tag; /*判断页面是否已在内存中*/ intEquation(int fold,Page *b) int i; for(i=0;i=0) bval.time=0; for(i=0;iM;i+) if (i!=val) bi.time+; else queue+K=fold;/*记录调入页面*/ val=GetMax(b); bval.num=fold; bval.time=0; for(i=0;iM;i+) if (i!=val) bi.time+; /*主程序*/ void main() int aN=1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4; int i,j; start: K=-1; Init(b, c); for(i=0;iN;i+) Lru(ai,b); c0i=ai; /*记录当前的内存单元中的页面*/ for(j=0;jM;j+) cji=bj.num; /*结果输出*/ printf(内存状态为：n); Myprintf; for(j=0;jN;j+) printf(|%2d ,aj); printf(|n); Myprintf; for(i=0;iM;i+) for(j=0;jN;j+) if(cij=-1) printf(|%2c ,32); else printf(|%2d ,cij); printf(|n); Myprintf; printf(n调入队列为:); for(i=0;i1: 后鼠标闪烁，键入20 然后按 Enter，模拟继续运行到断点 # 2 处。 在Clock cycle diagram 窗口中，在指令之间出现了红和绿的箭头。红色箭头表示需要一个暂停，箭头指向处显示了暂停的原因。R-Stall（R-暂停）表示引起暂停的原因是RAW。绿色箭头表示定向技术的使用。现在我们来看一下寄存器中的内容。为此，双击主窗口中的Register 图标。Register 窗口会显示各个寄存器中的内容。看一下R1到 R5的值。按F5使模拟继续运行到下一个断点处，有些值将发生改变，指令lw从主存中取数到寄存器中。如果你希望不设置断点，而使模拟继续进行。办法是：点击Execute / Multiple Cycles 或者按 F8键，在新出现的窗口中输