OS: Note of Chapter 9

Nesting of Scheduling Functions

The scheduling model of processes is the 7-state model. The 7 states of a process are:

• New
• Ready
• Ready/Suspend
• Blocked
• Blocked/Suspend
• Running
• Exit

The states “running”, “ready”, and “blocked” is called short term scheduling, the ready/suspend and blocked/suspend is the medium term scheduling, and then the states “new” and “exit” is called long term scheduling. The easiest way of scheduling is using queue, which is the most simple, only maintaining a queue for each state.

The Criteria of Scheduling

User oriented

• Turnaround time: Interval of time between the submission of a process and the completion, including the execution time and the waiting time.
• Response time: Interval of time between the submission of a process and the first response.

System oriented

• Throughput: Number of tasks executed in a unit of time.
• Processor utilisation: The ratio of time that the processor is occupied.

Some Process Scheduling Algorithms

1. First Come First Served (FCFS)

   This is the non-preemptive scheduling algorithm. The processes are executed in the order of arrival. This will cause that the last some tasks may have to wait for a long time. The wait time have factly a very long standard deviation.

2. Round Robin

   The processes run in a preemptive mode. The time slice is the quantum time, and the processes are executed in a circular order. The time slice is the maximum time that a process can run in a row. The time slice is the most important parameter of this algorithm.

3. Virtual Round Robin

   For the I/O bound processes, the round robin algorithm is not efficient. The virtual round robin algorithm is a variant of the round robin algorithm, which prevents that the processes will not be dispatched when they are blocked by I/O. This algorithm introduces a new queue that storing I/O blocked processes, and the CPU will call them at a higher priority.

4. Shortest Process Next (SPN)

   When a process is done, the shortest process will be dispatched.

5. Shortest Remaining Time (SRT)

   When a process is done or reaching out time slice, the shortest remaining time process will be dispatched.