Virtual MemoryCS241 Discussion Section Week 104/09/07 – 4/15/07OutlineDebugging memory allocationContiguous allocation and compactionPaging and page replacement algorithmsPage tables, address translationDebugging Memory AllocationWith LMP2, we have learned how to implement dynamic memory allocation similar to malloc()/free() in C.Problem: it is very easy to go outside of the allocated space by accident, and errors often do not show up immediately.Example:int *ptr = (int *)malloc(100);for (i = 0; i < 100; i++)ptr[i] = i;What’s wrong with this code? How can we help the programmer detect and avoid such errors?Debugging Memory AllocationChange malloc() and free() implementations to check for such errors.malloc(): allocate extra space on both sides of the requested allocation, and fill this memory with a pattern (called guard)free(): check that the guards have not been overwritten, otherwise indicate an errorProblem: Implement a Debugging MMdebug.c provides you with a very simple memory manager, similar to the one in LMP2.Change myAlloc() and myFree() functions to check for out of bounds memory accessesNote: similar, but more thorough and efficient techniques are used in practice.See, for example, the Electric Fence memory debugger by Bruce Perens.Memory OrganizationHow is program data is loaded and stored in memory?Contiguous AllocationMemory is allocated in monolithic segments or blocksPublic enemy #1: external fragmentationWe can solve this by periodically rearranging the contents of memoryCompactionAfter numerous malloc() and free() calls, our memory will have many holesTotal free memory is much greater than that of any contiguous chunkWe can compact our allocated memoryShift all allocations to one end of memory, and all holes to the other endTemporarily eliminates of external fragmentationCompaction (example)Lucky that A fit in there! To be sure that there is enough space, we may want to compact at (d), (e), or (f)Unfortunately, compaction is problematicIt is very costly. How much, exactly?How else can we eliminate external fragmentation?Review: PagingDivide memory into pages of equal sizeWe don’t need to assign contiguous chunksInternal fragmentation can only occur on the last page assigned to a processExternal fragmentation cannot occur at allNeed to map contiguous logical memory addresses to disjoint pagesReview: Virtual MemoryRAM is expensive (but fast), disk is cheap (but slow)Need to find a way to use the cheaper memoryStore memory that isn’t frequently used on diskSwap pages between disk and memory as neededTreat main memory as a cache for pages on diskPage ReplacementWe may not have enough space in physical memory for all pages of every process at the same time.But which pages shall we keep?Use the history of page accesses to decideAlso useful to know the dirty pagesPage Replacement StrategiesIt takes two disk operations to replace a dirty page, so:Keep track of dirty bits, attempt to replace clean pages firstWrite dirty pages to disk during idle disk timeWe try to approximate the optimal strategy but can seldom achieve it, because we don’t know what order a process will use its pages.Best we can do is run a program multiple times, and track which pages it accessesPage Replacement AlgorithmsOptimal: last page to be used in the future is removed firstFIFO: First in First Out Based on time the page has spent in main memoryLRU: Least Recently Used Locality of reference principle againMRU: most recently used = removed firstWhen would this be useful?LFU: Least Frequently Used Replace the page that is used least oftenExamplePhysical memory size: 4 pagesPages are loaded on demandAccess history: 0 1 2 3 4 0 1 2 3 4 …Which algorithm does best here?Access history: 0 1 2 3 4 4 3 2 1 0 …And here?Page Tables and Address TranslationMatching virtual addresses to physical memory locationsReview: Page Tables64kB logical address space8 pages * 4kB == 32kB RAM16-bit virtual address consists of:Page number (4 bits)Page offset (12 bits)Virtual page number – table indexPhysical frame number – valuePresent bit – is page in memory?Multi-level Page TablesInstead of one large table, keep a tree of tablesTop-level table stores pointers to lower level page tablesFirst n bits of the page number == index of the top-level page tableSecond n bits == index of the 2nd-level page tableEtc.Example: Two-level Page Table32-bit address space (2GB)12-bit page offset (4kB pages)20-bit page addressFirst 10 bits index the top-level page tableSecond 10 bits index the 2nd-level page table10 bits == 1024 entries * 4 bytes == 4kB == 1 pageNeed three memory accesses to read a memory locationWhy use multi-level page tables?Split one large page table into many page-sized chunksTypically 4 or 8 MB for a 32-bit address spaceAdvantage: less memory must be reserved for the page tablesCan swap out unused or not recently used tablesDisadvantage: increased access time on TLB missn+1 memory accesses for n-level page tablesInverted Page Table“Normal” page tableVirtual page number == indexPhysical page number == valueInverted page tableVirtual page number == valuePhysical page number == indexNeed to scan the table for the right value to find the indexMore efficient way: use a hash tableExample1010 110100 11010100101101Page TableVirtual Address (1010110)Physical Address (100110)Index == 4 (100)0123456Index Present Virtual AddrImplementationTLB is same as beforeTLB miss is handled by softwareIn-memory page table is managed using a hash tableNumber of entries ≥ number of physical framesNot found: page faultHash tableVirtual pagePhysical pageWhy use inverted page tables?One entry for each page of physical memoryvs. one per page of logical address spaceAdvantage: less memory needed to store the page tableIf address space >> physical memoryDisadvantage: increased access time on TLB missUse a hash table to limit the search to one – or at most a few extra memory accessesRecapDebugging memory allocationContiguous allocation + compaction: slowPaged virtual memoryCan address a much larger space than we have physical memoryNeed to replace pages loaded in memory using an appropriate replacement algorithmAddress translationMulti-level and inverted page
View Full Document
Unlocking...