6-10 Flashcards
(157 cards)
1
Q
What is memory virtualization?
(3)…
A
- OS virtualizes its physical memory
- OS provides an illusion of memory space per each process
- It is as if each process can access the entire memory space
2
Q
Memory virtualization benefits:
(3)…
A
• Ease of use in programming
• Memory efficiency in terms of time and space
• The guarantee of isolation for processes as well as OS
- Protection from errant accesses of other processes
3
Q
Early OSes:
• Load __ in memory
- Poor utilization and efficiency
A
only one process
4
Q
Multiprogramming and Time Sharing: Load multiple processes in memory: (3)... Causes an important protection issue: ...
A
- Execute one for a short while
- Switch processes between them in memory
- Increase utilization and efficiency;
• Errant memory accesses from other processes
5
Q
Address Space:
The OS creates an __ of physical memory
A
• The address space contains all the information about a running process
- program code, heap, stack and etc.
6
Q
Address Space: Code: (1)... Heap: (1)... Stack: (2)...
A
1. Code • Where instructions live 2. Heap • Dynamically allocate memory - malloc in C - new in Java 3. Stack • Store return addresses or values • Contain local variables and arguments to functions
7
Q
Virtual Address:
Every address in a running program is __.
OS translates the __ to __.
A
virtual;
virtual address;
physical address
—
#include [LTS]stdio.h>
#include [LTS]stdlib.h>
// Compile with: gcc -Og -no-pie -o print_address print_address.c
int main(int argc, char *argv[]){
int x = 3; // allocated on the stack frame of main()
printf(“location of code : %p\n”, (void *) main);
printf(“location of heap : %p\n”, (void *) malloc(1));
printf(“location of stack : %p\n”, (void *) &x);
return x; // so compiler doesn’t optimize x away
}
• The output in 64-bit Linux machine:
9/23/2019 CMPU 335 – Operating Systems 8
location of code : 0x4005c7
location of heap : 0x1623670
location of stack : 0x7fff633fbe54
8
Q
Memory Virtualization Overview:
(4)…
A
• Just like the CPU, memory is virtualized
• Every address generated by a user program is a virtual address
• Virtual memory provides the illusion of a large private address space to
programs
- For instructions and data
• The OS, with help from the hardware translates each virtual memory
address to an actual physical address
- Protects and isolates processes from each other
- And from the kernel
9
Q
Memory Virtualizing with Efficiency and Control:
In memory virtualizing, efficiency and control are attained by __.
A
• E.g., registers, TLB (Translation Look-aside Buffer)s, page-table
• Control means no process is allowed to access any memory but its own
10
Q
Address Translation:
Mechanism: __
• Hardware transforms __
• The desired information is actually stored in a __
A
hardware-based address translation;
a virtual address to a physical address;
physical address
11
Q
The OS must get involved at key points to set up the hardware
• The OS manages __
• Keeps track of __
A
memory;
which locations are free and which are in use
12
Q
Example: Address Translation
void func() int x = 3000; x = x + 3; // this is the line of code we are interested in ...
(3)…
A
- Load a value from memory
- Increment it by three
- Store the value back into memory
13
Q
Example: Address Translation
void func() int x = 3000; x = x + 3; // this is the line of code we are interested in
Assembly:
…
A
128 : movl 0x0(%ebx), %eax ; load 0+ebx into eax
132 : addl $0x03, %eax ; add 3 to eax register
135 : movl %eax, 0x0(%ebx) ; store eax back to mem
• Presume that the address of ‘x’ has been place in ebx register
• Load the value at that address into eax register
• Add 3 to eax register
• Store the value in eax back into memory
—
5 memory references just to add 3 to a number!:
• Fetch instruction at address 128
• Execute this instruction (load from address 15KB)
• Fetch instruction at address 132
• Execute this instruction (no memory reference)
• Fetch the instruction at address 135
• Execute this instruction (store to address 15 KB)
14
Q
- Base and bounds also called __
* Bounds register also called __
A
dynamic relocation;
limit register
15
Q
Dynamic (Hardware base) Relocation:
When a program starts running, the OS decides __.
• Sets the base register accordingly
𝑝ℎ𝑦si𝑐𝑎𝑙 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 = __
• Every virtual address must not be greater than __
A
where in physical memory a process should be loaded;
𝑣𝑖𝑟𝑡𝑢𝑎𝑙 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 + 𝑏𝑎𝑠e;
bound and negative:
0 ≤ 𝑣𝑖𝑟𝑡𝑢𝑎𝑙 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 < 𝑏𝑜𝑢𝑛𝑑s
16
Q
Relocation and Address Translation:
128 : movl 0x0(%ebx), %eax
(2)…
A
• Fetch instruction at address 128 (virtual address):
32896 = 128 + 32𝐾𝐵(𝑏𝑎𝑠𝑒)
• Execute this instruction
- Load from address 15KB (virtual address)
47𝐾𝐵 = 15𝐾𝐵 + 32𝐾𝐵(𝑏𝑎𝑠𝑒)
17
Q
Two ways to check Bounds:
(2)…
A
- Either hold the size of the address space or the physical address of the end of the address space
- Depends on whether you bounds check before or after translation
18
Q
The OS must take action to implement base-and-bounds approach
• Three critical junctures:
(3)…
A
• When a process starts running:
- Finding space for address space in physical memory
• When a process is terminated:
- Reclaiming the memory for use
• When context switch occurs:
- Saving and storing the base-and-bounds pair
19
Q
OS Issues: When a Process Starts Running
- The OS must find __
- free list : __
A
a room for a new address space;
A list of the range of the physical memory which are not in use
20
Q
OS Issues: When a Process Is Terminated
• The OS must __
A
put the memory back on the free list
21
Q
OS Issues: When Context Switch Occurs:
• The OS must __
- In __
A
save and restore the base-and-bounds pair;
process structure or process control block (PCB)
22
Q
Address Translation Overview:
- Extend limited direct execution with address translation
(1) … - Hardware support is necessary
(2) … - Base and bounds is efficient and offers protection
(2) …
A
- Extend limited direct execution with address translation
• Can control each and every memory access from a process - Hardware support is necessary
• Process has no idea memory references are being translated
• Part of the memory management unit (MMU) of a processor - Base and bounds is efficient and offers protection
• Suffers from internal fragmentation due to fixed-sized slots
• This leads us to segmentation, a generalization of base and bounds
23
Q
Inefficiency of the Base and Bound Approach:
(3)…
A
- Big chunk of “free” space
- “free” space takes up physical memory
- Hard to run when an address space does not fit into physical memory
24
Q
Segment is just a __.
A
contiguous portion of the address space of a particular length
• Logically-different segments: code, stack, heap
25
Each segment can be placed in __
| • __ exist per each segment
different parts of physical memory;
| Base and bounds
26
Address Translation on Segmentation:
𝑝ℎ𝑦𝑠𝑖𝑐𝑎𝑙 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 = __
• The offset of virtual address 100 is __
- The code segment starts at __
𝑜𝑓𝑓𝑠𝑒𝑡 + 𝑏𝑎𝑠e;
100;
virtual address 0 in address space
27
The offset of virtual address 4200 is (4200 – 4096) = 104
| • The heap segment starts at virtual address __ in address space
4096
28
Referring to Segment:
Explicit approach:
__
• Divide the address space into segments based on the top few bits of virtual address
29
Segmentation Fault or Violation:
| ...
• If an illegal address such as 7KB which is beyond the end of heap is referenced, the OS occurs segmentation fault
- The hardware detects that address is out of bounds
30
Referring to Stack Segment:
```
• Stack grows backward
• Extra hardware support is needed
- The hardware checks which way the segment grows
- 1 positive direction
- 0 negative direction
```
• To calculate negative offset
- Get virtual address segment offset (offset bits from addr.)
- Subtract offset from maximum segment size to get negative offset
- Subtract negative offset from base to get physical address
31
Support for Sharing:
Segments can be shared between __
(2)...
address spaces
• Code sharing is still in use in systems today
• With extra hardware support
32
Extra hardware support adds __
| • A few more bits per segment to indicate __
protection bits;
| permissions of read, write, and execute
33
Coarse-Grained means __
| • e.g., __
segmentation in a small number;
| code, heap, stack
34
Fine-Grained segmentation allows more __.
| (2)...
flexibility for address space in some early systems
---
• To support many segments, hardware support with a segment table (kept in memory) is required
• OS could better learn which segments are in use to utilize memory efficiently
35
External Fragmentation:
__.
(2)...
little holes of free space in physical memory that make it difficult to allocate new segments
• There are 24KB free, but not in one contiguous segment
• The OS cannot satisfy the 20KB request
36
Compaction:
__.
(3)...
```
rearranging the exiting segments in physical memory
• Compaction is costly
- Stop running process
- Copy data to somewhere
- Change segment register value
```
37
Segmentation Summary
| (5)...
• Allows for dynamic relocation
• Better support for large address spaces
- Avoids internal fragmentation
• Segmentation is fast
- Well suited to hardware
- Base and bound registers for each segment
- Optional protection bits for each segment
• External fragmentation is still a major concern
• Still not flexible enough
- E.g., large but sparsely-used heap
38
Concept of Paging:
| Paging...
splits up the virtual address space into fixed-sized units called pages
• Compare to segmentation: variable size of logical segments(code, stack, heap, etc.)
39
Concept of Paging: Physical memory is also split into some number of pages called a __.
• Virtual pages and page frames are __ size
page frame;
| all the same
40
Paging Advantages:
| (2)...
1. Flexibility
• Supports the abstraction of address effectively
• No assumptions on how the heap and stack are used
2. Simplicity
• The page in the address space and the page frame are the same size
• Ease of free-space management
• Easy to allocate and keep a free list
41
Paging Advantages:
| (2)...
1. Flexibility
• Supports the abstraction of address effectively
• No assumptions on how the heap and stack are used
2. Simplicity
• The page in the address space and the page frame are the same size
• Ease of free-space management
• Easy to allocate and keep a free list
42
Paging Example:
| (3)...
* 128-byte physical memory with 16 bytes page frames
* 64-byte address space with 16 bytes pages
* Page table maps virtual pages to physical pages - Per process data structure that maps virtual pages to physical pages
43
Address Translation:
Two components in the virtual address:
(2)...
* VPN: virtual page number
| * Offset: offset within the page
44
What Is In The Page Table?:
The page table is __.
• Simplest form: __.
just a data structure that is used to map the virtual address to physical address;
a linear page table, an array
45
What Is In The Page Table?:
The OS indexes the array by __ and looks up the __.
In addition to the Physical Frame Number, each page table entry has some __.
VPN;
page table entry;
status flags
46
Common Page Table Entry Flags:
| (5)...
* Valid Bit: Indicating whether the particular translation is valid
* Protection Bits: Indicating whether the page could be read from, written to, or executed from
* Present Bit: Indicating whether this page is in physical memory or on disk (swapped out)
* Dirty Bit: Indicating whether the page has been modified since it was brought into memory
* Reference Bit (Accessed Bit): Indicating that a page has been accessed
47
Valid Bit
Indicating whether the particular translation is valid
48
Protection Bits
Indicating whether the page could be read from, written to, or executed from
49
Present Bit
Indicating whether this page is in physical memory or on disk (swapped out)
50
Dirty Bit
Indicating whether the page has been modified since it was brought into memory
51
Reference Bit (Accessed Bit)
Indicating that a page has been accessed
52
```
Example: x86 Page Table Entry
• P: __
• R/W: __
• U/S: __
• A: __
• D: __
• G, PAT, PCD, PWT: __
• PFN: __
```
* P: present
* R/W: read/write bit
* U/S: supervisor
* A: accessed bit
* D: dirty bit
* G, PAT, PCD, PWT: Used for caching
* PFN: the page frame number
53
A Memory Trace:
• Example: A Simple Memory Access
int array[1000];
...
for (i = 0; i < 1000; i++)
array[i] = 0;
• Compile and execute:
gcc –o array array.c –Wall –o
./array
• Resulting Assembly code:
...
```
# i in %eax
# array in %edi
0x1024 movl $0x0,(%edi,%eax,4)
0x1028 incl %eax
0x102c cmpl $1000,%eax
0x1030 jne 0x1024
```
54
Paging: Too Slow:
• To find a location of the desired PTE, the __ is needed
• For every memory reference, paging requires the OS to perform __
• How do we speed up memory access?
- __
• Next up: Introducing the TLB (Translation Lookaside Buffer)
- A purpose-built cache for page table lookups
starting location of the page table;
one extra memory reference;
Caching to the rescue!
55
Faster Translations:
Paging can lead to high performance overheads:
...
• Every memory access needs to read an entry in the page table
- Stored in memory!
- Doubles the number of memory accesses in the system!
56
• Need to make page table lookups go faster. What techniques have we seen before to speed up memory access?
(2)...
1. Caching to the rescue!
| 2. Smaller and faster memory that holds a portion of the page table for a process
57
Making page table access is so important to overall system performance that a dedicated purpose-built cache is used:
(2)...
* Called Translation Lookaside Buffer (TLB) for historic reasons
* A better name would be address-translation cache
58
TLB:
| (2)...
* Part of the chip’s memory-management unit(MMU)
| * A hardware cache of popular virtual-to-physical address translation
59
Accessing An Array:
| (3)...
```
• 10 4-byte integers starting at virtual address 100
• 8-bit virtual address space
• 16 byte pages
- 4-bits offset
- 4-bits VPN
```
60
Temporal Locality
An instruction or data item that has been recently accessed will likely be reaccessed soon in the future
61
Spatial Locality
If a program accesses memory at address x, it will likely soon access memory near x
62
Who Handles The TLB Miss?
| (2)...
1. Hardware handles the TLB miss entirely (e.g., X86)
| 2. OS handles the TLB miss (e.g., ARM)
63
Hardware handles the TLB miss entirely (e.g., X86)
| (4)...
* Known as a hardware-managed TLB
* The hardware knows exactly where the page tables are located in memory
* The hardware finds the correct page-table entry, and extracts the desired translation
* Updates TLB and retries the instruction
64
OS handles the TLB miss (e.g., ARM)
| (2)...
• Known as a software-managed TLB
• On a TLB miss, the hardware raises exception (trap handler)
- Code within the OS that is written with the express purpose of handling TLB miss
- Can be a more flexible solution
65
TLB is typically __
Fully Associative
---
Entries can go anywhere in the TLB
66
A typical TLB might have _(3)_ entries
32, 64, or 128
---
• Hardware searches the entire TLB in parallel to find the desired translation
• Other bits: valid bits, protection bits, address-space identifier, dirty bit
67
Address Space Identifier:
| Provides __ in the TLB
an address space identifier (ASID) field
68
Two processes share a page
| (3)...
* Process 1 is sharing physical page 101 with Process 2
* P1 maps this page into the 10th page of its address space
* P2 maps this page to the 50th page of its address space
69
Sharing of pages is useful as it __.
reduces the number of physical pages in use
70
TLB Replacement Policy:
| (3)...
1. Least Recently Used (LRU)
2. First In First Out (FIFO)
3. Random
71
TLB Replacement Policy:
Least Recently Used (LRU)
(3)...
* Evict an entry that has not recently been used
* Take advantage of locality in the memory-reference stream
* Requires keeping track of what was used when
72
TLB Replacement Policy:
First In First Out (FIFO)
(1)...
• Evicts the block that was accessed first
73
TLB Replacement Policy:
Random
(3)...
* Evict a random block
* Simple to implement
* Can avoid corner-cases (e.g., looping over n+1 pages with n TLB entries)
74
Hybrid Approach: Paging and Segments:
| (4)...
1. Use base and bounds registers to reduce the memory overhead of page tables
• Base holds the physical address of the page table of that segment
• Bounds register indicates the end of the page table (i.e., how many pages in segment)
2. Each process has three page tables associated with it
• When process is running, the base register for each segment contains the physical address of a linear page table for that segment
3. We still can have page table waste with a large but sparse heap
4. Arbitrary sized page tables can lead to external fragmentation
75
Multi-Level Page Table:
| (3)...
* Chop up the page table into pagesized units
* If an entire page of page-table entries is invalid, don’t allocate that page of the page table
* To track whether a page of the page table is valid, use a new structure, called page directory
76
A Detailed Multi-Level Example: Page Directory Index:
Divide the page table entries into pages:
(4)...
* Assume 4 byte page table entry
* Page size is 64 bytes
* Each page can hold 16 page table entries
* Need 16 pages to hold all the entries (256/16)
77
A Detailed Multi-Level Example: Page Directory Index:
Page Directory:
(3)...
* One Page Directory Entry (PDE) for each page of the page table
* Page Directory Index is 4-bits
* If a PDE is valid, there is a Page Table in memory
78
A Detailed Multi-Level Example: Page Table Index
• If the PDE is valid, we __.
- The Page Table Index is the __.
• If the PDE is not valid, we have __.
use the Page Table Index to get the PTE;
offset into the Page Table Pointed to by the PDE;
an illegal memory access
79
More than Two Level : Page Directory
* If our page directory has 2^14 entries, it spans not one page but __.
* To remedy this problem, we __.
128;
| build a further level of the tree, by splitting the page directory itself into multiple pages of the page directory
80
Multi-level Page Tables: Advantage & Disadvantage:
Advantages:
(2)...
* Only allocates page-table space in proportion to the amount of address space you are using
* The OS can grab the next free page when it needs to allocate or grow a page table
81
Multi-level Page Tables: Advantage & Disadvantage:
Disadvantages:
(2)...
* Multi-level table is a small example of a time-space trade-off
* Complexity
82
Inverted Page Tables:
| (3)...
1. Keeping a single page table that has an entry for each physical page of the system
• PID, VPN, Protection bits
2. The entry tells us which process is using this page, and which virtual page of that process maps to this physical page
3. Steps in translation:
1. Hash PID and VPN to get HAT index
2. Lookup a Physical Frame Number in the HAT
3. Look in the inverted page table entry to see if the PID and VPN match
4. If they don’t match, follow the pointer to the next link
83
Inverted Page Tables:
Steps in translation:
(4)...
Steps in translation:
1. Hash PID and VPN to get HAT index
2. Lookup a Physical Frame Number in the HAT
3. Look in the inverted page table entry to see if the PID and VPN match
4. If they don’t match, follow the pointer to the next link
84
Beyond Physical Memory: Mechanisms:
How can we maintain the illusion of a large virtual address space?:
(2)...
* Virtual address space can be much larger than physical memory
* Support multiprogramming
85
Beyond Physical Memory: Mechanisms:
Add a new level to our memory hierarchy:
(2)...
* A place for the OS to stash away portions of address space that currently aren’t in great demand
* In modern systems, this role is usually served by a hard disk drive
86
Swap Space:
| (2)...
* Reserve some space on the disk for moving pages back and forth
* OS reads and writes the swap space in page-sized units
87
Present Bit:
| (3)...
• Need some machinery higher up in the system in order to support swapping pages to and from the disk
• Add a present bit to the PTE
- When the hardware looks in the PTE, it may find that the page is not present in physical memory
• Accessing a page that is not in physical memory is known as a Page Fault
88
The Page Fault:
| A page fault occurs by __.
accessing a page that is not in physical memory
• If a page is not present and has been swapped disk, the OS needs to swap the page into memory in order to service the page fault
89
The Page Fault:
| How does the OS know where to look for the page on disk?
* Store the disk address in the PTE
| * While OS is fetching the page, the process is blocked (allowing another process to run)
90
The Page Fault:
| After the OS fetches the page from disk, __.
update the page table to mark page as present
• Update the PTE with the PFN of the page now in memory
• Optionally update the TLB
91
Swapping: What If Memory Is Full?:
| (3)...
• The OS needs to make room for the new page
• The process of picking one or more pages to swap out is known as page-replacement policy
• Getting this policy right is important to overall performance
- Hard drives are 10,000 to 100,000 times slower than memory!
92
Page Fault Control Flow Summary:
After a TLB miss:
(3)...
• Check present and valid bits of the PTE
- If valid bit is 0, seg fault
- If present bit is 1, grab the PFN from the PTE, place in TLB and restart the instruction
- If present bit is 0, page must be swapped in from disk (page fault)
93
Page Fault Control Flow Summary:
Servicing a Page Fault
(4)...
* Find an available physical frame for the soon-to-be-swapped-in page
* If there is not a physical frame available (physical memory is full) need to wait for page replacement algorithm to run and kick some pages out
* OS issues I/O request to read in page from swap space
* When I/O completes, update the page table and restart the instruction
94
Our current model of page replacement:
| (2)...
* OS waits until memory is entirely full and only then replaces a page to make room for some other page
* This is a little bit unrealistic, and there are many reasons for the OS to keep a small portion of memory free more proactively
95
When to start and stop evicting pages?:
| (3)...
* High Watermarks (HW) and Low Watermarks (LW)
* Fewer than LW available pages, a background process (Page Daemon) starts evicting pages
* Page Daemon stops when HW number of free pages are available
96
Swapping is the mechanism that allows us to __.
support accessing more memory than is physically present in the system
97
Swapping needs extra complexity in the page table:
| (2)...
* Present bit (is page in memory or not)
| * Location of page on disk if not in memory
98
The page fault handler runs when a page is not present in memory:
(2)...
* Transfers the page from disk to physical memory
| * May have to replace some pages in memory to make room for the swapped in page
99
Memory pressure forces the OS to start __.
paging out pages to make room for actively-used pages
100
Deciding which page to evict is encapsulated within the __.
replacement policy of the OS
101
Cache Management:
| (2)...
1. Goal in picking a replacement policy for this cache is to minimize the number of cache misses
2. The number of cache hits and misses let us calculate the average memory access time (AMAT)
• Cost of accessing memory ~ 100 ns
• Cost of accessing disk ~ 10 ms (100,000 times slower)
AMAT = (P_Hit_ * T_M_) + (P_Miss_ * T_D_)
102
AMAT = __
(P_Hit_ * T_M_) + (P_Miss_ * T_D_)
---
𝑇_𝑀_ = The cost of accessing memory
𝑇_𝐷_ = The cost of accessing disk
𝑃_𝐻𝑖𝑡_ = The probability of finding the data item in the cache (a hit)
𝑃_𝑀𝑖𝑠𝑠_ = The probability of not finding the data in the cache (a miss)
103
The Optimal Replacement Policy:
| (2)...
1. Leads to the fewest number of misses overall
• Replaces the page that will be accessed furthest in the future
• Resulting in the fewest-possible cache misses
2. Not achievable in the real world (we can’t predict the future)
• However, useful as a comparison point
• Let’s us know how close we are to optimal
104
Tracing the Optimal Policy:
• Can hold __ pages in memory
• Memory starts out __
• __
three;
empty;
Cold (compulsory) misses
105
A Simple Policy: FIFO
| (2)...
• Pages were placed in a queue when they enter the system
• When a replacement occurs, the page on the tail of the queue(the “First-in” pages) is evicted
- It is simple to implement, but it can’t determine the importance of pages
106
Another Simple Policy: Random
| (1)...
Picks a random page to replace under memory pressure
• It doesn’t really try to be too intelligent in picking which blocks to evict
• Random does depends entirely upon how lucky it is in its choice
107
Sometimes, Random is as good as __, achieving 6 hits on the example trace
optimal
108
LRU
Replaces the least-recently-used page
109
Workload Example : The No-Locality Workload:
Each reference is to a __
• Workload accesses __
• Choosing the __
random page within the set of accessed pages;
100 unique pages over time;
next page to refer to at random
110
Workload Example : The 80-20 Workload
(2)...
* Exhibits locality: 80% of the references are made to 20% of the pages
* The remaining 20% of the references are made to the remaining 80% of the pages
111
LRU is more likely to hold onto the __.
hot pages
112
Workload Example: The Looping Sequential
| (2)...
• Refer to 50 pages in sequence
- Starting at 0, then 1, … up to page 49, and then we Loop, repeating those accesses, for total of 10,000 accesses to 50 unique pages
• Worst case scenario for LRU and FIFO
113
To keep track of which pages have been least-and-recently used, the system has to __.
do some accounting work on every memory reference
• Need support from hardware
• Can be expensive
114
Approximating LRU:
Requires some hardware support, in the form of a __.
(2)...
use bit;
• Whenever a page is referenced, the use bit is set by hardware to 1
• Hardware never clears the bit, though; that is the responsibility of the OS
115
Approximating LRU:
Clock Algorithm
(4)...
• All pages of the system are arranged in a circular list
• A clock hand points to some particular page
• When a page fault occurs, the page the hand is pointing to is inspected
- The action taken depends on the use bit
• The algorithm continues until it finds a use bit that is set to 0
116
Meanings?:
1. Use bit: 0
2. Use bit: 1
1. Use bit: 0
Evict the page
2. Use bit: 1
Clear use bit and advance hand
117
Clock algorithm doesn’t do as well as __, but it does do better than __.
LRU;
| approaches that don’t consider history at all
118
The hardware includes a modified bit (a.k.a dirty bit) for each page:
(3)...
* This bit is set at any time a page is written
* If a page has been modified, it must be written back to disk when evicted
* If a page has not been modified, the eviction is free
119
Page replacement algorithm might prefer to evict __ pages over __ ones
clean;
dirty
---
E.g., clock algorithm could scan for pages that are both unused and clean to evict first, before evicting unused pages that are dirty
120
Page Selection Policy:
| (3)...
• The OS has to decide when to bring a page into memory
• For most pages, the OS uses demand paging
- Brings the page into memory when it is accessed
• Other policy is prefetching
- Guess what page is about to be used
- Should only be done where there is a good chance of success
121
Policy for writing pages to disk:
Clustering
(2)...
* Collect a number of pending writes together in memory and write them to disk in one write
* Perform a single large write more efficiently than many small ones
122
Thrashing:
| ...
When memory is oversubscribed and the memory demands of the set of running processes exceeds the available physical memory
123
Thrashing:
Admission control
(3)...
* Decide not to run a set of processes
* Kill off some processes
* Reduce the set of processes working sets to fit in memory
124
Look at real VM systems:
| (2)...
* VAX/VMS
| * Linux
125
VMS Virtual Memory System:
| (4)...
1. VAX-11 Minicomputer introduced in the late 70’s
2. VMS was designed to run on a broad range of machines
• Mechanisms and policies had to work well across a range of systems
3. 32-bit virtual address, with 512-byte pages
• How many offset bits?
• How many VPN bits?
4. Upper two bits were used as segment bits
• Used both segments and page tables
• Hybrid system
126
VAX/VMS Address Space:
| (4)...
1. Very small size for pages (512 bytes)
• Chosen for historical reasons
• Excessively large linear page table
- Use segments to help reduce size of tables
2. Four Segments (determined by bits 31 and 30)
• 00 – User (P0)
• 01 – User (P1)
• 10 – System (S)
• 11 – Unused
3. Process space (P0 and P1)
• Used for each process
• Base and bounds register for each segment
- Base holds the address of page table for segment
- Bounds holds the size of the page table
4. System space (S)
• Protected OS code and data
• Shared across processes
127
Notes on the address space:
| (3)...
1. Page 0 is marked as invalid
• Used to detect NULL pointer dereferences
2. Kernel virtual address space is part of each users address space
• Makes it easy for kernel to copy data from a process to its own structures
• Kernel appears as a protected library to applications
3. Protection for kernel pages done by adding protection bits in the page table
• What privilege level the CPU must be at to access a page
128
VAX Page Table Entries:
Page table entry (PTE) in VAX:
(5)...
* Valid bit
* 4 Protection bits
* Modified (dirty) bit
* 5-bits reserved for OS
* Physical frame number (PFN)
129
VAX Page Table Entries:
Note: no reference bit
- (1)...
Replacement algorithm doesn’t have hardware support for knowing which pages are active
130
Controlling Memory Hogs:
| (4)...
1. Developers of VMS were concerned about programs that use a lot of memory, making it hard for other programs to run
2. LRU is a global policy
• Doesn’t share memory fairly among processes
3. Solution: segmented FIFO replacement policy
• Each process has resident set size (RSS)
- The maximum number of pages it can keep in memory
- Pages are kept on a FIFO list
- When a process exceeds its RSS, the “first-in” page is evicted
4. Problem: FIFO doesn’t perform very well
131
Controlling Memory Hogs:
Solution: segmented FIFO replacement policy
• Each process has resident set size (RSS)
(3)...
* The maximum number of pages it can keep in memory
* Pages are kept on a FIFO list
* When a process exceeds its RSS, the “first-in” page is evicted
132
Second-chance Lists:
| (5)...
1. To improve FIFO’s performance, VMS uses second-chance lists
2. A global list where pages are placed before getting evicted from memory
• Clean-page free list
• Dirty-page free list
3. When a process exceeds its RSS
• “First-in” page is removed from its per-process FIFO
- Placed on global clean or dirty second-chance list depending on whether it has been modified
4. If another process needs a page, it takes the first free page off the clean list
5. If a process faults on one of its pages in the second-chance list
• Reclaims that page from either the free or dirty list
• Avoids costly disk access
133
Page Clustering:
| (2)...
1. VMS groups large batches of pages together from the global dirty list and writes them out to disk together
• Optimization to help overcome the small page size in VMS
• Amortizes the cost of writing one page across the cluster of pages
2. After the pages are written out to disk, we can mark them clean
134
Demand Zeroing of Pages:
For security purposes, the OS should __.
Otherwise, __.
zero out any new pages added to a processes virtual address space;
you would be able to see what was on the page from when some other process used it
---
Could leak encryption keys, for example
135
Demand zeroing defers __.
the zeroing out of a page until it is referenced
136
Demand Zeroing of Pages:
Example: adding a page of memory to the heap of a process:
(3)...
• When a page is added to the page table, it is marked as inaccessible (note: this is different than invalid)
- Physical page is not allocated at this time
• If the process accesses the page, a trap into the OS takes place
- OS then finds a physical page, zeros it, and maps it the processes virtual address space (by updating the PTE)
• If the process never accesses that page, no work is done
137
Copy-on-write (COW):
| Optimization for __.
copying a page from one address space to another
138
Copy-on-write (COW):
Instead of copying the page:
(3)...
1. Mark the physical page as read only (copy-on-write)
2. Have the virtual page in both address spaces map to the (read only) physical page
• If both pages never write to the page, no further work is done
3. If one of the address spaces does try to write to the page
• Trap into the OS, which sees the page marked copy-on-write
• Then the OS can allocate a new page, fill with data, add to the PTE
139
Copy-on-write (COW):
| __ can be marked COW for many processes
Shared libraries
140
Copy-on-write (COW):
Helpful for
(2)...
fork() and exec();
• fork() creates an exact copy, but usually is immediately overwritten by exec()
• Copy-on-write prevents this needless copying
141
The Linux Virtual Memory System:
| (3)...
1. Focus on Linux Intel x86
2. Address Space divided into kernel and user space
• Each user process has own userspace
• Kernel region same across processes
3. Kernel region is protected, divided into logical and virtual regions
• Logical – mapped directly to physical memory
- 0xC0000000 -> 0x00000000
- Translation is trivial
- Contiguous regions in logical memory are contiguous in physical memory
• Virtual – map to any physical page
- Easy to allocate
- Used for large buffers where finding large chunk of physical memory is challenging
142
Address Space divided into kernel and user space:
| (2)...
• Each user process has own userspace • Kernel region same across processes
143
Kernel region is protected, divided into logical and virtual regions:
(2)...
1. Logical – mapped directly to physical memory
• 0xC0000000 -> 0x00000000
• Translation is trivial
• Contiguous regions in logical memory are contiguous in physical memory
2. Virtual – map to any physical page
• Easy to allocate
• Used for large buffers where finding large chunk of physical memory is challenging
144
Page Table Structure:
| (4)...
1. Hardware managed, multi-level page table
2. One page table per process
• OS sets up mappings in its kernel memory
• Points a privileged register at the start of the page directory
• Hardware handles the rest
3. OS gets involved at process creation, deletion, and context switches
4. X86-64 (64-bit addresses)
• Four-level page table, 4k page size
• Only the bottom 48 bits are currently used
145
Large Page Support:
| (5)...
1. X86 allows for multiple page sizes in hardware
• 2-MB and even 1-GB pages
2. Reduces number of mappings in the page table
3. More Importantly, it reduces the pressure on the TLB
• Some applications spend 10% of their system servicing TLB misses
4. Implemented in Linux incrementally
• Applications explicitly request memory with large pages via mmap()
• In recent versions of Linux have added transparent large page support
• Automatically looks for opportunities to allocate 2 MB pages without application modification
5. Issues
• Larger pages can lead to internal fragmentation
146
Page Cache:
| (4)...
1. Since hard drives are so slow, Linux uses aggressive caching to keep popular data items in memory
2. Page cache keeps pages in memory from three sources
• Memory-mapped files
• File data
• Heap and stack pages
3. Page cache keeps track if entries are clean or dirty
• Dirty pages are periodically written back to disk by background threads
• After a certain period of time or if too many pages are dirty
4. How does Linux decide which pages to evict?
• 2Q replacement algorithm
147
• Page cache keeps pages in memory from three sources:
| (3)...
* Memory-mapped files
* File data
* Heap and stack pages
148
Page cache keeps track if entries are clean or dirty:
| (2)...
* Dirty pages are periodically written back to disk by background threads
* After a certain period of time or if too many pages are dirty
149
2Q Replacement Algorithm:
| (3)...
1. Design goal: LRU-like performance without the penalty for some common access patterns
• Reading through a large file can kick every other file out of memory
• If you just read through the file once, those pages are never referenced again
2. Keep two lists and divide memory between them
• When a page is accessed for the first time it is put on the inactive list
• When it is re-referenced, the page is promoted to the active list
• When needed, pages are evicted from the inactive list
• Pages are periodically moved from the bottom of the active list to the inactive list
• Active list is about 2/3 the total page cache size
• LRU is a approximated by an algorithm similar to the clock replacement algorithm
3. Handles the case of cyclic large-file access
• Pages that are never re-referenced are confined to the inactive list and won’t evict pages from the active list
150
2Q Replacement Algorithm:
Design goal:
(2)...
LRU-like performance without the penalty for some common access patterns
• Reading through a large file can kick every other file out of memory
• If you just read through the file once, those pages are never referenced again
151
2Q Replacement Algorithm:
| (4)...
• When a page is accessed for the first time it is put on the inactive list
• When it is re-referenced, the page is promoted to the active list
• When needed, pages are evicted from the inactive list
• Pages are periodically moved from the bottom of the active list to the inactive list
- Active list is about 2/3 the total page cache size
- LRU is a approximated by an algorithm similar to the clock replacement algorithm
152
Security and Buffer Overflows:
How to protect from buffer overflow attacks?
(2)...
* Prevent execution of any code found within the stack
| * NX bit (AMD) and XD bit (Intel) prevents execution from any page that has this bit set in the PTE
153
Security and Buffer Overflows:
| Return-oriented programming (ROP) strings together...
pieces of existing code (called gadgets)
• Mitigate by performing Address space layout randomization (ASLR)
- OS randomizes the placement of code, heap, and stack each time a program is run
- Makes it almost impossible to predict the addresses of the gadgets in memory
154
Security and Buffer Overflows:
Kernel address space layout randomization (KASLR):
...
Kernel is placed at a random location
155
Meltdown and Spectre:
| (4)...
1. These attacks reveal memory by taking advantage of speculative execution done by the processor
• The CPU guesses which instructions will soon be executed in the future
• Starts executing them ahead of time
• Correct guesses mean the program runs faster
• Wrong guesses are undone by the CPU by restoring state (registers)
2. However, state is not fully restored
• E.g., caches, branch predictors
3. These subtle changes in state can make vulnerable the contents of memory
• Even protected memory
4. Can’t disable speculative execution, programs will run much much slower
156
Meltdown and Spectre:
These attacks reveal memory by taking advantage of speculative execution done by the processor
(4)...
* The CPU guesses which instructions will soon be executed in the future
* Starts executing them ahead of time
* Correct guesses mean the program runs faster
* Wrong guesses are undone by the CPU by restoring state (registers)
157
Kernel Page Table Isolation (KPTI):
| (5)...
• Remove as much of the kernel address space from each user process
• Have a separate kernel page table for most kernel data
• Kernel code and data structures are no longer mapped into each process
• When switching into the kernel, a switch to the kernel page table is needed
- The cost is performance
- Switching page tables is costly
• Solves some, but not all of the problems of speculative execution
