Department of Electronics Engineering

TE-Sem 5-COA

Module 3 - Memory Organization

Classification of Memory

In computers, memory is the most essential component of the normal functioning

of any system. The computer system categorizes the memory for different
purposes and uses. In this section, we have discussed the classification of
memory in detail. Also, we will discuss types of memory, features of memory,
RAM, ROM, SRAM, DRAM, and its advantages and disadvantages.

What is computer memory?

Computer memory is any physical device, used to store data, information or

instruction temporarily or permanently. It is the collection of storage units that
stores binary information in the form of bits. The memory block is split into a small
number of components, called cells. Each cell has a unique address to store the
data in memory, ranging from zero to memory size minus one. For example, if the
size of computer memory is 64k words, the memory units have 64 * 1024 = 65536
locations or cells. The address of the memory's cells varies from 0 to 65535.
 Department of Electronics Engineering
TE-Sem 5-COA

Why do we need a computer memory?

In the computer system, we need computer memory to store various types of data
like text, images, video, audio, documents, etc. We can retrieve it when the data is
required. For example, when we write and execute any computer program, it is
initially stored in primary memory. If the processor does not need particular items
for a longer time, the program or data is automatically saved into the permanent
or secondary memory. Then the data is called from secondary memory to main
memory and performs the execution of codes.

Features of Memory

Following are the different features of the memory system that includes:

1. Location: It represents the internal or external location of the memory in a

computer. The internal memory is inbuilt in computer memory. It is also
known as primary memory. the example of primary memory are registers,
cache and main memory. Whereas, external memory is the separate storage
device from the computer, such as disk, tape, USB pen drive.

2. Capacity: It is the most important feature of computer memory. Storage

capacity can vary in external and internal memory. External devices' storage
capacity is measured in terms of bytes, whereas the internal memory is
measured with bytes or words. The storage word length can vary in bits, such
as 8, 16 or 32 bits.

3. Access Methods: Memory can be accessed through four modes of memory.

 Department of Electronics Engineering
TE-Sem 5-COA

o DMA: As the name specifies, Direct Memory Address (DMA) is a

method that allows input/output (I/O) devices to access or retrieve
data directly or from the main memory.

o Sequential Access Method: The sequential access method is used in a

data storage device to read stored data sequentially from the
computer memory. Whereas, the data received from random access
memory (RAM) can be in any order.

o Random Access Method: It is a method used to randomly access data

from memory. This method is the opposite of SAM. For example, to go
from A to Z in random access, we can directly jump to any specified
location. In the Sequential method, we have to follow all intervening
from A to Z to reach at the particular memory location.

o Associative Access Method: It is a special type of memory that

optimizes search performance through defined data to directly access
the stored information based on a memory address.

4. Unit of transfer: As the name suggests, a unit of transfer measures the

transfer rate of bits that can be read or write in or out of the memory devices.
The transfer rate of data can be different in external and internal memory.

o Internal memory: The transfer rate of bits is mostly equal to the word
size.

o External memory: The transfer rate of bit or unit is not equal to the
word length. It is always greater than a word or may be referred to
as blocks.
 Department of Electronics Engineering
TE-Sem 5-COA

5. Performance: The performance of memory is majorly divided into three

parts.

o Access Time: In random access memory, it represents the total time

taken by memory devices to perform a read or write operation that an
address is sent to memory.

o Memory Cycle Time: Total time required to access memory block and
additional required time before starting second access.

o Transfer rate: It describes the transfer rate of data used to transmit

memory to or from an external or internal memory device. Bit transfer
can be different for different external and internal devices.

6. Physical types: It defines the physical type of memory used in a computer

such as magnetic, semiconductor, magneto-optical and optical.

7. Organization: It defines the physical structure of the bits used in memory.

8. Physical characteristics: It specifies the physical behaviour of the memory

like volatile, non-volatile or non-erasable memory. Volatile memory is known
as RAM, which requires power to retain stored information, and if any power
loss has occurred, stored data will be lost. Non-volatile memory is a
permanent storage memory that is used to obtain any stored information,
even when the power is off. Non-erasable memory is a type of memory that
cannot be erased after the manufactured like ROM because at the time of
manufactured ROM are programmed.
 Department of Electronics Engineering
TE-Sem 5-COA

Classification of Memory

The following figure represents the classification of memory:

Primary or Main Memory

Primary memory is also known as the computer system's main memory that
communicates directly within the CPU, Auxiliary memory and the Cache memory.
Main memory is used to kept programs or data when the processor is active to use
them. When a program or data is activated to execute, the processor first loads
instructions or programs from secondary memory into main memory, and then the
processor starts execution. Accessing or executing of data from primary memory is
faster because it has a cache or register memory that provides faster response, and
it is located closer to the CPU. The primary memory is volatile, which means the
data in memory can be lost if it is not saved when a power failure occurs. It is
 Department of Electronics Engineering
TE-Sem 5-COA

costlier than secondary memory, and the main memory capacity is limited as
compared to secondary memory.

The primary memory is further divided into two parts:

1. RAM (Random Access Memory)

2. ROM (Read Only Memory)

Random Access Memory (RAM)

Random Access Memory (RAM) is one of the faster types of main memory accessed
directly by the CPU. It is the hardware in a computer device to temporarily store
data, programs or program results. It is used to read/write data in memory until
the machine is working. It is volatile, which means if a power failure occurs or the
computer is turned off, the information stored in RAM will be lost. All data stored
in computer memory can be read or accessed randomly at any time.
 Department of Electronics Engineering
TE-Sem 5-COA

There are two types of RAM:

