Chapter 3: Processes

Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013
 Chapter 3: Processes

 Process Concept
 Process Scheduling
 Operations on Processes
 Interprocess Communication

Operating System Concepts – 9th Edition 3.2 Silberschatz, Galvin and Gagne ©2013
 Objectives
 To introduce the notion of a process
 To describe the various features of
processes, including scheduling, creation
and termination, and communication
 To explore interprocess communication
using shared memory and message
passing

Operating System Concepts – 9th Edition 3.3 Silberschatz, Galvin and Gagne ©2013
 Process Concept
 Process is a program in execution, which forms the basis of
all computation.
 process execution must progress in sequential fashion.
 Multiple parts:
 The program code, also called text section
 Current activity including program counter, and the
contents of the processor’s registers
 Stack containing temporary data
 Function parameters and local variables
 Data section containing global and static variables
 Heap which is a memory that is dynamically allocated
during process run time

Operating System Concepts – 9th Edition 3.4 Silberschatz, Galvin and Gagne ©2013
 Process in Memory

Operating System Concepts – 9th Edition 3.5 Silberschatz, Galvin and Gagne ©2013
 Process Concept (Cont.)
 A program by itself is not a process; program is
passive entity, such as a file containing a list of
instructions stored on disk (executable file);
process is an active entity, with a program counter
specifying the next instruction to execute and a set
of associated resources.
 Program becomes process when executable file
loaded into memory.
 Two common techniques for loading executable
files are double-clicking an icon representing the
executable file and entering the name of the
executable file on the command line.

Operating System Concepts – 9th Edition 3.6 Silberschatz, Galvin and Gagne ©2013
 Process Concept (Cont.)
 One program can be several processes.
 Consider multiple users executing the same
program, or the same user may invoke
many copies of the Web browser program.
Each of these is a separate process, and
although the text sections are equivalent,
the data, heap, and stack sections vary.

Operating System Concepts – 9th Edition 3.7 Silberschatz, Galvin and Gagne ©2013
 Process State
 As a process executes, it changes its state. The
state of a process is defined by the current activity
of that process.
 new: The process is being created
 ready: The process is loaded into memory and
waiting to be assigned to a processor
 running: Instructions are being executed by the
processor
 waiting: The process is waiting for some event
to occur
 terminated: The process has finished execution

Operating System Concepts – 9th Edition 3.8 Silberschatz, Galvin and Gagne ©2013
 Diagram of Process State

It is important to realize that only one process can be

running on any processor at any time. Many processes
may be ready and waiting,

Operating System Concepts – 9th Edition 3.9 Silberschatz, Galvin and Gagne ©2013
 Process Control Block (PCB)
A PCB is a data structure maintained by the OS and
contains information associated with each process
(also called task control block) including these:
 Process ID - unique identification for each of the
process in the operating system.
 Process state – current state of the process e.g. new,
ready, running, waiting, etc.
 Process privileges - this is required to allow/disallow
access to system resources.
 Pointer - a pointer to parent process.
 Program counter –indicates the address of the next
instruction to be executed for this process.

Operating System Concepts – 9th Edition 3.10 Silberschatz, Galvin and Gagne ©2013
 Process Control Block (PCB)
 CPU registers – contents of all process-centric
registers
 CPU scheduling information- priorities, scheduling
queue pointers
 Memory-management information – memory
allocated to the process
 Accounting information – CPU used, clock time
elapsed since start, time limits
 I/O status information – I/O devices allocated to
process, list of open files

Operating System Concepts – 9th Edition 3.11 Silberschatz, Galvin and Gagne ©2013
 PCB Diagram

Operating System Concepts – 9th Edition 3.12 Silberschatz, Galvin and Gagne ©2013
 Threads
 So far, process has a single thread (a basic unit of
CPU utilization) of execution.
 Many modern operating systems have extended the
process concept to allow a process to have multiple
threads of execution and thus to perform more than
one task at a time.
 Consider having multiple program counters per
process. For example, simultaneously type in
characters and run the spell checker within the same
process.
 Must then have storage for thread details, multiple
program counters in PCB.
 We will discuss Threads in Chapter 4.

Operating System Concepts – 9th Edition 3.13 Silberschatz, Galvin and Gagne ©2013
 Process Scheduling
 The objective of multiprogramming is to have some
