操作系统实验进程调度

实验三进程调度一．实验目的加深理解并模拟实现进程（作业）调度算法。1）熟悉常用的进程调度算法，如FCFS、SPF、FPF、高响应比优先、时间片轮转；2）结合所学的数据结构及编程知识，选择三种进程调度算法予以实现。二．实验属性该实验为设计性实验。三．实验仪器设备及器材普通PC386以上微机四．实验要求本实验要求2学时完成。本实验要求完成如下任务：编程实现单处理机系统中的进程调度，要求从FCFS、SPF、FPF、高响应比优先、时间片轮转算法中至少选择三个；最后编写主函数对所做工作进行测试。实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告（参见附录A），并要求用正规的实验报告纸和封面装订整齐，按时上交。五：实验具体设计此程序模拟了两种调度算法，FCFS和SPF，首先FCFS就是按照进程的创建顺序依次顺序进行，流程图为：进程顺序执行新进程进程1进程2进程3进程4新进程进程1进程2进程3进程4SPF:每次都进行循环，选出在该时间刻运行时间最短的进程优先执行。程序代码具体详解：创建一结构体作为进程控制器typedefstructPCB{ intID; charstate; intarrivetime; intstarttime; intfinishtime; intservicetime; structPCB*next;}pcb;定义全局变量作为计时器inttime;//计时器创建进程链表：从txt文件中读取数据，构造一条不含头结点的单链表voidCreate_process(){ ifstreaminFile; inFile.open("test.txt"); inFile>>n; inFile.get(); inti=0; for(;i<n;i++) { p=(pcb*)malloc(sizeof(pcb)); inFile>>p->ID; inFile>>p->arrivetime; inFile>>p->servicetime; p->starttime=0; p->finishtime=0; p->state='F'; p->next=NULL; if(head==NULL) { head=p;q=p;time=p->arrivetime; } if(p->arrivetime<time) time=p->arrivetime; q->next=p; q=p; }若执行FCFS算法，按顺序遍历链表voidfcfs1(){ inti; p=head; for(i=0;i<n;i++) { if(p->state=='F') { q=p; run_fcfs1(q); } p=p->next; }}voidrun_fcfs1(pcb*p1){ time=p1->arrivetime>time?p1->arrivetime:time; p1->starttime=time; printf("\n现在时间：%d,开始运行作业%d\n",time,p1->ID); time+=p1->servicetime; p1->state='T'; p1->finishtime=time; printf("ID号到达时间开始运行时间服务时间完成时间\n"); printf("%d%10d%12d%12d%12d\n",p1->ID,p1->arrivetime,p1->starttime,p1->servicetime,p1->finishtime);}若执行SPF算法，每次都从链表头开始遍历链表，找出arrivetime<=time并且运行时间最短的节点，执行该节点进程，最后再删除该节点。voidfcfs2(){ while(head) { p=head; q=p; intRun_time=p->servicetime; while(p!=NULL) { if(p->arrivetime<=time) { if(p->servicetime<Run_time) { q=p; } p=p->next; } else p=p->next; }run_fcfs2(q);pcb*pre; if(q==head) { head=head->next; } else { pre=head; while(pre->next!=q) pre=pre->next; if(q->next==NULL) pre->next=NULL; else pre->next=q->next; } }}voidrun_fcfs2(pcb*p1){ p1->starttime=time; printf("\n现在时间：%d,开始运行作业%d\n",time,p1->ID); time+=p1->servicetime; p1->state='T'; p1->finishtime=time; printf("ID号到达时间开始运行时间服务时间完成时间\n"); printf("%d%10d%12d%12d%12d\n",p1->ID,p1->arrivetime,p1->starttime,p1->servicetime,p1->finishtime);}六：程序执行效果：实验总结：模拟实验调度算法，用到的具体知识还主要是数据结构中的知识，在这次实验中，FCFS算法实现还算比较简单，SPF算法稍微有一些麻烦，主要是在进行查找运行时间最短的节点，并需要满足到达时间<time,并且还要是没有执行的节点，这一点稍微有些麻烦。源码#include<windows.h>#include<fstream.h>#include<stdio.h>#include<iostream>typedefstructPCB{ intID; charstate; intarrivetime; intstarttime; intfinishtime; intservicetime; structPCB*next;}pcb;inttime;//计时器intn;//进程个数pcb*head=NULL;pcb*p,*q;voidfcfs1();voidfcfs2();voidrun_fcfs1(pcb*p1);voidCreate_process();voidCreate_process(){ ifstreaminFile; inFile.open("test.txt"); inFile>>n; inFile.get(); inti=0; for(;i<n;i++) { p=(pcb*)malloc(sizeof(pcb)); inFile>>p->ID; inFile>>p->arrivetime; inFile>>p->servicetime; p->starttime=0; p->finishtime=0; p->state='F'; p->next=NULL; if(head==NULL) { head=p;q=p;time=p->arrivetime; } if(p->arrivetime<time) time=p->arrivetime; q->next=p; q=p; } inFile.close(); }voidrun_fcfs1(pcb*p1){ time=p1->arrivetime>time?p1->arrivetime:time; p1->starttime=time; printf("\n现在时间：%d,开始运行作业%d\n",time,p1->ID); time+=p1->servicetime; p1->state='T'; p1->finishtime=time; printf("ID号到达时间开始运行时间服务时间完成时间\n"); printf("%d%10d%12d%12d%12d\n",p1->ID,p1->arrivetime,p1->starttime,p1->servicetime,p1->finishtime);}voidrun_fcfs2(pcb*p1){ p1->starttime=time; printf("\n现在时间：%d,开始运行作业%d\n",time,p1->ID); time+=p1->servicetime; p1->state='T'; p1->finishtime=time; printf("ID号到达时间开始运行时间服务时间完成时间\n"); printf("%d%10d%12d%12d%12d\n",p1->ID,p1->arrivetime,p1->starttime,p1->servicetime,p1->finishtime);}voidfcfs1(){ inti; p=head; for(i=0;i<n;i++) { if(p->state=='F') { q=p; run_fcfs1(q); } p=p->next; }}voidfcfs2(){ while(head) { p=head; q=p; intRun_time=p->servicetime; while(p!=NULL) { if(p->arrivetime<=time) { if(p->servicetime<Run_time) { q=p; } p=p->next; } else p=p->next; }run_fcfs2(q); //删除该节点pcb*pre; if(q==head) { head=head->next; } else { pre=head; while(pre->next!=q) pre=pre->next; if(q->next==NULL) pre->next=NULL; else pre->next=q->