Transcript Processes

Course Overview
Principles of Operating Systems







Introduction
Computer System
Structures
Operating System
Structures
Processes
Process Synchronization
Deadlocks
CPU Scheduling
© 2000 Franz Kurfess








Memory Management
Virtual Memory
File Management
Security
Networking
Distributed Systems
Case Studies
Conclusions
Processes 1
Chapter Overview
Processes







Motivation
Objectives
Processes and Programs
Process States
Operations on Processes
Operating System Control
Structures
Process Control Block
© 2000 Franz Kurfess






Processes and Threads
Process Scheduling
Cooperating Processes
Interprocess
Communication
Important Concepts and
Terms
Chapter Summary
Processes 2
Motivation
 applications
can only run through the use of
processes
 processes are the fundamental unit of operation in
an operating system
 most components of the operating systems provide
services for the execution of processes
 processes require resources for their execution
© 2000 Franz Kurfess
Processes 3
Objectives
 understand
the use of processes for running
programs
 know the requirements and mechanisms for the
execution of processes
 understand the principles of cooperation between
processes
 acquire the terminology related to processes and
their execution
© 2000 Franz Kurfess
Processes 4
Processes and Programs
 both
terms are used to describe the activities
performed by a computer
 program refers to the instructions as specified by the
programmer
 process refers to the activities performed by the
computer as the instructions of a program are
executed
© 2000 Franz Kurfess
Processes 5
Terminology
 program
 application
 job
 task
 process
 thread
© 2000 Franz Kurfess
Processes 6
Program
 set
of instructions specifying the activities necessary
to accomplish a task
 frequently used in a broad sense
 static: usually doesn’t change unless modified by the
programmer
© 2000 Franz Kurfess
Processes 7
Application
 program
used for a specific task
 often used for programs available to the user, in
contrast to programs used internally by the OS
© 2000 Franz Kurfess
Processes 8
Job
 used
to describe the unit of work in a batch system
 frequently used synonymously to process
© 2000 Franz Kurfess
Processes 9
Task
 unit
of work from the user’s perspective in a timesharing or multitasking system
 often corresponds to an application program
 may comprise several processes
© 2000 Franz Kurfess
Processes 10
Process
 program
in execution
 unit of work from the OS perspective, in particular
with respect to resource ownership
 dynamic: changes its state over time (during
execution)
 may consist of several threads
© 2000 Franz Kurfess
Processes 11
Thread
 smallest
dispatchable unit in the OS
 several threads are usually grouped into a process,
and can cooperate on a task
 sometimes also called lightweight processes
© 2000 Franz Kurfess
Processes 12
Execution of Programs
 multiprogramming
 multiprocessing
 multitasking
 multithreading
© 2000 Franz Kurfess
Processes 13
Example Processes
 consider
three processes
 process A executes
100 instructions, reads two blocks
from hard disk, and executes another 100 instructions
 process B reads one block from hard disk, executes 100
instructions, and writes one block to disk
 process C executes 1000 instructions, and writes two
blocks to disk
 timing
 10
ns per CPU instruction (100 MHertz clock frequency)
 10 ms average transfer time per block between hard disk
and memory
© 2000 Franz Kurfess
Processes 14
Example Single-Programming
A
B
1,000 ns
CPU
1,000 ns
I/O
CPU
20 ,000 ,000 ns


I/O
C
1,000 ns
CPU
I/O
10 ,000 ,000 ns 10 ,000 ,000 ns
10,000 ns
CPU
I/O
20 ,000 ,000 ns
overall execution time for single-programming
20,002,000 + 20,001,000 + 20,010,000 ns = 60,013,000 ns
CPU is idle for 60,000,000 ns
© 2000 Franz Kurfess
Processes 15
Multiprogramming
 several
programs are simultaneously under
execution
 they
are between start and finish
 simultaneously refers to a human time-scale (seconds)
 at the CPU time scale, only one process is handled by the
CPU (single processor systems)
 creates
logical parallelism
 mainly used in batch systems to increase CPU
utilization
© 2000 Franz Kurfess
Processes 16
Example Multiprogramming
1,000 ns
A
1,000 ns
I/O A
CPU A
CPU A

20 ,000 ,000 ns
1,000 ns
B
I/O B CPU B
10 ,000 ,000 ns
I/O B
10 ,000 ,000 ns

logical parallelism: all three
programs are run
simultaneously
problem: only one CPU
available
10,000 ns
C
CPU C
I/O C
20 ,000 ,000 ns
© 2000 Franz Kurfess
Processes 17
Example Multiprogramming
1,000 ns 10,000 ns
Proc. A
Proc. C
I/O B
10 ,000 ,000 ns