process running at all times, to maximize CPU
utilization.
 The objective of time sharing (multitasking) is to
switch the CPU among processes so frequently that
users can interact with each program while it is
running.
 Process scheduling is the removal of the running
process from the CPU and the selection of another
process from the ready queue to maximize CPU
utilization.
 Process scheduler selects among available
processes for next execution on CPU.
Operating System Concepts – 9th Edition 3.14 Silberschatz, Galvin and Gagne ©2013
 Process Scheduling (cont…)
 Maintains scheduling queues of processes
 Job queue – set of all processes in the
system
 Ready queue – set of all processes residing
in main memory, ready and waiting to
execute
 Device (I/O) queue – set of processes
waiting for an I/O devices
 Processes migrate among the various queues
throughout its lifetime.

Operating System Concepts – 9th Edition 3.15 Silberschatz, Galvin and Gagne ©2013
 Representation of Process Scheduling

 Queueing diagram represents queues, resources,

and flows.

Operating System Concepts – 9th Edition 3.16 Silberschatz, Galvin and Gagne ©2013
 Schedulers
 The operating system must select processes from
these queues in some fashion. The selection
process is carried out by the appropriate
scheduler.
 Short-term scheduler (or CPU scheduler) –
selects from among the processes that are ready to
execute and allocates the CPU to one of them.
 Short-term scheduler is invoked frequently
(milliseconds).
 Because of the short time between executions,
the short-term scheduler must be fast.

Operating System Concepts – 9th Edition 3.17 Silberschatz, Galvin and Gagne ©2013
 Schedulers (cont…)
 Long-term scheduler (or job scheduler) –
selects processes from job pool and loads
them into ready queue (memory) for execution.
 Long-term scheduler is invoked infrequently
(seconds, minutes)  (may be slow)
 The primary distinction between CPU
scheduler and job scheduler lies in frequency
of execution.

Operating System Concepts – 9th Edition 3.18 Silberschatz, Galvin and Gagne ©2013
 Schedulers (cont…)
 Processes can be described as either:
 I/O-bound process – is one that spends more of
its time doing I/O than it spends doing
computations.
 CPU-bound process – generates I/O requests
infrequently, using more of its time doing
computations.
 Long-term scheduler strives for good process mix
of I/O-bound and CPU-bound processes. The
system with the best performance will have a
combination of CPU-bound and I/O-bound
processes.

Operating System Concepts – 9th Edition 3.19 Silberschatz, Galvin and Gagne ©2013
 Addition of Medium-Term Scheduling
 Medium-term scheduler can be added if degree of
multiprogramming needs to decrease using
swapping.
 Remove process from memory, store on disk
(swap out), bring back it from disk to memory
(swap in) to continue execution where it left off.

Operating System Concepts – 9th Edition 3.20 Silberschatz, Galvin and Gagne ©2013
 Context Switch
 When CPU switches to another process, the
system must save the state of the old process
and load the saved state for the new process
via a context switch
 Context of a process represented in the PCB
of the process.
 Context-switch time is pure overhead, because
the system does no useful work while
switching.
 Context-switch times are highly dependent on
hardware support.

Operating System Concepts – 9th Edition 3.21 Silberschatz, Galvin and Gagne ©2013
 CPU Switch From Process to Process

Operating System Concepts – 9th Edition 3.22 Silberschatz, Galvin and Gagne ©2013
 Operations on Processes
 The processes in most systems can execute
concurrently, and they may be created and
deleted dynamically.
 System must provide mechanisms for:
 process creation
 process termination

Operating System Concepts – 9th Edition 3.23 Silberschatz, Galvin and Gagne ©2013
 Process Creation
 A process may create several new processes, via
a create-process() system call, during the course
of execution.
 The creating process: parent process
 The new processes: children of that process.
 Each of these new processes may in turn
create other processes, forming a tree of
processes.
 Generally, process identified and managed via a
process identifier (pid), which is a unique integer
number.

Operating System Concepts – 9th Edition 3.24 Silberschatz, Galvin and Gagne ©2013
 Tree of processes

Operating System Concepts – 9th Edition 3.25 Silberschatz, Galvin and Gagne ©2013
 Process Creation (cont…)
 In general, a process will need certain
