Unit-IV

COMPUTER ARITHMETIC
MEMORY ORGANIZATION
COMPUTER ARITHMETIC: Addition and
Subtraction, Multiplication Algorithms,
Division Algorithms ,Floating-point Arithmetic
[Link].1-10.5
MEMORY ORGANIZATION: Memory Hierarchy,
Main Memory, Auxiliary memory, Associative
Memory, Cache Memory, Virtual Memory.
Ch:12.1-12.6
 Fixed Point Representation
• All positive numbers including zero can be
represented as unsigned numbers.
• Ex: 4,5,6,7,89
• But to represent negative numbers it is
customary to designate sign with a bit placed
in left most position of a number.
• -23,-45
• In binary,Convention; 0 +ve 1 -ve
• In addition to a sign, a number may have a
binary point. 10.111 10111. .10111
• The position of the binary point is needed to
represent fractions , integers or mixed integer
fraction numbers.
• Two ways to specify the position of a binary
point in a register
– by giving a fixed position
– by employing a floating point representation
 Fixed Point Method

• Assume that the binary point is always fixed in

one position
• Two positions most widely used:
– A binary point in the extreme left of the register to
make the fraction
– A binary point in the extreme right of the register
to make the fraction
• In either case binary point is not actually
present but it’s presence is assumed from the
fact that the number stored in the register is
treated as a fraction or as an integer.
• Floating point representation uses a second
register to represent a number that designate
the position of the decimal point in the first
register.
 Integer representation
Sign: most significant bit
Remaining number represented in one of the
following three ways:
1) signed magnitude form
2) signed one’s complement form
3) signed two’s complement form
• 14- use 8 bits to represent the number
- 0000 1110
But to represent ( -14)
1)signed magnitude form: 1000 1110
(used only for ordinary arithmetic)
2)signed one’s complement form : 1111 0001
(take one’scomplement of positive number including sign bit)
3)signed two’s complement form : 1111 0010
( take two’s complement of positive number including sign
bit)
 Floating point representation
• Two parts
– represents a signed fixed point number called mantissa
– Designates the position of binary point called exponent
Fixed point mantissa can be a fraction or an integer .
+6132.789 -
fraction(m) exponent(e)
+0.6132789 +04 =m x( r**e)
1001.11 - .1001110 x (2**(+4) )
.
 Sign-Magnitude

used in every day arithmetic calculations .

Left most bit is sign bit- 0 – positive 1 –
negative
• +18 = 00010010
• -18 = 10010010
—Two representations of zero (+0 and -0)

10
 Addition and Subtraction

• Normal binary addition

• Monitor sign bit for overflow
• So we only need addition and complement
Circuits
Assume:-
-magnitudes of two numbers as A and B.
when those sign numbers are added we have eight
different conditions depending on the sign bits
and operations performed.
11
 SIGNED MAGNITUDE ADDITION AND
SUBTRACTION
• Addition: A + B ; A: Augend; B: Addend
• Subtraction: A - B: A: Minuend; B:
Subtrahend

12
 Case 1: addition

• If signs are same:

• 3+5 both numbers positive
• (-3) + ( -5) both numbers negative -(3+5)
• If signs differ:
• (+3) + ( -5) numbers differ in sign so, 3-5 (results
in subtraction operation ) A>B sign of A
• (-3) + (+5) different in signs so, -(3-5) A<B
complement sign of A
• (results in subtraction operation )
13
 Case 2: Subtraction

• If signs are same:

• 5-3 both numbers positive: A>B sign of A
• (-3) - ( -5) both numbers negative -(3-5): A<B
complement sign of A
• If signs differ:
• (+3) - ( -5) numbers differ in sign so, 3+5 (results
in addition operation ) Result sign of A
• (-3) -(+5) different in signs so, -(3+5)
• (results in addition operation )
14
15
Hardware Implementation for signed magnitude Addition and Subtraction

