COMPUTER

ARCHITECTURE
PCC-CS 402
Module 2 Part 3

Department of Computer Science & Engineering

2nd Year,4th Semester
2022
Memory Organization

• Virtual memory organization

• Mapping and management techniques,
memory replacement policies
• Memory management
 Virtual Memory

Registers

Cache
Access Time

Capacity Memory
Cost

Main Memory
Virtual
Memory
Hard Disk

CD/DVD/Tape
 Virtual Memory
• Hard Disk capacity is much more than Main Memory
• To increase effective size of the Main Memory, part of Hard Disk
memory can be utilized to behave similar to Main Memory
• Cache memory is an architectural arrangement which makes main
memory appear faster to the processor than it really is
• Virtual memory is an architectural arrangement which makes main
memory appear larger than it really is
 Address Space
• Memory address space depends on the number of address bits in a
computer:
− For a computer using 32-bit addresses, address space is 4 Gigabytes
− For a 64-bit computer, address space is 16 Exabytes
• Physical main memory in a computer is generally not as large as the
entire addressable space
• Large programs that cannot fit completely into the main memory have
their parts stored on auxiliary storage devices
• Pieces of programs transferred to the main memory from secondary
storage before they can be executed
 Virtual Memory
• When a new piece of a program is to be transferred to the main
memory, and if the main memory is full, some other piece in the main
memory must be replaced
• The portion of main memory moved out is stored in disk memory
• Operating system automatically transfers data between the main
memory and disk storage
• Application programmer need not be concerned with this transfer
• Also, application programmer does not need to be aware of the
limitations imposed by the available physical memory
 Virtual Memory
• Virtual Memory techniques automatically move program and data
between main memory and disk storage
• Address used by Processor for instruction or data is called logical or
virtual addresses
• Virtual addresses are translated into physical addresses by a
combination of hardware and software subsystems
− If virtual address maps to an address in main memory, it is accessed
immediately
− If virtual address maps to an address currently not in the main memory,
it is first transferred to the main memory before it can be used
 Memory Page
• Memory is broken down into fixed-length units called pages
• A page occupies contiguous locations in the main memory
• Page is a basic unit of information transferred between disk storage
and main memory
• Size of a page commonly ranges from 2K to 16K bytes
− Page size should not be too small, because it will require too many
access to disk, slowing down memory access
− Page size can not be too large, else a large portion of the page may
not be used, wasting valuable space in the main memory
VIRTUAL MEMORIES (CONTD..)

 Virtual addresses are translated into physical

addresses by a combination of hardware and software
subsystems.
 If virtual address refers to a part of the program that is currently in
the main memory, it is accessed immediately.
 If the address refers to a part of the program that is not currently in
the main memory, it is first transferred to the main memory before it
can be used.
VIRTUAL MEMORY ORGANIZATION

Processor
•Memory management unit (MMU) translates
virtual addresses into physical addresses.
Virtual address
•If the desired data or instructions are in the
Data MMU main memory they are fetched as described
previously.
Physical address •If the desired data or instructions are not in
the main memory, they must be transferred
Cache
from secondary storage to the main memory.
Data Physical address •MMU causes the operating system to bring
the data from the secondary storage into the
Main memory main memory.
DMA transfer

Disk storage

10
physical
pages
virtual
pages
 Address Translation
• Each virtual or logical address generated by a processor contains the
virtual page number along with an offset that specifies the location of a
particular byte within that page
• Information about location of each page in is kept in a special table
called Page Table, which includes:
• Area of the main memory that can hold a page is called Page Frame
• Starting address of the page table is kept in Page Table Base Register
 Address Translation
Virtual address from processor
Page table base register
Page table address Virtual page number Offset

+
PAGE TABLE

Control Page frame Offset

Page frame
bits In memory
Physical address in main memory
 ADDRESS TRANSLATION (CONTD..)
PTBR holds Virtual address from processor
Page table base register
the address of
the page table. Page table address Virtual page number Offset
Virtual address is
interpreted as page
+ number and offset.
PAGE TABLE
PTBR + virtual
page number provide
the entry of the page This entry has the starting location
in the page table. of the page.

Page table holds information

about each page. This includes
the starting address of the page
in the main memory. Control
bits
Page frame
in memory Page frame Offset

Physical address in main memory

14
 Page Table
