DOC PREVIEW
U of I CS 241 - System Programming Memory Management

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 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 26 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 26 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 26 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 26 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 26 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS241 System ProgrammingMemory Management (II)ContentAdministrativeReviewHow Bad Is Fragmentation?FragmentationFragmentationFragmentationEstimates of FragmentationDerivation of Unused Memory Rule EstimateDerivation of Unused MemoryEstimates of FragmentationQuestionsVirtual MemoryBenefits of Virtual MemoryPaging RequestPagingPagingPagingPagingPage Mapping HardwarePage FaultPaging IssuesVirtual-to-Physical LookupsSummaryCS241 System ProgrammingMemory Management (II)Klara NahrstedtLecture 294/5/20064/5/2006CS 241 - System Programming, Klara Nahrstedt2Content z Fragmentationz Virtual Memoryz Paging4/5/2006CS 241 - System Programming, Klara Nahrstedt3Administrative z MP4 is posted, due April 17, 2006z Quiz 8 is April 7, 2006Reviewz Memory Manager– Monitor used and free memory– Allocate memory to processes– Reclaim (De-allocate) memory– Swapping between main memory and diskz Mono-programming memory management– Overlayz Multi-programming memory management– Fixed partition, Variable partition– Relocation and protection4/5/2006CS 241 - System Programming, Klara Nahrstedt5How Bad Is Fragmentation?z Statistical arguments - Random sizesz First-fitz Given N allocated blocksz 0.5∗N blocks will be lost because of fragmentationz I.e. 33% of memory may be unusable!!!z Known as 50% RULEz Let’s look at the derivation of the 50% rule4/5/2006CS 241 - System Programming, Klara Nahrstedt6Fragmentationz consider a system in equilibrium– the insertion rate is the same as the deletion rate.z what can be said about memory usage?4/5/2006CS 241 - System Programming, Klara Nahrstedt7Fragmentation4/5/2006CS 241 - System Programming, Klara Nahrstedt8Fragmentation8 segments8 segments4 holes4 holes4/5/2006CS 241 - System Programming, Klara Nahrstedt9Estimates of Fragmentationz 50% rule – if the system has an average of n segments and h holes, where n and h are large: – i.e. there are approximately half as many holes as segments in memory 2nh ≅4/5/2006CS 241 - System Programming, Klara Nahrstedt10Derivation of Unused Memory Rule Estimatez Let be f the fraction of memory occupied by holes. z Let be SSthe average segment sizez Let the average hole size be at least Sh. The ratio of hole size to segment sizeSsSesegmentsizholesizekh≥=4/5/2006CS 241 - System Programming, Klara Nahrstedt11Derivation of Unused Memory2+=+××≥×+××=×+××==kknkhkhSSnSShSShSnShShytotalmemorlesmemoryinhofSSShShShh4/5/2006CS 241 - System Programming, Klara Nahrstedt12Estimates of Fragmentationusing the 50% rulez it is impossible to use all of central memory,– f > 0z simulation indicates f can be made about 10%2+≥kkf4/5/2006CS 241 - System Programming, Klara Nahrstedt13 Memory Utilization00.050.10.150.20.250.30.350.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1K Ratio of Hole to Segment Sizef Fraction Unused Memory4/5/2006CS 241 - System Programming, Klara Nahrstedt14Questionsz What schemes could be used to overcome fragmentation?z What does the use of secondary storage for swap space imply about memory organization?Virtual Memoryz Provide user with virtual memory that is as big as user needsz Store virtual memory on diskz Cache parts of virtual memory being used in real memoryz Load and store cached virtual memory without user program interventionBenefits of Virtual Memoryz Use secondary storage($)– Extend DRAM($$$) with reasonable performancez Protection– Programs do not step over each otherz Convenience– Flat address space– Programs have the same view of the world– Load and store cached virtual memory without user program intervention z Reduce fragmentation: – make cacheable units all the same size (page)z Remove memory deadlock possibilities:– permit pre-emption of real memoryPaging Request3 1234DiskMemoryVirtual Memory Stored on Disk12 34 5 6 7812341234Page TableVM FrameReal MemoryRequest Page 3Paging3 11 234DiskMemoryVirtual Memory Stored on Disk12 34 5 6 7812341234Page TableVM FrameReal MemoryRequest Page 1Paging3 116234DiskMemoryVirtual Memory Stored on Disk12 34 5 6 7812341234Page TableVM FrameReal MemoryRequest Page 6Paging3 116234DiskMemoryVirtual Memory Stored on Disk12 34 5 6 7812341234Page TableVM FrameReal MemoryRequest Page 22Paging3 16234DiskMemoryVirtual Memory Stored on Disk12 34 5 6 7812341234Page TableVM FrameReal Memory2Load Page 8 to Memory88Page Mapping HardwareContents(4006)Contents(5006)004 006005 0064→50101101Page TableVirtual MemoryPhysical MemoryVirtual Address (004006)Physical Address (F,D)0040050060064Page size 1000Number of Possible Virtual Pages 1000Number of Page Frames 8Page Faultz Access a virtual page that is not mapped into any physical page– A fault is triggered by hardwarez Page fault handler (in OS’s VM subsystem)– Find if there is any free physical page availablez If no, evict some resident page to disk (swapping space)– Allocate a free physical page– Load the faulted virtual page to the prepared physical page– Modify the page tablePaging Issuesz Page size is 2n– usually 512 bytes, 1 KB, 2 KB, 4 KB, or 8 KB– E.g. 32 bit VM address may have 220(1 MB) pages with 4k (212) bytes per pagez Page table:– 220page entries take 222bytes (4 MB)– page frames must map into real memory– Page Table base register must be changed for context switchz No external fragmentation; internal fragmentation on last page onlyVirtual-to-Physical Lookupsz Programs only know virtual addresses– The page table can be extremely largez Each virtual address must be translated– May involve walking hierarchical page table– Page table stored in memory– So, each program memory access requires several actual memory accessesz Solution: cache “active” part of page table– TLB is an “associative memory”4/5/2006CS 241 - System Programming, Klara Nahrstedt26Summary z Fragmentation needs to be minimizedz Virtual memory is a great concept, enlarges the memory space that the users/programs can use z Pages, Page Tables, Page Table Hardware are important conceptsz Virtual to Physical address translation must be done fast and


View Full Document

U of I CS 241 - System Programming Memory Management

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 System Programming Memory Management
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 System Programming Memory Management 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 System Programming Memory Management 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?