CO2017 — Week 1L2 — Processes and Multi-tasking
CO2017 — Week 1L2 — Processes and
Multi-tasking
Dr Gilbert Laycock (gtl1)
2017–01–24
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 1 / 33
How to implement multi-tasking Why multi-tasking?
Simple Fetch-Execute Cycle
CPU operates in a Fetch-Execute cycle — it just does one thing at a
time
1 Fetch next instruction from memory
2 Execute the instruction
If an I/O operation is required, CPU will wait until I/O is complete
Execute
Start
process
Fetch
instruction
instruction
Process
terminated
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 2 / 33
How to implement multi-tasking Why multi-tasking?
Why do we want more than one process at a time?
For convenience of the user.
A modern OS typically needs to monitor and control all kinds of
background tasks.
For better CPU utilisation.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 3 / 33
How to implement multi-tasking How to appear to multi-task
How to implement multi-tasking:
There is only a single CPU (or perhaps a handful).
Apparent simultaneous execution of several processes is
achieved by the CPU performing a little bit of each process then
suspending it and moving to the next.
CPU needs a mechanism to determine that a particular process
can be suspended to allow the next one to take over.
Mechanism is interrupts
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 4 / 33
How to implement multi-tasking Interrupts and the CPU cycle
The (interrupted) CPU cycle
N
Handle
interrupt
Process
terminated
Start
process
Fetch
instruction
instruction
Interrupt?
Execute
Y
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 5 / 33
How to implement multi-tasking Interrupts and the CPU cycle
Definition and rôle of interrupts
Interrupts: events that cause the CPU to stop the current process
and switch to the special process for handling the interrupt.
The Dispatcher performs the operation required by the interrupt
(e.g. sending data to a printer) and then decides which process
is the next to run.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 6 / 33
How to implement multi-tasking Interrupts and the CPU cycle
Types of Interrupts
Input/Output (I/O): by I/O devices to signal completion, error or other
state change.
Timer: by a clock within the CPU; used to alert the OS at pre-set
intervals for time critical activities.
Hardware Error: by hardware faults.
Program: by error conditions within user programs, e.g, division by zero
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 7 / 33
How to implement multi-tasking Programs and processes
Programs and processes
A program is code ready to execute on a system.
A process is a program in execution, i.e, a particular instance of
a program together with its data.
There may be several copies of the same program running
simultaneously as different processes.
The OS stores information about each process in a process
control block (PCB) (also called process descriptor).
Multi-tasking: is the simultaneous running of two or more
processes.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 8 / 33
How to implement multi-tasking Programs and processes
Sharing Code among Processes
Tetris
Alice’s second document
Operating System
Emacs code (shared)
Alice’s first document
Bob’s document
Alice
Bob
Memory
Shared code must not be changed during execution
Each processes requires its own data area
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 9 / 33
How to implement multi-tasking Programs and processes
Process Creation
E.g, Created by a user via a command:
When a user invokes a program, OS creates a PCB to represent the
execution of this process.
OS also allocates resources for the process.
So, a process consists of machine code in memory and a PCB.
Created by another process, called spawning a process:
The process that creates a new process is called the parent while the
created process is the child
The child can also spawn further processes, forming a tree of processes
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 10 / 33
How to implement multi-tasking Programs and processes
Aside about Kernel Mode vs User Mode
OS needs to protect processes from each other for security
If a user’s process had access to all machine instructions, then the
user could do anything the OS can.
The solution is for the CPU to have a special operating mode, kernel or
supervisor mode, which can only be invoked by the OS.
In kernel mode, certain privileged instructions, e.g, interrupt
processing, dispatcher, memory allocation, are possible; normal
processes run in user mode
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 11 / 33
How to implement multi-tasking The Dispatcher
The Dispatcher
After an interrupt has been handled, control is passed to the
Dispatcher (or Low Level Scheduler).
1 Is the current process still the most suitable to run? If so, resume
execution; otherwise . . .
2 Save the state of the current process in its PCB
3 Retrieve the state of the most suitable process from its PCB
4 Transfer control to the new process, at the point indicated in the PCB
The action of storing the state of current process and (re-)starting
another process is called a context switch
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 12 / 33
How to implement multi-tasking The Dispatcher
States of processes
The running process is in the RUNNING state; only one RUNNING
process on a processor at a time.
Clock interrupt:
Initiated by a clock within the CPU.
Gives the dispatcher an opportunity to context switch.
A process stopped by clock interrupt goes to READY state.
I/O interrupt:
Initiated by CPU when an I/O instruction occurs in the running
process or by an I/O device signalling completion of an I/O
operation
When a process starts an I/O operation it goes to the BLOCKED
state
When an I/O operation completes for a process, it goes to READY
state
The dispatcher can select a process to run only if it is READY.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 13 / 33
How to implement multi-tasking The Dispatcher
Diagram of process states
Process entry
READY BLOCKED
RUNNING
Dispatch
Termination
I/O wait
I/O completion
Timeout
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 14 / 33
How to implement multi-tasking The Dispatcher
Summary of the story and what next
A process can be RUNNING (currently running), READY (ready to run)
or BLOCKED (waiting on I/O).
Interrupts are used to stop the currently RUNNING process.
A clock interrupt causes the current process to become READY.
An I/O interrupt causes the current process to become BLOCKED, upon
completion of the I/O it becomes READY
The Dispatcher chooses the next process to run from the queue of
READY processes.
Scheduling: is the policy for choosing among the READY processes.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 15 / 33
How to implement multi-tasking The Dispatcher
Types of Scheduling policy
Scheduling policy determines:
Which READY process to run next.
How long a process is given to use the CPU.
Non-preemptive scheduling:
A process releases CPU only if it BLOCKS on I/O (or it finishes).
i.e. the process cannot be stopped during regular operation.
Preemptive scheduling:
A process can be stopped at any point by a clock interrupt.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 16 / 33
How to implement multi-tasking The Dispatcher
Efficiency measures of scheduling policies
There are many possible ways to measure efficiency of
scheduling policies.
We consider the following 3:
Turnaround time.
CPU usage.
Response time.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 17 / 33
How to implement multi-tasking The Dispatcher
Turnaround time
Turnaround time of a particular process is its duration in real
time, i.e. the difference between the end and the start times.
Turnaround time of a group of processes is the average of their
individual turnaround times.
Example:
We have 3 processes with respective start and end times
(100,200), (150,300) and (200,400).
The individual turnaround times are 100, 150, 200.
The average turnaround time is 150
A good scheduling policy keeps average turnaround time as low
as possible.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 18 / 33
How to implement multi-tasking The Dispatcher
CPU Usage
If all the processes are blocked waiting for completion of their I/O
operations, the CPU stays idle.
A good scheduling policy minimises the idleness time.
CPU usage: given some amount of time, the percentage of time
during which the CPU is busy.
Clearly, it is good if the scheduling policy maximises CPU usage.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 19 / 33
How to implement multi-tasking The Dispatcher
Response time
The OS classifies some processes as user commands.
E.g, in Linux, user requests are commands like cp, cd, ls, etc. or
applications.
The response time is average turnaround time of user requests.
The turnaround time of other processes is ignored.
response time must be minimised in interactive systems.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 20 / 33
How to implement multi-tasking The Dispatcher
Types of operating systems
Batch systems:
Run a series of programs without human intervention.
Examples: scientific computing, salary calculation in big
companies.
Turnaround time and CPU usage are more important measures
than response time.
Interactive systems:
Designed to continuously communicate with the user.
Examples: Linux, Windows.
Response time is more important measure than the other two.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 21 / 33
How to implement multi-tasking Scheduling policies
Generalisations
I/O is not important for this discussion — when a process blocks
on I/O it is no longer available for scheduling.
Consider each long running process to be split into short bursts
that require no I/O; treat these bursts as separate processes as
far as the scheduler is concerned.
Can estimate the expected burst length for long running
processes by empirically measuring previous behaviour.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 22 / 33
How to implement multi-tasking Scheduling policies
First come first served (FCFS) policy
This policy is non-preemptive.
The first READY process in the queue is started.
The process releases the CPU when it finishes or it BLOCKs on
I/O
When a BLOCKed process returns to READY state, it goes to the
back of the READY queue.
Suitable for batch systems only.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 23 / 33
How to implement multi-tasking Scheduling policies
Advantages and disadvantages of the FCFS policy
Advantages:
Easy to implement.
No indefinite waiting (when a process can potentially wait forever
to be run).
Disadvantage: turnaround time of short processes can be much
longer than their actual execution time.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 24 / 33
How to implement multi-tasking Scheduling policies
Shortest job first (SJF) policy
The policy is non-preemptive.
Requires knowledge about the runtime of processes before they
actually execute.
From the queue of READY processes choose the one whose
(expected) runtime is smallest.
Otherwise, as for FCFS.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 25 / 33
How to implement multi-tasking Scheduling policies
Advantages and disadvantages of the SJF policy
Advantage: favourable to processes with short runtimes.
Disadvantages:
Requires advance knowledge about runtimes.
Indefinite waiting is possible: a long process can wait a long time
if multiple new short processes arrive.
Does not take into account the situation when a long process is
close to completion (i.e. effectively becomes a short process).
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 26 / 33
How to implement multi-tasking Scheduling policies
Shortest remaining time first (SRTF) policy
This is a preemptive policy.
For every process, requires knowledge of the remaining runtime.
Very similar to SJF.
The differences are:
Arrival of a process in the READY queue leads to an interrupt.
Chooses process with the shortest remaining time instead
shortest overall time.
So if a process with shorter remaining time than the current one
arrives in the READY queue, the current process is preempted.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 27 / 33
How to implement multi-tasking Scheduling policies
Advantages and disadvantages of the SRTF policy.
Advantage: even more sensitive to the short processes than SJF.
Disadvantages: requires advance knowledge of runtimes;
indefinite waiting is still possible.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 28 / 33
How to implement multi-tasking Scheduling policies
Round-Robin scheduling policy
This is a preemptive policy used in interactive systems.
Each process in turn gets the CPU for a fixed time quantum
(typically 10–100 ms).
When the quantum finishes: a timeout interrupt occurs and the
process goes to the back of the READY queue.
New processes join the back of the READY queue.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 29 / 33
How to implement multi-tasking Scheduling policies
Quantum duration for round-robin
Context switch: is the procedure of replacing the currently
running process by another one. This takes a non-zero amount
of time.
If the quantum is too short (similar to the time taken for a
context switch), the CPU spends a large proportion of its time
just context switching.
If the quantum is too long then the response time may become
unacceptable (behaves like FCFS).
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 30 / 33
How to implement multi-tasking Scheduling policies
Multi-level schedulers
Most real systems use multiple levels of job queue.
For example, 3 queues, high, medium and low priority READY
queues.
Each queue can operate its own policy; e.g. round-robin, FCFS,
etc.
Processes that are pre-empted move between the different
levels depending on various criteria, e.g. age of the process.
Higher level queues are given more priority by the scheduler,
e.g. shorter quantum, but more regularly serviced.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 31 / 33
How to implement multi-tasking Real world schedulers
Schedulers used in actual OSes
MS-DOS: single process (no scheduling);
Windows 3.1: non-preemptive;
Windows NT (and newer): multi-level feedback queue;
Linux: multi-level feedback queue until 2.6; then the O(1)
scheduler; uses completely fair scheduler (CFQ) since
2.6.23;
MacOS 9: Round-robin, with cooperative non-preemptive threads;
MacOS X: multi-level feedback queue;
Android: CFQ, but with processes grouped into 5 priority levels;
aggressively kills “idle” processes;
iOS (iphone): none until iOS4; cooperative multi-tasking since then.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 32 / 33
Summary
Summary
What a process is.
What interrupts are.
The Dispatcher implements scheduling policy.
Compared various simple scheduling policies.
gtl1–R874 W1L2 — Multi-tasking 2017–01–24 33 / 33
How to implement multi-tasking
Why multi-tasking?
How to appear to multi-task
Interrupts and the CPU cycle
Programs and processes
The Dispatcher
Scheduling policies
Real world schedulers
Summary