Transcript Process and Thread

Process and Thread
Chapter 3
Advanced Operating System
Process


A program in execution
The entity that can be assigned to and
executed on a processor


Program code: which may be shared with
other processes that are elements of a
process
Set of data
Process

OS maintains the following for a process




Executable program (.EXE, .DLL, etc)
Data (variables, constant, buffer, …)
User stack (local variables, function call)
Process control block (PCB)
Process management

Interleave the execution of several
processes ...




to maximize processor utilization
while providing reasonable response time
Allocate resources to processes
Support inter-process communication
Dispatcher


Program that moves the processor from
one process to another
Prevents a single process from
monopolizing processor time.

Every process should be able to use the
processor for a fair amount of time
Two-state process model
Dispatch
Enter
Exit
Not
running
Running
Pause
Two-state process model







The operating system creates a new process
Operating system creates PCB
Operating system enters process into the system in
the not running state
The process exists is waiting to execute
The currently running process will be interrupted
The dispatcher will select some other process to run
The former process moves from the running state to
the not running state, and one of the other processes
move to the running state
Process creation




Submission of a batch job
User logs on
Create to provide a service such as
printing
Spawned by an existing process
Process creation



Process spawning: When the operating
system creates a process at the explicit
request of another process
When one process spawns another, the
former is referred to as the parent
process
The spawned process is referred to as
the child process
Process termination




Batch job issues Halt instruction
User logs off
Process executes a service request to
terminate
Parent terminates so child processes
terminate
Process termination

Operating system intervention


E.g. when deadlock occurs
Error and fault conditions

E.g. memory unavailable, protection error,
arithmetic error, I/O failure, invalid
instruction
Round-robin scheduling


The queue is a first-in-first-out list
The processor operates in round-robin
fashion on the available process

Each process in the queue is given a
certain amount of time, in turn, to execute
and then returned to the queue, unless
blocked
Round-robin scheduling
queue
dispatch
processor
Each process is
allowed to execute for
at most a quantum.
At timeout, process
switching occurs.
Process is preempted when…

In the following two cases, a process
cannot continue running and must leave
the processor. It is preempted.


Timeout
I/O, or wait for other events
Two states are not enough...

Not-running:



ready to execute
blocked, e.g. waiting for I/O
Dispatcher cannot just select the
process that has been in the queue the
longest (i.e. the one in queue front)
because it may be blocked
Running process
Ready process
Blocked process
Five-state Process Model
Dispatch
Admit
New
Ready
Release
Running
Time-out
Event
occurs
Blocked
Event wait
Exit
Five-state Model





Running – being executed by the
processor
Ready – ready to execute
Blocked – cannot execute until some
event occurs
New – created, but not yet admitted
Exit – released
Blocked Queues
Timeout
Ready queue
Admit
Processor
Dispatch
Release
Event occurs
Blocked queue/ Event queue
Event wait
Running process
Ready process
Blocked process
A separate queue holds the
processes waiting for each event.
How process state changes (1/8)
ready
 a := 1
b := a + 1
c := b + 1
read a file
a := b - c
c := c * b
b := 0
ready
 a := 1
read a file
b := a + 1
c := b + 1
a := b - c
c := c * b
b := 0
ready
 a := 1
b := a + 1
c := b + 1
a := b - c
c := c * b
b := 0
c := 0
How process state changes (2/8)
running
 a := 1
 b := a + 1
 c := b + 1
read a file
a := b - c
c := c * b
b := 0
ready
 a := 1
read a file
b := a + 1
c := b + 1
a := b - c
c := c * b
b := 0
ready
 a := 1
b := a + 1
c := b + 1
a := b - c
c := c * b
b := 0
c := 0
Timeout
How process state changes (3/8)
ready
a := 1
b := a + 1
c := b + 1
 read a file
a := b - c
c := c * b
b := 0
running
 a := 1
 read a file
b := a + 1
c := b + 1
a := b - c
c := c * b
b := 0
ready
 a := 1
b := a + 1
c := b + 1
a := b - c
c := c * b
b := 0
c := 0
Start I/O
How process state changes (4/8)
ready
a := 1
b := a + 1
c := b + 1
 read a file
a := b - c
c := c * b
b := 0
blocked
running
a := 1
zz read a file
b := a + 1
c := b + 1
a := b - c
c := c * b
b := 0
 a := 1
 b := a + 1
 c := b + 1
