DOC PREVIEW
U of I CS 241 - Memory Management 2

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Memory Management 2OutlineContiguous AllocationCompactionCompaction (example)Review: PagingReview: Virtual MemoryPage ReplacementPage Replacement StrategiesPage Replacement AlgorithmsClock Explained..Clock ExampleReplacement ExampleProblem 1Slide 15Page Tables and Address TranslationReview: Page TablesMulti-level Page TablesExample: Two-level Page TableWhy use multi-level page tables?Inverted Page TableExampleImplementationWhy use inverted page tables?RecapMemory Management 2CS241 Discussion Section Fall 2007Week 12OutlineContiguous allocation and compactionPaging and page replacement algorithmsPage tables, address translationContiguous 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 UsedReplace what you brought in When would this be useful?LFU: Least Frequently Used Replace the page that is used least often Clock: “Second chance” policyReplace a page that hasn’t been used since it was last checkedClock Explained..View pages as a circular FIFO list, with pointer just after most recently placed pageProvide an access flag on each page (one extra bit per page)•When a page is placed or accessed, set the bit to 1•When a new page needs to be placed, search (starting from the pointer) for a page with access bit 0, setting each 1 to 0 as you pass. If none found, default to the pointer page.•After placing a page, advance the pointer to just after most recently placed page.Clock ExampleReplacement ExamplePageAccesses0 1 2 3 4 5 4 3 2 1 3 2 1 0 2 2 1Optimal- - - - 0 1 - - - 4 - - - 5 - - -FIFO - - - - 0 1 - - - 2 - 3 - 4 - - -LRU - - - - 0 1 - - - 5 - - - 4 - - -LFU - - - - 0 1 - - - 5 - - - 4 - - -MRU - - - - 3 4 5 4 - - - - - - - - -Physical memory contains 4 pages. Each table entry shows which page is evicted to make room for the new page.Problem 1PageAccesses0 1 2 3 4 1 3 4 4 5 3 1 2 0 4 5 4Optimal- - - - 0 - - - - 4 - - - 3 2 - -FIFO - - - - 0LRU - - - -LFU - - - -MRU - - - -Clock - - - -Fill in this table with the correct page evictions.There are still 4 page frames.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)0123456 Index 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


View Full Document

U of I CS 241 - Memory Management 2

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download Memory Management 2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Memory Management 2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Memory Management 2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?