CPU Scheduling Algorithms

First-Come, First-Served (FCFS) Scheduling
Shortest-Job-First (SJF) Scheduling
Shortest Remaining Time First (SRTF / Preemptive SJF) Scheduling
Non-preemptive Priority Scheduling
Preemptive Priority Scheduling
Round Robin (RR) Scheduling

Some term

PN0 - Process Number (aka PID): This typically refers to the Process Identification Number or PID. It’s a unique identifier assigned to each process running in an operating system. PIDs are used to manage and control processes.
AT - Arrival Time 到达时间: Arrival time represents when a process arrives or is submitted to the operating system for execution. It’s an important parameter in scheduling algorithms, as it determines the order in which processes are executed.
BT - Burst Time 突发时间: Burst time is the amount of time a process requires to complete its execution. It’s also a crucial factor in process scheduling, as it helps determine the efficiency and performance of scheduling algorithms.
CT - Completion Time 完成时间: Completion time is the time at which a process finishes its execution. It’s calculated by adding the arrival time and burst time for a process.
TAT - Turn-around Time (CT - AT) 周转时间: Turn-around time is the total time taken by a process from its arrival to its completion. It’s calculated by subtracting the arrival time (AT) from the completion time (CT).
WT - Waiting Time (TAT - BT) 等待时间: Waiting time represents the total time a process spends waiting in the ready queue before it gets CPU time for execution. It’s calculated by subtracting the burst time (BT) from the turn-around time (TAT).
AWT - Average Waiting Time 平均等待时间: Average waiting time is the average of waiting times for all processes in a scheduling scenario. It’s used to evaluate the efficiency of a scheduling algorithm, with lower values indicating better performance.

https://www.tutorialspoint.com/operating_system/os_process_scheduling_algorithms.htm

First-Come, First-Served (FCFS) Scheduling

Example 1

Gantt Chart

--------------------
| P1     | P2 | P3 |
--------------------
|        |    |    |
0        24   27   30

PN0	BT	CT	TAT	WT
P1	24	24	24	0
P2	3	27	27	24
P3	3	30	30	27

AWT = (0 + 24 + 27) / 3 = 17ms

Example 2

Gantt Chart

--------------------
| P2 | P3 | P1     |
--------------------
|    |    |        |
0    3    6        30

PN0	BT	CT	TAT	WT
P1	24	30	30	6
P2	3	3	3	0
P3	3	6	6	3

AWT = (0 + 3 + 6) / 3 = 3ms

Example 3

PN0	AT	BT	CT	TAT	WT
P1	0	5	5	5	0
P2	1	3	8	7	4
P3	2	8	16	14	6
P4	2	4	20	18	14

AWT = (0 + 4 + 6 + 14) / 4 = 6ms

For quick check, let’s sum all BT, 5+3+8+4=20, eventually gantt chart:

---------------------
| P1 | P2 | P3 | P4 |
---------------------
|    |    |    |    |
0    5    8    16   20

Shortest-Job-First (SJF) Scheduling

Example 1

Process	Burst Time
P1	6
P2	8
P3	7
P4	3

Concept is to pick the process with the shortest burst time. Which mean the smallest BT will be executed first. So the order will be P4, P1, P3, P2. Let’s see the gantt chart:

---------------------
| P4 | P1 | P3 | P2 |
---------------------
|    |    |    |    |
0    3    9    16   24

PN0	BT	CT	TAT	WT
P1	6	9	9	3
P2	8	24	24	16
P3	7	16	16	9
P4	3	3	3	0

Quick notes! CT can refer to gantt chart, no need to calcualte.

AWT = (3 + 16 + 9 + 0) / 4 = 7ms

Example 2

PN0	AT	BT	CT	TAT	WT
P1	1	5	6	5	0
P2	2	6	15	13	7
P3	3	7	22	19	12
P4	2	1	7	5	4
P5	5	2	9	4	2

            (21) -sum of BT
             |
          becuase AT start from 1, that's why gannt chart result is (21+1)=22

