Transcript CS 1104 Help Session II Virtual Memory

Virtual Memory
 Modern Operating systems can run programs that
require more memory than the system has
 If your CPU is 32-bit, meaning that it has registers that
are 32-bits, you can access up to 4G
 Which means you would need 4Gb of RAM in order to
take advantage of this
 Although many systems are currently available with
512MB
 Usually memory requirements of the programs you are
running, reach far beyond the physical memory you
have.
 Usually we don't notice any performance problems.
So, how is this possible?
Virtual Memory
1
Virtual Memory
• To solve this problem OS uses something called virtual
memory
• It is virtual because it can use more that you actually
have.
• In fact, with virtual memory you can use the whole 232
bytes.
• Basically, what this means is that you can run more
programs at once without the need for buying more
memory.
• E.g, in Linux OS if you have more data than physical memory, the
system store it temporarily on the hard disk if not needed at the
moment.
• Process of moving data to and from the disk is called swapping.
Virtual Memory
2
Main Idea
System Cache
Is cached by
Main Memory
Is cached by
Virtual Memory
(residing on disk)
• All memory transfers are only between consecutive levels
(e.g. VM to main memory, main memory to cache).
Virtual Memory
3
Cache vs. VM
• Concept behind VM is almost identical to concept behind
cache.
• But different terminology!
– Cache: Block
– Cache: Cache Miss
VM: Page
VM: Page Fault
• Caches implemented completely in hardware.
• VM implemented in software, with hardware support from
CPU.
• Cache speeds up main memory access, while main memory
speeds up VM access.
Virtual Memory
4
Virtual Memory Design
• Main Memory at Virtual Memory are both divided into
fixed size pages.
– Page size is typically about 16KB to 32KB.
– Large page sizes are needed as these can be more efficiently
transferred between main memory and virtual memory.
– Size of physical page ALWAYS equal to size of virtual page.
• Pages in main memory are given physical page numbers, while
pages in virtual memory are given virtual page numbers.
– I.e. First 32KB of main memory is physical page 0, 2nd 32KB is
physical page 1 etc.
– First 32KB of virtual memory is virtual page 0, etc.
Virtual Memory
5
Virtual Memory Design
• In cache, we can search through all the blocks until
we find the data for the address we want.
– This is because the number of blocks is small.
• This is extremely impractical for virtual memory!
– The number of VM pages is in the tens of thousands!
Virtual Memory
6
Solution
• Use a look up table.
• The addresses generated by the CPU is called the virtual
address.
• The virtual address is divided into a page offset and a
virtual page number:
Virtual Page Number
Page Offset
• The virtual page number indicates which page of
virtual memory the data that the CPU needs is in.
Virtual Memory
7
Solution…cont
• The data must also be in physical memory before it can be
used by the CPU!
• Need a way to translate between the virtual page number
where the data is in VM, to the page number of the physical
page where the data is in physical memory.
• To do this, use Virtual Page Table.
– Page Table resides in main memory.
– One entry per virtual page. Can get VERY large as the number of
virtual pages can be in the tens of thousands.
Virtual Memory
8
Virtual Page Table
1.
2.
Gives the physical page (frame) # of a virtual page, if that page is
in memory.
Gives location on disk if virtual page is not yet in main memory.
page0
page1
page2
page3
page4
page5
frame0
frame1
frame2
frame3
Virtual Memory
Virtual Memory Table
Physical Memory
9
VM (on Disk Space)
Page Table Contents
• The page table also contains a Valid Bit (V) to indicate if
the virtual page is in main memory (V=1) or still on disk
(V=0).
page0
page1
page2
page3
page4
page5
1
0
1
1
0
1
2
(2,1,7)
0
1
(7,2,9)
3
• If a page is in physical memory (V=1), then the page
table gives the Frame #.
• Otherwise it gives the location of the page on disk , in
Virtual
10
the form (side#, track
#,Memory
block#).
Accessing Data
• To retrieve data:
1. Extract the Virtual Page Number from the Virtual
Address
Virtual Page Number (e.g. 02)
Virtual Page Number (e.g. 02)
Virtual Memory
Page Offset
Page Offset
11
Accessing Data
2. Use the page to look up the page table. If V=1, get the frame from
the page table:
page = 2
page0
page1
page2
page3
page4
page5
1
0
1
1
0
1
2
(2,1,7)
0
1
(7,2,9)
3
frame=0
Here virtual page#2 mapped to frame#0.
Virtual Memory
12
Accessing Data
3. Combine the frame found with the page offset to form the physical
memory address:
Phyiscal Page Number 0
Page Offset
Physical Page Number 0
Page Offset
Physical Address
Virtual Memory
13
Accessing Data
4. Access main memory using the physical address.
– A page consists of many bytes (e.g. 32KB)
– The page offset tells us exactly which byte of these 32KB we are
accessing.
• Similar to the idea of block offset and byte offset in caches
Virtual Memory
14
Page Fault
• What if the page we want is not in main memory yet?
1. In this case, V=0, and the page table contains the disk
address of the page (e.g. page1 in the previous example is
still at side 2, track 1, block 7 (2,1,7) of the disk.
2. Find a free physical page
- if none are available, apply a replacement policy (e.g. LRU) to
find one.
3. Load the virtual page into the physical page.
- Set the V flag, and update the page table to show which
physical page the virtual page has gone to.
Virtual Memory
15
Behavior of Page Replacement Algorithms
Virtual Memory
16
Example: 2 blocks cache, 4bytes/block
VA space=8 pages &32 Byte/page VA= 3bits(page#) + 5-bit(offset)
load
load
C-Miss
C-Miss
00100 0 00
00101 0 00
Index
Valid
0
1
NYY
N
P-Fault
P- Hit!
Tag
load 32
load 40
Data
00100
00101
Memory[000100
Memory[000101 0000]
00]
Virtual Page Number
Page offset
001
001
00000
01000
Page Index
Valid
Frame number
0
1
...
N
NY
N
111
Virtual Memory
Memory
Disk
17
Example
Suppose we have
32 bit virtual address (232 bytes)
4096 bytes per page (212 bytes)
4 bytes per page table entry (22 bytes)
What is the total page table size?
2 32
Number of page table entries  12  2 20 entries
2
Size of page table  2 20 entries  2 2 bytes  2 22 bytes  4 MB
4 Megabytes just forVirtual
page
tables!! Too Big
Memory
18
Writing to VM
• Writes to Virtual Memory is always done on a writeback basis.
• To support write-back, the page-table must be
augmented with a dirty-bit (D).
• This bit is set if the page is updated in physical
memory.
Virtual Memory
19
Writing to VM
D
page0 0
page1 0
1
page2 1
page3 0
page4 0
page5 0
V frame or disk location
1
2
0
(2,1,7)
11
0
1
1
0
(7,2,9)
1
3
• Here virtual page#2 was updated in physical frame#0.
• If frame#0 is ever replaced, its contents must be written back to disk
to update page#2.
Virtual Memory
20
Translation Look-aside Buffer
• An access to virtual memory requires 2 main memory accesses at best.
– One access to read the page table, another to read the data.
• Remember from the Cache section that main memory is slow
• Fortunately, page table accesses themselves tend to display both
temporal and spatial locality!
– Temporal Locality: Accesses to the different words in the same page will cause
access to same entry in page table!
– Spatial Locality: Sequential access of data from one virtual page into the next
will cause consecutive accesses to page table entries.
• Initially I am at page0, and I access Page Table entry for page0. As I move into
page1, I will access Page Table entry for page1, which is next to page table entry for
page0!
Virtual Memory
21
Translation Look-aside Buffer
• Solution:
– Implement a cache for the page table! This cache is called the
translation look-aside buffer, or TLB.
– The TLB is separate from the caches we were looking at earlier.
• Those caches cached data from main memory.
• The TLB caches page table entries! Different!
– TLB is small (about 8 to 10 blocks), and is implemented as a fully
associative cache.
Virtual Memory
22
Translation Look-aside Buffer
• Fully Associative
– New page table entries go into the next free TLB block,
or a block is replaced if there are none.
• Note that only page table entries with V=1 are
written to the TLB!
• The page table entries already in the TLB are not
usually updated, so no need to consider writethrough or write-back
– Exceptional cases: page aliasing, where more than 1
page can refer to the same Physical Page.
Virtual Memory
23
Translation Look-aside Buffer
• The tags used in the TLB is the virtual page number of a
virtual address.
• All TLB blocks are searched for the page. If found, we have
a TLB hit and the physical page number is read from the
TLB. This is joined with the page offset to form the
physical address.
• If not found, we have a TLB miss. Then we must go to the
page table in main memory to get the page table entry there.
Write this entry to TLB.
Virtual Memory
24
Translation Look-aside Buffer
• Complication
– If we have a TLB miss and go to main memory to get the page
table entry, it is possible that this entry has a V of 0 - page fault.
– In this case we must remedy the page fault first, update the page
table entry in main memory, and then copy the page table entry
into TLB. The tag portion of TLB is updated to the page of the
virtual address.
• Note that the TLB must also have a valid bit V to indicate if
the TLB entry is valid (see cache section for more details on
the V bit.)
Virtual Memory
25
Integration Cache, Main Memory and
Virtual Memory
• Suppose a Virtual Address V is generated by the CPU
(either from PC for instructions, or from ALU for lw and sw
instructions).
1. Perform address translation from Virtual Address to Physical
Address
(a) Look up TLB or page table (see previous slides). Remedy page
fault if necessary (again, see previous slides).
2. Use the physical address to access the cache (see cache notes).
3. If cache hit, read the data (or instruction) from the cache.
4. If cache miss, read the data from main memory.
Virtual Memory
26
Use of a Translation Lookaside Buffer
Virtual Memory
27
Integration Cache, Main Memory and
Virtual Memory
• Note that a page-fault in VM will necessarily cause a cache
miss later on (since the data wasn’t in physical memory, it
cannot possibly be in cache!)
• Can optimize algorithm in event of page fault:
1. Remedy the page fault.
2. Copy the data being accessed directly to cache.
3. Restart previous algorithm at step 3.
• This optimization eliminates 1 unnecessary cache access
that would definitely miss.
Virtual Memory
28
Page Table Size
• A Virtual Memory System was implemented for a MIPS
workstation with 128MB of main memory. The Virtual
Memory size is 1GB, and each page is 32KB. Calculate the
size of the page table.
Virtual Memory
29
Page Table Size
• Previous calculation shows that page tables are
huge!
• These are sitting in precious main memory space.
• Solutions:
– Use inverted page tables
• Instead of indexing virtual pages, index physical pages.
• Page table will provide virtual page numbers instead.
• Search page table for the page of address virtual address V. If
the page is found in entry 25, then the data can be found in
physical page 25.
– Have portions of page table in virtual memory.
• Slow, complex
Virtual Memory
30
Finer Points of VM
• VM is a collaboration between hardware and OS
– Hardware:
• TLB
• Page Table Register
– Indicates where the page table is in main memory
• Memory Protection
– Certain virtual pages are allocated to processes running in memory.
– If one process tries to access the virtual page of another process without
permission, hardware will generate exception.
– This gives the famous “General Protection Fault” of windoze and the
“Segmentation Fault” of Unix.
Virtual Memory
31
Finer Points of VM
– Hardware
• Does address translations etc.
– Operating System
• Actually implements the virtual memory system.
– Does reads and writes to/from disk
– Creates the page table in memory, sets the Page Table Register to point to the
start of the page table.
– Remedies page faults,updates the page table.
– Remedies VM violations
» Windows: Pops up blue screen of death, dies messily. Sometimes thrashes
your hard-disk.
» Unix: Gives “Segmentation Fault”. Kills offending process and continues
working.
Virtual Memory
32
Finer Points of VM
• Where is the Virtual Memory located on disk?
– Virtual memory is normally implemented as a very large file,
created by the OS. E.g. in Windows NT, the virtual memory file is
called swapfile.sys
• Insecure. Sometimes sensitive info gets written to swapfile.sys, and you can
later retrieve the sensitive info.
• In Unix, implemented as a partition on the disk that cannot be read except by
the OS. Unix good. Windows bad.
– Whenever virtual memory is read or written to, the OS actually
reads or writes from/to this file.
• Virtual Memory is NOT the other files on your disk (e.g. your JAVA
assignment)
Virtual Memory
33
Page Tables
Page table register
Virtual address
31 30 29 28 27
15 14 13 12 11 10 9 8
Virtual page number
Page offset
20
Valid
3 2 1 0
12
Physical page number
Page table
18
If 0 then page is not
present in memory
29 28 27
15 14 13 12 11 10 9 8
Physical page number
Physical
address
Virtual
Memory
3 2 1 0
Page offset
34
Making Address Translation Fast
• A cache for address translations: translation lookaside
buffer
Virtual page
number
TLB
Valid
Tag
Physical page
address
1
1
Physical memory
1
1
0
1
Page table
Physical page
Valid or disk address
1
1
1
Disk storage
1
0
1
1
0
1
1
0
1
Virtual Memory
35
TLBs and caches
Virtual address
TLB access
TLB miss
exception
No
Yes
TLB hit?
Physical address
No
Yes
Write?
Try to read data
from cache
No
Write protection
exception
Cache miss stall
No
Cache hit?
Yes
Deliver data
to the CPU
Virtual Memory
Write access
bit on?
Yes
Write data into cache,
update the tag, and put
the data and the address
into the write buffer
36