P3L2: Memory Management

Question 1

What are three guiding principles of Memory Management system?

Answer 1

1. Intelligently sized containers: The size of memory pages and segments is an important design consideration.
2. Not all memory is needed at once: Tasks operate on a subset of memory.
3. Optimize for performance: Reducing the time needed to access memory improves performance.

Question 2

What are the three tasks of memory management? (What does mem mgmt DO?)

Answer 2

• Manage physical memory (DRAM) on behalf of executing processes. We do this by decoupling physical from virtual addresses.
• Allocate physical memory: track how it’s used and what’s free, determine what should be stored in memory and what can be moved to disk
• Arbitrate: OS needs to perform translation from virtual to physical address and validate it.

Question 3

Describe page-based memory management

Answer 3

• The virtual address space is divided into fixed-sized segments called pages.
• Physical memory is divided into page frames of the same size.
• Allocation is then about mapping pages to page frames
• Arbitration is accomplished via page tables

(this is the most common method)

Question 4

Describe segment-based memory management

Answer 4

• Allocation is accomplished using flexibly-sized segments which can be mapped to regions of physical memory or swapped in and out of physical memory
• Arbitration is accomplished using segment registers

(this is less common than page-based mem mgmt)

Question 5

How does hardware support memory management?

Answer 5

• Memory management units
• Registers
• Translation Lookaside Buffer

Question 6

What is the memory management unit?

Answer 6

• Equipped on the CPU package
• Translates virtual to physical addresses
• Generates faults: illegal access, inadequate permissions, requested page isn’t present in memory

Question 7

How are hardware registers used in the address translation process?

Answer 7

• Page-based system: Register points to currently active page table
• Segment-based system: Register stores the base address of segments, limit address (size) of segment, number of segments

Question 8

Describe the Translation Lookaside Buffer

Answer 8

The TLB is a hardware cache of valid virtual to physical address translations. This avoids the need to perform translation and speeds things up.

Question 9

What performs translation of virtual to physical addresses, hardware or software? How does this affect the design of memory management system?

Answer 9

Hardware! The hardware therefore dictates what kinds of memory management are supported (paging vs segment, what kind of pages, etc.)

Question 10

What performs allocation of memory, hardware or software? What does this mean for design of mm system?

Answer 10

Software! This means the system can be more flexible.

Question 11

What performs replacement policy for memory management, hardware or software?

Answer 11

Software! This makes it more flexible.

Question 12

What are page tables and how do they work?

Answer 12

• Page tables intermediate between virtual memory addresses (pages) and physical memory, translating one to the other.
• Because the virtual pages and physical page frames are the same size, the page table only has to map the first virtual address in each page to the first physical address in each page frame.

Question 13

Describe the mapping of virtual to physical addresses via the page table

Answer 13

Because we only need to map the first entry in each page to the first entry in each page frame, the page table only requires the Virtual Page Number (VPN), i.e., the first part of the virtual address.

We use the VPN as an offset in the page table to find the Physical Frame Number (PFN).

Once we have that, we append the remainder of the virtual address after the VPN (the offset) to the PFN.

Question 14

What is “allocation on first touch”?

Answer 14

This means that we only allocate physical memory to an object when we first try to access it. This prevents the allocation of physical memory to objects that are never used.

Question 15

What happens when pages go unused for a long time?

Answer 15

The associated physical page frames are reclaimed and eventually reassigned to other pages. The data stored in the page frame is pushed to disk.

Question 16

How do page tables help detect reclaimed page frames?

Answer 16

In addition to the mapping from VPN to PFN, the page table also includes bits that tell the mem mgmt system info about the validity of an attempted access.

If the page is in physical memory, the bit is 1, otherwise 0.

If MMU sees that bit is zero, it will raise a fault and the OS will take over and decide how to handle it.

As long as this was a valid address is being accessed, the data will be brought back into physical memory, likely at a different location. Page map is updated.

Question 17

How many page tables are maintained?

Answer 17

One per process

Question 18

How are page tables involved in a context switch?

Answer 18

On a context switch to a new process, the OS must switch to the page table for that process.

Question 19

Describe a generic page table entry

Answer 19

A page table entry will include:

• Page frame number ( PFN)
• Valid bit (also called present bit): indicates whether page is in memory
• Dirty bit: indicates whether a page has been written to. Useful in file caching.
• Access bit: has the page been read or written to?
• Protection bits (RWX): Can indicate that page is only readable, only writable, or some other kind of access

Question 20

What is the common page size?

Answer 20

4kb

Question 21

Describe the storage issue for page tables

Answer 21

Page table has n entries, where n is the number of virtual page numbers in virtual address space. Each entry holds PFN + flags, 8 bytes oughtta do it for 64-bit arch.

The number of entries depends on the size of the addresses and page size. On 64-bit architecture with 4 kb pages, that means 2^64 / 4 kb = 2^64 / 2^12 = 2^52 entries. If each entry is 8 bytes long, that’s 2^52 * 8 bytes = 32 PB!

Per process!

Question 22

How do you solve the page table storage size issue?

Answer 22

By using hierarchical page tables instead of flat!

Question 23

Describe Hierarchical Page Tables

Answer 23

An outer page table (or top page table, page table directory) points to internal page tables.

Internal page tables are only allocated for valid virtual memory regions. Blank regions don’t get internal tables.

On malloc, a new internal page table may be created.

Question 24

What does the virtual address look like for hierarchical page tables?

Answer 24

The first element indexes the outer page table, the second element indexes the internal page table, and the offset is still at the end (like in a regular virtual address)

Question 25

What are the tradeoffs involved in using a multi-level hierarchical page table (HPT with directories of directories)?

