Skip to content
Tutorials Center
My learning

Topics

Lesson 174 of 225 ยท Greedy Algorithms

Greedy in Operating Systems: Memory Fit, SJF and Page Replacement

See greedy ideas inside an operating system: first, best and worst fit memory allocation, shortest job first scheduling, and FIFO, LRU and optimal page replacement.

An operating system makes small decisions millions of times a second: where to put a new block of memory, which process to run next, which page to throw out of RAM. Each decision must be fast and made with incomplete information, which is exactly the situation greedy algorithms are built for. This lesson simulates three of these decisions in Python, so you can compare strategies side by side.

You will see that some of these greedy rules are provably the best possible (shortest job first for average waiting time, and the "optimal" page replacement rule), some are practical heuristics with known weaknesses (first fit, best fit, worst fit), and some look sensible but even behave strangely (FIFO page replacement and Belady's anomaly). Knowing which is which is the real lesson.

Memory allocation: first, best and worst fit

Memory is a row of free blocks of different sizes. A request arrives for some number of units. The allocator must pick a free block that is big enough and carve the request from it. Three greedy rules decide which block:

  • First fit: the first block, scanning from the start, that is large enough. Fast, since it stops early.
  • Best fit: the smallest block that is large enough. It leaves the least waste per request, but tends to leave many tiny, useless slivers.
  • Worst fit: the largest block. The idea is that the leftover stays big enough to be useful.
TEXT
free blocks: [100, 500, 200, 300, 600]
requests:    212, 417, 112, 426

Run all three on the same input in the next TryIt. The function returns which block index (counting from 0) each request got, or None if no block could hold it, and the free space left in each block afterwards.

Python First, best and worst fit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On this input, first fit and worst fit fail the last request, while best fit places all four. That does not make best fit the universal winner: another input flips the result. No fit strategy is optimal for every sequence, because the allocator cannot see future requests. In practice allocators combine the idea with free lists sorted by size, and best fit is a common default.

Time per request is O(n) with a plain scan over n blocks. A balanced tree keyed by size makes best fit O(log n).

Shortest job first (SJF)

A CPU has a queue of processes, and each has a known burst time (how long it will run). Processes run one at a time, to completion. The waiting time of a process is how long it sits in the queue before it starts. You want the lowest average waiting time.

Greedy rule: run the shortest job first.

Why is that optimal? Each job delays every job behind it by its own length. A long job placed early multiplies its length by the number of jobs waiting. Take any schedule where a longer job runs right before a shorter one. Swapping them makes the shorter job's delay smaller for everyone behind and costs the longer job only the shorter job's length. The total never goes up, so repeated swaps lead to sorted order. This is the exchange argument from greedy in a very clean form.

Python Shortest job first beats arrival order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorted order matches the best of all 24 orders. The catch in real systems is that the OS does not know burst times in advance; it estimates them from recent behavior, and SJF can starve long jobs when short ones keep arriving.

If jobs arrive over time, the rule becomes: whenever the CPU is free, pick the shortest job among those that have already arrived. A min-heap makes that efficient.

Python SJF with arrival times and a heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Job A starts at time 0 because nothing else has arrived. When it finishes at 7, the ready queue holds B (4), C (1), D (4), so C goes first, then B and D. Time is O(n log n).

Page replacement

RAM holds a limited number of frames. When a program touches a page that is not in memory, that is a page fault, and if all frames are full the OS must evict a page. Fewer faults means a faster program. Each policy is a different greedy rule for choosing the victim:

  • FIFO: evict the page that has been in memory the longest.
  • LRU (least recently used): evict the page unused for the longest time. It bets that the past predicts the future.
  • Optimal (Belady's): evict the page whose next use is farthest in the future (or that never comes). This is provably the minimum number of faults, but it needs to see the future, so real systems cannot use it. It serves as a yardstick.
Python Counting page faults for FIFO, LRU and optimal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Optimal wins with 9 faults, LRU is next with 12, and FIFO is last with 15. The ordering optimal <= LRU is typical, because LRU approximates "farthest in the future" by "farthest in the past".

Belady's anomaly

More memory should mean fewer faults. For LRU and optimal, it always does. For FIFO it can go the wrong way: adding a frame can increase the faults.

Python Belady's anomaly with FIFO

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Three frames cause 9 faults, but four frames cause 10. FIFO ignores how useful a page is, so with more frames it sometimes holds the wrong pages for longer. LRU and optimal are stack algorithms: the set of pages held with k frames is always a subset of the set held with k + 1 frames, which rules out the anomaly.

LRU needs bookkeeping on every memory access, which is too slow in hardware. Real systems use cheap approximations such as the clock algorithm (a circle of pages with a "recently used" bit) that behave much like LRU.

Common mistakes

  • Expecting one fit strategy to win always. Allocators cannot see future requests, so any of first, best or worst fit can lose on some inputs.
  • Forgetting arrival times in SJF. Pick the shortest among jobs that have already arrived, not the shortest of all, and jump the clock forward when the queue is empty.
  • Treating optimal page replacement as a real policy. It needs future knowledge. Use it only to measure how close another policy gets.
  • Assuming more frames never hurts. FIFO can do worse with more memory; test it, do not assume.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which rule does best fit use for a memory request?

    Best fit leaves the least unused space in the chosen block, though it can create many tiny leftovers.
  2. 2. Why does shortest job first minimize the average waiting time?

    A swap argument shows each adjacent out-of-order pair can be improved without making anything else worse.
  3. 3. Which page does the optimal policy evict?

    That page is needed last, so evicting it postpones the next fault as long as possible. It requires knowing the future.
  4. 4. What is Belady's anomaly?

    For some reference strings FIFO suffers more faults with four frames than with three. Stack algorithms like LRU cannot.
  5. 5. What should non-preemptive SJF do when no job has arrived yet at the current time?

    The CPU idles until the next job arrives, so the simulation moves the clock forward to that arrival time.

Summary

  • Operating systems use greedy rules for fast, local decisions with limited information.
  • First, best and worst fit allocate memory by scanning for a block; none is optimal for every input.
  • Shortest job first minimizes average waiting time, provable with an exchange argument; with arrivals, use a min-heap of ready jobs.
  • Page replacement: FIFO evicts the oldest page, LRU the least recently used, and optimal the page used farthest in the future (a yardstick, not a real policy).
  • FIFO can show Belady's anomaly (more frames, more faults); LRU and optimal cannot.

Next: Greedy vs Dynamic Programming