FrançaisGet started

Page replacement

What to do when memory is full: FIFO, LRU, clock and optimal, Belady's anomaly, swap space and thrashing.

  • 24 cards
  • 4 topics
  • Free
Study this deck

The outline, topic by topic

Each topic is weighted the way the exam weighs it.

  1. Concepts
  2. Questions
  3. The numbers
  4. Scenarios

A few cards from the deck

  • Swap space: what is it?

    Show the answer

    An area of disk reserved for the kernel, where it stores process pages it removed from physical memory for lack of room.

    An evicted page is written there if it was modified; that is where the kernel reads it back at the next page fault. A page never modified can simply be dropped, its content already exists on disk.

  • Three frames are full; pages 1, 2 and 3 were loaded in that order, then the following references arrived: 1, 4. Page 4 is missing and a frame must be freed. Which page do FIFO, then LRU, evict?

    • FIFO removes 1, LRU removes 2
    • FIFO removes 1, LRU removes 1
    • FIFO removes 3, LRU removes 2
    • FIFO removes 2, LRU removes 3
    Show the answer

    FIFO removes 1, LRU removes 2

    FIFO looks at load age: 1 is the oldest, even if it was just read. LRU looks at the last access: 1 was just used, so the least recent is 2.

  • A … page is the page the algorithm chooses to remove from memory to free a frame; if it was modified, it is first written to the ….

    Show the answer

    A victim page is the page the algorithm chooses to remove from memory to free a frame; if it was modified, it is first written to the swap space.

    A dirty bit, set to 1 by the hardware on each write, avoids writing unchanged pages back to disk: evicting an unmodified page costs no write at all.

  • FIFO replacement: what is it?

    Show the answer

    The algorithm that removes the page that has been in memory the longest, regardless of how much it has been used.

    It is simple (a queue) but may evict a heavily used page just because it is old. It can suffer Belady's anomaly, like the clock, whereas LRU and optimal are immune.

  • A machine stops responding. vmstat 1 shows si and so columns at several thousand (KiB per second), wa at 90 and id almost 0. What is happening, and what should be done?

    • Thrashing: memory is short, stop processes or add memory
    • The processor is saturated: a faster processor is needed
    • The disk is too slow: the swap space needs enlarging
    • A process leaks descriptors: the limit needs raising
    Show the answer

    Thrashing: memory is short, stop processes or add memory

    si and so measure the memory read back from swap and written to it each second, wa the time spent waiting on disk: the processor waits for pages instead of computing. Enlarging swap would only delay the saturation without reducing the back-and-forth.

Study this deck