程序代写代做代考 algorithm cache PowerPoint 演示文稿
PowerPoint 演示文稿
CO101
Principle of Computer
Organization
Lecture 18: Memory 4
Liang Yanyan
澳門科技大學
Macau of University of Science and
Technology
Problems
• Not enough main memory?
• A program requests too much memory space.
• Multiple programs?
• Different programs try to access the same address → conflict.
• How to protect a program’s data from being modified by other
programs?
2
Processor Main memory
physical
address
instruction
and data
Solution for size limitation
• Create a big virtual memory and presents to processor.
• The processor just know it has a big memory.
• Actually, some data are stored in main memory, some are stored
in hard disk. Processor doesn’t know where data are stored.
• Processor read/write data from virtual memory through a
virtual address.
3
Processor
Main
memory
physical
address
Disk
virtual
address
address
translator
Virtual memory
instruction
and data
Solution for conflict
• Each program can use the virtual address arbitrarily, and use as
much space (virtual memory) as it wants.
• E.g. two distinct programs can use the same virtual address, which
can be mapped to two different physical memory locations by the
operating system → resolve address conflict.
4
V
ir
tu
al
A
dd
re
ss
Physical
Memory
Disk
V
irtual A
ddress
Program A Program B
Review: The Memory Hierarchy
• Take advantage of the principle of locality to present the user with as
much memory as is available in the cheapest technology at the
speed offered by the fastest technology
5
Increasing
distance from
the processor
in access
time
L1$
L2$
Main Memory
Secondary Memory
Processor
(Relative) size of the memory at each level
Inclusive– what
is in L1$ is a
subset of what is
in L2$ is a
subset of what is
in MM that is a
subset of is in
SM
4-8 bytes (word)
1 to 4 blocks
1,024+ bytes (disk sector = page)
8-32 bytes (block)
Virtual Memory
• Use main memory as a “cache” for secondary memory
• Allows efficient and safe sharing of memory among multiple
programs
• Provides the ability to easily run programs larger than the size of
physical memory
• Simplifies loading a program for execution by providing for code
relocation (i.e., the code can be loaded anywhere in main memory)
• Managed jointly by CPU hardware and the operating system (OS)
• What makes it work? – again the Principle of Locality
• A program is likely to access a relatively small portion of its address
space during any period of time
• Each program is compiled into its own address space – a
“virtual” address space
• During run-time each virtual address must be translated to a
physical address (an address in main memory)
• VM “block” is called a page
• VM translation “miss” is called a page fault
6
The big picture (32-bit address)
7
CPU
Program A
(I have 4GB
memory)
Program B
(I have 4GB
memory)
Program C
(I have 4GB
memory)
Virtual
address
Data
Main memory
(1 GB)
(program A: data 1)
(program B: data 2)
(program A: data 2)
(program C: data 4)
…
…
physical
address
Address
Translator
(Operating
System)
Disk
(32 GB)
(program A: data 5)
(program B: data 6)
(program A: data 8)
(program C: data 9)
…
…
• Use the main memory as a cache, reduce the read/write delay of accessing disk.
• Fully associative, least recently used policy for replacement.
Virtual memory
• Virtual memory is divided into pages.
• Virtual address is divided into two fields.
• Virtual page number
• Page offset
8
page 0
page 1
page 2
page 3
…
…
page N
Virtual memory
Virtual address
Program A
(I have 4GB
memory)
Convert virtual address to physical address
• The conversion is done using a page table.
• Each program (process) has a separate page table stored in main memory.
A “page table register” points to the page table of current program (process).
• The page table is indexed with the virtual page number (VPN)
• Each entry contains a valid bit, and a physical page number (PPN)
• The PPN is concatenated with the page offset to form a physical address.
• No tag is needed because the index is the full VPN.
• Virtual address → physical address by combination of HW/SW.
• Each memory request needs first an address translation.
9
Convert virtual address to physical address
10
How big is
a page?
212 bytes
Loading data using virtual address
11
• If Valid == 1, get the
Physical page number
and concatenate with the
page offset to form the
physical address, load
data from physical
memory.
• If Valid == 0, locate data
in disk, load data from
disk to physical memory.
Record the physical
page number and use it
to update the Page table,
change Valid to 1.
Virtual Addressing with a Cache
• Thus it takes an extra memory access to translate a VA
to a PA.
12
CPU Trans- lation Cache
Main
Memory
VA PA miss
hit
data
Problems
• How big is the page table?
• In the previous example, virtual page number is 20-bit long →
the table contains 220 entries.
• Where can we store this table?
• It can be stored in main memory, but the time for an address
translation is much longer. We need to access the main memory
and do an address translation.
13
To read a data using virtual address:
Step 1: read the page table stored in main memory, load
the physical page number and calculate the
physical address.
Step 2: load data using the physical address.
→ Involves two memory accesses!!
Solution
• Add a cache to store portion of the page table.
• Instead of read table entries from main memory, load
table entries from cache.
• Just like the data cache introduced before, the only difference is
that the cache here is used to store table entries.
14
Processor
Table cache
(store portion
of the table)
Main
Memory
(store entire
page table)
Virtual
address
Physical
address
Translation Lookaside Buffers (TLBs)
• Just like any other cache, the TLB can be organized as
fully associative, set associative, or direct mapped.
• TLB access time is typically smaller than cache access
time (because TLBs are much smaller than caches)
• TLBs are typically not more than 512 entries even on high end
machines.
15
Table cache: Translation Lookaside Buffer (TLB)
16
1. TLB is a fast
cache to store a
portion of the
page table.
2. As a result,
instead of two
memory
accesses for
each read, now
we need 1 cache
access and 1
memory access.
3. Since it is a
cache, we need
a tag field.
TLB miss and page fault
• Address cannot be found in TLB → TLB miss
• Need to search the page table (e.g. in main memory), load the
table entry into TLB, and the program will be resumed.
• If a table entry is found, but the valid bit is off. It means
data is not in main memory → page fault.
• Handled by operating system.
• Copy data from disk to main memory, which may previously be
swapped out of main memory to make room for other processes.
• Record the physical page number of the data in main memory.
• Update page table entry: store the physical page number in the
table entry indexed by the virtual page number, update the valid
bit.
• Resume the program, now the data can be found in main
memory.
17
TLB miss and page fault
• A TLB miss – is it a page fault or merely a TLB miss?
• If the page is loaded into main memory, then the TLB miss can
be handled (in hardware or software) by loading the translation
information from the page table into the TLB.
• Takes 10’s of cycles to find and load the translation info into the TLB
• If the page is not in main memory, then it’s a true page fault.
• Takes 1,000,000’s of cycles to service a page fault
• TLB misses are much more frequent than true page
faults.
• On page fault, the page must be fetched from disk.
• Takes millions of clock cycles
• Handled by OS code
• Try to minimize page fault rate
• Fully associative placement
• Smart replacement algorithms
18
Cooperation of TLB & Cache
19
TLB Event Combinations
20
TLB Page
Table
Cache Possible? Under what circumstances?
Hit Hit Hit
Hit Hit Miss
Miss Hit Hit
Miss Hit Miss
Miss Miss Miss
Hit Miss Miss/
Hit
Miss Miss Hit
Yes – what we want!
Yes – although the page table is not
checked if the TLB hits
Yes – TLB miss, PA in page table
Yes – TLB miss, PA in page table, but data
not in cache
Yes – page fault
Impossible – TLB translation not possible if
page is not present in memory
Impossible – data not allowed in cache if
page is not in memory
4 Questions for the Memory Hierarchy
• Q1: Where can a entry be placed in the upper level?
(Entry placement)
• Q2: How is a entry found if it is in the upper level?
(Entry identification)
• Q3: Which entry should be replaced on a miss?
(Entry replacement)
• Q4: What happens on a write?
(Write strategy)
21
CO101�Principle of Computer Organization
Problems
Solution for size limitation
Solution for conflict
Review: The Memory Hierarchy
Virtual Memory
The big picture (32-bit address)
Virtual memory
Convert virtual address to physical address
Convert virtual address to physical address
Loading data using virtual address
Virtual Addressing with a Cache
Problems
Solution
Translation Lookaside Buffers (TLBs)
Table cache: Translation Lookaside Buffer (TLB)
TLB miss and page fault
TLB miss and page fault
Cooperation of TLB & Cache
TLB Event Combinations
4 Questions for the Memory Hierarchy