AWT = (0 + 7 + 12 + 4 + 2) / 5 = 5ms

Ohh.. now we only have AT and BT, we need to order them first, NOTE THAT IT’S DIFFERENT WITH FCFS:

--------------------------------
| idk | P1 | P4 | P5 | P2 | P3 |
--------------------------------
|     |    |    |    |    |    |
0     1    6    7    9    15   22

now can calculate CT, TAT, WT already.

SJF (Non-preemptive) - once process is assign to a processer, they will run until they terminate or block themselves. SJF kinda selfish, they will not give up the CPU until they finish their own job. There a example: P1’s bt is 10sec, P2’s bt is 1sec. First P1 will run for 10sec, during this 10 sec time P2 will wait, all process will wait, until P1 finish.

Shortest Remaining Time First (SRTF / Preemptive SJF) Scheduling

The SJF we talked before is non-preemptive. Then Preemptive SJF or SRTF here is the preemptive version of SJF. Which is the version that not selfish.

Example 1

PN0	AT	BT	CT	TAT	WT
P1	0	6	11	11	5
P2	1	4	6	5	1
P3	3	1	4	1	0
P4	3	5	16	13	8

AWT = (5 + 1 + 0 + 8) / 4 = 3.5ms

 (5)   (2)
-------------------------------
| P1 | P2 | P3 | P2 | P1 | P4 |
-------------------------------
|    |    |    |    |    |    |
0    1    3    4    6    11   16

+-----------------------+
|        P1 (5)         |
|                       |
| P2 (2)         P4(5)  |
+-----------------------+

Example 2

PN0	AT	BT	CT	TAT	WT
P1	0	5	12	12	7
P2	1	3	5	4	1
P3	2	1	3	1	0
P4	2	3	8	6	3

AWT = (7 + 1 + 0 + 3) / 4 = 2.75ms

(4)   (2)   /    /    /    /
-------------------------------
| P1 | P2 | P3 | P2 | P4 | P1 |
-------------------------------
0    1    2    3    5    8    12

The first process to be executed is always be the process with the shortest burst time. If there are two processes with the same burst time, then the process with the lowest process number will be executed first. Reading second by second.

Non-preemptive Priority Scheduling

Example 1

PN0	AT	BT	CT	TAT	WT	Priority No
P1	0	5	5	5	0	2
P2	1	3	8	7	4	1
P3	2	1	9	7	6	2
P4	2	3	12	10	7	3

AWT = (0 + 4 + 6 + 7) / 4 = 4.25ms

---------------------
| P1 | P2 | P3 | P4 |
---------------------
0    5    8    9    12

The first process to be executed is always P1(i guess), then all the other processes will be executed in the order of their priority number.

Example 2

PN0	AT	BT	CT	TAT	WT	Priority No
P1	0	7	7	7	0	3
P2	1	2	10	9	7	2
P3	1	1	8	7	6	1
P4	3	3	13	10	7	2

AWT = (0 + 7 + 6 + 7) / 4 = 5ms

---------------------
| P1 | P3 | P2 | P4 |
---------------------
0    7    8   10    13

Preemptive Priority Scheduling

Example 1

PN0	AT	BT	CT	TAT	WT	Priority No
P1	0	5	8	8	3	2
P2	1	3	4	3	0	1
P3	2	1	9	7	6	2
P4	2	3	12	10	7	3

AWT = (3 + 0 + 6 + 7) / 4 = 4ms

 (4)   /    /    /    /
--------------------------
| P1 | P2 | P1 | P3 | P4 |
--------------------------
0    1    4    8    9    12

Example 2

PN0	AT	BT	CT	TAT	WT	Priority No
P1	0	7	13	13	6	3
P2	1	2	4	3	1	2
P3	1	1	2	1	0	1
P4	3	3	7	4	1	2

