Chapter 5 Memory Hierarchy part 3 Virtual Memory
1
Virtual memory
• Main memory acting as a “cache” for hard disk (usually magnetic disks)
• Two major motivations for Virtual Memory:
1. Allowefficientandsafesharingamongmultipleprograms 2. Removestheprogrammingburdensofasmallmemory
Different terminologies but same concepts cache vs. virtual memory
block vs. page
cache miss vs. page fault
Virtual addresses
Physical addresses
Address translation
Disk addresses
2
• Advantages:
– illusionofhavingmorephysicalmemory – programrelocation
– protection
Virtual memory block is called a page. Virtual memory miss is called a page fault.
3
Address translation
With virtual memory, the processor produces a virtual address, which is translated by a combination of hardware and software to a physical address (address in main memory).
4
Relocation
• Relocation: It maps the virtual addresses used by a program to different physical addresses before the addresses are used to access memory.
• We can load the program anywhere in main memory.
• All virtual memory systems in use relocate the program as a set of fixed-size blocks (pages), eliminating the need to find a contiguous block of memory to allocate to a program.
• The operating system needs to find a sufficient number of pages in main memory
• In Virtual memory, the address is broken into a virtual page number and a page offset. (see the picture in the next page).
5
In Virtual memory, the address is broken into a virtual page number and a page offset.
6
Pages: virtual memory blocks
• Page faults: the data is not in memory, retrieve it from disk
– huge miss penalty (millions of clock cycles to process), thus pages should be fairly large (e.g., 4KB-16KB)
– reducingpagefaultsisimportant(LRUisworththeprice)
– canhandlethefaultsinsoftwareinsteadofhardware(overhead
is small compared to disk access)
– usingwrite-throughistooexpensivesoweusewrite-back
7
Write-back/Copy-back, dirty bit
• Virtual memory systems must use write-back, performing the individual writes into the page in memory and copying the page back to disk when it is replaced in the memory.
• To track whether a page has been written since it was read into the memory, a dirty bit is added to the page table. The dirty bit is set when any word in a page is written.
• If the OS needs to replace the page, the dirty bit indicates whether the page needs to be written out before its location in memory can be given another page.
8
Page Table: Placing a Page and Finding it Again
• Page Table: The table containing the virtual to physical address translations in a virtual memory system. It resides in memory. The table, which is stored in memory, is typically indexed by the virtual page number; each entry in the table contains the physical page number for that virtual page if the page is currently in memory.
• Library analogy: The page table – a mapping between book titles and library locations.
• Just as the card catalog may contain entries for books in another library on campus rather than the local branch library, the page table may contain entries for pages not present in memory.
• Page Table Register: The hardware includes a register that points to the start of the page table.
9
Page Tables
• The page table together with the program counter and the registers,
specifies the state of a program.
• A program can continue its execution using this state. • This state is referred as a process.
• Rather than saving the entire page table, the operating system simply loads the page table register to point to the page table of the process it wants to make active.
• Each process has its own page table, since different processes use the same virtual addresses.
• The operating system is responsible for allocating the physical memory and updating the page tables, so that different process do not collide.
10
Operating System
An operating system is the infrastructure software component of a computer system
– It is responsible for the management and coordination of activities and the sharing of the limited resources of the computer
Hardware
Software/ Application programs
Operating System
11
Operating System
– The operating system acts as a host for applications
that are run on the machine. As a host, one of the purposes of an operating system is to handle the details of the operation of the hardware.
12
Software Classification: (operating system – cont.)
Application Software
— consists of the programs for performing tasks particular to the machine’s utilization. Example: spreadsheets, database systems, accounting systems, and games.
System Software
– performs those tasks that are common to computer systems. It provides the environment in which the application software resides. System Software can be categorized into the operating system and utility software.
Utility Software – consists of programs for performing activities that are fundamental to computer installations yet not included in the operating system.
It can extend the capabilities of the operating system.
Example: the ability to format a disk or to copy a file.
Software to compress and decompress data. Software for handling network communication.
13
Page Tables
The page table is indexed with the virtual page number to obtain the corresponding portion of the physical address.
Page table
3130292827
Virtual address
15141312111098 3210
Valid
Physical page number
If 0 then page is not present in memory
292827
15141312111098 3210 Physical page number Page offset
20
12
Page table register
Virtual page number
Page offset
18
Physical address
14
Page Tables
The page table maps each page in virtual memory to either a page in main memory or a page stored on disk
Virtual page number
Valid
1 1 1 1 0 1 1 0 1 1 0 1
Disk storage
Page table Physical page or disk address
Physical memory
15
Page Faults
• If the valid bit for a virtual page is off, a page fault occurs. The operating system must be given control.
• This transfer is done with the exception mechanism.
• Swap Space: The space on the disk reserved for the full virtual
memory space of a process.
• The operating system creates the space (swap space) on disk for all the pages of a process when it creates the process.
• The OS also creates a data structure to record where each virtual page is stored on disk.
• The OS also creates a data structure that tracks which processes and which virtual addresses use each physical page.
• If all pages in main memory are in use and a page fault occurs, the OS replaces LRU (least recently used) page.
16
Page Faults: Example
• Suppose the page references (in order) were 10, 12, 9, 7, 11, 10, and then we referenced page 8, which was not present in memory.
• The LRU page is 12, we would replace page 12 in main memory with page 8.
• Use Bit/Reference Bit: A field that is set whenever a page is accessed and that is used to implement LRU or other replacement scheme.
• The OS periodically clears the reference bits and later records them so it can determine which pages were touched during a particular time period.
• If this bit is not provided by the hardware, the OS must find another way to estimate which pages have been accessed.
17
• With a 32-bit virtual address, 4KB pages, and 4 bytes per page table entry, Compute the total page table size:
• Number of page table entries 2 (32-12) = 2 32 / 2 12 = 2 20 (2 12 ≈ 4096)
• Size of page table = 2 20 page table entries x 2 2 bytes/page table
entry=220 x4=4MB
• We need to use 4MB of memory for each program in execution at any time.
18
5 techniques to reduce the total maximum storage requires as well as minimizing the main memory dedicated to page tables.
1. Tokeepalimitregisterthatrestrictthesizeofthepagetablefora given process. If the virtual page number becomes larger than the contents of the limit register, entries must be address to the page table.
2. To divide the page table and let it grow from the highest address down as well as from the lowest address up. A limit register for each segment specifies the current size of the segment, which grows in units of pages.
3. Toapplyahashingfunctiontothevirtualaddresssothatthepage table data structure need to be only the size of the number of physical pages in main memory. (inverted page table)
4. Multiple levels: The 1st level maps large fixed size block (segment) of virtual address space (64-256 pages in total.) If the segment address is valid, the next set of high-order bits is used to index the page table indicated by the segment table entry.
5. Thepagetablesarepaged.
19
TLB: Making Address Translation Fast
• TLB ( translation-lookaside buffer) or translation cache: A cache that keeps track of recently used address mappings to avoid an access to the page table.
• Library Analogy: a piece of paper we use to record the location of a set of books that we look up in the card catalog, rather than continually searching the entire catalog, we record the location of several books and use the scarp of paper as a cache of Library of Congress call numbers.
• Each tag entry in the TLB holds a portion of the virtual page number, and each data entry of the TLB holds a physical page number.
• Since we will no longer access the page table on every reference, the TLB will need to include other bits including the dirty and the reference bit.
20
TLB: Making Address Translation Fast
•
A cache for address translations: translation-lookaside buffer (TLB)
Typical values:
TLB size: 8 – 4096 entries
Block size: 1-2 page table entries (4-8 bytes each) Hit time: 0.5-1 clock cycle
Miss-rate: 0.01% – 1%
Miss-penalty: 10 – 30 cycles
21
TLB: Making Address Translation Fast
• The TLB acts as a cache on the page table for the entries that map to physical pages only.
Virtual page number
TLB
Tag address
Valid Dirty Ref
1 0 1 111 111 101 000 101
Physical memory
Valid Dirty Ref
Physical page or disk address
111 100 100 101 000 101 101 000 1 1 1 111 000 111
Disk storage
Page table
Physical page
22
Processing a read or write-through in the Intrinsity FastMATH and cache
TLB miss exception
No
TLB hit? Yes
Cache miss stall while read block
No
Cache hit? Yes
Write protection exception
Try to write data to cache
Virtual address
TLB access
No Write? Yes Try to read data
from cache
No Write access bit on?
Yes
Deliver data to the CPU
Physical address
Cache miss stall while read block
No
Cache hit? Yes
Write data into cache, update the dirty bit, and put the data and the address into the write buffer
23
TLBs and Caches
C ache
Cache hit
TLB TLB hit
= = = = = =
Valid Dirty
Tag
12 Physical page number
8
Valid Tag
12
Data
31 30 29 20
Virtual address
14 13 12 11 10 9 3 2 1 0
=
Virtual page num ber
Page offset
Physical page number
Physical address
Page offset
Physical address tag Cache index
18 842
offset
32 Data
24
20
Block Byte
offset
The possible combinations of events in the TLB, virtual memory system, and cache.
TLB Page Cache table
Possible? If so, under what circumstance?
Hit Hit Miss Miss Hit Hit Miss Hit Miss Miss Miss Miss Hit Miss Miss Hit Miss Hit Miss Miss Hit
Possible, although the page table is never really checked if TLB hits.
TLB misses, but entry found in page table; after retry data is found in cache.
TLB misses, but entry found in page table; after retry data misses in cache.
TLB misses and is followed by a page fault; after
retry, data must miss in cache.
Impossible: cannot have a translation in TLB if page is not present in memory.
Impossible: cannot have a translation in TLB if page is not present in memory.
Impossible: data cannot be allowed in cache if the page is not in memory.
25
Operating System Protection
• To enable the OS to implement protection in the virtual memory system, the hardware must provide:
• Support at least two modes that indicate whether the running process is a use process or an operating system process, called a supervisor/kernel/executive process.
• Provide a portion of the processor state that a user process can read but not write, including the user/supervisor mode, the page table pointer, and the TLB.
• Provide mechanisms whereby the processor can go from user mode to supervisor mode, and vice versa.
– Use -> supervisor: by system call exception (syscall in MIPS)
– The PC from the point of the system call is saved in the exception PC
(EPC), and the processor is placed in supervisor mode.
– Supervisor->User: use the return from exception (ERET) instruction, which sets the user mode and jumps to the address in EPC.
26
Operating System Protection – cont.
• The OS needs to modify other process pages, but to prevent use processes from modifying its own page tables.
• Placing the page table in the protected address space of the operating system satisfies both requirements.
• To allow another process, say P1, to read a page owned by process P2, P2 would ask the operating system to create a page table entry for a virtual page in P1’s address space that points to the same physical page that P2 wants to share.
• The OS could use the write protection bit to prevent P1 from writing the data, if that was P2’s wish. Any bits that determine the access rights for a page must be included in both the page table and the TLB because the page table is accessed only on a TLB miss.
27
Handling TLB Misses and Page Faults
• A TLB miss occurs when no entry in the TLB matches a virtual address.
• A TLB miss can indicate one of two possibilities:
1. Thepageispresentinmemory,andweneedonlycreatethe
missing TLM entry.
2. Thepageisnotpresentinmemory,andweneedtotransfer control to the operating system to deal with a page fault.
28
Exception Enable/Interrupt Enable
• Exception Enable/Interrupt Enable : A signal or action that controls whether the process responds to an exception or not; necessary for preventing the occurrence of exceptions during intervals before the processor has safely saved the state needed to restart.
• When an exception first occurs, the processor sets a bit that disables all other exceptions; this could happen at the same time the processor set the supervisor mode bit. The OS will then save just enough state to allow it to recover if another exception occurs, EPC and Cause registers.
29
• Once the OS knows the virtual address that caused the page faulty, it must complete 3 steps:
1. Loopupthepagetableentryusingthevirtualaddressandfindthe location of the reference page on disk.
2. Choseaphysicalpagetoreplace;ifthechosenpageisdirty,itmust be written out to disk before we can bring a new virtual page into this physical page.
3. Startareadtobringthereferencepagefromdiskintothechosen physical page.
30
Re-startable instruction
• Re-startable instruction: an instruction that can resume execution after an exception is resolved without the exception’s affecting the result of the instruction.
• We can simply prevent the instruction from completing (by not writing) and restart the instruction at the beginning.
31