16
17
 ALGORITHM
o The two signs As and Bs are compared by EX-OR them. If result is 0
then As = Bs and if result is 1 the As ≠ Bs.
o For add operations if have same sign bits the magnitude must be
added. For subtract operations different sign bits means
magnitudes be added as well.
o E bit is carry bit after addition and moves to AVE overflow bit only at
this state.
o If sign bits are different in add operations or the same in subtract
operations the two magnitudes will be subtracted A – B. No
overflow can occur here.
o if E=1 this means A>B and if E=0 then A<B. then here it is necessary
to get 2’s complement of A (by invert A then add 1) and sign of A is
inverted only in this case.
18
 SIGNED 2’S COMPLEMENT
ADDITION AND SUBTRACTION

20
 Signed 2’s complement

The left most bit in 2’s complement represented binary number is the
sign bit. If 0 the number is positive and if 1 then number is negative.
If sign bit is 1 the entire number is represented in 2’s complement.
The addition of two numbers represented in 2’s complement is carried
out by normal binary addition with carry discarded.
The subtraction is carried out by taking 2’s complement (B) of
subtrahend and adding it to minuend (A).
Overflow can be detected by inspecting last 2 carries out of addition by
EX-OR them. If different then overflow is detected.
For addition simply implement add then see overflow. For subtract add
2’s complement of B to A and watch overflow since the A and –B
could be of same sign.
21
22
23
24
25
• Qn, designates the least significant bit of the
multiplier in register QR
• An+1 extra flip-flop, Qn+1 is appended to QR to
facilitate a double bit inspection of the
multiplier
• AC and the appended bit Qn+1 are initially
cleared to 0
• the sequence counter SC is set to a number n
equal to the number of bits in the multiplier
26
27
28
BOOTH MULTIPLICATION ALGORITHM FOR
SIGNED 2’S COMPLEMENT

Booth's multiplication algorithm is a

multiplication algorithm that multiplies two
signed binary numbers in
two's complement notation

29
• Booth's algorithm examines adjacent pairs of bits of the N-bit
multiplier Y in signed two's complement representation,
including an implicit bit below the least significant bit, y-1 = 0.
• For each bit yi, for i running from 0 to N-1, the bits yi and yi-
1 are considered.

• Where these two bits are equal, the product

accumulator P is left unchanged.
• Where yi = 0 and yi-1 = 1, the multiplicand times 2i is added
to P; and where yi = 1 and yi-1 = 0, the multiplicand times 2i is
subtracted from P.
• The final value of P is the signed product.
30
• The multiplicand and product are not specified; typically,
these are both also in two's complement representation,
like the multiplier, but any number system that supports
addition and subtraction will work as well.
• the order of the steps is not determined. Typically, it
proceeds from LSB to MSB, starting at i = 0; the
multiplication by 2i is then typically replaced by
incremental shifting of the P accumulator to the right
between steps; low bits can be shifted out, and
subsequent additions and subtractions can then be done
just on the highest N bits of P.[1]
31
• The algorithm is often described as converting
strings of 1's in the multiplier to a high-order
+1 and a low-order –1 at the ends of the
string. When a string runs through the MSB,
there is no high-order +1, and the net effect is
interpretation as a negative of the appropriate
value.

32
• Booth's algorithm can be implemented by
repeatedly adding (with ordinary unsigned
binary addition) one of two predetermined
values A and S to a product P, then performing
a rightwardarithmetic shift on P.
Let m and r be the multiplicand and multiplier,
respectively; and let x and y represent the
number of bits in m and r.

33
Gives procedure for multiplying binary integers in signed
2’s complement representation.
It operates in fact that string of 0’s in multiplier requires no
addition but only shifting. And strings of 1’s in multiplier
needs addition by strings
As with all multiplication schemes. Booth algorithm
requires testing of multiplier bits and shifting of partial
products. Before shifting, the multiplicand may be added
to partial product, subtracted from partial product, or
left unchanged.
o
34
Multiplicand is subtracted from partial product when first
least significant 1 of string of 1’s in multiplier is
encountered. (10)
o Multiplicand is added to partial product when
encountering first 0 and if there were a previous 1 in a
string of 0’s in multiplier. (01)
o The partial product does not change when multiplier bits
are identical. (00 or 11)

