Transcript Document

Ştefan Stăncescu
PART II
Operating Systems
LECTURE 9
PROCESSES MANAGEMENT
1
PROCESSES MANAGEMENT
blocked - not completely inactive, without time share
stored process status,
ready to be included in the time share
active - active state in time slot share
ready - inactive state but ready to receive
share time slot
2
PROCESSES MANAGEMENT
PROCESSES MANAGEMENT:
Share time slot allocation policy
PROCESSES Dispatcher:
priority process of OS dealing with
PROCESSES MANAGEMENT
“applications”
arbitration between processes in
the allocation of time slots
3
PROCESSES MANAGEMENT
Criteria for assessment of dispatching algorithms:
- fair play
any process takes some proper CPU
- Efficiency
CPU busy all the time
- reaction time
interactive users to be served promptly
-
Processing time
users that require outputs to be served quickly
- productivity
increasing the number of work / unit time.
4
PROCESSES MANAGEMENT
Specific contradictory processes elements ,
which can not be addressed dispatching standard:
- any evolutionary process is unique and unpredictable
(even same evolutionary process is different
every resume processing with other data)
- each process uses unpredictable resources
quantity (number) and quality (type)
- each process can not be estimated previously running
occurrence and duration of locking.
5
PROCESSES MANAGEMENT
The main problem:
excessive blocking a process.
Simple control : clock 50 Hz (or other ranges)
-
every interval - examines state of processes
- decision to continue or end the current process
Variations dispatching processes :
- run to completion - batch processing
one takes it and learn to control their own evolution
(cooperative scheduling)
- preemptive scheduling one process influence the
evolution of the other - the dialogue between processes
(eg supervisor).
- - RT scheduling – evolution of self-imposed periods
6
previously known
PROCESSES MANAGEMENT – Scheduling algorithms
Round Robin scheduling
old, simple, fair play, often used
rule: democratic distribution of time resources for CU
- Any process running in the same time period (quanta common, equal to any process)
- (A) the end of the quantum, or (b) it has been
blocked before or if (c) ended before
- Switch in ready tail and
- choose the next process in ready queue
7
PROCESSES MANAGEMENT – Scheduling algorithms
Round Robin scheduling
Disadvantage: unique quantum size selection:
- 5ms: CU is losing time (1ms) switching each process
- 500ms: large response time in interactive activities
(500ms x 10 trials = 5 s response time console)
Compromise (100ms) is difficult - unacceptable for all
8
PROCESSES MANAGEMENT – Scheduling algorithms
Priority scheduling
any process has a priority level, the high priority runs first => it decrements
the priority process
on CLOCK IT;
when sufficiently diminishing his priority
choose another process.
Processes assigned priorities are established:
-fixed – grade: general 100, colonel 90, captain 80 etc.
- cost:100lei/h -100;50lei/h -50 ;1leu/h - 1; etc.
-dynamic – priority assigned according to the current situation demand / supply
Increased priority will be assigned to processes that require more
resources available processes that require urgent access (mouse window)
9
PROCESSES MANAGEMENT – Scheduling algorithms
Multiple queuing scheduling
For example: m m tails round robin
10
PROCESSES MANAGEMENT – Scheduling algorithms
Multiple queuing scheduling
The process requires 500 quanta
Tails: 1,2,4,8,16,32,64,128
Round Robin on 1-100 switching (500ms CU lost)
Run the m m queue slots 2^^n
=>1=>2=>4=>8=>16=>32=>64 =>>> 7 switching
(7ms CU lost)
11
PROCESSES MANAGEMENT – Scheduling algorithms
Short Job First scheduling
Running necessary time in order ABCD:8444
ABCD => 8+(8)+4+(8+4)+4+(8+4+4)+4 =56
Total 56:4=14 for each average.
CDBA=> 4+(4)+4+(4+4)+4+(4+4+4)+4=44
Total 44:4=11 for each average
It requires previous knowledge of the runtime
(applications RT – algorithms RT)
12
PROCESSES MANAGEMENT – Scheduling algorithms
Short Job First scheduling - OK
but => we need run interval DR for each process
solution=collect info from previous runs of the processes
DRestimated for future = a * DRpast + (1-a) * DRpresent
At each run, from precedent and present DR => future DR
a < 1/2 => fast radical change => liberalism,
a => 0
instability,
a > 1/2 => slow change => conservatory,
a => 1
no change al all, inadaptability
13
PROCESSES MANAGEMENT – Scheduling algorithms
Guaranteed scheduling
good run guaranteed for each process
ex: each from n processes should have DR=1/n of DRtotal
=> A cell memory DRcosummed for each process
Calculate new priority for next run with
1/priority= DRcosummed / DRtotal
Random lottery scheduling
Each process receive a set of lottery tickets
Run probability = nr tickets ( may be OS controlled)
Threads in each process may transfer tickets between
From blocked threads to “important” threads
14
PROCESSES MANAGEMENT – Scheduling algorithms
RT scheduling
embedded systems – microcomputers
RT requirements – deadline mark for complete run
Hard RT - absolute requirements to be respected
Soft RT - easy – recommended requirements
Generally DR known for each, start from RT events
For a/periodic events – RT general schedule
For periodic events – Liu Layland schedulability formula
∑mi=1 DRi / Pi ≤ 1
(n processes, DRi= DR of i process, started by event at Pi time interval )
15
PROCESSES MANAGEMENT – Scheduling algorithms
RT scheduling EXAMPLE
periodic RT (rotating shaft w/sensors & actuators)
Pi=50ms
5 processes with DRi=25ms each
`
∑mi=1 DRi / Pi = 5 * 25 / 50 = 2,5 > 1
 3 processors are needed (or clock increase > 2,5 times)
16
PROCESSES MANAGEMENT – Scheduling algorithms
Threads scheduling
Scheduling in kernel or user zone
Threads list in user
Application management fast and optimized in the process
Threads list in kernel
Centralized management for all threads in all processes
fairness, fot all processes, but slow in save/restore
Compromise:
Kernel list in supervisor w/parameters by user
17