o SRAM

o DRAM

DRAM: DRAM (Dynamic Random-Access Memory) is a type of RAM that is used

for the dynamic storage of data in RAM. In DRAM, each cell carries one-bit
information. The cell is made up of two parts: a capacitor and a transistor. The size
of the capacitor and the transistor is so small, requiring millions of them to store
on a single chip. Hence, a DRAM chip can hold more data than an SRAM chip of the
same size. However, the capacitor needs to be continuously refreshed to retain
information because DRAM is volatile. If the power is switched off, the data store
in memory is lost.

Characteristics of DRAM

1. It requires continuously refreshed to retain the data.

2. It is slower than SRAM

3. It holds a large amount of data

4. It is the combination of capacitor and transistor

5. It is less expensive as compared to SRAM

6. Less power consumption

SRAM: SRMA (Static Random-Access Memory) is a type of RAM used to store

static data in the memory. It means to store data in SRAM remains active as long
as the computer system has a power supply. However, data is lost in SRAM when
power failures have occurred.
 Department of Electronics Engineering
TE-Sem 5-COA

Characteristics of Static Ram

1. It does not require to refresh.

2. It is faster than DRAM

3. It is expensive.

4. High power consumption

5. Longer life

6. Large size

7. Uses as a cache memory

SRAM Vs. DRAM

SRAM DRAM

It is a Static Random-Access Memory. It is a Dynamic Random Access

Memory.

The access time of SRAM is slow. The access time of DRAM is high.

It uses flip-flops to store each bit of It uses a capacitor to store each bit of
information. information.

It does not require periodic refreshing to It requires periodically refreshing to

preserve the information. preserve the information.

It uses in cache memory. It is used in the main memory.

 Department of Electronics Engineering
TE-Sem 5-COA

The cost of SRAM is expensive. The cost of DRAM is less expensive.

It has a complex structure. Its structure is simple.

It requires low power consumption. It requires more power consumption.

Advantages of RAM

o It is a faster type of memory in a computer.

o It requires less power to operate.

o Program loads much faster

o More RAM increases the performance of a system and can multitask.

o Perform read and write operations.

o The processor can read information faster than a hard disc, floppy, USB, etc.

Disadvantages of RAM

o Less RAM reduces the speed and performance of a computer.

o Due to volatile, it requires electricity to preserve the data.

o It is expensive than ROM

o It is unreliable as compared to ROM

o The Size of RAM is limited.

 Department of Electronics Engineering
TE-Sem 5-COA

Read-Only Memory (ROM)

ROM is a memory device or storage medium that is used to permanently store

information inside a chip. It is a read-only memory that can only read stored
information, data or programs, but we cannot write or modify anything. A ROM
contains some important instructions or program data that are required to start or
boot a computer. It is a non-volatile memory; it means that the stored information
cannot be lost even when the power is turned off or the system is shut down.

Types of ROM

There are five types of Read Only Memory:

1. MROM (Masked Read Only Memory):

MROM is the oldest type of read-only memory whose program or data is pre-
configured by the integrated circuit manufacture at the time of
manufacturing. Therefore, a program or instruction stored within the MROM
chip cannot be changed by the user.
 Department of Electronics Engineering
TE-Sem 5-COA

2. PROM (Programmable Read Only Memory):

It is a type of digital read-only memory, in which the user can write any type
of information or program only once. It means it is the empty PROM chip in
which the user can write the desired content or program only once using the
special PROM programmer or PROM burner device; after that, the data or
instruction cannot be changed or erased.

3. EPROM (Erasable and Programmable Read Only Memory):

It is the type of read only memory in which stored data can be erased and re-
programmed only once in the EPROM memory. It is a non-volatile memory
chip that holds data when there is no power supply and can also store data
for a minimum of 10 to 20 years. In EPROM, if we want to erase any stored
data and re-programmed it, first, we need to pass the ultraviolet light for 40
minutes to erase the data; after that, the data is re-created in EPROM.

4. EEPROM (Electrically Erasable and Programmable Read Only Memory):

The EEROM is an electrically erasable and programmable read only memory

used to erase stored data using a high voltage electrical charge and re-
programmed it. It is also a non-volatile memory whose data cannot be erased
or lost; even the power is turned off. In EEPROM, the stored data can be
erased and reprogrammed up to 10 thousand times, and the data erase one
byte at a time.
 Department of Electronics Engineering
TE-Sem 5-COA

5. Flash ROM:

Flash memory is a non-volatile storage memory chip that can be written or

programmed in small units called Block or Sector. Flash Memory is an
EEPROM form of computer memory, and the contents or data cannot be lost
when the power source is turned off. It is also used to transfer data between
the computer and digital devices.

Advantages of ROM

1. It is a non-volatile memory in which stored information can be lost even

power is turned off.

2. It is static, so it does not require refreshing the content every time.

3. Data can be stored permanently.

4. It is easy to test and store large data as compared to RAM.

5. These cannot be changed accidently

6. It is cheaper than RAM.

7. It is simple and reliable as compared to RAM.

8. It helps to start the computer and loads the OS.

Disadvantages of ROM

1. Store data cannot be updated or modify except to read the existing data.

2. It is a slower memory than RAM to access the stored data.

3. It takes around 40 minutes to destroy the existing data using the high charge
of ultraviolet light.
 Department of Electronics Engineering
TE-Sem 5-COA

RAM Vs. ROM

RAM ROM

It is a Random-Access Memory. It is a Read Only Memory.

Read and write operations can be Only Read operation can be performed.
performed.

Data can be lost in volatile memory Data cannot be lost in non-volatile

