Process Scheduling Course Notes in Operating Systems 1 (OPESYS1)

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

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s