SME
Operating Systems
Scheduling
Use this for “Four jobs of 10, 4, 2 and 6 ms arrive together. Compare FCFS and SJF waiting times.”
Diagram
FCFS: waits 0, 10, 14, 16, average 10 ms; average turnaround 15.5 ms.
SJF: waits 12, 2, 0, 6, average 5 ms; average turnaround 10.5 ms.
Every job arrives at 0; a job’s wait is the time it spends not running before it ends.
This is an example. Type your own values to start a new problem.
b₁
Burst of job 1
example
b₂
Burst of job 2
example
b₃
Burst of job 3
example
b₄
Burst of job 4
example
WFCFS
FCFS average wait
worked out (not typed)
TFCFS
FCFS average turnaround
worked out (not typed)
WSJF
SJF average wait
worked out (not typed)
TSJF
SJF average turnaround
worked out (not typed)
Formulas
WFCFS
=
3 ×
b₁
+ 2 ×
b₂
+
b₃
4
10
=
3 × 10 + 2 × 4 + 2
4
TFCFS
=
WFCFS
+
b₁
+
b₂
+
b₃
+
b₄
4
15.5
=
10
+
10 + 4 + 2 + 6
4
WSJF
=
the
SJF
average
wait
of
b₁
,
b₂
,
b₃
,
b₄
5 = the SJF average wait of 10, 4, 2, 6
TSJF
=
WSJF
+
b₁
+
b₂
+
b₃
+
b₄
4
10.5
=
5
+
10 + 4 + 2 + 6
4
Assumptions
•
All four jobs arrive at time 0 in the order 1, 2, 3, 4, and none of them waits for I/O.
•
A job waits for every job run before it; a tie in SJF keeps the arrival order.
•
Turnaround is the job’s wait plus its own burst, from arrival to finish.
Step-by-step
WE KNOW
b₁ = 10 ms, b₂ = 4 ms, b₃ = 2 ms, b₄ = 6 ms
FIND
FCFS average wait (WFCFS), FCFS average turnaround (TFCFS), SJF average wait (WSJF), SJF average turnaround (TSJF)
Step 1 · Find FCFS average wait (WFCFS)
Use WFCFS = (3 × b₁ + 2 × b₂ + b₃) ÷ 4
Job
1
waits
0,
job
2
waits
b₁
,
job
3
waits
b₁
+
b₂
and
job
4
waits
b₁
+
b₂
+
b₃
;
average
the
four.
WFCFS
=
3 × 10 + 2 × 4 + 2
4
WFCFS
=
30 + 8 + 2
4
=
40
4
WFCFS = 10 ms
Step 2 · Find FCFS average turnaround (TFCFS)
Use TFCFS = WFCFS + (b₁ + b₂ + b₃ + b₄) ÷ 4
Each FCFS turnaround is the job’s wait plus its own burst, so the averages add.
TFCFS
=
10
+
10 + 4 + 2 + 6
4
TFCFS
=
10
+
22
4
=
10
+
5.5
TFCFS = 15.5 ms
Step 3 · Find SJF average wait (WSJF)
Use WSJF = the SJF average wait of b₁, b₂, b₃, b₄
Run the shortest burst first: the three jobs after it each wait for it, the next is waited for twice, then once.
WSJF = the SJF average wait of 10, 4, 2, 6
SJF order: J₃ 2, J₂ 4, J₄ 6, J₁ 10
WSJF
=
3 × 2 + 2 × 4 + 6
4
=
20
4
WSJF = 5 ms
Step 4 · Find SJF average turnaround (TSJF)
Use TSJF = WSJF + (b₁ + b₂ + b₃ + b₄) ÷ 4
Each SJF turnaround is the job’s wait plus its own burst, so the averages add.
TSJF
=
5
+
10 + 4 + 2 + 6
4
TSJF
=
5
+
22
4
=
5
+
5.5
TSJF = 10.5 ms
Check
Put the numbers back in. Both sides should match.
10
=
3 × 10 + 2 × 4 + 2
4
✓
15.5
=
10
+
10 + 4 + 2 + 6
4
✓
5 = the SJF average wait of 10, 4, 2, 6 ✓
10.5
=
5
+
10 + 4 + 2 + 6
4
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.