北邮高级计算机系统结构实验二三四五

北邮世纪学院数据结构实验文档实验一：<编程文档><注意：生成日期和修改日期不需要填写，系统自动填写><生成新文档的时候，需要修改页眉中标注的部分，不需要修改页脚><修改文档之后，请刷新一下目录，由于我们的文档一般比较长，还是有目录比较好。

> <文件名起名原则：_文档名称>修订历史记录本文档简要说明。

目录修订历史记录 (1)1问题描述 (3)2主函数流程MAIN() (3)2.1功能 (3)2.2性能 (3)2.3输人项 (3)2.4输出项 (3)2.5算法 (3)2.6流程逻辑 (3)2.7注释设计 (4)2.8限制条件 (4)3函数1设计说明 (4)4源程序 (4)5测试报告 (5)5.1案例一：测试MAIN() (5)5.2案例二：测试子函数 (5)5.3尚未解决的问题 (5)6心得体会 (5)7分工及签名 (5)1问题描述给出对该程序的简要描述(作业题)，主要说明安排设计本程序的目的意义。

2主函数流程main()2.1功能说明该程序应具有的功能，可采用IPO图（即输入一处理一输出图）的形式。

2.2性能说明对该程序的全部性能要求，包括对精度、灵活性和时间特性的要求。

2.3输人项给出对每一个输入项的特性，包括名称、标识、数据的类型和格式、数据值的有效范围、输入的方式。

数量和频度、输入媒体、输入数据的来源和安全保密条件等等。

2.4输出项给出对每一个输出项的特性，包括名称、标识、数据的类型和格式，数据值的有效范围，输出的形式、数量和频度，输出媒体、对输出图形及符号的说明、安全保密条件等等。

2.5算法详细说明本程序所选用的算法，具体的计算公式和计算步骤。

2.6流程逻辑用图表（例如流程图、判定表等）辅以必要的说明来表示本程序的逻辑流程。

Word自带的绘图工具一般都不利于排版，建议使用Visio绘制所有的流程图和模块图，插入Word。

Visio可以有很多页，最好将自己的论文图片都放在一个vsd文件中。

北京邮电大学实验报告课程名称计算机系统结构计算机学院03班王陈(11)目录实验一WINDLX模拟器安装及使用......................................... 错误!未定义书签。

·实验准备................................................................................ 错误!未定义书签。

·实验环境................................................................................ 错误!未定义书签。

·实验步骤................................................................................ 错误!未定义书签。

·实验内容及要求.................................................................... 错误!未定义书签。

·实验过程............................................................................. 错误!未定义书签。

·实验总结............................................................................. 错误!未定义书签。

实验二指令流水线相关性分析 ............................................... 错误!未定义书签。

·实验目的............................................................................. 错误!未定义书签。

实验三DLG处理器程序设计1.实验目的学习简单编译优化方法，观察采用编译优化方法所带来的性能的提高。

2.实验原理采用静态调度方法重排指令序列，减少相关，优化程序。

3、实验内容和要求自编一段汇编代码，完成一维向量加法运算，并输出结果。

观察程序中出现的数据/控制/结构相关。

（注：使用一维数组表示一维向量。

）4．1向量加法代码清单及注释说明1、向量加法设计源代码.dataVectorLength:.word16Vector1:.word1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16Vector2:.word1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16；声明向量长度以及声明向量1、2Printf1:.asciiz"Vector="Printf2:.asciiz"%f".align2PrintPrompt:.wordPrintf1PrintPar:.wordPrintf2Result:.space4；存放打印数据的空间申请.teGtmain:addir14,r0,PrintPrompttrap5lwr20,VectorLengthaddir2,r0,0Loop:ldf10,Vector1(r2)ldf12,Vector2(r2)；循环体中读入向量cvti2df0,f10cvti2df2,f12adddf4,f2,f0；加法运算Finish:;GGGGFinish,writeresultintostdoutsdResult,f4addir14,r0,PrintPartrap5；系统中断，输出结果addir2,r2,4subir20,r20,1bnezr20,Loop;GGGGEndtrap02、运行结果5．1程序相关性分析结果（1）观察程序中出现的数据/控制/结构相关。

指出程序中出现上述现象的指令组合。

产生34.12%的数据相关。

北京邮电大学操作系统第二次实验实验报告班级302班第一部分：内存管理的伙伴算法1.实验描述：实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。

用随机函数仿真进程进行内存申请，并且以较为随机的次序进行释放。

