Paging Flashcards
(133 cards)
1
Q
⭐️ What’s another method, apart from segmentation, that allows the physical address space of a process to be non-contiguous?
A
Paging
2
Q
⭐️ Paging divides physical memory into fixed-size blocks, called
A
page frames
3
Q
⭐️ Paging divides virtual memory into blocks of the same size called
A
pages
4
Q
⭐️ Paging uses a page table for
A
address translation
5
Q
⭐️ Does paging need both OS and hardware?
A
Yes
6
Q
⭐️ What sort of fragmentation does paging avoid, and what sort of fragmentation doesn’t it avoid?
A
Avoids external fragmentation
Doesn’t avoid internal fragmentation
7
Q
⭐️ The fact that paging doesn’t need to assume how the heap and stack grow and are used makes it more…
A
flexible
8
Q
⭐️ The fact that the page in the address space and the page frame are the same size in paging makes it easy to allocate and keep a free list, this makes paging more…
A
simple
9
Q
⭐️ To translate a page a virtual address is split into two parts, which are they?
A
Virtual Page Number (VPN) and offset
10
Q
⭐️ Give the definition:
Used as an index into a page table which contains base address of each page in physical memory.
A
Virtual Page Number (VPN)
11
Q
⭐️ Give the definition:
Combined with base address to define the physical memory address that is sent to the memory unit
A
Offset
12
Q
⭐️ To determine where a physical page is in paging we only need to translate the…
A
page number
13
Q
⭐️ What does the page table in paging do?
A
Keeps track of the mapping of virtual to physical addresses
14
Q
⭐️ Give the definition:
A register that indicates the starting address of the page table
A
Page table base register
15
Q
What does page sharing allow 2 pages to do?
A
Point to the same frame
16
Q
⭐️ What is the simplest form a page table?
A
A linear page table
17
Q
What does a Page Table Entry (PTE) include?
A
Translation information, etc.
18
Q
Give the definition:
A sort of page table that has an entry for each physical page frame of the system. The entry tells us which process is using this page, and which virtual page of the process maps to this physical page
A
Inverted page table
19
Q
What are the pros of inverted page tables?
A
Memory saving
20
Q
What are the cons of inverted page tables?
A
Long searching time
Page sharing
21
Q
How is page sharing implemented for a per-process page table?
A
By letting two pages point to the same frame
22
Q
How is page sharing implemented for an inverted page table?
A
It’s difficult to implement; 2 virtual pages cannot point to the same frame due to inverted page tables only supporting 1:1 mapping
23
Q
What is the biggest problem with paging?
A
The performance is affected by a factor of 2 due to every instruction requiring two memory accesses
24
Q
Which 2 steps in every memory reference are memory accesses?
A
- Fetching page table address
- Fetching physical address to register
25
⭐️ Why do we use a Table Lookaside Buffer (TLB)?
To speed up the paging translation
26
⭐️ Give the definition:
A buffer that uses hardware to speed up paging translation by building a cache to store popular translations
Table Lookaside Buffer (TLB)
27
⭐️ Which computer component is the TLB a part of?
Memory Management Unit (MMU)
28
⭐️ Give the definition:
Virtual Page Number (VPN) is in TLB and can be quickly accessed
TLB hit
29
⭐️ Give the definition:
VPN is not in TLB. Access page table to get the translation, update the TLB entry with the translation
TLB miss
30
⭐️ What sort of locality makes it possible for the TLB to improve performance?
Spatial locality
31
⭐️ Give the definition:
An instruction or data item that has been recently accessed will likely be re-accessed soon in the future
Temporal locality
32
⭐️ Give the definition:
If a program accesses memory at address X, it will likely soon access memory near X
Spatial locality
33
TLB is a ... associative cache
fully
34
⭐️ Why is the TLB a fully associative cache?
- Any given translation can be anywhere in the TLB
- Hardware searches entire TLB in parallell to find the target
35
⭐️ What sort of entry is this?
VPN | PFN | Other bits
TLB entry
36
What is the biggest issue with the TLB?
Context switch
37
What are the two solutions to the issue with context switch with a TLB?
Flush and Address Space Identifier (ASID)
38
Give the definition:
- OS flushes the whole TLB on context switch
- Flush operation sets all valid bits to 0
Flush
39
What solution to context switching has this problem?
The overhead is too high if OS switches processes frequently
Flush
40
Give the definition:
- A field in the TLB, sort of like a process identifier, that makes it possible to identify which process a TLB entry belongs to
Adsress Space Identifier (ASID)
41
What's the issue with using smaller pages to solve the problem of a too big page table in paging?
Internal fragmentation; Don't use up the whole page
42
What do we use instead of smaller pages to solve the problem of too big pages in paging?
Variable page size
43
A smaller page size results in ... TLB entries
more
44
Give the definition:
A hybrid approach. One page table for each logical segment
Paging and segmentation
45
What does the base register in paging and segmentation combined point to?
Physical address of the page table
46
What does the limit register in the combination of segmentation and paging determine?
The size of the segment, i.e., how many valid pages the segment has
47
What 3 segments are used in the combination of paging & segmentation?
Code, heap & stack
48
What are the two problems with combining segmentation and paging?
- Page table waste for sparsely used heap
- External fragmentation (inherited from segmentation)
49
What's the motivation for multi-level paging?
Large page table is contiguous & may have some unused pages
50
Does multi-level paging allocate the page table in a contiguous or non-contiguous manner?
Non-contiguous
51
Give the definition:
Creating multiple levels of page tables with an outer level called a page directory which tracks whether a page of the page table is valid
Multi-level paging
52
In multi-level paging, if an entire page of page tables is invalid, what happens?
The page isn't allocated
53
Multi-level paging only allocates page-table space in proportion to what?
The amount of address space being used
54
In multi-level paging the page number of the virtual address is divided into two parts due to the paging of the page table, what are the 2 parts?
1. Index to the page directory
2. Page table index
55
What's the solution to the problem with page directories not fitting in a page that can occur in paging with several levels?
Multi-level page directories
56
What are these three points a motivation for?
- Processes spend the majority of time in a small portion of code
- Processes only use a small amount of address space at any moment
- Only a small amount of address space needs to be resident in physical memory
Page swapping
57
What are these 2 points a motivation for?
- Memory: fast, but small
- Disk: slow, but large
Page swapping
58
What's this the idea behind?
Processes can run with only some of their pages in memory. Only keep actively used pages in memory & keep unreferenced pages on disk
Page swapping
59
Swapping makes it possible for the total physical address space of all processes to...
exceed the real physical memory of the system
60
Give the definition:
Reserving of space on the disk for moving pages back and forth. Tracked in page-sized units.
Swap space
61
How do we know where a pages lives?
Present bit / Valid bit
62
What does a present bit equal to 1 indicate?
That a page lives in-memory
63
What does a present bit equal to 0 indicate?
That a page is in-disk
64
Give the definition:
If present bit in PTE is 0 when accessing a page
Page fault
65
What's the objective of page swapping policies?
To minimize the number of page faults (cache misses)
66
What are the two sorts of page selection?
Demand paging and prefetch
67
Give the definition:
- Load page only when it's needed (demand)
Demand paging
68
What are the pros of demand paging?
Less I/O communication & less memory use
69
What's the issue with demand paging?
High page fault cost
70
Give the definition:
- Load page before referencing
- OS predicts future accessed pages and brings them into memory early
- Works well for some access patterns, like sequential pages
Prefetch
71
Give the definition:
Copy the page only if a process writes to it (demand). A memory management technique that delays copying data until it's modified.
Copy-On-Write Paging
72
What are the 2 benefits of copy-on-write paging?
1. Efficiently reduces memory usage
2. Improves performance
73
What approach to page replacement is this?
If memory is entirely full, OS then replaces a page to make room for another page. An unrealistic approach due to the OS usually reserving some room for new pages
Lazy approach
74
What is the normal approach to page replacement?
Swap Daemon/Page Daemon
75
Give the definition:
If there are fewer than LW (Low Watermark) pages available, a background thread that's responsible for freeing memory is activated. The thread evicts pages until there are High Watermark (HW) pages available
Swap Daemon/Page Daemon
76
⭐️ What metric is used to determine the performance of page replacement policies?
Average Memory Access Time (AMAT)
77
⭐️ Average Memory Access Time (AMAT)
P_hit * T_m + P_miss * T_d
78
⭐️ What are the four most commonly used page replacement policies?
Optimal replacement
FIFO
Least-Recently-Used (LRU)
79
⭐️ Give the definition:
Replace the page which isn't used for the longest time in the future
Optimal replacement
80
⭐️ What page replacement policy has the following pros:
Minimal number of page faults
Optimal replacement
81
⭐️ What page replacement policy has the following cons:
Impractical, need to predict the future
Optimal replacement
82
The optimal replacement page replacement policy can be used for what purpose, other than as a policy?
Comparison baseline
83
⭐️ Give the definition:
Replace the page which is loaded into memory first
FIFO
84
⭐️ What page replacement policy has the following pros:
Fair & easy to implement
FIFO
85
⭐️ What page replacement policy has the following cons:
May evict useful pages
FIFO
86
⭐️ Give the definition:
Replace the page which hasn't been used for the longest time. Predict using history.
Least-Recently-Used (LRU)
87
⭐️ What page replacement policy has the following pros:
Approximate optimal replacement - minimizes number of page faults
LRU
88
⭐️ What page replacement policy has the following con:
Difficult to implement
LRU
89
⭐️ The performance of replacement policies also depends on...
workloads
90
When there's a random workload, which replacement policy works best out of FIFO, RAND & LRU?
No difference
91
When there's a 80/20 workload, which replacement policy works best?
LRU
92
What type of workload is this?
80% memory accesses go to 20% of the pages
80-20 workload
93
When there's a looping sequential workload, which replacement policy works best?
RAND
94
What happens to the performance of LRU and RAND, if more physical memory is added?
Have fewer, or the same number, of page faults
95
What happens to the performance of FIFO, if more physical memory is added?
More page faults due to Belady's anomaly
96
Give the definition:
The increase of the number of page frames resulting in an increase in the number of page faults for certain memory access patterns
Belady's anomaly
97
What type of LRU implementation is this?
- A datastructure to track reference time of all pages
Software Perfect LRU
98
What type of LRU implementation is this?
- A timestamp register added to each page
Hardware Perfect LRU
99
What type of LRU implementation is this?
- Approximate implementation, finds an old page, but not necessarily the oldest one
Practical LRU
100
What algorithm does this describe?
A use/reference bit for each page
A circular queue of all physical pages
A clock hand to select which page to evict
Clock algorithm (second chance)
101
What does it indicate if the use/reference bit for the clock algorithm is: 0
Page not used
102
What does it indicate if the use/reference bit for the clock algorithm is: 1
Page used
103
What happens if the clock hand for the clock algorithm selects a page with the use/reference bit set to: 0
Page's evicted
104
What happens if the clock hand for the clock algorithm selects a page with the use/reference bit set to: 1
The use/reference bit is set to 0 & the clock hand moves onto the next page
105
⭐️ A form of flexible virtual memory management is...
Paging
106
What non-contiguous memory access method has these to challenges:
Slow access
Big page table and high memory consumption
Paging
107
⭐️ What is used to solve the problem with slow access in paging?
TLB
108
⭐️ What techniques within paging are used when we have a big page table?
Multi-level paging and inverted page tables
109
⭐️ What techniques are used when we have a larger address space in paging?
Swapping and replacement
110
⭐️ How many bits does the offset need for a page size of 4 KB?
12
111
⭐️ For an OS with a 32-bit address space and 4KB page size, how many bits are used for page index/number?
20
112
⭐️ If the physical memory is 2GB & the page size is 4KB, how many frames does the system have?
19
113
⭐️ An OS uses paging to manage memory. It has a 16-bit address space & a page size of 2KB. How many bits does the offset require?
11 bits
114
⭐️ An OS uses paging to manage memory. It has a 16-bit address space & a page size of 1KB. How many bits does the page index have?
6 bits
115
⭐️ In XV6-RISCV, the default page size is 4 KB & each page table entry (PTE) is 54 bits. How many PTEs can a page store? (1 B = 8 bits)
606 PTEs
116
⭐️ Given a 39-bit address space, a page size of 4KB, a PTE of 4B. What's the memory requirement of the page table?
2^29
117
⭐️ Paging may suffer from external fragmentation (T/F)
False; paging may suffer from internal fragmentation due to fixed page partitions
118
⭐️ Page offset is determined by the number of pages (T/F)
False; page offset is determined by page size
119
⭐️ Page table is stored in main memory (T/F)
True
120
⭐️ Inverted page table implements a per-process page table for each process (T/F)
False; inverted page table implements a large table for the physical frames
121
⭐️ Given an OS with a per-process page table, what does a page table entry (PTE) include?
1. Page number
2. Frame number
3. Offset
4. PTE flags
2 & 4
122
⭐️ Using a Table Lookaside Buffer (TLB) can reduce the page table size (T/F)
False; speeds up paging translation, doesn't reduce the page table size
123
⭐️ What does an entry of the TLB store?
1. Page Table Entry
2. Frame number
3. Page number
4. Other related information
5. Offset
2, 3 & 4
124
⭐️ Given a 64-bit virtual address, a page table entry size of 8 bytes, and a page size of 8 KB, how many bits are required for the page offset?
11
12
13
13
125
⭐️ Given a 64-bit virtual address, a page table entry (PTE) size of 8 bytes, and a page size of 8 KB, how many PTEs does a page store?
2^10
2^11
2^12
2^13
2^10
126
⭐️ Given a 64-bit address, and a 8 KB page size, the system uses 3-level paging. How many bits are required for the page table index?
10 bits
11 bits
12 bits
13 bits
10 bits. Due to a page storing 2^10 PTEs. (See flashcard 125 for explanation & 07.02.3035)
127
⭐️ Demand paging loads required pages into the physical memory only when they're needed (T/F)
True
128
⭐️ The copy-on-write mechanism allows a process' virtual memory to exceed the available physical memory (T/F)
False. This is only the case for page swapping.
129
⭐️ Page swapping space is a designated area in physical memory (T/F)
False. It is a designated area on disk.
130
⭐️ The Least-Recently-Used (LRU) replacement policy always performs the best of all replacement policies (T/F)
False. The optimal replacement policy is the only policy that this is the case for, and it isn't implementable, and the performance of replacement policies depends on workloads.
131
⭐️ Upon the first access of a page, two memory references are made (T/F)
True
132
⭐️ A multi-level page table is used to reduce the performance overhead (T/F)
False
133
⭐️ Which of the following statements are true?
1. If the dirty bit of a page is set, it means the page has been modified and is different from
the one on disk.
2. Demanding page loads required pages in advance.
3. in xv6-riscv, each process has its own page table.
4. Even using swapping, the virtual address size must be smaller than the physical address
size.
1, 3
