Transcript scheduling

What Is In This Presentation?
• It is about Process Scheduling.(zaman
çizelgesi)
• The design of a scheduler
• It centers around Round Robin algorithms that
perform
start
In computer science, scheduling is the method
by which threads, processes or data flows are
given access to system resources (e.g. processor
time, communications bandwidth).
scheduling
This is usually done to load balance a system
effectively or achieve a target quality of service.
• The need for a scheduling algorithm arises from
the requirement for most modern systems
• to perform multitasking (execute more than
one process at a time)
• and multiplexing (transmit multiple flows
simultaneously).
The scheduler
The scheduler is concerned mainly with:
• Throughput(üretilen iş) - The total number of processes
that complete their execution per time unit.
• Latency (gecikme), specifically:
– Turn-around time (dönüş süresi)- total time between
submission of a process and its completion.
– Response time (tepki süresi)- amount of time it takes from
when a request was submitted until the first response is
produced.
• Fairness / Waiting Time(bekleme süresi) - Equal CPU
time to each process (or more generally appropriate
times according to each process' priority). It is the time
for which the process remains in the ready queue.
The scheduler
• The scheduler assigns a fixed time unit per process, and
cycles through them.
• RR scheduling involves extensive overhead, especially with
a small time unit.
• Balanced throughput between FCFS and SJF, shorter jobs
are completed faster than in FCFS and longer processes are
completed faster than in SJF.
• Poor average response time, waiting time is dependent on
number of processes, and not average process length.
• Because of high waiting times, deadlines are rarely met in a
pure RR system.
• Starvation can never occur, since no priority is given.
• Order of time unit allocation is based upon process arrival
time, similar to FCFS.
 There is no universal “best” scheduling algorithm, and many
operating systems use extended or combinations of the scheduling
algorithms above.
 Windows uses a multilevel feedback queue, a combination of
-fixed priority preemptive scheduling,
- round-robin,
- and first in first out.
In this system, threads can dynamically increase or decrease in priority
depending on if it has been serviced already, or if it has been waiting
extensively.
 Every priority level is represented by its own queue, with roundrobin scheduling amongst the high priority threads and FIFO among
the lower ones.
 The algorithm used may be as simple as round-robin in which each
process is given equal time (for instance 1 ms, usually between
1 ms and 100 ms) in a cycling list. So, process A executes for 1 ms,
then process B, then process C, then back to process A.
Scheduling disciplines
• Scheduling disciplines are algorithms used for
distributing resources among parties which
simultaneously and asynchronously request them
Scheduling disciplines are used
• in routers (to handle packet traffic) as well as
• in operating systems (to share CPU time among
both threads and processes),
• disk drives (I/O scheduling),
• printers (print spooler), most embedded
systems, etc.
Scheduling Goals
• Maximize throughput and resource utilization.
– Need to overlap CPU and I/O activities.
• Minimize response time, waiting time and
turnaround time.
• Share CPU in a fair way.
• May be difficult to meet all these goals-sometimes need to make tradeoffs(An
exchange that occurs as a compromise).
Purpose of scheduling
 The main purposes of scheduling algorithms are
to minimize resource starvation and to ensure
fairness amongst the parties utilizing the
resources.
Note :- Starvation occurs if a low priority process never
runs. The ssolution is: build aging into a variable priority.
 Scheduling deals with the problem of deciding
which of the outstanding requests is to be
allocated resources. There are many different
scheduling algorithms
 One of them are Round Robin Algorithem
Round-robin scheduling
Round-robin (RR) is one of the algorithms
employed by process and network schedulers in
computing.
As the term is generally used,
• time slices are assigned to each process in equal
portions and in circular order,
• handling all processes without priority (also
known as cyclic executive).
• Round-robin scheduling is simple, easy to
implement, and starvation-free.
Round-robin scheduling cont.
• Round-robin scheduling can also be applied to
other scheduling problems, such as data packet
scheduling in computer networks.
• It is an Operating System concept.
• The name of the algorithm comes from the
round-robin principle known from other fields,
where each person takes an equal share of
something in turn.
RR Process scheduling
 In order to schedule processes fairly, a roundrobin scheduler generally employs time-sharing,
giving each job a time slot or quantum[1] (its
allowance of CPU time), and interrupting the job
if it is not completed by then.
 The job is resumed next time a time slot is
assigned to that process. In the absence of timesharing, or if the quanta were large relative to the
sizes of the jobs, a process that produced large
jobs would be favoured over other processes.
ROUND ROBIN:
 Use a timer to cause an interrupt after a predetermined
time.
 Preempts (have precedence over) if task exceeds it’s
quantum.
 Definitions:
– Context Switch -Changing the processor from
running one task (or process) to another. Implies
changing memory.
– Processor Sharing Use of a small quantum such that
each process runs frequently at speed 1/n.
– Reschedule latency How long it takes from when a
process requests to run, until it finally gets control
of the CPU.
Choosing a time quantum
 Choosing a time quantum
– Too short - inordinate (excessive) fraction of
the time is spent in context switches.
–
Too long - reschedule latency is too great. If
many processes want the CPU, then it's a
long time before a particular process can get
the CPU. This then acts like FCFS.
– Adjust so most processes won't use their
slice. As processors have become faster, this
is less of an issue.
Round Robin (RR)
– FCFS + preemptive scheduling.
• First Come First Served (FCFS)-Scheduler selects the process
at the head of the ready queue; typically non-preemptive
– Ready queue is treated as a circular queue.
– Each process gets the CPU for a time quantum (or
time slice), typically 10 - 100 ms.
– A process runs until it blocks, terminates, or uses
up its time slice.
Example
– Example: Assuming a time quantum of 4 ms, what’s the
average waiting time?
• Issue: What’s the right value for the time quantum?
• Too long => poor response time
• Too short => poor throughput
• RR pros & cons:
+ Works well for short jobs; typically used in timesharing systems.
– High overhead due to frequent context switches.
– Increases average waiting time, especially if CPU bursts are the
same length and need more than one time quantum.
Scheduling
Algorithms
CPU SCHEDULING
EXAMPLE DATA:
Process Arrival
Time
0
1
2
3
1
2
3
4
Note:
Example violates rules for
quantum size since most
processes don’t finish in one
quantum.
Service
Time
8
4
9
5
Round Robin, quantum = 4, no priority-based preemption
P1
0
P2
4
P3
8
P4
12
P1
16
P3
20
P4
24
P3
25
Average wait = ( (20-0) + (8-1) + (26-2) + (25-3) )/4 = 74/4 = 18.5
5: CPU-Scheduling
17
26
Example
As an Example From networks
• Round robin DNS & DDNS (Dynamic DNS) is
often used to load balance requests between
a number of Web servers.
For example, a company has one domain name
and three identical copies of the same web site
residing on three servers with three different IP
addresses.
5: CPU-Scheduling
18
Weighted round robin
• Weighted round robin (WRR) is a scheduling
discipline
• specifically for scheduling in ATM networks using
fixed size packets (cells).
• In the more general case of IP networks with
variable size packets, in order to approximate
GPS(Generalized processor sharing) the weight
factors must be normalized.
Service is shared between all non-empty classes in the
same ratio as the weight factors (positive values for
each service class).
5: CPU-Scheduling
19
Deficit Round Robin
• Deficit Round Robin (DRR), also Deficit Weighted
Round Robin (DWRR), is a scheduling algorithm for
the network scheduler.
WRR serves every non-empty queue where as DRR
serves packets at the head of every non-empty queue
whose deficit counter is greater than the packet's size at
the head of the queue (HoQ).
If the deficit counter is lower,
• then the queue is skipped (HoQ packet is not served)
• and its credit is increased by some given value called quantum.
• This increased value is used to calculate the deficit counter the next time around
when the scheduler examines this queue for serving its head-of-line packet. If
the queue is served, then the Credit is decremented by the size of packet being
served.
5: CPU-Scheduling
20
What if?
• What happens if the time allocated in a Round
Robin Scheduling is very large? And what
happens if the time allocated is very low?
 Ans: It results in a FCFS scheduling, that means
Scheduler selects the process at the head of the
ready queue; typically non-preemptive
If time is too low, the processor through put
is reduced. More time is spent on context
switching
Operating System
Preemption
Algorithm
Amiga OS
Yes
Prioritized Round-robin scheduling
FreeBSD
Yes
Multilevel feedback queue
Linux pre-2.6
Yes
Multilevel feedback queue
Linux
2.6-2.6.23
Summary
Yes
O(1) scheduler
Linux post-2.6.23
Yes
Completely Fair Scheduler
Mac OS pre-9
None
Cooperative Scheduler
Mac OS 9
Some
Preemptive for MP tasks, Cooperative
Scheduler for processes and threads
Mac OS X
Yes
Multilevel feedback queue
NetBSD
Yes
Multilevel feedback queue
Solaris
Yes
Multilevel feedback queue
Windows 3.1x
None
Cooperative Scheduler
Windows 95, 98, Me
Half
Preemptive for 32-bit processes, Cooperative
Scheduler for 16-bit processes
Windows NT (including 2000, XP, Vista, 7, and
Yes
Server)
Multilevel feedback queue