CPU Scheduling

CPU Scheduling Simulation To understand details about CPU schedulers to better understand the dynamic behaviors of operating systems.  Overview A CPU Scheduler is a core component of any multiprogramming operating system kernel. It is important to understand the details about the CPU scheduler to know dynamic behaviors of the operating system. In this project, C […]
Project Name
CPU Scheduling Simulation
Project Goal
To understand details about CPU schedulers to better understand the dynamic behaviors of operating systems.

Details

 Overview

A CPU Scheduler is a core component of any multiprogramming operating system kernel. It is important to understand the details about the CPU scheduler to know dynamic behaviors of the operating system.

In this project, C programs were written to simulate the following CPU scheduling algorithms for a single CPU machine:

  1. First-Come, First-Served (FCFS) scheduling
  2. Round-Robin (RR) scheduling with time quantum q=2 milliseconds, q=12 milliseconds, q=50 milliseconds, respectively
  3. Multilevel Feedback Queue (FBQ) preemptive scheduling with q1=10 milliseconds and q2=30 milliseconds

CPU scheduling algorithm not included in this project:

  1. Shortest-Job-First (SJF) scheduling

Based on a given static CPU workload, the programs calculate the following:

  • The average waiting time
  • The average turnaround time
  • Time all processes finished
  • Average CPU utilization
  • Number of context switches
  • Last process to finish


Documentation

 Basic Concepts

CPU scheduling is the basis of multiprogramming. By switching the CPU among processes, the operating system can make the computer more productive. The idea is relatively simple, the objective of multiprogramming is to have some process running at all times, to maximize CPU utilization.

CPU scheduling consists of two components:

  1. CPU scheduler: when CPU becomes idle, the CPU scheduler must select from among the processes in ready queue.
    • Preemptive scheduling
    • Non-preemptive scheduling
  2. Dispatcher: the module which gives control of CPU to the process selected by the CPU scheduler.
    • Switching context
    • Switching to user mode
    • Jumping to the proper location in user program to restart that program
    • Dispatch latency: the time it takes for the dispatcher to stop one process and start another running

Proccess States

Proccess States
  • New: Process being created
  • Running: Process instructions being executed by CPU
  • Waiting: Process waiting for some event, I/O completion or a signal
  • Ready: Process waiting to be assigned to CPU to run
  • Terminated: Process being completed

CPU – I/O Burst Cycle

Process execution consists of a cycle of CPU execution and I/0 wait. Processes alternate between these two states until the final CPU burst that ends with a system request to terminate execution.

CPU - I/O Burst Cycle

The durations of CPU bursts have been measured extensively and they vary greatly from process to process and from computer to computer. However, they tend to have a frequency curve similar to that shown below:

CPU Scheduling

Preemptive vs Non-preemptive Scheduling

CPU scheduling decisions may take place when a process:

  1. Switches from running to waiting state.
  2. Switches from running to ready state.
  3. Switches from waiting to ready.
  4. Terminates.

Preemptive scheduling takes place in 1, 2, 3, 4.

  • A running process can be preempted by another process
  • Not easy to make OS kernel to support preemptive scheduling
  • How about if the preempted process is updating some critical data structure?

Non-preemptive scheduling takes place under 1 and 4.

  • Once the CPU has been allocated to a process, the process keeps the CPU until it releases CPU.

Scheduling Criteria

CPU utilization keep the CPU as busy as possible. Conceptually, CPU utilization can range from 0 to 100 percent. In a real system, it should range from 40 percent (for a lightly loaded system) to 90 percent (for a heavily used system).
Throughput Number of processes that complete their execution per time unit.
Turnaround time amount of time to execute a particular process. The interval from the time of submission of a process to the time of its completion.
Waiting time amount of time a process has been waiting in the ready queue.
Response time amount of time it takes from when a request was submitted until the first response is produced, not the final output (for time-sharing environment).

 CPU Scheduling Algorithms

First-Come, First-Served Scheduling

The First-Come, First-Served (FCFS) scheduling algorithm is the simplest CPU-scheduling algorithm. The process that requests the CPU first is allocated the CPU first. FCFS is easy to implement (as a FIFO queue) but it results in long waits in most cases and suffers convoy effect.
This effect results in lower CPU and device utilization than might be possible if the shorter processes were allowed to go first.

Example of FCFS

Process Burst Time (ms)
P1 24
P2 3
P3 3

