Accommodate job requests

Chapter 3

Processor
Management
3.1. How Does Processor Manager
Allocate CPU(s) to Jobs?
• Process Manager performs job scheduling,
process scheduling and interrupt
management.
• In single-user systems, processor is busy only
when user is executing a job—at all other times it
is idle.
– Processor management is simple.
• In multiprogramming environment, processor
must be allocated
⮚ Requires to each
scheduling job (code/data) in a fair
policy
and efficient vs
(preemptive manner.
non-preemptive) and a
scheduling algorithm (FCFS, SRTF
….)
⮚ Execution of > 1 program. CPU switching
rapidly between them.
⮚ Pre-condition: sufficient memory!
• Active multiprogramming is a time-
sharing (multi tasking) system which
allows each program to use a preset
slice of each CPU time. When the time
expires, the job is interrupted and
another job is allowed to begin. J1 C
J2
– More control over interrupts, ⇧ CPU utilization.
– With preemption, context switching happen
• Passive multiprogramming allows
each program to be serviced in turn,
one after another by an interrupt. It ties
up CPU time while all other jobs have to
wait. …J4, J3, J2 J1C

• Without preemption
State diagram with boundaries between program, job and process
2.2. Job Scheduling vs. Process
Scheduling

Processor Manager has 2 sub-managers:

• Job Scheduler
– in charge of job scheduling.

• Process Scheduler
– in charge of process scheduling.
1. Job Scheduler New/ Ready
Hold
•High-level / long term scheduler.
•Selects jobs from a queue of incoming jobs.
•Places them in ready queue (batch or
interactive), based on each job’s
characteristics.
•Goal is to put jobs in a sequence that uses
all system’s resources as fully as possible.
•Provide a balanced mix of jobs.
🡪I/O bound vs processor bound)
•Tries to keep most system components
busy most of time.
🡪controls the degree of multiprogramming
2. Process SchedulerReady Runni
ng
• Low-level scheduler / dispatcher – assigns
the CPU to execute processes of those jobs
placed on ready queue by Job Scheduler.
• After a job has been placed on the READY
queue by Job Scheduler, Process Scheduler
that takes over.
▪ Determines which process will get CPU,
when, and for how long.
▪ Decides when processing should be
interrupted.
▪ Determines queues process should be
moved to during execution.
▪ Recognizes when a process has concluded
and should be terminated.
CPU Cycles and I/O Cycles
• To schedule CPU, Process Scheduler uses
common trait among most computer programs:
they alternate between CPU cycles and I/O
cycles.
• I/O-bound jobs (such as printing a series
of documents) have many brief CPU cycles
and long I/O cycles.
• CPU-bound jobs (such as finding the first
300 prime numbers) have long CPU cycles
and shorter I/O cycles.
I/O-bound CPU-bound
process
I/O Module process
Computation
I/O Module Computation
I/O Module Computation
I/O Module Computation
I/O Module Computation
I/O Module Computation
Computation I/O Module
I/O Module Computation
I/O Module Computation
I/O Module Computation
I/O Module Computation
I/O Module Computation
Computation Computation
I/O Module
 pg3

3. Middle-Level Scheduler
•In a highly interactive environment there’s a
third layer. E.g.. Time sharing environment.
– called swapper.

•Removes active jobs (processes) from

memory to reduce degree of
multiprogramming and allows jobs to be
completed faster
🡪in-charge of handling the swapped out-processes.
 Ready Queue

MP4 MSN

M.Playe
MS Faceboo
Word
r k
 Middle-Level
Scheduler
Swapped out
processes Sw

in
ou ap

ap
t

Sw Ready En
Disk Queue CPU
Job d
Process
Scheduler Scheduler

I/O waiting
I/O Queue
• Purpose of swapping.
– To reduce the degree of
multiprogramming
– To improve the process Mix – jobs completed
faster.

Problem is Thrashing
− Happen when a process is busy swapping
pages in and out.
− if there is not 'sufficient' physical memory . The page-
fault rate is high. This leads to low CPU utilization
 Thrashing

CPU
Utilization

Degree of
Multiprogramming
2.3. Process State Diagram

• Scheduler dispatch select job from ready queue and send

it to CPU run. (Short term)
• Interrupt force CPU to stop and save PCB and put it in
ready queue. (Context switching ) pg6
Process State - Job status

