Transcript CPU Scheduling

Operating System Examples Scheduling
References
 http://www.oreilly.com/catalog/linuxkernel/chapt




er/ch10.html
http://linuxbangalore.org/blug/meetings/200401/scheduler2.6.pdf
http://josh.trancesoftware.com/linux/linux_cpu_s
cheduler.pdf
http://www.linuxinsight.com/files/sched-designCFS.txt
Windows Operating System Internals Curriculum
Development Kit, developed by Solomon,
Russinovich and Polze
Solaris
 Solaris uses
priority-based
thread scheduling
 Each thread
belongs to one of
six classes
Time sharing
 Interactive
 Real time
 System
 File share
 Fixed priority

 Default class: time
sharing
 Within each class
there are
different priorities
 Each class uses
different
scheduling
algorithms
Solaris
 Time sharing scheduling algorithm
Dynamically alters priorities of processes
 Uses a multilevel feedback queue
 The higher the priority the smaller the time
slice
 The lower the priority the larger the time slice
 Interactive processes typically have higher
priority (good response time)
 CPU-bound processes have lower priority (good
throughput)

Solaris
 Time sharing scheduling algorithm
If a thread has used its entire time quantum
without blocking its priority is changed
 The priority of a thread that is returning from
sleeping (e.g. waiting for I/O) has its priority
increased

 Interactive scheduling algorithm
 Similar to time sharing but give window
managers (e.g., KDE, GNOME) a higher priority
Solaris Dispatch Table
Solaris
 Real-time class
Highest priority
 A thread in this class will before a process in
any other class
 Few processes belong in this class

 System class
 Kernel threads are assigned to this class e.g.,
scheduler and paging daemons
Solaris
 Fixed-priority
Relatively new
 Same number of priorities as time sharing but
no dynamic adjustment of priorities

 Fair-share
 Uses CPU shares instead of priorities
 A share is an indicator of entitlement
Solaris
 Each scheduling class includes a set of
priorities
 However, the scheduler converts the classspecific priorities into global priorities
 The thread with the highest global priority
is chosen to run
Solaris Scheduling
Windows XP
 The scheduler is called a dispatcher
 32-level priority scheme
 Priorities are divided into two classes:
 Variable class: priorities 1 to 15
 Real-time class: priorities 16 to 31
 There is a queue for each priority
 The dispatcher traverses the set of
queues from highest to lowest until it finds
a thread that is ready to run
 If there are no processes ready to run the
dispatcher executes the idle thread
Windows XP Scheduling
 Processes are given a priority class upon
creation:
REALTIME_PRIORITY_CLASS
 HIGH_PRIORITY_CLASS
 ABOVE_NORMAL_PRIORITY_CLASS
 NORMAL_PRIORITY_CLASS
 BELOW_NORMAL_PRIORITY_CLASS
 IDLE_PRIORITY_CLASS

 Priorities in all classes except the
REALTIME_PRIORITY class can change
Windows XP Scheduling
 A thread within a given priority class has a
relative priority within the class:
TIME_CRITICAL
 HIGHEST
 ABOVE_NORMAL
 NORMAL
 BELOW_NORMAL
 LOWEST
 IDLE

Windows XP
 Each thread has a base priority
representing a value in the priority range
for the class that the thread belongs
 The priority of each thread is based on
both the priority class it belongs to and its
relative priority within that class
 As with Solaris the classes and the
priorities in the classes are mapped to a
global priority
Windows XP Priorities
Windows XP
 Priority changes for threads in the variable
class
Time quantum expires: Priority is lowered but
not below the base priority
 Thread switches from blocked to running:
Priority is increased

• The amount depends on what the thread was doing
• Keyboard I/O gets a large increase while disk I/O
gets a moderate increase
Windows XP
 Windows XP distinguishes between the
foreground process that is currently
selected on the screen and the background
processes that are not currently selected
 The strategy tends to give good response
times to interactive threads that are using
the mouse and windows
 The I/O devices are kept busy
Linux Scheduling
 The Linux kernel internally represents
processes and threads as tasks via the
task_struct
 Linux uses task_struct (process control
block)to represent any execution context
A single-threaded process will be represented
with one task structure
 A multithreaded process will have one task
structure for each of the user-level threads

Linux Scheduling
 Constant order O(1) scheduling time
 Two priority ranges: time-sharing and real-
time
 Real-time range from 0 to 99 and nice
value from 100 to 140
 Linux (unlike Solaris) assigns higher
priority tasks longer time quanta and lower
priority tasks shorter time quanta
Linux Scheduling
Priorities and Time-slice length
Linux Scheduling
 A runnable task is considered for
execution on the CPU as long as it has time
remaining in its time slice
 When a task has exhausted its time slice,
it is considered expired and is not eligible
for execution again until all other tasks
have all exhausted their time slice
Linux Scheduling
 The kernel maintains a list of all runnable
tasks in a runqueue data structure
 In a multi-core machine there is a runqueue
for each processor
 Each runqueue consists of two priority
arrays:
Active: Contains all tasks with time remaining in
their time slices
 Expired: Contains all expired tasks

 The active, expired queues are indexed
according to priority
Linux Scheduling
List of Tasks Indexed According to Priorities
Linux Scheduling
 The scheduler chooses the task with the
highest priority from the active array for
execution
 When there are no more tasks in the
active array, the expired array becomes
the active array and the active array
becomes the expired array.
Linux Scheduling
 The scheduler chooses the task with the
highest priority from the active array for
execution
 A task’s dynamic priority is recalculated
when the task has exhausted its time
quantum and is to be moved to the expired
array
Linux Scheduling
 Linux tries to give a higher
priority to
interactive tasks
 The scheduler somehow needs to measure
the interactivity of a process
 Interactive processes sleep more than
others
Linux Scheduling
 The scheduler keeps track of the average
amount of time a task sleeps vs average
amount of time task uses CPU

Use the sleep_avg variable
 When a process wakes the time spent
sleeping is added to its sleep_avg;
 The run time is subtracted from sleep_avg
 The higher the value of sleep_avg the more
I/O bound it is
Question
Can Linux processes starve?
Case Study Discussion
 Basic idea for schedule user processes is the same
for all systems:


Lower priority for CPU bound process
Increase priority for I/O bound process
 The scheduling in Solaris / Linux is more
concerned about fairness.

More popular as the OSes for servers.
 The scheduling in Window XP is more concerned
about user perceived performance.

More popular as the OS for personal computers.
Summary
 We have examined scheduling in several
contemporary operating systems