Virtual memory is a memory management technique that allows programs to use more memory than physically available by mapping virtual addresses to physical addresses using hardware (MMU) and software (OS), enabling efficient multitasking, faster program startup, and process isolation.
Mind Map
คลิกเพื่อขยาย
คลิกเพื่อสำรวจ Mind Map แบบอินเตอร์แอคทีฟฉบับเต็ม
in the following we will discuss about
virtual memory
virtual memory is related to the second
interface that we will discuss in the
memory hierarchy
which is the interface between the main
memory of the computer
and the secondary memory on magnetic
disk or on flash memory
as the word virtual memory already alludes
alludes
the processor does not work with
physical addresses but when the program executes
executes
in modern computing system it uses
virtual addresses
and these virtual addresses they are
mapped to the physical addresses through
a combination of hardware
which is the memory management unit mmu
and software in the operating system
the main memory itself that is attached
to the processor
is then accessed with physical addresses
as the virtual addresses is what is
presented to the processor
and the programmer and the physical addresses
addresses
is where the memory is actually
installed in our computing system
let us review important terminology
up front so a block on both
virtual and physical memory is denoted
as a page
so the in the cache we denoted this as a block
block
and in the virtual memory context we
denote this block
as the page whenever we have a miss
on the access to the main memory then we
denote this as a page fault
and that adjusts to the cache miss
so here on the bottom we have a small illustration
illustration
how these terms relate to each other so
we have the virtual addresses that are
used by
the processor and we have the physical
addresses that are used by the memory
and then a translation process needs to happen
happen
that translates all virtual addresses to
physical addresses
not all of the memory needs to be
present in the main
not all pages need to be present in the
main memory
at every point in time and some of the pages
pages
may be offloaded or swapped
to disk that means the
virtual addresses can also map to a
there are several motivations for
virtual memory the initial
motivation which was also the main
reason why virtual memory has been introduced
introduced
is that the program can utilize more memory
memory
than is physically available in the system
system
today this is usually not an issue
anymore because
ours our computers have large
dram memories main memory and it is
rarely the case that the program a
single program uses more than the
available memory
another motivation for virtual memory is
that programs can start
fast because without virtual memory
before we can start a program the whole
program had to be brought
in into the main memory before it could
be executed
with virtual memory we bring in the
program on a demand basis
that means page by page we only load
those pages that relates to the program
that is currently executed
into the main memory so the program can
already start executing and we will
bring in
additional codes on a demand basis
the third motivation for virtual memory
which is still
very important today is that modern
operating systems allow
the quasi-parallel execution of processes
processes
and there are several implications of
that or
requirements that are enabled by virtual
memory so first of all the total memory
required by all processes might easily
exceed available physical memory
what i said before us for a single
program it
is rarely the case that it exceeds the
space of the physical memory
but in our current program operating systems
systems
and usage contexts we may have
dozens or hundreds of processes
available at any point in time
and in aggregates their total memory
consumption is typically exceeding
the amount of installed memory in the
system hence virtualization allows us to
only keep a subset
of the memory that is currently used in the
the
available in the physical memory and
offload everything else to secondary storage
storage
further virtual memory is key in providing
providing
isolation of processes from each other
in the operating system
that means that each process can have
its own address space we can
for example execute two programs at the
same time
and these or two instances of the same
program at the same time
and they use the same virtual addresses
but to avoid a conflict when running two
instances of the same program
concurrently the operating system can
translate the addresses the virtual
addresses to different physical addresses
addresses
so these two programs don't conflict
with each other
this is one case where the processes are
isolated from each other to offer also protection
protection
for this protection is between programs
from the same user
but in a multi-user system also
protection of
programs from different users and the
operating system codes that run all concurrently
concurrently
there are several implementation of the
virtual memory concept
and the two most important ones are paging
paging
which uses blocks of constant sizes
this is a so-called program page or the
alternative approach is called
segmentation that uses blocks of
variable size
segmentation was very popular and in
widespread use
a couple of decades ago but today most
of the operating system used the paging concept
concept
simplicity
when we now want to translate an address
from a virtual address
that is exposed to the programmer to the
physical address
which is related to the actually
installed memory
we need to translate translate these
addresses from virtual addresses to
physical addresses
for this purpose we split each address into
into
two into two parts
there's the virtual page number that is translated
translated
into the physical page number so
assuming here we have a virtual address
with 32 bits and the most significant bits
bits
in this case here this is the the up
the bits 12 to 31
comprise the virtual page number and
this virtual page number is then translated
translated
into the physical page number
the page offset is taken one
by one from the virtual address to the
physical address
that means when we want to translate
a virtual address to a physical address
the lowest 12 bits in this example
are the same for both addresses only the
the the most significant bits of the
address change
and the translation between these two
the virtual address in the physical
space is affected by the page table
which we'll discuss in a later point in time
time
in this example we see that the offset
within the page this is the part of the
address that does not change between the
virtual and the physical address has 12 bits
bits
that means we have 2
to the 12 bytes in our page which is 4 kilobytes
kilobytes
which is a typical page size in
similarly to our discussion of cache we
also have the possibility
that in virtual memory we access
a page that is currently not present in
our computing system
and stored on a secondary storage
we denote this as a page fault now in contrast
contrast
to the cache where a page fault requires
to get the data from the lower level cache
cache
or from main memory which has a penalty of
of
a few until dozens or hundreds of clock cycles
cycles
when we have a page fault in the virtual
memory system this incurs an
cost of millions of processor cycles
because the secondary storage is so slow
as we have seen in the initial overview
of the different levels in the memory hierarchy
hierarchy
that means to bring in this page of a
couple of kilobytes of length
from a spinning disc takes in the order
of milliseconds
which means that millions of processor cycles
cycles
will go by until the data has been
retrieved from the secondary memory
to amortize for the very long access
time to secondary memory
pages are made relatively large that
means typically we have page sizes of 4
kilobytes to 16 kilobytes
in many computing systems it is even
possible to
customize the page sizes some operating
systems even support
different page sizes but the standard is
that we will discuss here
the operating system has just a single
page size
in the range that i just indicated
to minimize the number of page faults in
a virtual memory system the pages are
placed fully associatively in the main memory
memory
that means we don't use direct map or
set associative placement but there's
always a fully associative
placement in name memory that means any
virtual page related to a virtual address
address
can be placed at an arbitrary location
in the main memory
so this is required to have an optimal
usage of the main memory
we can also since we need to minimize
the impact of page fall and
fault and the probability for page fault
we can also
use more complex algorithms for placing
the pages
in a good way and this means that the
page faults and page replacements are
handled by the operating system
which can use much more advanced
algorithms as in a
cache for instance where all of the
algorithms for replacements have to be
implemented in hardware
finally when we talk about virtual
memory we always use
the right back policy right through is
not possible
because the access time to the secondary
medium is so long
that it would destroy all of the
performance of the computing system if
you would use
the entity that is providing the
translation between the virtual
addresses and the physical addresses is
a data structure which is called the
page table
and this data structure is used to
identify the location where a page is
stored in a main memory
the basic idea is that the page table
stores for
for each virtual page number the corresponding
corresponding
physical page number the offset doesn't
have to be stored because the
offset is just fed through from when
translating between
virtual pages and physical pages
for each entry and the page table we
have a valid bits
also similar to what we had in caches
that indicates
whether the requested page is currently
stored in memory
or whether it is currently stored on the
each process has its own page table and
this provides the isolation i have
discussed before
so as each process has its own page table
table
it is possible to have two copies of the same
same
process binary and map them to different
physical addresses the page table itself
is stored in the main memory as well
and the start of the page table is held
in the page table register
which is one of the processor registers
that is usually
here we see an example of address
translation by using a page table
the page table is found in memory by the processor
processor
by looking at the page table register
which points to a memory location
where the actual page table is stored in
this case
we use the page table to translate a
virtual address
with the page table into a physical
address that has
hence what we have is we
looked at that each address is split
into two parts one is the page offset
and the rest is the virtual page number
the page offset here has 12 bits
and we have the remaining bits as the
virtual page number
the remaining 20 bits and these 20 bits now
now
index here into the page table and
select one of the entries that has a
width of 18 bits
which then gives us the physical page
number from looking at
these numbers and the width of the
signals we can determine the parameters
of the page table of the computing system
system
so what we see is that the page table
offset is 12 bits
that means we have a 2 to the 12
bytes that
is 4 kilobytes page size
then we if we look at the
virtual page number which has 20 bits
2 to the 20 entries
hence we have a total of
in reality not all of this page table
entries will be used so some of them
will be empty now let's look quickly at
how much
data that we need to store in the page
table if the page table
is stored in memory we have a problem
with storing this 18 bit physical page numbers
numbers
because we need to our address our data
in in the at the word level granularity
rather at the bit level granularity
hence if you store the page table in memory
memory
the size that is required is 2 to the 20
this is the number of entries
multiplied by four bytes
hence we end up with a size of four megabytes
megabytes
this is an example of a page table that
would be used for the mips processor
so we can imagine that a four megabyte
page table still easily fits into the
main memory
of the processor but what we also see is
if we
have a physical uh virtual page
addresses that are no longer
32 bits but 64 bits these page tables
will become excessively large
hence more sophisticated hierarchical
page table
methods are required to fit these page
tables into the main memory of the computer
computer
how can we deal now with page faults
a page fold means that we want to access
a page
and the page is currently not stored in the
the
main memory but it is not present in the
computing system
so we detect the page fault when the
valid bits in the page table is zero
whenever this happens the operating system
system
is triggered by by an exception and the
operating system then takes control
of solving or resolving this page fault
that means the operating system for
instance is a read to a page that is
currently not present in the main memory
the operating system decides which of the
the
currently stored pages in the main
memory shall be replaced
stores back this page to the disk if it is
is
been modified it stores the new contents
to the disk
and then retrieves the requested page
from the disk storage into the operating system
system
the operating system hence does not only
need to store the addresses
with the mapping between the physical
the virtual and the physical memory
but it also needs to take care of
remembering where the pages have been
stored on disks
so this can be done either in the page
table or in a separate table that
translates virtual address
since the secondary memory is much
slower than the memory
we need to be very careful that we keep
those pages in our main memory
which are accessed again with high probability
probability
to avoid that we constantly move pages
between the main memory
and the secondary memory and have the
according overheads
hence our our goal is to exploit the temporal
temporal
locality and memory accesses so since
our programs have
temporal locarity locality and
instruction and data access
the same applies also the pages also
the pages will then be accessed with
temporal locality
to make sure that we keep those pages in
the main memory which
are most likely to be reused the policy
that should be used is the least
recently used policy that means
those pages which did not ha have not
been used for the longest amount of time
are likely not to be used in the close
future and are candidates for replacement
replacement
it is however very difficult and
expensive to implement the exact
least recently used information because
if you imagine how this will be
implemented in the operating system
whenever we make an access to a specific page
page
we need to increment the page usage
counter for this page and that would
incur many thousands or
many instructions and this overhead
would not be
justifiable instead
there is a combination of the operating
system with hardware support
which uses a reference bits per page
table entry
this reference bit in the page table
entry is set
when error and access to a page has been made
made
and the operating system clears these
reference bits from time to time
we can exploit this reference bit now in
the following way so first
all of the reference bits are cleared
and then from time to time this is
triggered by a timer interrupt in the
operating system
for instance every tens of milliseconds
the operating looks at all of the page
table entries
and checks which of the pages have been accessed
accessed
by looking at the reference bit this is
then when the global counters for
page accesses are increased
by one and then the reference bits are
set back to zero so we accumulate the reference
reference
to the to each of the page for a bit of
a longer time
the page table entries are also extended
by dirty bit
this dirty bit is set by a com
set by the processor whenever there is a
writing to a page
that's when we need to replace a page
the operating system can look at the
dirty bit for the corresponding page
table entry
and if the dirty page bit indicates that
the page has been modified
it will be written back into the
secondary memory otherwise
it can be discarded during the
finally to make the replacement of pages
much more efficient the operating system
usually also creates so-called swap space
space
this is a part of the uh
that is reserved for the operating
system only secondary storage on the disk
disk
that is not managed by a file system or
something similar but just a raw
collection of pages that are currently
stored on disk
and by avoiding walking through a file
system structure and so forth the
operating system
can very easily access pages on the disk
and move them back and forth between
the main memory and the disk for later
page replacements
we will now discuss the translation
locker side buffer which is a hardware unit
unit
in our processor to accelerate the
asterisk translation
the problem that is solved by the local
aside buffer is that
it makes the translation of the
addresses more efficient
than if you would just use a software approach
approach
consider the following so our page table
is itself stored in memory
that means if you want to have a memory
access a read or a write
we would first have to look up in the
page table the information how to translate
translate
this virtual address into the physical address
address
and then once we know the physical
address we would have
to make another memory quest to perform
the actual read
and write operation this means that
for every read or write we would have to
make at least
two memory operations which is very costly
costly
and would result in a strong slowdown of
our program
we can however exploit the fact that the
accesses to the page table also show
temporal locality and this is a natural
consequence of the temporal locality in
our program
since the program has temporal locality
in instructions and data
means consecutive addresses are accessed
the consecutive addresses will also be
with very very high likelihoods
part of the same page that means the same
same
address translation will be executed
many times
after each other so there has a very
strong temporal locality in the page
table accesses for that purpose
modern processes use a translational
look aside buffer
also denoted as the tlb and this tlb is
essentially a cache for virtual to
physical address mappings
so whenever we have a translation look
side buffer miss
the processor must determine whether the
request to the page is already in the memory
memory
if this is the case then the
corresponding page table entry is loaded
into the tlb
if this is not as if this is not the
case then this is a page fault
and an exception is raised and the
operating system now
deals with bringing the information from
the main memory
from the page table in the main memory into
into
the cache within the translation looker
site buffer
on this slide we see the relation
between the translation local site buffer
buffer
and the page table that is stored in
memory so on the top here
we see the tlb which is a small cache like
like
structure on the processor which
contains copies
of the page table the page table it can
be very large we have seen the page
tables reach in the order
of megabytes or many megabytes and
therefore they need to be stored in the
main memory
hence the access to this main memory is
rather slow
to provide for a very fast
translation of the virtual page number
into the physical page number
the tlb now has a small cache of the
most recently
used entries from the page table that we
see above here
the tlb has the same data the data
format as the page table
that in this case it has three metadata
bits the valid bit
which denotes whether the entry in the current
current
line of the tlb is valid then it has a
dirty bit
that means whether the page
that is that is translated by this entry
of the tlb
has been modified so it has been written
to or whether this is just a read-only copy
copy
and the reference bit is set to 1
as soon as the page has been referenced
that is read
like for the cache although the tlb
needs to
store the tag of the address that
is currently stored since it acts also
as a cache and then finally as the data contents
contents
the translation to the physical page is
stored here in each of the tlb
entries what we also see here in this illustration