AWT = (6 + 1 + 0 + 1) / 4 = 2ms

 (1)  (0)  (0)  (0)  (0)
--------------------------
| P1 | P3 | P2 | P4 | P1 |
--------------------------
0    1    2    4    7    13

Round Robin (RR) Scheduling

tq = time quantum, aka time slice In this case, tq = 3ms

PN0	AT	BT	CT	TAT	WT
P1	0	6	11	11	5
P2	1	4	12	11	7
P3	1	2	8	7	5

 (3)   (1)   /    /    /
--------------------------
| P1 | P2 | P3 | P1 | P2 |
--------------------------
0    3    6    8    11   12

Week 7 Activity 題目

PN0	AT	BT	Priority
P1	0	10	3
P2	1	1	2
P3	1	2	1
P4	3	1	4
P5	2	5	2

FCFS

PN0	AT	BT	CT	TAT	WT
P1	0	10	10	10	0
P2	1	1	11	10	9
P3	1	2	13	12	10
P4	3	1	19	16	15
P5	2	5	18	16	11

--------------------------
| P1 | P2 | P3 | P5 | P4 |
--------------------------
0    10   11   13   18   19

SRTF

PN0	AT	BT	CT	TAT	WT
P1	0	10	19	19	9
P2	1	1	2	1	0
P3	1	2	4	3	1
P4	3	1	5	2	1
P5	2	5	10	8	3

 (9)   /    /    /    /    /
-------------------------------
| P1 | P2 | P3 | P4 | P5 | P1 |
-------------------------------
0    1    2    4    5    10   19

SJF

PN0	AT	BT	CT	TAT	WT
P1	0	10	10	10	0
P2	1	1	11	10	9
P3	1	2	12	11	9
P4	3	1	14	11	10
P5	2	5	19	17	12

--------------------------
| P1 | P2 | P4 | P3 | P5 |
--------------------------
0    10   11   12   14   19

Non Preemptive Priority

PN0	AT	BT	CT	TAT	WT	Priority
P1	0	10	10	10	0	3
P2	1	1	13	12	11	2
P3	1	2	12	11	9	1
P4	3	1	19	16	15	4
P5	2	5	18	16	11	2

--------------------------
| P1 | P3 | P2 | P5 | P4 |
--------------------------
0    10   12   13   18   19

Preemptive Priority

PN0	AT	BT	CT	TAT	WT	Priority
P1	0	10	18	18	8	3
P2	1	1	4	3	2	2
P3	1	2	3	2	0	1
P4	3	1	19	16	15	4
P5	2	5	9	7	2	2

 (9)   /    /    /    /    /
-------------------------------
| P1 | P3 | P2 | P5 | P1 | P4 |
-------------------------------
0    1    3    4    9    18   19

Round Robin

PN0	AT	BT	CT	TAT	WT
P1	0	10	19	19	9
P2	1	1	3	2	1
P3	1	2	6	5	3
P4	3	1	10	7	6
P5	2	5	15	13	7

Ready Queue: P1 P2 P3 P5 P4

 (7)   /    /    (2)  /    (4)  /    (1)  /
----------------------------------------------
| P1 | P2 | P3 | P5 | P4 | P1 | P5 | P1 | P1 |
----------------------------------------------
0    3    4    6    9    10   13   15   18   19

OS FCFS

CPU Scheduling Algorithms

Table of Contents

Some term

First-Come, First-Served (FCFS) Scheduling

Example 1

Example 2

Example 3

Shortest-Job-First (SJF) Scheduling

Example 1

Example 2

Shortest Remaining Time First (SRTF / Preemptive SJF) Scheduling

Example 1

Example 2

Non-preemptive Priority Scheduling

Example 1

Example 2

Preemptive Priority Scheduling

Example 1

Example 2

Round Robin (RR) Scheduling

Week 7 Activity 題目

FCFS

SRTF

SJF

Non Preemptive Priority

Preemptive Priority

Round Robin