Lecture 3

Processes
Process
• A computer program in execution on a machine is a process

• More formally:
– A Sequential stream of Execution in its own address space

2
Why use processes?

• Why use processes?

– Express concurrency
– Systems have many concurrent jobs going on
– E.g. Multiple users running multiple shells, I/O, ...

• General principle of divide and conquer

– Decompose a large problem into smaller ones
– easier to think of well contained smaller problems
Process =? Program

• Program: series of
commands (e.g. C
statements, assembly
commands, shell
commands)

4
 Program != process

• Program: static code + static data

• Process: dynamic instantiation of code + data +
more

• Program process: no 1:1 mapping

– Process has more than code and data
– one program runs many processes
– many processes of same program
Process
• A computer program in execution on a machine is a process

• More formally:
– A Sequential stream of Execution in its own address space

6
Process Address Space
• A list of memory locations from some min (usually 0) to some
max that a process can read and write.

• Contains
– the executable program
– program’s data
– Stack
– Associated with a process is a set of registers e.g. PC,SP
and other information to run the program.

7
CPU State

• CPU registers contain the current state

1. Processor Status Word (PSW): includes
bits
2. Instruction Register (IR):
3. Program Counter (PC):
4. Stack Pointer (SP):
5. General purpose registers:

8
Environment
• Contains the relationships with other entities
• A process does not exist in a vacuum
• It typically has connections with other entities, such as
– A terminal where the user is sitting.
– Open files
– Communication channels to other processes, possibly on other
machines.

9
Process Control Block

• The OS keeps all the data it

needs about a process in
the process control block
(PCB)
• Thus another definition of a
process:
– “the entity described by a
PCB”
• This includes many of the
data items described above,
or at least pointers to where
they can be found
– e.g. for the address space

10
PCB
• PCB is "the manifestation of a process in an operating
system”.

• Data Structure defined in the operating system kernel

containing the information needed to manage a
particular process.

• It must be kept in an area of memory protected from

normal user access.

11
PCB
• In general a PCB includes:
– The identifier of the process (a process identifier, or PID)
– Register values for the process including, notably, the program counter
and stack pointer values for the process.
– The address space for the process
– Priority (in which higher priority process gets first preference. e.g., nice
value on Unix operating systems)
– Process accounting information, such as when the process was last run,
how much CPU time it has accumulated, etc.
– I/O Information (i.e. I/O devices allocated to this process, list of opened
files, etc.)

12
OS Data Process
Process Control Block
Structures Address
Space
RAM CPU
Kernel User
PSW

State text
IR
Memory .
Files
Accounting PC
Priority data
User SP
CPU register storage

heap General
Purpose
Registers
stack

13
CPU Switch From Process to
Process

14
CPU Switch From Process to
Process
• Switching a process requires
– Saving the state of old process
– Loading the saved state of the new process
• This is called Context Switch
• Part of OS responsible for switching the processor among the
processes is called Dispatcher

15
Trace from Processors point of view

Time
out
I/O
Process States
• At any given time a process is either running or not running
• Number of states
– Running
– Not Running
• When the OS creates a process, the process is entered into
which state?
– Not Running

18
Two-state process model
Dispatch

Enter Not Exit

Not Running
running
running Running

Pause

• Number of processes Running at a particular time?

• Number of processes Not Running at a particular time?
• Data Structure?
• Processes that are Not Running at a particular time should be kept
in some sort of a queue

19
Two-state process model
Processor
Queue
Enter Dispatch Exit

Pause

Dispatcher is now redefined:

• Moves processes to the waiting queue
• Remove completed/aborted processes
• Select the next process to run

20
How process state changes1

Ready Ready Ready

 a := 1  a := 1  a := 1
b := a + 1 read a file b := a + 1
c := b + 1 b := a + 1 c := b + 1
read a file c := b + 1 a := b - c
a := b - c a := b - c c := c * b
c := c * b c := c * b b := 0
b := 0 b := 0 c := 0

21
How process state changes2

Running Ready Ready

 a := 1  a := 1  a := 1
b a:=a:=a:=1+ 11 read a file b := a + 1
c b:=:=b a+ +1 1 b := a + 1 c := b + 1
c b:= :=b a
+ +
1 1
read
readc :=a file
bfile
+1 c := b + 1 a := b - c
a :=read a
b - ca file a := b - c c := c * b
c :=ac:=*b bb- c- c
a := Timeout
Timeout
c := c * b b := 0
b c:=c:=0:=c c* b* b b := 0 c := 0
b := 0
b := 0

22
How process state changes3

Ready Running Ready

a := 1  a := 1  a := 1
b := a + 1 a :=a1file
read b := a + 1
c := b + 1 b read
:= a +a 1file c := b + 1
 read a file cb:=:= ba ++ 11 a := b - c
a := b - c a c:=:=b b- c+ 1 c := c * b
c := c * b ca I/O
:=:=
I/Oc *b b- c b := 0
b := 0 b c:=:=0 c * b c := 0
b := 0

23
How process state changes4

Ready Blocked Running

