Process Management

Module 2

Topics under Process Mgmt: Process concepts and states Scheduling (CPU and I/O) Synchronization (concurrency) Deadlock handling

OS Responsibilities for Process Mgmt. Creating and deleting of process Scheduling of a process (suspending and

resuming the execution of process) Process synchronization Process communication Deadlock handling

What is a process? Process

– Program in execution needing resources (such as CPU time, memory, files and I/O devices) to accomplish its tasks. - Executing set of machine instructions - Execution of a process must progress in a sequential fashion; at most one instruction is executed on behalf of the process.

Components of a process Code Data Resources Status Threads

Classification of OS according to the types of system: Single-process single-threaded – only one

process can execute at a time. Once a process is allocated to the CPU, that process runs to completion before any other process can execute. Example: DOS

Classification of OS according to the types of system: Multi-process single threaded – a single

entity (the process), is the object upon which both resource allocation and CPU scheduling are performed. Example: UNIX

Classification of OS according to the types of system: Multi-process multi-threaded – resources are

allocated to the processes but CPU scheduling can be in terms of thread. Example: Windows, Mach, Solaris

Is process the same as program? No, it is both more and less More – a program is just part of a process context. Less – a program may invoke several processes

Uniprogramming & Multiprogramming Uniprogramming allows execution of only one process at a time

(e.g. personal computer) Multiprogramming allows more than one process (e.g. concurrent

execution of many processes)

How can several processes share one CPU? OS takes care of this by making sure that: Each process gets a chance to run

(fair scheduling) They do not modify each other’s state

(protection)

OS Execution An OS executes a variety of programs: Batch systems Time-shared systems

A process includes: Program counter and contents of processor

registers. Process stack (contains temporary data such as subroutine parameters, return addresses, variables) Data section (contains global variables) Heap Memory that is dynamically allocated during run

time.

Six (6) Process States: New Process is being created but not yet included in

the pool of executable processes (resource acquisition) Ready Waiting to be assigned to the processor

Running (or active) Process that is currently being executed

Six (6) Process States: (cont) Waiting (or blocked) Waiting for some event to occur (I/O completion)

Stopped Special case of blocked where the operator/user

suspends the process. Terminated (or exiting) Process has finished execution. A process is about

to be removed from the pool of executable processes.

Diagram of process state Stopped Stopped

kill suspend

resume New New create

time-out Active Active

Ready Ready

Event occurs or resource available

dispatch

Blocked Blocked

State transition _____ internal _ _ _ _external

exit Exiting Exiting kill error

Additional process states Medium term scheduling adds two additional

process states: Swapped blocked – process is waiting for some

event to occur and has been swapped out to secondary storage Swapped-ready – process is ready to run but is swapped out to secondary storage and may not be allocated to the CPU since it is not in main memory.

Process Control Block (PCB) Each process is represented in the OS by a PCB. It is where collection of process information are

kept and accessed. Sometimes called the Task Control Block (TCB)

PCB Information: Process state Program counter (PC) CPU Registers CPU Scheduling information Memory-Management Information Accounting information  I/O status information

Process Control Block

Process scheduling: Objective of multiprogramming: have some user

process running at all times OS keeps the CPU busy with productive work by

dynamically selecting (scheduling) the next user process to become active.

Dispatcher Dispatcher – performs the scheduling and

only executes the primitive pseudo-code: Loop forever { run the process for a while stop process and save its state load the state of another process }

Dispatcher Process Process22 Process Process 11

Operating System

Process Processnn CPU CPU

dispatcher dispatcher

Ready queue

Control of the CPU The CPU can only do one thing at a time. While a

user process is running, dispatcher cannot run thus the OS may lose control.

How does the dispatcher regain control of the CPU? Trust the process to wake up the dispatcher

when done (sleeping beauty approach) Not a good solution because sometimes process

loop indefinitely Provide a mechanism to wake the dispatcher

(alarm clock)

Scheduling queues Job queue Set of all processes that enter the system

Ready queue (linked-list) Set of all processes residing in main memory,

ready and waiting to execute. Device queues Set of processes waiting for an I/O device, each

device has a device queue.

Queuing diagram:

Long-term scheduler (or job scheduler) Selects which processes should be brought into

the ready queue; these processes are spooled to a mass-storage (disk) where they are kept for later execution. Controls the degree of multiprogramming

