Title	CPU Scheduling algorithm implementation
Author:	Boopathi Visitor Submitted Source Code
Author Email:	kmb6983@yahoo.co.in
Description:
Hits:	8945 Since 25th November, 2003
Code:	Select and Copy the Code #include<stdio.h> #include<conio.h> #include<dos.h> #include<graphics.h> #define N 100 struct processors //PROCESS ATTRIBUTES// { float burst; float arrival; int priority; int num; }p[20],temp; struct ssss { int no; int xx; float arr; float burst; float ww; int pri; float wait; }process[N]; void main() { void fcfs(int); void sjfp(int); void sjfnp(int); void priority(int); void roundrobin(int); void doneby(); //void graphics(float *,float,int); int i,j,c,n;float left,right,top,bottom; /* select a driver and mode that supports */ /* multiple background colors. */ int gdriver = EGA, gmode = EGAHI, errorcode; int bkcol, maxcolor, x, y; char msg[80]; /* initialize graphics and local variables */ initgraph(&gdriver, &gmode, "C:\\TC\\BGI"); /* read result of initialization */ errorcode = graphresult(); if (errorcode != grOk) /* an error occurred */ { printf("Graphics error: %s\n", grapherrormsg(errorcode)); printf("Press any key to halt:"); getch(); exit(1); /* terminate with an error code */ } cleardevice();//Gets the input from the user// printf("ENTER THE NUMBER OF PROCESSES:\t"); scanf("%d",&n); for(i=0;i<n;i++) { gotoxy(22,2); printf("PROCESS:%d\n",i+1); printf("BURST TIME :\t"); scanf("%f",&p[i].burst); printf("ARRIVAL TIME :\t"); scanf("%f",&p[i].arrival); printf("PRIORITY :\t"); scanf("%d",&p[i].priority); p[i].num = i+1; if(p[i].arrival < 0 || p[i].burst <=0 || p[i].priority > n || p[i].burst > 40) { printf("\n\nINVALID INPUT\n"); printf("PLEASE RE ENTER THE PARAMETERS FOR PROCESS %d",i+1); i--; getch(); } cleardevice(); } for(i=0;i<n;i++) { for(j=i;j<n;j++) { if(p[i].arrival > p[j].arrival) { temp = p[i]; p[i] = p[j]; p[j] = temp; } } } cleardevice(); gotoxy(22,2); //Selects the scheduling algorithm printf("CPU SCHEDULING\n"); printf("1.FCFS scheduling\n"); printf("2.SHORTEST JOB FIRST pre emptve scheduling\n"); printf("3.SHORTEST JOB FIRST non preemptive scheduling\n"); printf("4.PRIORITY scheduling\n"); printf("5.ROUND ROBIN scheduling\n"); printf("ENTER YOUR CHOICE:\t"); scanf("%d",&c); switch(c) { case 1: { fcfs(n); break; } case 2: { sjfp(n); break; } case 3: { sjfnp(n); break; } case 4: { priority(n); break; } case 5: { roundrobin(n); break; } } getch(); } //FCFS scheduling void fcfs(int n) { int i,w,y=0,pr[30],l=0; float awt = 0,wt[10],s=0,q=0,g[100]; void graphics(float *,float,int,float *,int,int *,int);//graphics declaration cleardevice(); gotoxy(22,2); g[y++] = s; g[y++] = 0; g[y++] = s = p[0].arrival; g[y++] = p[0].num; //g[] is declared to implement graphics g[y++] = s = s + p[0].burst; //first process is completed for(i=1;i<n;i++) { if(p[i].arrival>s) //Checks for idle time { wt[i] = 0; g[y++] = 0; g[y++] = s = p[i].arrival; g[y++] = p[i].num; g[y++] = s = s + p[i].burst; } else { g[y++] = p[i].num; //completes the i th process g[y++] = s = s + p[i].burst; wt[i] = s - p[i].arrival - p[i].burst; } } g[y++] = p[i-1].num; for(i=1;i<n;i++) { q = q + wt[i]; //Calculates the sum of all the process's waiting time } awt = q/n; //Calculates average waitiing time graphics(&wt,awt,n,&g,y,&pr,l); outtextxy(200,0,"FOR FCFS SCHEDULING"); getch(); } //SJF non pre emption void sjfnp(int n) { int i,w,j,z,d=0,o,h,k,c,m=0,u,y=0,l=0,pr[30]; float awt = 0,s=0,wt[10],q=0,g[100]; void graphics(float *,float,int,float *,int,int *,int); p[n].arrival = -564; //Finds the no.of processes that arrive along with the first process for(i=0;i<n;i++) { if(p[0].arrival == p[i+1].arrival) { m++; } } //Sorts the above processes in ASC of burst time for(i=0;i<=m;i++) { for(j=i;j<=m;j++) { if(p[i].burst > p[j].burst) { temp = p[j]; p[j] = p[i]; p[i] = temp; } } } cleardevice(); g[y++] = s; g[y++] = 0; g[y++] = s = p[0].arrival; wt[0] = 0; g[y++] = p[0].num; g[y++] = s = s + p[0].burst; z=1;i=1; while(i<n) //keeps track of the no.of processes completed { c = z; for(j=z;j<n;j++) //selects the batch of processes to be considered further { if(s>=p[j].arrival) //considers the processes that has arrived before { //the completion of the current process d = d + 1; } else if(s<p[j].arrival && c==z) //checks for idle time { d = d + 1; g[y++] = 0; g[y++] = s = p[j].arrival; } c++; } for(o=z;o<=d;o++) //sorts the selected processes in ASC order { for(h=o;h<=d;h++) { if(p[o].burst > p[h].burst) { temp = p[o]; p[o] = p[h]; p[h] = temp; } } } for(k=z;k<=d;k++) //allocates the CPU to the processes { g[y++] = p[k].num; g[y++] = s = s + p[k].burst; for(i=d+1;i<=n;i++) //checks whether any other process has { //arrived in between if(s >= p[i].arrival) { u = 1; } if(u==1) break; } wt[k] = s - p[k].burst - p[k].arrival; q = q + wt[k]; if(u==1) { z=k+1; d=k; i=z; break; } } if(u!=1) { z = d + 1; i = z; } } g[y++] = s + p[n].burst; g[y] = p[n].num; //getch(); awt = q/n; //Calculates average waiting time graphics(&wt,awt,n,&g,y,&pr,l); outtextxy(200,0,"FOR SJFNP SCHEDULING"); getch(); } //PRIORITY SCHEDULING ALGORITHM void priority(int n) { int i,w,j,z,y=0,l=0,pr[30]; float awt = 0,q=0,s=0,wt[10],g[100]; void graphics(float *,float,int,float *,int,int *,int); //clrscr(); cleardevice(); g[y++] = 0; //printf("%f ",s); g[y++] = p[0].num; g[y++] = s = 0; gotoxy(22,12); wt[0] = 0; for(i=0;i<n;i++) //Sorts the processes w.r.t priority { for(j=0;j<n;j++) { if(p[i].priority < p[j].priority) { temp = p[i]; p[i] = p[j]; p[j] = temp; } } } for(i=0;i<n;i++) // calculates waiting time of each process { g[y++] = p[i].num; g[y++] = s = s + p[i].burst; //printf("%f ",s); wt[i] = s - p[i].burst; //getch(); q = q + wt[i]; } g[y++] = p[i-1].num; awt = q/n; graphics(&wt,awt,n,&g,y,&pr,l); outtextxy(200,0,"FOR PRIORITY SCHEDULING"); getch(); } //ROUND ROBIN ALGORITHM void roundrobin(int n) { int i,j,l=0,pr[30];float tot[10]={1,1,1,1,1,1,1,1,1,1},s[10]={0,0,0,0,0,0,0,0,0,0},c=1,y=0; float q,awt,total=0,wt[10]={0,0,0,0,0,0,0,0,0,0},g[400]; void graphics(float *,float,int,float *,int,int *,int); cleardevice(); printf("Enter the time quantum: "); scanf("%f",&q); for(i=0;i<n;i++) { tot[i] = p[i].burst; } g[y++] = total; g[y++] = 0; g[y++] = total = total + p[0].arrival; while(c<=n) //Keeps track of the processes that are completed { for(i=0;i<n;j++)//Performs the round robin function { if(tot[i]>0) //Checks whether the process is over or not { tot[i] = tot[i] - q; //decreases the burst time by the //time quantum if(tot[i]<=0) // checks whether this is the last //round for this process { g[y++] = p[i].num; g[y++] = total = total + tot[i] + q; //calculates the waiting time of the proces wt[i] = total - p[i].burst - p[i].arrival; //checks whether a process has arrived in the mean time if(total>=p[i+1].arrival) { i++; } else { i=0; } c++; } else { g[y++] = p[i].num; g[y++] = total = total + q; while(tot[i+1]<=0)//increments 'i' till it reaches an incomplete i++; //process if(total>=p[i+1].arrival) { i++; } else { i=0; } } } else { i++; if(p[i].arrival > total) //checks for idle time { if(i<=n) { g[y++] = 0; g[y++] = total = p[i].arrival; } else if(i==n-1 && c==n-1) { g[y++] = 0; g[y++] = total = p[i].arrival; } } } } } g[y++] = p[i-1].num; q=0; for(i=0;i<n;i++) //calculates average waiting time { //printf("%d. %f\n",p[i].num,wt[i]); q = q + wt[i]; } awt = q/n; graphics(&wt,awt,n,&g,y,&pr,l); outtextxy(200,0,"FOR ROUND ROBIN SCHEDULING"); getch(); } void graphics(float *wt,float awt,int n,float *g,int y,int *pr,int l) { int i,msg1=0,j=0,u=0; char msg[30]; float left,right,top,bottom,awd=0,turn=0,d=0; getch(); cleardevice(); setlinestyle(4, 1, 1); setfillstyle(10,1); bar3d(0,0,620,340,0,0); line(0, 2, 618, 2); line(2,2,2,338); line(2,338,618,338); line(618,338,618,2); setlinestyle(0,1,1); left = 0; top = 40; bottom = 80; right = 15; for(i=0;i<y;i++) { left = right; right = *(g+i); right = (15-j) * (right - u); bar3d(left,top,right,bottom,0,0); sprintf(msg,"%2.1f",*(g+i)); outtextxy(right,(82+msg1),msg); i++; setfillstyle(1,*(g+i)); if(right>=600) { right = 0; top = 120; bottom = 160; msg1 = 82;u= *(g+i-1); i--; outtextxy(right,164,msg); i++; } delay(500); } setcolor(CYAN+BLINK); settextstyle(DEFAULT_FONT, HORIZ_DIR, 0); sprintf(msg,"AVERAGE WAITING TIME : %f",awt); outtextxy(20,30,msg); for(i=0;i<n;i++) { d = d + p[i].burst; } awd = d/n; turn = awd + awt; //settextstyle(DEFAULT_FONT, HORIZ_DIR, 4); sprintf(msg,"AVERAGE TURN AROUND TIME : %f",turn); outtextxy(300,30,msg); setcolor(WHITE); sprintf(msg,"PROCESS"); outtextxy(32,210,msg); sprintf(msg,"WAITING TIME"); outtextxy(190,210,msg); outtextxy(340,210,"COLORS"); outtextxy(410,210,"IDLE"); setfillstyle(1,0); bar3d(455,206,515,216,0,0); for(i=0;i<n;i++) { sprintf(msg,"%d.",p[i].num); outtextxy(48,226+(i*17),msg); sprintf(msg,"%f",*(wt+i)); outtextxy(208,226+(i*17),msg); if(i==6) break; } //getch(); //cleardevice(); /*for(i=7;i<n;i++) { sprintf(msg,"%d.",p[i].num); outtextxy(48,226+((i-7)*17),msg); sprintf(msg,"%f",*(wt+i)); outtextxy(208,226+((i-7)*17),msg); } */ for(i=0;i<n;i++) { setfillstyle(1,p[i].num); bar3d(330,225+(i*17),390,235+(i*17),0,0); if(i==6) break; } settextstyle(TRIPLEX_FONT, HORIZ_DIR,2 ); outtextxy(50,0,"GANTT CHART"); if(n>=7) { getch(); cleardevice(); settextstyle(DEFAULT_FONT,HORIZ_DIR,0); sprintf(msg,"PROCESS"); outtextxy(32,10,msg); sprintf(msg,"WAITING TIME"); outtextxy(190,10,msg); outtextxy(340,10,"COLORS"); outtextxy(410,10,"IDLE"); setfillstyle(1,0); bar3d(455,6,515,16,0,0); for(i=7;i<n;i++) { sprintf(msg,"%d.",p[i].num); outtextxy(48,26+((i-7)*17),msg); sprintf(msg,"%f",*(wt+i)); outtextxy(208,26+((i-7)*17),msg); } for(i=7;i<n;i++) { setfillstyle(1,p[i].num); bar3d(330,25+((i-7)*17),390,35+((i-7)*17),0,0); } } getch(); } void sjfp(int k) { void graphics1(float *,float,int,float *,int); int i,j,s,l,m,c,t,r,z,order[N],g[N],q[N]; float left,right,b,cc[N],timslice,ara,awt,cat,la,kb,tw,tr,imp[N],shortest,test,i nfo[400]; tw=tr=test=0; c=0; s=0; clrscr(); cleardevice(); for(i=0;i<k;i++) { process[i].xx=i; //INITIALIZE ALL VARIABLES , NAMELY// process[i].arr=p[i].arrival; //PROCESS[I].XX->ORDER OF THE PROCESS I// process[i].no=p[i].num; // IN THE ARRAY OF PROCESSES// process[i].burst=p[i].burst; // ALSO INITIALIZE PROCESS BURSTS,NUMBERS,..// imp[i]=p[i].burst; test=test+imp[i]; process[i].wait=0; process[i].ww=0; printf("\n\n"); } for(i=0;i<k-1;i++) { //CREATE AN ARRAY ORDER OF K ELEMENTS// order[i]=process[i].xx; // TO SORT THE K PROCESSES// if(process[i].arr==process[i+1].arr) //INITIALIZE THE ORDER ARRAY TO // c=c+1; // ORDER OF PROCESSES// } order[k-1]=process[k-1].xx; if(c==k-1) // CHECK IF," ALL THE K PROCESSES" ARRIVE// { // AT SAME TIME// for(i=0;i<k-1;i++) { // IF SO, THEN SORT THEM ON THE// for(j=0;j<k-i;j++) //BASIS OF THEIR CPU BURSTS// { if(j!=k-1) { if(process[order[j]].burst>process[order[j+1]].burst) { t=process[order[j+1]].xx; order[j+1]=process[order[j]].xx; order[j]=t; } // USING BUBBLE-SORT TECHNIQUE// } } } } else { for(i=0;i<k-1;i++) { for(j=0;j<k-i;j++) // IF ALL,'K' PROCESSES DO NOT ARRIVE// { //AT SAME TIME ,SORT THEM// if(j!=k-1) //ON THE BASIS OF THEIR BURSTS // { if(process[order[j]].arr>process[order[j+1]].arr) { t=process[order[j+1]].xx; order[j+1]=process[order[j]].xx; //USING BUBBLE-SORT TECHNIQUE// order[j]=t; } else if(process[order[j]].arr==process[order[j+1]].arr) { if(process[order[j]].burst>process[order[j+1]].burst) { t=process[order[j+1]].xx; // IF 2 PROCESSES ARRIVE AT SAME// order[j+1]=process[order[j]].xx; //TIME , SORT THEM ON THEIR // order[j]=t; //BURSTS// } } } } } } ara=process[order[k-1]].arr; // ARA -> LAST PROCESS'S ARRIVAL TIME// la = 0; info[s++]=0; info[s++]=0; //FIX LA AS THE TIME-BASE// la=process[order[0]].arr; //LA-> FIRST PROCESS'S ARRIVAL TIME// info[s++] = la; kb=la; while(test!=0) //TEST-> SUM OF ALL PROCESS'S BURSTS// { j=r=0; for(i=0;i<k;i++) { if((process[order[i]].arr <= la)&&(process[order[i]].burst!=0)) { g[j]=order[i]; // FIND THE ARRAY G OF ALL PROCESSES// j=j+1; // WHICH ARRIVE BEFORE LA // } else if((process[order[i]].arr > la)&&(process[order[i]].burst!=0)) { q[r]=order[i]; // FIND THE ARRAY Q OF ALL PROCESSES// r=r+1; //WHICH ARRIVE AFTER LA// } else b=0; } if(la<ara) // IF LA(CURRENT TIME INSTANT) < ARA(LAST PROCESS'S ARRIVAL TIME // { // DO SJF PRE-EMPTION// if(j!=0) { timslice=process[q[0]].arr-la; //TIMSLICE->TIME FOR WHICH A PROCESS// c=q[0]; // IS TO BE EXECUTED// shortest=process[g[0]].burst; m=g[0]; for(l=0;l<j;l++) //IF ATLEAST ONE OR MORE PROCESSES// { //HAVE ARRIVED BEFORE LA// if(process[g[l]].burst!=0) // FIND THE SHORTEST OF THEM ALL// { //LET M CONTAIN THE ORDER VALUE OF// if(process[g[l]].burst<shortest) //THE SHORTEST PROCESS// { shortest=process[g[l]].burst; m=g[l]; } } } } else { //IF NO PROCESS HAS ARRIVED BEFORE LA// if((r>1)&&(process[q[1]].arr!=process[q[0]].arr)) { c=q[1]; // THEN, FIND THE SHORTEST OF ALL THOSE PROCESSES// timslice=process[q[1]].arr-la; // WHICH ARE YET TO ARRIVE AFTER LA// m=q[0]; } else if((r==1)||(process[q[1]].arr==process[q[0]].arr)) { timslice=process[q[0]].burst; m=c=q[0]; } else b=0; } if(la<process[m].arr) // IF NO PROCESS IS AVAILABLE TO EXECUTE// { printf("\n CPU SITS IDLE FROM %f ms TO %f ms",la,process[m].arr); la=process[m].arr; kb=la; //AND IF THE NEXT PROCESS ARRIVES AFTER LA SECONDS// info[s++]=0; // CPU SITS IDLE UNTIL IT ARRIVES// info[s++]=process[m].arr; if(r>1) timslice=process[c].arr-la; else if(r==1) timslice=process[c].burst; else b=0; } } else // IF ALL ,'K'PROCESSES HAVE ARRIVED // { for(t=0;t<k;t++) // SJF PRE-EMPTION REDUCES TO THAT WITH NO PRE-EMPTION// { if(process[t].burst!=0) { shortest=process[t].burst; timslice=shortest; m=t; } } for(l=0;l<k;l++) // FIND THE SHORTEST OF ALL PROCESSES AVAILABLE // { if(process[order[l]].burst!=0) { if(process[order[l]].burst<shortest) { shortest=process[order[l]].burst; m=order[l]; timslice=shortest; } } } } if(process[m].burst!=0) { if(process[m].burst<timslice) //COMPUTE THE NET WAITING TIME// { //FOR PROCESS I// process[m].ww=la+process[m].wait-process[m].arr; process[m].wait=la-process[m].arr; la=la+process[m].burst; printf("\n PROCESS P%d IS EXECUTED FROM %f ms TO %f ms",process[m].no,kb,la); if(s>3) { if(info[s-2]!=process[m].no) { info[s++]=process[m].no; info[s++]=la; } else { info[s-1]=la; } } else { info[s++]=process[m].no; info[s++]=la; } tw=tw+process[m].wait; kb=la; process[m].burst=0; } else { process[m].ww=process[m].wait+la-process[m].arr; process[m].wait=la-process[m].arr; la=la+timslice; printf("\n PROCESS P%d IS EXECUTED FROM %f ms TO %f ms",process[m].no,kb,la); if(s>3) { if(info[s-2]!=process[m].no) { info[s++]=process[m].no; info[s++]=la; } else { info[s-1]=la; } } else { info[s++]=process[m].no; info[s++]=la; } process[m].burst=process[m].burst+kb; process[m].burst=process[m].burst-la; tw=tw+process[m].wait; kb=la; process[m].arr=kb; } } b=0; for(t=0;t<k;t++) { b=b+process[t].burst; } test=b; // UPDATE TEST TO THE NEW SUM OF ALL PROCESS'S CPU BURSTS // } for(i=0;i<k;i++) // COMPUTE THE TOTAL TURN-AROUND TIME// { cc[i]=process[i].ww; tr = tr + imp[i]; printf("\n WAITING TIME OF PROCESS P%d IS %f ms",process[i].no,cc[i]); } awt=tw/k; cat=(tw+tr)/k; printf("\n AVERAGE WAITING TIME : %f ms",awt); printf("\n AVERAGE TURN AROUND TIME : %f ms",cat); printf("\n\n"); graphics1(&cc,awt,k,&info,s); outtextxy(200,0,"FOR SJF PREEMPTIVE SCHEDULING"); getch(); } void graphics1(float *cc,float awt,int k,float *info,int s) { int i,msg1=0,j=0,u=0; char msg[30]; float left,right,top,bottom; getch(); cleardevice(); left = 0; top = 40; bottom = 80; right = 0; for(i=0;i<s;i++) { left = right; right = *(info+i); right = (15-j) * (right - u); bar3d(left,top,right,bottom,0,0); sprintf(msg,"%2.1f",*(info+i)); outtextxy(right,(82+msg1),msg); i++; setfillstyle(1,*(info+i)); if(right>=600) { right = 0; top = 120; bottom = 160; msg1 = 82;u= *(info+i-1); i--; outtextxy(right,164,msg); i++; } delay(100); } sprintf(msg,"PROCESS"); outtextxy(32,210,msg); sprintf(msg,"WAITING TIME"); outtextxy(190,210,msg); outtextxy(340,210,"COLORS"); outtextxy(410,210,"IDLE"); setfillstyle(1,0); bar3d(455,206,515,216,0,0); for(i=0;i<k;i++) { sprintf(msg,"%d.",process[i].no); outtextxy(48,226+(i*17),msg); sprintf(msg,"%f",*(cc+i)); outtextxy(208,226+(i*17),msg); if(i==6) break; } for(i=0;i<k;i++) { setfillstyle(1,process[i].no); bar3d(330,225+(i*17),390,235+(i*17),0,0); if(i==6) break; } settextstyle(TRIPLEX_FONT, HORIZ_DIR,2 ); outtextxy(50,0,"GANTT CHART"); if(k>=7) { getch(); cleardevice(); settextstyle(DEFAULT_FONT,HORIZ_DIR,0); sprintf(msg,"PROCESS"); outtextxy(32,10,msg); sprintf(msg,"WAITING TIME"); outtextxy(190,10,msg); outtextxy(340,10,"COLORS"); outtextxy(410,10,"IDLE"); setfillstyle(1,0); bar3d(455,6,515,16,0,0); for(i=7;i<k;i++) { sprintf(msg,"%d.",process[i].no); outtextxy(48,26+((i-7)*17),msg); sprintf(msg,"%f",*(cc+i)); outtextxy(208,26+((i-7)*17),msg); } for(i=7;i<k;i++) { setfillstyle(1,process[i].no); bar3d(330,25+((i-7)*17),390,35+((i-7)*17),0,0); } } }