a := 1 a := 1  a := 1
b := a + 1  read a file ba:=:=
a
1+ 1
a:= 11
c := b + 1 b := a + 1 c b:=:=b a+ + 1+ 1
b := a
 read a file c := b + 1 a:=c b:=- bc +1 1
c := b +
a := b - c a := b - c ca :=a:=c:=*b bb- c- c
c := c * b Timeout
Timeout
c := c * b b c:=c:=0:=c c* b* b
b := 0 b := 0 cb :=b:=0:=0 0
c := 0
c := 0

24
How process state changes5

Running Blocked Ready

a := 1 a := 1 a := 1
b := a + 1  read a file b := a + 1
c := b + 1 b := a + 1 c := b + 1
 read a file c := b + 1  a := b - c
a := b - c a := b - c c := c * b
c := c * b I/O
I/O
c := c * b b := 0
b := 0 b := 0 c := 0

25
How process state changes6

Blocked Blocked Running

The Next Process to
a := 1 a := 1 Run acannot
:= 1 be simply
b := a + 1  read a file b := a + 1
c := b + 1 b := a + 1 selected
c := bfrom
+1 the front
 read a file c := b + 1  a := b - c
a := b - c a := b - c c := c * b
c := c * b c := c * b b := 0
b := 0 b := 0 c := 0

26
How process state changes7

Blocked Blocked Running

a := 1 a := 1 a := 1
b := a + 1  read a file b a:=:=a 1+ 1
c := b + 1 b := a + 1 cb :=:=ba ++ 11
 read a file c := b + 1 c :=
 a := bb- c+ 1
a := b - c a := b - c ca :=:=c *b b- c
Suppose
Suppose the
the Green
Green process
c := c * b process finishes
finishes I/O
c := c * b b c:=:=0 c * b
I/O
b := 0 b := 0 cb :=:=00
c := 0

27
How process state changes8

Blocked Ready Running

a := 1 a := 1 a := 1
b := a + 1 read a file b a:=a:=a:=1+ 11
c := b + 1  b := a + 1 cb :=b:=
b:=a+ a+1 +1 1
 read a file c := b + 1 c :=
 a := b:=b- cb+ +1 1
c
a := b - c a := b - c ca :=a:=
c:=*b bb- c- c
c := c * b Timeout
Timeout
c := c * b b c:=:=0 c * b
c :=0 c * b
b := 0 b := 0 cb:=b:=
0
c :=:=0 0
c := 0

28
How process state changes9

Blocked Running Ready

a := 1 a := 1 a := 1
b := a + 1 a :=a1file
read b := a + 1
a :=a1file
read
c := b + 1  b :=read
a + 1a file c := b + 1
 read a file c :=bb:=a
b := + a+
1 +1 1 a := b - c
a := b - c a c:=:=b b- + cb 1 c := c * b
c := - c+ 1
c := c * b Timeout
ca:=a:=
Timeout c:=*b b
b-c b := 0
b := 0 b c:=c:=0:=c c* b* b  c := 0
b := 0
b := 0

29
Problem in Two-state Process
model
• A process may be waiting for I/O request
• A single queue for both the ready to run and
waiting processes
• The dispatcher cannot simply select the process
at the front, it can be a busy process
• In the worst case, it has to scan the whole queue
to find the next process to run
• Solution?
• Split the Not Running state to:
– Waiting, Ready
30
Five-state Process Model
• Running: currently being run
• Ready: ready to run
• Blocked: waiting for an event (I/O)
• New: just created, not yet admitted to set of run-able
processes
• Exit: completed/error exit

31
Five-state Process Model

Dispatch Release
Admit
New
New Ready
Ready Running
Running Exit
Exit
Time-out

Event
occurs Event wait

Blocked
Blocked

32
Diagram of Process State
Blocked Queues
Timeout

Ready queue Processor

Admit Dispatch
Release

Event occurs Blocked queue/ Event queue Event wait

Running process
Ready process
Blocked process

Further
FurtherEnhancement:
Enhancement:
AAseparate
separatequeue
queueholds
holdsthe
the
processes
processeswaiting
waitingfor
fordifferent
differentevent.
event.

34
Scheduling Queues
• The queues are generally stored as linked lists
• A queue header points to the first and the final PCB’s in the
list
• We extend each PCB to include a pointer field that points to
the next PCB in the ready queue

35
Scheduling Queues

36
Schedulers
• Short term Scheduler or CPU Scheduling
– Which program is to be run next
• Long term Scheduler or Job Scheduler
– Which ready jobs should be brought to memory
– May need to invoke only when a process leaves the system
– Must make a careful selection

37
Process Types
• Most processes can be described as either I/O bound or
CPU bound
• I/O bound:
– Spends more of its time doing I/O than doing computations
• CPU bound:
– Spends more of its time doing computations than doing I/O
• If all processes are I/O bound,
– The ready queue will almost always be empty
• If all processes are CPU bound,
– The I/O waiting queue will almost always be empty, devices will
go unused
– System will again be unbalanced

38
Process Types
• Sometimes OS may swap a blocked process to disk
to free up more memory
• Or to improve process mix
• This is called Swapping

39