 |
Model
the process behavior, in multiprogrammed environment, in terms of system
demand
 |
System
demand - a unified resource (in this paper, only processor and
memory) requirement by a process |
|
Q:
Why not disk, devices, network bandwidth, etc. too? |
|
A:
disk - disk usage is considered partly due to virtual memory |
|
|
Process
behavior should be modeled based only its dynamic resource requirement
|
Input
from user or assist from compiler can NOT be expected |
|
|
Each
process has its own virtual machine, which is composed of a processor and
infinite one-level virtual memory |
|
Page
is brought in only on demand. No look-ahead! |
|
Introduction
|
Programmer's
view of WS: the smallest collection of information that must be in
memory to execute her program efficiently |
|
System's
view of WS: the set of most recently referenced pages |
|
Working
set W(t, t): the set of pages referenced by the process during
(t - t,
t) |
|
w(t,
t):
the size of W(t, t) |
|
x
= the mean value of the interval within which the same page is
referenced |
|
Assumptions
(restrictions)
about W(t, t)
 |
pages
in W(t, t) is continuously in memory |
|
process
is never interrupted except for page faults |
|
a
page is removed from memory the moment it leaves W |
|
|
|
Properties
of Working Set
|
size
and t: Fig 3 |
|
prediction:
when a < t,
W(t, t) is a good predictor of
W(t + a,
t) |
|
reentry
rate
|
reentry
of a page = leaving the working set and brought into the set
again |
|
process
reentry rate = 1 / mean time between reentries
|
proportional
to (1 - prob(page x is referenced
again within t)) |
|
proportional
against expected value of inter-reference interval |
|
l(t) = [1 - prob(page x is referenced
again within t)] / expected value of
inter-reference interval |
|
|
real
time reentry rate:
|
reentry
rate = number of reentries during A sec / (A sec + total
time spent page traffics for reentries)
|
number
of reentries during A sec = A sec * l(t) |
|
total
time spent page traffics for reentries = time to
bring a page from disk to memory * number of
reentries during A sec |
|
|
f(t) =
[A * l(t)] / [
A + A * l(t) *
time to bring the page from disk into memory]
|
l(t) / [
1 + l(t) *
time to bring the page from disk into memory] |
|
|
|
traffic
rate between memory and disk: 2 * [ real time reentry rate * S(w(t,
t)) ] |
|
|
t-Sensitivity:
how sensitive is l(t) to changes in
t
|
sensitivity
s(t)
= - (d l(t) / d
t) |
|
Decreasing
t never
results in decreasing l(t) |
|
|
|
Choice
of t
|
residency:
the fraction of time a page is potentially available in memory
|
x(=
inter-reference interval) < t ->
1 = 100% |
|
t
< x < t
+ T (page traffic time) -> t
/ [t + 2 *
T] |
|
t
+ T < x -> t
/ [x + T] |
|
Fig.
4: residency vs x => t
should be determined considering T |
|
|
|
Detecting
W(t, t)
|
Using
a special hardware is impractical |
|
Software
scheme
|
use
referenced bit |
|
periodically
shift the reference bit |
|
If
OR(bits) = 1, the page is in the W(t, t) |
|
|
|
Memory
Allocation
|
Look-ahead
is not good
|
Look-ahead
requires the knowledge of W(t, t) |
|
Interactive
program make look-ahead futile |
|
|
Reserving
w(t, t) pages together with demand-paging is enough
|
Q:
Is this true for modern OS? |
|
|