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

This preview shows page 1-2-3-4-5 out of 16 pages.

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

Unformatted text preview:

CS 241 System ProgrammingVirtual MemoryDiscussion Section 1010 April – 13 AprilOutline MP4 Compaction Uses of Virtual Memory Virtual Memory Addressing Examples Page Replacement AlgorithmsCompaction After numerous MyMalloc and MyFree calls, our memory will have many holes Total free memory is much greater than that of any contiguous chunk And for MP4 we’re just doing contiguous allocations, not any kind of paging We should compact our memory Shift all allocations to one end of memory, and all holes to the other end Temporarily rids of external fragmentationCompaction (example) Lucky that A fit in there, may want to compact at (d), (e), or (f) Sadly, compaction is very costly How costly? How else can we eliminate external fragmentation?Paging Divide memory into pages, all of equal size We don’t need to assign contiguous chunks Internal fragmentation can only occur on the last page assigned to a process External fragmentation cannot occur at all Process 4 may be using pages 3, 12, and 89Virtual Memory RAM is expensive (and fast) Disk is cheap (and slow) Need to find a way to use the cheaper memory Store memory that isn’t frequently used on disk “Swap” Still uses pages Process 3 (running) uses pages 1, 5, and 19 Process 4 (suspended) uses pages 3, 12, and 89 If we only can fit 4 pages in RAM, which should be there?Page Table Keeps track of what pages are in memory Provides a mapping from virtual address to physical addressHandling a Page Fault Suspend process 3, run process 4 Process 4 wants all of its pages How do we get these back into memory? Page fault Look for an empty page in RAM May need to write a page to disk and free it Load the faulted page into that empty page Modify the page tableAddressing System has 64MB RAM (2^26) We have 32bit addresses So 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?Addressing 64MB RAM (2^26) 2^31 (2GB) total memory 4KB page size (2^12) So we need 2^12 for the offset, we can use the remainder bits for the page 19 bits, we have 2^19 pages (524288 pages)Virtual Address (31 bits)Virtual Page number (19 bits) Page offset (12 bits)Address Conversion That 19bit page address can be optimized in a variety of ways Translation Look-aside Buffer m – memory cycle, α-hit ratio, ε- TLB lookup time Effective access time (Eat) Eat = (m + ε)α + (2m + ε)(1 –α) = 2m + ε–mα Multilevel Page Table Similar to indirect pointers in I-nodes Split the 19bits into multiple sections Inverted Page Table Much smaller, but is slower and more difficult to lookupMultilevel Page Tables 20 bits of page addressing First 10 indexes the top-level page table Then we follow the pointer and index that table Use the second 10 bits to find out the actual physical address Load page into memory accordinglyMore Addressing Get comfortable with these calculations 128MB RAM, 16KB page size 32bit addresses, use all bits 1GB RAM, 128KB page size 64bit addresses only use 40 of the 64 bits for addresses How large of a chunk of hard disk do we need to set aside in each of these cases?Page Replacement Policies Not every process can have their pages in memory at a time But whose shall we keep? Optimal – last to be used next = removed first FIFO – Inserted first = removed first LRU – used least recently = removed first NRU – approximation using bit shifting Second chance – approximation using single bit Would also be useful to know the dirty pagesPage Replacement Strategies Takes two disk operations to replace a dirty page We keep track of dirty bits, so we should attempt to replace clean pages first Write dirty pages to disk during idle disk time Then we can clear the dirty bit Need to approximate optimal strategy, but can’t because we never know what order a process will use its pages Best we can do is run a program multiple times, and track what memory it usesSummary Slow to use contiguous allocations + compaction Very fast (and only one extra lookup) to use virtual memory Can also address a much larger space than we have physical memory No external fragmentation Use the right page replacement


View Full Document

U of I CS 241 - System Programming Virtual Memory

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 Virtual Memory
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 Virtual Memory 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 Virtual Memory 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?