Memory Management Flashcards
Explain the concept of a memory hierarchy
Few MB of volatile quickly accessible expensive cache memory
Few GB of volatile medium speed medium expense main memory
Few TB of nonvolatile slow speed cheap disk memory
(May also have removable storage)
How can multiple programs be run at the same time with no memory abstraction?
OS saves entire contents of memory to a disk file then brings in and runs next program. This works so long as there is only one program in memory at a time.
Explain memory addresses
A memory address is a memory abstraction. These are fixed length sequences of digits. This means memory location 28 in 1 program will be different to that in the memory address of another
What are the base and limit registers used for? What is a disavantage?
Base register contains the physical address where program begins in memory (tells you how far offset actual address is_ and limit register has the length of the program. Access is aborted if memory trying to be accessed is greater than or equal to limit register. The disadvantage is having to perform addition and comparison on every memory address.
What approaches have been developed to deal with memory overload?
1) swapping: bringing each process into memory in its entirety, running for a time then swapping it out
2) virtual memory: allows programs to run even when they are only partially in main memory
Explain swapping
Bringing each process into memory in its entirety, running for a time then swapping it out to disk. If a dynamically sized process needs more space, but cannot grow and swap area on disk is full, this process will have to be temporarily suspended or killed
Is memory compaction done often?
No, as it requires a lot of CPU time
Who manages dynamically assigned memory?
The OS
How can we keep track of memory usage?
1) Bitmap
2) Free lists
Explain memory management with bitmaps. What is the disadvantage of them?
Memory is divided into allocation units with each unit having a corresponding bit (0 if free, 1 if full or vice versa).
The disadvantage is that if something of size k units enters, k consecutive 0 bits must be found which is a long operation
Explain memory management with linked lists
Each entry in the linked list is either a hole or a process (H or P). These are sorted by address. Multiple holes in a row are combined into one.
Explain the first fit algorithm
Memory manager scans along until a hole of big enough size is found. This is fast as limited searching needs to be done
Explain the next fit algorithm
This starts searching the list at the place it last left off, rather than the start, to find a hole of big enough size
Explain the best fit algorithm
Best fit searches entire list and takes the smallest adequate hole. Best fit is slower than first fit as it searches entire list. This results in wasted memory as it leaves lots of little holes, which nothing can fit in. Best fit and first fit can be same time if the list is only a list of holes (not processes)
Explain the worst fit algorithm
Worst fit searches entire list and takes biggest hole, such that breaking it up will cause large holes to be left.
Explain the quick fit algorithm
Maintains separate lists for holes of different but common sizes. Merges can be expensive
What are the memory allocation algorithms?
1) First fit
2) Next fit
3) Best fit
4) Worst fit
5) Quick fit
What solutions are available to the problem of having programs larger than memory?
1) Breaking programs into overlays
2) Virtual memory
Explain the concept of virtual memory
Only parts of program have to be in main memory at once.
Each program has an address space broken into chunks (contiguous range of addresses) called pages. Pages are mapped onto physical memory, but not all pages have to be in memory to run. When program references part of address space that isn’t in physical memory, the OS will retrieve this piece and reexecute instruction after a page fault occurs.
This means that pages do not have to be in contiguous memory sections themselves.
This is the illusion that the user has all of the memory for their process. This should solve the problem of external fragmentation
Explain paging
This is a technique used by virtual memory systems. In this, pages are stored on disk and retrieved by OS in the case of a page fault when required. Whole pages must be sent, not parts.
What are virtual addresses?
Each program has a virtual address space
What happens to virtual addresses on computers without virtual memory? What about computers with virtual memory?
Without: Virtual address is put directly onto memory bus, causing physical memory word with same address to be read/written
With: Virtual address goes to MMU that maps virtual addresses onto physical memory addresses
With 64KB of virtual address space and 32KB of physical memory, if we get 16 virtual pages, how many page frames will there be?
- This means only 8 of the virtual pages are mapped onto physical memory at a time. Present/absent bit keeps track of which pages are physically present in memory.
What does the present/absent or valid bit do?
Present/absent bit keeps track of which pages are physically present in memory in the case of virtual memory being used
Explain the mapping of virtual addresses onto physical addresses
Virtual address is split into virtual page number (high-order bits) and an offset (low-order bits). The virtual page number is used as an index into page table to find entry for that virtual page.
Describe the structure of a page table entry
Page frame number followed by present/absent or valid bit, followed by protection, followed by modified, followed by referenced, followed by caching disabled
What does protection do in a page table entry?
Tells what kind of accesses are permitted. Normally this will be 2 bits: 0 for read/write, 1 for read only. This could be 3 bits however with read/write, read only and executing the page
What does modified do in a page table entry?
Keeps track of page usage. This bit tells whether the page has been modified. When page is loaded back to disk, if it hasn’t been modified (clean) the version on disk doesn’t need to be altered. If this is a dirty bit, it must be reloaded to disk.
What does referenced bit do in a page table entry?
This tells whether the page is being used or not in the case of swapping out for a page fault. If page fault occurs, it would be wiser to swap out pages not being referenced.
What does caching disabled bit do in a page table entry?
This allows caching to be disabled for the page
What are the 2 major issues faced in paging?
1) Mapping from virtual to physical addresses must be fast
2) If virtual address space is large, the page table will be large
Explain how the TLB works
When MMU needs to translate virtual memory address, the hardware checks to see if virtual memory address is in TLB. The page frame is taken directly from TLB (no need to visit the page table).
If the virtual memory address isn’t in the TLB, the MMU will look up the page in the page table, and evict an entry in TLB, replacing it with this memory address. The alternative would be to hand control to OS to locate this page.
This is a sort of memory cache holding recently accessed page table entries.
How do we process a TLB miss?
Go to page table and perform indexing operations to locate page being referenced
What’s the difference between a hard miss and soft miss?
Hard: when page isn’t in memory or TLB
Soft: when page isn’t in TLB, but is in memory
What 2 types of TLB misses are there?
Hard: when page isn’t in memory or TLB
Soft: when page isn’t in TLB, but is in memory
What page tables are available for large memories?
1) Multilevel page table
2) Inverted page table
What is the address in a paged system?
page number ∗ page size + offset where page size is 2 raised to the power of the number of bits in the offset
To map to physical page frame: take new page fram * page size (same as above) + offset (same as above)
What is the goal of memory management?
Abstraction
Keep track of what parts of memory are free and what parts aren’t