resources (CPU time, memory, files, I/O
devices) to accomplish its task.
 Resource sharing options
 Parent and children share all resources
 Children share subset of parent’s resources
 Parent and child share no resources

Operating System Concepts – 9th Edition 3.26 Silberschatz, Galvin and Gagne ©2013
 Process Creation (cont…)
 Execution options
 Parent and children execute concurrently
 Parent waits until children terminate
 Address space
 The child process is a duplicate of the parent
process (it has the same program and data as
the parent).
 The child process has a new program loaded
into it.

Operating System Concepts – 9th Edition 3.27 Silberschatz, Galvin and Gagne ©2013
 Process Termination
 A process terminates when it finishes executing
its final statement and asks the operating
system to delete it by using the exit() system
call.
 Returns status data from child to parent wait()
system call.
 All the resources of the process—including
physical and virtual memory, open files, and I/O
buffers—are deallocated by the operating
system.
 Parent may terminate the execution of children
processes using the abort() system call.
Operating System Concepts – 9th Edition 3.28 Silberschatz, Galvin and Gagne ©2013
 Process Termination (cont…)
 Some reasons for parent to terminate child process:
 Child has exceeded allocated resources.
 Task assigned to the child is no longer required.
 The parent is exiting, and the operating systems does
not allow a child to continue if its parent terminates.
 Some operating systems do not allow child to exists if its
parent has terminated. In such systems, if a process
terminates (either normally or abnormally), then all its
children must also be terminated (cascading
termination).
 All children, grandchildren, etc. are terminated.
 The termination is initiated by the operating system.

Operating System Concepts – 9th Edition 3.29 Silberschatz, Galvin and Gagne ©2013
 Process Termination (cont…)
 The parent process may wait for termination of
a child process by using the wait() system call.
The call returns status information and the pid
of the terminated child so that the parent can
tell which of its children has terminated.
 Zombie is a process that has finished the
execution but still has an entry in the process
table to report to its parent process who's
already terminated.

Operating System Concepts – 9th Edition 3.30 Silberschatz, Galvin and Gagne ©2013
 Process Termination (cont…)
 Zombie processes don't use any system
resources, but they do retain their process ID.
If there are a lot of zombie processes, then all
the available process ID’s are monopolized by
them. This prevents other processes from
running as there are no process ID’s available.
 Orphan is a process running and its parent
terminated without invoking wait() system call.

Operating System Concepts – 9th Edition 3.31 Silberschatz, Galvin and Gagne ©2013
 Interprocess Communication
 Processes executing concurrently in the operating
system may be either independent or cooperating
processes.
 Any process that does not share data with any other
process is independent.
 Any process that shares data with other processes is a
cooperating process.
 Cooperating process can affect or be affected by the
execution of other processes, including sharing data.
 Cooperating processes require an interprocess
communication (IPC) mechanism that will allow them to
exchange data and information.

Operating System Concepts – 9th Edition 3.32 Silberschatz, Galvin and Gagne ©2013
 Cooperating Processes
 Reasons for cooperating processes:
 Information sharing: users may be
interested in the same piece of information.
 Computation speedup: If we want a
particular task to run faster, we must break it
into subtasks, each of which will be
executing in parallel with the others.
 Modularity: dividing the system functions
into separate processes or threads.
 Convenience: an individual user may work
on many tasks at the same time.
Operating System Concepts – 9th Edition 3.33 Silberschatz, Galvin and Gagne ©2013
 Producer-Consumer Problem
 Example for cooperating processes is the
producer-consumer problem.
 Producer process produces information that is
consumed by a consumer process.
 Think of a server as a producer and a client as
a consumer. For example, a Web server
produces HTML files and images, which are
consumed by the client Web browser
requesting the resource.
 One solution to the producer–consumer
problem uses shared memory.

Operating System Concepts – 9th Edition 3.34 Silberschatz, Galvin and Gagne ©2013
 Producer-Consumer Problem (cont…)
 To allow producer and consumer processes to run
concurrently, we must have available a buffer of
items that can be filled by the producer and
emptied by the consumer.
 This buffer will reside in a region of memory that is
shared by the producer and consumer processes.
 A producer can produce one item while the
consumer is consuming another item.
 The producer and consumer must be
synchronized, so that the consumer does not try to
consume an item that has not yet been produced.