对其碎片进行统计，当申请分配内存失败时区分实际空间不足和由于碎片而不能满足。

2.实验原理解释：假设要求分配的块其大小为128个页面。

该算法先在块大小为128个页面的链表中查找，看是否有这样一个空闲块。

如果有，就直接分配；如果没有，该算法会查找下一个更大的块，具体地说，就是在块大小为256个页面的链表中查找一个空闲块。

如果存在这样的空闲块，内核就把这256个页面分为两等份，一份分配出去，另一份插入到块大小为128个页面的链表中。

如果在块大小为256个页面的链表中也没有找到空闲页块，就继续找更大的块，即512个页面的块。

如果存在这样的块，内核就从512个页面的块中分出128个页面满足请求，然后从384个页面中取出256个页面插入到块大小为256个页面的链表中。

然后把剩余的128个页面插入到块大小为128个页面的链表中。

如果512个页面的链表中还没有空闲块，该算法就放弃分配，并发出出错信号。

以上过程的逆过程就是块的释放过程，这也是该算法名字的来由。

满足以下条件的两个块称为伙伴：两个块的大小相同，两个块的物理地址连续。

伙伴算法把满足以上条件的两个块合并为一个块，该算法是迭代算法，如果合并后的块还可以跟相邻的块进行合并，那么该算法就继续合并。

3.试验运行截图：第一组数据测试截图：第二组数据测试截图：第三组数据测试截图：4.实验代码：#include<iostream>#include<stdio.h>#define GETMIN(a,b) ((a)<(b)?(a):(b)) #define GETMAX(a,b) ((a)>(b)?(a):(b)) using namespace std;struct Node{int size;int remain;int frag;int isSplit;Node *left;Node *right;Node *parent;};struct Process{int oriMem;int reqMem;Node *ptr;void init(int _oriMem){int i;if(_oriMem<=0){oriMem=0;reqMem=0;ptr=NULL;return;}oriMem=_oriMem;for(i=31;i>=0;i--){if(oriMem&(1<<i)){break;}}if(oriMem==1<<i){reqMem=oriMem;}else{reqMem=1<<(i+1);}ptr=NULL;}};class BuddyTree{private:Node *root;Node *newNode(Node *_parent,int _size,int _remain){Node *ptr=new(Node);ptr->size=_size;ptr->remain=_remain;ptr->frag=0;ptr->isSplit=0;ptr->left=NULL;ptr->right=NULL;ptr->parent=_parent;return ptr;}public:Node* getRoot(){return root;}void init(int MaxMem){root=newNode(NULL,MaxMem,MaxMem);}void requestMem(Node *ptr,Node *&res,int reqSize,int oriSize){ if(ptr->remain<reqSize){res=NULL;return;}if(ptr->size==reqSize){res=ptr;ptr->remain=0;ptr->frag+=reqSize-oriSize;return;}if(ptr->isSplit==0){int _size=ptr->size/2;ptr->isSplit=1;ptr->left=newNode(ptr,_size,_size);ptr->right=newNode(ptr,_size,_size);requestMem(ptr->left,res,reqSize,oriSize);}else{int minMem=GETMIN(ptr->left->remain,ptr->right->remain); if(minMem>=reqSize){if(ptr->left->remain<=ptr->right->remain){requestMem(ptr->left,res,reqSize,oriSize);}else{requestMem(ptr->right,res,reqSize,oriSize);}}else{if(ptr->left->remain>=reqSize){requestMem(ptr->left,res,reqSize,oriSize);}else{requestMem(ptr->right,res,reqSize,oriSize);}}}ptr->remain=GETMAX(ptr->left->remain,ptr->right->remain);ptr->frag=ptr->left->frag+ptr->right->frag;}void releaseMem(Node *ptr){int memsize=ptr->size;int frag=ptr->frag;ptr->frag=0;ptr->remain=memsize;ptr=ptr->parent;while(ptr){if(ptr->left->remain==ptr->left->size&&ptr->right->remain==ptr->right->size){ ptr->remain=ptr->size;}else{ptr->remain=GETMAX(ptr->left->remain,ptr->right->remain);}ptr->frag-=frag;ptr=ptr->parent;}}void printTree(Node *ptr){if(ptr==NULL)return;char tmp[100];sprintf(tmp,"[Node size %dB]",ptr->size);printf("%-26s",tmp);sprintf(tmp,"remaining : %dB",ptr->remain);printf("%-26s",tmp);sprintf(tmp,"fragment : %dB",ptr->frag);printf("%s\n",tmp);printTree(ptr->left);printTree(ptr->right);}};Process P[200];int test[3][20]={{24,80,4600,8,100,1,500},{70,480,3300,25,10600,8909,490,99,40},{1,20,300,4000,50000,600000,7000000,80000000,900000000}}; int n[3]={7,9,9};int memory[3]={1024,1024*1024,1024*1024*1024};int main(){BuddyTree BT;char tmp[100];for(int t=0;t<3;t++){printf("Test%d:\n",t+1);printf("Process status:\n");for(int j=0;j<n[t];j++){P[j].init(test[t][j]);sprintf(tmp,"Original request: %d",P[j].oriMem);printf("%-30s",tmp);sprintf(tmp,"Actual request: %d",P[j].reqMem);printf("%s\n",tmp);}printf("\nMemory amount : %dB\n",memory[t]);BT.init(memory[t]);printf("\n");printf("Constructing the tree:\n");for(int j=0;j<n[t];j++){sprintf(tmp,"The process needs %d bytes.",P[j].oriMem);printf("%-35s",tmp);BT.requestMem(BT.getRoot(),P[j].ptr,P[j].reqMem,P[j].oriMem);if(P[j].ptr){printf("Request success,obtain %d bytes.\n",P[j].reqMem);}else{printf("Request failed.\n");}}printf("\n");printf("After constructing,preorder the tree:\n");BT.printTree(BT.getRoot());printf("\n");printf("After constructing the tree,the sum of fragment is %d.\n",BT.getRoot()->frag);printf("\n");printf("After the release,the tree(preorder) is:\n");for(int j=0;j<n[t];j++){if(P[j].ptr){BT.releaseMem(P[j].ptr);}}BT.printTree(BT.getRoot());printf("\n");printf("\n");system("pause");printf("\n");}return 0;}第二部分：设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率1.实验描述：设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。