when the power supply is turned off. memory when the power supply is turned
off.

It is a faster and expensive memory. It is a slower and less expensive memory.

Storage data requires to be Storage data does not need to be

refreshed in RAM. refreshed in ROM.

The size of the chip is bigger than the The size of the chip is smaller than the
ROM chip to store the data. RAM chip to store the same amount of
data.

Types of RAM: DRAM and SRAM Types of ROM: MROM, PROM, EPROM,
EEPROM
 Department of Electronics Engineering
TE-Sem 5-COA

Secondary Memory

Secondary memory is a permanent storage space to hold a large amount of data.

Secondary memory is also known as external memory that representing the various
storage media (hard drives, USB, CDs, flash drives and DVDs) on which the
computer data and program can be saved on a long term basis. However, it is
cheaper and slower than the main memory. Unlike primary memory, secondary
memory cannot be accessed directly by the CPU. Instead of that, secondary
memory data is first loaded into the RAM (Random Access Memory) and then sent
to the processor to read and update the data. Secondary memory devices also
include magnetic disks like hard disk and floppy disks, an optical disk such as CDs
and CDROMs, and magnetic tapes.

Features of Secondary Memory

o Its speed is slower than the primary/ main memory.

o Store data cannot be lost due to non-volatile nature.

o It can store large collections of different types, such as audio, video, pictures,
text, software, etc.

o All the stored data in a secondary memory cannot be lost because it is a

permanent storage area; even the power is turned off.

o It has various optical and magnetic memories to store data.

Types of Secondary Memory

The following are the types of secondary memory devices:

 Department of Electronics Engineering
TE-Sem 5-COA

Hard Disk

A hard disk is a computer's permanent storage device. It is a non-volatile disk that

permanently stores data, programs, and files, and cannot lose store data when the
computer's power source is switched off. Typically, it is located internally on
computer's motherboard that stores and retrieves data using one or more rigid fast
rotating disk platters inside an air-sealed casing. It is a large storage device, found
on every computer or laptop for permanently storing installed software, music, text
documentation, videos, operating system, and data until the user did not delete.

Floppy Disk

A floppy disk is a secondary storage system that consisting of thin, flexible magnetic
coating disks for holding electronic data such as computer files. It is also known as
Floppy Diskette that comes in three sizes like 8 inches, 5.5 inches and 3.5 inches.
The stored data of a floppy disk can be accessed through the floppy disk drive.
Furthermore, it is the only way through a new program installed on a computer or
backup of the information. However, it is the oldest type of portable storage device,
which can store data up to 1.44 MB. Since most programs were larger, that required
 Department of Electronics Engineering
TE-Sem 5-COA

multiple floppy diskettes to store large amounts of data. Therefore, it is not used
due to very low memory storage.

CD (Compact Disc)

A CD is an optical disk storage device, stands for Compact Disc. It is a storage device
used to store various data types like audio, videos, files, OS, Back-Up file, and any
other information useful to a computer. The CD has a width of 1.2 mm and 12 cm
in height, which can store approximately 783 MB of data size. It uses laser light to
read and write data from the CDs.
 Department of Electronics Engineering
TE-Sem 5-COA

Types of CDs

1. CD-ROM (Compact Disc Read Only Memory): It is mainly used for bulk size
mass like audio CDs, software and computer games at the time of
manufacture. Users can only read data, text, music, videos from the disc, but
they cannot modify or burnt it.

2. CD-R (Compact Disc Recordable): The type of Compact Disc used to write
once by the user; after that, it cannot be modified or erased.

3. CD-RW (Compact Disc Rewritable): It is a rewritable CD disc, often used to

write or delete the stored data.

DVD Drive/Disc

DVD is an optical disc storage device, stands for Digital Video Display or Digital
Versatile Disc. It has the same size as a CD but can store a larger amount of data
than a compact disc. It was developed in 1995 by Sony, Panasonic, Toshiba and
Philips four electronics companies. DVD drives are divided into three types, such as
DVD ROM (Read Only Memory), DVD R (Recordable) and DVD RW (Rewritable or
Erasable). It can store multiple data formats like audio, videos, images, software,
operating system, etc. The storing capacity of data in DVD is 4.7 GB to 17 GB.
 Department of Electronics Engineering
TE-Sem 5-COA

Blu Ray Disc (BD)

Blu Ray is an Optical disc storage device used to store a large amount of data or
high definition of video recording and playing other media files. It uses laser
technology to read the stored data of the Blu-ray Disk. It can store more data at a
greater density as compared to CD/ DVD. For example, compact discs allow us to
store 700 MB of data, and in DVDs, it provides up to 8 GB of storage capacity, while
Blu-ray Discs provide 28 GB of space to store data.

Pen Drive

A pen drive is a portable device used to permanently store data and is also known
as a USB flash drive. It is commonly used to store and transfer the data connected
to a computer using a USB port. It does not have any moveable part to store the
data; it uses an integrated circuit chip that stores the data. It allows the users to
store and transfer data like audio, videos, images, etc. from one computer to any
USB pen drive. The storing capacity of pen drives from 64 MB to 128 GB or more.

Cache Memory

It is a small-sized chip-based computer memory that lies between the CPU and the
main memory. It is a faster, high performance and temporary memory to enhance
 Department of Electronics Engineering
TE-Sem 5-COA

the performance of the CPU. It stores all the data and instructions that are often
used by computer CPUs. It also reduces the access time of data from the main
memory. It is faster than the main memory, and sometimes, it is also called CPU
memory because it is very close to the CPU chip. The following are the levels of
cache memory.