The algorithm works for positive or negative multipliers in

2’s complement representation.
35
BOOTH MULTIPLICATION ALGORITHM FOR
SIGNED 2’S COMPLEMENT

36
37
38
EXAMPLE OF BOOTH MULTIPLIER
-9x-13=117

39
40
MEMORY MANAGEMENT

prepared by Dr PVSL 41
 Memory Hierarchy

The memory unit that communicates with directly with CPU

is called main memory.
Not enough storage space.

programs and data currently needed are stored here

Devices that provide backup storage are called auxiliary
memory.
Most common are magnetic disks and tape drives.
Used to store system programs, large data files, backup
data
prepared by Dr PVSL 42
Total memory capacity of a computer can be visualized as a hierarchy
of components.
o starting from slow but high capacity , then to relatively faster and less
capacitive main memory , next to 3- smaller and fast cache memory.
o At bottom of hierarchy ,slow magnetic tapes(removable files)
o at middle ,magnetic disks (backup storage)
o then main memory which can communicate with CPU and auxiliary
memories.
o At top of pyramid resides the cache memory, Used to increase speed
of processing and to compensate the speed difference between
CPU and main memory.

prepared by Dr PVSL 43
MEMORY HIERARCHY

prepared by Dr PVSL 44
Usually in cache, segments of programs and
data frequently accessed are stored to benefit
from high speed access by CPU not found in
main memory.
Balance performance with cost
Small memories are fast but expensive
Large memories are slow but cheap

prepared by Dr PVSL 45
prepared by Dr PVSL 46
prepared by Dr PVSL 47
 Main Memory

-central storage unit in computers .

-Fast and relatively large type of memory
- used to store programs and data used in program execution
RAM: integrated circuit chips (Static or Dynamic)
o SRAM consists of flip flops as storage media.
Stored data remains valid as long as power is applied to the unit
o DRAM stores data as form of electric charges in small capacitors.
Capacitors are provided by CMOS transistors.
Needs refreshing periodically as charges on small capacitor discharge
soon (need electronic control unit for that).
DRAM compared to SRAM offer reduced power consumption and larger
capacity.
But SRAM are faster.

prepared by Dr PVSL 48
ROM:
- different type of main memory.
-Used to store programs and data that
does not change at all (programs,
tables, etc.)
o Used for storing bootstrap loaders (start
loading operating systems).
o used to start up any computer.

prepared by Dr PVSL 49
ROM and RAM are available in different sizes.
We have to combine many chips to increase size.
RAM chip has 2 chip enables CS1, CS2#. Those
called chip select controls and they enable the
chip to function if selected.

prepared by Dr PVSL 50
 128 words of 8 bits per word RAM chip
7 address bits and 8 bidirectional data bits

prepared by Dr PVSL 51
prepared by Dr PVSL 52
• ROM chips are constructed the same way.
• It has address bits, one direction data bits, CS
control pin.
• Internal binary cells of ROM occupy much less
space than RAM.

prepared by Dr PVSL 53
prepared by Dr PVSL 54
 Memory Address Map and Connection to
CPU
Designer must decide the memory size, RAM
size, ROM size.
Then interconnection between memory and
processor is established
Memory Address Map is “address space
assignment to each memory chip”.
This is a pictorial representation of assigned
address space for each chip in the system.

prepared by Dr PVSL 55
• Assume computer system with 512 bytes of
RAM and 512 bytes of ROM as shown in next
figure.
• The memory address map is shown in next
table.

