1
$\begingroup$

If I have a set of processes, let's say 9 and I know the burst time and the waiting time for SJF algorithm and also know that processes arrive in groups of 3 processes at M1 moment, M2 moment, M3 moment (M1, M2 and M3 are given), how can I decide at what moment each process will arrive?

enter image description here

Improve this question
$\endgroup$
8
  • $\begingroup$ @Apass.Jack No. The arrival time. The problem only gives 3 arrival times and I need to figure out what arrival time correspond to each process $\endgroup$
    – Robert
    Commented Jan 13, 2019 at 17:10
  • $\begingroup$ Can you add an accessible reference to the original problem in the question such as a url or its location in a book? An image of the original problem description will do, too. $\endgroup$
    – John L.
    Commented Jan 14, 2019 at 17:09
  • $\begingroup$ @Apass.Jack I added an image of the problem to the post $\endgroup$
    – Robert
    Commented Jan 14, 2019 at 17:48
  • $\begingroup$ Meanwhile, can you find which process was executed first? second? last? Etc. It would be great if you can add your thoughts or partial result to the question. $\endgroup$
    – John L.
    Commented Jan 14, 2019 at 18:28
  • $\begingroup$ I think P4 was executed first because it has 0 waiting time. Also (if I'm not wrong) the turn around time of a process X is equal to the waiting time of a process Y where Y is the successor of X. $\endgroup$
    – Robert
    Commented Jan 14, 2019 at 18:36

1 Answer 1

Reset to default
0
$\begingroup$

What are their execution time and possible start time and finish times? For each process time, its execution time is $\text{TAT}-\text{WT}$. Its start time should be WT plus one of 0, 12 and 24. Its finish time should be TAT plus one of 0, 12, 24.

$$ \begin{array}{|c|c|c|c|c|} \hline \text{Process} & \text{WT} & \text{TAT}&\text{Execution Time} & \text{Start Time} & \text{Finish Time} \\\hline P1 & 6 & 15 &9 & 6, 18, 30 & 15, 27, 39 \\\hline P2 & 3 & 6 &3 & 3, 15, 27 & 6, 18, 30 \\\hline P3 & 63 & 84 & 21 & 63, 75, 87&84, 96, 108 \\\hline P4 & 0 & 6 & 6 & 0& 6\\\hline P5 & 24 & 36 & 12 & 24, 36, 48& 36, 48, 60\\\hline P6 & 7 & 15 & 8 & 7, 19, 31 & 15, 27, 39\\\hline P7 & 24 & 39 & 13 & 24, 36, 48 & 39, 51, 63\\\hline P8 & 6 & 12 & 6 & 6, 18, 30 & 12, 24, 36\\\hline P9 & 3 & 7 & 4 & 3, 15, 27 &7, 19, 31\\\hline \end{array} $$

What can we say about start times and finish times?

  • The start time of any process except the first process must be the finish time of another process.
  • The finish time of any process except the last process must be the start time of another process.

What does it mean by SJF? It means among all jobs that have been queued/submitted, the shortest job will be executed first.

So our task is to select 10 numbers $0, 6, \cdots$ from the column "Start time" and "Finish Time" so that

  • each number must appear in column "Start Time" and column "Finish Time", except the first number 0, which only appears in column "Start Time" and the last number, which only appears in column "Finish time".
  • The sequence starts with 0, 6 since, as you have observed, the first process started at 0 and ended with at 6.
  • For the initial numbers that are not greater than 12, their successive differences should become bigger and bigger. For the next segment of numbers that are not greater than 24, their successive differences should become bigger and bigger. For the last four numbers, their successive differences should become bigger and bigger.

There should be enough hint to set you moving again.

Just in case you are still stuck, move your mouse over the following to reveal the spoiler.

Check the column "Finish Time". Which process must finish last? Then which process' finish time could be the last process' start time? Then which process' finish time could be that process' start time? And so on.

It turns out the condition SJF is not needed at all. This problem can be solved as long as the processes are executed one after another.

On the other hand, SJF can be helpful. The three processes with longest execution time, P3, P5 and P7 must be the last three jobs since all of them started later than 24. Since SJF, $P5\prec P7\prec P3$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Processes arrive in groups of 3 processes, at moments M1, M2, M3. That is what I wanted to say $\endgroup$
    – Robert
    Commented Jan 13, 2019 at 18:25
  • $\begingroup$ Can you give me a hint? $\endgroup$
    – Robert
    Commented Jan 14, 2019 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.