1. L1 Cache: The L1 cache is also known as the onboard, internal, or primary

cache. It is built with the help of the CPU. Its speed is very high, and the size
of the L1 cache varies from 8 KB to 128 KB.

2. L2 Cache: It is also known as external or secondary cache, which requires fast

access time to store temporary data. It is built into a separate chip in a
motherboard, not built into the CPU like the L1 level. The size of the L2 cache
may be 128 KB to 1 MB.

3. L3 Cache: L3 cache levels are generally used with high performance and
capacity of the computer. It is built into a motherboard. Its speed is very
slow, and the maximum size up to 8 MB.
 Department of Electronics Engineering
TE-Sem 5-COA

Advantages of Cache Memory

1. Cache memory is the faster memory as compared to the main memory.

2. It stores all data and instructions that are repeatedly used by the CPU for
improving the performance of a computer.

3. The access time of data is less than the main memory.

Disadvantage of Cache Memory

1. It is very costly as compared to the Main memory and the Secondary

memory.

2. It has limited storage capacity.

Register Memory

The register memory is a temporary storage area for storing and transferring the
data and the instructions to a computer. It is the smallest and fastest memory of a
computer. It is a part of computer memory located in the CPU as the form of
registers. The register memory is 16, 32 and 64 bits in size. It temporarily stores
data instructions and the address of the memory that is repeatedly used to provide
faster response to the CPU.
 Department of Electronics Engineering
TE-Sem 5-COA

Primary Vs. Secondary Memory

Primary Memory Secondary Memory

It is also known as temporary memory. It is also known as a permanent

memory.

Data can be access directly by the Data cannot be accessed directly by the
processor or CPU. I/O processor or CPU.

Stored data can be a volatile or non- The nature of secondary memory is

volatile memory. always non-volatile.

It is more costly than secondary It is less costly than primary memory.

memory.

It is a faster memory. It is a slower memory.

It has limited storage capacity. It has a large storage capacity.

It required the power to retain the It does not require power to retain the
data in primary memory. data in secondary memory.

Examples of primary memory are Examples of secondary memory are CD,

RAM, ROM, Registers, EPROM, PROM DVD, HDD, magnetic tapes, flash disks,
and cache memory. pen drive, etc.
 Department of Electronics Engineering
TE-Sem 5-COA

Memory Interleaving

It is a technique for compensating the relatively slow speed of DRAM(Dynamic

RAM). In this technique, the main memory is divided into memory banks which can
be accessed individually without any dependency on the other.

Memory interleaving is a technique for increasing memory access speed. It is a

process that makes the system more efficient, fast and reliable.

Memory Interleaving is an abstraction technique which divides memory into a

number of modules such that successive words in the address space are placed in
the different module.

An interleaved memory with n banks is said to be n-way interleaved

CPU CPU

Cache Cache
Memory Memory

Main Memory Bank 3 Bank 2 Bank 1 Bank 0

 Department of Electronics Engineering
TE-Sem 5-COA

Types of interleaved memory

• High order interleaving

• Low order interleaving

In high order memory interleaving, most significant bits of the memory address
decides, memory banks where a particular location resides. But, in low order
interleaving least significant bits of the memory address decides the memory
banks.

One major difference between high order and low order interleaving is,
consecutive memory location is found in the same memory module in high order
interleaving. But in low order interleaving consecutive memory location is found in
consecutive banks.

• High order interleaving

• Low order interleaving

 Department of Electronics Engineering
TE-Sem 5-COA

Memory Hierarchy

In computer architecture, the memory hierarchy separates computer storage into

a hierarchy based on response time. Since response time, complexity, and capacity
are related, the levels may also be distinguished by their performance and
controlling technologies.

• Processor registers – the fastest possible access (usually 1 CPU cycle).

• Cache Level 0 (L0) Micro operations cache – 6 KB in size

Level 1 (L1) Instruction cache – 128 KB in size

Level 1 (L1) Data cache – 128 KB in size

Level 2 (L2) Instruction and data (shared) – 1 MB in size.

Level 3 (L3) Shared cache – 6 MB in size.

Level 4 (L4) Shared cache – 128 MB in size.

• Main Memory (Primary Storage) – GB in size.

• Disk Storage (Secondary Storage) – TB in size.

• Remote Storage
 Department of Electronics Engineering
TE-Sem 5-COA

Cache Memory Concepts

Cache Memory is a special very high-speed memory. It is used to speed up and

synchronizing with high-speed CPU. Cache memory is costlier than main memory
or disk memory but economical than CPU registers. Cache memory is an
extremely fast memory type that acts as a buffer between RAM and the CPU. It
holds frequently requested data and instructions so that they are immediately
available to the CPU when needed.
Cache memory is used to reduce the average time to access data from the Main
memory. The cache is a smaller and faster memory which stores copies of the
data from frequently used main memory locations. There are various different
independent caches in a CPU, which store instructions and data.

Levels of memory:
• Level 1 or Register –
It is a type of memory in which data is stored and accepted that are
immediately stored in CPU. Most commonly used register is
accumulator, Program counter, address register etc.
• Level 2 or Cache memory –
It is the fastest memory which has faster access time where data is
temporarily stored for faster access.
 Department of Electronics Engineering
TE-Sem 5-COA

• Level 3 or Main Memory –