1,000 ns
Proc. B
Proc. A
I/O A
20 ,000 ,000 ns
Attention:
Dimensions
not to scale
I/O B
I/O C
20 ,000 ,000 ns
10 ,000 ,000 ns
solution:



1,000 ns
multiplexing of the CPU by switching between processes
I/O operations concurrently with CPU operations
problem:


more complex
requires process management
© 2000 Franz Kurfess
Processes 18
Multiprocessing
 several
processes run simultaneously on different
CPUs
 creates physical parallelism
 advantages
 short
overall execution time
 problems
 CPUs
might have to share
memory, I/O devices
 low CPU utilization
 communication between processes
 process allocation and
load balancing
© 2000 Franz Kurfess
Processes 19
Example Multiprocessing
1,000 ns
CPU 1
1,000 ns
I/O A
Proc. A
Proc. A
20 ,000 ,000 ns

physical parallelism: all
three programs are run
simultaneously on three
different CPUs
1,000 ns
CPU 2
I/O B Proc. B
10 ,000 ,000 ns
I/O B
10 ,000 ,000 ns
10,000 ns
CPU 3
Proc. C
I/O C
20 ,000 ,000 ns
© 2000 Franz Kurfess
Processes 20
Multitasking
 conceptually
similar to multiprogramming: better
CPU utilization by switching between processes
 more frequent switching so that users can interact
with the program
 necessary for time-sharing system
© 2000 Franz Kurfess
Processes 21
Multithreading
 within
one single process, multiple threads of
execution are used
 independent activities within one program or
application can be performed in parallel
 either
on different CPUs, or via switching between threads
 decreases
the overhead of switching between
processes
© 2000 Franz Kurfess
Processes 22
Process States
 over
their existence, processes can be in different
states
 newly
created
 ready to run on the CPU
 running on the CPU
 blocked because it is waiting for an event or an I/O
operation
 terminated
© 2000 Franz Kurfess
Processes 23
Process State Diagram
new
terminated
admission
release
dispatch
ready
running
time-out
I/O or event
completion
© 2000 Franz Kurfess
blocked
I/O or event
wait
Processes 24
Operations on Processes
 process
 new
creation
batch job, user login, OS service, child process
 process
termination
 normal
completion, time limit exceeded, resources
unavailable, protection error, calculation error, invalid
instruction, OS intervention, parent termination, parent
request
 context
switch
 execution
of one process is stopped, and another process
continues
 change
of process state
 implicit
via context switch, explicit by the OS
© 2000 Franz Kurfess
Processes 25
Operating System
Control Structures
 used
to maintain information about important entities
and activities in the computer system
 management of processes and resources
 information about the status of processes and
devices
 usually stored in tables, possibly with pointers to
further information
 cross-references must exist between different tables
 the OS must know the basic configuration of the
computer system
© 2000 Franz Kurfess
Processes 26
OS Control Structures
Memor
y
Tables
Devic
e
Tables
File
Tables
Memory
Devices
Files
Processes
Process Image
Process 1
Process Image
Process
Tables
Process 1
Process 2
Process 3
Process n
.
.
.
Process n
© 2000 Franz Kurfess
[adapted from Stallings 98]
Processes 27
Memory Tables
 used
to keep track of memory usage
 allocation

OS and user processes
 allocation

of secondary memory to processes
swap space or virtual memory
 protection

of main memory to processes
attributes of memory segments
access permissions
© 2000 Franz Kurfess
Processes 28
I/O Tables
 used
for the management of I/O devices
 allocation
of devices to processes
 status of devices



available, allocated to a process
I/O operation in progress
memory segment involved in the I/O operation
 in
some operating systems, I/O devices are integrated into
the file system
© 2000 Franz Kurfess
Processes 29
File Tables
 used
for the management of files and directories
 access


 file


information for files
name, path
location on secondary memory
status information
open, closed
processes using the file
© 2000 Franz Kurfess
Processes 30
Process Tables
 used
for the management of processes
 location of the process
 main
memory, secondary storage
 process
attributes
 process

identification (pid)
unique number, often used as index into the process table
 parent
process, affiliated user, children
© 2000 Franz Kurfess
Processes 31
Process Image
 user
program
 program
 user
to be executed
data
 program
 system
data, user stack, modifiable parts of the program
stack
 parameters,
procedure call and return addresses
 at least one per process
 process