a := b - c
c := c * b
b := 0
c := 0
Timeout
How process state changes (5/8)
running
blocked
a := 1
b := a + 1
c := b + 1
 read a file
a := b - c
c := c * b
b := 0
a := 1
zz read a file
b := a + 1
c := b + 1
a := b - c
c := c * b
b := 0
ready
a := 1
b := a + 1
c := b + 1
 a := b - c
c := c * b
b := 0
c := 0
Start I/O
How process state changes (6/8)
blocked
blocked
running
a := 1
b := a + 1
c := b + 1
zz read a file
a := b - c
c := c * b
b := 0
a := 1
zz read a file
b := a + 1
c := b + 1
a := b - c
c := c * b
b := 0
a := 1
b := a + 1
c := b + 1
 a := b - c
 c := c * b
b := 0
c := 0
Suppose the
Green process
finishes I/O
How process state changes (7/8)
blocked
a := 1
b := a + 1
c := b + 1
zz read a file
a := b - c
c := c * b
b := 0
ready
a := 1
read a file
 b := a + 1
c := b + 1
a := b - c
c := c * b
b := 0
running
a := 1
b := a + 1
c := b + 1
a := b - c
c := c * b
 b := 0
c := 0
Timeout
How process state changes (8/8)
blocked
running
a := 1
b := a + 1
c := b + 1
zz read a file
a := b - c
c := c * b
b := 0
a := 1
read a file
 b := a + 1
 c := b + 1
 a := b - c
c := c * b
b := 0
ready
a := 1
b := a + 1
c := b + 1
a := b - c
c := c * b
b := 0
 c := 0
Timeout
Suspend Processes

Suspend – stop the execution of a
process temporarily




OS may suspend a process that causes a
problem
Interactive user request
Timing: a process that executes
periodically
Swapping: sometimes OS may swap a
blocked process to disk to free up more
memory
Suspend states


Ready,
Two new states: suspend
Think about these…



Blocked,
suspend
What’s the meaning of the two new states?
Why not a single ‘suspend’ state?
Why no ‘running, suspend’ state?
Process state transition with suspend
states
New
Admit
Admit
Suspend
Ready,
suspend
Dispatch
Activate
Ready
Timeout
Suspend
Event
Occurs
Event
Occurs
Blocked,
suspend
Running
Activate
Blocked
Suspend
Event
Wait
Exit
Release
An example of state transition
Running
The process starts an
I/O operation
Blocked
Blocked
suspend
The process is suspended while
waiting for the I/O to finish
I/O is finished
The process is
activated
afterwards
Ready
suspend
Ready
The process
is activated
before I/O is
finished
Blocked
I/O is finished
Ready
Process control block (PCB)


Operating system creates and manages
a process control block
PCB is the key tool that enables the
operating system


to support multiple processes
to provide the multiprocessing
Process Control Block


PCB contains data that
the OS needs to control
the process
PCB consists of



Process identification
Processor state
information
Process control
information
PCB
Process identification
pid:123
uid:tom
Processor state info
ax, bx, cx, eflags, pc, …
cs, ds, ss, …
Process control info
…
…
Process Identification


Process ID, a unique numeric identifier
User identifier


who is responsible for the job, or who runs
the process
used to determine what access rights the
process has
Processor State Information

Processor state: contents of processor
registers, incl.




Data registers
Address registers: e.g. stack pointer
Control and status registers
Used to save and restore the processor
state in process switching
Process Control Information

Additional information needed by the
operating system to control and coordinate
the various active processes






scheduling and state information
data structuring
interprocess communication
process privileges
memory management
resource ownership and utilization
Process switching may happen
at…



Interrupt – an interruption request from
hardware external to the CPU
Trap – an error condition or exceptional
condition associated with the current
instruction
Supervisor call – call of some special
functions of the OS
Process switching may happen
at…

Interrupts



Clock
I/O: I/O completion, I/O error
Traps





Timeout
illegal file access attempt
memory fault
Supervisor call
file open, read a char
synchronization primitive
Event occurs
Event
wait
Process switching at Interrupt
Timeout checked in
clock interrupt
(In OS that implements priority)
When the I/O operation is finished for
a blocked process, it is waken up. If
its priority is higher than the running
process, it will be dispatched.
In case of I/O error (interrupt),
the blocked process that is
waiting for the I/O may be
terminated.
Process switching at Trap
In case error conditions caught as traps
(memory fault, illegal access..), the
process may be terminated, or blocked
(or suspended) by the OS.
Process switching at Supervisor
call
A process may be blocked in
executing supervisor call (for
I/O, synchronization …)
Process Switching, Steps

