Process Scheduling Course Notes in Operating Systems 1 (OPESYS1)

Justin David Pineda

Faculty, Asia Pacific College

November 2015

Introduction

On the first half of the term, we discussed the conceptual terms and functions of the operating system such as process states, threads, synchronization to name a few. The second half of the term is dedicated for the simulation on how an operating system works.

Review

During the discussion of processes, we have defined it as a program in execution. It has, in simplest forms, three states: Ready state, Running state and the Blocked state. For the purposes of process scheduling, we will limit ourselves with the three states and not anymore use the expanded one. All processes reside in the Ready state, particularly in the ready queue prior to its execution. Also, only one process is executed at a time. Context switching happens when a process is switched from the ready to the running state or vice versa.

We also learned that all processes in the ready state reside in the RAM while a running process is found in the processor.

Terms

1. Arrival Time (AT) – Time when the process reaches the Ready Queue (RQ).
2. Burst Time (BT) – Total execution or service time of a process.
3. Turnaround Time (TAT) – Total time from the time a process arrives in the RQ until it finishes its execution.
4. Waiting Time (WT) – Total wait time before the process gets executed.
5. Time Quantum (TQ) – Time given to a process to execute before switching to the next process.
6. Response Ratio (RR2) – Value computed to determine the balance between processes based on AT and BT
7. Start Time (ST) – Time when process starts executing.
8. Completed Time (CT) – Time when process finishes executing.

Requirements

By default, you are required to show the following in all algorithms that will be discussed:

1. ∑BT (10%) – Summation BT or Sigma BT is the total BT of all processes in the Process Table.
2. Gantt Chart (60%) – This shows the order of the execution of processes with its time.
3. Performance Table (30%) – Show the TAT and WT of the processes.

Note: The Gantt Chart is the most important requirement. A correct Gantt Chart is a prerequisite of a correct performance table.

Example Process Table

For all algorithms, we will be using this process table:

Process	AT	BT
P1	2	10
P2	3	6
P3	4	4
P4	5	1
	∑BT	21

Note: ∑BT is always the same regardless of the algorithm used.

Algorithms

There are 5 algorithms that will be discussed: First Come First Serve (FCFS), Shortest Job First- Non Preemptive (SJF-NP), Shortest Job First- Preemptive (SJF-P), Round Robin (RR) and Highest Response Ratio Next (HRRN).

First Come First Serve (FCFS)

Quick Facts

Criteria	Arrival Time (AT)
Description	First process to arrive gets executed first.
Mode	Non-Preemptive
Advantages	Simple to implement
Disadvantages	First process to arrive does not mean it is an important process. Short important process that arrive in a later time will not be executed until the early process gets finished. If the early process is very long, a problem arises.
Exceptions	If two or more processes have the same AT, choose the first given in the question.

Gantt Chart:

IDLE	P1	P2	P3	P4
0             2	2          12	12        18	18        22	22        23

 

Performance Table:

Process	ST	CT	TAT (CT-AT)	WT (TAT-BT)
1	2	12	10	0
2	12	18	15	9
3	18	22	18	14
4	22	23	18	17
		Total:	61	40

 

Shortest Job First – Non Preemptive (SJF-NP)

Quick Facts

Criteria	Burst Time (BT)
Description	If two or more processes are in the RQ, choose the one that has the lowest BT and execute until completion.
Mode	Non-Preemptive
Advantages	Efficient
Disadvantages	Starvation – Long processes are always the last to be executed. Hypothetical – Unless you are executing batch files, you cannot predict the BT of a process.
Exceptions	If two or more process have the same BT, choose the first given in the question.

 

Gantt Chart:

IDLE	P1	P4	P3	P2
0             2	2          12	12        13	13        17	17        23

 

Performance Table:

Process	ST	CT	TAT (CT-AT)	WT (TAT-BT)
1	2	12	10	0
4	12	13	8	7
3	13	17	13	9
2	17	23	20	14
		Total:	51	30

 

Shortest Job First – Preemptive (SJF-P)

Quick Facts

SJF-P has same specifications with SJF-NP with additional features.

Criteria	Burst Time (BT)
Description	§  If two or more processes are in the RQ, choose the one that has the lowest BT and execute until completion. §  If a process enters the ready queue while another process is in execution, compare the BT of both processes. If the BT of the former is lower than the latter, PREEMPT. Otherwise, the process in execution will continue to execute.
Mode	Non-Preemptive
Advantages	Efficient
Disadvantages	Starvation – Long processes are always the last to be executed. Hypothetical – Unless you are executing batch files, you cannot predict the BT of a process.
Exceptions	§  If two or more process have the same BT, choose the first given in the question. §  If during execution, another process enters the RQ with the same BT, don’t preempt anymore. Give priority to the process in execution.

 