control block
 essential
© 2000 Franz Kurfess
process data needed by the OS
Processes 32
Process Control Block
 process
identification
 processor state information
 process control information
© 2000 Franz Kurfess
Processes 33
Process Identification
 process
id, parent process, user id
 used by the operating system for all activities
involving processes
 process
management, main memory, I/O devices,
interprocess communication
 cross-reference to between process and other OS tables
© 2000 Franz Kurfess
Processes 34
Processor State Information
 user
registers
 registers
 system
available to the user program
registers
 used
for control and status information
 program counter, condition codes (e.g. division by zero,
overflow), status register (interrupt enabled, system/user
mode)
 stack
pointers
 points
to the top of system stacks
 these stacks contain parameters, procedure call and
return addresses, and execution-related data
© 2000 Franz Kurfess
Processes 35
Process Control Information
 scheduling
 process
 process
and state information
state, priority, time in ready queue, etc.
relations
 links
to other processes (waiting queues,
parent/child)interprocess communications
 flags, signals, messages, shared memory
 process
privileges
 memory
 memory
access, instruction execution, resources
management
 pointers
to memory segments used by the process
 resources
 ownership
© 2000 Franz Kurfess
and utilization of resources
Processes 36
Processes and Address Spaces
Process 1
Process 2
Process n
Process
Identification
Process State
Information
Process Control
Information
Process
Identification
Process State
Information
Process Control
Information
Process
Identification
Process State
Information
Process Control
Information
System Stack
System Stack
System Stack
User Stack
User Stack
Process
Control
Block
User Stack
User
Address Space
Shared
Address Space
© 2000 Franz Kurfess
User
Address Space
User
Address Space
Shared
Address Space
[adapted from Stallings 98]
Processes 37
Processes in Memory
Process 2



several processes need to
be accomodated
OS has its own memory
section
simplified view



larger number of processes
processes do not occupy one
single section in memory, but
several smaller ones (noncontiguous allocation)
not the whole process image
is always present in memory
(virtual memory)
© 2000 Franz Kurfess
Main Memory
Process n
Process 1
Operating
System
Processes 38
Process Scheduling
 objective:
efficient allocation of CPU processing time
to processes
 in
uniprocessor systems: multiplexing of the CPU between
processes
 in multiprocessor systems: allocation of processes to
CPUs, load balancing across CPUs, multiplexing if there
are more processes than processors
 very
important in multiprogramming and multitasking
 maximization
of CPU utilization
 interaction between programs and users
© 2000 Franz Kurfess
Processes 39
Schedulers
 job
scheduler
 long-term
scheduling
 medium-term
 not
 CPU
scheduler
used in all systems
scheduler
 short-term
© 2000 Franz Kurfess
scheduling
Processes 40
Job Scheduler
 manages
processes that can’t be executed
immediately
 not
enough memory available
 CPU load too high
 processes waiting for I/O are kept separately
 controls
the degree of multiprogramming
 number
 is
of processes in main memory
not invoked too frequently
 mainly
© 2000 Franz Kurfess
when processes enter or leave the system
Processes 41
Medium-Term Scheduler
 processes
are temporarily moved out of main
memory to secondary storage (“swapping”)
 memory
space restrictions
 to improve the process mix (balance between
CPU-intensive and I/O-intensive processes)
 determines
© 2000 Franz Kurfess
which processes to swap out and in
Processes 42
CPU scheduler
 manages
processes in the ready queue
 processes
have all the resources they need, except for
CPU time
 is
invoked very frequently
a
process requests an I/O operation
 time slice of a process is over
 interrupt or trap
 OS intervention
 must
be very fast to reduce overhead
© 2000 Franz Kurfess
Processes 43
Scheduling Queues
 first-in,
first-out (FIFO) data structures used to
administer the scheduling of processes
 types of queues
 job
queue: newly created processes not yet ready for
execution
 ready queue: processes in main memory and ready for
execution
 device queue: processes waiting for a particular device
 event queue: processes waiting for an event
 queuing
 can
diagrams display the interdependencies
be derived from the process state diagram
© 2000 Franz Kurfess
Processes 44
Two-State Process Model
Process State Diagram
admission
dispatch
not running
running
release
pause
Queuing Diagram
admission
© 2000 Franz Kurfess
release
dispatch
Queue
CPU
pause
[adapted from Stallings 98]
Processes 45
Five-State Process Model
new
terminated
admission
release
dispatch
ready
running
time-out
I/O or event
completion
© 2000 Franz Kurfess
blocked
I/O or event
wait
Processes 46
Queuing Diagram Five-State
admission
Job Queue
release
forward
dispatch
Ready Queue
CPU
time-out
Event 1 Queue
Event 2 Queue
I/O or event
completion
© 2000 Franz Kurfess
.
.
.
Event n Queue
I/O or event
wait
Processes 47
Context Switch
 the
