Operating Systems 2015F Lecture 18

Video

The video from the lecture given on November 13, 2015 is now available.

Notes

Lecture 18
----------

Virtual Memory

swapping, er...paging

Swapping technically means writing currently running program to disk and loading another one to run

Paging means moving pages out of RAM and onto disk

Question: why does linux use much more than the bare minimum of RAM?  What is it doing with all of that extra memory?

Answer: very aggressive caching of disk contents

Problem: But what if I need more RAM for programs?

Need algorithms for moving pages between RAM and disk

Types of page contents:
* Program data
* Program code
* File contents

Note that program code is also (read only) file contents

Really, you have:
1. File contents, read only
2. File contents, read write
3. Program data

You need more RAM.  What do you kick out first?
 - not such an easy question!

Kick out (evict) read only file contents first
Pro: we don't have to write anything to disk!
Con: Hey, I was running that code!

Evict read write file contents
Pro: hey they are supposed to go to disk anyway, go ahead and write it
Con: but we have to wait for it to be written first

Evict program data...to swap
Pro: Hey, we didn't need that data anyway
Con: Hey, we *did* need that data!


Hardware helps with the decision on what pages can be kicked out
* accessed bit
* dirty bit

Ideal eviction targets are pages with accessed bit clear and dirty bit clear (a clean, non-accessed page)

Next eviction target is non-accessed dirty pages.  Save them to disk then evict

After evict accessed but clean pages...but this is bad if done frequently (system is "thrashing")

Dirty pages are easy - just have a process constantly writing dirty pages to disk, thus "cleaning" them
  - sweeps through memory periodically looking for dirty pages

Ideally what you'd want is a timestamp of last access for every page

For accessed bits, periodically sweep through memory setting accessed bits to 0.  If it is 1, then you know the page has been accessed since the last sweep.

These "sweep" type algorithms are called clock algorithms because you can think of the pages as positions on a very very big clock, with a hand moving from one to the next.

Page replacement algorithms can get very complex because, in their ideal form, they predict the future.  Best approximation is a bunch of heuristics and adaptive mechanisms based on past behavior.

But page replacement needs to be reasonable, especially on systems with no swap


When a program asks for memory, how do you know if you have enough?  When do you say no?

Conservative way: find pages for every byte requested, return yes only once you've allocated it all

Linux kernel is not conservative at all

Example: fork
 - logically, doubles RAM usage
 - at least, doubles program data RAM usage
 - but in practice it generally only causes a modest increase in RAM usage

Example: malloc
 - are you really going to use all that memory at once?

Linux kernel memory allocation is like banking
 - gives out loans at a drop of the hat, takes deposits...
 - assumes everyone won't want their money at once