lab3.rar

////////////////////////////////////// // // CPU scheduler algorithm experiment // 2011-4-28 Liu @USTC // ////////////////////////////////////// #include <stdio.h> #include <stdlib.h> #include <time.h> #define N_PROCESS 10 #define T_SLICE 4 struct t_PCB { int pid; int arrive_time; int need_time; int start_time; int finished_time; } pcb_queue[N_PROCESS]; struct t_PCB work_q[N_PROCESS]; void init(); void sort_queue(); void set_work_q(); void print_queue(); void set_work_q(); void AWT(char *); void FCFS(); void SJF(); void RR(); int main() { init(); print_queue(); FCFS(); SJF(); RR(); } void init() { int i; printf("initializing...\nProcess number: %d time slice length: %d.\n randomly generlize arrive-time and need-time\n", N_PROCESS, T_SLICE); srand(time(NULL)); for(i=0;i<N_PROCESS;i++) { pcb_queue[i].pid=i+1; pcb_queue[i].arrive_time = rand() % (N_PROCESS); pcb_queue[i].need_time = rand() %(2*N_PROCESS)+1; //可以根据实验结果调整自定义,非零值 pcb_queue[i].finished_time=-1; pcb_queue[i].start_time=-1; } sort_queue(); } void sort_queue() //按照到达顺序排序 { int i,j,t; struct t_PCB p; for(i=0;i<N_PROCESS-1;i++) { t=i; for(j=i+1;j<N_PROCESS;j++) if(pcb_queue[j].arrive_time<pcb_queue[t].arrive_time) t=j; if(t!=i) { p=pcb_queue[i];pcb_queue[i]=pcb_queue[t];pcb_queue[t]=p; } } } void print_queue() { int i; for(i=0;i<N_PROCESS;i++) { printf("pid=%3d\t arrived_time:%3d\t need_time:%3d\n", pcb_queue[i].pid,pcb_queue[i].arrive_time,pcb_queue[i].need_time); } } void set_work_q() { int i; for(i=0;i<N_PROCESS;i++) work_q[i]=pcb_queue[i]; } void AWT(char *s) //求平均等待时间 { int i; float w=0.0, t=0.0; for( i=0;i<N_PROCESS; i++) { //w=w+work_q[i].start_time-work_q[i].arrive_time; //注 这样RR平均等待时间计算不对。 w=w+work_q[i].finished_time-work_q[i].arrive_time-pcb_queue[i].need_time ; t=t+work_q[i].finished_time-work_q[i].arrive_time; } w=w/N_PROCESS; t=t/N_PROCESS; printf("\n%s\t:平均等待时间：%5.2f\t平均周转时间：%5.2f\n",s,w,t); } void FCFS() { int timeline; int i; printf("\n\nFCFS running...\n"); set_work_q(); for(i=0,timeline=work_q[0].arrive_time; i<N_PROCESS; i++) { work_q[i].start_time=timeline; printf("proc %d started at time %d.\t",work_q[i].pid, timeline); timeline=work_q[i].start_time+work_q[i].need_time; work_q[i].finished_time=timeline; printf("finished at time %d.\n",timeline); } AWT("FCFS"); } void SJF()//短作业优先非抢占式 { int timeline=0; int finished=0; int found=0; int i; int j; int t; printf("\n\nSJF running...\n"); set_work_q(); while(finished<N_PROCESS) { t=100000; found =0; for(i=0;i<N_PROCESS ; i++) if(work_q[i].arrive_time<=timeline && work_q[i].finished_time<0 && work_q[i].need_time<t) { j=i;t=work_q[i].need_time;found=1; } if(found) { work_q[j].start_time=timeline; printf("proc %d started at time %d.\t",work_q[j].pid, timeline); work_q[j].finished_time =timeline+ work_q[j].need_time; timeline=timeline+work_q[j].need_time; finished++; printf("finished at time %d.\n", timeline); } else { timeline++; } } AWT("SJF"); } void RR() //轮转法 { int timeline=0; int finished=0; int i=0; int ts=T_SLICE; int nop_schedule=0; printf("\n\nRoundRobine running...\n"); set_work_q(); while(finished<N_PROCESS) { if(work_q[i].arrive_time<=timeline && work_q[i].finished_time<0 && work_q[i].need_time!=0) { nop_schedule=0; if( work_q[i].start_time<0) { work_q[i].start_time=timeline; printf("proc%2d started at time %2d.\n",work_q[i].pid, timeline); } if(work_q[i].need_time<=ts) { timeline=timeline + work_q[i].need_time; work_q[i].need_time=0; work_q[i].finished_time=timeline; finished++; printf("proc%2d finished at time %d.\n",work_q[i].pid, timeline); } else { work_q[i].need_time=work_q[i].need_time-ts; timeline+=ts; } } else { nop_schedule++; if (nop_schedule>=N_PROCESS) { timeline++; nop_schedule=0; } } i=(i+1)%N_PROCESS; } AWT("RR"); }