
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 interreference interval 

l(t) = [1  prob(page x is referenced
again within t)] / expected value of
interreference 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)) ] 


tSensitivity:
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(=
interreference 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

Lookahead
is not good

Lookahead
requires the knowledge of W(t, t) 

Interactive
program make lookahead futile 


Reserving
w(t, t) pages together with demandpaging is enough

Q:
Is this true for modern OS? 

