memory Flashcards
To protect against the meltdown attack, the kernel address space is largely hidden from user mode and an explicit address space switch takes place when entering the kernel. Explain which hardware feature can reduce the cost of this switch and how
it works.
The cost can be reduced by using tagged TLBs. With tagged TLBs, every address space is assigned a tag and only TLB entries with the current tag are used
for translation, thus eliminating the need to flush the TLB on kernel entries and exits
Which property of a forward page table determines the maximum size of the physical
address space?
The size of the physical address space is determined by the width of the page frame number field.
Linear page table
The virtual address space is divided into fixed-size pages, and each page table entry (PTE) maps a virtual page to a physical page frame in memory.
It is suited for systems with small or mostly filled virtual address spaces.
Inverted page table
Each entry corresponds to a physical page frame in memory and contains information such as the virtual page number and process ID that the page frame belongs to.
It makes sense when the physical address is smaller than virtual address space
Which three conditions must apply so that external fragmentation can occur for a set
of allocations?
Different allocation lifetimes
Different allocation sizes
No relocation of previous allocations
Name an address space segment that is never part of an ELF file
ELF File
Executable and Linkable Format:
text section, data section, BSS section, symbol table, relocation table, dynamic linking table
Explain a method for the OS to determine that a memory area has been written to when using page-based memory management on x86. Specify the accuracy with which the location, time, and number of accesses can be determined.
Dirty Bit on a write access, the MMU sets the dirty bit in the page table entry (PTE) of the target page. By periodically inspecting and resetting dirty bits, the OS can detect that at least one write access to a page has been taken place since the latest reset. However, it is not possible to derive the exact offset within the page, the number of accesses, or the exact point in time.
Page Faults: If the pages of the respective memory area are write protected, page faults can be used to detect write accesses. However, page faults are much more costly and single-stepping or emulation is needed to allow the attempted write access to actually be performed.This leads to excessive runtime overhead. This method provides the exact addresses, points in time, number of the accesses.
All elements are stored sequentially on separate 4-KiB pages in a hypothetical data structure. To sort the data structure, the virtual addresses of the elements should
be adjusted through the page tables instead of copying the elements back and forth
in memory. Discuss the advantages and disadvantages of this approach
+We only have to adjust two PTEs to exchange two elements in the data structure. This is especially advantageous if the elements are large and we save copy time.
-Since the respective TLB entries have to be invalidated, this method leads to a large number of TLB misses and consecutive page table walks. At the same time, page table structure caches may be less effective as the page tables have been modified.
Name two properties of a forward page table that determine the size of the virtual address space
Number of levels
Size of page
Size of PTEs
What happens to dynamically-allocated memory after program termination, if it has not been freed with free() before
The memory is automatically freed by the OS in the course of releasing the underlying memory pages
What is meant by Bélády’s anomaly
With FIFO page replacement, it is possible to construct a reference string for a number N of page frames that performs worse with N+1 frames
Explain for which allocation pattern it makes sense to use arena allocation. What
advantages does it offer in this case?
Arena allocation is suitable with peak allocation patterns, where many allocations are done without any intermediate frees. Instead, the objects are freed all at once at the end. Using area allocation in this case saves metadata as an allocation is just a pointer increment and the free just returns the whole arena in one call.
How are memory-mapped files basically implemented in an operating system? In
particular, explain how the consistency of the mapping is ensured in the presence of
writes from foreign processes (e.g., with the write() system call).
The OS loads the file into a system-wide file cache in kernel mode. Memory mappings of the file are established by mapping the same cache pages into the respective user address spaces. To guarantee consistency writes via the write() syscall are directed to the cache pages in kernel memory. The OS periodically flushes the data to the actual file on disk to keep the on-disk representation consistent (write-back cache).
Explain two disadvantages of simple base and limit registers compared to segment tables.
- With base and limit registers all memory of a process needs to be contiguous in physical memory, as there is only one pair of registers describing the virtual address space layout. Segments tables, on the other side, can map different areas of physical memory independently.
- Sharing memory is very difficult with base and limit registers as the memory regions have to overlap in physical memory. It becomes impossible to share memory between more than two processes without breaking isolation.
- Base and limit registers generally do not allow to assign specific protections to certain areas of a process.
Why can the heap conceptually act as a stack, but not vice versa?
The lifetime of data in a stack frame is limited to the thread’s execution in the corresponding function.
Give two reasons why it makes sense to maintain CPU-local lists for recently freed memory areas in a memory allocator.
- As lists are CPU-local they do not need synchronization when memory blocks are allocated from them, which allocation faster
- The memory areas are more likely to be hot in the local CPU cache so that accesses do not cause cache misses (even for the first writes)
Explain the advantage of tagging in a TLB.
With tagging support in the TLB, the OS does not have to flush the whole TLB when an address space switch occurs. This allows (some) translations to remain cached in the TLB and reduces the TLB miss rate (and thus memory access latency) when switching between address spaces.
Explain for which scenarios linear and inverted page table types are suitable
Linear page table: It is particularly suited for systems with small or mostly filled virtual address spaces. In these cases, there is no benefit in using multiple levels for translation due to the small size and missing sparseness. Instead, the additional levels only increase translation costs and waste memory.
Inverted page table: It makes sense if the physical address space is considerably smaller than the virtual address space. This way, less memory is wasted on page tables
A process calls fork(). Describe for the parent and the child process, how each address space has to be configured to allow copy-on-write (COW).
Both, the parent and the child processes, map to the same page frames. Therefore, both address spaces need to be write-protected. This way, a write access triggers a page-fault and the OS is invoked, which can create a private copy.
Briefly explain the term ASID.
ASID is the abbreviation for address space identifier and it associates a TLB entry with an address space to avoid having to flush all TLB entries on a context switch.
What is the difference between a software- and a hardware-managed TLB?
The software-managed TLB does not walk the page table in memory on a TLB miss. Instead, the OS has to resolve the TLB miss and manually add the TLB entry.
Explain the terms demand paging and pre-paging. Which method is expected to use more memory? Why can this method nevertheless be advantageous?
With demand paging, pages are loaded into the address space only on their first access. In contrast, pre-paging loads all contents into memory at the process start. Consequently, with pre-paging, the probability is higher that more memory is used. Nevertheless, the method avoids page faults at runtime and can thus be faster.
Give two disadvantages of segment-based memory management compared to page-based memory management.
- Segments need to be kept contiguous in physical memory.
- Segments can only be swapped in and out as a whole.
- Segmentation may suffer from external fragmentation.
An already selected heap page should be swapped out from the address space of process A and made available to process B as a free page. Explain which basic steps are necessary for this operation. Assume that the kernel has its own mapping
of the physical page.
(1) Invalidate user mapping in process A (unset P-bit in corresponding PTE)
(2) Flush TLB entry
(3) Write page to swap file via kernel mapping. Note offset somewhere.
(4) Clear page via kernel mapping
(5) Create new user mapping in process B (configure PTE with correct frame number and set P-bit)
What is meant by the term thrashing?
The system is under heavy memory pressure and busy swapping pages in and out.
CPU utilization is low as processes wait for pages to be fetched from secondary storage.
