SJF Scheduling Problem

2 Attachment(s)

My code is 99% complete but it doesn't print out the correct output. I know there is a simple problem here that I'm going to bang my head over, but I just can't find it.

Here's my code: C code - 149 lines - codepad

Here's a Gantt Chart that i did in excel to predict my output:
Attachment 11187

Here's the input I've been using for this example along with the output of the program:
Attachment 11188

As you can see, according to my Gantt chart, the second process to run should be P3, but the program I wrote picks P4. I've been over it many times and I know it has to be something simple, I just can't find it.

If anyone can help enlighten me, I would be eternally grateful.

Thank you very much.

Post your code HERE ... don't be making us go get it... cause most of us won't.

Quote:

Originally Posted by CommonTater

Post your code HERE ... don't be making us go get it... cause most of us won't.

My apologies, I didn't think clicking a single link would be a problem. I wanted to keep the post as uncluttered as possible. As requested though, here's my code.

edit, fixed formatting

Code:

//Shortest Job First Scheduling #include <stdio.h> #include <stdlib.h> #include <string.h> /*Define Structure with Variables*/ typedef struct { char pid[10]; /* Process ID */ int arr; /* Arrival */ int brt; /* Burst */ int rmt; /* Runtime */ int wt; /* Wait Time */ int tat; /* Total TIme */ int active; /* Active Process */ int finish; /* Finish */ }prc; /*Main Function*/ int main () { /*Define Variables*/ int i, j, l, lq; /* Count and temp varialbes */ int startp, totalt, endt; /* Start Process, Total Time, End Time varialbes */ int num; /* Number of Processes varialbe */ int startt; /* Start Time */ int remaint, tmp, tmp1; /* Remaining Time and Temps */ int fakep = 9999; /* Idle CPU Time Check */ int pr[100], cpr[100], que[100];/* process, current process, and que */ prc p[100]; /* Structure */ /*Obtain User Input*/ printf("Enter the number of processes: "); scanf("%d", &num); /*Init Start and Total Time*/ startt = 9999; totalt = 0; /*Obtain User Input based on the number of processes entered*/ for (i=0;i<num;i++) { printf("Enter the Process Name, Arrival Time, and Burst Time: "); scanf("%s%d%d", &p[i].pid, &p[i].arr, &p[i].brt); p[i].rmt = p[i].brt; p[i].wt = 0; p[i].tat = 0; p[i].active = 0; p[i].finish = 0; /*Check for the lowest arrival time to determine the start time*/ if(p[i].arr < startt) { startt = p[i].arr; startp = i; }//end if /*Calculate the Total time by adding all of the burst times*/ totalt += p[i].brt; }//end for /*Calculate the end time by adding the start and total times together*/ endt = startt + totalt; //printf("After Input \n"); /***** SJF ALGORITHM *****/ lq = 0; for(i=0;i<startt;i++) cpr[i] = fakep; l = i; cpr[l] = startp; p[cpr[l]].active = 1; while (lq >= 0) { for(i=0;i<num;i++) { if((p[i].active==0)&&(p[i].finish==0)&&(p[i].arr==l)) { if(lq == 0) { que[lq] = i; }//end if else { tmp = i; for(j=0;j>lq;j++) { if (p[tmp].brt > p[que[j]].brt) { tmp1 = tmp; tmp = que[j]; que[j] = tmp1; }//end if }//end for que[lq] = tmp; }//end else lq++; }//end if }//end for remaint = p[cpr[l]].rmt - 1; l++; if(remaint > 0) { cpr[l] = cpr[l-1]; p[cpr[l]].rmt = remaint; }//end if else { lq--; if(lq >= 0) { cpr[l] = que[lq]; p[cpr[l-1]].finish = 1; p[cpr[l]].active = 1; }//end if }//end else }//end while /*Print the Gantt Chart*/ printf("\nGantt Chart:\n"); // Run for i less than endtime plus 1, print the timeline for (i=0; i<endt+1;i++) printf("%2d ",i); printf("\n"); // Run for i less than end time for (i=0; i<endt;i++) { //print a space for idle cpu time if(cpr[i] == fakep) printf(" "); else //print the pid for the process printf(" %s", p[cpr[i]].pid); }//end for printf("\n"); }//end main

Care to try that again... this time with line endings and indentation?

Quote:

Originally Posted by CommonTater

Care to try that again... this time with line endings and indentation?

Not sure what else I can do to make it prettier. I'm pasting right out of g editor into this with the proper tags. it looks good and easy to read on my codepad link however.