高级计算机系统结构实验报告实验二指令流水线相关性分析实验三DLX处理器程序设计实验四代码优化实验五循环展开专业计算机科学与技术班级2015姓名学号2015实验二指令流水线相关性分析1. 实验目的：通过使用WINDLX模拟器，对程序中的三种相关现象进行观察，并对使用专用通路，增加运算部件等技术对性能的影响进行考察，加深对流水线和RISC处理器的特点的理解。

2. 实验设备环境：2.1 WinDLX模拟器可以装入DLX汇编语言程序，然后单步、设置断点或者连续执行该程序；2.2 CPU的寄存器、流水线、I/O和存储器都可以使用图形的方式表示出来；2.3 模拟器还提供了对流水线操作的统计功能；2.4 该模拟器对理解流水线和RISC处理器的特点很有帮助；2.5 所有浮点运算部件的延时都设定为4个周期；3. 实验原理：指令流水线中主要有结构相关、数据相关、控制相关。

相关影响流水线性能。

3.1数据相关定义：原有先后顺序的两条指令（I1，I2)在对共享变量（位置）进行读、写时，指令流水线中实际完成的读、写顺序与原有顺序不一致，导致流水线输出错误。

三类数据相关：写读(WR)相关读写(RW)相关写写(WW)相关解决方法技术：1.使某些流水线指令延迟、停顿一或多个周期。

2.双端口存储器:如果指令和数据放在同一个存储器。

3.设置两个存储器：一个数据存储，一个为指令存储器。

4.软件优化编译：通过指令重新排序，消除数据相关。

