Transcript CS 5520 Operating Systems

Operating Systems:
Introduction
1.
 2.
 3.
 4.

Historical Development
The OS as a Resource Manager
Definitions
The Process
The OS as a Resource
Manager

Resources
– 4 functions
 Keep track of resource
 Enforce policy  Allocate
 Reclaim
The OS as a Resource
Manager

Memory management
– Keep track
– If multiprogramming:
– Allocate
– Reclaim (pi relinquishes it or terminates)
The OS as a Resource
Manager

Processor management
– Keep track of
– Scheduling:
– Allocate :
– Reclaim : pi relinquishes P, terminates, exceeds
TS
The OS as a Resource
Manager

Device management
– Keep track of devices, channels, control
units
– Efficient allocation policy
– Allocate :
– Reclaim : Normally automatic termination
The OS as a Resource
Manager

Information management
– Keep track : Location, use, status (
)
– Who gets use of resources, enforce
protection, provide accessing routines
– Allocate (“Open file”)
– Deallocate (“Close file”)
Kernel
Level 5
Level 4
Level 3
Processor management
lower module (P,V),
Process Scheduler
Level 2
Memory management
Level 1
Processor management
upper module
(messages, createdestroy process)
Bare
machine
Device management
(I/O traffic control)
Info management
(File system)
Jobs
Hierarchical
OS Structure
Supervisor process
(Job scheduler)
Process 1
Process 2
SPOOLing
Process 3
User-created
process
I/O process
Layer 2
Layer 1
I/O process
working with
User process 3
Kernel
(Layer 0)
Definitions

Operating System (OS) :
– Software governing control of resources
–(
)
– Interface
Processor : Hardware which interprets
and executes instructions
 Process (task) :


Job : Set of modules req’d to perform
Definitions

Multiprogramming :

Privileged instruction :
– Instruction available only to
– Executed in supervisor (executive) state as
opposed to problem (user) state.

Interrupt :
– Mechanism forcing processor to take notice of
event
I.4 The Process
Process (pi) : A program in a state of
execution
 Life : (Higher level view)

– 1. Run : pi<-P
– 2. Wait : For event
– 3. Ready :
RUN
pi
READY
P
I/O complete
Wait for I/O
completion
WAIT
Life of a Process

Lower level view :
COMPLETE
RUN
SUBMIT
HOLD
READY
WAIT
Processor Management and
Scheduling
1. Introduction
 2. Basic Concepts
 3. Processor Scheduling Algorithms

Introduction
Given : 2 jobs, A and B.
 Each executes for 1 sec, waits for 1 sec
 Repeat this for 60 cycles [ 2 min ]

– 1. Let’s run A, then B
A:
2 min
B:
2 min
Elapsed Time : 4 min
Compute Time : 2 min
CPU Utilization : 2/4 = 50%
Introduction
– 2. Now multi-program A and B
A:
B:
Elapsed Time : 2+ min
Compute Time : 2 min
CPU Utilization : 2/2+ = ~100%
– Compare to 1 : A finishes at same time,
B in half the time.
Introduction

So now we have multiprogramming:
– N jobs in memory
– Job i
P
– When i waits for I/O, j
P
 Overlap CPU and I/O to keep P busy
– Benefits : Increased CPU utilization and
higher throughput.
 Throughput : Work done in given period.
– E.g. 10 jobs per hour.
Basic Concepts

Process : a program in a state of
execution.
– E.g. Batch job, transaction (in T-S system)
– Also called : job, program, task, activity.

Process behavior : pi alternate between
execution(CPU burst) & I/O(I/O burst).
– Generally begins and ends with CPU
bursts.
Basic Concepts

pi change state as they execute
– READY, RUN, WAIT, HOLD.

Process Control Block (PCB)
– Process is represented internally by its PCB
– Active representation of passive entity,
the PGM
 “The only tangible part of a process”
– PCB










Process id
Current State
Priority
Other CPU Scheduling info
State info : PC (address of NI to be executed)
register, cc contents
Memory management info : base-bounds
registers, page tables
Accounting info : amount of CPU time, account #
I/O status info : I/O requests pending, I/O
devices allocated, list of open files
Pointer to list of all pi in same state
etc.
Basic Concepts