• Page table maps each virtual page to a specific page frame in
memory
• The virtual address provided by processor contains virtual page
number along with offset of the desired location in the page
• Virtual page number, added with Page Table Base Register,
identifies the page in Page Table
• For each virtual page, its page frame starting address in memory
in stored in the Page Table
• The physical address of the memory location is arrived at by
combining starting address of the page frame along with the
offset
 Page Table Control
• Page table entry also includes control information about the page
• Valid Bit indicates the validity of the page, set to ‘1’ if the page
frame is in memory, ‘0’ otherwise
• In case the page in not in main memory, accessing the page will
result in a page fault and it will be copied from disk storage
• Modified Bit indicates whether the page content has been
modified
• If Modified, the page must be written back to the disk when it is
removed from the main memory
• Similar consideration as the dirty or modified bit of cache
memory
 Page Table Access
• Page Table is accessed frequently, for every read and write operation
in the memory
• Depending upon the total size of virtual memory, number of entries
Page Table can quite large
• Thus the Page table is kept in the main memory
• A small portion of the page table, containing recently accessed pages,
is kept in the cache memory to improve access time
• This copy of Page Table in cache is called Translation Lookaside
Buffer (TLB)
ADDRESS TRANSLATION (CONTD..)
 A small cache called as Translation Lookaside Buffer (TLB) is
included in the MMU.
 TLB holds page table entries of the most recently accessed pages.
 Recall that cache memory holds most recently accessed blocks from
the main memory.
 Operation of the TLB and page table in the main memory is similar to the operation of
the cache and main memory.
 Page table entry for a page includes:
 Address of the page frame where the page resides in the main memory.
 Some control bits.
 In addition to the above for each page, TLB must hold the virtual
page number for each page.

18
 Translation Lookaside Buffer
• Translation Lookaside Buffer (TLB) is a fully associative cache that
holds page table entries
• Page table entry in TLB includes address of the page frame in the main
memory, along with its control information
• The mapping of an entry in TLB is done in the same way as Page Table
Address Translation
• To map a virtual page number in TLB, all entries of TLB are checked for
a match (fully associative cache)
• In case of a hit, entry from TLB is used to access page in memory
• In case of miss, the page entry is copied from Page Table before access
 TLB frame
frame
frame
frame

We access the TLB on every reference instead of the page table. TLB must
therefore include the valid, dirty and the reference bits.
 Every reference looks up the virtual
page # in TLB.
frame
frame
frame
frame TLB hit uses the physical page #
to form the address and turns on
the reference bit. Write turns on
the dirty bit too.

A TLB miss can be either a true page fault or just a TLB miss. If the
page exists in memory, the processor loads the translation from the page
table into the TLB and tries the reference again.

In a true page fault the processor invokes the OS (exception).

TLB has much fewer entries than pages in main memory. TLB misses are therefore 21
much more frequent than page faults.
 TLB Operation
Virtual address from processor

Virtual page number Offset

TLB
Virtual page Control Page frame in
number bits memory

No
=?
Miss
Yes
Hit
Page frame Offset

Physical address in main memory

 TLB UPDATES
• Any updates in Page Table in Main Memory must be also be carried
out in the TLB
• Operating system may change contents of the Page Table
• In case an entry in Page Table is modified, corresponding entry in TLB
is no longer valid
• Valid Bit for the entry in TLB indicates if the copy of the page entry is
valid or not
• If an entry is invalid, TLB needs to update it from the Page Table
• Very similar to cache update operation
 PAGE FAULT
• Page Fault occurs when a program requests access to a page
not in Main Memory
• The page must be brought into the main memory from the
Disk Memory, before the program can proceed
• Operating System suspends processing of the program while
the page is being copied from disk
• Once the page is available in main memory, corresponding
Page Table entry is updated and the program resumes
execution
 PAGE REPLACEMENT
• When a new page is to be brought into the main memory from
secondary storage, the main memory may be full
• A page in the main memory must be replaced for this new page
• Two common page replacement strategies are
− FIFO (First In First Out)
Pages copied earliest are replaced first
− LRU (Least Recently Used)
Page accessed earliest are replaced first
• Very similar to replacement operation in Cache Memory
PAGE REPLACEMENT ALGORITHMS 1
 The page replacement algorithm decides which memory page is to
be replaced. The process of replacement is sometimes called swap
out or write to disk. Page replacement is done when the requested
page is not found in the main memory (page fault).
PAGE REPLACEMENT
 PAGE AND FRAME REPLACEMENT ALGORITHMS

 Frame-allocation algorithm determines

 How many frames to give each process
 Which frames to replace

 Page-replacement algorithm
 Want lowest page-fault rate on both first access and re-access
 Evaluate algorithm by running it on a particular string of memory