prepared by Dr PVSL 56
prepared by Dr PVSL 57
o RAM chips are 128 words each so they need 7 address lines.
o ROM chips are 512 words each so they need 9 address lines.
o For RAM selection A10 is always 0 whereas for ROM selection A10 is always
1.
o Memory chips are connected to CPU through address and data busses.
RAM chips stores 128 by 4 = 512 bytes. ROM chip stores 512 bytes alone.
o A10 selects ROM chip if it is 1. And it selects all RAM chips if it is 0.
o RD and WR control pins are connected to RD and WR pins in corresponding
ROM and RAM chips to initiate read or write operation from CPU.
o Address range from 0 to 511 is assigned for RAM chips while address range
from 512 to 1023 is assigned to ROM chip.

prepared by Dr PVSL 59
Auxiliary memory
Magnetic disk

prepared by Dr PVSL 60
Commonly used secondary memory - magnetic disks and
magnetic tapes.
Other devices (magnetic drums, bubble memory, CD, DVD, flash disks,
etc.)
The important characteristics of those storage devices are
o Access mode
o Access time
o Transfer rate
o Capacity
o Cost.
prepared by Dr PVSL 61
Access time
Average time needed to reach storage location and obtain contents.
Access time = seek time + transfer time
Seek time:
Transfer time: time required to transfer data to-from device.
Secondary storage devices are organized into records (blocks).
Reading or writing is always done with entire record.
Transfer rate
The number of characters or words the device can transfer in one
second.

prepared by Dr PVSL 62
 Magnetic Disk

Circular plate constructed of metal or plastic coated

with magnetized material.
Both sides of disks are used and disks may be stacked
with read-write heads available for each surface.
All disks rotate together at high speed.
Bits are stored in tracks which are concentric circles.
Tracks are divided into sections called sectors .

prepared by Dr PVSL 63
Some disk systems use single read-write head moveable to different
tracks using mechanical assembly
Others use multiple read-write heads positioned on each track
(faster , more expensive).

Addressing used to specify disk number, surface, track number, and

sector within track.
After head positioned at track, must wait to synchronize with sector
Then reading data will start as same speed of rotation

Hard disks are permanently attached to unit and cannot move.

Floppy disks are removable ones. With 2 sizes 5.25 and 3.5 INCHES.
prepared by Dr PVSL 64
• Disks contain platters, each with two surfaces
• Each surface is organized in concentric rings
called tracks.
• Each track consists of sectors separated by
gaps.

prepared by Dr PVSL 65
prepared by Dr PVSL 66
prepared by Dr PVSL 67
Disk Geometry (Multiple-Platter View)
Aligned tracks form a cylinder

prepared by Dr PVSL 68
prepared by Dr PVSL 69
 Magnetic tapes

Strip of plastic coated with magnetic recording material.

Bits are recorded as magnetic spots along several parallel
tracks(7 to 9 tracks to form character with parity).
Read-write heads are positioned on each track.
Magnetic tape units can be started stopped, forward moved, or
reverse moved or rewound.
Data are recorded in records (number of characters) followed by
gaps between record for synchronization.
At start and end of each record there is ID bit patterns.
Records are identified by reading ID bit patterns.
prepared by Dr PVSL 70
prepared by Dr PVSL 71
ASSOCIATIVE MEMORY

prepared by Dr PVSL 72
Accessed by the content of the data rather than by an
address.
Also called Content Addressable Memory (CAM).
When word is written to CAM, no address is needed; next
available unused storage location is located.
When word is read from CAM, the content of word or part of
it is specified, the memory locates all words which give
match and marks them for reading.
Associative memories are expensive and used for application
where time search is critical.
prepared by Dr PVSL 73
HARDWARE ORGANIZATION
 HARDWARE ORANIZATION

• Consists of memory array of m words each of n bits, argument