• New/Hold: The process is being

created.
• Ready: The process is waiting to be
assigned to a process. (waiting for
CPU)
• Running: Instructions are being
executed.
• Waiting: The process is waiting for
some event to occur. (wait for
I/O)
Process Control Block (PCB)

• Each process in the O/S is represented

by a PCB repository for information that
vary from process to other process.
 PCBs and
• Queuing
PCB of job created when Job Scheduler
accepts it. (PCB store in queue)
• Queues use PCBs to track jobs.
(Disk)

(Memory)
Process Scheduling Queues

• Job queue – set of all processes in the system.

• Ready queue
– set of all processes residing in main memory,
ready and waiting to execute.
– generally stored as a linked list with a header
node containing pointers to the first and last
PCBs.
• Device queues
– set of processes waiting for an I/O device.
– each device has its own device queue
Ready Queue

Queue
Header P1 P2 Pn
Head
PCB1 PCB2 PCBn
Tail
 Process State Diagram
New/
Hold Interrupt Finish

Admitted Exit
Ready Runni
ng

Scheduler
I/O I/O or
dispatch
Completion event wait
Waitin
g
 pg5
2.4. Interrupt Types
– Page interrupt (memory manager)
⮚ Accommodate job requests
– Time quantum expiration interrupt
– I/O interrupt
⮚ Result when a READ or WRITE command is
issued
– Internal interrupt (synchronous interrupt)
⮚ Result from arithmetic operation or job
instruction
– Illegal arithmetic operation interrupt
⮚ Dividing by zero; bad floating-point operation
generating an overflow or underflow
23
• Interrupt Types (continued)
– Illegal job instruction interrupt
⮚ Protected or non-existent storage access
attempt
⮚ Attempts to make system changes, such as trying to
change the size of the time quantum.

Interrupt handler
– Control program
• Handles interruption event sequence

24
• Interrupt handler sequence is as follows: pg5

– Interrupt type described and stored (passed to

user as an error message)
– Interrupted process state saved (value of the
program counter and contents of all registers)
– Interrupt is processed
• non-recoverable interrupt
– job processing is terminated
– resources allocated to the job are released
– an error message is sent to the user
• Recoverable
– I/O interrupt - the job is moved to the I/O queue
– time quantum interrupt - the job is moved to the
READY queue).
– Processor resumes normal operation
25
CPU Switch From Process to Process
Process P0 Process P1
Save State into PCB0
executing Context
idle
Switch
Reload State from
PCB1

Interrupts or I/O executing

idle
Save State into PCB1
Context
Switch
Reload State from idle
PCB0
executing
2.5. Process Scheduling Policies

• Before operating system can schedule all

jobs in a multiprogramming environment,
it must resolve three limitations of
system:
– finite number of resources (such as disk
drives, printers, and tape drives)
– some resources can’t be shared once
they’re allocated (such as printers)
– some resources require operator
intervention (such as tape drives).
A Good Scheduling Policy

• Maximize throughput by running as many

jobs as possible in a given amount of time.
Batch system
• Maximize CPU efficiency by keeping CPU
busy 100 % of time.
• Ensure fairness for all jobs by giving
everyone an equal amount of CPU and I/O
time.
• Minimize response time by quickly turning
around interactive requests. Interactive Systems
• Minimize turnaround time by moving entire
jobs in/out of system quickly.
• Minimize waiting time by moving jobs out
of READY queue as quickly as possible
Waiting Time (w) = Finish Time – Arrival Time – CPU Cycle

Turnaround Time (t) = Finish Time – Arrival Time

• Preemptive scheduling policy
interrupts processing of a job and
transfers the CPU to another job. (the
Arrival process will interrupt the current
process)
– Algorithms 🡪 SRT,RR, PS

• Non-preemptive scheduling policy

functions without external interrupts.
– Once a job captures processor and
begins execution, it remains in
RUNNING state uninterrupted until it
issues an I/O request (natural wait) or
until it is finished (exception for infinite
loops).
– Algorithms 🡪 FCFS, SJN
Process Scheduling Algorithms

• First Come First Served (FCFS) –non

preemptive

• Shortest Job Next (SJN)- non preemptive

• Shortest Remaining Time First (SRT)
preemptive

• Round Robin- preemptive