Gantt Chart:

IDLE	P1	P2	P3	P4	P3	P2	P1
0             2	2            3	3            4	4             5	5             6	6            9	9          14	14        23

Performance Table:

Process	ST	CT	TAT (CT-AT)	WT (TAT-BT)
1	2	23	21	11
2	3	14	9	15
3	4	9	5	1
4	5	6	1	0
		Total:	36	27

 

Round Robin (RR)

Quick Facts

Criteria	Arrival Time (AT), order in Ready Queue (RQ) & Time Quantum (TQ)
Description	The first process in the RQ is executed based on TQ.
Mode	Preemptive
Advantages	Gives equal time share to each process.
Disadvantages	§  If TQ is very small, there will be a lot of context switching. §  If TQ is very big, it will become FCFS.
Exceptions	If two or more process have the same AT, choose the first given in the question.
Additional Requirement	§  Show the order of processes in the RQ. §  This has a 10% weight in grading and the Gantt chart becomes 50%.

 

Note: Even if it is the only process remaining, you need to show the execution based on TQ. DO NOT RAILROAD THE EXECUTION!

Gantt Chart:

TQ = 4

RQ = P1, P2, P3, P4, P1, P2, P1

IDLE	P1	P2	P3	P4	P1	P2	P1
0             2	2           6	6         10	10       14	14         15	15         19	19         21	21        23

Performance Table:

Process	ST	CT	TAT (CT-AT)	WT (TAT-BT)
1	2	23	21	11
2	6	21	18	12
3	10	14	10	6
4	14	15	10	9
		Total:	59	38

Highest Response Ratio Next (HRRN)

Quick Facts

Criteria	Response Ratio (RR2)
Description	The goal of the algorithm is to balance FCFS and SJF algorithms. The algorithm takes into consideration the AT and BT at the same time. RR2 is computed as (W+S) / S where W or (X – AT) is Waiting Time so far and S is the Service Time or Burst Time (BT).
Mode	Non-Preemptive
Advantages	§  Better than SJF §  No Starvation
Disadvantages	Too much complexity
Exceptions	If two or more processes have the same RR2, choose the first given in the question.
Additional Requirement	§  Show all RR2 computations. §  This has a 10% weight in grading and the Gantt chart becomes 50%.

 

Process	AT	BT	t=12	t=13
P1	2	10
P2	3	6	2.5	2.67
P3	4	4	3	3.25
P4	5	1	8

 

Gantt Chart:

IDLE	P1	P4	P3	P2
0             2	2          12	12        13	13        17	17        23

 

Performance Table:

Process	ST	CT	TAT (CT-AT)	WT (TAT-BT)
1	2	12	10	0
4	12	13	8	7
3	13	17	13	9
2	17	23	20	14
		Total:	51	30

 

Caveats

1. There are no negative values when you do the Performance Table. If you get a negative answer, either your subtraction or Gantt chart is wrong.
2. The end time and ∑BT for a Process Table given will always be the same regardless of the algorithm given. Only the TAT and WT will be different.
3. The ∑BT is not always equal to the end time in the Gantt chart. This will differ if the Gantt chart has idle time.
4. For preemptive algorithms, always look for the last CT when the process finishes executing. Otherwise, it will yield to a negative result.
5. Always check the AT. A lot of students get confused that they look for a lower BT in SJF but the process has not arrived yet. It will yield to a negative result!
6. The basis of your performance table is the Gantt chart. Write the processes based on the order in the Gantt chart, NOT based on the Process Table.

 

References

Agarwal, A. (2015, November 22). Anshul Agarwal’s Tutorial. Retrieved from YouTube Channel: https://www.youtube.com/channel/UCgathW7WSdooPMwOrW17oMw

Gagne, G., Galvin, P. B., & Silverschatz, A. (2005). Operating System Principles (7th Ed). NJ: John WIley & Sons Inc. .

Krzyzanowski, P. (2015, November 22). Operating Systems CS416. Retrieved from Pau at Rutgers: https://www.cs.rutgers.edu/~pxk/416/index.html

PDF copy can be downloaded here: Process Scheduling