🧠
Mechanism Depth - How It Works
💡 This level explains the internal workings, trade-offs, and practical considerations of each algorithm. Understanding these details helps you discuss implementation and performance in interviews.
Intuition
Each algorithm uses a different heuristic to approximate the best page to evict, balancing complexity and performance.
Explanation
FIFO maintains a queue of pages in the order they were loaded; when a page fault occurs, it evicts the page at the front of the queue. This is simple but can lead to suboptimal decisions, including Belady's anomaly where more frames cause more faults. LRU tracks page usage over time, evicting the page that has not been used for the longest period, approximating the optimal future knowledge. Implementing LRU requires additional data structures or hardware support, such as counters or stacks. The Optimal algorithm, while not implementable in practice, serves as a benchmark by evicting the page that will not be used for the longest time in the future, minimizing page faults theoretically. Understanding these mechanisms helps in analyzing trade-offs between implementation complexity and fault rates.
Memory Hook
💡 Imagine FIFO as a queue line, LRU as a 'last touched' list, and Optimal as a perfect oracle predicting future needs.
Illustrative Code
def fifo_page_replacement(pages, capacity):
queue = [] # Queue to store pages in FIFO order
page_set = set() # Set for O(1) lookup
page_faults = 0
for page in pages:
if page not in page_set:
page_faults += 1
if len(queue) == capacity:
removed = queue.pop(0) # Remove oldest page
page_set.remove(removed)
queue.append(page)
page_set.add(page)
return page_faults
def lru_page_replacement(pages, capacity):
page_faults = 0
page_map = {} # Map page to its last used index
pages_in_memory = set()
for i, page in enumerate(pages):
if page not in pages_in_memory:
page_faults += 1
if len(pages_in_memory) == capacity:
# Evict least recently used page
lru_page = min(page_map, key=page_map.get)
pages_in_memory.remove(lru_page)
del page_map[lru_page]
pages_in_memory.add(page)
page_map[page] = i # Update last used index
return page_faults
def optimal_page_replacement(pages, capacity):
page_faults = 0
pages_in_memory = set()
for i in range(len(pages)):
page = pages[i]
if page not in pages_in_memory:
page_faults += 1
if len(pages_in_memory) == capacity:
# Find page with farthest future use
farthest = -1
page_to_remove = None
for p in pages_in_memory:
try:
next_use = pages[i+1:].index(p)
except ValueError:
next_use = float('inf')
if next_use > farthest:
farthest = next_use
page_to_remove = p
pages_in_memory.remove(page_to_remove)
pages_in_memory.add(page)
return page_faults