in demand paging, if we have to kick out a page, which one do we kick?

possible basic approaches

• random page (this works surprisingly well)
• throw out the page that’s the longest in memory (this is BAD because if a page is there for a long time, its probably accessed a lot)
• oracle (pick the page whose next accesses is farest in the future… we can’t predict the future)
• LRU (replace the page that’s accessed longest time ago)

LRU sounds decently good, but recall that \(2^{36}\) wall times to store wall time for each page are needed which is bad

to be closed means that the operation of a group applied to an element of a group would produce another element of the group.

Exploring CLRS.

2

• insertion sort