Transcript The Active Streams Approach to adaptive distributed systems

Desktop Scheduling
You are running some long simulations.
In the mean time, why not watch an
illegally downloaded Simpsons
episode?
How can the operating system know
that the movie player slowdown is much
more perceivable than the batch
process slowdown?
4.1 Advanced Operating Systems
Scheduling Metric
Operating systems’ schedulers need a
new metric to identify and prioritize
interactive and multimedia jobs.
4.2 Advanced Operating Systems
Real-Time Priority
Most of UNIX and Windows versions
support a real-time scheduling.
A real-time process is served before the
other processes will be served.
In some OSes the real-time definition is
set on coding time, while in some other
OSes the definition can be set on
running time.
Both shift the burden to the
user/programmer
4.3 Advanced Operating Systems
What can be done automatically?
Desktop operating systems prioritize
processes based on CPU consumption.
– The less CPU consumed by a process, the higher
its priority.
It’s good for fairness:
– Each process gets a fair share of the CPU.
– Processes that wake up get a higher priority.
This scheme originates from UNIX (1970s).
And… operating systems still work that way.
4.4 Advanced Operating Systems
Linux Non-Realtime Scheduling
The Linux scheduler partitions time into
epochs.
In each epoch, every process has a time slice
of how long it may run.
When there are no ready processes with a time
slice left, a new epoch is started.
The order within the epoch is set according to
the dynamic priority.
– The dynamic priority is a number between 100 to
140 that is set according to the nice value
plus/minus bonus of 5. The bonus reflects the CPU
consuming of the processes.
4.5 Advanced Operating Systems
Linux Scheduling (cont.)
The calculation of the time slice is based on:
– The "nice" value.
– In Linux 2.4 Processes that did not use up all their previous
time slice transfer half of it to the new epoch.
• In Linux 2.6 the half of the unused time is not added.
Linux 2.6 tries to recognize interactive processes.
Essentially, tasks get an interactive credit when they
sleep for a longtime, and lose an interactive credit
when they run for a long time.
– Linux 2.6 will give another time slice in the same epoch to an
interactive process, if the interactive process uses up its
initial time slice.
In Linux 2.4 the time slices were calculated in the
beginning of the epoch. In Linux 2.6 the time slice is
calculated when a process leaves the CPU.
4.6 Advanced Operating Systems
Windows 2000 Scheduling
The "nice" value of Windows 2000 is called
"thread's type".
There are also some dynamic rules:
– Threads associated with the focus window get a triple
quantum.
• Multi-Media threads are not always in the focus window.
– After an I/O wait, the priority is boosted by a factor that
is inversely proportional to the speed of the I/O device.
This is then decremented by one at the end of each
quantum, until the original priority is reached again.
• Keyboard and mouse are very slow; hence contribute a big
boost.
4.7 Advanced Operating Systems
What About Interactivity?
In its early days, interactive computing was
text based.
– Drawing text does not require much CPU.
– User input devices are very slow.
Interactive jobs waited a lot, and consumed
little CPU.
Result: the little-CPU-long-waits-highpriority scheme favored interactive jobs.
Unfortunately, this is no longer the case.
4.8 Advanced Operating Systems
Contemporary Interactive Applications
Nowadays, applications use a lot of visual
and audible means for user interaction e.g.:
– Window based systems and the graphical user
interface widgets.
– Movie players with CPU intensive decompression.
– Games based on CPU massive graphical engines.
Modern Interactive and multimedia
applications consume substantial amounts of
CPU cycles.
Let us denote such processes as HumanCentered, or HuC for short.
4.9 Advanced Operating Systems
CPU Consumption
CPU consumption can no longer separate the
HuC processes from the rest
– Mplayer and Xine are movie players and Quake is
a computer game.
4.10 Advanced Operating Systems
Voluntary Context Switches
Switches that are induced by the process itself.
Does a HuC process relinquish the CPU
voluntarily more often?
– Reactive nature.
– Block on device.
– Wait for a timer.
4.11 Advanced Operating Systems
Effective Quantum Length
Effective Quantum Length is the interval from
when a process is allocated a CPU, until the
CPU is relinquished.
Does a HuC process consume CPU time in
small portions?
4.12 Advanced Operating Systems
Huc Characteristic
Because CPU consumption patterns
cannot automatically identify HuC
processes, the correct way is to directly
quantify the amount of user interaction
for the various processes.
Devices that mediate between the user
and a process will be called HuC
devices e.g. keyboard, mouse, screen,
joystick, speaker.
– For now, we will focus on the first three…
4.13 Advanced Operating Systems
Quantifying User Interactions
In UNIX, all user I/O is mediated by the
X-Windows system - specifically by the
X-Server.
The X-Server has been modified a little:
– X saves user I/O statistics for each window.
– These statistics are periodically reported to the
operating system kernel.
Quantifying I/O with the user raises cognitive
questions about relative importance of events.
– Is a keyboard press more important than a mouse drag?
– Is drawing a character more important than drawing an
image?
4.14 Advanced Operating Systems
The Simplest Solution
Input:
– simply accumulate input events.
– Dragging the mouse will generate multiple events, while
clicking the mouse or a keyboard press are just one
event.
• The user is very slow!
Output:
– quantify the changes produced by each graphical request.
• In graphical shapes, count the pixels that have been changed.
• In text, assume all of the pixels in the character's box have been
changed.
– Do not count changes in hidden portions of the window.
4.15 Advanced Operating Systems
Scheduling by I/O Quantification
Windows with input are the most important ones.
The next priority is widows with output.
Windows without I/O are less important.
Applications like Emacs are unaffected.
– Emacs requires less than 1% of the CPU cycles and
gets that in the old and the modified scheduler.
The responsiveness of the windows manager is
also improved.
– On heavy loaded systems the windows manager
(using the old scheduler) finds difficult in moving
windows around.
4.16 Advanced Operating Systems
Experimental Results
Desktop Scheduling autonomously
identifies HuC processes, and prioritizes
them.
4.17 Advanced Operating Systems
Open Questions
Where does sound fit in?
Is it practical to measure network
bandwidth in order to improve
streaming?
How can other devices integrated into
this model?
4.18 Advanced Operating Systems