Model

Cyclic access: LRU against random replacement

LRU on a loop is bimodal: a cliff with nothing on it. Random replacement degrades smoothly.

h_{LRU} = {01 c < n c \geq n, h_{random} = (1 - \frac{1}{c})^{n (1 - h)} \approx e^{- n (1 - h) / c}

$n$: Loop length; pages in the loop
$c$: Frames; frames in the pool
$h$: Hit rate; the steady-state hit rate (a fixed point)

Recurring principle: Randomization replaces coordination

How it behaves

One input on the horizontal axis, the others held fixed.

random replacementLRU

Data table

Hit rate on a loop larger than the pool, by pool size
Pool ÷ loop c/n	series	Hit rate
0.1	random replacement	0
0.114	random replacement	0
0.128	random replacement	0
0.141	random replacement	0.001
0.155	random replacement	0.002
0.169	random replacement	0.003
0.182	random replacement	0.004
0.196	random replacement	0.006
0.21	random replacement	0.009
0.224	random replacement	0.012
0.237	random replacement	0.016
0.251	random replacement	0.02
0.265	random replacement	0.025
0.279	random replacement	0.031
0.292	random replacement	0.037
0.306	random replacement	0.044
0.32	random replacement	0.052
0.334	random replacement	0.06
0.347	random replacement	0.069
0.361	random replacement	0.078
0.375	random replacement	0.088
0.389	random replacement	0.098
0.402	random replacement	0.109
0.416	random replacement	0.121
0.43	random replacement	0.133
0.444	random replacement	0.146
0.458	random replacement	0.159
0.471	random replacement	0.173
0.485	random replacement	0.187
0.499	random replacement	0.202
0.512	random replacement	0.217
0.526	random replacement	0.233
0.54	random replacement	0.249
0.554	random replacement	0.265
0.568	random replacement	0.282
0.581	random replacement	0.3
0.595	random replacement	0.318
0.609	random replacement	0.336
0.622	random replacement	0.355
0.636	random replacement	0.374
0.65	random replacement	0.393
0.664	random replacement	0.413
0.677	random replacement	0.433
0.691	random replacement	0.454
0.705	random replacement	0.475
0.719	random replacement	0.496
0.732	random replacement	0.518
0.746	random replacement	0.54
0.76	random replacement	0.562
0.774	random replacement	0.585
0.787	random replacement	0.607
0.801	random replacement	0.631
0.815	random replacement	0.654
0.829	random replacement	0.678
0.842	random replacement	0.702
0.856	random replacement	0.727
0.87	random replacement	0.752
0.884	random replacement	0.777
0.897	random replacement	0.802
0.911	random replacement	0.828
0.925	random replacement	0.854
0.939	random replacement	0.88
0.952	random replacement	0.907
0.966	random replacement	0.933
0.98	random replacement	0.96
0.994	random replacement	0.985
1.01	random replacement	0.998
1.02	random replacement	1
1.03	random replacement	1
1.05	random replacement	1
1.06	random replacement	1
1.08	random replacement	1
1.09	random replacement	1
1.1	random replacement	1
1.12	random replacement	1
1.13	random replacement	1
1.15	random replacement	1
1.16	random replacement	1
1.17	random replacement	1
1.19	random replacement	1
1.2	random replacement	1
0.1	LRU	0
0.114	LRU	0
0.128	LRU	0
0.141	LRU	0
0.155	LRU	0
0.169	LRU	0
0.182	LRU	0
0.196	LRU	0
0.21	LRU	0
0.224	LRU	0
0.237	LRU	0
0.251	LRU	0
0.265	LRU	0
0.279	LRU	0
0.292	LRU	0
0.306	LRU	0
0.32	LRU	0
0.334	LRU	0
0.347	LRU	0
0.361	LRU	0
0.375	LRU	0
0.389	LRU	0
0.402	LRU	0
0.416	LRU	0
0.43	LRU	0
0.444	LRU	0
0.458	LRU	0
0.471	LRU	0
0.485	LRU	0
0.499	LRU	0
0.512	LRU	0
0.526	LRU	0
0.54	LRU	0
0.554	LRU	0
0.568	LRU	0
0.581	LRU	0
0.595	LRU	0
0.609	LRU	0
0.622	LRU	0
0.636	LRU	0
0.65	LRU	0
0.664	LRU	0
0.677	LRU	0
0.691	LRU	0
0.705	LRU	0
0.719	LRU	0
0.732	LRU	0
0.746	LRU	0
0.76	LRU	0
0.774	LRU	0
0.787	LRU	0
0.801	LRU	0
0.815	LRU	0
0.829	LRU	0
0.842	LRU	0
0.856	LRU	0
0.87	LRU	0
0.884	LRU	0
0.897	LRU	0
0.911	LRU	0
0.925	LRU	0
0.939	LRU	0
0.952	LRU	0
0.966	LRU	0
0.98	LRU	0
0.994	LRU	0
1.01	LRU	1
1.02	LRU	1
1.03	LRU	1
1.05	LRU	1
1.06	LRU	1
1.08	LRU	1
1.09	LRU	1
1.1	LRU	1
1.12	LRU	1
1.13	LRU	1
1.15	LRU	1
1.16	LRU	1
1.17	LRU	1
1.19	LRU	1
1.2	LRU	1

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

c = 0.9n → h ≈ 0.81 (LRU: 0)

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Memory & Resource Management
Who is allowed to hold how much memory, for how long, and what happens to the work when the answer is less than it asked for?
$h = (1 - 1/ c)^{n (1 - h)} \approx e^{- n (1 - h) / c}$
Read it in place →