Memory Organization
G. Rajendra, Assistant Professor,
MCA Department, LBRCE,
Mylavaram
Memory Organization
A memory unit is a device to which binary information
is transferred for storage and from which the
information is retrieved when needed for processing.
A memory unit is a collection of cells capable of
storing a large quantity of binary information.
The process of storing new information into memory
is referred to as a memory write operation.
The process of transferring the stored information out
of memory is referred to as a memory read operation.
A memory unit stores binary information in groups of
bits called words.
Memory Organization.
A word in memory is an entity of bits that move
in and out of storage as a unit.
A memory word is a group of 1s and 0s and
may represent a number, an instruction, one or
more alphanumeric characters, or any other
binary coded information.
A group of 8-bits is called a byte.
Most computer memories use words that are
multiples of 8 bits in length. Thus, a 16-bit word
contains two bytes, and a 32-bit word is made
of four bytes
Memory Organization.
The capacity of a memory unit is usually stated
as the total number of bytes that the unit can
store.
Figure: Block diagram of a
Memory Unit
K address line
Read
Write
n data input lines
Memory Unit
2k words
n bits per word
n data output lines
Memory Organization.
Communication between memory and its
environment is achieved through data input and
output lines, address selection lines and control
lines specify the direction of transfer.
The n data input lines provide the information to
be stored in memory, and the n data output lines
supply the information coming out of memory.
The k address lines specify the particular word
chosen among the many available.
The two control inputs specify the direction of
transfer desired.
Memory Organization.
The write input causes binary data to be
transferred into the memory, and the read input
causes binary data to be transferred out of
memory.
The memory unit is specified by the number of
words it contains and the number of bits in each
word. The address lines select one particular word.
Each word in memory is assigned an identification
number, called address, starting from 0 up to 2 k
1, where k is the number of address lines.
Memory Hierarchy
Main Memory
Main memory is the central storage unit in a
computer system. It is relatively large and fast
memory used to storage programs and data
during the computer operation.
The principle technology used for the main
memory is based on the semiconductor
integrated circuits.
Integrated circuit RAM chips are available in
two possible operating modes: Static and
Dynamic
Main Memory
The static RAM consists of essentially of internal
flip flops that store the binary information. The
stored binary information remains valid as long
as power is applied to the circuit.
Most of the main memory in a general purpose
computer is made up of RAM integrated chips,
but a portion of the memory may be constructed
with ROM chips.
The dynamic RAM offers reduced power
consumption and large storage capacity in a
single memory chip.
Main Memory
The dynamic RAM stores the binary
information in the form of electric charges that
are applied to capacitors. The stored charge on
the capacitors tend to discharge with time and
the capacitors must be periodically recharged
by refreshing the dynamic memory.
The static RAM is easier to use and has
shorter read and write cycles.
RAM is used for storing the bulk of the
programs and data that are subject to change.
Main Memory
ROM is used for storing programs that are
permanently resident in the computer and for table
of constants that do not change in value once the
production of the computer is completed.
ROM portion of the main memory is needed for
storing an initial program called a bootstrap loader.
The Bootstrap loader is a program whose function is
to start the computer software operating when the
power is turned on.
since RAM is volatile, its contents are destroyed
when the power is turned off.
Main Memory
The contents of ROM remain unchanged after
power is turned off and on again.
The startup of a computer consists of turning the
power on and starting the execution of an initial
program. Thus, when the power is turned on, the
hardware of the computer sets the program
counter to the first address of the bootstrap loader.
The bootstrap program loads a portion of a
operating system from disk to main memory and
control is then transferred to the operating system,
which prepares the computer for general use.
Main Memory
Various types of ROM are as follows
1. PROM: Programmable ROM:
This type of ROM that can be programmed
using special equipment, it can be written
to, but only once.
This is useful for companies that make
their own ROMs from software they write,
because when they change their code
they can create a new PROMs without
requiring expensive equipment.
Main Memory
This is similar to the way a CD-ROM recorder works
by letting you burn programs onto blanks once
and then letting you read from them many times.
Erasable programmable ROM(EPROM):
An EPROM is a ROM that can be programmed and
erased by the user using ultraviolet light and
special circuitry external to the computer.
Obviously this is more useful than a regular PROM,
but it does requires the erasing light.
Continuing the CD analogy, this technology is
analogous to a reusable CD-RW.
Main Memory
Electrically Erasable Programmable
ROM(EEPROM):
Can be erased and reprogrammed by special
circuitry within the computer. This is the most
flexible type of ROM and is now commonly used
for holding BIOS programs.
There is a limit to the number of times the
EEPROMs can be reprogrammed, usually
10,000 times.
Main Memory
Flash Memory:
It is electrically erasable and Programmed
permanent type of memory. The entire block is
erased and reprogrammed as a whole at a time.
The name flash memory has been given due
to fast reprogrammed capacity.
Due to lower power consumption flash memory
is used in battery driven digital devices such as
handled computers, cell phones, digital
cameras, MP3 players etc.
Auxiliary Memory
The most common auxiliary memory
devices used in computer systems are
magnetic disks and tapes.
The important characteristics of any
device are its access time, access modes,
transfer rate, and capacity and cost.
The average time required to reach a
storage location in memory and obtain its
contents is called access time.
Auxiliary Memory
Auxiliary memory is organized in records
or blocks. A record is a specified numbers
of characters or words. Reading or writing
is always done on entire records.
The transfer rate is the number of
characters or words that the device can
transfer per second, after it has been
positioned at the beginning of the record.
Auxiliary Memory
Magnetic Disks: A Magnetic Disk is a circular
plate constructed of metal or plastic coated
with magnetized material.
All disks rotate together at high speed and are
not stopped or started for access processes.
Bits are stored in the magnetized surface in
spots along concentric circles called tracks.
The tracks are commonly divided into sections
called sectors.
Auxiliary Memory
Some units use a single read/write head
for each disk surface.
In other disk systems, separate
read/write heads are provided for each
track in each surface.
A disk system is addressed by address
bits that specify the disk number, the
disk surface, the sector number and the
track within the sector.
Auxiliary Memory
After the read/write heads are positioned
in the specified track, the system has to
wait until the rotating disk reaches the
specified sector under the read/write head.
Information transfer is very fast once the
beginning of a sector has been reached.
Disks may have multiple heads and
simultaneous transfer of bits from several
tracks at the same time.
Auxiliary Memory
A track in a given sector near the circumference
is longer than a track near the center of the disk.
If bits are recorded with equal density, some
tracks will contain more recorded bits than
others.
To make all the records in a sector of equal
length, some disks use a variable recording
density. This equalizes the number of bits on all
tracks of a given sector.
A disk drive with removable disks is called a
floppy disk.
Auxiliary Memory
Magnetic Tapes:
Magnetic tapes consists of the electrical,
mechanical, and electronic components to
provide the parts and control mechanism for a
magnetic tape unit.
The tape it self is a strip of plastic coated with
magnetic recording medium. Bits are recorded as
magnetic spots on the tape along several tracks.
Read/write heads are mounted on one track so
that data can be recorded and read as a
sequence of characters.
Auxiliary Memory
Each record on tape has an identification bit
pattern at the beginning and end.
By reading the bit pattern at the beginning , the
tape control identifies the record number.
A tape unit is addressed by specified the record
number and number of characters in the record.
Records may be fixed or variable length.
Memory Hierarchy
The memory unit is an essential
component in any digital computer since
it is needed for storing programs and data
Not all accumulated information is needed
by the CPU at the same time
Therefore, it is more economical to use
low-cost storage devices to serve as a
backup for storing the information that is
not currently used by CPU
Memory Hierarchy
Since 1980, CPU has outpaced
DRAM
Gap grew 50%
per year
Memory Hierarchy
Q. How do architects address this
gap?
A. Put smaller, faster cache
memories between CPU and DRAM.
Create a memory hierarchy.
Memory Hierarchy
The memory unit that directly communicate
with CPU is called the main memory
Devices that provide backup storage are
called auxiliary memory
The memory hierarchy system consists of
all storage devices employed in a computer
system from the slow by high-capacity
auxiliary memory to a relatively faster main
memory, to an even smaller and faster
cache memory
Memory Hierarchy
The main memory occupies a central
position by being able to communicate
directly with the CPU and with auxiliary
memory devices through an I/O processor
A special very-high-speed memory called
cache is used to increase the speed of
processing by making current programs
and data available to the CPU at a rapid
rate
Memory Hierarchy
Memory Hierarchy
CPU logic is usually faster than main memory
access time, with the result that processing
speed is limited primarily by the speed of main
memory
The cache is used for storing segments of
programs currently being executed in the CPU
and temporary data frequently needed in the
present calculations
The typical access time ratio between cache and
main memory is about 1 to 7~10
Auxiliary memory access time is usually 1000
times that of main memory
Main Memory
Most of the main memory in a general
purpose computer is made up of RAM
integrated circuits chips, but a portion of
the memory may be constructed with
ROM chips
RAM Random Access memory
Integated RAM are available in two possible
operating modes, Static and Dynamic
ROM Read Only memory
Random-Access Memory
(RAM)
Static RAM (SRAM)
Each cell stores bit with a six-transistor circuit.
Retains value indefinitely, as long as it is kept powered.
Relatively insensitive to disturbances such as electrical noise.
Faster (8-16 times faster) and more expensive (8-16 times more
expansive as well) than DRAM.
Dynamic RAM (DRAM)
Each cell stores bit with a capacitor and transistor.
Value must be refreshed every 10-100 ms.
Sensitive to disturbances.
Slower and cheaper than SRAM.
SRAM vs DRAM Summary
Tran.
per bit
Access
time
Persist? Sensitive?
Cost
Applications
SRAM
1X
Yes
No
100x
cache memories
DRAM
10X
No
Yes
1X
Main memories,
frame buffers
Virtually all desktop or server
computers since 1975 used DRAMs for
main memory and SRAMs for cache
ROM
ROM is used for storing programs that are
PERMENTLY resident in the computer and
for tables of constants that do not change in
value once the production of the computer
is completed
The ROM portion of main memory is needed
for storing an initial program called
bootstrap loader, witch is to start the
computer software operating when power is
turned off
Main Memory
A RAM chip is better suited for
communication with the CPU if it has
one or more control inputs that select
the chip when needed
The Block diagram of a RAM chip is
shown next slide, the capacity of the
memory is 128 words of 8 bits (one
byte) per word
RAM
ROM
Memory Address Map
Memory Address Map is a pictorial
representation of assigned address space for
each chip in the system
To demonstrate an example, assume that a
computer system needs 512 bytes of RAM and
512 bytes of ROM
The RAM have 128 byte and need seven
address lines, where the ROM have 512 bytes
and need 9 address lines
Memory Address Map
Memory Address Map
The hexadecimal address assigns a range
of hexadecimal equivalent address for each
chip
Line 8 and 9 represent four distinct binary
combination to specify which RAM we chose
When line 10 is 0, CPU selects a RAM. And
when its 1, it selects the ROM
Outline
Memory Hierarchy
Associative Memory
Cache
Virtual memory
Associative Memory
The number of accesses to memory depends on
the location of the item and efficiency of the
search algorithm.
Many search algorithms have been developed to
minimize the number of access while searching
for an item in a random or sequential access
memory.
The time required to find an item stored in
memory can be reduced considerably if stored
data can be identified for access by the content
of the data itself rather than by an address.
Associative Memory
A memory unit accessed by the content is called
an associative memory or content addressable
memory (CAM).
This type of memory is accessed simultaneously
and in parallel on the basis of data content
rather then by specific address or location.
When a word is read from an Associative
memory, the content of the word , or part of the
word, is specified. The memory locates all words
which match the specified content and marks
them for reading.
Associative Memory
Associative Memory is more expensive
than an random access memory because
each cell mast have storage capacity as
well as logic circuits for matching its
content with an external argument.
For this reason, associative memory are
used in applications where the search
time is very critical and must be very
short.
Associative Memory
Hardware Configuration
Associative Memory
It consists of a memory array and logic
for m words with n bits per word. The
argument register A and key register K
each have n bits, one for each bit of a
word.
The match register M as m bits, one for
each memory word. Each word in
memory is compared in parallel with the
content of the argument register.
Associative Memory
Reading is accomplished by a sequential access to
memory for those words whose corresponding bits in
the match register has been set.
The key register provides a mask for choosing a
particular field or key in the argument word.
The entire argument is compared with each memory
word if the key register contains all 1s, otherwise, only
those bits in the argument that have 1s in their
corresponding position of the key register are
compared.
Thus the key provides a mask for identifying piece of
information which specifies how to reference to memory
is made.
Associative Memory
To illustrate with an numeric example,
suppose that the argument register A
and key register K have the bit
configuration as shown below.
Only the three left most bits of A are
compared with memory word because K
has 1s in these positions.
Associative Memory
A
K
Word1
Match
Word2
101 111100
111 000000
100 111100 No
101 000001 Match
Associative Memory
Read Operation
If more than one word in memory matches
the unmasked argument field, all the match
words will have 1s in the corresponding bit
position of the match register.
It is then necessary to scan the bits of the
match register one at a time.
The matched words are read in sequence
by applying a read signal to each word line
whose corresponding Mi bit is a 1.
Associative Memory
Write Operation
An associative memory must have a write
capability for storing the information to be
searched.
Writing in Associative Memory can take
different forms, depending on the application.
If the entire memory is loaded with new
information, at once prior to search operation,
then the writing can be done by addressing
each location in sequence.
Cache memory
If the active portions of the program and
data are placed in a fast small memory,
the average memory access time can be
reduced,
Thus reducing the total execution time of
the program
Such a fast small memory is referred to
as cache memory
The cache is the fastest component in
the memory hierarchy and approaches
the speed of CPU component
Cache memory
The fundamental idea of cache
organization is that by keeping the most
frequently accessed information and data
in the fast cache memory, the average
memory access time will approach the
access time of the cache.
The basic operation of the cache is as
follows. When the CPU needs to access
the memory, the cache is examined. If
the word is found in the cache, it is read
from the fast memory.
Cache memory
When CPU needs to access memory, the
cache is examined
If the word is found in the cache, it is read
from the fast memory
If the word addressed by the CPU is not
found in the cache, the main memory is
accessed to read the word
Cache memory
When the CPU refers to memory and finds
the word in cache, it is said to produce a
hit
Otherwise, it is a miss
The performance of cache memory is
frequently measured in terms of a
quantity called hit ratio
Hit ratio = hit / (hit+miss)
Cache memory
The basic characteristic of cache memory is its
fast access time,
Therefore, very little or no time must be
wasted when searching the words in the cache
The transformation of data from main memory
to cache memory is referred to as a mapping
process, there are three types of mapping:
Associative mapping
Direct mapping
Set-associative mapping
Cache memory
To help understand the mapping
procedure, we have the following
example:
Cache memory
For every word stored in cache, there is a
duplicate copy in main memory. The CPU
communicates with both memories.
It first sends a 15 bit address to cache. If
there is a hit, the CPU accepts the 12 bit
data from the cache. If there is a miss,
the CPU reads the word from the main
memory and the word is transferred to
cache.
Associative mapping
The fastest and most flexible cache
organization uses an associative memory
The associative memory stores both the
address and data of the memory word
This permits any location in cache to store
ant word from main memory
The address value of 15 bits is shown as a
five-digit octal number and its
corresponding 12-bit word is shown as a
four-digit octal number
Associative mapping
Fig: Associative Mapping Cache( all numbers in
octal)
Associative mapping
The diagram shows three words presently
stored in cache.
The address value of 15 bits is shown as a
five digit octal number and its
corresponding 12-bit word is shown as a
four digit octal number.
A CPU address of 15 bits is places in the
argument register and the associative
memory is searched for a matching address
If the address is found, the corresponding
12-bits data is read and sent to the CPU
Associative mapping
If not, the main memory is accessed for the
word
If the cache is full, an address-data pair
must be displaced to make room for a pair
that is needed and not presently in the
cache.
The decision as to what pair is replaced is
determined from the replacement algorithm
that the designer chooses for the cache.
A simple procedure is to replace cells of the
cache in round-robin order When a new
word is requested from main memory. This
constitutes a First-In First Out(FIFO)
replacement policy.
Direct Mapping
Associative memory is expensive
compared to RAM because of the
added logic associated with each cell.
In general case, there are 2^k words in
cache memory and 2^n words in main
memory (in our case, k=9, n=15)
The n bit memory address is divided
into two fields: k-bits for the index and
n-k bits for the tag field
Direct Mapping
The CPU address of 15 bits is divided into
two fields. The nine least significant bits
constitute the index field and the
remaining six bits form the tag field.
The figure shows that main memory
needs an address that includes both tag
and the index bits. The number of bits in
the index field is equal to the number of
address bits required to access the cache
memory.
Direct Mapping
fig: Addressing Relationships Between
Main And Cache Memories
6 bits 9 bits
Address = 15 bits
Data = 12 bits
Address = 9
bits
Data = 12 bits
Direct Mapping
In general case, there are 2^k words in cache
memory and 2^n words in main memory. The
n-bit memory address is divided into two
fields: K bits for the index field and n-k bits for
the tag field.
The direct mapping cache organization uses
the n-bit address to access the main memory
and k-bit index to access the access the cache.
The internal organization of the words in the
cache memory as shown in figure below.
Direct Mapping
Fig: Direct mapping cache organization
a. Main Memory
b. Cache Memory
Direct Mapping
Each word in cache consists of the data
word and its associated tag. When a new
word is first brought into the cache, the tag
bits are stored alongside the data bits.
When the CPU generates a memory
request, the index field is used for the
address to access the cache.
The tag field of the CPU address is
compared with the tag filed in the word
read from the cache.
Direct Mapping
If the two tags match, there is a hit and
the desired data word is in cache. If
there is no match, there is a miss and
the required word is read from the main
memory.
The disadvantage of direct mapping is if
two or more words whose address have
the same index but different tags are
accessed repeatedly.
Direct Mapping
Fig: Direct Mapping Cache with a block size of 8 words
Block 0
Index
Tag
000
01
3450
007
01
6578
Data
6
Tag
Block
Word
010
Block 1
017
Index
770
Block 63 777
02
6710
02
Direct Mapping
The word at address zero is presently stored in
the cache (index=000,tag=00,data=1220).
Suppose that the CPU now wants to access the
word at address 02000. The index address is
000, so it is used to access the cache.
The two tags are compared. The cache tag 00
but the address tag is 02, which does not
produce a match. Therefore, the main memory is
accessed and the data word 5670 is transferred
to the CPU.
The cache word at index address 000 is then
replaced with a tag of 02 and data of 5670.
Set-Associative Mapping
The disadvantage of direct mapping is that
two words with the same index in their
address but with different tag values cannot
reside in cache memory at the same time
Set-Associative Mapping is an improvement
over the direct-mapping in that each word of
cache can store two or more word of
memory under the same index address
Set-Associative Mapping
Fig: Two-Way Set-Associative Mapping Cache
Set-Associative Mapping
Each data word is stored together with its tag
and the number of tag-data items in one word
of cache is said to form a set.
The words stored at address 01000 and 02000
of main memory are stored in cache memory at
index address 000.
Similarly, the words at addresses 02777 and
00777 are stored in cache at index address 777.
When the CPU generates a memory request, the
index value of the address is used to access the
cache.
Set-Associative Mapping
In the slide, each index address
refers to two data words and their
associated tags
Each tag requires six bits and each
data word has 12 bits, so the word
length is 2*(6+12) = 36 bits
Cache Memory
Writing into Cache
If the operation is a write , there are two ways that the
system can proceed.
Write-through method: The simplest and commonly
used procedure is to update main memory with every
memory write operation, with cache memory being updated
in parallel if it contains the word at the specified address.
This method as the advantage that main memory always
contains the same data as the cache.
Write-back method: In this method only the cache location
is updated during a write operation. The location is then
marked by a flag so that later when the word is removed
from the cache it is copied into main memory.
Virtual Memory
Virtual memory is a concept used in some
large computer systems that permit the
user to construct programs as though a
large memory space were available,
equal to the totality of auxiliary memory.
Each address that is referenced by the
CPU goes through an addressing mapping
from the so called virtual address to a
physical address in main memory.
Virtual Memory
Virtual memory is used to give programmers
the illusion that they have a very large memory
at their disposal, even though the computer
actually has relatively small main memory.
Virtual memory system provides a mechanism
for translating program-generated addresses
into correct main memory locations.
This is done dynamically, while programs are
being executed in the CPU. The translation or
mapping is handled automatically by the
hardware by means of mapping table.
Virtual Memory
Address Space and Memory Space
An address used by a programmer will be called a virtual
address, and the set of such addresses the address
space.
An address in main memory is called a location or
physical address. The set of such locations is called
memory space.
The address space is the set of addresses generated by
programs as they reference instructions and data; the
memory space consists of the actual main memory
locations directly addressable for processing
In most computers the address and memory spaces are
identical. The address space is allowed to be larger than
the memory space in computer with a main memory
Virtual Memory
As an illustration, consider a computer with a main memory
capacity of 32k words(k=1024). Fifteen bits are needed to
specify a physical address in memory since 32k = 2^15
Suppose that the computer has available auxiliary memory
for storing 1024k= 2^20 words. Thus the auxiliary memory
has a capacity for storing information equivalent to the
capacity of 32 main memories.
Denoting the address space by N and the memory space by
M, we than have for this example N=1024 k and M=32 k
The address used by a programmer will be called a logical
address
An address in main memory is called a physical address
Virtual Memory
Fig: relation between address and memory space in a
virtual memory system
Auxiliary Memory
Program1
Data1,1
Data1,2
Main Memory
Program1
Program 2
Data 2,1
Data 1,1
Address Space
N=1024K=2^20
Memory space
M=32k=2^15
Virtual Memory
Fig: Memory table for mapping a virtual address
Virtual
addres
s
register
(20
bits)
Memory
Mapping
Table
Memory
Table
Buffer
register
Main
Memory
address
register
(15 bits)
Main
Memory
Main
Memory
Buffer
Register
Virtual Memory
Address mapping using pages:
The implementation of the address mapping is simplified
if the information in the address space and the memory
space are divided into groups of fixed size.
The physical memory is broken down into groups of equal
size called blocks.
The term page refers to groups of address space of the
same size
For example, if a page or block consists of 1k words, then
using previous example, address space is divided into
1024 pages and main memory is divided into 32 blocks
Virtual Memory
The programs are also considered to be split
into pages. Portions of programs are moved
from auxiliary memory to main memory in
records of equal size of a page. The term
page-frame is some times used to denote a
block.
Consider a computer with an address space of
8k and memory space of 4k. If we split each
into groups of 1k words we obtain eight pages
and four blocks as shown in figure.
Virtual Memory
Fig: Address space and memory space split into groups of 1k words
Page 0
Page 1
Block 0
Address space Page 2
N = 8k = 2^13Page 3
Block 1
Page 4
Block 3
space
Page 5
M = 4K = 2^12
Page 6
Page 7
Block 2
Memory
Virtual Memory
The programs are also considered to be split
into pages. Portions of programs are moved
from auxiliary memory to main memory in
records of equal size of a page. The term
page-frame is some times used to denote a
block.
Consider a computer with an address space of
8k and memory space of 4k. If we split each
into groups of 1k words we obtain eight pages
and four blocks as shown in figure.
Virtual Memory
The mapping from address space to memory space is
facilitated if each virtual address is considered to be
represented by two numbers:
A page number address and line within the page
In the example of above figure, a virtual address has 13
bits since each page consists of 2^10 =1024 words,
the high order three bits of a virtual address will
specify one of the eight pages and the lower order 10
bits give the line address within the page.
At any time, up to four pages of address space may
reside in main memory in any one of the four blocks.
The organization of memory mapping table in a paged
system is shown in figure below.
Page no Line number
1 0 1 010101 0 0 1
1
000
001
010
Virtual address
Presence bit
Main memory
Block 0
11
Block 1
00
Table Address
0
1
010101001
1
Virtual
Memory
0
100
0
011
Main memory address register
Block 2
Block 3
Fig:
01
1 table in a paged system
101 Memory
110
10
111
Memory page table
01
MBR
Virtual Memory
The memory page table consists of eight words; one for
each page. The address in the page table denotes the
page number and the content of the word gives the block
number where that page is stored in main memory.
The table shows that pages 1,2,5 and 6 are now available in
main memory in blocks 3,0,1 and 2 respectively.
A presence bit in each location indicates whether the page
has been transferred from auxiliary memory into main
memory.
A 0 in the presence bit indicates that this page is not
available in main memory.
The CPU references a word in memory with a virtual address
of 13 bits. Three high order bits of the virtual address
specify a page number and also an address for the
memory page table.
Virtual Memory
The line number from the virtual address is transferred
into the 10 low-order bits of the memory address
register.
Associative Memory Page Table:
A more efficient way to organize the page table would
be to construct it with a number of words equal to the
number of blocks in main memory.
This method can be implemented by means of an
associative memory with each word in memory
containing page number together with its
corresponding block number.
Virtual Memory
Fig: An associative memory page table
Virtual Address
Page no
1
1
0
0
1
1
1
Line Number
0
001
11
010
00
101
01
110
10
Page No
Block No
Key Register
Associative Memory
Argument Register
Virtual Memory
Each entry in the associative memory array consists of two
fields. The first three bits specify a field for storing the page
number.
The last two bits consists a field for storing the block number
The virtual address is placed in the argument register. The
page number bits in the argument register are compared
with all page numbers in the page field of the associative
memory.
If the page number is found, the 5bit word is read out from
memory. The corresponding block number, being in the
same word, is transferred to the main memory address
register.
If no match occurs, a call to the operating system is generated
to bring the required page from auxiliary memory.
Page Replacement
The memory management software system handles
all the software operations for the efficient utilization
of memory space.
It must decide
1.which page in main memory should be removed to
make a room for a new page.
2.when a new page is to be transferred from
auxiliary memory to main memory.
3. where the page is to be placed in main memory.
The program is executed from main memory until it
attempts to reference a page that is still in auxiliary
memory. This condition is called page fault.
Page Replacement
When page fault occurs, the execution of the present
program is suspended until the required page is brought
into main memory.
Since loading a page from auxiliary to main memory
basically an I/O operation, the operating system assigns
this task to the I/O processor.
If main memory is full, it would be necessary to remove a
page from memory block to make room for the new page.
The policy for choosing pages to remove is determined
from the replacement algorithms that is used.
The goal of replacement policy is to try to remove the
page least likely to be referenced in the immediate
future.
Page Replacement
Two of the most common replacement algorithms used
are First-In, First Out (FIFO), and the Least Recently
Used(LRU)
FIFO algorithm selects for replacement the page that
has been in memory the longest time.
The LRU policy is more difficult to implement but has
been more attractive on the assumption that the least
recently used pages is a better candidate for removal
then the least recently loaded pages as in FIFO.
