Process management

What are we going to learn?

• Processes : Concept of processes, process scheduling, co-operating processes, inter-process

communication.

• CPU scheduling : scheduling criteria, preemptive & non-preemptive scheduling, scheduling algorithms
(FCFS, SJF, RR, priority), algorithm evaluation, multi-processor scheduling.

• Process Synchronization : background, critical section problem, critical region, synchronization hardware,
classical problems of synchronization, semaphores.

• Threads : overview, benefits of threads, user and kernel threads.

• Deadlocks : system model, deadlock characterization, methods for handling deadlocks, deadlock
prevention, deadlock avoidance, deadlock detection, recovery from deadlock.
 Process concept
Memory
• Process is a dynamic entity
– Program in execution Disk
User
• Program code program
– Contains the text section
• Program becomes a process when
– executable file is loaded in the memory
– Allocation of various resources
• Processor, register, memory, file, devices
• One program code may create several processes
– One user opened several MS Word
– Equivalent code/text section
– Other resources may vary
 Process State

• As a process executes, it changes state

– new: The process is being created
– ready: The process is waiting to be assigned to a
processor
– running: Instructions are being executed
– waiting: The process is waiting for some event to
occur
– terminated: The process has finished execution
 Process State diagram
Job pool

Single
processor

Multiprogramming As a process executes, it changes state

– new: The process is being created
– running: Instructions are being executed
– waiting: The process is waiting for some event to
occur
– ready: The process is waiting to be assigned to a
processor
– terminated: The process has finished execution
 Job pool Process State diagram

Multitasking/Time sharing
As a process executes, it changes state
– new: The process is being created
– running: Instructions are being executed
– waiting: The process is waiting for some event to
occur
– ready: The process is waiting to be assigned to a
processor
– terminated: The process has finished execution
 How to represent a process?
• Process is a dynamic entity
– Program in execution
• Program code
– Contains the text section
• Program counter (PC)
• Values of different registers
– Stack pointer (SP) (maintains process stack)
• Return address, Function parameters
C Z O S I K
– Program status word (PSW)
– General purpose registers
• Main Memory allocation
– Data section
• Variables
– Heap
• Dynamic allocation of memory during process execution
 Process Control Block (PCB)
• Process is represented in the operating system
by a Process Control Block
Information associated with each process
• Process state
• Program counter
• CPU registers
– Accumulator, Index reg., stack pointer, general
Purpose reg., Program Status Word (PSW)
• CPU scheduling information
– Priority info, pointer to scheduling queue
• Memory-management information
– Memory information of a process
– Base register, Limit register, page table, segment table
• Accounting information
– CPU usage time, Process ID, Time slice
• I/O status information
– List of open files=> file descriptors
– Allocated devices
 Process Representation in Linux
Represented by the C structure task_struct
pid t pid; /* process identifier */
long state; /* state of the process */
unsigned int time slice /* scheduling information */
struct task struct *parent; /* this process’s parent */
struct list head children; /* this process’s children */
struct files struct *files; /* list of open files */
struct mm_struct *mm; /* address space of this pro */

Doubly
linked list
 CPU Switch From Process to Process

Context switch
 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

• Context-switch time is overhead; the system does no do useful

work while switching
– The more complex the OS and the PCB -> longer the context switch

• Time dependent on hardware support

– Some hardware provides multiple sets of registers per CPU -> multiple
contexts loaded at once
 Scheduling queues

• 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 queues – set of processes waiting for an I/O
device
• Processes migrate among the various queues
 Scheduling queues

Job queue

Ready queue

Device queue
 Ready Queue And Various
I/O Device Queues

Queues are linked list of PCB’s

Device queue

Many processes
are waiting for
disk
 Process Scheduling
• We have various queues
• Single processor system
– Only one CPU=> only one running process
• Selection of one process from a group of
processes
– Process scheduling
 Process Scheduling
• Scheduler
– Selects a process from a set of processes
• Two kinds of schedulers
1. Long term schedulers, job scheduler
– A large number of processes are submitted (more than
memory capacity)
– Stored in disk
– Long term scheduler selects process from job pool and loads
in memory
2. Short term scheduler, CPU scheduler
– Selects one process among the processes in the memory
(ready queue)
– Allocates to CPU
Long Term Scheduler

CPU scheduler
 Representation of Process Scheduling
CPU scheduler selects
a process Dispatched (task of
Dispatcher)

Parent at
wait()
 Dispatcher
• Dispatcher module gives control of the CPU to
the process selected by the short-term scheduler;
this involves:
– switching context
– switching to user mode
– jumping to the proper location in the user program to
restart that program

• Dispatch latency – time it takes for the dispatcher

to stop one process and start another running
 Creation of PCB
a.out Shell

Create
initial Child Shell
PCB

Exce()

Loader (Loads program image in

memory)

Update PCB
Context switch

Insert in ready Allocate CPU

queue
 Schedulers
• Scheduler
– Selects a process from a set
• Long-term scheduler (or job scheduler) –
selects which processes should be brought
into the ready queue
• Short-term scheduler (or CPU scheduler) –
selects which process should be executed
next and allocates CPU
– Sometimes the only scheduler in a system
Schedulers: frequency of execution
• Short-term scheduler is invoked very frequently (milliseconds) 
(must be fast)
– After a I/O request/ Interrupt
• Long-term scheduler is invoked very infrequently (seconds, minutes)
 (may be slow)
– The long-term scheduler controls the degree of multiprogramming

• Processes can be described as either:

– I/O-bound process – spends more time doing I/O than computations,
many short CPU bursts
• Ready queue empty
– CPU-bound process – spends more time doing computations; few very
long CPU bursts
• Devices unused
• Long term scheduler ensures good process mix of I/O and CPU
bound processes.
Addition of Medium Term Scheduling

disk Swap Space

Swapper
 ISR for context switch
Current <- PCB of current process
Context_switch()
{
switch to kernel mode
Disable interrupt;
Save_PCB(current);
Insert(ready_queue, current);
next=CPU_Scheduler(ready_queue);
remove(ready_queue, next);
Enable Interrupt;

Dispatcher(next);
}
Dispatcher(next)
{
Load_PCB(next); [update PC]
switch to user mode;