Answer 25

Pros: Internal page tables/directories cover smaller regions of virtual address space, making it more likely that we will be able to leave out entire tables because those regions of VAS are empty. This reduces overall page table size. Cons: More memory accesses are required for translation, increasing translation lattency.

Question 26

What is the downside of using multi-level page table?

Answer 26

Increased overhead! A flat page table requires only 2 memory accesses, one for the page table entry and another for the actual memory. A four-level table will require 5! One for each level of the table plus one for memory.

Question 27

How do we avoid the increased overhead of using a multi-level page table?

Answer 27

We cache page table results! i.e., use the Translation Lookaside Buffer.

Question 28

What is an Inverted Page Table?

Answer 28

An Inverted Page Table has one entry per item in physical memory (say, a frame) instead of one entry per process. This avoids storing mappings from page to page frame when the page frame is no longer in memory.

Question 29

What is the benefit of the Inverted Page Table?

Answer 29

It can be much smaller! The size of the Inverted Page Table is determined by the size of physical memory (smaller) rather than virtual (larger).

Question 30

How do we speed up the search of an Inverted Page Table?

Answer 30

Use a hashing page table. We hash on part of the virtual/logical address and this points to a linked list of potential matches. Then we just search this smaller list.

Question 31

What does the virtual/logical address look like for an Inverted Page Table?

Answer 31

Process ID (pid) | virtual page number (p)

Question 32

What is the problem with Inverted Page Tables?

Answer 32

We have to perform a linear search of the table looking for matches to process ID and VPN. In practice, TLB will catch a lot of these, so no search is needed.

Question 33

How are segment sizes determined when using segmentation?

Answer 33

Segments typically correspond to some logically meaningful unit: code, heap, data, stack, etc.

Question 34

Describe a virtual address when using segmentation?

Answer 34

segment descriptor | offset

Question 35

In segmentation, how are virtual addresses mapped to physical?

Answer 35

The first part of the address, the segment descriptor, is used with a "descriptor table" to produce information about the physical address. This is combined with the offset from the virtual address.

Question 36

In practice, segmentation and paging are typically used together. How?

Answer 36

The CPU passes the "logical" address to the segmentation unit, which uses this with the descriptor table to get the "linear" address. The linear address is passed to the paging unit, which then gets the physical address.

Question 37

What are the three page sizes that can be used by Linux x86?

Answer 37

Default: 4 kb Large: 2 mb Huge: 1 gb

Question 38

What are the tradeoffs involved in larger page sizes (large and huge)

Answer 38

Pros: - Smaller page tables! More address bits are used for offsets, therefore fewer bits are available for virtual page numbers - More TLB hits: able to translate more of physical memory using TLB cache Cons: - Actual page size: If large virtual page is sparsely populated, this wastes memory. Internal fragmentation.

Question 39

What do kernel level and user level memory allocators do?

Answer 39

Kernel level: Allocates memory for kernel state and static process state (code stack, initialized data, etc.), keeps track of free memory in system. User level: Handles dynamic process state (heap), i.e., memory that is dynamically allocated during process execution. This is what malloc and free are for.

Question 40

What issues might a memory allocation algorithm be concerned with?

Answer 40

- Limit the extent of fragmentation | - Allow for quick coalescing/aggregation of free areas

Question 41

Describe the Buddy Allocator (memory allocation)

Answer 41

- Start with a contiguous region of free memory with size that's a power of 2 - When request comes in, the allocator subdivides region into 2 chunks. Continues doing so until it reaches the appropriate size.

Question 42

What is the benefit of the Buddy Allocator?

Answer 42

While fragmentation will still occur, it's very easy to see if free memory can be aggregated because every region has a size that's a power of two. This means that neighboring regions have addresses that only ever differ by one bit!

Question 43

Describe the Slab allocator

Answer 43

- Pre-creates caches of commonly used objects. Items in the cache map to physically contiguous regions of memory. - Freed objects are returned to their respective caches

Question 44

What are the benefits of the Slab Allocator?

Answer 44

- Avoids internal fragmentation because slabs are the right size for new objects - Avoids external fragmentation because freed objects are easily replaced by the same object type in the future.

Question 45

What is demand paging?

Answer 45

- Virtual memory page not always in physical memory (since virtual is so much larger than physical) - Physical page frame is saved to and restored from secondary storage

Question 46

What is a swap partition?

Answer 46

This is where pages are stored on disk when they are swapped out of memory

Question 47

What is page pinning?

Answer 47

When we disable swapping that page out of memory. We might do this if using a device with direct memory access.

Question 48

When should pages be swapped out?

Answer 48

- When memory usage is above some threshold | - And when CPU usage is BELOW some threshold (to not disrupt execution)

Question 49

Which pages should be swapped out?

Answer 49

- Pages that won't be used in the future! We determine this with the Least Recently Used policy (LRU), which takes advantage of the access bit. - Pages that don't need to be written out to disk. We can use the Dirty Bit to track what has been modified

Question 50

What is Copy-On-Write?

Answer 50

- When we create a new process, instead of copying the original address space, we map the new to the original - Then write protect the original - When the new process tries to write, MMU will detect a page fault and OS will make a copy!

Question 51

What are OS services that benefit from memory management hardware support?

Answer 51

- Copy On Write | - Checkpointing

Question 52

What is Failure Management Checkpointing?

Answer 52

- Periodically save process state | - Then if failure occurs, can restart from checkpoint! Faster recovery

Question 53

What does MMU-enabled checkpointing look like?

Answer 53

- Write-protect and try to copy everything at once, WITHOUT PAUSING - MMU tracks dirty pages that are modified in execution - At incremental checkpoints, only copy those pages that have been modified