The following is a list of processes Process Arrival Time M

The following is a list of processes:

Process #

Arrival Time

Memory Size

Running Time

Priority

1

0

8K

3

4

2

0

2K

2

3

3

2

3K

6

2

4

3

5K

1

1

5

6

2K

4

4

6

6

1K

2

1

Where arrival time and running time are in seconds, and memory size in K Bytes.

If appropriate, the time quantum = 1 second. Lower Priority values are higher priority.

(Priority 2 is more important than priority 3.)

(When arrival time is the same, select lowest process number first, if more than one

   process can be selected, and there is a new process, use \"most fair\" - allow next a

   new process to run next.

   Please do not “combine” scheduling policies, unless scheduler normally does that.)

(a) (1) Please show the CPU timeline (GANTT chart) for a FCFS scheduler.

      (2) What is the turnaround time for Job 2, and Job 5?

      (3) What is the wait time for Job 2, and Job 5?

(b) Please show the GANTT chart for a Shortest Job Next (SJN) scheduler

          (with no preemption).

(c) Please show the GANTT chart for a SJN scheduler, with preemption.

(d) Please show the GANTT chart for a Round Robin (RR) scheduler.

(e) Please show the GANTT chart for a Priority scheduler, with no preemption.

(f) Please show the GANTT chart for a Priority scheduler, with preemption.

(g) Comparing: 1. FCFS, 2. SJN with preemption, and 3. RR

      (1) What is the turnaround time for process 3?

      (2) What is the throughput for the first 15 seconds?

(h) If there were many additional processes continually entering the queue,

      (1) which scheduler (give one, if possible) could lead to “starvation”?

      (2) How could that happen (if possible)?

Process #	Arrival Time	Memory Size	Running Time	Priority
1	0	8K	3	4
2	0	2K	2	3
3	2	3K	6	2
4	3	5K	1	1
5	6	2K	4	4
6	6	1K	2	1

Solution

a ) FCFS

0 3 5 11 12 16 18

turn around time for job 2 = 5-0 =5sec

turn around time for job 5 = 16-6 = 10 sec

wait time for job 2 = 3-0 = 3sec

wait time for job 5 = 12-6 = 6 sec

b) SJN (with no pre-emption)

0 2 5 6 8 12 18

c)SJN (with preemption)

0 2 3 4 6 8 12 18

d) RR(Quantum =1 sec)

e)priority(no pre-emption)

0 2 8 9 11 14 18

f)priority(with pre-emption)

0 2 3 4 6 8 11 14 18

g) Turn aroound time for process p3

FCFS = 11-2 = 9 sec

SJN(preemptive) = 18-2 = 16 sec

RR = 18-2 = 16sec

Throughput for the first 15 sec

FCFS = 5 jobs/15 sec = 0.33 jobs/sec

SJN(preemptive) =  5 jobs/15 sec = 0.33 jobs/sec

RR = 4 jobs/15 sec = 0.26 jobs/sec

h

Starvation

priority scheduling may lead to starvation of process p1. As the new jobs with higher priority are added p1 may starve.

p1

p2

p3

p4

p5

p6