Transcript Unit 7

Operating Systems
Operating Systems
Unit 7:
– Virtual Memory
organization
Evolution of memory organization
COP 5994 - Operating Systems
2
Virtual Memory concept
• Solves problem of limited memory space
– Creates illusion of more memory than exists
• Creates 2 types of addresses
• Virtual addresses
– Referenced by processes
• Physical addresses
– Describes locations in main memory
• Memory management unit (MMU)
• Dynamic address translation
• Translates virtual addresses to physical address
COP 5994 - Operating Systems
3
Two-level Storage
• backing store:
– maintained on hard drive
– contains complete virtual memory
• real memory:
– portion of virtual memory that is currently in
use
• Process can only access real memory
– Management of mapping is essential
COP 5994 - Operating Systems
4
Two-level Storage
COP 5994 - Operating Systems
5
Address Translation
• Mapping virtual addresses to real
addresses
• need address translation map per
process
• Address translation maps
– Indicate which regions of a process’s virtual
address space are currently in main memory
and where they are located
COP 5994 - Operating Systems
6
Mapping based on block
COP 5994 - Operating Systems
7
Concept: block map table
• address translation map is table with
– block number
– actual location of block in memory
• typical implementation
– block number is offset from table origin
– table entries contain block location in
memory
COP 5994 - Operating Systems
8
Concept: virtual address
• structure of virtual address:
• b is the block number in virtual memory
• d is the displacement from the start of block b
at which the referenced item is located
COP 5994 - Operating Systems
9
Block Mapping Process
COP 5994 - Operating Systems
10
Blocks ?
• Pages
– Blocks are fixed size
– Technique is called paging
• Segments
– Blocks maybe of different size
– Technique is called segmentation
COP 5994 - Operating Systems
11
Paging
• Paging uses fixed-size block mapping:
– Virtual address in paging system: v = (p, d)
• p is the number of the page in virtual memory on
which the referenced item resides
• d is the displacement from the start of page p at
which the referenced item is located
COP 5994 - Operating Systems
12
Page Frame: page in real memory
• Fixed-size
block of main
memory
• Aligned with
page size
multiple
COP 5994 - Operating Systems
13
Page to Frame
correspondence
COP 5994 - Operating Systems
14
Page Table Entry (PTE)
• maps virtual page p to page frame p´
– Contains bit to indicate if page is in real memory
– Term: Page Fault
• access to memory location on page that is not in real
memory
COP 5994 - Operating Systems
15
Page Address Translation
• Direct Mapping
• Associative Memory
• Translation Lookaside Buffer
• Concerns:
– memory access speed
– size of page table
COP 5994 - Operating Systems
16
Address Translation by Direct
Mapping
COP 5994 - Operating Systems
17
Page Table size
• address size: 4 bytes
32
2 bytes virtual memory amount: 4GB
• Page size: 4k
20
2 pages in virtual memory
• PTE size: 8 bytes
23
2 bytes maximum page table size:
8MB
• Page table will not fit into processor cache
COP 5994 - Operating Systems
18
Page Table size
• address size: 8 bytes
64
2 bytes virtual memory amount
• Page size: 4k
52
2 pages in virtual memory
• PTE size: 16 bytes
2 56 bytes maximum page table size
• Page table will not fit into processor cache
COP 5994 - Operating Systems
19
Address Translation by Associative
Mapping
COP 5994 - Operating Systems
20
Combination: Direct/Associative Mapping
Experience shows:
TLB size of
64 or 128
Can reach 90% of
associative
mapping
performance
COP 5994 - Operating Systems
21
Page Address Translation: concerns
• memory access speed
– consider cache speed
• size of page table
– 32 bit vs. 64 bit
• use of memory space
– locality of memory references
– sparseness
• advanced approaches
– multi-level page tables
– inverted page table
COP 5994 - Operating Systems
22
Multilevel Page Tables
• Hierarchy of page tables
– Each level containing a table that stores
pointers to tables in the level below
– Bottom-most level comprised of tables
containing address translations
• Can reduce memory overhead compared
to direct-mapping system
– page table does not have to be contiguous
COP 5994 - Operating Systems
23
Multilevel Page Tables
COP 5994 - Operating Systems
24
Inverted Page Tables
– One inverted page table stores one PTE in
memory for each page frame in the system
– Inverted relative to traditional page tables
– Uses hash functions to map virtual page to
inverted page table entry
COP 5994 - Operating Systems
25
Inverted Page Tables
COP 5994 - Operating Systems
26
Inverted Page Tables
• Hash collisions increase memory
accesses
• Collisions can be reduced by increasing
the range of the hash function
– Cannot increase the size of the inverted
page table because it must store exactly one
PTE for each page frame
• trick: hash anchor table
– one more level of indirection
COP 5994 - Operating Systems
27
Inverted Page Tables with hash anchor
table
COP 5994 - Operating Systems
28
Also: Page Sharing
• programs may
share
common
pages
– data and/or
instructions
• pages marked
as sharable or
nonsharable
COP 5994 - Operating Systems
29
Segmentation
• based on variable-size segments
– contiguous block of process’ address space
• data, text, stack
• process can run
if current segment(s) is in main memory
COP 5994 - Operating Systems
30
Segmentation
COP 5994 - Operating Systems
31
Segmentation
• virtual memory address v = (s, d)
– s is the segment number in virtual memory
– d is the displacement within segment s at
which the referenced item is located
COP 5994 - Operating Systems
32
Address Translation by Direct Mapping
COP 5994 - Operating Systems
33
Segment map table entry
• maps segment s to real memory address
s´
– has resident bit to indicate segment is in
memory
• If so, it stores the segment base address
• Otherwise, it stores the location of the segment
on secondary storage
– has segment length field
• useful to protect memory outside of segment
COP 5994 - Operating Systems
34
Segment map table entry
COP 5994 - Operating Systems
35
Segment map table entry: protection
COP 5994 - Operating Systems
36
Also: Segment Sharing
Caution: segment protection
COP 5994 - Operating Systems
37
Combination: Segmentation/Paging
Systems
• Segments occupy one or more pages
• All pages of segment need not be in main
memory at once
• Pages contiguous in virtual memory need
not be contiguous in main memory
COP 5994 - Operating Systems
38
Virtual memory address
– s is segment number
– p is page number within segment
– d is displacement within page at which
desired item located
COP 5994 - Operating Systems
39
Address Translation
COP 5994 - Operating Systems
40
System-wide Table Structure
COP 5994 - Operating Systems
41
Sharing and Protection
• Page
replacement
requires
updates to
several tables
• Protection
checking is
complex
COP 5994 - Operating Systems
42
Agenda for next week:
• next week:
– Chapter 11: Virtual Memory Management
– Read ahead !
COP 5994 - Operating Systems
43