It is memory on which computer works currently. It is small in size and
once power is off data no longer stays in this memory.
• Level 4 or Secondary Memory –
It is external memory which is not as fast as main memory but data stays
permanently in this memory.
Cache Performance:
When the processor needs to read or write a location in main memory, it first
checks for a corresponding entry in the cache.
• If the processor finds that the memory location is in the cache, a cache
hit has occurred and data is read from cache
• If the processor does not find the memory location in the cache, a cache
miss has occurred. For a cache miss, the cache allocates a new entry and
copies in data from main memory, then the request is fulfilled from the
contents of the cache.
The performance of cache memory is frequently measured in terms of a quantity
called Hit ratio.
Hit ratio = hit / (hit + miss) = no. of hits/total accesses

We can improve Cache performance using higher cache block size, higher
associativity, reduce miss rate, reduce miss penalty, and reduce the time to hit in
the cache.

Locality of Reference : It refers to a phenomenon in which a computer program

tends to access same set of memory locations for a particular time period. In other
words, Locality of Reference refers to the tendency of the computer program to
 Department of Electronics Engineering
TE-Sem 5-COA

access instructions whose addresses are near one another. The property of
locality of reference is mainly shown by loops and subroutine calls in a program.

Temporal Locality of Reference:

Temporal locality means current data or instruction that is being fetched may be
needed soon. So we should store that data or instruction in the cache memory so
that we can avoid repeated searching in main memory for the same data.

Spatial Locality of Reference:

Spatial locality means instruction or data near to the current memory location
that is being fetched, may be needed soon in the near future. This is slightly
different from the temporal locality. Here we are talking about nearly located
memory locations while in temporal locality we were talking about the memory
location that was being fetched repeatedly.

Cache Mapping

There are three different types of mapping used for the purpose of cache memory
which are as follows: Direct mapping, Associative mapping, and Set-Associative
mapping. These are explained below.

1. Direct Mapping
The simplest technique, known as direct mapping, maps each block of
main memory into only one possible cache line. or
In Direct mapping, assign each memory block to a specific line in the
cache. If a line is previously taken up by a memory block when a new block
needs to be loaded, the old block is trashed. An address space is split into
two parts index field and a tag field. The cache is used to store the tag
 Department of Electronics Engineering
TE-Sem 5-COA

