CPPC 10 Operating Systems Lecture Notes 2

Lecture Notes 2 - Process Management

Process Management Activities

 Creating and deleting both user and system processes
 Suspending and resuming processes
 Providing mechanisms for process synchronization
 Providing mechanisms for process communication
 Providing mechanisms for deadlock handling

A process is a program in execution. It is a unit of work within the system. Program is a passive
entity, process is an active entity. Process needs resources to accomplish its task:
 CPU, memory, I/O, files
 Initialization data

Process termination requires reclaim of any reusable resources.

Single-threaded process has one program counter specifying location of next instruction to
execute.
 Process executes instructions sequentially, one at a time, until completion.

Multi-threaded process has one program counter per thread.

Typically system has many processes, some user, and some operating system running
concurrently on one or more CPUs.
 Concurrency by multiplexing the CPUs among the processes / threads

Concept of a process

Terminology

Job - (also known as program) is an inactive unit such as a file in disk. This entity contains
at least two types of elements: program code and a set of data

Process - (also called task) is an executed program code on the processor, that is, a part
of an active entity

Thread - is a portion of a process that can be run independently

In multiprogramming environment, the processor is used by multiple programs/processes

Process manager needs to arrange the execution of the programs/processes (to make a
schedule for them) to promote the most efficient use of resources (including hardware and
software) and to avoid competition and deadlock.
Job and Process Scheduling
CPPC 10 Operating Systems Lecture Notes 2

Schedulers
Job scheduler
 Initialize each job
 Only concerned with selecting jobs from a queue of incoming jobs
 Places them in a process queue (READY queue)

Process scheduler
 Determines which jobs get the CPU, when, and for how long.
 Also decides when processing should be interrupted
 Decides when each step will be executed
 Recognizes when a job has concluded and should be terminated

Hierarchy
 Job scheduler is the high-level scheduler
 Process scheduler is the low-level scheduler

Process Scheduler

Common trait among most computer programs: they alternate between CPU cycles and
IO cycles

Process scheduler is a low-level scheduler that assigns CPU to execute the processes
of those jobs placed in the ready queue by the job scheduler.

Although CPU cycles vary from program to program, there are some general types of
jobs:
 IO-Bound jobs e.g. printing a series of documents. Many brief CPU cycles and
long IO cycles.
 CPU-Bound jobs e.g. finding the first 300 prime numbers. Long CPU cycles and
shorter IO cycles.

Total statistical effect approximates a Poisson distribution.

Highly interactive environment has a third level - begin a middle-level scheduler - finding
it advantageous to remove active jobs from memory; allowing jobs to complete faster.

Process status

Process queue
 Processes are divided into threads
The threads form a “ready queue” waiting for being processed in the
processor

Two-state model
 A process is in “running” state if it is executed on the processor
 It is in “not running” state otherwise
CPPC 10 Operating Systems Lecture Notes 2

Five-state model
States
 Running: the process is currently executed on the processor
 Ready: a process is prepared to execute
 Waiting: a process waits for resources
 Hold: a process is just created
 Exit: a process is released from pool of executable programs by OS

State transitions:
HOLD to READY:
 When OS is prepared to take an additional process. Initiated by job
scheduler; availability of memory and devices checked.
READY to RUNNING:
 Process scheduler chooses a ready process to execute.
RUNNING to EXIT:
 Currently executed process has completed or a run time error. Initiated
by job or process scheduler.
RUNNING to WAIT:
 Handled by process scheduler, initiated by job instruction for I/O or other
resources request.
WAIT to READY:
 Handled by process scheduler, initiated when I/O or other resources
become available.
RUNNING to READY:
 Handled by process scheduler; maximum allowable time is reached or
other criterion e.g. a priority interrupt.
CPPC 10 Operating Systems Lecture Notes 2

 User submits job (batch/interactive)

 Job accepted
o Put on HOLD and placed in queue
 Job state changes from HOLD to READY
o Indicates job waiting for CPU
 Job state changes from READY to RUNNING
o When selected for CPU and processing
 Job state changes from RUNNING to WAITING
o Requires unavailable resources
 Job state changes to FINISHED
o Job completed (successfully or unsuccessfully)