execution of one process on the CPU is halted,
and the CPU continues with another
 information about the old process must be saved
 saved information about the new process must be
restored
 highly dependent on hardware support
 multiple
sets of registers
 special instructions, e.g. to load and store registers
 context
switching time is pure overhead
 no
productive work is done
 should be kept as low as possible
© 2000 Franz Kurfess
Processes 48
Threads
 reduce
the overhead of context switching
 only
essential information about individual threads is
saved for a thread switch

program counter, register set, stack
 other
information is shared by a group of threads within a
process or task

code section, data section, resources
 enable
asynchronous and distributed processing
 support modular programs
 also sometimes referred to as lightweight processes
© 2000 Franz Kurfess
Processes 49
Types of Threads
 user-level
threads
 managed
by the user process instead of the OS
 uses user-level libraries instead of system calls
 often more efficient since the OS is not involved
 can be difficult to program
 kernel-level
threads
 scheduled
by the OS
 threads may be distributed over several processors
© 2000 Franz Kurfess
Processes 50
Multithreaded Process Model
Process
Process
Identification
Process State
Information
Process Control
Information
Process Control Block
User
Address Space
Shared
Address Space
© 2000 Franz Kurfess
Thread 1
Thread 2
Thread 3
Thread
Identification
Thread State
Information
Thread Control
Information
Thread
Identification
Thread State
Information
Thread Control
Information
Thread
Identification
Thread State
Information
Thread Control
Information
User
Stack
User
Stack
User
Stack
System
Stack
System
Stack
System
Stack
[adapted from Stallings 98]
Processes 51
Cooperating Processes
 processes
existing simultaneously may be
independent or cooperating processes
 independent:
not affected by the execution of other
processes in the system

processes are not completely independent since they have to
share resources
 cooperating:



influences the execution of other processes
information sharing
computation speedup
modularity
© 2000 Franz Kurfess
Processes 52
Example: Producer-Consumer
a
producer process produces data that is consumed
by a consumer process
 a buffer is used to allow producer and consumer
processes to run concurrently
 unbounded
buffer: unlimited size
 bounded buffer: limited size
 explicitly coded (shared memory) or provided by the OS
(interprocess communication)
 shared data are accessed through regular memory read
and write operations
© 2000 Franz Kurfess
Processes 53
Interprocess Communication
 mechanisms
for processes to communicate and
synchronize their activities
 does
not rely on shared variables or shared memory
 communication
links must be established between
processes
 basic operations
 send(message)
 receive(message)
© 2000 Franz Kurfess
Processes 54
Direct Communication
 processes
must explicitly name the recipient or
sender of the messages
 send(receiver,
message)
 receive(sender, message)
 processes
must know each other’s identity
 properties of direct links
 links
are established automatically by the OS
 one link between a pair of processes
 a link is associated with exactly two processes
© 2000 Franz Kurfess
Processes 55
Indirect Communication
 messages
are sent to and received from mailboxes
 send(mailbox_1,
message)
 receive(mailbox_1 , message)
 processes
can communicate only if they share a
mailbox
 properties of direct links
 links
are established only if there is a common mailbox
 mailboxes are created by the OS
 there may be several links between a pair of processes
 a mailbox may be associated with several processes
© 2000 Franz Kurfess
Processes 56
Important Concepts and Terms














address space
CPU scheduler
computer system
context switch
graphical user interface
hardware
interprocess communication
job
kernel-level thread
lightweight process
link
mailbox
message
message passing
© 2000 Franz Kurfess














multiprocessing
multiprogramming
multitasking
multithreading
port
process
register
resources, services
scheduling
shared memory
stack
task
thread
user-level thread
Processes 57
Chapter Summary Processes
a
process is a program in execution
 it
is the dynamic entity associated with a static program
 a process requires resources

a
CPU time, main memory, I/O devices
process can be in one of several states

new, ready, running, blocked, terminated
 process
control block contains important information
 processes
 short,
are scheduled for execution
medium, long term scheduling
 processes
can run concurrently
 independent
or cooperating
 multiplexing in a single-processor system
© 2000 Franz Kurfess
Processes 58