• New: A process is created.
  Program code are moved from disk to main memory.
• Ready: The process is waiting to be scheduling to a processor.
  Program code reside in main memory.
• Running: Instructions are being executed in CPU.
  Instructions reside in CPU.
• Waiting: The process is blocked and waiting for some events to occur(signal)
  Program code are in main memory or has been swapped out to virtual memory.
• Terminated: The process has finished execution.
  Program code are removed from memory.

This is the state transition diagram of the process states.

The table below shows where do program code mainly reside at each state.

There are three kinds of scheduling including long-term scheduling , medium-term scheduling and short-term scheduling. This article is mainly focus on short-term scheduling.

This table shows when do we do the three scheduling in terms of state transitions.

We mark them on the state transition diagram:

There are a bunch of scheduling criteria that we need to consider when choosing a scheduling algorithm.

• CPU utilization (u%)
• Throughput (process/second)
• Turnaround time (seconds/process)
• Waiting time (seconds)
• Response time (seconds)
• Deadline
• Fairness
• Predictability
• Policy enforcement
• Balance

Different systems should follow different criteria based on their own requirements.

We will introduce four scheduling algorithms with examples. In next section, we will explain the details of these algorithms.

Selection Function: Select the process with the minimum arrival time. (Non-preemptive)
Example for FCFS:
Suppose there are four processes whose arrival time and service time are listed in the table.

The scheduling result in Gantt chart:

Selection Function: Each process execute for fixed length of time quantum. (Preemptive)
Example for RR:
Suppose there are four processes whose arrival time and service time are listed in the table.

The scheduling result in Gantt chart:

Selection Function: Select the process with the minimum service time (Non-preemptive)
Example for SJF:
Suppose there are four processes whose arrival time and service time are listed in the table.

The scheduling result in Gantt chart:

Selection Function: Select the process with the minimum remaining service time (Preemptive)
Example for PSJF:
Suppose there are three processes whose arrival time and service time are listed in the table.

The scheduling result in Gantt chart:

We define some terms first.

• a : arrival time of a process
• e : time spent in execution so far
• s : total service time required by the process, including e

The following table shows the corresponding properties to the scheduling algorithms.

Based on the criteria for different systems and scheduling algorithm properties, we can decide what kind of algorithms we should choose for each kind of systems. As is shown from below:

Some processes are CPU bound, and some are I/O bound. An I/O bound process will be blocked when it tries to do I/O. To improve CPU utilization rate, engineers proposed the concept of Multiprograming. That is to say — we load many processes into the main memory at the same time. When a running process is blocked by I/O operation, we switch to run other processes. Multiprograming is the root cause that we need to do short-term scheduling.

Multiprograming is for improving CPU utilization, while Multithreading is for many other reasons. For example: share resources, parallelism, simplify code structure, improve concurrency and many others.