Process Control Blocks

Process control block (PCB): Any process is uniquely characterized by a list of

elements:
 Identifier: a unique identifier which distinguishes a process from others
 State: a process can have different states
 Priority: this shows the priority level of a process relative to other
process
 Program counter: the address of the instruction to be executed next of a
process (program code)
 Memory pointers: include those point to program code and data
associated of a process, plus any memory blocks shared with other
processes
 Context data: These are date that are presented in registers in the
processor while a process is running
 I/O status information: includes I/O requests and the availability of files
and I/O devices
 Accounting information: includes time and number countered
CPPC 10 Operating Systems Lecture Notes 2

PCBs and Queuing

Job PCB
 Created when Job Scheduler accepts job
 Updated as job executes
 Queues use PCBs to track jobs
 Contains all necessary job management processing data
 PCBs linked to form queues (jobs not linked)
 Manage queues using process scheduling policies and algorithms

Process State
This contains all of the information needed to indicate the current state of the job such
as:
Process Status Word current instruction counters and registers contents when
a job isn’t running.
Register Contents if the job has been interrupted and is waiting.
Main Memory Information including the address where the job is stored.
CPPC 10 Operating Systems Lecture Notes 2

Resources Information about all resources allocated to the job, being hardware
units or files.
Process Priority used by systems with priority scheduling algorithm.

Accounting
Information for billing purposes and performance measurement
Typical charges include:
 Amount of CPU time used from beginning to end of execution.
 Total time the job was in the system until exited.
 Main storage occupancy - how long the job stayed in memory until it finished
execution.
 Secondary storage used during execution.
 System programs used (compilers, editors, utilities, etc.)
 Number and type of IO operations, including IO transmission time (includes
use of channels, control units, devices)
 Time spent waiting for IO completion
 Number of input records read, and number of output records written

Multithreading
A process can be divided into multiple threads

Multithreading is a “condition” for a processor manager to make a schedule for multi-

processes

An example of a process and threads

Get input for Job A
Identify resources
Execute the process
Interrupt
Switch to Job B
Get input for Job B
Identify resources
Execute the process
Terminate Job B
Switch back to Job A
Resume executing interrupted process
Terminate Job A

Process Scheduling Policies

A good process scheduling policy:
 Maximize throughput - run as many jobs as possible in a given amount of time
 Minimize response time - quickly turn around interactive requests
 Minimize turnaround time - move entire jobs in and out of the system quickly
 Minimize waiting time - move jobs out of the ready queue as quickly as possible
 Maximize CPU efficiency - keep the CPU busy 100% of the time
 Ensure fairness for all jobs - give every job an equal amount of CPU and IO time
CPPC 10 Operating Systems Lecture Notes 2

A scheduling strategy that interrupts the processing of a job and transfers the CPU to another
job is preemptive scheduling policy. The alternative is non-preemptive scheduling policy which
functions without external interrupts.

Process Scheduling Algorithms

1. FCFS - First-come-first-served
 Batch environment
 Job handled based on arrival time
 Earlier job arrives, earlier served
 Those jobs/processes are collected in batches
 First-come-first-serve (FCFS)
 A READY queue for storing ready processes that are initialized by Job scheduler
 When a process is in RUNNING state, its execution will be completed in one go,
that is, these is no waiting state in this algorithm
 Average turnaround time (τ )
 Total time needed for every process completed divided by the number of
processes in the queue
 Depends on how the processes are queued in the READY queue

Example:
Process A has CPU cycle (ta = 5 ms)
Process B has CPU cycle (tb = 2 ms)
Process C has CPU cycle (tc = 1 ms)
When the 3 processes become ready in the order of ABC

τ = (5 + 7 + 8)/3 = 6.67

When the 3 processes become ready in the order of BCA

τ = (2 + 3 + 8)/3 = 4.33
CPPC 10 Operating Systems Lecture Notes 2

2. Shortest Job First [next] (SJF) [SJN]

 Non-preemptive
 Also known as shortest job first (SJF)
 Job handled based on length of CPU cycle time
 Easy implementation in batch environment
o CPU time requirement known in advance
 Does not work well in interactive systems
 Optimal algorithm