Long term scheduler: (cont) Must make careful selection among the

processes (a good process mix). Processes can be described as either: I/O bound process – spends more time doing I/O

than computations, may short CPU bursts CPU bound process – spends more time doing

computations, few very long CPU bursts.

Short-term scheduler Known as the CPU scheduler. Selects which process should be executed next

and allocates the CPU.

Medium-term scheduler (Swapper) Involves suspending or resuming processes by

swapping or rolling them out of or into memory. Swapping Removing a process from the memory.

Medium-term scheduler

Context switch When a CPU switches to another process, the

system must save the state of the old process and load the saved state of the new process Context-switch time is overhead; the system

does no useful work during switching.

Context Switch

Operations on Processes Process Creation Via a create-process system call Parent process – creating process Children process – siblings (sub-process) of

the parent process. Has a unique process identifier (pid)

Independent Processes Independent Processes Cannot affect or be affected by the execution of

another process. Properties Deterministic Reproducible Can stop and restart without “side effects” Can proceed at an arbitrary rate

Cooperating Processes Cooperating Processes Can affect or be affected by the execution of

another process. Properties: Share (or exchange) a common object Non-deterministic May be irreproducible Subject to race conditions

Race Condition Situation where two or more processes access

shared data concurrently

Why cooperation? Information sharing Allow concurrent access to shared resources.

Computation Speedup Tasks are broken down into subtasks, each of

which is executing in parallel with the others

Issues with cooperating system Requires mechanism to allow processes to

communicate with one another and to synchronize their actions Shared memory Message passing (interprocess communication)

Issues with cooperating system May give rise to a race condition during critical

section processing which may lead to inconsistent states / data. Especially troublesome for multiprocessor

systems and distributed systems.

Example Process A

Process B

Concurrent Access

A=1

B=2

Does not matter

A=B+1

B=B*2

IMPORTANT!

Bounded Buffer Producer consumer problem An example of a race condition

InterProcess Communication (IPC) Mechanism for processes to communicate and

to synchronize their actions Message system – process communicate with

each other without resorting to shared variables

Communications models: Process A

M

Process B

M

Process A

M

shared Process B

M

M

Kernel

M

Kernel

Message Passing

Shared memory

IPC IPC facility provides two operations Send (message) – message size fixed or variable Receive (message)

Example: if P and Q wish to communicate, they

need to Establish a communication link between them Exchange messages via send/receive

Implementation of a communication link Physical (e.g. shared memory, hardware bus) Logical (e.g. logical properties)

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 a 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 bidirectional

Indirect Communication Messages are directed and received from

mailboxes (also known 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 Links may be unidirectional or bi-directional

Operations Create a new mailbox 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.

Thread: definition A basic unit of CPU utilization Comprises a thread ID, program counter,

register set, and a stack. Process types: Single-threaded – performs one task at a

time Multithreaded – performs more than one task at a time.

Examples of Thread Web browser One thread – displays images/text Another thread – retrieves data from network

Word processor One thread – displays graphics Another thread – responds to user keystrokes Another thread – performs spelling and

grammar

Benefits of Multithreading Responsiveness Allows interactive activities while the

program is running Resource sharing Sharing of code and data - allows an

application to have several thread activities Economy More economical to create and context-

switch threads

Benefits of Multithreading (cont) Utilization of multiple architectures Threads may be running in parallel on

different processor.  Single thread – run on one CPU regardless of the

number of CPUs.  Multithreaded – increases concurrency.

Support for threads User threads Supported above the kernel and are

managed without kernel support. Kernel thread Supported and managed directly by the OS.

Multithreading models Many to one model Maps many user-level threads to one kernel

thread.  Older versions of Solaris uses this model

User thread

K

Kernel thread

Multithreading models (cont) One to one model Maps each thread to a kernel thread. Provides more concurrency than Many to one

model. Allows multiple threads to run in parallel on multiprocessors Drawback: user thread requires creating kernel thread (suffers performance) Linux, Windows (starting Win 95 onwards) and Solaris 9 use this model.

One to one model User thread

K

K

K

K

Kernel thread

Multithreading models (cont) Many to many model Multiplexes many user-level threads to a

smaller or equal number of kernel threads Can create as many user threads, and the kernel threads can run in parallel on a multiprocessor. IRIX, HP-UX, and TRu64UNIX use this model.

Many to many model User thread

K

K

K

Kernel thread