Consists of the following steps
1

2

3

Save processor state (incl. program
counter and other registers) in the PCB:
processor state information
Update the PCB with the new state and
any accounting information
Move the PCB to appropriate queue –
ready, blocked
Process Switching, Steps

(Continue)
4

5

6 
7 
Select another process for execution
Update the PCB of the process selected
(new state and accounting information)
Update memory-management data
structures
Restore context of the selected process

restore the previous value of the program
counter and other registers from the PCB
Steps in Process Switching (1/10)
PCB of process A
PCB of process B
state ready
state ready
AX
0
AX
10
PC
A0
PC
B0
Memory used by A
 A0: mov AX, a
A1: inc AX
A2: mov a, AX
Memory used by B
 B0: mov AX, 8
B1: mov b, AX
a 2
b 99
a++
b=8
CPU
AX xx
PC xx
Steps in Process Switching (2/10)
PCB of process A
PCB of process B
state running
state ready
AX
0
AX
10
PC
A0
PC
B0
Memory used by A
 A0: mov AX, a
A1: inc AX
A2: mov a, AX
a 2
CPU
AX 0
PC A0
Memory used by B
 B0: mov AX, 8
B1: mov b, AX
b 99
Process A is dispatched. PCB of A is updated, and the processor
state information is copied to the CPU.
Steps in Process Switching (3/10)
PCB of process A
PCB of process B
state running
state ready
AX
0
AX
10
PC
A0
PC
B0
Memory used by A
A0: mov AX, a
 A1: inc AX
A2: mov a, AX
a 2
After executing A0
Memory used by B
 B0: mov AX, 8
B1: mov b, AX
b 99
CPU
AX 2
PC A1
Steps in Process Switching (4/10)
PCB of process A
PCB of process B
state running
state ready
AX
0
AX
10
PC
A0
PC
B0
Memory used by A
A0: mov AX, a
A1: inc AX
 A2: mov a, AX
a 2
After executing A1
Memory used by B
 B0: mov AX, 8
B1: mov b, AX
b 99
CPU
AX 3
PC A2
Steps in Process Switching (5/10)
PCB of process A
PCB of process B
state ready
state ready
AX
3
AX
10
PC
A2
PC
B0
Memory used by A
A0: mov AX, a
A1: inc AX
 A2: mov a, AX
a 2
CPU
AX 3
PC A2
Memory used by B
 B0: mov AX, 8
B1: mov b, AX
b 99
Timeout for Process A, which state changes from running to ready.
PCB of A is updated, and the processor state information is copied
from the CPU.
Steps in Process Switching (6/10)
PCB of process A
PCB of process B
state ready
state running
AX
3
AX
10
PC
A2
PC
B0
Memory used by A
A0: mov AX, a
A1: inc AX
 A2: mov a, AX
a 2
CPU
AX 10
PC B0
Memory used by B
 B0: mov AX, 8
B1: mov b, AX
b 99
Process B is dispatched. PCB of B is updated, and the processor
state information is copied to the CPU.
Steps in Process Switching (7/10)
PCB of process A
PCB of process B
state ready
state running
AX
3
AX
10
PC
A2
PC
B0
Memory used by A
A0: mov AX, a
A1: inc AX
 A2: mov a, AX
Memory used by B

a 2
After executing B0 and B1
B0: mov AX, 8
B1: mov b, AX
b 8
CPU
AX 8
PC B2
Steps in Process Switching (8/10)
PCB of process A
PCB of process B
state ready
state ready
AX
3
AX
8
PC
A2
PC
B2
Memory used by A
A0: mov AX, a
A1: inc AX
 A2: mov a, AX
a 2
CPU
AX 8
PC B2
Memory used by B

B0: mov AX, 8
B1: mov b, AX
b 8
Timeout for Process B, which state changes from running to ready.
PCB of B is updated, and the processor state information is copied
from the CPU.
Steps in Process Switching (9/10)
PCB of process A
PCB of process B
state running
state ready
AX
3
AX
8
PC
A2
PC
B2
Memory used by A
A0: mov AX, a
A1: inc AX
 A2: mov a, AX