o All jobs are available at same time
o CPU estimates available and accurate

 Process that uses the shortest CPU cycle will be selected for running first

Example:

Tb = 2, Td = 6, Ta = 11, Tc = 17
τ = (Tb + Td + Ta + Tc)/4 = 9
Optimal in terms of occupying the least CPU time

Example:

τ = (1 + 3 + 8)/3 = 4
CPPC 10 Operating Systems Lecture Notes 2

3. Shortest remaining time (SRT)

Real-time environment
o Preemptive version of SJN
o Processor allocated to job closest to completion
 Preemptive if newer job has shorter completion time
o Often used in batch environments
 Short jobs given priority
o Cannot implement in interactive system
 Requires advance CPU time knowledge
o Involves more overhead than SJN
 System monitors CPU time for READY queue jobs
 Performs context switching
o Process that the mostly close to complete will be process first, and even this
process can be pre-empted if a newer process in READY queue has a shorter
complete time

Example:

τ = (14 + 4 + 1 + 6)/4 = 6.25

CPPC 10 Operating Systems Lecture Notes 2

4. Round Robin

Time is divided into slices called time quantum

o Preemptive
o Used extensively in interactive systems
o Based on predetermined slice of time
 Each job assigned time quantum
o Time quantum size
 Crucial to system performance
 Varies from 100 ms to 1-2 seconds
o CPU equally shared among all active processes
 Not monopolized by one job
o Processes in the READY queue will be processed in FIFO
o Process scheduler will pick up a process from the front of the READY queue and
allocate it to CPU when a time slide starts
o When the time slide ends but the processing has not been complete, the
scheduler will send the remaining part of the process back to the end of the
READY queue
o Timer expires
o It can only be resumed when it gets to the front of the queue

o If job CPU cycle < time quantum

 Job finished: allocated resources released and job returned to user
 Interrupted by I/O request: information saved in PCB and linked to I/O
queue
o Once I/O request satisfied
 Job returns to end of READY queue and awaits CPU

o Efficiency
 Depends on time quantum size
 In relation to average CPU cycle
o Quantum too large (larger than most CPU cycles)
 Algorithm reduces to FCFS scheme
o Quantum too small
 Context switching occurs
 Job execution slows down
 Overhead dramatically increased
CPPC 10 Operating Systems Lecture Notes 2

o Best quantum time size

 Depends on system
 Interactive: response time key factor
 Batch: turnaround time key factor
 General rules of thumb
 Long enough for 80% of CPU cycles to complete
 At least 100 times longer than context switch time requirement

Example:

τ = (20 + 7 + 24 + 22)/4 = 18.25

Priority Scheduling
 Non-preemptive
 Preferential treatment for important jobs
o Highest priority programs processed first
o No interrupts until CPU cycles completed or natural wait occurs
 READY queue may contain two or more jobs with equal priority
o Uses FCFS policy within priority
CPPC 10 Operating Systems Lecture Notes 2

 System administrator or Processor Manager use different methods of assigning priorities

 Allowing process with the highest priority to be processed first
 The processing is not interrupted unless the CPU cycle of the process is completed or a
natural wait occurs.
 If more than one process has the same priority, the one which joins the ready queue
first is processed first

Priorities:
Memory requirements - jobs requiring large amounts of memory could be allocated
lower priorities than those requiring small amounts of memory

Number and type of device - jobs requiring many devices would be allocated lower
priorities

Total CPU time - jobs having long CPU cycle, or estimated run time, would be given
lower priorities

Amount of time already spent in the system - some systems increase priority of jobs
that have been in the system for an unusually long time. This is known as aging.

Multiple-level Queues
 Works in conjunction with several other schemes
 Works well in systems with jobs grouped by common characteristic
 Priority-based
 Different queues for each priority level
 CPU-bound jobs in one queue and I/O-bound jobs in another queue
 Hybrid environment
 Batch jobs in background queue
 Interactive jobs in foreground queue
 Scheduling policy based on predetermined scheme
 Four primary methods
 When time out for a high-priority process, it is added to the tail of the queue consisting of
lower priority level processes.

Priority inversion and inheritance

