C语言模拟操作系统运行课程设计.doc

操作系统课程设计报告时间：2010-12-202010-12-31地点：信息技术实验中心计算机 专业2008级x班xx号xx2010-12-31目录一 课程设计的目的和意义3二 进程调度算法模拟41 设计目的42 设计要求43 时间片轮转算法模拟44 先来先服务算法模拟9三 主存空间的回收与分配141 设计目的142 设计要求143 模拟算法的实现15四 模拟DOS文件的建立和使用261 设计目的262 设计要求263 模拟算法的实现27五 磁盘调度381 设计目的382 设计要求383 模拟算法的实现38六 总结49一、课程设计的目的和意义本次操作系统课程设计的主要任务是进行系统级的程序设计。本课程设计是操作系统原理课程的延伸。通过该课程设计，使学生更好地掌握操作系统各部分结构、实现机理和各种典型算法，加深对操作系统的设计和实现思路的理解，培养学生的系统设计和动手能力，学会分析和编写程序。课程设计的实施将使学生在以下几个方面有所收获：（1）加深对操作系统原理的理解，提高综合运用所学知识的能力；（2）培养学生自主查阅参考资料的习惯，增强独立思考和解决问题的能力；（3）通过课程设计，培养严谨的科学态度和协作精神。二：进程调度算法模拟1 设计目的（1）要求学生设计并实现模拟进程调度的算法：时间片轮转及先来先服务。（2）理解进程控制块的结构。（3）理解进程运行的并发性。（4）掌握进程调度算法。2 设计要求在多道程序运行环境下，进程数目一般多于处理机数目，使得进程要通过竞争来使用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之运行，分配处理机的任务是由进程调度程序完成的。一个进程被创建后，系统为了便于对进程进行管理，将系统中的所有进程按其状态，将其组织成不同的进程队列。于是系统中有运行进程队列、就绪队列和各种事件的进程等待队列。进程调度的功能就是从就绪队列中挑选一个进程到处理机上运行。进程调度的算法有多种，常用的有优先级调度算法、先来先服务算法、时间片轮转算法。进程是程序在处理机上的执行过程。进程存在的标识是进程控制块（PCB），进程控制块结构如下：typedef struct node char name10; /* 进程标识符 */ int prio; /* 进程优先数 */ int round; /* 进程时间轮转时间片 */ int cputime; /* 进程占用 CPU 时间*/ int needtime; /* 进程到完成还需要的时间*/ int count; /* 计数器*/ char state; /* 进程的状态*/ struct node *next /*链指针*/ PCB; 系统创建一个进程，就是由系统为某个程序设置一个PCB，用于对该进程进行控制和管理，进程任务完成，由系统收回其PCB，该进程便消亡。每个进程可以有三个状态：运行状态、就绪状态和完成状态。用C语言、C+或者Java语言编写一个程序实现进程调度的算法，模拟进程调度的过程，加深对进程控制块概念和进程调度算法的理解。本任务要求完成时间片轮转及先来先服务两个算法。3.时间片轮转算法完成进程的调度3.1设计要求：（1）进程的调度采用时间片轮转算法。（2）设计三个链队列，分别用来表示运行队列、就绪队列和完成队列。（3）用户输入进程标识符以及进程所需的时间，申请空间存放进程 PCB信息。（4）输出的格式和上面的运行结果分析中的格式相同。时间片轮转调度，具体做法是调度程序每次把 CPU 分配给就绪队列首进程使用一个时间片。当这个时间片结束时，就强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。实现这种调度要使用一个间隔时钟。当一个进程开始运行时，就将时间片的值置入间隔时钟内，当发生间隔时钟中断时，就表明该进程连续运行的时间已超过一个规定的时间片。此时，中断处理程序就通知处理器调度进行处理器的切换工作。3.2.时间片轮转算法主要思想：在计算机中系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后再把处理机分配给就绪队列中给定的时间内均能获得一时间片的处理机执行时间。3.3算法的实现1.数据结构及变量说明 typedef struct pcb char name10; /进程标识符 int pArriveTime; /到达时间 int pRunTime; /估计运行时间 int round; /进程时间轮转时间片 int cputime; /进程占用CPU时间 int needtime; /进程到完成还要的时间 int count; /计数器 char state; /进程的状态 struct pcb *next; /链指针PCB;PCB *finish,*ready,*tail,*run; /队列指针PCB head_input; int N; /进程数2.完成功能的主要函数void roundrun()/时间片轮转法函数3.时间片轮转的主要算法功能及注释：void insert2(PCB *p2)/轮转法插入函数 tail->next=p2; /将新的PCB插入在当前就绪队列的尾 tail=p2; p2->next=NULL;void create2()/轮转法创建进程PCB PCB *p; int i,time,n; char na10; ready=NULL; finish=NULL; run=NULL; printf("输入进程名及所需时间n"); for(i=1;i<=N;i+) p=(PCB*)malloc(sizeof(PCB); scanf("%s",na); scanf("%d",&time); strcpy(p->name,na); p->cputime=0; p->needtime=time; p->count=0; /计数器 p->state='W' p->round=3; if(ready!=NULL) insert2(p); else p->next=ready; ready=p; tail=p; system("cls"); printf(" 轮转法输出n"); printf("*n"); prt(); /输出进程PCB信息 run=ready; /将就绪队列的第一个进程投入运行 ready=ready->next; run->state='R'void roundrun()/时间片轮转法 while(run!=NULL) run->cputime=run->cputime+1; run->needtime=run->needtime-1; run->count=run->count+1; if(run->needtime=0)/运行完将其变为完成态，插入完成队列 run->next=finish; finish=run; run->state='F' run=NULL; if(ready!=NULL) firstin(); /就绪对列不空，将第一个进程投入运行 else if(run->count=run->round) /如果时间片到 run->count=0; /计数器置0 if(ready!=NULL) /如就绪队列不空 run->state='W' /将进程插入到就绪队列中等待轮转 insert2(run); firstin(); /将就绪对列的第一个进程投入运行 prt(); /输出进程信息 4.时间片算法主要流程图如下：开始创建PCB进程，输入进程名及时间就绪队列ready!nullYrun->cputime=run->cputime+1;run->needtime=run->needtime-1;run->count=run->count+1;run->needtime=0Yrun->next=finish; finish=run;run->state='F' run=NULL;ready!=NULLYrun=ready; run->state='R'ready=ready->next;run->count=run->roundNrun->count=0;/计数器置0Yready!=NULLYtail->next=run; tail=run;run->next=NULL; run->state='W' run=ready; run->state='R' ready=ready->next;输出进程信息NN结束ready!=NULL5.时间片算法运行结果分析如下：4.用先来先服务算法完成进程的调度4.1设计要求：（1）进程的调度采用先来先服务算法。（2）设计三个链队列，分别用来表示运行队列、就绪队列和完成队列。（3）用户输入进程标识符以及进程所需的时间，申请空间存放进程PCB信息。（4）输出的格式和上面的运行结果分析中的格式相同。先来先服务：按照进程进入就绪队列的先后次序来分配处理器。先进入就绪队列的进程优先被挑选，运行进程一旦占有处理器将一直运行下去直到运行结束或被阻塞，这是一种非剥夺式调度。4.2先来先服务调度算法主要思想：此算法既可用于作业调度，也歌词用于进程调度。当作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。4.3 算法的实现1.数据结构及变量说明 typedef struct pcb char name10; /进程标识符 int pArriveTime; /到达时间 int pRunTime; /估计运行时间 int round; /进程时间轮转时间片 int cputime; /进程占用CPU时间 int needtime; /进程到完成还要的时间 int count; /计数器 char state; /进程的状态 struct pcb *next; /链指针PCB;PCB *finish,*ready,*tail,*run; /队列指针PCB head_input; int N; /进程数2.完成功能的主要函数void ExecProcessList()/先来先服务函数3.先来先服务的主要算法功能及注释：void ExecProcessList() run=head_input.next; while(run!=NULL) run=head_input.next;/run指向对头的下一个进程 printf("开始运行 正在运行 已经运行时间 剩余时间 等 待 中 的 进程 已结束进程n"); for (int j=0;j<(run->pRunTime)/1000;j+)/输出每次运行的统计信息 if (0=j) printf(" %s n",run->name);/到达进程开始执行 printf(" %s %d %d",run->name,j+1,(run->pRunTime/1000)-(j+1); ready=run->next; /判断此时还有哪些进程在队列里面 while (ready!=NULL) printf(" %s ",ready->name); ready=ready->next; printf("n"); run->state='C' /将进城状态设置为执行完的状态 printf(" %sn",run->name); ready=run;/将run指向下一个元素 run=run->next; head_input.next=run; delete ready;/将此进程从进程队列里面删除 4.先来先服务算法主要流程图如下：ready=run->next; printf(" %s %d %d",run->name,j+1,(run->pRunTime/1000)-(j+1);开始run=head_input.next;run!=NULLYrun=head_input.next; run->state='C' printf(" %sn",run->name); ready=run; run=run->next; head_input.next=run; delete ready; j=0j=0?Yprintf(" %s n",run->name);ready!=NULLprintf(" %s ",ready->name); ready=ready->next;结束5.先来先服务运行结果如下：三：主存空间的回收与分配1 设计目的主存是中央处理器能直接存取指令和数据的存储器，能否合理地利用主存，在很大程度上将影响到整个计算机系统的性能。主存分配是指在多道作业和多进程环境下，如何共享主存空间。主存回收是指当作业执行完毕或进程运行结束后将主存空间归还给系统。主存分配与回收的实现是与主存储器的管理方式有关。本次设计主要是为了帮助学生深入理解主存空间的分配与回收的几种算法。（1）掌握最先适应分配算法（2）掌握最优适应分配算法（3）掌握最坏适应分配算法2 设计要求用户提出内存空间请求，系统根据申请者要求，按照最先适应分配算法的分配策略分析内存空间的使用情况，找出能满足请求的空闲区，分给申请者，当程序执行完毕时，系统要收回它所占用的内存空间。建立空闲数据文件，空闲区数据文件包括若干行，每行有两个字段：起始地址、内存块大小（均为整数），各字段以逗号隔开。下面是一个空闲区数据文件的示例：0，10 10，08 18，10 28，06 34，10 44，09 读取空闲区数据文件，建立空闲区表并在屏幕上显示空闲内存状态，空闲区表记录了可供分配的空闲内存的起始地址和大小，用标志位指出该分区是否是未分配的空闲区。接收用户的内存申请，格式为：作业名、申请空间的大小。按照内存分配算法中的一种方法选择一个空闲区，分割并分配，修改空闲区表，填写内存已分配区表（起始地址、长度、标志位），其中标志位的一个作用是指出该区域分配给哪个作业。进程结束后回收内存。本次设计要求完成如下算法：（1）设计一个内存分配回收的程序使用最先适应分配算法（2）设计一个内存分配回收的程序使用最优适应分配算法（3）设计一个内存分配回收的程序使用最坏适应分配算法用户提出内存空间请求，系统根据申请者要求，选择上述算法的一种分配策略分析内存空间的使用情况，找出合适的空闲区，分给申请者，当进程执行完毕时，系统收回它所占用的内存空间。创建空闲区表：空闲区表的结构如下：typedef struct node int start; int length; char tag20; job; 3.算法的设计实现3.1设计实现：1.数据结构及变量说明const int MAXJOB=100;/定义表最大记录数 typedef struct node int start; int length; char tag20; job; job freesMAXJOB;/定义空闲区表 int free_quantity; job occupysMAXJOB;/定义已分配区表 int occupy_quantity;2.完成功能的主要函数initial() 初始化readData() 从文本文件读取数据sortearliest() 最先适应算法排序earliest() 实现最先适应算法sortbest() 最佳适应算法排序bestMethod() 实现最佳适应算法sortbad() 最坏适应算法排序BadMethod() 实现最坏适应算法finished() 实现主存回收view() 显示3.2.最先适应算法的功能及注释/声明变量char job_name20; int job_length; int i,j,flag,t; /输入进程名和空间大小cout<<"请输入新申请内存空间的作业名和空间大小:" cin>>job_name; cin>>job_length; flag=0; /标志变量for(i=0;i<free_quantity;i+) if(freesi.length>=job_length)/空闲区长度是否大于进程所需空间 flag=1; if(flag=0) /空闲区长度小于进程所需空间cout<<endl<<"Sorry,当前没有能满足你申请长度的空闲内存,请稍候再试"<<endl; else /空闲区长度大于进程所需空间，从首地址开始查询，找到大于进程长度的及分配给进程t=0; i=0; while(t=0) if(freesi.length>=job_length) t=1; i+; i-; occupysoccupy_quantity.start=freesi.start; strcpy(occupysoccupy_quantity.tag,job_name); occupysoccupy_quantity.length=job_length; occupy_quantity+; if(freesi.length>job_length) freesi.start+=job_length; freesi.length-=job_length; else for(j=i;j<free_quantity-1;j+) freesj=freesj+1; free_quantity-;最先适应算法的主要流程图如下：最先适应算法运行结果如下：3.3.最佳适应算法的实现/声明变量char job_name20; /名字 int job_length; /长度 int i,j; int max=0,min=0,maxx;/输入进程名和空间大小 cout<<"请输入新申请内存空间的作业名和空间大小:" cin>>job_name; cin>>job_length;/查找最合适的空闲区 for(i=0;i<free_quantity;i+) for(j=0;j<i;j+) if(freesj.length<=freesi.length) max=i;elsemax=j; for(j=0;j<i;j+) if(freesj.length>=freesi.length) min=i;elsemin=j; if(freesmin.length<=job_length && freesmax.length>=job_length) maxx=i; if(freesmaxx.length<job_length)/ 没有能满足的空闲区 cout<<endl<<"Sorry,当前没有能满足你申请长度的空闲内存,请稍候再试"<<endl; else/符合要求，给进程分配空间 occupysoccupy_quantity.start=freesmaxx.start; strcpy(occupysoccupy_quantity.tag,job_name); occupysoccupy_quantity.length=job_length; occupy_quantity+; if(freesmaxx.length>job_length) freesmaxx.start+=job_length; freesmaxx.length-=job_length; else for(j=maxx;j<free_quantity-1;j+) freesj=freesj+1;free_quantity-;最优流程图：最佳算法运行结果如下：3.4.最坏适应算法的实现/声明变量char job_name20; /名字 int job_length; /长度 int i,j; int max;/输入进程名和空间大小 cout<<"请输入新申请内存空间的作业名和空间大小:" cin>>job_name; cin>>job_length;/找出空闲区最大的 for(i=0;i<free_quantity;i+) for(j=0;j<i;j+) if(freesj.length<freesi.length) max=i; else max=j; if(freesmax.length<job_length)/如果最大空闲区都臂进程空间小，则不满足要求 cout<<endl<<"Sorry,当前没有能满足你申请长度的空闲内存,请稍候再试"<<endl; else/满足要求，给进程分配空间 occupysoccupy_quantity.start=freesmax.start; strcpy(occupysoccupy_quantity.tag,job_name); occupysoccupy_quantity.length=job_length; occupy_quantity+; if(freesmax.length>job_length) freesmax.start+=job_length; freesmax.length-=job_length; else for(j=max;j<free_quantity-1;j+) freesj=freesj+1; free_quantity-;最坏流程图：最坏算法运行结果如下：3.5.主存回收算法的实现/声明变量char job_name20; int i,j,flag,p=0; int start; int length; /输入要回收的进程名cout<<"请输入要撤消的作业名:" cin>>job_name; flag=-1; /标志变量/找到指定进程for(i=0;i<occupy_quantity;i+) if(!strcmp(occupysi.tag,job_name) flag=i; start=occupysi.start; length=occupysi.length; if(flag=-1) cout<<"没有这个作业名"<<endl; else /加入空闲表 for(i=0;i<free_quantity;i+) if(freesi.start+freesi.length)=start) if(i+1)<free_quantity)&&(freesi+1.start=start+length) freesi.length=freesi.length+freesi+1.length+length; for(j=i+1;j<free_quantity;j+) freesj=freesj+1; free_quantity-; p=1; else freesi.length+=length; p=1; if(freesi.start=(start+length) freesi.start=start; freesi.length+=length; p=1; if(p=0) freesfree_quantity.start=start; freesfree_quantity.length=length; free_quantity+; /删除分配表中的该作业 for(i=flag;i<occupy_quantity;i+) occupysi=occupysi+1; occupy_quantity-;主存回收的流程图如下：回收算法运行结果如下：四：模拟DOS文件的建立和使用1 设计目的磁盘文件是磁盘上存储的重要信息，通过本实验模拟DOS文件的建立和使用情况，理解磁盘文件的物理结构。文件管理是操作系统中重要的内容之一，不同的文件系统提供了不同的物理结构，通过实验，深入理解文件的物理结构与存取方法之间的关系，以便更好的掌握文件系统的概念。2 设计要求（1） 模拟设计DOS操作系统中磁盘文件的存储结构DOS操作系统对磁盘文件的管理采用链接结构，将所有的链接指针集中在一起，存放在文件分配表（FAT）中。连接文件的第一个物理块号登记在文件目录中。其设计思想是：假定磁盘上共有N个物理块可供使用，当要存放文件时，从FAT表中寻找其值为0的项，用其对应的物理块存放文件信息，并把文件占有的各物理块用链接指针登记在FAT表中，再把文件的第一个物理块号登记在文件目录中。文件目录及FAT表如图所示: 在DOS中FAT表的前两项用来记录磁盘的类型。而从第2项开始记录磁盘的分配情况和文件各物理块的链接情况。在FAT表中第三项的值如果为0，表示对应的第三块空闲。由图还知道文件A的各记录依次存放在第2、第4、第15、第16、第50等六个物理块中。第50块中的指针为FFF，表示文件A的结束。文件B的各记录依次存放在第7、第10、第20等三个物理块中。第20块中的指针为FFF。假定磁盘存储空间共有100个物理块，设计一个文件分配表。为了简单，文件分配表可用一个数组定义，其中每一个元素与一个物理块对应。当第 i 个元素为 0 时，表示第 i 块空闲；当第 i 个元素既不为 0 也不为 FFF 时，其值表示该文件的下一个物理块号。另外，再设一个空闲块总数变量记录系统还有的空闲块数。为了简单，假定一个物理块指存放一个逻辑记录，要求设计一个程序，把文件的逻辑记录结构转换成 DOS 的链接结构。当用户要求将已在主存的文件保存在磁盘上时，给出文件名及文件的记录个数，系统应能在磁盘上正确地保存文件。或当用户要求给指定文件增加记录时，也应正确的实现，并插在指定记录之后。为了正确地执行模拟程序，可用键盘模拟输入用户的要求。输入格式为：write(文件名，记录个数) 或insert(文件名，逻辑记录号) （2） 模拟设计便于直接存取的索引文件结构为了便于用户直接存取文件的各个逻辑记录，在 MS-DOS 中通过文件目录，再沿着链查找FAT表，便可直接找到指定逻辑记录对应的物理块。在小型机或更高级的文件系统中，直接存取文件的方法是为每个文件建立一个索引表，指出各逻辑记录与物理块的对应关系。最简单的形式是一个逻辑记录对应一个物理块。文件目录与索引表的关系如图所示。通常索引表按照逻辑记录顺序建立，这样既有利于顺序存储，又有利于直接存储。为了标识哪些记录已经建立，哪些记录还没建立，故在索引表中增设一个标志位。写文件或插入一个记录的过程是寻找一个空闲物理块，然后将其填入索引表对应项中。其建立过程同第一题，即 write（文件名，记录号）和 insert（文件名，记录号）。要求用位示图描绘出磁盘的使用情况，并要求模拟程序执行过程的每一步都能显示文件目录、位示图、索引表。3模拟算法的实现:1.数据结构及变量名：const int FDF=-2;const int FFF=-1;const int N=100;/存储空间(FAT表长度)int filenumber;/文件数量struct FILEINFOchar filename10;int startaddress;int filelength;2.实现功能的主要函数Void printfmenu()/打印目录表Void printfFAT()/打印FAT表Void search2()/搜索文件void write(char *tmpname,int tmplength)/写入文件void insert(char *tmpname,int insertpoint)/插入文件（1）.模拟设计DOS操作系统中磁盘文件的存储结构的主要算法功能及注释如下：写入函数算法：void write(char *tmpname,int tmplength)int last,i,j;strcpy(filefilenumber.filename,tmpname);/复制文件名和文件块个数