virtual memory

Virtual Memory
If the valid bit is zero in the page table entry for the logical
address, this means that the page is not in memory and
must be fetched from disk.
– This is a page fault.
– If necessary, a page is evicted from memory and is
replaced by the page retrieved from disk, and the valid
bit is set to 1.

If the valid bit is 1, the virtual page number is replaced by
the physical frame number.
The data is then accessed by adding the offset to the
physical frame number.
As an example, suppose a system has a virtual address
space of 8K and a physical address space of 4K, and the
system uses byte addressing.
– We have 213/210 = 23 virtual pages – each page is 1K
A virtual address has 13 bits (8K = 213) with 3 bits for the
page field and 10 for the offset, because the page size is
1024.
A physical memory address requires 12 bits, the first two
bits for the page frame and the trailing 10 bits the offset.

Virtual Memory

What if a process has an address space larger than Physical
Memory? For instance, you want 2 gigabytes of
instructions/storage to run on a machine with 1 gigabyte of
physical memory?
Main Memory (DRAM)?
Process Address space is 0 to 2n-1 where n = machine
size (I.e. 32 bit) Main memory is temporary storage; not
as big as process address space. Instead your program is
usually stored on some form of permanent storage (disk or
tape).
Why not just make main memory large enough?
• Can’t rely totally on Memory Technology – cost, speed and
capacity factors
Memory Comparison - cost
• Full address space is quite large:
e.g. 32-bit address (with 1 byte storage ): ~4 GB
• Disk storage is ~300X cheaper than DRAM
80 GB of DRAM: ~ $5,000 vs. 200 GB of disk: ~ $70
• To access large amounts of data in a cost-effective
manner, the bulk of the data must be stored on disk
Original Motivation for VM
• IBM wanted one software suite for a family of System 370
computers
• Allowed customers to purchase a smaller system with the
knowledge they could upgrade to larger system
• Allowing same program run on machines with different
memory sizes (Earlier programmers had to do explicit
memory management)
• Idea was to create an illusion for a process that it has
memory as big as its address space. Hence the concept of
Virtual Memory i.e. memory appears to be but isn't.
• A physical address is the actual memory address of
physical memory. We’ve seen this address in our PIC
programming.
• Programs use virtual addresses that are mapped to
physical addresses by the memory manager. (Example
– suppose I have three identical processes running.
How could they each touch a piece of data at location
1000?)
• Page faults occur when a logical address requires that a
page be brought in from disk.
• Memory fragmentation occurs when the paging process
results in the creation of small, unusable clusters of
memory addresses.
• Main memory and virtual memory are divided into equal
sized pages.
• The entire address space required by a process need
not be in memory at once. Some parts can be on disk,
while others are in main memory.
• Further, the pages allocated to a process do not need to
be stored contiguously-- either on disk or in memory.
• In this way, only the needed pages are in memory at
any time, the unnecessary pages are in slower disk
storage.

The Memory Hierarchy

• Faster memory is more expensive than slower memory.
• For the best performance at the lowest cost, memory is organized in a
hierarchical fashion.
• Small, fast storage elements are kept in the CPU, larger, slower main memory
is accessed through the data bus.
• Larger, (almost) permanent storage in the form of disk and tape drives is still
further from the CPU.
• An entire blocks of data is copied after a hit because the principle of
locality tells us that once a byte is accessed, it is likely that a
nearby data element will be needed soon.
• There are three forms of locality:
– Temporal locality- Recently-accessed data elements tend to be
accessed again.
– Spatial locality - Accesses tend to cluster.
– Sequential locality - Instructions tend to be accessed
sequentially.
• Cache Line -- The number of bytes brought in with this block
Mechanism:
• To access a particular piece of data, the CPU sends a request to its
nearest memory, usually cache.
• If the data is not in cache, then main memory is queried. If the data is
not in main memory, then the request goes to disk.
• Once the data is located, the data,
SDRAM; Random Access Memory
• Short for Synchronous DRAM, a type of DRAM that can run at much
higher clock speeds than conventional memory. SDRAM actually
synchronizes itself with the CPU's bus and is capable of running at 133
MHz,
DDR (Double Data Rate) is a technology used in some SDRAM memories
to increase the speed at which data can be written/retrieved from the
memory.
DDR increase the transfer rate by sending/receiving memory data twice
per clock cycle. This give a theoretical multiplication of transfer speed by
two.
DDR2-SDRAM maintains the same core functions, transferring 64 bits of data twice
every clock cycle for an effective transfer rate twice that of the front-side bus
(FSB) of a computer system, and an effective bandwidth equal to its speed x 8.
Flash Memory
A type of EEPROM.
Non-volatile – doesn’t require power to
hold data.
Data is written in blocks - not byte
accessible. Great for disk-like devices
requiring 4096 bytes to be read/written;
not good for Random Access Memory.
Limited to 1,000,000 cycles – and blocks
can go bad.
The controller can do bad block remapping
and error checking.
The controller can do wear leveling –
moving blocks around so that no one
area on the chip has excessive wear.

Cache Memory

• The purpose of cache memory is to speed up
accesses by storing recently used data closer to the
CPU, instead of storing it in main memory.
• Although cache is much smaller than main memory,
its access time is a fraction of that of main memory.
• Unlike main memory, which is accessed by address,
cache is typically accessed by content; hence, it is
often called content addressable memory.
• Because of this, a single large cache memory isn’t
always desirable-- it takes longer to search.
• The “content” that is addressed in content
addressable cache memory is a subset of the bits of
a main memory address called a field.
• The fields into which a memory address is divided
provide a many-to-one mapping between larger
main memory and the smaller cache memory.
• Many blocks of main memory map to a single block
of cache. A tag field in the cache block
distinguishes one cached memory block from
another.
• The simplest cache mapping scheme is direct
mapped cache.
• In a direct mapped cache consisting of N blocks of
cache, block X of main memory maps to cache block
Y = X mod N.
• Thus, if we have 10 blocks of cache, block 7 of cache
may hold blocks 7, 17, 27, 37, . . . of main memory.
• Once a block of memory is copied into its slot in
cache, a valid bit is set for the cache block to let the
system know that the block contains valid data.