Priority inversion problem: a high-priority process waits on a low-priority process
that is starved by a medium-priority process (for example, releasing some
resources)
CPPC 10 Operating Systems Lecture Notes 2

Example:
Three processes, a, b and c with p(a)=2, p(b)=3 and p(c)=4
Process c waits on a
a is starved by b (b is never put in waiting state)
Process a cannot compete with b and therefore b is always running and a
and c never get chance to run
It looks like c with p(c)=4 had lower priority than b with p(b)=3
Solution – priority inheritance
Elevating the priority a to 4 so that it can compete with b and win in
competition

Case 1: No Movement between Queues

 Simple
 Rewards high-priority jobs
 Processor allocated using FCFS
 Processor allocated to lower-priority jobs
 Only when high-priority queues empty
 Good environment
 Few high-priority jobs
 Spend more time with low-priority jobs

Case 2: Movement between Queues

 Processor adjusts priorities assigned to each job
 High-priority jobs
 Initial priority favorable
Treated like all other jobs afterwards
 Quantum interrupt
 Job preempted
 Moved to next lower queue
 May have priority increased
 Good environment
 Jobs handled by cycle characteristics (CPU or I/O)
 Interactive systems

Case 3: Variable Time Quantum per Queue

 Case 2 variation: movement between queues
 Each queue given time quantum size
 Size twice as long as previous queue
 Fast turnaround for CPU-bound jobs
 CPU-bound jobs execute longer and given longer time periods
 Improves chance of finishing faster

Case 4: Aging
 Ensures lower-level queue jobs eventually complete execution
 System keeps track of job wait time
 If too “old”
 System moves job to next highest queue
 Continues until old job reaches top queue
 May drastically move old job to highest queue
CPPC 10 Operating Systems Lecture Notes 2

 Advantage
 Guards against indefinite unwieldy job postponement

Interrupt Types
1. Page interrupt (memory manager)
 Accommodate job requests
2. Time quantum expiration interrupt
3. I/O interrupt
 Result from READ or WRITE command issuance
4. Internal interrupt
 Synchronous
 Result from arithmetic operation or job instruction
5. Illegal arithmetic operation interrupt
 Dividing by zero; bad floating-point operation

SUMMARY
 Processor Manager allocates CPU among all users
 Job Scheduler
o Assigns job to READY queue
 Based on characteristics
 Process Scheduler
o Instant-by-instant allocation of CPU
 Scheduling algorithm is unique
o Characteristics, objectives, and applications
 System designer selects best policy and algorithm
o After careful strengths and weaknesses evaluation
CPPC 10 Operating Systems Lecture Notes 2

Exercises No. 2:

1) Describe the following scheduling algorithms

 Non Pre-Emptive, First Come, First Serve

 Round Robin
 Shortest Job First

2) Given the following processes and burst times

Process Burst Time

P1 10
P2 6
P3 23
P4 9
P5 31
P6 3
P7 19

a) Calculate the average wait time when each of the above scheduling algorithms is
used?

Assume that a quantum of 8 is being used.

b) Which scheduling algorithm, as an operating systems designer, would you

implement?

3) Given the following processes, burst times and priority

Process Burst Priority

P1 8 4
P2 6 1
P3 1 2
P4 9 2
P5 3 3

First Come First Served

0 8 14 15 24 27
P1 P2 P3 P4 P5

a) Calculate the average wait time and the turnaround time when each of the above
scheduling algorithms is used?
CPPC 10 Operating Systems Lecture Notes 2

Shortest Job First

0 1 4 10 18 27
P3 P5 P2 P1 P4

c) Calculate the average wait time and the turnaround time when each of the above
scheduling algorithms is used?

Round Robin (1ms Quantum)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2627
P1 P2 P3 P4 P5 P1 P2 P4 P5 P1 P2 P4 P5 P1 P2 P4 P1 P2 P4 P1 P2 P4 P1 P4 P1 P4 P4

d) Calculate the average wait time and the turnaround time when each of the above
scheduling algorithms is used?

e) Which scheduling algorithm has the shortest waiting time and shortest turnaround
time? Fill out the table below.

Algorithm Avg Wait Avg TAT

FCFS
SJF
RR