5.定向技术：又称旁路技术或专用通路技术，是使后续指令提前得到前指令的运算结果(适合ALU类指令）3.2结构相关定义：如果某指令在流水线重叠执行过程中，硬件资源满足不了指令重叠执行的要求，会产生资源冲突或竞争，称为流水线结构相关解决方法技术：1.延迟技术：使某些指令延迟、停顿一或多个时钟周期2.双端口存储器：允许同时读两个数据或指令3.设置双存储器（哈弗结构）：一个数据存储，一个指令存储。

4软件优化编译：通过指令重新排序消除结构相关。

课程名称：计算机系统结构实验名称：代码优化实验班级：09211311姓名：schnee学号：日期：2012年4月20日目录1.实验目的 (3)2.实验原理 (3)3.优化程序代码清单及注释说明 (3)4.实验分析 (4)观察程序中出现的数据/结构/控制相关，指出程序中出现上述现象的指令组合。

(4)考察增加浮点运算部件对性能的影响。

(5)考察增加FORWARD部件对性能的影响。

(5)观察转移指令在转移成功和转移不成功时候的流水线开销。

(6)5.实验心得和总结 (6)1.实验目的学习简单编译优化方法，观察采用编译优化方法所带来的性能的提高。

2.实验原理采用静态调度方法重排指令序列，减少相关，优化程序。

3.优化程序代码清单及注释说明1..data2.VectorLength: .word 163.Vector1: .word 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,164.Vector2: .word 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,165.Printf1: .asciiz "Vector ="6.Printf2: .asciiz " %f"7..align 28.PrintPrompt: .word Printf19.PrintPar: . word Printf210.Result: .space 411..text12.main: ;**** Print prompt "Vector ="13.addi r14,r0,PrintPrompt14.trap 515. addi r2,r0,0 ;调换两行代码，;提前写入R2以减少下面语句的相关16.lw r20,VectorLength17.Loop:18.ld f10,Vector1(r2)19.ld f12,Vector2(r2)20.addi r2,r2,4 ;r2地址加4个字节，;相当于寻找下一个元素;将下面的句子1移动到此处21.cvti2d f0,f10 ;把int型改为double D0(f0:f1)22.cvti2d f2,f12 ;把int型改为double D1(f2:f3)23.subi r20,r20,1 ;r20值设为16，此处-1以循环16次;此处是将下面的句子2移动到此处24. addd f4,f2,f0 ;add D2=D0+D1;**** Finish,write result into stdout25.sd Result,f426.addi r14,r0,PrintPar27.trap 528.;addi r2,r2,4 ;句子129.;subi r20,r20,1 ;句子230. bnez r20,Loop;**** End31.trap 04.实验分析这个实验的优化思路在于：1、根据原先实验3中实验分析1）中关于相关性的分析来找出代码中的相关性，2、对其中具有相关性的指令，通过把无关紧要的代码提前或者拖后至相关性语句之间，以此来减少甚至消除数据相关性所造成的stall带来的效率低下。

数据结构实验报告实验名称：实验四——排序学生姓名：1．实验要求实验目的：通过选择实验内容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

题目2：使用简单数组实现下面各种排序算法，并进行比较。

排序算法如下：1、插入排序；2、希尔排序；3、冒泡排序；4、快速排序；5、简单选择排序；6、堆排序；7、归并排序；8、基数排序（选作）；9、其他。

具体要求如下：1、测试数据分成三类：正序、逆序、随机数据。

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。

5、编写main（）函数测试各种排序算法的正确性。

2. 程序分析2.1 存储结构2.2 关键算法分析一、关键算法：1、插入排序a、取排序的第二个数据与前一个比较b、若比前一个小，则赋值给哨兵c、从后向前比较，将其插入在比其小的元素后d、循环排序2、希尔排序a、将数组分成两份b、将第一份数组的元素与哨兵比较c、若其大与哨兵，其值赋给哨兵d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组e、循环进行数组拆分3、对数据进行编码a、取数组元素与下一个元素比较b、若比下一个元素大，则与其交换c、后移，重复d、改变总元素值，并重复上述代码4、快速排序a、选取标准值b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较c、否则后面元素赋给前面元素d、若后指针元素小于标准值，前指针后移，重新比较e、否则前面元素赋给后面元素5、简单选择排序a、从数组中选择出最小元素b、若不为当前元素，则交换c、后移将当前元素设为下一个元素6、堆排序a、生成小顶堆b、将堆的根节点移至数组的最后c、去掉已做过根节点的元素继续生成小顶堆d、数组倒置7、归并排序a、将数组每次以1/2拆分，直到为最小单位b、小相邻单位数组比较重排合成新的单位c、循环直至完成排序二、代码详细分析：1、插入排序关键代码：①取排序的第二个数据与前一个比较：if(r[i]<r[i-1])②若比前一个小，则赋值给哨兵：r[0]=r[i];③从后向前比较，将其插入在比其小的元素后：for(j=i-1;r[0]<r[j];j--){r[j+1]=r[j];a++;} r[j+1]=r[0];④循环排序2、希尔排序关键代码：①将数组分成两份：d=n/2②将第一份数组的元素与哨兵比较：for(int i=d+1;i<=n;i++)③若其大与哨兵，其值赋给哨兵：if(r[0]<r[i-d]){ r[0]=r[i];}④哨兵与第二份数组元素比较，将较大的值赋给第二份数组：for(j=i-d;j>0&&r[0]<r[j];j=j-d) {r[j+d]=r[j]; }⑤循环进行数组拆分：for(int;d>=1;d=d/2)3、冒泡排序关键代码：①取数组元素与下一个元素比较： for(int i=1;i<bound;i++)if(r[i]>r[i+1])②若比下一个元素大，则与其交换： r[0]=r[i]; r[i]=r[i+1]; r[i+1]=r[0];③后移，重复：for(int i=1;i<bound;i++)④改变总元素值，并重复上述代码：int bound=pos;4、快速排序关键代码：①选取标准值：r[0]=r[i]②比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较：while(i<j&&r[j]>=flag) {j--;}③否则后面元素赋给前面元素：r[i]=r[j];④若后指针元素小于标准值，前指针后移，重新比较：while(i<j&&r[i]<=flag){i++;}⑤否则前面元素赋给后面元素：r[j]=r[i];5、简单选择排序关键代码：①从数组中选择出最小元素： for(int j=i+1;j<=n;j++)②{if(r[j]<r[index]) index=j; }③若不为当前元素，则交换：if(index!=i) {r[0]=r[i]; r[i]=r[index];r[index]=r[0];}④后移将当前元素设为下一个元素：for(int i=1;i<n;i++)6、堆排序关键代码：①生成小顶堆：while(j<=m) {if(j<m&&r[j]>r[j+1]) {j++;}②if(r[i]<r[j]) {break; }③else{ int x; x=r[i]; r[i]=r[j]; r[j]=x; i=j; j=2*i; }}④将堆的根节点移至数组的最后： x=r[1]; r[1]=r[n-i+1]; r[n-i+1]=x;⑤去掉已做过根节点的元素继续生成小顶堆：sift(r,1,n-i,x,y);⑥数组倒置输出: for(int i=n;i>0;i--)cout<<r[i]<<" ";7、归并排序关键代码：①将数组每次以1/2拆分，直到为最小单位：mid=(low+high)/2;②小相邻单位数组比较重排合成新的单位：while(i<=m&&j<=high)if(L.r[i]<=L.r[j]) t[k++]=L.r[i++];else t[k++]=L.r[j++];while(i<=m) t[k++]=L.r[i++];while(j<=high) t[k++]=L.r[j++];for(i=low,k=0;i<=high;i++,k++) L.r[i]=t[k];三、计算关键算法的时间、空间复杂度插入排序O（n2）希尔排序O（n2）冒泡排序O（n2）快速排序O（nlog2n）简单选择排序O（n2）堆排序O（nlog2n）归并排序O（nlog2n）3. 程序运行结果1、测试主函数流程：流程图如图所示流程图示意图程序运行结果图如下：2、测试条件：按题目要求分别输入同组数据的正序、逆序、随机序列进行测试。

北邮计算机组成实验报告北邮计算机组成实验报告一、实验概述计算机组成实验是计算机科学与技术专业的一门重要实践课程，旨在通过实际操作和实验验证，加深学生对计算机硬件组成的理解和掌握。

本次实验的主要内容是通过搭建一个简单的计算机系统，包括CPU、存储器和输入输出设备等，来实现一个简单的指令执行过程。

二、实验目的1. 理解计算机系统的基本组成部分，包括CPU、存储器和输入输出设备等。

2. 掌握计算机指令的执行过程，包括指令的获取、解码和执行等。

3. 熟悉计算机系统的工作原理，包括时钟信号、总线传输和寄存器的使用等。

三、实验过程1. CPU设计与搭建在本次实验中，我们选择了基于MIPS架构的CPU进行设计和搭建。

首先，我们需要设计并实现CPU的指令集，包括算术运算、逻辑运算和数据传输等。

然后，根据指令集的要求，设计并实现CPU的控制逻辑电路，包括指令获取、解码和执行等。

最后，通过连接寄存器、ALU和存储器等组件，完成CPU的搭建。

2. 存储器设计与实现在计算机系统中，存储器是用于存储指令和数据的重要组成部分。

在本次实验中，我们选择了SRAM作为存储器的实现方式。

首先，我们需要根据CPU的指令集和数据需求，确定存储器的容量和位宽等参数。

然后，设计并实现存储器的读写控制电路，以实现指令和数据的读写功能。

最后，通过连接存储器和CPU，完成存储器的搭建。

3. 输入输出设备设计与实现在计算机系统中，输入输出设备用于与外部环境进行数据交互。

在本次实验中，我们选择了键盘和显示器作为输入输出设备的实现方式。

首先，我们需要设计并实现键盘的输入控制电路，以实现对输入数据的获取和传输。

然后，设计并实现显示器的输出控制电路，以实现对输出数据的显示和传输。

最后，通过连接输入输出设备和CPU，完成输入输出设备的搭建。

四、实验结果与分析通过实验，我们成功搭建了一个简单的计算机系统，并进行了指令执行的测试。

在测试过程中，我们编写了一些简单的程序，包括加法、乘法和逻辑运算等。

实验报告（2）姓名：学号：班级：日期：一、实验目的：掌握特殊线性表栈和队列的有关运算，熟悉栈和队列的存储结构的基本特点。

二、实验原理：完成特殊单链表-----栈和队列的运算。

具体：1、利用栈完成1个字符串的逆置运算；2、在一个循环队列中入队2元素的运算。

三、实验内容及要求：1、编写一个算法程序实现在一个顺序栈中把一个字符串逆置的运算，要求使用入栈和出栈运算来完成。

2、编写一个算法程序实现在一个循环队列中入队2个元素，要求先建立一个循环队列，元素个数为4个，然后在循环队列的末尾加入2个元素。

要求：请同学把步骤、调试好的程序及存在的问题写在下面。

第一题:步骤:首先创建一个空栈 ,然后提示用户输入一个字符串,依次读取字符串的每个字符并入栈 ,再依次取栈顶元素并出栈 ,便可得到原字符串的逆置。

第一题实验程序代码：#include <stdio.h>#define Stack_Size 50//数组大小定义typedef char DataType;typedef struct{DataType elem[Stack_Size];int top;}SeqStack;//栈的结构定义SeqStack *InitStack();//栈的创建函数int StackEmpty(SeqStack *S);//判断栈是否为空int StackFull(SeqStack *S);//判断栈是否为满void Push(SeqStack *S,DataType x);//元素入栈DataType Pop(SeqStack *S);//元素出栈void playdata(SeqStack *S);//打印输出栈中的元素int main(){SeqStack *S;char x;S=InitStack();if(S==NULL)return 0;printf("请输入一个字符串，以回车键结束：\n");//打印提示语x=getchar();while(x!='\n'){Push(S,x);x=getchar();}if(!StackEmpty(S))//判断字符串是否为空{printf("该字符串的逆序是：\n");playdata(S);}elseprintf("该字符串为空！\n");system("pause");return 0;}SeqStack *InitStack()//栈的创建函数{SeqStack *S;S=(SeqStack*)malloc(sizeof(SeqStack));if(S==NULL)return NULL;else{S->top=-1;return S;}}int StackEmpty(SeqStack *S)//判断栈是否为空{return S->top==-1;}int StackFull(SeqStack *S)//判断栈是否为满{return S->top==Stack_Size-1;}void Push(SeqStack *S,DataType x)//元素入栈{S->elem[++S->top]=x;}DataType Pop(SeqStack *S)//元素出栈{return S->elem[S->top--];}void playdata(SeqStack *S)//打印输出栈中的元素{int i=0;for(i=S->top;i>=0;i--){printf("%c",S->elem[i]);}printf("\n");}第二题:步骤：首先创建一个循环队列，接着在循环队列中入队四个元素，接着提示用户输入2个元素，再入队，再将入队后的队列元素从队头到队尾打印出来，程序结束。

北京邮电大学课程设计报告目录实验一：交通灯控制器设计............................................................................. 实验二：电子钟设计 ........................................................................................ 实验三：药片装瓶系统设计............................................................................. 附：数字逻辑课程设计调试日志及个人心得体会...........................................实验一：交通灯控制器设计一、实验目的①学习采用状态机方法设计时序逻辑电路。

②掌握ispLEVER软件的使用方法。

③掌握用VHDL语言设计数字逻辑电路。

④掌握ISP器件的使用。

二、实验所用器件和设备在系统可编程逻辑器件ISP1032 一片示波器一台万用表或逻辑笔一只TEC-5实验系统，或TDS-2B数字电路实验系统一台三、实验内容以实验台上的4个红色电平指示灯，4个绿色电平指示灯模仿路口的东南西北4个方向的红，绿，黄交通灯。

控制这些交通灯，使它们按下列规律亮，灭。

(1)初始状态为4个方向的红灯全亮，时间1s。

(2)东，西方向绿灯亮，南，北方向红灯亮。

东，西方向通车，时间5s。

(3)东，西方向黄灯闪烁，南，北方向红灯，时间2s。

(4)东，西方向红灯亮，南，北方向绿灯亮。

南，北方向通车，时间5s。

(5)东，西方向红灯闪烁，南，北方向黄灯闪烁，时间2s。

(6)返回(2)，继续运行。

(7)如果发生紧急事件，例如救护车，警车通过，则按下单脉冲按钮，使得东，南，西，北四个方向红灯亮。

紧急事件结束后，松开单脉冲按钮，将恢复到被打断的状态继续运行。

北京邮电大学实验报告题目：微机原理软件实验三班级： 2010211127专业：信息工程姓名：付莹学号：10210759实验五：中断实验1. 实验类设计型实验：编程实现时钟的显示。

2. 实验目的掌握计数器/定时器8253的工作原理和编程方法；掌握中断控制器8259的工作原理；掌握中断处理程序的编写。

3. 实验条件硬件条件：PC机一台。

软件条件：DOS操作系统；任意一种编辑程序，如EDIT；宏汇编程序MASM；连接程序LINK；调试程序DEBUG。

可借用该程序中的中断服务程序以及8253的初始化程序段（口地址为40H、41H、42H、43H，控制字为36H=00110110B，时间常数TC=11932：1.1932MHz/11932=100Hz，输出方波频率为100Hz，其周期为1000/100=10ms）。

4. 实验内容及步骤编一程序，在显示器上显示时、分、秒。

借用计数器8253的Timer0作为中断源，通过8259A向CPU发中断，每10ms产生一次中断。

在中断服务程序中管理刷新时、分、秒Current time is: xx:xx:xx （时分秒键盘输入）回车后时、分、秒开始计时，时钟不停的刷新。

当键入CTRL+C时，停止计时，返回系统，且系统正常运行不死机。

5. 实验报告（1）画出程序流程图。

开始等待回车键按下（08H 中断调用）取原8H 中断的中断矢量并压栈保护建立数据段的可寻址性 装载现在的中断服务程序8253初始化产生10ms 方波，10ms 中断一次重写IMR ，只开放时钟和键盘中断开中断监测键盘（06H 中断调用）是Ctrl+C ？ 关中断 恢复IMR重置8253，,55ms 中断一次恢复原中断开中断返回DOS ，结束Yes有键按下？显示时间值（09H 中断调用）取消秒Yes 计数达到100次(1秒)？NoYesNoNo实现等待计时功能实现循环，秒值变化则返回继续执行程序显示“Current time is ：” 读入键盘输入（2）提交调试好的汇编语言源程序（.asm）。

操作系统实验三文件系统和设备管理作者：北邮班级2009211309学院(系)：计算机学院专业：指导教师：分数：目录1. 实验目的 (2)2. 实验要求 (2)3. 具体实现 (2)3.1.LINUX下串口的非阻塞读写程序 (2)3.2.模块 (3)3.3 实现一个procfs文件系统的模块 (7)4. 实验心得……………………………………………………………5.附录源代码 (9)1.实验目的了解LINUX下文件系统和I/O的实现，了解其中模块的设计。

2.项目要求（a）实现一个LINUX下串口的非阻塞读写程序。

（b）了解LINUX下模块的实现方式，及相应的编译和安装及卸载过程。

实现一个模块，在模块安装时可打印信息（Hello）和卸载时打印信息（Goodbye）.（c）实现一个procfs文件系统的模块。

3.具体实现3.1 LINUX下串口的非阻塞读写程序在Linux 下串口文件是位于/dev 下，串口一为/dev/ttyS0，串口二为/dev/ttyS1打开串口是通过使用标准的文件打开函数操作：int fd;/*以读写方式打开串口*/fd = open( "/dev/ttyS0", O_RDWR);if (-1 == fd){/* 不能打开串口一*/perror(" 提示错误！");}在使用时还应当设置串口、读写串口、关闭串口等，通过查阅资料实现了对串口的读写代码见附录3.2 模块模块是具有独立功能的程序，它可以被单独编译，但不能独立运行。

它在运行时被链接到内核作为内核的一部分在内核空间运行，这与运行在用户空间的进程是不同的。

模块通常由一组函数和数据结构组成，用来实现一种文件系统、一个驱动程序或其他内核上层的功能。

首先在电脑里编写一段C语言代码，hello.c。

代码如下分析：(1)在内核模块的开始一部分，跟C语言的一般程序一样，是模块所需要的头文件。

(2)模块许可证声明，这部分是必须有的。

实验二指令流水线相关性分析·实验目的通过使用WINDLX模拟器，对程序中的三种相关现象进行观察，并对使用专用通路，增加运算部件等技术对性能的影响进行考察，加深对流水线和RISC 处理器的特点的理解。

·实验原理：指令流水线中主要有结构相关、数据相关、控制相关。

相关影响流水线性能。

·实验步骤一．使用WinDLX模拟器，对Fact.s做如下分析：（1）观察程序中出现的数据/控制/结构相关。

指出程序中出现上述现象的指令组合。

（2）考察增加浮点运算部件对性能的影响。

（3）考察增加forward部件对性能的影响。

（4）观察转移指令在转移成功和转移不成功时候的流水线开销。

·实验过程一．使用WinDLX模拟器，对Fact.s做如下分析：浮点加、乘、除部件都设置为1，浮点数运算部件的延时都设置为4，如图1：图1 初始设置将fact.s和input.s加载至WinDLX中，如图2示。

图2 加载程序1.观察程序中出现的数据/控制/结构相关；指出程序中出现上述现象的指令组合。

1）数据相关点击F7，使程序单步执行，当出现R-Stall时停止，运行过程中出现下图3所示，输入整数6。

图3 输入整数6打开Clock Diagram，可以清楚的看到指令执行的流水线如图4所示。

图4 指令流水线双击第一次出现R-Stall的指令行，如图5所示。

图5 指令详细信息对以上出现的情况分析如下：程序发生了数据相关，R-Stall（R-暂停）表示引起暂停的原因是RAW。

lbu r3,0×0(r2)要在WB周期写回r3中的数据；而下一条指令seqi r5,r3,0×a要在intEX周期中读取r3中的数据。

上述过程发生了WR冲突，即写读相关。

为了避免此类冲突，seq r5,r4,0×a的intEX指令延迟了一个周期进行。

由此，相关指令为：2）控制相关由图6可以看出，在第4时钟周期：第一条指令处于MEM段，第二条命令处于intEX段，第三条指令出于aborted状态，第四条命令处于IF段。

计算机系统结构的发展历程课程：高级计算机系统结构姓名：学号：班级：2015年12月一、计算机系统结构随着当今社会和科技的飞速发展，自四十年代计算机问世以来，计算机科学更是发展迅速，应用领域不断扩展计算机的普及和广泛应用，现代社会正朝着高度信息化，自动化方向发展。

计算机逐渐成为社会必不可少的支柱力量。

计算机系统是按人的要求接收和存储信息，自动进行数据处理和计算，并输出结果信息的机器系统。

计算机是脑力的延伸和扩充，是近代科学的重大成就之一。

计算机系统由硬件系统和软件系统组成。

前者是借助电、磁、光、机械等原理构成的各种物理部件的有机组合，是系统赖以工作的实体。

后者是各种程序和文件，用于指挥全系统按指定的要求进行工作。

而计算机系统结构是计算机的的机器语言程序员或编译程序编写者所看到的外特性。

所谓外特性，就是计算机的概念性结构和功能特性，主要研究计算机系统的基本工作原理，以及在硬件、软件界面划分的权衡策略，建立完整的、系统的计算机软硬件整体概念。

其也称为计算机体系结构，它是由计算机结构外特性，内特性，微外特性组成的。

经典的计算机系统结构的定义是指计算机系统多级层次结构中机器语言机器级的结构，它是软件和硬件/固件的主要交界面，是由机器语言程序、汇编语言源程序和高级语言源程序翻译生成的机器语言目标程序能在机器上正确运行所应具有的界面结构和功能。

以最常见的冯诺依曼计算机为例，计算机系统结构包含了以下几个方面：1.指令集架构（Instruction set architecture；简称ISA）：被视为一种机器语言，包含了许多相关的指令集（存储器定址、处理器控制，寄存器控制等等……）。

2.微体系结构/微架构（Microarchitecture）或称计算机组织（Computerorganization）：是更详细的叙述系统内部各元素如何进行合作与沟通。

3.数据表示，即硬件能直接识别和处理的数据类型和数据格式。

4.寻址方式，包括最小寻址单位和地址运算等。