You have some warnings you should take care of:

Code:

jf.c: In function ‘main’: sjf.c:50: warning: format ‘%s’ expects type ‘char *’, but argument 2 has type ‘char (*)[10]’ sjf.c:33: warning: unused variable ‘pr’ sjf.c:149: warning: control reaches end of non-void function

The lack of comments and poor variable naming, coupled with my complete lack of knowledge of SJF, means I can't help you further.

Would suggest stepping into the code in the debugger. Best course of action for this kind of algorithmic issue.

Yeah I've never understood how when someone post code it completly disables the usual syntax hilighting.
Perhaps make sure what you're pasting is plain text, not formatted text. The best way to do that is to paste it into notepad and then copy it out again from there, then post it.

Quote:

Originally Posted by rags_to_riches

You have some warnings you should take care of:

Code:

jf.c: In function ‘main’: sjf.c:50: warning: format ‘%s’ expects type ‘char *’, but argument 2 has type ‘char (*)[10]’ sjf.c:33: warning: unused variable ‘pr’ sjf.c:149: warning: control reaches end of non-void function

The lack of comments and poor variable naming, coupled with my complete lack of knowledge of SJF, means I can't help you further.

Would suggest stepping into the code in the debugger. Best course of action for this kind of algorithmic issue.

Yea, sorry. I'm pretty new to this stuff. I'm learning from many different sources to proper coding is sort of lost. As for the warning, when I compile with gcc the only one I get is the formatting error. i'm going to fix that, but it does compile and run. I just get the wrong input. I think i have something switched somewhere. Just haven't been able to find it.

Quote:

Originally Posted by iMalc

Yeah I've never understood how when someone post code it completly disables the usual syntax hilighting.
Perhaps make sure what you're pasting is plain text, not formatted text. The best way to do that is to paste it into notepad and then copy it out again from there, then post it.

Might it have something to do with me coming from a Linux machine? The only way I was able to get it to work without printing everything in a paragraph with no line breaks whatsoever was to copy from my codepad link.

[edit] tried copy and pasting from different sources and still no go.

Your Gantt chart is slightly wrong. P1 has 6 units of work and shows up at t = 1. It should finish at 1 + 6 = 7 (At the beginning of the seventh time unit). Here's how it should be

0-1: idle
1-7: p1
7-8: p3
8-11: p2
11-14: p4

I'm looking through the code now.

Here are a few things that I see are wrong:

1) main does not return 0
2) On line 50, &p[i].pid should be p[i].pid
3) You need to check for the final arrival time. If p4 in your example arrived at t = 16, your algorithm for calculating the end time gives incorrect results.
4) I could be wrong, but perhaps "the something simple" is this:

Code:

for(j=0;j>lq;j++) /* Should that be a < sign? */

That's line 95.

Just by implementing 1, 2, and 4, I got this output:

Quote:

Enter the number of processes: 4
Enter the Process Name, Arrival Time, and Burst Time: p1 1 6
Enter the Process Name, Arrival Time, and Burst Time: p2 3 3
Enter the Process Name, Arrival Time, and Burst Time: p3 4 1
Enter the Process Name, Arrival Time, and Burst Time: p4 5 3

Gantt Chart:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
p1 p1 p1 p1 p1 p1 p3 p4 p4 p4 p2 p2 p2

Quote:

Originally Posted by failure67

Your Gantt chart is slightly wrong. P1 has 6 units of work and shows up at t = 1. It should finish at 1 + 6 = 7 (At the beginning of the seventh time unit). Here's how it should be

0-1: idle
1-7: p1
7-8: p3
8-11: p2
11-14: p4

I'm looking through the code now.

Thank you, I'd appreciate any help I could get. I tried going through it over and over again with a buddy of mine, but we can't figure out why it's choosing P4 over P3. I see what I did wrong with my Gantt chart as well. Thank you for pointing that out! :-)

I updated my last post. Flipping the > sign into a < sign on line 95 fixes most of your problems of it choosing the wrong process. You still need to redo how you calculate your end time though because of the reasons I mentioned beforehand.

Quote:

Originally Posted by failure67

I updated my last post. Flipping the > sign into a < sign on line 95 fixes most of your problems of it choosing the wrong process. You still need to redo how you calculate your end time though because of the reasons I mentioned beforehand.

THANK YOU!!!!!!!!!

I knew it was something simple. You can't get more simple than that, that's for sure. You are a God amongst men and thank you once again for your help!