references (reference string) and computing the number of page faults on
that string
 String is just page numbers, not full addresses
 Repeated access to the same page does not cause a page fault
 Results depend on number of frames available

 In all our examples, the reference string of referenced page numbers is

7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
PAGE REPLACEMENT ALGORITHMS 2

 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.
PAGE REPLACEMENT ALGORITHMS 3
 First In First Out (FIFO) –In this algorithm, a queue is
maintained. The page which is assigned the frame first will be
replaced first. In other words, the page which resides at the rare
end of the queue will be replaced on the every page fault.
 Least recent used (LRU) page replacement algorithm → this
algorithm replaces the page which has not been referred for a long
time. This algorithm is just opposite to the optimal page
replacement algorithm. In this, we look at the past instead of
staring at future.
 Optimal Page Replacement algorithm → this algorithms
replaces the page which will not be referred for so long in future.
Although it can not be practically implementable but it can be used
as a benchmark. Other algorithms are compared to this in terms of
optimality.
FIRST-IN-FIRST-OUT (FIFO) ALGORITHM

 Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

 3 frames (3 pages can be in memory at a time per process)

15 page faults

 Can vary by reference string: consider 1,2,3,4,1,2,5,1,2,3,4,5

 Adding more frames can cause more page faults!
 Belady’s Anomaly
 How to track ages of pages?
 Just use a FIFO queue
FIFO ILLUSTRATING BELADY’S ANOMALY
 OPTIMAL ALGORITHM
 Replace page that will not be used for longest period of time
 9 is optimal for the example
 How do you know this?
 Can’t read the future
 Used for measuring how well your algorithm performs
LEAST RECENTLY USED (LRU) ALGORITHM

 Use past knowledge rather than future

 Replace page that has not been used in the most amount of time
 Associate time of last use with each page

 12 faults – better than FIFO but worse than OPT

 Generally good algorithm and frequently used
 But how to implement?
LRU ALGORITHM (CONT.)
 Counter implementation
 Every page entry has a counter; every time page is referenced through this
entry, copy the clock into the counter
 When a page needs to be changed, look at the counters to find smallest
value
 Search through table needed
 Stack implementation
 Keep a stack of page numbers in a double link form:
 Page referenced:
 move it to the top
 requires 6 pointers to be changed

 But each update more expensive

 No search for replacement
 LRU and OPT are cases of stack algorithms that don’t have
Belady’s Anomaly
TUTORIAL
 Consider page reference string 1, 3, 0, 3, 5, 6,3 with 3 page frames.
Find number of page faults.
PAGE REPLACEMENT ALGORITHMS EXAMPLE (FIFO)
THRASHING

 If a process does not have “enough” pages, the page-fault rate is

very high
 Page fault to get page
 Replace existing frame
 But quickly need replaced frame back
 This leads to:
 Low CPU utilization
 Operating system thinking that it needs to increase the degree of

multiprogramming
 Another process added to the system

 Thrashing  a process is busy swapping pages in and out

MEMORY MANAGEMENT
 Operating system is concerned with transferring programs and data
between secondary storage and main memory.
 Operating system needs memory routines in addition to the other
routines.
 Operating system routines are assembled into a virtual address
space called system space.
 System space is separate from the space in which user application
programs reside.
 This is user space.
 Virtual address space is divided into one
system space + several user spaces.
MEMORY MANAGEMENT (CONTD..)
 Recall that the Memory Management Unit (MMU) translates
logical or virtual addresses into physical addresses.
 MMU uses the contents of the page table base register to
determine the address of the page table to be used in the
translation.
 Changing the contents of the page table base register can enable us to use a
different page table, and switch from one space to another.
 At any given time, the page table base register can point to one
page table.
 Thus, only one page table can be used in the translation process at a given
time.
 Pages belonging to only one space are accessible at any
given time.
MEMORY MANAGEMENT (CONTD..)
 When multiple, independent user programs coexist in the main
memory, how to ensure that one program does not modify/destroy
the contents of the other?
 Processor usually has two states of operation:
 Supervisor state.
 User state.
 Supervisor state:
 Operating system routines are executed.
 User state:
 User programs are executed.
 Certain privileged instructions cannot be executed in user state.
 These privileged instructions include the ones which change page table base
register.
 Prevents one user from accessing the space of other users.