![](indbul1a.gif) |
Task
model
![](indbul2a.gif) |
Task
is modeled as a memory reference string, which is a sequence of (p, d) such
that
![](indbul3a.gif) |
p
is a page in the virtual address space of the process |
![](indbul3a.gif) |
d
is dirty flag |
|
![](indbul2a.gif) |
Virtual
time of a task: the number of completed references to pages for the
task |
|
![](indbul1a.gif) |
Operating
system model
![](indbul2a.gif) |
A
task is either
![](indbul3a.gif) |
in
the active queue, |
![](indbul3a.gif) |
in
the ready queue, or |
![](indbul3a.gif) |
dormant
(or blocked) |
|
![](indbul2a.gif) |
Load
control moves tasks between the ready and the active queue |
![](indbul2a.gif) |
Tasks
in the active queue get scheduled according to a scheduling
discipline |
|
![](indbul1a.gif) |
Working
Set
![](indbul2a.gif) |
Working
set determination: finding pages leaving W is difficult
![](indbul3a.gif) |
Needs
to scan all the resident pages of the process, or needs to
maintain the set of pages in W to scan only pages in W |
|
![](indbul2a.gif) |
Load
control and replacement
![](indbul3a.gif) |
Needs
to maintain a free list of pages which do not belong to any W |
|
![](indbul2a.gif) |
Page
Writing and Reclamation
![](indbul3a.gif) |
Pages
in the free list should be reclaimed if it is referenced
before being kicked out |
|
|
![](indbul1a.gif) |
Global
Clock
![](indbul2a.gif) |
Naive
extension of Clock algorithm but with some feedback mechanism (such
as clock hand movement rate) to control multiprogramming level |
|
![](indbul1a.gif) |
Comparing
WS and Clock
![](indbul2a.gif) |
WS
requires more memory and complex algorithm
![](indbul3a.gif) |
WS-scan
procedure |
![](indbul3a.gif) |
Space
for LR(p) (Latest Reference time of the page) doubles page table.
Remember that the size of page table does matter |
![](indbul3a.gif) |
Algorithm
to maintain free list of pages, including a method to reclaim
pages from the list |
|
![](indbul2a.gif) |
Clock
requires a fine tuned adaptive feedback load control mechanism |
![](indbul2a.gif) |
In
Clock, a greedy process can monopolize memory |
|
![](indbul1a.gif) |
Process
is either in loading phase or running phase
![](indbul2a.gif) |
Loading
phase: W has not been loaded yet |
|
![](indbul1a.gif) |
Problem
![](indbul2a.gif) |
Loading
time (wall-clock-time to bring pages in W in memory) is proportional to the
number of loading processes because all the loading processes
contend for a single auxiliary memory |
![](indbul2a.gif) |
Many
loading processes increase the probability that
![](indbul3a.gif) |
running processes
finish their
job while loading processes contending each other and |
![](indbul3a.gif) |
they
are replaced by even more loading processes |
|
![](indbul2a.gif) |
=>
Disk is over committed, but memory is under committed! |
|
![](indbul1a.gif) |
Solution
![](indbul2a.gif) |
Decrease the loading time
by controlling the number of loading processes at a moment |
|
![](indbul1a.gif) |
A
process is in loading phase until
![](indbul2a.gif) |
v virtual time
elapsed, or |
![](indbul2a.gif) |
the
process issues an I/O request, otherwise I/O bound process can
prevent new task activation undefinitely |
|
![](indbul1a.gif) |
LT/RT
can be used to refrain from loading another process
![](indbul2a.gif) |
while
some of memory resident processes are still in loading phase, where
![](indbul3a.gif) |
the
size of the working set is not known yet! |
|
|