Suppose that the processes arrive at time 0 in the order: P1, P2, P3. The Gantt Chart for the scheduling is:

FCFS CPU Scheduling Grant Chart

Waiting time:

Process Burst Time (ms) Wait Time (ms)
P1 24 0
P2 3 24
P3 3 27

Average waiting time: (0 + 24 + 27) / 3 = 17 ms

Now suppose that the processes arrive at time 0 in the order: P2, P3, P1. The Gantt Chart for the scheduling is:

FCFS CPU Scheduling Grantt Chart

Waiting time:

Process Burst Time (ms) Wait Time (ms)
P1 24 6
P2 3 0
P3 3 3

Average waiting time: (6 + 0 + 3) / 3 = 3 ms

As you can see, the average waiting time reduction is substantial.

The FCFS scheduling algorithm is nonpreemptive. Once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/0.

Round-Robin Scheduling

The Round-Robin (RR) scheduling algorithm is designed especially for timesharing systems. It is similar to FCFS scheduling, but preemption is added to enable the system to switch between processes. A small unit of time, called a time quantum or time slice, is defined. A time quantum is generally from 10 to 100 milliseconds in length. The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.

Fairness: If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.

Time Quantum and Context Switch Time

Time Quantum and Context Switch Time

Example of RR with Time Quantum q = 20

Process Burst Time (ms)
P1 53
P2 17
P3 68
P4 24

Suppose that the processes arrive at time 0 in the order: P1, P2, P3, P4. The Gantt Chart for the scheduling is:

RR CPU Scheduling Grantt Chart

Waiting time:

Process Burst Time (ms) Wait Time (ms)
P1 53 81
P2 17 20
P3 68 94
P4 24 97

Average waiting time: (81 + 20 + 94 + 97) / 4 = 73 ms

RR Performance:
If q large, then RR resembles FCFS.
If q small, then there are too many context switches, so overhead is high.

Multilevel Feedback Queue Scheduling

A multilevel queue scheduling algorithm partitions the ready queue into several separate queues.

Multilevel Feedback Queue Scheduling

In a multilevel feedback queue scheduling algorithm a process can move between the various queues; aging can be implemented this way.

  • If a process uses too much CPU time, it will be moved to a lower-priority queue.
  • If a process waits too long, it will be moved to a higher-priority queue.

This form of aging prevents starvation or indefinite blocking, one the major problems with priority scheduling algorithms.

Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.

Multilevel-feedback-queue scheduler defined by the following parameters:

  • number of queues
  • scheduling algorithms for each queue
  • method to determine when to upgrade a process
  • method to determine when to demote a process
  • method to determine which queue a process will enter when that process needs service

The multilevel feedback queue scheduling algorithm is the most general CPU scheduling algorithm. It can be configured to match a specific system under design.

Example of Multilevel Feedback Queue

Multilevel Feedback Queue Scheduling

Three queues are implemented as follows:

  • Q0 – RR scheduling with time quantum 8 ms
  • Q1 – RR scheduling with time quantum 16 ms
  • Q2 – FCFS scheduling
  • A new job enters queue Q0. When it gains CPU, job receives RR with 8 ms. If it does not finish in 8 ms, job is moved to queue Q1.
  • At Q1 job is again served RR and receives 16 ms. If it still does not complete, it is preempted and moved to queue Q2.
  • At Q2 job finishes because FCFS is always preemptive.

 CPU Workload – Data Format

Each line in the CPU workload data files represent one process with the following format: (all numbers are in unit of millisecond)

pid arrival_time 1st_CPU_burst (1st_IO_burst) 2nd_CPU_burst (2nd_IO_burst) ...

e.g.

0  0  4 (100) 12 (67) 2 ...
1  13 7 (210) 20 (23) 67 ...

where each I/O burst includes both the time waiting in the device queue and the time spent in actual I/O operations.
If two or more processes are identical in terms of scheduling criterion, priority is given to the process which has lowest pid number.


Development

 API

API

 References

  1. The C Programming Language, 2nd Edition
    Brian W. Kernighan, Dennis Ritchie
  2. Beej’s Guide to Unix IPC
    Brian “Beej Jorgensen” Hall
  3. Beej’s Guide to Unix IPC – PDF
    Brian “Beej Jorgensen” Hall
  4. Operating System Concepts, 8th Edition
    Abraham Silberschatz, Peter B. Galvin, Greg Gagne
  5. Linux man pages
    Michael Kerrisk