DOC PREVIEW
U of I CS 241 - Section Week #9

This preview shows page 1-2-3-4-5-6-39-40-41-42-43-80-81-82-83-84-85 out of 85 pages.

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

Unformatted text preview:

CS 241 Section Week #9 (04/09/09)TopicsLMP2 OverviewSlide 4LMP1 OverviewSlide 6Memory ManagementMemoryFragmentationContiguous AllocationStorage Placement AlgorithmsSlide 12Slide 13Slide 14ExerciseSlide 16Slide 17Slide 18Slide 19Slide 20malloc RevisitedSlide 22Slide 23malloc Revisited (continued)CompactionCompaction (example)PagingPage ReplacementPage Replacement StrategiesPage Replacement AlgorithmsExampleVirtual MemoryWhy Virtual Memory?Slide 34Slide 35Principle of LocalitySlide 37Slide 38Slide 39VM Address TranslationPage TableSlide 42Handling a Page FaultSlide 44Slide 45AddressingSlide 47Slide 48Slide 49Slide 50Address ConversionTranslation Lookaside Buffer (TLB)Slide 53Slide 54Slide 55Slide 56Multilevel Page TablesSlide 58Slide 59Summary: Multi-level Page TablesExample: Two-level Page TableSlide 62Slide 63Slide 64Why use multi-level page tables?Slide 66Slide 67Slide 68Inverted Page TableSlide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Why use inverted page tables?Slide 81Slide 82Summary: Address ConversionSummary: Page TablesSummary: Virtual MemoryCS 241 Section Week #9(04/09/09)Topics•LMP2 Overview•Memory Management•Virtual Memory•Page TablesLMP2 OverviewLMP2 Overview•LMP2 attempts to encode or decode a number of files the following way:–encode: %> ./mmap -e -b16 file1 [file2 ...]–decode: %> ./mmap -d -b8 file1 [file2 ...]•It has the following parameters:–It reads whether it has to encode (‘-e’) or decode(‘-d’);–the number of bytes (rw_units) for each read/write from the file;LMP1 Overview•You have TWO weeks to complete and submit LMP2. We have divided LMP2 into two stages:–Stage 1:•Implement a simple virtual memory.•It is recommended you implement the my_mmap() function during this week. •You will need to complete various data structures to deal with the file mapping table, the page table, the physical memory, etc.LMP1 Overview•You have TWO weeks to complete and submit LMP2. We have divided LMP2 into two stages:–Stage 2•Implement various functions for memory mapped files including:–my_mread() , my_mwrite() and my_munmap()•Handle page faults in your my_mread() and my_mwrite() functions•Implement two simple manipulations on files:–encoding–decodingMemory ManagementMemory•Contiguous allocation and compaction•Paging and page replacement algorithmsFragmentation•External Fragmentation–Free space becomes divided into many small pieces–Caused over time by allocating and freeing the storage of different sizes•Internal Fragmentation–Result of reserving space without ever using its part–Caused by allocating fixed size of storageContiguous Allocation•Memory is allocated in monolithic segments or blocks•Public enemy #1: external fragmentation–We can solve this by periodically rearranging the contents of memoryStorage Placement Algorithms•Best Fit–Produces the smallest leftover hole–Creates small holes that cannot be usedStorage Placement Algorithms•Best Fit–Produces the smallest leftover hole–Creates small holes that cannot be used•First Fit–Creates average size holesStorage Placement Algorithms•Best Fit–Produces the smallest leftover hole–Creates small holes that cannot be used•First Fit–Creates average size holes•Worst Fit–Produces the largest leftover hole–Difficult to run large programsStorage Placement Algorithms•Best Fit–Produces the smallest leftover hole–Creates small holes that cannot be used•First Fit–Creates average size holes•Worst Fit–Produces the largest leftover hole–Difficult to run large programsFirst-Fit and Best-Fit are better than Worst-Fit in terms of SPEED and STORAGE UTILIZATIONExercise•Consider a swapping system in which memory consists of the following hole sizes in memory order: 10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB, and 15KB. Which hole is taken for successive segment requests of (a) 12KB, (b) 10KB, (c) 9KB for–First Fit?Exercise•Consider a swapping system in which memory consists of the following hole sizes in memory order: 10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB, and 15KB. Which hole is taken for successive segment requests of (a) 12KB, (b) 10KB, (c) 9KB for–First Fit? 20KB, 10KB and 18KBExercise•Consider a swapping system in which memory consists of the following hole sizes in memory order: 10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB, and 15KB. Which hole is taken for successive segment requests of (a) 12KB, (b) 10KB, (c) 9KB for–First Fit? 20KB, 10KB and 18KB–Best Fit?Exercise•Consider a swapping system in which memory consists of the following hole sizes in memory order: 10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB, and 15KB. Which hole is taken for successive segment requests of (a) 12KB, (b) 10KB, (c) 9KB for–First Fit? 20KB, 10KB and 18KB–Best Fit? 12KB, 10KB and 9KBExercise•Consider a swapping system in which memory consists of the following hole sizes in memory order: 10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB, and 15KB. Which hole is taken for successive segment requests of (a) 12KB, (b) 10KB, (c) 9KB for–First Fit? 20KB, 10KB and 18KB–Best Fit? 12KB, 10KB and 9KB–Worst Fit?Exercise•Consider a swapping system in which memory consists of the following hole sizes in memory order: 10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB, and 15KB. Which hole is taken for successive segment requests of (a) 12KB, (b) 10KB, (c) 9KB for–First Fit? 20KB, 10KB and 18KB–Best Fit? 12KB, 10KB and 9KB–Worst Fit? 20KB, 18KB and 15KBmalloc Revisited•Free storage is kept as a list of free blocks–Each block contains a size, a pointer to the next block, and the space itselfmalloc Revisited•Free storage is kept as a list of free blocks–Each block contains a size, a pointer to the next block, and the space itself•When a request for space is made, the free list is scanned until a big-enough block can be found–Which storage placement algorithm is used?malloc Revisited•Free storage is kept as a list of free blocks–Each block contains a size, a pointer to the next block, and the space itself•When a request for space is made, the free list is scanned until a big-enough block can be found–Which storage placement algorithm is used?•If the block is found, return it and adjust the free list. Otherwise, another large chunk is obtained from the OS and linked into the free listmalloc Revisited (continued)typedef long Align; /* for alignment to long */union header { /* block header */ struct { union


View Full Document

U of I CS 241 - Section Week #9

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 Section Week #9
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 Section Week #9 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 Section Week #9 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?