Space Allocation, Virtual Memory
1
Today’s topics
Kernel memory Space allocation Virtual memory
2
12
What about the kernel itself?
bound virtual address >
+ base
physical address
What happens when OS is running? OS runs with relocation turned off (a
bit in processor status word (PSW) controls relocation)
How to prevent users from controlling base & bound, relocation?
Does kernel need multiple address spaces?
error
How does OS regain control? Need to atomically
Branch into/out of OS
Turn relocation on/off
3
Today’s topics
Kernel memory Space allocation Virtual memory
7
37
A System’s View
A System’s View (cont’d)
21 22
[lec13] Sharing main memory
Simple multiprogramming – 4 drawbacks Lack of protection
Cannot relocate dynamically
dynamic memory relocation: base&bound Single segment per process
dynamic memory relocation: segmentation, paging
Entire address space needs to fit in mem More need for swapping
Need to swap whole, very expensive!
23
The last drawback
So far we’ve separated the process’s view of memory from the OS’s view using a mapping mechanism
Each sees a different organization
Allows OS to shuffle processes around
Simplifies memory sharing
What is the essence of the mechanism that enables this?
But, a user process had to be completely loaded into memory before it could run
Wasteful since a process only needs a small amount of its total memory at any time (reference locality!) 24
23 24
http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/
http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/
Virtual Memory
Definition: Virtual memory permits a process to run with only some of its virtual address space loaded into physical memory
Key idea: Virtual address space translated to either Physical memory (small, fast) or
Disk (backing store), large but slow
Deep thinking – what made above possible?
Objective:
To produce the illusion of memory as big as necessary 25
Virtual Memory
“To produce the illusion of memory as big as necessary”
Without suffering a huge slowdown of execution
What makes this possible?
Principle of locality
Knuth’s estimate of 90% of the time in 10% of the code There is also significant locality in data references
Temporal locality
Spatial locality
26
25 26
Virtual Memory Implementation
Virtual memory is typically implemented via demand paging
demand paging:
Load memory pages (from storage) “on demand” paging with swapping, e.g., physical pages are
swapped in and out of memory
Swapping is an optional (yet common) OS feature
Side note: Android low mem killer
27
Demand Paging
(paging with swapping)
If not all of a program is loaded when running, what happens when referencing a byte not loaded yet?
What does “referencing” mean?
How to detect this? In software?
CPU
virtual address
physical address
Translation (MMU)
Physical memory
I/O device
28
27 28
Demand Paging
(paging with swapping)
If not all of a program is loaded when running, what happens when referencing a byte not loaded yet?
Hardware/software cooperate to make things work
Extend PTEs with an extra bit “present” (valid bit)
Any page not in main memory right now has the
“present” bit cleared in its PTE
If “present” isn’t set, a reference to the page results in
a trap by the paging hardware, called page fault What needs to happen when page fault occurs?
29
x86 Page Table Entry
Pageframenumber U P CwGl L D A CdWt O W V
31 12 Reserved
Valid (present) Read/write
Owner (user/kernel) Write-through
Cache disabled Accessed (referenced) Dirty
PDE maps 4MB Global
30
29 30
What is happening before and after malloc()?
Before malloc()?
After malloc()?
Upon first access?
How to capture the first write to a virtual page? e.g. want to trap into page fault handler
Use valid bit
In handler, check if vpage is allocated (and access
permitted)
If not, segmentation fault
Else allocate physical page
31
Page Fault Handling in Demand Paging
mem ref
Inst seq.
fault
Load M
vi
vi
Page Table (TLB)
physical pages
VM subsystem
32
31 32
Page fault handling (cont)
On a page fault
Find an unused phys page or a used phys page (how?)
If the phys page is used
If it has been modified (how to know?), write it to disk
Invalidate its current PTE and TLB entry (how?)
Load the new page from disk
Update the faulting PTE and its TLB entry
Restart the faulting instruction
Supporting data structure
For speed: A list of unused physical pages (more later)
Data structure to map a phy. page to its pid(s) and virtual
address(es)
Why need this? Sounds familiar?
33
33