操作系统课程设计报告.doc

操作系统课程设计报告时间：2013-1-72013-1-18地点：信息技术实验中心软件工程 专业2010级2班26号钟镁城2013-1-18一 课程设计的目的和意义3二 进程调度算法模拟41 设计目的42 设计要求43 使用动态优先权的进程调度算法的模拟5三 动态分区分配方式模拟91 设计目的92 设计要求93 模拟算法的实现10（1）首次适应算法13（2）最佳适应算法14四 请求调页存储管理方式模拟161 设计目的162 设计要求163模拟算法的实现17（1）OPT算法19（2）FIFO算法20（3） LRU算法21五 简单的文件操作231 设计目的232 设计要求233 模拟算法的实现24六 总结35一 课程设计的目的和意义本次课程设计目的是通过c语言对学过的课程进行理解应用。本次课程设计共有四个部分：（1） 使用动态优先权的进程调度算法的模拟，通过实现动态优先权的模拟加深对进程概念和进程调度的理解。了解在实际进程调度中，除了按调度算法选择下一个执行的进程外，还有哪些工作等。（2） 了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。了解采用首次适应算法和最佳适应算法对内存分配和回收的基本机制。（3） 通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求页面系统的原理和实现过程的理解。（4） 通过具体的文件存储空间的管理和文件的物理结构、目录和文件操作加深对文件管理机制的理解。 加深对计算机操作系统进程管理、文件管理机制的理解和应用。二 进程调度算法模拟1 设计目的通过动态优先权算法的模拟加深对进程概念和进程调度过程的理解。2 设计要求 （1）用C语言来实现对N个进程采用动态优先算法的进程调度； （2）每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：l 进程标识符idl 进程优先数priority，并规定优先数越大的进程，其优先权越高；l 进程已占用的CPU时间cputime；l 进程还需占用的CPU时间alltime，当进程运行完毕时，alltime变为0；l 进程的阻塞时间startblock，表示当进程再运行startblock个时间片后，进程将进入阻塞状态；l 进程被阻塞的时间blocktime，表示已阻塞的进程再等待blocktime个时间片后，将转换成就绪态l 进程状态state；l 队列指针next，用来将PCB排成队列（3）优先数改变的原则：l 进程在就绪队列中呆一个时间片，优先数增加1l 进程每运行一个时间片，优先数减3。（4）假设在调度前，系统中有5个进程，它们的初始状态如下：ID01234PRIORITY93830290CPUTIME00000ALLTIME33634STARTBLOCK2-1-1-1-1BLOCKTIME30000STATEREADYREADYREADYREADYREADY （5）为了清楚地观察诸进程的调度过程，程序应将每个时间片内的进程的情况 显示出来，参照的具体格式如下：RUNNING PROG： iREADY_QUEUE:-id1-id2BLOCK_QUEUE:-id3-id4=ID 01234PRIORITY P0P1P2P3P4CPUTIME C0C1C2C3C4ALLTIME A0A1A2A3A4STARTBLOCK T0T1T2T3T4BLOCKTIME B0B1B2B3B4STATE S0S1S2S3S43 使用动态优先权的进程调度算法的模拟 （1）程序流程图 （2） 关键算法设计 程序清单：void init();void print();int getRunning();void sort();int run(int time);enum STATEReady,Run,Block,RunOut;/设定进程状态：就绪、执行、阻塞、 中断 struct PROCESSint ID;/进程标识符idint Priority;/进程优先数priority，并规定优先数越大的进程，其优先权越高 int Cputime;/ 进程已占用的CPU时间cputimeint Alltime;/进程还需占用的CPU时间alltime，当进程运行完毕时，alltime变为0int Startblock;/进程的阻塞时间startblock，表示当进程再运行startblock个时间片后，进程将进入阻塞状态 int Blocktime;/进程被阻塞的时间blocktime，表示已阻塞的进程再等待blocktime个时间片后，将转换成就绪态enum STATE State;/进程状态stateProcessN;int READYN;int BLOCKN;int RUNOUTN2;int main()关键算法如下：int run(int time)/进程在就绪队列中呆一个时间片，优先数增加1。进程每运行一个时间片，优先数减3int i,runNum;runNum=READY0;if(runNum0&BLOCK0=0)ProcessrunNum.Priority-=3;ProcessrunNum.Alltime-=1;ProcessrunNum.Cputime+=1;ProcessrunNum.State=Run;for(i=0;iN;+i)if(i!=runNum)if(Processi.State=Ready)Processi.Priority+=1;else if(Processi.State=Block)Processi.Blocktime-=1;if(Processi.Blocktime=0)Processi.State=Ready;/print();if(ProcessrunNum.Alltime=0)/ProcessrunNum.State=RunOut;for(i=0;iN;+i)if(RUNOUTi0=0)ProcessrunNum.Startblock-=1;if(ProcessrunNum.Startblock=0)ProcessrunNum.State=Block;/ProcessrunNum.Startblock-=1; else if(BLOCK0=0)for(i=0;iadd=p-address;m-size=b;m-num=a;m-next=n-next;n-next=m;n=m; /保证n始终指向被占用链表的尾部，方便以后新生成结点的插入 if(p-sizeb) /如果申请空间的大小小于找到空闲空间的大小的处理p-size=p-size-b;p-address=p-address+b;else /如果申请空间的大小等于找到空闲空间的大小的处理 p-before-after=p-after;if(p-after!=NULL) p-after-before=p-before;free(p);void sort() /对空闲链表进行排序int max; node *p,*q,*r,*s;node a;p=L.after;while(p!=NULL) /让指针q指向链表的最后一个结点q=p;p=p-after;if(L.after-after=NULL) return;else while(p!=q) s=r=p=L.after; max=r-size; while(s!=q-after) if(s-sizemax) max=s-size; r=s; s=s-after; else s=s-after; a.size=q-size; a.address=q-address; q-size=r-size; q-address=r-address; r-size=a.size; r-address=a.address;if(q-before-before=&L)return;else q=q-before; 程序流程图： 如下图 （1）首次适应算法 void firstfit() /首次适应算法int a,b,i;Init();Print();while(1)printf(n1、申请空间n); printf(2、释放空间n); printf(3、退出首次适应算法n); printf(请输入你的选择:); scanf(%d,&i); switch(i) case 1: printf(请输入申请空间的作业号:); scanf(%d,&a); printf(请输入申请空间的大小:); scanf(%d,&b); alloc(a,b); Print(); break; case 2: printf(请输入释放空间的作业号:); scanf(%d,&a); printf(请输入释放空间的大小:); scanf(%d,&b); recovery(a,b); Print(); break; case 3:printf(n);return; （2）最佳适应算法void bestfit()int a,b,i;Init();Print();while(1)printf(n1、申请空间n); printf(2、释放空间n); printf(3、退出最佳适应算法n); printf(请输入你的选择:); scanf(%d,&i); switch(i) case 1: printf(请输入申请空间的作业号:); scanf(%d,&a); printf(请输入申请空间的大小:); scanf(%d,&b); alloc(a,b); sort(); Print(); break; case 2: printf(请输入释放空间的作业号:); scanf(%d,&a); printf(请输入释放空间的大小:); scanf(%d,&b); recovery(a,b); sort(); Print(); break; case 3:printf(n);return; 运行效果图：效果图1 效果图2四 请求调页存储管理方式模拟1 设计目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调用系统的原理和实现过程的理解。掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。2 设计要求1假设每个页面中可存放10条指令，分配给作业的内存块数为4。2用C语言或C+语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中， 如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3 置换算法：请分别考虑最佳置换算法（OPT）、先进先出（FIFO）算法和最近最久未使用（LRU）算法。4作业中指令的访问次序按下述原则生成；50%的指令是顺序执行的；25%的指令是均匀分布在前地址部分；25%的指令均匀分布在后地址部分。 具体的实现办法是：（1）在0，319之间随机选取一条起始执行指令，其序号为m；（2）顺序执行下一条指令，其序号为m+1条指令；（3）通过随机数，跳转到前地址部分0，m-1中的某条指令处，其序号为m1；（4）顺序执行下一条指令，即序号为m1+1的指令；（5）通过随机数，跳转到后地址部分m1+2,319中的某条指令处，其序号为m2；（6）顺序执行下一条指令，则序号为m2+1的指令；（7）重复跳转到前地址部分，顺序执行，跳转到后地址部分；顺序执行的过程，直至 执行320条指令。3模拟算法的实现 程序清单： int count;/程序计数器，用来记录指令的序号 int n;/缺页计数器，用来记录缺页的次数 static int temp320;/用来存储320条随机数 BLOCK blocksize; /定义一大小为4的物理块数组 void init( ); /程序初始化函数 int findExist(int curpage);/查找物理块中是否有该页面 int findSpace( );/查找是否有空闲物理块 int findReplace( );/查找应予置换的页面 void display ( );/显示 void Random( );/产生320条随机数,显示并存储到temp320 void pagestring( );/显示调用的页面队列 void OPT( );/OPT算法 void LRU( );/ LRU算法 void FIFO( );/FIFO算法 程序流程图： （1）OPT算法 发生缺页时，有些页面在内存中，其中有一页见很快被访问（也包含紧接着的下指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。如果某页在八百万条指令内不会被使用，另一页在600万条指令内不会被使用，则置换前一个页面，从而把因需要调回这 一页发生的缺页推到将来，越远越好。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。 关键算法： void OPT( )int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); count=tempi; curpage=count/10; exist = findExist(curpage); if(exist=-1) space = findSpace ( ); if(space != -1)blockspace.pagenum = curpage; display( ); n=n+1; elsefor(int k=0;ksize;k+)for(int j=i;j320;j+)if(blockk.pagenum!= tempj/10)blockk.accessed = 1000;/将来不会用，设置为一个很大数 elseblockk.accessed = j;break; position = findReplace( ); blockposition.pagenum = curpage; display( ); n+; cout缺页次数:nendl; cout缺页率:(n/320.0)*100%endl; （2）FIFO算法该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中，每当页面被置换进入内存时，将置换页面所在的物理块中访问标记设为-1；并且每执行一次指令，便将物理块的访问标记自动加1，需要置换时将访问标记最大的物理块中的页面置换出去，这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法。关键算法设计：void FIFO( ) int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); /getch直接从键盘获取键值 count=tempi; curpage=count/10; exist = findExist(curpage); /查找物理块中是否有该页面 if(exist=-1)space = findSpace( ); /查找是否有空闲物理块 if(space != -1) /有空闲物理块 blockspace.pagenum = curpage; display( ); n=n+1; else /无空闲物理块，则寻找置换页面 position = findReplace( ); /查找应予置换的页面 blockposition.pagenum = curpage; display( ); n+; blockposition.accessed-; /置换页面所在的物理块中访问标记设为-1 else/若存在该页for(int i=0; isize; i+) if(blocki.pagenum != -1) /物理块不空printf( %02d ,blocki.pagenum);cout指令已经存在! 其物理块地址为:&blockexistendl;for(int j=0; jsize; j+)blockj.accessed+; cout缺页次数:nendl; cout缺页率:(n/320.0)*100%endl;（3） LRU算法该算法以最近的过去作为不久将来的近似， 将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当物理块中的页面被访问时（包括原先存在的和后来置换进入的页面），便将其物理块访问标记置为1。以后每执行一条指令，便将物理块中各页面的访问标记加1，需置换时访问标记最大的便是将要被置换的。关键算法设计：void LRU( ) int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); /getch直接从键盘获取键值 count=tempi; /指令在数组中的位置 curpage=count/10; /指令所在页面 exist = findExist(curpage); /查找物理块中是否有该页面,若有返回物理块号 if(exist=-1) /物理块中不存在该页space = findSpace( ); /查找是否有空闲物理块 if(space != -1) /有空闲物理块blockspace.pagenum = curpage; display( ); n=n+1; else /无空闲物理块，则寻找置换页面 position = findReplace( ); /查找应予置换的页面 blockposition.pagenum = curpage; blockposition.accessed = -1; /恢复刚调入的BLOCK中页面accessed为-1 display( ); n+; else blockexist.accessed = -1;/恢复存在的并刚访问过的BLOCK中页面accessed为-1 for(int j=0; j4; j+) blockj.accessed+; cout缺页次数:nendl; cout缺页率:(n/320.0)*100%root);elsedir=(struct dirFile *)(osPoint-data current-3);for(i=1;ifcbi.type=DIRECTORY & strcmp(dir-fcbi.fname,sonfname)=0)break;temp=i;if(i=BlockFcbCount)printf(当前目录下不存在该子目录!n);return 0;j = dir-fcbtemp.currentBlockNum;struct dirFile *sonDir; /当前子目录的指针sonDir=(struct dirFile *)(osPoint-data j - 3);for(i=1;ifcbi.type!=Zero)printf(该文件夹为非空文件夹,为确保安全，请清空后再删除!n);return 0;/*开始删除子目录操作*/osPoint-FAT1j = osPoint-FAT2j=0; /fat清空char *p=osPoint-dataj-3; /格式化子目录memset(p,0,BlockSize);dir-fcbtemp.initialize(); /回收子目录占据目录项 printf(删除当前目录下的文件夹成功n);return 1;/*-在当前目录下创建文本文件-*/int create(char *name)int i,iFAT;/temp,int emptyNum = 0,isFound = 0; /空闲目录项个数struct dirFile *dir; /当前目录的指针if(current=2)dir=&(osPoint-root);elsedir=(struct dirFile *)(osPoint-data current-3);for(i=1;ifcbi.type = Zero & isFound = 0)emptyNum = i;isFound = 1;else if(dir-fcbi.type=GENERAL & strcmp(dir-fcbi.fname,name)=0 )printf(无法在同一目录下创建同名文件!n);return 0;if(emptyNum = 0)printf(已经达到目录项容纳上限，无法创建新目录!n);return 0;for(i = 3;iFAT1i=0)break;if(i=BlockCount)printf(磁盘已满!n);return 0;iFAT=i;/*-进入分配阶段-*/分配磁盘块osPoint-FAT1iFAT = osPoint-FAT2iFAT = 1;/*-接下来进行分配-*/填写该分派新的盘块的参数strcpy(dir-fcbemptyNum.fname,name);dir-fcbemptyNum.type=GENERAL;dir-fcbemptyNum.fatherBlockNum=current;dir-fcbemptyNum.currentBlockNum=iFAT;dir-fcbemptyNum.size =0;char* p = osPoint-dataiFAT -3;memset(p,4,BlockSize);printf(在当前目录下创建文本文件成功！n);return 1;/*-查询子目录-*/int listshow()int i,DirCount=0,FileCount=0;/搜索当前目录struct dirFile *dir; /当前目录的指针if(current=2)dir=&(osPoint-root);elsedir=(struct dirFile *)(osPoint-data current-3);for(i=1;ifcbi.type=GENERAL) /查找普通文件FileCount+;printf(%s 文本文件.n,dir-fcbi.fname);if(dir-fcbi.type=DIRECTORY) /查找目录文件DirCount+;printf(%s 文件夹.n,dir-fcbi.fname);printf(n该目录下共有 %d 个文本文件, %d 个文件夹nn,FileCount,DirCount);return 1;/*-在当前目录下删除文件-*/int delfile(char *name)int i,temp,j;/确保当前目录下有该文件,并且记录下它的FCB下标struct dirFile *dir; /当前目录的指针if(current = 2)dir=&(osPoint-root);elsedir=(struct dirFile *)(osPoint-data current-3);for(i=1;i fcbi.type=GENERAL & strcmp(dir-fcbi.fname,name)=0)break;if(i = BlockFcbCount)printf(当前目录下不存在该文件!n);return 0;int k;for(k=0;kf k.type = GENERAL)&(strcmp(openlist-f k.fname,name)=0)if(openlist-fk.fatherBlockNum = current)break;elseprintf(该文件未在当前目录下!n);return 0;if(k!=OPEN_MAX)close(name);/从打开列表中删除/*开始删除文件操作*/temp=i;j = dir-fcb temp.currentBlockNum ; /查找盘块号josPoint-FAT1j=osPoint-FAT2j=0; /fat1,fat2表标记为空白char *p=osPoint-dataj - 3;memset(p,0,BlockSize); /清除原文本文件的内容dir-fcbtemp.initialize(); /type=0; /标记该目录项为空文件printf(在当前目录下删除文件成功！n);return 1;/*-进入当前目录下的子目录-*/int changePath(char *sonfname)struct dirFile *dir; /当前目录的指针if(current=2)dir=&(osPoint-root);elsedir=(struct dir