Grant Novota
About Projects Peaks Blog Links Resume

Frame Allocation

22 Jul 2019

Techniques to Improve Page Replacement Performance

  1. Use a dirty/modify bit to reduce disk writes.
  2. Choose a smart page replacement algorithm
    • Keeps the most important pages in memory and evicts the least important.
  3. Make the search for the least important page be fast.
  4. Page-buffering
    • Read in a frame first and start executing, then select a victime and write it out at a later time - faster perceived performance.
    • Periodically write out all modified frames to disk when there is no other activity - most frames are clean so there will be few disk writes on a page fault.
  5. Keep a pool of free frames and remember their content.
    • Reuse this free frame if the same contents are needed again. This reduces disk reads.
  6. Allocate the appropriate # of frames so a process avoids thrashing.

Allocation of Memory Frames

Given that the OS employs paging for memory management, then physical memory is divided into fixed-size frames or pages.

How many frames does each process get allocated?

How many frames does the OS get allocated versus user processes?

Memory Allocation Policies

  1. Minimum # frames:
    • Determine the minimum # of frames that allow a process to allocate. Ideally, this is just one page, i.e. the page in which the program counter is currently executing. Or one for code and one for data.
    • In practice, some CPU’s support complex instructions.
    • Multi-address instructions. Each address could belong to a different page. * There can be multiple levels of indirection in addressing, i.e. pointers.
    • Each such level of indirection could result in a different page being accessed in order to execute the current instruction. Up to N levels of indirection may be supported, which means may need up to N pages as the minimum.
  2. Equal allocation:
    • Split m frames equally among n processes
    • m/n frames per process.
    • Problem: This doesn’t account for size of processes, e.g. a large database process versus a small client process whose size is « m/n
    • Needs to be adaptive as new processes enter and the value of n fluctuates.
  3. Proportional allocation:
    • Allocate the number of frames relative to the size of each process
    • Let S_i = size of process P_i
    • S = the sum of all the S_i
    • Allocate a_i = (S_i/S) * m frames to process P_i
    • Proportion a_i can vary as new processes start and existing processes finish.
    • Also, if size is based on the code size, or address space size, then that is not necessarily the number of pages that will be used by a process.

Local vs. Global Allocation/Replacement

In local allocation/page replacement, a process is assigned a fiexed set of N memory pages for the liefetime of the process. When a page needs to be replaced, it is chosen only from this set of N pages. This is easy to manage and processes are isolated from each other (kinda). Windows NT follows this model.

Problems with local allocation:

  1. The behavior of processes may change as they execute.
    • Sometimes they’ll need more memory, sometimes less.
    • Local replacement doesn’t allow a process to take advantage of unused pages in another process.
    • Want a more adaptive alloation strategy that would allow a page fault to trigger the page replacement algorithm to increase its page allocation.
  2. Local replacement would seem to isolate a process’s paging behavior from other processes.
    • Amount of memory allocated to each process is fixed.
    • If a process P1 page faults frequently, then P1 will queue up many requests to read/write from/to disk.
    • If another process P2 needs to access the disk, e.g. to page fault, then even if P2 page faults less frequently, P2 will still be slowed down by P1’s many queued up reads and writes to disk.

Global allocation and page replacement:

  • Pool all pages from all processes together.
  • When a page needs to be replaced/evicted, choose it from the global pool of pages.
  • Linux follows this model.
  • Global allocation and page replacement allows the # of pages allocated to a process to fluctuate dramatically.
    • Good: system adapts to let a process utilize “unused’ pages of another process, leading to better memory utilization overall and better system throughput.
    • Bad: a process cannot control its own page fault rate under global replacement because other processes will take its allocated frames, potentially increasing its own page fault rate.
Top