register A and key register K each of n bits.
• Match register M has m bits, one for each memory word
• Each word of memory is compared in parallel with content of
argument register and set corresponding bit in match register.
• Those bits set in match register indicate their words has
match.
• Key register provides mask to select particular bits in
argument word to be included in match or not.
• 1 means corresponding bit in argument register is in match
and 0 means not.

prepared by Dr PVSL 75
prepared by Dr PVSL 76
CAM memory of m words by n cells per wor
Internal Organization Of Single Cell
 MATCHING LOGIC

The match logic for each word can be derived from comparison
algorithm of two binary numbers.
1. K is neglected
Word i is equal to argument A
if Aj = Fij for j=1 ,2, 3, …,n
xj = Aj Fij + A’j F’ij
for word i to be equal to argument A we must have all xi
variables equal 1.
The Boolean function for that will be
Mi = x1 x2 x3 x4 ……. xn
prepared by Dr PVSL 79
2. K is included
Requirement will be
xi + K’j = xi if Kj=1
=1 if Kj=0
Then match logic will be
Mi = (x1 + K’1) (x2 + K’2) (x3 + K’3) ….. (xn + K’n)

The function now can be expressed in detail as

Mi = Π(Aj Fij + A’jF’ij + K’j) for j=1 to n
prepared by Dr PVSL 80
 READ OPERATION
MATCH LOGIC FOR OMNR WORD OF ASSOCIATIVE MEMORY
Cache Memory
Analysis has shown that references to memory at given interval of time is
confined within few localized areas in memory. (Locality of Reference)

Programs has loops and repeated subroutine calls encountered frequently. So

computer repeatedly refers to set of instructions in memory of the loop

Same applies for subroutine; every time a subroutine is called the

instructions of the subroutine will be executed.

Memory reference of data also tend to be localized . lookup tables data

repeatedly refer to same area in memory.

prepared by Dr PVSL 83
 Cache Memory
The property of Locality of Reference makes the Cache memory
systems work

Cache is a fast small capacity memory that should hold those

information which are most likely to be accessed.

Then the average memory access time can be reduced dramatically

Placed between processor and main memory

Have access time less than main memory access time by a factor of (5
– 10)
prepared by Dr PVSL 84
prepared by Dr PVSL 85
 Cache and memory Access
All the memory accesses are directed first to
Cache.
If the word is in Cache; Access cache to provide it
to CPU.

If the word is not in Cache; bring a block (or a

line) including that word to replace a block now
in Cache.
Block varies between (1 – 16 words)
prepared by Dr PVSL 86
 Cache Memory system Performance
Hit Ratio :
"% of memory accesses satisfied by Cache memory system"
If processor searches for a word in cache and finds it then we call
this state as "hit";
if the word is not found in cache then must it be pulled from main
memory and placed in cache, then we call this state as "miss"
Te = Tc + (1 -h) Tm
Where:
Te: Effective memory access time in Cache memory system
Tc: Cache access time
Tm: Main memory access time
prepared by Dr PVSL 87
Example: Assume a cached processor system
with cache access time of Tc = 0.4 us, and a
memory access time of Tm = 1.2us, and cache
hit ratio of h = 0.85%. Then get the effective
access time?
Answer:
Te = 0.4 + (1 -0.85) * 1.2 = 0.58 us

prepared by Dr PVSL 88
 Different Types of Mappings
• Three types of mapping procedures are of
practical interest when considering the
organization of cache
– 1. Associative Mapping
– 2. Direct Mapping
– 3. Set- Associative Mapping
 Mapping Function: Associative Mapping
Any block location in Cache can store any block in memory
Most flexible

Mapping Table is implemented in an associative memory

Fast, very Expensive

Mapping Table
Stores both address and the content of the memory word.

Cache controller search for the existence of the address part.

If found then content is accessed;
otherwise the main memory is accessed and the address-data pair is
placed in next available place in cache.

prepared by Dr PVSL 90
If cache is full then a decision must be taken to
which line in cache to be replaced by the new
content (need a replacement algorithm).