a 2
CPU
AX 3
PC A2
Memory used by B

B0: mov AX, 8
B1: mov b, AX
b 8
Process A is dispatched. PCB of A is updated, and the processor
state information is copied to the CPU.
Steps in Process Switching
(10/10)
PCB of process A
PCB of process B
state running
state ready
AX
3
AX
8
PC
A2
PC
B2
Memory used by A

A0: mov AX, a
A1: inc AX
A2: mov a, AX
a 3
After executing A2
Memory used by B

B0: mov AX, 8
B1: mov b, AX
b 8
CPU
AX 3
PC A3
Process

Each process has


Some resources allocated by OS, including
memory to hold the process image
A single thread of execution


Only one instruction is being run at a time
More threads of execution

For each thread, only one instruction is being
run at a time
Process v.s. Thread

Process – Unit of resource ownership


Thread – Unit of dispatching



memory, files, I/O
an execution path
execution may be interleaved with other
threads / processes
A process has one or more threads
“More than one threads..”
Sometimes, we want to have
more than one threads of
execution inside a single
process. The multiple threads
can share memory and other
resources, while they can run
‘at the same time’.
OS Support for Threads and
Processes
one process one thread
e.g. MS-DOS
multiple processes
one thread per process
e.g. traditional Unix
one process
multiple threads
e.g. JVM
multiple processes
multiple threads per process
e.g. Windows 2000, Solaris,
Apple OS X, BeOS, Linux, OS/390
Thread

Has an execution state



Running, ready, blocked, suspend states …
Has an execution stack
Thread context is saved and restored in
thread switching

Read the following slides for how to
change the steps of process switching to
the steps of thread switching
Thread


Has access to the memory and
resources of its process
Has some per-thread static storage for
local variables
Single Threaded and Multithreaded Process
Models
Process
Control
Block
stack
Program
Data
Process image in
a single-threaded
process
Process image in
a multithreaded
process
In multithreaded process model, the OS
keeps a Thread Control Block (TCB) for
each thread. Much content of the original
PCB is moved to TCB for each thread.
Each thread has a TCB and a stack.
Process
Control
Block
Program
Data
Thread
Control
Block
Thread
Control
Block
stack
stack
Thread Switching, Steps

Consists of the following steps
1

2

3

Save processor state (incl. program
counter and other registers) in the TCB:
processor state information
Update the TCB with the new state and
any accounting information
Move the TCB to appropriate queue –
ready, blocked
Thread Switching, Steps

(Continue)
4

5

M

6

Select another thread for execution
Update the TCB of the thread selected
(new state and accounting information)
Update memory-management data
structures
Restore context of the selected thread

restore the previous value of the program
counter and other registers from the TCB
Thread Switching, Steps
(simplified)

Thread switching from thread A to thread B
1

2

3

4

5


6

Save thread context of thread A: CPU  TCB A
Update state in TCB A
Move TCB A to appropriate queue
Select another thread (thread B)
Update state in TCB B
Update memory-management data structures
Restore thread context of thread B: TCB B  CPU
Benefits of Threads



Less time to create / terminate a new thread
than a process
Less time to switch between two threads
within the same process
Communication among threads of the same
process is easier
Benefits of Threads

Less time to create / terminate a new thread
than a process


When the OS creates a process, it has to allocate
memory for the process image, load the program
and data, and initialize other resources
When the OS creates a thread within an existing
process, it does not need to initialize the process
image. It only needs to set up a stack and TCB
for the new thread.
Benefits of Threads

Less time to switch between two threads
within the same process

The “update memory management data structure”
step is only necessary in case of thread switching
between different process.
Benefits of Threads

Communication among threads of the same
process is easier


Threads within a process share memory and files
Different processes have to communicate with the
help of the kernel
Kernel is the core of OS
Multiprocessing



Refers to a computer system’s ability to support more
than one process (program) at the same time.
Multiprocessing operating system enable several
programs to run concurrently. UNIX is one of the
most widely used multiprocessing systems, but there
are many others, including OS/2 for high-end PCs.
Multiprocessing systems are much more complicated
than single-process systems because the operating
system must allocate resources to competing
processes in a reasonable manner.
Multithreading


The ability of an operating system to
execute different parts of a program,
called threads, simultaneously.
The programmer must carefully design
the program in such a way that all the
threads can run at the same time
without interfering with each other.