Operating System Concepts – 9th Edition 3.35 Silberschatz, Galvin and Gagne ©2013
 Producer-Consumer Problem (cont…)
Two types of buffers can be used:
 unbounded-buffer: places no practical limit on the
size of the buffer. The consumer may have to wait
for new items, but the producer can always produce
new items.
 bounded-buffer: assumes that there is a fixed
buffer size. The consumer must wait if the buffer is
empty, and the producer must wait if the buffer is
full.

Operating System Concepts – 9th Edition 3.36 Silberschatz, Galvin and Gagne ©2013
 Interprocess Communication (cont…)
 Cooperating processes need interprocess
communication (IPC) mechanism that will
allow them to exchange data and information.
 Two models of IPC
 Shared memory
 Message passing

Operating System Concepts – 9th Edition 3.37 Silberschatz, Galvin and Gagne ©2013
 Communications Models
(a) Message passing (b) shared memory

Operating System Concepts – 9th Edition 3.38 Silberschatz, Galvin and Gagne ©2013
 Interprocess Communication – Shared Memory

 An area of memory shared among the

processes that wish to communicate.
 The communication is under the control of the
users processes not the operating system.
 Major issues is to provide mechanism that will
allow the user processes to synchronize their
actions when they access shared memory.
 Synchronization is discussed in great details
in Chapter 6.

Operating System Concepts – 9th Edition 3.39 Silberschatz, Galvin and Gagne ©2013
 Interprocess Communication – Message Passing
 Mechanism for processes to communicate
and to synchronize their actions.
 Message system – processes communicate
with each other without resorting to shared
variables.
 IPC facility provides two operations:
 send(message)
 receive(message)
 The message size is either fixed or variable.

Operating System Concepts – 9th Edition 3.40 Silberschatz, Galvin and Gagne ©2013
 Message Passing (Cont.)

 If processes P and Q wish to communicate, they

need to:
 Establish a communication link between them
 Exchange messages via send/receive
operations
 Implementation issues (6 issues):
 How are links established?
 Can a link be associated with more than two
processes?
 How many links can there be between every
pair of communicating processes?

Operating System Concepts – 9th Edition 3.41 Silberschatz, Galvin and Gagne ©2013
 Message Passing (Cont.)
 What is the capacity of a link?
 Is the size of a message that the link can
accommodate fixed or variable?
 Is a link unidirectional or bi-directional?

Operating System Concepts – 9th Edition 3.42 Silberschatz, Galvin and Gagne ©2013
 Direct Communication
 Processes must name each other explicitly:
 send (P, message) – send a message to process P
 Receive (Q, message) – receive a message from
process Q
 Properties of communication link
 Links are established automatically
 A link is associated with exactly one pair of
communicating processes
 Between each pair there exists exactly one link
 The link may be unidirectional, but is usually bi-
directional

Operating System Concepts – 9th Edition 3.43 Silberschatz, Galvin and Gagne ©2013
 Indirect Communication
 Messages are directed and received from mailboxes
(also referred to as ports)
 Each mailbox has a unique id
 Processes can communicate only if they share a
mailbox
 Properties of communication link
 Link established only if processes share a common
mailbox
 A link may be associated with many processes
 Each pair of processes may share several
communication links
 Link may be unidirectional or bi-directional

Operating System Concepts – 9th Edition 3.44 Silberschatz, Galvin and Gagne ©2013
 Indirect Communication (cont…)
 Operations
 create a new mailbox (port)
 send and receive messages through mailbox
 destroy a mailbox
 Primitives are defined as:
send(A, message) – send a message to
mailbox A
receive(A, message) – receive a message
from mailbox A

Operating System Concepts – 9th Edition 3.45 Silberschatz, Galvin and Gagne ©2013
 Indirect Communication (cont…)
 Mailbox sharing
 P1, P2, and P3 share mailbox A
 P1, sends; P2 and P3 receive
 Who gets the message?
 Solutions
 Allow a link to be associated with at most two
processes
 Allow only one process at a time to execute a
receive operation
 Allow the system to select arbitrarily the receiver.
Sender is notified who the receiver was.

Operating System Concepts – 9th Edition 3.46 Silberschatz, Galvin and Gagne ©2013
 End of Chapter 3

Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013