程序代写代做 data structure android kernel cache Space Allocation, Virtual Memory

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