Operating Systems 2019F Lecture 19

Video

The video from the lecture given on November 16, 2019 is now available.

Notes

Lecture 19
----------

 - remember module
 - virtual memory (again)
 - /dev/describe (if time)

Key functions: alloc_pages, page_address

Remember that the kernel allocates memory in pages (fixed-sized chunks of memory), normally 4K or 8K in size (although you can have 2M pages or larger).

These pages are allocated as *physical* pages.
 - there is only one physical address space shared by everything on a system

This is a pain because physical addresses are shared across all processes
Each process (and the kernel) wants its own range of contiguous addresses
 - virtual addresses allow everyone to have their own view of memory
 - allows pages put all over the place to be connected together, so processes
   see no gaps

So each process has its own virtual->physical address mapping, as does the kernel (one for the kernel)
 - these mappings are called page tables

alloc_pages()
 - returns pages contiguous in physical memory
 - first argument is the priority (e.g., GFP_KERNEL)
 - second argument is the "order" of the allocation x
     order x = 2^x pages to allocate
   so order=0 means allocate one page
      order=4 means allocate 16 pages (2^4)

 - you allocate pages this way in order to reduce fragmentation
   - note each order is twice as much as the one previous, so you can get
     2 x-1 order allocations out of 1 x order allocation


The resident memory (RES) of a process is generally much smaller than the total virtual memory (VIRT) of a process.  This is because:
 - some pages may be swapped out to disk (data structures that aren't being accessed)
 - some pages may still be on disk (part of the executable)
 - memory that hasn't been allocated
   - the Linux kernel is lazy about memory allocation

If you allocate 1G of memory for a process, that doesn't mean it gets
1G of physical memory.  You'll only get that memory when you use it, and if the kernel can get away with not allocating it to your process, it won't!

One downside of this is memory can get overcommited.
 - just like a credit card, you can "spend" too much
 - and if the bill collector comes by, you may go bankrupt

working set = part of program needed to "make progess"
 - all of the working set must be in RAM (physical memory) for program to run at full speed
 - if you can't fit the working set of all running processes in RAM, system
   will slow down, potentially dramatically
 - on mobile devices, there is no swap, so it will just terminate processes
   when memory gets tight

What sort of algorithm do you use to decide what pages stay in memory? On what basis?

Ideally, you want to just keep the pages around that are needed for the future.
But, that would require you knowing the future.

So normally we assume the past is like the future, and so we want to throw out pages that were the least recently used (LRU)

But pure LRU is expensive, because it requires storing a timestamp for every page that is updated on every page access.

We replace that timestamp with a bit.

page replacement is normally done using a clock algorithm
  - a "hand" sweeps through all of memory, setting the access bit to 0
  - the access bit is set to 1 when a page is accessed
  - so, if a page has a 1, it has been used sometime since the last "sweep"
  - if the sweeps happen every 1 second, then we know page access times down to
    one second
  - in other words, we're roughly simulating a clock

So page replacement algorithms then just look for the pages with a 0 bit and chooses one of them to throw out.

But, also have to take into account pages that have been modified (the dirty bit)

Pages of an executable are read-only and have a backup on disk (in the executable)
Pages of data structures are read/write and have no backup unless written to swap.

 - so, prefer to throw out executable pages rather than data pages
 - write data pages to swap if we have to so they can also be kicked out