CPU
Scheduler
•
Selects from
among the processes in memory that are ready to execute, and allocates the CPU
to one of them.
•
CPU
scheduling decisions may take place when a process:
1.
Switches from running to waiting state.
2.
Switches from running to ready state.
3.
Switches from waiting to ready.
4.
Terminates.
•
Scheduling
under 1 and 4 is nonpreemptive.
•
All other
scheduling is preemptive.
Types of
scheduler
- Long-term scheduling The decision to add to the pool of processes to be executed
- Medium-term scheduling The decision to add to the number of processes that are partially or fully in main memory
- Short-term scheduling The decision as to which available process will be executed by the processor
- I/O scheduling The decision as to which process’s pending I/O request shall be handled by an available I/O device
Long Term
Scheduler
·
Determines
which programs are admitted to the system for processing
·
Controls the
degree of multiprogramming
·
the more
processes that are created, the smaller the percentage of time that each
process can be executed
·
may limit to
provide satisfactory service to the current set of processes
Medium Term
Scheduler
·
Part of the
swapping function
·
Swapping-in
decisions are based on the need to manage the degree of multiprogramming
·
considers
the memory requirements of the swapped-out processes
Short Term
Scheduler
·
Known as the
dispatcher
·
Executes
most frequently
·
Makes the
fine-grained decision of which process to execute next
·
Invoked when
an event occurs that may lead to the blocking of the current process or that
may provide an opportunity to preempt a currently running process in favor of
another
Short Term
Scheduling criteria
·
Main objective
is to allocate processor time to optimize certain aspects of system behavior
·
A set of
criteria is needed to evaluate the scheduling policy
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.
Scheduling
Criteria
•
CPU
utilization – keep the CPU as busy as possible
•
Throughput –
# of processes that complete their execution per time unit
•
Turnaround
time – amount of time to execute a particular process
•
Waiting time
– amount of time a process has been waiting in the ready queue
•
Response
time – amount of time it takes from when a request was submitted until the
first response is produced, not output (for time-sharing
environment)
Optimization
Criteria
•
Max CPU
utilization
•
Max
throughput
•
Min
turnaround time
•
Min waiting
time
•
Min response
time
Interactive
Scheduling Algorithm
•
Round-robin
scheduling
•
Virtual
Round Robin scheduling
•
Shortest
rocess Next
•
Shortest
Remaining Time Next
•
Highest
Response Ratio Next
•
Feedback
Scheduling
•
Guaranteed
Scheduling
•
Fair Share
Scheduling
•
Real Time
Scheduling
Round Robin
Scheduling
·
Uses
preemption based on a clock
·
Also known
as time slicing because each process is given a slice of time before
being preempted
·
Principal design
issue is the length of the time quantum, or slice, to be used
·
Particularly
effective in a general-purpose time-sharing system or transaction processing
system
·
One drawback
is its relative treatment of processor-bound and I/O-bound processes
Shortest
Process Next
·
Nonpreemptive
policy in which the process with the shortest expected processing time is
selected next
·
A short
process will jump to the head of the queue
·
Possibility
of starvation for longer processes
·
One
difficulty is the need to know, or at least estimate, the required processing
time of each process
·
If the
programmer’s estimate is substantially under the actual running time, the
system may abort the job
Shortest
Remaining Time Next
·
Preemptive
version of SPN
·
Scheduler
always chooses the process that has the shortest expected remaining processing
time
·
Risk of
starvation of longer processes
·
Should give
superior turnaround time performance to SPN because a short job is given
immediate preference to a running longer job
Highest
Respone Ratio Next
·
Chooses next
process with the greatest ratio
·
Attractive
because it accounts for the age of the process
·
While
shorter jobs are favored, aging without service increases the ratio so that a
longer process will eventually get past competing shorter jobs
Fair Share
Scheduling
·
Scheduling
decisions based on the process sets
·
Each user is
assigned a share of the processor
·
Objective is
to monitor usage to give fewer resources to users who have had more than their
fair share and more to those who have had less than their fair share
Fai Share
Scheduling
Fair Share Scheduling
Take into account who owns a process
Each user is allocated some fraction
of the CPU
Thus, if 2 users have been promised
50% of the CPU, they will each get that, no matter how many processes they have
Example:
User 1 has 4 processes: A, B, C, D
User 2 has 1 process: E
If both users are promised 50% of
CPU time, the possible scheduling sequence would be
A E B E C E D E A E …
if user 1 entitled twice as much CPU
time as user 2, we might get:
A B E C D E A B E C D E …
Real Time
Scheduling
Schedulable
real-time system
•
Given
–
m periodic events
–
event i
occurs within period Pi and requires Ci seconds
•
Then the
load can only be handled if
•
Example:
–
A soft real
time system with three periodic event, with periods of 100, 200, and 500 ms. If
these events require 50, 30, and 100 ms of CPU time per event à the system
is schedulable because
0.5 + 0.15 + 0.2 < 1Jawaban soal di E-book:
1. First-Come First-Serve
Waiting time for A=0, B=2, C=5, D=1, E=3
Average Waiting Time = (0+2+5+1+3)/5 = 2, 2
2. Shortest Job First – Non Preemptive
Waiting time for A=0, B=4, C=0, D=1, E=3
Average Waiting Time = (0+4+0+1+3)/5 = 1, 6
3. Shortest Job First – Preemptive
Waiting time for A=0, B=4, C=0, D=1, E=3
Average Waiting Time = (0+4+0+1+3)/5 = 1, 6
No comments:
Post a Comment