CS 241 System Programming Virtual MemoryOutlineCompactionCompaction (example)PagingVirtual MemoryPage TableHandling a Page FaultAddressingSlide 10Address ConversionMultilevel Page TablesMore AddressingPage Replacement PoliciesPage Replacement StrategiesSummaryCS 241 System ProgrammingVirtual MemoryDiscussion Section 1010 April – 13 AprilOutlineMP4 CompactionUses of Virtual MemoryVirtual Memory AddressingExamplesPage Replacement AlgorithmsCompactionAfter numerous MyMalloc and MyFree calls, our memory will have many holesTotal free memory is much greater than that of any contiguous chunkAnd for MP4 we’re just doing contiguous allocations, not any kind of pagingWe should compact our memoryShift all allocations to one end of memory, and all holes to the other endTemporarily rids of external fragmentationCompaction (example)Lucky that A fit in there, may want to compact at (d), (e), or (f)Sadly, compaction is very costlyHow costly?How else can we eliminate external fragmentation?PagingDivide memory into pages, all 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 allProcess 4 may be using pages 3, 12, and 89Virtual MemoryRAM is expensive (and fast)Disk is cheap (and slow)Need to find a way to use the cheaper memoryStore memory that isn’t frequently used on disk“Swap”Still uses pagesProcess 3 (running) uses pages 1, 5, and 19Process 4 (suspended) uses pages 3, 12, and 89If we only can fit 4 pages in RAM, which should be there?Page TableKeeps track of what pages are in memoryProvides a mapping from virtual address to physical addressHandling a Page FaultSuspend process 3, run process 4Process 4 wants all of its pagesHow do we get these back into memory?Page faultLook for an empty page in RAMMay need to write a page to disk and free itLoad the faulted page into that empty pageModify the page tableAddressingSystem has 64MB RAM (2^26)We have 32bit addressesSo we can address up to 2^32 bytes of memory(some 32bit systems use 64bit memory)Page size of 4KB (offset of 4KB)Using 31bits, how large can memory be?How many bits for page address? How many for offset?Addressing64MB RAM (2^26)2^31 (2GB) total memory4KB page size (2^12)So we need 2^12 for the offset, we can use the remainder bits for the page19 bits, we have 2^19 pages (524288 pages)Virtual Page number (19 bits) Page offset (12 bits)Virtual Address (31 bits)Address ConversionThat 19bit page address can be optimized in a variety of waysTranslation Look-aside Bufferm – memory cycle, - hit ratio, - TLB lookup timeEffective access time (Eat)Eat = (m + )(2m + )(1 – ) = 2m + – mMultilevel Page TableSimilar to indirect pointers in I-nodesSplit the 19bits into multiple sectionsInverted Page TableMuch smaller, but is slower and more difficult to lookupMultilevel Page Tables20 bits of page addressingFirst 10 indexes the top-level page tableThen we follow the pointer and index that tableUse the second 10 bits to find out the actual physical addressLoad page into memory accordinglyMore AddressingGet comfortable with these calculations128MB RAM, 16KB page size32bit addresses, use all bits1GB RAM, 128KB page size64bit addressesonly use 40 of the 64 bits for addressesHow large of a chunk of hard disk do we need to set aside in each of these cases?Page Replacement PoliciesNot every process can have their pages in memory at a timeBut whose shall we keep?Optimal – last to be used next = removed firstFIFO – Inserted first = removed firstLRU – used least recently = removed firstNRU – approximation using bit shiftingSecond chance – approximation using single bitWould also be useful to know the dirty pagesPage Replacement StrategiesTakes two disk operations to replace a dirty pageWe keep track of dirty bits, so we should attempt to replace clean pages firstWrite dirty pages to disk during idle disk timeThen we can clear the dirty bitNeed to approximate optimal strategy, but can’t because we never know what order a process will use its pagesBest we can do is run a program multiple times, and track what memory it usesSummarySlow to use contiguous allocations + compactionVery fast (and only one extra lookup) to use virtual memoryCan also address a much larger space than we have physical memoryNo external fragmentationUse the right page replacement
View Full Document