DOC PREVIEW
UCSD CSE 120 - Paging

This preview shows page 1-2-3 out of 8 pages.

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

Unformatted text preview:

Review CSE120 Principles of Operating Systems Fixed and variable size partition Prof Yuanyuan YY Zhou Lecture 10 paging Nov 2nd 2010 Paging Today s Lecture Segmentation Hybrid paging segmentation Segmentation table 11 1 2010 CSE 120 Lecture 10 Paging Page Mapping Hardware Today we ll cover more paging mechanisms Optimizations Page size is a power of 2 Virtual page number physical page frame How to calculate VPN from virtual address How to get physical address 2 Simple to implement base and limit registers Internal vs external fragmentation Best worst fast fit Bitmap vs link list implementation of free memory regions Page Table 0 P 1 0 1 P F 1 0 1 Managing page tables space Efficient translations TLBs time Demand paged virtual memory space Recap address translation Virtual Address P D P D Virtual Memory P Contents P D Physical Memory F D F Physical Address F D Contents F D 3 11 1 2010 CSE 120 Lecture 10 Paging 4 D 11 1 2010 D CSE 120 Lecture 10 Paging 1 Paging Issues Page Mapping Hardware Page Table 0 4 1 0 1 4 5 1 0 1 Virtual Memory Virtual Address 004006 004 006 Contents 4006 004 006 Page size 0x1000 Number of Possible Virtual Pages 0x1000 Number of Page Frames 8 11 1 2010 005 Contents 5006 006 CSE 120 Lecture 10 Paging 6 Managing Page Tables The page table for a 32 bit address space w 4K pages to be 4MB How can we reduce this overhead 7 11 1 2010 CSE 120 Lecture 10 Paging Discussion How to reduce page table size if the virtual pages are sparse This is far too much overhead for each process Observation Only need to map the portion of the address space actually being used tiny fraction of entire addr space How do we only map what is being used 220 page entries take 222 bytes 4MB 006 Physical Address F D 5 usually 512 1k 2k 4k or 8k E g 32 bit VM address may have 220 1MB pages with 4k 212 bytes per page Page table Physical Memory 005 Page size is 2n Can dynamically extend page table Does not work if addr space is sparce internal fragmentation why So now what 11 1 2010 CSE 120 Lecture 10 Paging 8 11 1 2010 CSE 120 Lecture 10 Paging 2 Two Level Page Tables Two level page tables Physical Memory Virtual addresses VAs have three parts Two Level Page Tables Master page number secondary page number and offset Master page table maps VAs to secondary page table Secondary page table maps page number to physical page Offset indicates where in physical page address is located Virtual Address Master page number 9 Physical Address 4K pages 4 bytes PTE How many bits in offset 4K 12 bits Want master page table in one page 4K 4 bytes 1K entries Hence 1024 secondary page tables How many bits Master 1K 10 offset 12 secondary 32 10 12 10 bits 11 1 2010 CSE 120 Lecture 10 Paging Master Page Table 10 CSE 120 Lecture 10 Paging Hints Easy to address no translation required But allocated page tables consume memory Programs only know virtual addresses Each virtual address must be translated So each program memory access requires several actual memory accesses Cold unused page table pages can be paged out to disk But addressing page tables requires translation How do we stop recursion Do not page the master page table called wiring or pinning If we re going to page the page tables might as well page the entire OS address space too 11 Page frame 11 1 2010 Virtual memory OS virtual address space Offset So what is the problem with twolevel page table Where do we store page tables which address space Physical memory Page frame Secondary Page Table Addressing Page Tables Offset Page table Example Secondary Need to wire special code and data fault interrupt handlers 11 1 2010 CSE 120 Lecture 10 Paging 12 11 1 2010 CSE 120 Lecture 10 Paging 3 Translation Look aside Buffer TLB Efficient Translations Our original page table scheme already doubled the cost of doing memory lookups VPage Two lookups into the page tables a third to fetch the data And this assumes the page table is in memory How can we use paging but also have lookups cost about the same as fetching from memory offset One lookup into the page table another to fetch the data Now two level page tables triple the cost Virtual address VPage PPage VPage PPage VPage PPage Miss Real page table TLB Cache translations in hardware Translation Lookaside Buffer TLB TLB managed by Memory Management Unit MMU Hit PPage offset Physical address 13 11 1 2010 CSE 120 Lecture 10 Paging 14 11 1 2010 TLBs Fully associative cache all entries looked up in parallel Cache tags are virtual page numbers Cache values are PTEs entries from page tables With PTE offset can directly calculate physical address If a virtual address is presented to MMU the hardware checks TLB by comparing all entries simultaneously in parallel If match is valid the page is taken from TLB without going through page table If match is not valid TLBs exploit locality Processes only use a handful of pages at a time 15 Translate virtual page s into PTEs not physical addrs Can be done in a single machine cycle TLBs implemented in hardware TLB Function Translation Lookaside Buffers 16 48 entries pages 64 192K Only need those pages to be mapped Hit rates are therefore very important 11 1 2010 CSE 120 Lecture 10 Paging CSE 120 Lecture 10 Paging 16 MMU detects miss and does an ordinary page table lookup It then evicts one page out of TLB and replaces it with the new entry so that next time that page is found in TLB 11 1 2010 CSE 120 Lecture 10 Paging 4 Page Mapping Hardware Page Mapping Example Virtual Memory Address P D P D Associative Look Up Page Table 0 P 1 0 1 P F 1 0 1 P F First F D Page Table 0 4 1 0 1 004 009 1 0 1 Physical Address F D 17 11 1 2010 CSE 120 Lecture 10 Paging 18 11 1 2010 Address translations for most instructions are handled using the TLB Who places translations into the TLB loads the TLB 99 of translations but there are misses TLB miss Hardware Memory Management Unit x86 Table organized by LRU 11 1 2010 CSE 120 Lecture 10 Paging 20 Knows where page tables are in main memory OS maintains tables HW accesses them directly Tables have to be in HW defined format inflexible Software loaded TLB OS MIPS Alpha Sparc PowerPC Physical Address F D 19 CSE 120 Lecture 10 Paging 00a Table organized by LRU 006 Managing TLBs Virtual Memory Address P D 004 00a Associative Look Up 1 12 4 9 19 3 First 3 7 009 009 Physical Address F D Page Mapping Example next reference Page Table 0 4 1 0 1 004 009 1 0 1 Virtual Memory Address P D 004 006 Associative …


View Full Document

UCSD CSE 120 - Paging

Documents in this Course
Threads

Threads

14 pages

Deadlocks

Deadlocks

19 pages

Processes

Processes

14 pages

Paging

Paging

13 pages

Processes

Processes

18 pages

Threads

Threads

29 pages

Security

Security

16 pages

Paging

Paging

13 pages

Processes

Processes

32 pages

Lecture 2

Lecture 2

13 pages

Threads

Threads

14 pages

Paging

Paging

13 pages

Paging

Paging

26 pages

Paging

Paging

13 pages

Lecture

Lecture

13 pages

Processes

Processes

14 pages

Paging

Paging

13 pages

Security

Security

17 pages

Threads

Threads

15 pages

Processes

Processes

34 pages

Structure

Structure

10 pages

Lecture 3

Lecture 3

13 pages

Lecture 1

Lecture 1

28 pages

Threads

Threads

15 pages

Paging

Paging

30 pages

Load more
Download Paging
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 Paging 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 Paging 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?