prepared by Dr PVSL 91
prepared by Dr PVSL 92
 Mapping Function: Direct Mapping

Associative memories are expensive compared to RAMs

Each memory block has only one place to load in Cache

Mapping Table is made of RAM instead of CAM

n-bit memory address consists of 2 parts;

( k ) bits of Index field
( n-k ) bits of Tag field

n-bit addresses are used to access main memory and k-bit Index is used to access
the Cache.
Tag part of the address is stored with the data in cache line that it represent.
prepared by Dr PVSL 93
addessing relationship between main and
cache memories

prepared by Dr PVSL 94
Direct mapping cache organisation

prepared by Dr PVSL 95
Note that location 00000 will be placed in cache in
location 000. And its content 1220 will be placed in
cache at that address
Note that content of 02777 which is 6710 will be placed in
address 777 in cache.

Note that the next main memory addresses 00000, 01000,

and 02000 when referenced will occupy the same cache
line address of 000. But they have different TAG parts.

prepared by Dr PVSL 96
 Operation of Direct mapped caches

address is generated from CPU with 2 parts INDEX and TAG

cache is accessed using INDEX; the required word is
accessed and TAG if compared with cache TAG
IF matches then it is a "Hit"
o Data is pulled from this line to processor
If not a match then it is a "Miss"
o The required address content is read into cache. It may
replace an old content with the same INDEX but not the
TAG
o A copy is presented to the processor
prepared by Dr PVSL 97
 Example

Next figure shows a direct mapping with block

size = 8 bytes
Each line in cache stores TAG and DATA
Data will be content of 8 bytes addressed
sequentially in main memory
We have 64 cache lines
TAG stored with data ion cache line is the
remaining address of memory location after the
3 bits word and 6 bits block
prepared by Dr PVSL 98
prepared by Dr PVSL 99
Disadvantage
Hit ratio may drop if 2 or more address words
whose address has the same INDEX but
different TAG are accessed repeatedly.

Main memory address can have the same index

part but different tag part will occupy the
same cache line

prepared by Dr PVSL 100

SET ASSOCIATIVE MEMORY MAPPING

prepared by Dr PVSL 101

Write-Back (Copy-Back)
When writing into memory
o If Hit, only Cache is written
o If Miss, missing block is brought to cache and write into
Cache

For a read miss, replaced block must be written back to the

memory.
And this is the only time the block is updated.
Memory is not up-to-date, i.e., the same item in cache and
memory may have different value
prepared by Dr PVSL 102
Cache Write policies
Write Through
Memory is always updated
When writing into memory
o If Hit, then both cache and memory is written in parallel
o If Miss, then memory is written
o For a read miss, missing block may be overloaded onto
a cache block
Slow as memory is always accessed

prepared by Dr PVSL 103

VIRTUAL MEMORY
 Virtual Memory
• The address used by a programmer will be called a
virtual address or logical address. Or addresses of
auxiliary memory
• An address in main memory is called a physical
address
 Virtual Memory
The term page refers to groups of address space
of the same size

For example: if auxiliary memory contains

1024K and main memory contains 32K and
page size equals to 1K, then auxiliary memory
has 1024 pages and main memory has 32
pages
 Virtual Memory
Only part of the program needs to be in memory
for execution
Logical address space can therefore be much
larger than physical address space
Allows for more efficient process creation
prepared by Dr PVSL 108
prepared by Dr PVSL 109
prepared by Dr PVSL 110
prepared by Dr PVSL 111
 Page Replacement
• 1. FIFO
• 2. LRU
Logical to physical address mapping
Numerical example
prepared by Dr PVSL 116
prepared by Dr PVSL 117
prepared by Dr PVSL 118
prepared by Dr PVSL 120
Memory protection

prepared by Dr PVSL 121

ADDITIONAL

prepared by Dr PVSL 122

 Demand Paging
• In stead of loading whole program into
memory, demand paging is an alternative
strategy to initially load pages only as they are
needed

