84 lines
1.9 KiB
Typst
84 lines
1.9 KiB
Typst
|
#let sim-demand-paging(size: 3, requests, algo) = {
|
||
|
let mem = ()
|
||
|
|
||
|
let j = 0
|
||
|
let last-used = (:)
|
||
|
|
||
|
let states = ()
|
||
|
let cells = ()
|
||
|
let faults = 0
|
||
|
|
||
|
for (i, req) in requests.enumerate() {
|
||
|
// In memory
|
||
|
if req in mem {
|
||
|
cells.push(req)
|
||
|
|
||
|
// Not in memory but enough space
|
||
|
} else if mem.len() < size {
|
||
|
mem.push(req)
|
||
|
cells.push(req)
|
||
|
|
||
|
// Page fault
|
||
|
} else {
|
||
|
faults += 1
|
||
|
|
||
|
if algo == "FIFO" {
|
||
|
mem.at(j) = req
|
||
|
j = calc.rem(j + 1, size)
|
||
|
|
||
|
} else if algo == "OPT" {
|
||
|
let future = requests.slice(i + 1)
|
||
|
let dists = mem.map(v => {
|
||
|
let pos = future.position(v2 => v2 == v)
|
||
|
return if pos == none {calc.inf} else {pos}
|
||
|
})
|
||
|
let max = calc.max(..dists)
|
||
|
let k = dists.position(v => v == max)
|
||
|
mem.at(k) = req
|
||
|
|
||
|
} else if algo == "LRU" {
|
||
|
let k = mem.enumerate()
|
||
|
.map(p => (
|
||
|
p.first(),
|
||
|
last-used.at(
|
||
|
str(p.last())
|
||
|
)
|
||
|
))
|
||
|
.sorted(key: p => p.last())
|
||
|
.first()
|
||
|
.first()
|
||
|
|
||
|
mem.at(k) = req
|
||
|
}
|
||
|
|
||
|
cells.push(grid.cell(fill: red.lighten(40%), str(req)))
|
||
|
}
|
||
|
last-used.insert(str(req), i)
|
||
|
|
||
|
states.push(mem)
|
||
|
}
|
||
|
|
||
|
cells.insert(0, grid.cell(
|
||
|
rowspan: size + 1,
|
||
|
stroke: black,
|
||
|
inset: (x: 0.4em, y: 0.4em),
|
||
|
rotate(-90deg, reflow: true)[Faults: #faults]
|
||
|
))
|
||
|
|
||
|
for i in range(size) {
|
||
|
cells += states.map(s => s.at(i, default: none))
|
||
|
}
|
||
|
|
||
|
grid(
|
||
|
columns: requests.len() + 1,
|
||
|
inset: (x: 0.2em, y: 0.4em),
|
||
|
stroke: (x, y) => if y != 0 {
|
||
|
black + .5pt
|
||
|
},
|
||
|
column-gutter: 0.6em,
|
||
|
row-gutter: (0.4em,) + (0pt,) * size,
|
||
|
align: center + horizon,
|
||
|
fill: (x, y) => if y != 0 {blue.lighten(60%)},
|
||
|
..cells.map(c => if type(c) == int {str(c)} else {c})
|
||
|
)
|
||
|
}
|