field whereas the rest is stored in the main memory. Direct mapping`s
performance is directly proportional to the Hit ratio.
i = j modulo m

where

i=cache line number

j= main memory block number

m=number of lines in the cache

For purposes of cache access, each main memory address can be viewed
as consisting of three fields. The least significant w bits identify a unique
word or byte within a block of main memory. In most contemporary
machines, the address is at the byte level. The remaining s bits specify
one of the 2s blocks of main memory. The cache logic interprets these s
bits as a tag of s-r bits (most significant portion) and a line field of r bits.
This latter field identifies one of the m=2r lines of the cache.
 Department of Electronics Engineering
TE-Sem 5-COA

2. Associative Mapping
In this type of mapping, the associative memory is used to store content
and addresses of the memory word. Any block can go into any line of the
cache. This means that the word id bits are used to identify which word
in the block is needed, but the tag becomes all of the remaining bits. This
enables the placement of any word at any place in the cache memory. It
is considered to be the fastest and the most flexible mapping form.
 Department of Electronics Engineering
TE-Sem 5-COA

3. Set-associative Mapping –
This form of mapping is an enhanced form of direct mapping where the
drawbacks of direct mapping are removed. Set associative addresses the
problem of possible thrashing in the direct mapping method. It does this
by saying that instead of having exactly one line that a block can map to
in the cache, we will group a few lines together creating a set. Then a
block in memory can map to any one of the lines of a specific set..Set-
associative mapping allows that each word that is present in the cache
can have two or more words in the main memory for the same index
address. Set associative cache mapping combines the best of direct and
associative cache mapping techniques.
In this case, the cache consists of a number of sets, each of which
consists of a number of lines. The relationships are

m=v*k

i= j mod v

where

i=cache set number

j=main memory block number

v=number of sets

m=number of lines in the cache number of sets

k=number of lines in each set

 Department of Electronics Engineering
TE-Sem 5-COA

Application of Cache Memory –

Usually, the cache memory can store a reasonable number of blocks at any given
time, but this number is small compared to the total number of blocks in the main
memory.
The correspondence between the main memory blocks and those in the cache is
specified by a mapping function.
Types of Cache
Primary Cache
A primary cache is always located on the processor chip. This cache is small and
its access time is comparable to that of processor registers.
 Department of Electronics Engineering
TE-Sem 5-COA

Secondary Cache
Secondary cache is placed between the primary cache and the rest of the
memory. It is referred to as the level 2 (L2) cache. Often, the Level 2 cache is also
housed on the processor chip.
Cache Write Policies

A cache’s write policy is the behaviour of a cache while performing a write

operation. A cache’s write policy plays a central part in all the variety of different
characteristics expressed by the cache. Let’s now take a look at three policies:

• Write-through

• Write-around

• Write-back

Write-through

Suppose we design our cache to ensure consistency first. That is, we’d want to
update our backing store synchronously before sending the response back to the
client, we use write through policy.

In case the requested entry is not found in the cache, we create an entry in cache
storage first.

This is the easiest policy to implement

 Department of Electronics Engineering
TE-Sem 5-COA

Write-around

Now, write-through provides the best outcome in case we expect written data to
be accessed soon. Depending on our cache usage pattern, this might not be true.

If we do not expect a read operation shortly after, the cache would become
polluted with the entries we’re not using. To avoid cache pollution, we may bypass
cache entry allocation in case of a cache miss.
 Department of Electronics Engineering
TE-Sem 5-COA

Write-back

While write-through provides us the best consistency, it does not help us with write
operation latency – the cache returns a response to the client only after the backing
storage is updated.

We may take advantage of our fast cache storage to streamline this as well. To do
this, we would have to return the response before updating the backing storage. In
this case, the backing storage update happens asynchronously in a separate
sequence.

We can kick off such a sequence in several ways – right before the response return,
periodically, or integrated into cache eviction based on cache entry dirty state. For
CPU caches, we use a dirty bit as a state indicator.
 Department of Electronics Engineering
TE-Sem 5-COA

The asynchronous update brings us better responsiveness as well as the chance to

improve throughput.

Write-back having more difficult implementation, it’s possible to encounter

consistency issues. Having cache in volatile memory, power outage before write-
back is complete would result in data loss.

Cache Coherency

In a multiprocessor system, data inconsistency may occur among adjacent levels or

within the same level of the memory hierarchy.

In a shared memory system, multiple processors with a separate cache memory for
each processor, it is possible to have many copies of any one instruction operand:
one copy in the main memory and one in each cache memory. When one copy of
an operand is changed, the other copies of the operand must be changed also.
 Department of Electronics Engineering
TE-Sem 5-COA

Example :

Cache and the main memory may have inconsistent copies of the same object.

Suppose there are three processors, each having cache. Consider the following
scenario:-

• Processor 1 read X : obtains 24 from the memory and caches it.

• Processor 2 read X : obtains 24 from memory and caches it.

• Again, processor 1 writes as X : 64, Its locally cached copy is updated. Now,
processor 3 reads X, what value should it get?

• Memory and processor 2 thinks it is 24 and processor 1 thinks it is 64.

As multiple processors operate in parallel, and independently multiple caches may

possess different copies of the same memory block, this creates a cache coherence
problem.

Cache coherence is the discipline that ensures that changes in the values of shared
operands are propagated throughout the system in a timely fashion.
 Department of Electronics Engineering
TE-Sem 5-COA

There are various Cache Coherence Protocols in multiprocessor system.

MESI Protocol:

• The MESI protocol is a method of insuring cache coherence in

a multiprocessor system.
• With shared memory and more than one processor, it is vital to ensure that
data in a processor's cache is an accurate reflection of main memory.
• These are the extra bits stored with each cache line in order to track its
modification status within the shared memory system.

• Modified - Dirty Bit, data needs to be written to main memory

• Exclusive - Only this cache has a copy and it is unmodified

• Shared - two or more caches contain this data

• Invalid - Data is invalid

 Department of Electronics Engineering
TE-Sem 5-COA

Virtual Memory Management-Concept

Virtual Memory is a storage allocation scheme in which secondary memory can

be addressed as though it were part of the main memory. The addresses a
program may use to reference memory are distinguished from the addresses the
memory system uses to identify physical storage sites, and program-generated
addresses are translated automatically to the corresponding machine addresses.

The size of virtual storage is limited by the addressing scheme of the computer
system and the amount of secondary memory is available not by the actual
number of the main storage locations.

It is a technique that is implemented using both hardware and software. It maps

memory addresses used by a program, called virtual addresses, into physical
addresses in computer memory.

1. All memory references within a process are logical addresses that are
dynamically translated into physical addresses at run time. This means
that a process can be swapped in and out of the main memory such that
it occupies different places in the main memory at different times during
the course of execution.
2. A process may be broken into a number of pieces and these pieces need
not be continuously located in the main memory during execution. The
combination of dynamic run-time address translation and use of page or
segment table permits this.
If these characteristics are present then, it is not necessary that all the pages or
segments are present in the main memory during execution. This means that the
required pages need to be loaded into memory whenever required.
 Department of Electronics Engineering
TE-Sem 5-COA

Memory Management

Memory segmentation is an OS memory management technique of division of

a computer's primary memory into partitions or sections. In a computer
system using segmentation, a reference to a memory location includes a value that
identifies a segment and an offset (memory location) within that segment.

Segments usually correspond to natural divisions of a program such as individual

routines or data tables
 Department of Electronics Engineering
TE-Sem 5-COA

Segmentation was originally invented as a method by which system software could

isolate different software processes (tasks) and data they are using. It was intended
to increase reliability of the systems running multiple processes simultaneously

In a system using segmentation, computer memory addresses consist of a segment

id and an offset within the segment.

A memory management unit (MMU) is responsible for translating the segment and
offset into a physical address, and for performing checks to make sure the
translation can be done and that the reference to that segment and offset is
permitted.
 Department of Electronics Engineering
TE-Sem 5-COA

Advantages of Segmentation

• No internal fragmentation

• Average Segment Size is larger than the actual page size.

• Less overhead

• It is easier to relocate segments than entire address space.

• The segment table is of lesser size as compare to the page table in paging.

Disadvantages of Segmentation

• It can have external fragmentation.

• It is difficult to allocate contiguous memory to variable sized partitions.

• Costly memory management algorithms.

 Department of Electronics Engineering
TE-Sem 5-COA

Paging

Memory Allocation: Memory allocation is a process by which computer programs

and services are assigned with physical or virtual memory space. The memory
allocation is done either before or at the time of program execution. There are
two types of memory allocations:
1. Compile-time or Static Memory Allocation
2. Run-time or Dynamic Memory Allocation
Static Memory Allocation: Static Memory is allocated for declared variables by
the compiler. The address can be found using the address of operator and can be
assigned to a pointer. The memory is allocated during compile time.
Dynamic Memory Allocation: Memory allocation done at the time of
execution(run time) is known as dynamic memory allocation. Functions calloc()
and malloc() support allocating dynamic memory. In the Dynamic allocation of
memory space is allocated by using these functions when the value is returned by
functions and assigned to pointer variables.
 Department of Electronics Engineering
TE-Sem 5-COA

Difference Between Static and Dynamic Memory Allocation

[Link] Static Memory Allocation Dynamic Memory Allocation

In the static memory allocation,

variables get allocated
1 permanently, till the program In the Dynamic memory allocation,
executes or function call variables get allocated only if your
finishes. program unit gets active.

Static Memory Allocation is

2 done before program Dynamic Memory Allocation is done
execution. during program execution.

It uses stack for managing the It uses heap for managing the
3
static allocation of memory dynamic allocation of memory

4 It is less efficient It is more efficient

In Static Memory Allocation,

5 In Dynamic Memory Allocation,
there is no memory re-usability
there is memory re-usability and
 Department of Electronics Engineering
TE-Sem 5-COA

memory can be freed when not

required

In static memory allocation,

once the memory is allocated, In dynamic memory allocation, when
6
the memory size can not memory is allocated the memory
change. size can be changed.

This allows reusing the memory. The

user can allocate more memory
7 In this memory allocation when required. Also, the user can
scheme, we cannot reuse the release the memory when the user
unused memory. needs it.

In this memory allocation

scheme, execution is faster In this memory allocation scheme,
8
than dynamic memory execution is slower than static
allocation. memory allocation.

In this memory is allocated at In this memory is allocated at run

9
compile time. time.
 Department of Electronics Engineering
TE-Sem 5-COA

In this allocated memory In this allocated memory can be

10 remains from start to end of released at any time during the
the program. program.

Example: This static memory Example: This dynamic memory

11 allocation is generally used allocation is generally used for linked
for array. list.

Difference between Contiguous and Non-contiguous Memory Allocation

Non-Contiguous Memory
[Link]. Contiguous Memory Allocation Allocation

Contiguous memory allocation Non-Contiguous memory

allocates consecutive blocks of allocation allocates separate blocks
1. memory to a file/process. of memory to a file/process.

2. Faster in Execution. Slower in Execution.

3. It is easier for the OS to control. It is difficult for the OS to control.

Overhead is minimum as not More Overheads are there as there

4. much address translations are are more address translations.
 Department of Electronics Engineering
TE-Sem 5-COA

Non-Contiguous Memory
[Link]. Contiguous Memory Allocation Allocation

there while executing a

process.

Both Internal fragmentation

and external fragmentation External fragmentation occurs in
occurs in Contiguous memory Non-Contiguous memory
5. allocation method. allocation method.

It includes single partition

allocation and multi-partition It includes paging and
6. allocation. segmentation.

7. Wastage of memory is there. No memory wastage is there.

In contiguous memory In non-contiguous memory

allocation, swapped-in allocation, swapped-in processes
processes are arranged in the can be arranged in any place in the
8. originally allocated space. memory.

Why Paging ?

• In segmented memory the maximum size of a segment can be 4 GB swapping

in and out of 4GB to and from physical memory requires too long time
 Department of Electronics Engineering
TE-Sem 5-COA

• So paging mechanism was developed which divides the segments further

into pages of 4KB

• Swapping 4KB pages is faster

• With paging degree of multiprogramming will increase

• More number of processes can be in the ready state for execution

• With fixed size pages memory allocation process is faster

How Paging Mechanism Works

• 4GB of main memory is divided into 1M pages of 4KB each

• The starting addresses of these 1M pages are kept in two-level tables

• First level table, known as Page Directory, contains 1K entries for the second
level table, known as Page Table

• Each Page Table contains the starting addresses of 1K pages

• There is only one Page Directory in the system

• The paging unit is controlled by the contents of the microprocessor’s CR

• 80386 has 4 control registers CR0 through CR3

• Starting address of Page Directory is in CR3

 Department of Electronics Engineering
TE-Sem 5-COA

Cache Coherency

In a multiprocessor system, data inconsistency may occur among adjacent levels or

within the same level of the memory hierarchy.

In a shared memory system, multiple processors with a separate cache memory for
each processor, it is possible to have many copies of any one instruction operand:
one copy in the main memory and one in each cache memory. When one copy of
an operand is changed, the other copies of the operand must also be changed.

Example:
Cache and the main memory may have inconsistent copies of the same object.

Suppose there are three processors, each having cache. Consider the following
scenario:-

• Processor 1 read X : obtains 24 from the memory and caches it.

• Processor 2 read X : obtains 24 from the memory and caches it.

• Now, Processor 1 writes X : 64, Its locally cached copy is updated.

• Now, Processor 3 reads X, what value should it get?

 Department of Electronics Engineering
TE-Sem 5-COA

• Memory and processor 2 thinks it is 24 and processor 1 thinks it is 64.

As multiple processors operate in parallel, and independently multiple caches may

possess different copies of the same memory block, this creates a cache coherence
problem.

Cache coherence is the discipline that ensures that changes in the values of shared
operands are propagated throughout the system in a timely fashion.

There are various Cache Coherence Protocols in multiprocessor system.

MESI Protocol:

• The MESI protocol is a method of insuring cache coherence in

a multiprocessor system.

• With shared memory and more than one processor, it is vital to ensure
that data in a processor's cache is an accurate reflection of main
memory.

• These are the extra bits stored with each cache line in order to track
its modification status within the shared memory system.

• Modified - Dirty Bit, data needs to be written to main memory

• Exclusive - Only this cache has a copy and it is unmodified
• Shared - two or more caches contain this data
• Invalid - Data is invalid
 Department of Electronics Engineering
TE-Sem 5-COA

Page Table Entry

Present
Frame (1)/ Protection Reference Caching
Dirty
No Absent (R/W/X) (0/1) (Enable/Disable)
(0)

• Frame No -> The frame in which the specific page is present

• Present/ Absent -> The page is present in the frame or not

• Protection -> Read/Write/Execute

• Reference -> Whether the page is previously accessed or not

 Department of Electronics Engineering
TE-Sem 5-COA

• Caching -> Enabled/ Disabled for future access

• Dirty -> Whether the said page is modified or not

Translation Lookaside Buffer(TLB)

• The processor stores the most recently used page table entries in on-chip
cache called translation lookaside buffer or TLB.

• Most of the microprocessors has separate TLB's for the data and instruction
caches.

• Most paging is performed using the contents of the TLBs.

• Bus cycles to the page tables in memory are performed only when the TLBs
do not contain the translation information for a requested page

Paging & Segmentation

Paging Segmentation

Segmentation is closer to the user

Paging is closer to operating system
rather than the operating system.

In this, the information about

In this, the page information is stored
segments is stored in the segment
in the page table.
table.

In this, operating system is responsible In this, the compiler is responsible for

for working the working.
 Department of Electronics Engineering
TE-Sem 5-COA

Paging does not suffer from Segmentation suffers from external

fragmentation fragmentation

Paging divides our program into Segmentation divides our program into
various fixed size pages. various variable size segments.

In this, the logical address is divided In this, the logical address is divided
into two things: page number and page into two things: segment number and
offset segment offset

Paging is faster than segmentation Segmentation is slower than paging

It is a non-contiguous memory It is a non-contiguous memory

allocation allocation

The entry of the page table contains On the other hand, the entry of
frame number and flag bits so that it segment table contains base address,
can represent the details about the some protection bits of the segments
pages and segment offset

Page Replacement policies

In an operating system that uses paging for memory management, a page

replacement algorithm is needed to decide which page needs to be replaced when
new page comes in.
 Department of Electronics Engineering
TE-Sem 5-COA

Page Fault – A page fault happens when a running program accesses a memory
page that is mapped into the virtual address space, but not loaded in physical
memory.

Since actual physical memory is much smaller than virtual memory, page faults
happen. In case of page fault, Operating System might have to replace one of the
existing pages with the newly needed page. Different page replacement algorithms
suggest different ways to decide which page to replace. The target for all algorithms
is to reduce the number of page faults.

First In First Out (FIFO) :

This is the simplest page replacement algorithm. In this algorithm, the operating
system keeps track of all pages in the memory in a queue, the oldest page is in the
front of the queue. When a page needs to be replaced, page in the front of the
queue is selected for removal.

Example : Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3 page frames. Find

number of page faults.
 Department of Electronics Engineering
TE-Sem 5-COA

• Initially all slots are empty, so when 1, 3, 0 came they are allocated to the
empty slots —> 3 Page Faults.

• When 3 comes, it is already in memory so —> 0 Page Faults (Hit).

• Then 5 comes, it is not available in memory so it replaces the oldest page

slot i.e 1. —>1 Page Fault.

• When 6 comes, it is also not available in memory so it replaces the oldest

page slot i.e 3 —>1 Page Fault.

• Finally when 3 come it is not available so it replaces 0

—> 1 page fault

Belady’s Anomaly– Belady’s anomaly proves that it is possible to have more page
faults when increasing the number of page frames while using the First in First Out
(FIFO) page replacement algorithm. For example, if we consider reference string
3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4 and 3 frames, we get 9 total page faults, but if we
increase frames to 4, we get 10 page faults.

Optimal Page replacement :

In this algorithm, pages are replaced which would not be used for the longest
duration of time in the future.

Example : Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4

page frame. Find number of page faults.
 Department of Electronics Engineering
TE-Sem 5-COA

• Initially all slots are empty, so when 7 0 1 2 are allocated to the empty slots
—> 4 Page faults.

• 0 is already there so —> 0 Page fault (Hit).

• When 3 came it will take the place of 7 because it is not used for the
longest duration of time in the future.—>1 Page fault.

• 0 is already there so —> 0 Page fault (Hit).

• 4 will take place of 1 —> 1 Page Fault.

• Now for the further page reference string —> 0 Page fault (Hit) because
they are already available in the memory.

Optimal page replacement is perfect, but not possible in practice as the operating
system cannot know future requests. The use of Optimal Page replacement is to
set up a benchmark so that other replacement algorithms can be analysed against
it.
 Department of Electronics Engineering
TE-Sem 5-COA

Least Recently Used :

In this algorithm page will be replaced which is least recently used.

Example : Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3

with 4 page frames. Find number of page faults.

• Initially all slots are empty, so when 7 0 1 2 are allocated to the empty slots
—> 4 Page faults.

• 0 is already their so —> 0 Page fault (Hit).

• When 3 came it will take the place of 7 because it is least recently used
—>1 Page fault.

• 0 is already in memory so —> 0 Page fault (Hit).

• 4 will takes place of 1 —> 1 Page Fault.

• Now for the further page reference string —> 0 Page fault (Hit) because
they are already available in the memory.
 Department of Electronics Engineering
TE-Sem 5-COA

LIFO Page Replacement :

• As the name suggests, this algorithm works on the principle of “Last in First
out“.

• It replaces the newest page that arrived at last in the main memory.

• It is implemented by keeping track of all the pages in a stack.

Random Page Replacement :

• As the name suggests, this algorithm randomly replaces any page.

• So, this algorithm may behave like any other algorithm like FIFO, LIFO, LRU,
Optimal etc.