• Lazy Swapper: Pages are only loaded when

they are demanded during program execution
Transfer of a page memory to continuous
disk space
 Demand paging basic concepts
• When a process is to be swapped in, the pager
guesses which pages will be used before the
process is swapped out again.
• Instead of swapping in a whole process, the
pager brings only those necessary pages into
memory
 Valid-Invalid Bit

• With each page table entry a

valid–invalid bit is associated
(v=> in-memory , i =>not-in-memory)
• Initially valid–invalid bit is set to i on all entries

• During address translation, if valid–invalid bit in page

table entry is i => page fault
Valid-Invalid Bit Example
Valid-Invalid Bit Example
Page Fault
Page Fault
 Performance of Demand Paging
Page Fault Rate 0 ≤p≤1.0
• if p= 0 no page faults
• if p= 1, every reference is a fault

• Effective Access Time (EAT)=

(1-p)*ma + p*page fault time
Performance of Demand Paging
 Performance of Demand Paging
• If we want performance degradation to be less than
10%, we need

220 > 200+7,999,800*p

20>7,999,800*p
P<0.0000025

It is important to keep the page-fault rate low in a

demand-paging system
 9.4 Page Replacement
• What if there is no free frame?

• Page replacement –find some page in

memory, but not really in use, swap it out
• In this case, same page may be brought into
memory several times
Basic Page Replacement
Page Replacement
 Page Replacement Algorithms
• Goal:
Want lowest page-fault rate

Evaluate algorithm by running it on a particular string of

memory references (reference string) and computing the
number of page faults on that string

• In all our examples, the reference string is

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
 FIFO
• When a page must be replaced, the oldest
page is chosen
 FIFO
• When a page must be replaced, the oldest page is chosen

• In all our examples, the reference string is

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• 3 frame (9 page faults)
• 4 frame (10 page faults)

• Notice that the number of faults for 4 frames is greater than

the umber of faults for 3 frames!! This unexpected result is
known as Belady’s anomaly
FIFO Illustrating Belady’s Anomaly
FIFO Algorithm
 Optimal Page-Replacement Algorithm

• Replace page that will not be used for longest

period of time

• This is a design to guarantee the lowest page-

fault rate for a fixed number of frames
Optimal Page-Replacement Algorithm
Optimal Page-Replacement Algorithm
 Optimal Page-Replacement Algorithm
• Unfortunately, the optimal page-replacement
is difficult to implement, because it requires
future knowledge of the reference string
 Least-recently-used (LRU) algorithm
• LRU replacement associates with each page
the time of that page’s last use
• When a page must be replaced, LRU chooses
the page that has not been used for the
longest period of time
Least-recently-used (LRU) algorithm
Least-recently-used (LRU) algorithm
 Least-recently-used (LRU) algorithm
• The major problem is how to implement LRU replacement:
1. Counter: whenever a reference to a page is made, the
content of the clock register are copied to the time-of-use
filed in the page table entry for the page. We replace the
page with the smallest time value
2. Stack: Whenever a page is referenced, it is removed from
the stack and put on the top. In this way, the most recently
used page is always at the top of the stack
Stack implementation
 Second-Chance Algorithm
• Basically, it’s a FIFO algorithm
• If the page is referenced, we set the bit into 1
• When a page has been selected, we inspect its reference bit.
• If the value is 0, we proceed to replace this page, otherwise,
we give the page a second chance and move on to select the
next FIFO page
• When a page get a second chance, it’s reference bit is cleared,
and its arrival time is reset to the current time
 Second-Chance Algorithm
• When a page get a second chance, it’s
reference bit is cleared, and its arrival time is
reset to the current time
• If a page is used often enough to keep its
reference bit set, it will never be replaced
Counting Based Page Replacement
• Least Frequently used (LFU) page-replacement
algorithm

• Most frequently used (MFU) page-

replacement algorithm