Scheduling queues
– Ready queue : List of processes (PCBs) in ready
state (awaiting assignment of P)
Head
Tail
Queue
header
PCB i
Registers
.
.
.
PCB j
Registers
.
.
.
...
PCB n
Registers
.
.
.
– Device queue : List of pi waiting on this device
– I/O queue : pi waiting for I/O (once served, pi
moves to Ready queue).
Basic Concepts

Schedulers :
– Job (long-term) scheduler :

Selects job from spool queue to enter system,
loads it into memory
– Processor (CPU, short-term) scheduler :

Selects ready pi and dispatches (assigns P to) it
– Difference : How often they execute
– Job scheduler
 Infrequently once steady state is reached
 Controls degree of multiprogramming
(number of pi in memory)
– Processor scheduler
 Must select new pi very frequently (every
10 ms)
 FAST or much of the processor time is
spent in scheduling !
Basic Concepts

Dispatcher
– Assigns P to pi selected by Processor
scheduler
– Loads pi’s registers
– Changes to user mode
– Jumps to proper address [ to (re)start it ]
Processor Scheduling Algorithms
Problem : Which pi in Ready queue gets P?
 Performance Criteria (Comparing algorithms):

– Throughput : Work done in given period.
– CPU utilization : P busy time / Total elapsed time
 Want it as busy as possible (40-90%).
– Turnaround time : Interval between submission to
completion of job (Batch OS).
– Wait time : Time spent by pi in Ready queue.
– Response time : Interval from submission until
response produced (Interactive system).
Processor Scheduling Algorithms

Let’s optimize as follows :
– Maximize CPU utilization, throughput
– Minimize turnaround time (TT), wait,
response time.
– Operationally :
 Optimize average or max or min
 e.g. Minimize the max response time
Minimize variance in response time.
Common Scheduling
Algorithms
(a) First Come First Served (FCFS)
 (b) Shortest Job First (SJF)
 (c) Priority

– Preemptive vs Non-preemptive
(d) Round Robin
 (e) Multilevel Queues

Scheduling Algorithms

First Come First Served (FCFS)
– Implementation : FIFO queue
pi
– pj enters ready q : RQ
– pi dispatched :
RQ
– Consider :
Job
A
B
C
CPU burst
24
3
3
pk
...
pj
pk
...
pj
 FCFS
– Suppose jobs arrive in order A, B, C and
are served FCFS.
A
B
0
24
C
27
30
TT : For A = 24, For B = 27, For C = 30
 Avg TT : (24 + 27 + 30) / 3 = 27

– Now, suppose they arrive in order B, C, A
B
0
C
3

A
6
Avg TT : (3 + 6 + 30) / 3 = 13
30
Scheduling Algorithms

Shortest Job First (SJF)
– Associates with job the length of its next CPU
burst
– Example of priority scheduling (job with
shortest next CPU burst gets highest priority)
– Consider :
Job CPU burst
A
6
B
3
C
8
D
7
 SJF
B[3]
0
A[6]
3

D[7]
9
C[8]
16
Avg TT : (3 + 9 + 16 + 24) / 4 = 13
– This algorithm can be proved optimal

Gives min avg wait time for given set of jobs
– Problem : Length of next CPU burst
Batch jobs : Time limit supplied by user
 Processes : Can’t know [but can predict]

24
Scheduling Algorithms

Priority Scheduling
– Can be assigned : who is paying, type of work
– Can be computed :

Time limits, memory req., ratio avg I/O burst to CPU
burst, number of open files
– Major problem : Starvation


Low priority Ready pi can wait indefinitely for CPU
Eventually, load lightens and job gets run, or system
crashes and job is lost
– Remedy
 Aging : Increase priority of low priority job over time
Scheduling algorithms

Round Robin (RR)
– Designed for TS systems
 Given defined TS (10-100 ms).
– CPU scheduler traverses Ready queue,
selects pi to be dispatched for interval  TS
– Implementation :




Ready queue = FIFO queue
CPU scheduler picks 1st job in Ready queue
Sets timer to interrupt after 1 TS
Dispatches process
Scheduling algorithms

Multilevel Queue
– Good when jobs easily classified into groups

e.g. foreground (FG - interactive) and
background (BG - batch)
– In a multilevel scheduling algorithm :


Ready queue partitioned into separate queues
Each pi assigned permanently to one queue
– Due to memory size, job type, …

Each queue has its own scheduling algorithm
– FG : RR, BG : FCFS

Must have scheduling between the queues
– e.g. Fixed priority preemptive (such as FG > BG)