• Priority Scheduling- preemptive or non
preemptive
To draw timeline and to do
calculations for process scheduling
algorithms
Job Arrival Time CPU
Cycle
A 0 8
B 1 5
C 2 3
D 3 1
E 4 7
a. First Come First Serve (FCFS)
Scheduling Good for batch
systems

The Timeline / Gantt Chart for the schedule is:

Job Arrival Time CPU Cycle
A 0 8
B 1 5
C 2 3
D 3 1
E 4 7

A B C D E
0 8 13 16 17 24
a. First Come First Serve (FCFS)
Scheduling
The Timeline / Gantt Chart for the schedule is:
A B C D E
0 8 13 16 17 24

Waiting Time (w) = Finish Time – Arrival Time – CPU

Cycle

Turnaround Time (t) = Finish Time – Arrival Time

b. Shortest Job Next (SJN) Scheduling (Non
Preemption)

The Timeline / Gantt Chart for the schedule is:

Job Arrival Time CPU Cycle
A 0 8
B 1 5
C 2 3
D 3 1
E 4 7

A D C B E
0 8 9 12 17 24
c. Shortest Remaining Time First
(preemptive)
Process Arrival Time CPU Cycle
A 0 8
B 1 70
5 40
C 2 20 3
D 3 10
E 4 0
7
A B C D C B A E
0 1 2 3 4 6 10 17 24
Shortest
ProcessRemaining Time
Arrival Time CPU Cycle
(preemptive)
A 0 3
B 1 210
5 0
C 2 20 3
D 3 10
E 5 0
1
AA A D C E C B
0 1 2 3 4 5 6 8 13
Shortest Remaining Time
(preemptive)
Process Arrival Time CPU Cycle
A 0 3
B 1 5
C 2 3
D 3 1
E 5 1

A D C E C B
0 1 2 3 4 5 6 8 13
d. Round Robin (Preemption)
• Run process for 1 time slice, then move to
back of queue. Each process gets equal share
of the CPU
• Interactive systems

The Timeline / Gantt Chart

for the schedule is:
Job Arrival Time CPU Cycle
A 0 8
B 1 5
C 2 3
D 3 1
E 4 7

(Time Quantum = 3)
 Process Arrival Time CPU Cycle
A 0 8520
B 1 5 20
C 2 30
D 3 10
E 4 7 4 10
A B C D A E B A E E
0 3 6 9 10 13 16 18 20 23 24

Ready Queue
B C D A E B A E E
1 2 3 4 6 13 16 23
Round Robin (Preemption)

The Timeline / Gantt Chart for the schedule is:

Job Arrival Time CPU Cycle

A 0 8

B 0 5

C 2 3

D 3 1

E 4 7

(Time Quantum = 3)
 Process Arrival Time CPU Cycle
A 0 8520
B 0 5 20
C 2 30
D 3 10
E 4 7 4 10
A B C D A E B A E E
0 3 6 9 10 13 16 18 20 23 24

Ready Queue
B C D A E B A E E
0 2 3 4 6 13 16 23
 Process Arrival Time Burst Time
P1 0 10
P2 0 4
Quantum = 12
P1 P2
0 10 14
Quantum = 6
P1 P2 P1
0 6 10 14
Quantum = 2
P1 P2 P1 P2 P1 P1 P1
0 2 4 6 8 10 12 14
 e. Non-Preemptive Priority
Process Arrival Time Burst Time Priority
P1 0.0 7 9
P2 2.0 4 10
P3 2.0 1 9
P4 5.0 4 11
Assume a larger number implies a higher priority

P1 P4 P2 P3
0 7 11 15 16
 f. Preemptive Priority
Process Arrival Time Burst Time Priority
P1 0.0 7 50 9
P2 2.0 4 10 10
P3 2.0 10 9
P4 5.0 40 11
Assume a larger number implies a higher priority

P1 P2 P4 P2 P3 P1
0 2 5 9 10 11 16
Do you agree that round robin
algorithm is the best algorithm
for interactive system? State
TWO (2) reasons to support your
answer.
• Yes. It provides reasonable response
times to interactive users.
• It provides fair CPU allocation.
 Process Arrival Time CPU Cycle
A 0 6
B 1 7
C 3 4
D 4 2
E 7 1
F 8 6
1. Shortest Remaining Time First
2. Round Robin (Time Quantum = 3)