P3L2. Memory Management Flashcards
What is a page table?
The component that’s used to translate virtual memory addresses to physical memory addresses. The OS creates a page table for every process that it runs. This means that on context switch, the OS has to switch to the appropriate page table for the process. Hardware assists with page table accesses by maintaining a register that points to the current page table.
Why is the separation between virtual and physical memory important?
To avoid imposing any limitations on the size and layout of an address space based on the amount of physical or how its shared with other processes
In order to manage physical memory the OS must be able to allocate and arbitrate how it’s being accessed. Describe these two roles
Allocate Since the physical memory is smaller than the virtual memory, it’s likely that some of the contents needed in the virtual address space are not present in physical memory but instead in secondary storage like on disk. The OS must have algorithms in place to decide how to replace the contents that are in physical memory with whatever is needed by the process. Arbitrate OS is able to interpret and verify a process memory access. Able to translate a virtual address into a physical address and verify that it’s legal.
What are the two main memory management systems and what do they allocate/arbitrate?
Page-based memory management
Virtual memory is divided into pages and physical memory is divided into page frames of the same size.
- Allocate: pages (virtual memory) to page frames (physical memory)
- Arbitrate: page tables
Segment-based memory management
- Allocate: segments (flexible size?)
- Arbitrate: segment registers
What hardware support exists to support allocation and arbiration tasks?
Memory Management Unit (MMU)
- The CPU issues virtual memory addresses to the MMU and it’s responsible for translating that into a physical memory address.
- Or the MMU can generate a fault: illegal accesss, inadequate permissions, page not present in memory and must be fetched from disk
Registers
Designated registers during the address translation process
- pointers to page table
- base address and limit size, number of segments
Cache (translation lookaside buffer)
- valid virtual to physical address tranlations. if the translation is already in the cache we can save on performing operations
Translation
The OS maintains data structures (e.g., page tables) but the actual translation is performed by the hardware.
The hardware dictates what memory management modes are supported (e.g., paging or segmentation), virtual address formats, etc.
How is a page table used to determine where something is stored in physical memory?
A page tables is the component used to translate a virtual memory address into a physical memory address.
Pages and page frames are the same size so we can store less information in the page table.
Only the first portion of the virtual address is used to index into the page table. The first part of the virtual address is called the “virtual page number” and the rest is the offset.
Looking up the virtual page number in the page table produces the physical frame number in DRAM. When the offset is added then we get the actual memory location.
When is physical memory allocated?
The first time a process attempts to access it (allocation on first touch).
This ensures that phycial memory is allocated only when we actually need it.
If a process hasn’t used its data structures in a while it’s likely the memory will be reclaimed (put on disk).
What happens on a process context swith with regard to a page table?
The OS maintains a page table per process
On context switch, OS must switch to valid page table. Hardware assists with page table accesses by maintaining a register that points to the active page table. This means that on context switch, update register with address of new page table.
What kind of fields exist in a page table entry?
Page Frame Number (PFN)
Flags
- Present (valid/invalid)
- Dirty (written to)
- Accessed (for read or write)
- Protection bits (Read, Write, Execute)
How does a page fault happen?
The MMU uses page table entries to perform address tranlation, and also relies on flags (bits) to establish the validity of the access. If the hardware determines that a physical access cannot be performed it causes a page fault.
The CPU will place an error code on the stack of the kernel, then generate a trap into the kernel.
That generates a page fault handler, which will determine what action needs to be taken base don the error code and the address that caused the fault. Was the page not present or was there a permission error?
How do we determine a page table’s size?
Why is the page table design of assuming one entry per virtual page number a problem?
Number of entries = number of virtual page numbers in virtual address space
Example on 32-bit architecture:
- Page Table Entry = 4 bytes (includes PFN + flags)
- Virtual Page Number (VPN) = 2^32 / page size
- Page Size = 4 KB
== (2^32 / 2^12) * 4B = 4GB per process
This size gets out of hand quickly! We need a more efficnent way to store memory mappings!
How does a hierarchical page table work?
What are the pros and cont?
There’s an outer page table (aka top page table) which acts as a page table directory. Then there are internal page tabels exist only for valid virtual memory regions.
The address is composed of three parts (vs two for the flat page table design). The last portion of the address is still the offset thats used to index into the actual physical memory. The first two components of the address are used as indices into the different levels of the page table hierarchy The first part is an index into the directory page table. The second part is an index into the internal page table.They will ultimately produce the page frame number that’s used find the starting address of the physical region.
Multi-level Page Table Tradeoffs
Pros:
+ smaller internal page tables / directories granularity of coverage means potential reduced page table size
Cons:
- more memory accesses required for tranlation means increased translation latency
Multi-level page table quiz
How do inverted page tables work? What are their weakenesses and what mechanisms are in place to get around them?
An inverted page table is on the order of available physical memory rather than available virtual memory, so its footprint is much smaller.
Page table entries contain information for each element of the physical memory (e.g., each page table elements corresponds to one physical frame number)
To find the translation the page table is searched pased on the process id and the first part of the virtual address. When found, the index where that info is stored denotes the physical frame number, which is then combined with the offset to find the actual address in physical memory.
The problem with inverted page tables is we have to perform a linear search to find the entry that matches the pid + virtual memory id. The table isn’t ordered so there isn’t a clever way to speed up the search. The TLB cache saves us from having to do a ton of lookups, but we also supplement them with hashing page tables to increase efficiency of lookups.
A hashing page table computes a hash on part of the address, and that’s an entry into a hash table that points to a linked list of possible matches for this part of the address. This allows us to speed up the linear search by narrowing it down, which speeds up the address translation.
How does segmentation work?
Address space is divided into segments of arbitrary granularity
Address is composed of segment descriptor and offset
A segment can be represented with a contiguous portion of physical memory. In that case it would be defined by its base address + limit registers (which implies segment size)
What is demand paging?
Since physical memory is much smaller than addressable virtual memory, allocated pages don’t always have to be present in physical memory (DRAM).
The backing physical page frame can be repeatedly saved and restored to/from secondary storage
Demand paging is when pages are swapped in.out of memory and a swap partition (e.g., on disk).
When a page is not present in memory its page table entry has has its present bit set to 0. When there’s a reference to that page the MMU will raise an exception which will cause a trap into the kernel. The OS will determine that this exception is a page fault, that it had previously swapped that page onto disk, can establish the correct disk access to be performed and issue an I/O operation to retreive the page. Once the page is brought into memory, the OS will determine a free frame where that page can be placed, and use the page frame number to update the page table entry that corresponds to the virtual address of the page. At that point control is given back to the process that caused the reference and the program counter is restarted with the same instruction so the reference will be made again but this time it will find a valid entry with a reference to the new physical locaiton.
What is copy-on-write (COW)?
When a new process is created the OS copies the entire parent address space. However, most pages are static (don’t change) so to void unnecessary copying, portions of the virtual address space of the new process will point to the virtual address space of the old process. The address space is write protected so the OS knows if either process attempts to change it.
IF a change is made, only then is the content copied.
- the MMU will detect that the area is write protected, generate a page fault, which will cause the OS to copy and update the page table as the two processes.
This allows us to only pay the cost of copy if necessary
