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

C语言模拟操作系统运行课程设计 操作系统课程设计报告 时间:2010-12-20,2010-12-31 地点:信息技术实验中心 计算机 专业 2008级x班xx号 xx 2010-12-31 目录 一 课程设计的目的和意义………………………………………………………3 二 进程调度算法模拟……………………………………………………………4 1 设计目的………………………………………………………………………4 2 设计要求………………………………………………………………………4 3 时间片轮转算法模拟…………………………………………………………4 4 先来先服务算法模拟…………………………………………………………9 三 主存空间的回收与分配………………………………………………………14 1 设计目的………………………………………………………………………14 2 设计要求………………………………………………………………………14 3 模拟算法的实现………………………………………………………………15 四 模拟DOS文件的建立和使用…………………………………………………26 1 设计目的………………………………………………………………………26 2 设计要求………………………………………………………………………26 3 模拟算法的实现………………………………………………………………27 五 磁盘调度………………………………………………………………………38 1 设计目的………………………………………………………………………38 2 设计要求………………………………………………………………………38 3 模拟算法的实现………………………………………………………………38 六 总结……………………………………………………………………………49 2 一、课程设计的目的和意义 本次操作系统课程设计的主要任务是进行系统级的程序设计。本课程设计是操作系统原理课程的延伸。通过该课程设计，使学生更好地掌握操作系统各部分结构、实现机理和各种典型算法，加深对操作系统的设计和实现思路的理解，培养学生的系统设计和动手能力，学会和编写程序。课程设计的实施将使学生在以下几个方面有所收获: (1)加深对操作系统原理的理解，提高综合运用所学知识的能力; (2)培养学生自主查阅参考资料的习惯，增强独立思考和解决问题的能力; (3)通过课程设计，培养严谨的科学态度和协作精神。 3 二:进程调度算法模拟 1 设计目的 (1)要求学生设计并实现模拟进程调度的算法:时间片轮转及先来先服务。 (2)理解进程控制块的结构。 (3)理解进程运行的并发性。 4)掌握进程调度算法。 ( 2 设计要求 在多道程序运行环境下，进程数目一般多于处理机数目，使得进程要通过竞争来使用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之运行，分配处理机的任务是由进程调度程序完成的。一个进程被创建后，系统为了便于对进程进行管理，将系统中的所有进程按其状态，将其组织成不同的进程队列。于是系统中有运行进程队列、就绪队列和各种事件的进程等待队列。进程调度的功能就是从就绪队列中挑选一个进程到处理机上运行。进程调度的算法有多种，常用的有优先级调度算法、先来先服务算法、时间片轮转算法。 进程是程序在处理机上的执行过程。进程存在的标识是进程控制块(PCB)，进程控制块结构如下: typedef struct node { char name[10]; /* 进程标识符 */ 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)进程的调度采用时间片轮转算法。 4 (2)设计三个链队列，分别用来示运行队列、就绪队列和完成队列。 (3)用户输入进程标识符以及进程所需的时间，申请空间存放进程 PCB信息。 (4)输出的格式和上面的运行结果分析中的格式相同。 时间片轮转调度，具体做法是调度程序每次把 CPU 分配给就绪队列首进程使用一个时间 片。当这个时间片结束时，就强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下 一轮调度。实现这种调度要使用一个间隔时钟。当一个进程开始运行时，就将时间片的值置入 间隔时钟内，当发生间隔时钟中断时，就表明该进程连续运行的时间已超过一个规定的时间 片。此时，中断处理程序就处理器调度进行处理器的切换工作。 3.2.时间片轮转算法主要思想: 在计算机中系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾;然后再把处理机分配给就绪队列中给定的时间内均能获得一时间片的处理机执行时间。 3.3算法的实现 1.数据结构及变量说明 typedef struct pcb { char name[10]; //进程标识符 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 5 { PCB *p; int i,time,n; char na[10]; 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) 6 { 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.时间片算法主要流程图如下: 7 开始 创建PCB进程，输 入进程名及时间 就绪队列ready!, null Y run->cputime=run->cputime+1;run->needtime=run- >needtime-1;run->count=run->count+1; N run->needtime==0 Y N run->count==run->round run->next=finish; finish=run; run->state='F'; run=NULL; Y run->count=0;//计数器置0 ready!=NULL ready!=NULL N ready!=NULL Y Y run=ready; run->state='R'; ready=ready->next; tail->next=run; tail=run;run->next=NULL; run->state='W'; run=ready; run->state='R'; ready=ready->next; 输出进程信息 结束 8 5.时间片算法运行结果分析如下: 4.用先来先服务算法完成进程的调度 4.1设计要求: (1)进程的调度采用先来先服务算法。 (2)设计三个链队列，分别用来表示运行队列、就绪队列和完成队列。 (3)用户输入进程标识符以及进程所需的时间，申请空间存放进程PCB信息。 (4)输出的格式和上面的运行结果分析中的格式相同。 先来先服务:按照进程进入就绪队列的先后次序来分配处理器。先进入就绪队列的进程优先被挑选，运行进程一旦占有处理器将一直运行下去直到运行结束或被阻塞，这是一种非剥夺式调度。 9 4.2先来先服务调度算法主要思想: 此算法既可用于作业调度，也歌词用于进程调度。当作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。 4.3 算法的实现 1.数据结构及变量说明 typedef struct pcb { char name[10]; //进程标识符 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) 10 { printf(" %s ",ready->name); ready=ready->next; } printf("\n"); } run->state='C'; //将进城状态设置为执行完的状态 printf(" %s\n",run->name); run指向下一个元素 ready=run;//将 run=run->next; head_input.next=run; delete ready;//将此进程从进程队列里面删除 } } 4.先来先服务算法主要流程图如下: 11 开始 run=head_input.next ; run!=NULL Y run=head_input.next; run->state='C'; printf(" %s\n",run->name); ready=run; run=run->next; head_input.next=run; delete ready; j=0 ready=run->next; printf(" %s %d %d",run->name,j+1,(run->pRunTime/1000)-(j+1)); j==0? printf(" %s \n",run- >name); ready!=NULL Y printf(" %s ",ready->name); ready=ready->next; 结束 5.先来先服务运行结果如下: 12 13 三:主存空间的回收与分配 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; 14 int length; char tag[20]; }job; 3.算法的设计实现 3.1设计实现: 1.数据结构及变量说明 const int MAXJOB=100;//定义表最大记录数 typedef struct node{ int start; int length; char tag[20]; }job; job frees[MAXJOB];//定义空闲区表 int free_quantity; job occupys[MAXJOB];//定义已分配区表 int occupy_quantity; 2.完成功能的主要函数 initial() 初始化 readData() 从文本文件读取数据 sortearliest() 最先适应算法排序 earliest() 实现最先适应算法 sortbest() 最佳适应算法排序 bestMethod() 实现最佳适应算法 sortbad() 最坏适应算法排序 BadMethod() 实现最坏适应算法 finished() 实现主存回收 view() 显示 3.2.最先适应算法的功能及注释 //声明变量 char job_name[20]; int job_length; int i,j,flag,t; //输入进程名和空间大小 cout<<"请输入新申请内存空间的作业名和空间大小:"; cin>>job_name; cin>>job_length; 15 flag=0; //标志变量 for(i=0;i=job_length){//空闲区长度是否大于进程所需空间 flag=1; } } if(flag==0){ //空闲区长度小于进程所需空间 cout<=job_length){ t=1; } i++; } i--; occupys[occupy_quantity].start=frees[i].start; strcpy(occupys[occupy_quantity].tag,job_name); occupys[occupy_quantity].length=job_length; occupy_quantity++; if(frees[i].length>job_length){ frees[i].start+=job_length; frees[i].length-=job_length; } else{ for(j=i;j>job_name; cin>>job_length; //查找最合适的空闲区 for(i=0;i=frees[i].length) min=i;elsemin=j;} if(frees[min].length<=job_length && frees[max].length>=job_length){ maxx=i; }} if(frees[maxx].lengthjob_length){ frees[maxx].start+=job_length; frees[maxx].length-=job_length; } else{ for(j=maxx;j>job_name; cin>>job_length; //找出空闲区最大的 for(i=0;ijob_length) { frees[max].start+=job_length; frees[max].length-=job_length;} else{ for(j=max;j>job_name; flag=-1; //标志变量 //找到指定进程 23 for(i=0;i=0&&m=0&&marray[j]) //将磁道号从小到大排序 { temp=array[i]; array[i]=array[j]; array[j]=temp; } } } printf("请输入当前的磁道号:\n"); //输入当前磁道号 scanf("%d",&now); printf("最短寻道时间优先算法调度后的序列为:\n");//输出磁盘调度序列 if (array[m-1]<=now) //若被访问的下一最大的磁道号不大于当前的磁道号 { for (i=m-1;i>=0;i--) { printf("%d ",array[i]);//输出磁盘调度序列 40 sum+=now-array[i]; now=array[i]; } } else { if (array[0]>=now) //若被访问的下一最小的磁道号不小于当前的磁道号 { for (i=0;i=0) //先向磁道号减小方向访问 { printf("%d ",array[l]); //输出磁盘调度序列 sum=sum+now-array[l]; now=array[l]; l=l-1; } now=array[0]; for (j=r;j=0;j--) //再向磁道号减小方向访问 { printf("%d ",array[j]); //输出磁盘调度序列 sum+=now-array[j]; now=array[j]; } } } } avg=sum/(m); printf("平均寻道长度:%f\n",avg);//输出平均寻道长度 printf("移动的总道数:%f\n",sum); } 9.最短寻道时间调度的主要流程图如下: 42 开始 将磁道号从小到大排序 输入当前磁道号now N Y array[m- 1]<=now Y (array[0]输出磁盘调度序列>=now array[j] N 输出磁盘调度确定当前磁道在已磁头移动总距离序列array[j] 排的序列中的位置 sum+=now-array[i] 目前的位置变为当前磁头移动总距离Y N now-sum+=now-的位置now=array[i] array[l])<=(arraarray[i] y[r]-now 目前的位置变为i>=0 当前的位置先向磁道号先向磁道号now=array[i] 减小方向访增加方向访now=array[i] 问，再向磁问，再向磁N 道号增加方道号减小方 向访问 向访问 iarray[j]) //将磁道号从小到大排序 { temp=array[i]; array[i]=array[j]; array[j]=temp; } } printf("请输入当前的磁道号:\n");//输入当前磁道号 scanf("%d",&now); printf("请输入当前移动臂的移动的方向(1 表示向磁道号增加方向,0 表示向磁道号减小方向): \n"); scanf("%d",&d); //先要给出当前磁道号和移动臂的移动方向 printf("扫描算法(SCAN)调度后的序列为:\n"); if (array[m-1]<=now) //若被访问的下一最大的磁道号不大于当前的磁道号 44 { for (i=m-1;i>=0;i--) { printf("%d ",array[i]); //输出磁盘调度序列 sum=now-array[i]; now=array[i]; } } else { if (array[0]>=now) //若被访问的下一最小的磁道号不小于当前的磁道号 { for (i=0;i=0) { printf("%d ",array[l]); //输出磁盘调度序列 sum=sum+now-array[l]; now=array[l]; l=l-1; } now=array[0]; 45 for (j=r;j=0;j--) { printf("%d ",array[j]); //输出磁盘调度序列 sum+=now-array[j]; now=array[j]; } break; } default: printf("输入有误\n"); } } } avg=sum/(m); printf("平均寻道长度:%f\n",avg);//输出平均寻道长度 printf("移动的总道数:%f\n",sum); } 13.电梯调度的主要流程图如下: 46 开始 将磁道号从小到大排序 输入当前磁道号now N Y array[m- 1]<=now Y (array[0]输出磁盘调度序列>=now array[j] N 输出磁盘调度确定当前磁道在已排的序列中的位置 磁头移动总距离序列array[j] sum+=now-array[i] 输入d=0或1 目前的位置变为当前磁头移动总距离N sum+=now-的位置now=array[i] array[i] d=0 d=1 Y Y 目前的位置变为i>=0 当前的位置Y N now-now=array[i] array[l])<=(arranow=array[i] y[r]-now N i