Flashcards
SCC 211 - Memory Management
Cards in this deck (58)
- 1When does a process need entries?A process only needs entries for the memory it uses
- 2A virtual page can (in theory) be mapped to ANY physical frame, what order does the physical frame have to be in?– The physical frames for a process
• Could be in any order
• Need not be consecutive in memory - 3What happens if a process attempts to access a location not mapped in it's page tables?– Get a PAGE FAULT exception
• Kernel Page Fault handler called - 4As stack and heap expand, what happens to pages and how can this be handled?– More pages added as
new memory frames
referenced in code
Easily handled by
handling Page Faults and
Demand Paging - 5How do you start demanding paging?Start process with partial or even an empty Page Directory
Reference to unallocated memory will cause a PAGE FAULT
Page Fault Handler
Re run last instruction - 6Alternative manual procedure to page fault handler?creates Page Table and attaches it to Page Directory
– Allocates memory or, retrieves code or data from disk - 7What happens before a page fault and after a page fault?Kernel allocates
memory and
Page Table Entry - 8Can you summarise the flow of memory management?Process virtual memory -> Page Table -> Physical Memory -> Secondary store.
- 9Which is larger, virtual memory or physical memory?Virtual memory is larger than physical memory
- 10Benefit of paging in relation to physical memory access?Paging used to replace pages
in physical memory as needed - 11What happens if a page is present within a page table?If page is Present, Page Table/ Directory Entry references a valid frame in memory.
- 12What happens if a page is not present within a page table?If NOT Present, no frame allocated
to page – Page Table Entry free for storing disk reference/ address or other useful data. - 13Describe the page frame replacement process?1. Take Page Fault
2. If we have a free/ empty frame available in memory
– Select for use
Else
– Identify a victim frame
3. Write (swap out) current content of victim to disk
– Adjust Page Tables: Mark victim as not present/ invalid
4. Read requested page from disk into identified frame
– Adjust Page Tables: Mark new page entry as present
5. Restart process - 14What should we do if a page is not dirty?If page is NOT Dirty, no need to write to disk.
Disk copy will still have same content. - 15How can you speed up replacement?1. Keep at least one free page
– Use this page and restart process
– Then write next victim to disk and move to free list
2. Keep write queue of pages (likely victims)
– Use any idle time to perform writes, freeing pages
– Retain reference to pages on write queue
• If process tries to re-access, rescue page - 16Assumptions when selecting a victim for page replacement?– Processes don’t access all code/ data all the time
– Given a time period Δ / number of page references
Each process will have a working set (WS) of pages
• Locality of Reference suggests we’ll keep accessing same pages - 17What is locality of reference?In computer science, locality of reference, also known as the principle of locality, is a term for the phenomenon in which the same values, or related storage locations, are frequently accessed, depending on the memory access pattern.
- 18List the two types of locality of reference?Temporal and Spacial Locality
- 19What is temporal locality?Temporal locality refers to the reuse of specific data, and/or resources, within a relatively small time duration.
- 20What is spatial locality?Spatial locality refers to the use of data elements within relatively close storage locations.
- 21Different types of victim/frame allocation methods?First-In First-Out (FIFO)
Least Recently Used (LRU)
Accessed Pages
Practical Least Frequently Used
Clock Algorithm
Working set replacement - 22Describe the problem of the first in first out approach?• First pages likely to hold key parts of process
– Libraries
– Globals
etc. - 23Describe the least recently used approach?• Replace page not used for longest time
- 24How could the least recently used be implemented?– Keeping a count of total number of page accesses
– Keeping (doubly-linked list) stack of page references - 25Can you expand on how to keep a count of total number of page accesses• On each page access, update page details with counter value
• Least Recently Used page will have smallest counter value - 26Can you expand on how to Keep (doubly-linked list) stack of page references• On each page reference, move page to top of stack
• Least Recently Used page reference at bottom of stack - 27Problem with least recently used frame allocation method?• The level of hardware needed is expensive and rarely available
- 28How can we use access bit to get indication of access frequency?Accessed bit set whenever address in page referenced. By regularly resetting accessed bits in Page Tables we can get indication of
access frequency. - 29Can you describe the practical least frequency used approach to frame allocation?• Regularly shift Accessed Bit into byte per entry table
– Lowest value in shift ‘registers’ represents LFU page
– Clear Accessed bit on shift - 30What does the clock algorithm look to avoid?• Refinement of ‘Second Chance Algorithm’
– Avoids shuffling pages on list - 31Via the use of clock algorithm, what happens when a page fault occurs?– If accessed bit set:
• Clear bit, try next
– If accessed bit clear
• Replace page
• Advance pointer - 32Via the use of working set replacement, what happens to a page that is not in working set?• Pages not in working set
– Marked to be written out
– Then available for replacement - 33Each process has page fault frequency, what does low and high represent?Low: Working Set may be too large
– High: Working Set too small
• Consider swapping an entire process out to free pages
Argument for keeping this information between runs - 34How often should periodic update be over working set calculated?Periodic update should be at least twice
period over which working set calculated - 35Two memory allocation methods?Equal allocation
Proportional allocation - 36Describe the equal allocation method?• Could divide memory equally among n processes
– Equal allocation
– Each process gets m/n frames, for memory size m
– Unfair as processes will have different requirements - 37Describe the proportional allocation method?• Better to allocate based on size of processes
– Proportional allocation
– For processes pi of size si
, where i = 1..n
– Total size S will be: S = Σ si
– Allocation ai
for pi will be: ai = si
/ S * m frames - 38What is thrashing?In a virtual storage system (an operating system that manages its logical storage or memory in units called pages), thrashing is a condition in which excessive paging operations are taking place. A system that is thrashing can be perceived as either a very slow system or one that has come to a halt.
- 39With thrashing, what happens if a process is allocated too few frames?• If a process is allocated too few frames
– Experience high number of page faults
– CPU utilisation drops sharply – spend time paging in/ out - 40How can we limit thrashing?Limit thrashing by using local replacement algorithm
– Process cannot take frames from another
• A global replacement algorithm can take frame from any process
– Thus, thrashing can’t extend from one process to another - 41State some issues with accessing memory zones?– Some hardware can only access subset of main memory
– Some memory may not be fast enough for all operations - 42In relation to partitioning memory into zones, when should we only allocate memory from special zones?– Only allocate memory from ‘special’ zones if we have to
• Request for frame accessible by specific hardware
• No other frames available – may be better to reject such requests - 43Some hardware expect contiguous physical memory, how can this be ensured?– Must allocate adjacent memory frames (physical ‘pages’)
- 44When might we want to use a non page based allocation?• Can’t allocate whole page for every request
– Only makes sense when request almost size of a page
– Need mechanisms to allocate small areas of memory within a
set of pages - 45When processes may need memory area larger than one page, what may they need to ensure this?• Sometimes need memory area larger than one page
– May need these to be contiguous in physical memory
• Common requirement for kernel and I/O data structures
– Need to allocate pages as a group
• Then allocate from group - 46Problem with allocated regions?No protection between allocated regions
- 47Idea of buddy allocation?Idea is that a memory block can be split in two
– Two buddies
• Likewise, two buddies can be combined
– Reforming original larger block - 48How many bytes are each buddy?• Each buddy 2n bytes
- 49What properties does the initial state of buddy allocation have?• Single reference to full memory region being managed
• Region MUST be 2n
in size - 50Can you describe the bitmap allocation method?• Rather than maintaining a list
– Often keep (bit based) allocation map
• Compact and fast to search for free entries - 51With integer/arithmetic/shifts, how can we find parent and children?– Parent: [n/2]
– Children: 2n and 2n + 1 - 52What does flipping one bit in block address allow to happen?• Note that flipping one bit in a block address will give address of block’s buddy
- 53Problem of buddy allocation?• Suffers from internal fragmentation …we know this is bad
– Must round up any request to next block size
– With larger blocks this can add significant overhead - 54Describe a better approach to buddy in relation to slabs?• Better approach (introduced in Sun* Solaris)
– Allocate memory for group of objects in one go
– Use buddy allocator for a slab = n × object-size
– Manage allocation of objects internally
• Slab allocator - 55Can you describe the slab allocation process?More generally, allocate common memory sizes
– For efficiency, slabs normally multiple pages in size
– Objects of similar size share slabs - 56What is slab allocation?Slab allocation is a memory management mechanism intended for the efficient memory allocation of kernel objects. It eliminates fragmentation caused by allocations and deallocations. ... It is analogous to an object pool, but only applies to memory, not other resources.
- 57How does combined buddy and slab allocation allocate?• Allocate large (multi-page) areas using buddy
• Sub-divide areas into common sizes using slab - 58How are objects allocated to best slab based on?• Object size
• Memory word or cache alignment
– Many processors require base types to be word aligned
– Don’t want object split across cache lines (if we can avoid it)
• Any inter-object (guard) spacing to catch write overruns
Information
- Description
- Flashcards on SCC 211 - Memory Management, created by Ayo Olutobi on 19/03/2017.
- Created by
- Ayo Olutobi
- Views
- 0
- Rating