Thread: SJF Scheduling Problem

  1. #1
    Registered User
    Join Date
    Dec 2011
    Posts
    6

    SJF Scheduling Problem

    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:
    SJF Scheduling Problem-46vdb-png

    Here's the input I've been using for this example along with the output of the program:
    SJF Scheduling Problem-uqt1h-png

    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.

  2. #2
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Post your code HERE ... don't be making us go get it... cause most of us won't.

  3. #3
    Registered User
    Join Date
    Dec 2011
    Posts
    6
    Quote Originally Posted by CommonTater View Post
    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
    Last edited by IT_; 12-07-2011 at 11:17 AM.

  4. #4
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Care to try that again... this time with line endings and indentation?

  5. #5
    Registered User
    Join Date
    Dec 2011
    Posts
    6
    Quote Originally Posted by CommonTater View Post
    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.

  6. #6
    Registered User
    Join Date
    Dec 2007
    Posts
    2,675
    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.
    Last edited by rags_to_riches; 12-07-2011 at 12:13 PM.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Dec 2011
    Posts
    6
    Quote Originally Posted by rags_to_riches View Post
    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 View Post
    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.
    Last edited by IT_; 12-07-2011 at 12:29 PM.

  9. #9
    Registered User
    Join Date
    Nov 2011
    Posts
    63
    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.

  10. #10
    Registered User
    Join Date
    Nov 2011
    Posts
    63
    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:

    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
    Last edited by failure67; 12-08-2011 at 12:19 AM.

  11. #11
    Registered User
    Join Date
    Dec 2011
    Posts
    6
    Quote Originally Posted by failure67 View Post
    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! :-)

  12. #12
    Registered User
    Join Date
    Nov 2011
    Posts
    63
    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.

  13. #13
    Registered User
    Join Date
    Dec 2011
    Posts
    6
    Quote Originally Posted by failure67 View Post
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Exam Scheduling Problem
    By itsacezon in forum C Programming
    Replies: 4
    Last Post: 10-19-2011, 09:52 AM
  2. Partition and scheduling HW/SW help!
    By thangdc01_02 in forum C++ Programming
    Replies: 3
    Last Post: 11-18-2010, 02:07 PM
  3. process scheduling
    By lordofdarkness in forum C Programming
    Replies: 0
    Last Post: 03-29-2010, 04:53 PM
  4. Scheduling Policy
    By edesign in forum Linux Programming
    Replies: 9
    Last Post: 05-12-2009, 08:47 PM
  5. Scheduling
    By Jules in forum Tech Board
    Replies: 4
    Last Post: 01-18-2004, 01:47 PM