algorithm help

[COKEDUDE]

I am trying to do Shortest Remaining Time scheduling algorithms turnaround time. This is the formula.

Turnaround Time = Completion Time - Arrival Time

I have already sorted my arrays.

This is what it looks like my hand.

5,1 done with magical 0
9,2 2nd iteration     1
2,4 1st iteration      2
0,7  done because first  3


0 to 7, 7 to 11, 11 to 12, 12 to 14

7          9        7           5

Turnaround Time = Completion Time - Arrival Time


1        3        2        4
0 to 7, 7 to 8, 8 to 12, 12 to 14
7         3       10      5

My issue is the backtracking to the 9,2. Since it hasn't arrived yet you have to skip it. 9 is the arrival time and 2 is how much time it takes to process. It has A LOT of print statements because I have been trying to figure out what is going on.

for(j = 1; j < i; j++)
    {
        printf("kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk \n");
        printf("j is %d abcd \n", j);
        printf("arrival_time_array is %d\n", arrival_time_array[1]);
        printf("time_cycles_required_for_job_array is %d\n", time_cycles_required_for_job_array[1]);
        printf("completion_time[1] above while: %d \n",completion_time[1]);
        printf("aaacompletion_time[j]: %d \n",completion_time[j]);
        printf("%d %d\n", magical_completion_time ,arrival_time_array[j]);
        printf("arrival_time_array[j] is %d \n", arrival_time_array[j]);
        printf("kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk \n");
        if(completed_flag[j] != 1)
        {
        printf("%d %d\n", completion_time[j] ,arrival_time_array[j]);
        printf("bbbcompletion_time[j]: %d \n",completion_time[j]);
        if(magical_completion_time >= arrival_time_array[j])
        {
            printf("j is %d \n", j);
            printf("%d %d\n", completion_time[j] ,arrival_time_array[j]);
            printf("arrival_time_array is %d\n", arrival_time_array[j]);
            printf("time_cycles_required_for_job_array is %d\n", time_cycles_required_for_job_array[j]);
            printf("completion_time[j] is %d\n", completion_time[j]);
            completion_time[j+1] = magical_completion_time + time_cycles_required_for_job_array[j+1];
            magical_completion_time = completion_time[j];
            completed_flag[j] = 1;
            printf("setting completed_flag[j] at j which is: %d \n",j);
            printf("yyycompletion_time[j]: %d \n",completion_time[j]);
        }
        else
        {
            printf("j is %d \n", j);
            printf("In the else:  \n");
            printf("magical_completion_time is  %d \n", magical_completion_time);
            printf("completion_time[j]: %d \n",completion_time[j]);
            printf("time_cycles_required_for_job_array[j]: %d \n",time_cycles_required_for_job_array[j+1]);
            completion_time[j+1] = magical_completion_time + time_cycles_required_for_job_array[j+1];
            magical_completion_time = completion_time[j+1];
            printf("xxxcompletion_time[j+1]: %d \n",completion_time[j+1]);
            completed_flag[j+1] = 1;
            printf("setting completed_flag[j+1] at j + 1 which is: %d \n",j + 1);
            j = 1;
        }
        }
        printf("j is %d \n", j);
    }

[Taywin]

Before you attempt to calculate with program, do it by your hand first. You need to ID each process. I am going to assume as follows:

Arrival time 0 is ID 1 (processing time 7)
Arrival time 2 is ID 2 (processing time 4)
Arrival time 5 is ID 3 (processing time 1)
Arrival time 9 is ID 4 (processing time 2)

Now, I am going to create a time table regarding the information given, but it will associate time unit (TU), arriving ID (AID), processing ID (PID), process time left (PTL), and waiting queue with remaining processing time (WQ+T).

TU   AID  PID  PTL  WQ+T
 0    1    1    7   []
 2    2    2    4   [1=>5]
 5    3    2    1   [1=>5, 3=>1]
 6    -    3    1   [1=>5]
 7    -    1    5   []
 9    4    4    2   [1=>3]
11    -    1    3   []
14    -    -    -   []

Now the explanation.

Line 2, at time unit 0, process ID 1 arrives. It will immediately be put into process. The remaining processing time is 7 at time unit 0. There is no process waiting in the queue.

Line 3, at time unit 2, process ID 2 arrives. Because process ID 2 has shorter processing time (4) compared to process ID 1 remaining processing time (5), CPU should put process ID 1 into waiting queue, and let process ID 2 being processed.

Line 4, at time unit 5, process ID 3 arrives. This is a tie between process ID 2 and 3 (1 time unit for processing time). There are 2 ways to deal with this -- one is to compare ID and pick one (either lowest or highest ID number) to process, or to keep the processing one in place and put the new arrival into the queue. I use the latter.

Line 5, at time unit 6, process ID 2 has done its job, so it is removed. Then the CPU picks the shortest remaining time to process in the queue because there is no new process arriving, and it is process ID 3.

Line 6, at time unit 7, process ID 3 has done its job, so it is removed. Then the CPU picks the shortest remaining time to process in the queue, and of course it is process ID 1.

Line 7, at time unit 9, process ID 4 arrives. Because process ID 1 still has 3 time unit left to process, it has to give way to process ID 4. Thus, process ID 4 is in CPU and process ID 1 goes back to the queue.

Line 8, at time unit 11, process ID 4 is done, so it is removed. Now CPU takes back process ID 1 to continue processing.

Line 9, at time unit 14, process ID 1 is done, so it is removed. No other process is waiting or arriving, so it is done.

Next, do some calculation. Process ID 1 arrives at time unit 0 but finishes at time unit 14, so Turn around time (TAT) is 14-0 => 14. Process ID 2 arrives at time unit 2 and exits at time unit 6, so TAT is 6-2 => 4. Process ID 3 arrives at time unit 5 and exits at time unit 7, so TAT is 7-5 => 2. Last, process ID 4 arrives at time unit 9 and exits at time unit 11, so TAT is 11-9 => 2.

As you can see, your simple for-loop iteration with sorted process array will not cut it. You need to understand how each process arrives at what time unit, and then you need to figure out which process should be processing and which should be waiting in a queue. A simpliest way (brute-force) is to tick the time unit up by 1. Each tick, you check for any event occurs at the time unit (i.e. process arrival and process done from CPU). Then you have to appropriately deal with whatever event occurs at the time unit.

Hope this help...