Chameli Devi Group of Institutions

Department of Computer Science and Engineering

Subject: Computer Organization & Architecture(CS-404)

UNIT-IV (CO4)
Memory Organization: Main memory- RAM, ROM, Secondary Memory – Magnetic Tape, Disk, Optical
Storage, Cache Memory: Cache Structure and Design, Mapping Scheme, Replacement Algorithm, Improving
Cache Performance, Virtual Memory, memory management hardware.

Memory Organization
The memory unit is an essential component in any digital computer since it is needed for storing programs and
data. The memory unit that communicates directly with CPU is called the main memory. Devices that provide
backup storage are called auxiliary memory. The most common auxiliary memory devices used in computer
systems are magnetic disks and tapes. They are used for storing system programs, large data files, and other
backup information. Only programs and data currently needed by the processor reside in main memory. All the
other information is stored in auxiliary memory and transferred to main memory when needed.

Figure 4.1: Memory hierarchy

Figure 4.1 illustrates the components in a typical memory hierarchy.

At the bottom of the hierarchy are the relatively slow magnetic tapes used to store removable files.
Next are the magnetic disks used as backup storage.
The main memory occupies a central position by being able to communicate directly with the CPU and
with auxiliary memory devices through an I/O processor.
A special very-high-speed memory called a cache memory is sometimes used to increase the speed of
processing by making current programs and data available to the CPU at a rapid rate.
The cache memory is employed in computer systems to compensate for the speed differential between
main memory access time and processor logic.

Main Memory
 The main memory is the central storage unit in a computer system.
 It is a relatively fast memory used to store programs and data during the computer operation.
 The principal technology used for the main memory is based on semiconductor integrated circuits.
Integrated circuit RAM chips are available in two possible operating modes, static and dynamic.
 The static RAM consists essentially of internal flip-flops that store the binary information. The stored
information remains valid as long as power is applied to the unit.
 The dynamic RAM stores the binary information in the form of electric charges that are applied to
capacitors.
 The capacitors are provided inside the chip by MOS transistors.
RAM Chips

Figure 4.2: Block diagram of a RAM chip

The block diagram of a RAM chip is shown in Figure 4.2. The capacity of the memory is 128 words of eight
bits (one byte) per word. This requires a 7-bit address and an 8- bit bidirectional data bus.

The read and write inputs specify the memory operation and the two chips select (CS) control inputs are
enabling the chip only when it is selected by the microprocessor. The availability of more than one control input
to select the chip facilitates the decoding of the address lines when multiple chips are used in the
microcomputer. The read and write inputs are sometimes combined into one line labeled R/W. When the chip is
selected, the two binary states in this line specify the two operations of read or write. The function table listed in
Figure 3 specifies the operation of the RAM chip. When the WR input is enabled, the memory stores a byte
from the data bus into a location specified by the address input lines. When the RD input is enabled, the content
of the selected byte is placed into the data bus. The RD and WR signals control the memory operation as well as
the bus buffers associated with the bidirectional data bus.

ROM Chips

ROM chip is organized externally in a similar manner. However, since a ROM can only read, the data bus can
only be in an output mode. The block diagram of a ROM chip is shown in Figure 4. For the same-size chip, it is
possible to have more bits of ROM than of RAM, because the internal binary cells in ROM occupy less space
than in RAM. For this reason, the diagram specifies a 512-byte ROM, while the RAM has only 128 bytes. The
nine address lines in the ROM chip specify any one of the 512 bytes stored in it. The two chip select inputs must
be CS1 = 1 and CS2 = 0 for the unit to operate. Otherwise, the data bus is in a high-impedance state. There is no
need for a read or write control because the unit can only read. Thus when the chip is enabled by the two select
inputs, the byte selected by the address lines appears on the data bus.

Figure 4.3: Rom Chip

Secondary Memory
The most common auxiliary memory devices used in computer systems are magnetic disks and tapes. Other
components used, but not as frequently, are magnetic drums, magnetic bubble memory, and optical disks.
The recording surface rotates at uniform speed and stopped during access operations. Bits are recorded as
magnetic spots on the surface as it passes a stationary mechanism called a write head. Stored bits are detected by
a change in magnetic field produced by a recorded spot on the surface as it passes through a read head. The
amount of surface available for recording in a disk is greater than in a drum of equal physical size. Therefore,
more information can be stored on a disk than on a drum of comparable size. For this reason, disks have replaced
drums in more recent computers.
Magnetic Disks

Figure 4.4: Magnetic Disk

 A magnetic disk is a circular plate constructed of metal or plastic coated with magnetized material.
 Often both sides of the disk are used and several disks may be stacked on one spindle with read/write
heads available on each surface.
 All disks rotate together at high speed and are not stopped or started for access
purposes.
 The tracks are commonly divided into sections called sectors.
o In most systems, the minimum quantity of information which can be transferred
is a sector. The subdivision of one disk surface into tracks and sectors is shown
in Figure5.
o There are two sizes commonly used, with diameters of 5.25 and 3.5 inches. The 3.5-inch
disks are smaller and can store more data than can the 5.25-inch disks.
Optical Storage
Optical storage devices use optical technology to save and retrieve data on discs, like a Blu-ray, CD, DVD. The
device uses a laser light to read information on the disc and to "write" new information to the disc for future
retrieval.
Cache Memory
A special very-high-speed memory called a cache memory is sometimes used to increase the speed of
processing by making current programs and data available to the CPU at a rapid rate.
Cache Structure and Design
The basic operation of the cache is as follows:
 When the CPU needs to access memory, the cache is examined. If the word is found in the cache, it is
called cache hit. If the word addressed by the CPU is not found in the cache, the main memory is
accessed to read the word and it is called cache miss.
 Some data are transferred to cache so that future references to memory find the required words in the fast
cache memory.
 The performance of cache memory is frequently measured in terms of a quantity called hit ratio.
 The ratio of the number of hits divided by the total CPU references to memory (hits plus misses) is the hit
ratio.
 The transformation of data from main memory to cache memory is referred to as a mapping process.
.

Figure 4.5: Example of cache memory

Mapping schemes
1. Associative Mapping
The fastest and most flexible cache organization uses an associative memory.
The associative memory stores both the address and content (data) of the memory word.
This permits any location in cache to store any word from main memory.

Figure 4.6: Associative mapping

2. Direct Mapping
 Associative memories are expensive compared to random-access memories because of the added logic
associated with each cell.
 The CPU address of 15 bits is divided into two fields. The nine least significant bits constitute the index
field and the remaining six bits forms the tag field.

Figure 4.7: Direct Mapping

3. Set-Associative Mapping
A third type of cache organization, called set associative mapping, is an improvement over the direct-mapping
organization, in that each word of cache can store two or more words of memory under the same index address.
Each data word is stored together with its tag and the number of tag data items in one word of cache is said to
form a set.

Figure 4.8: Set Associative Mapping

Replacement Algorithm
A virtual memory system is a combination of hardware and software techniques. The memory management
software system handles all the software operations for the efficient utilization of memory space.
It must decide:
Which page in main memory ought to be removed to make room for a new page.
When a new page is to be transferred from auxiliary memory to main memory.
Where the page is to be placed in main memory.
The hardware mapping mechanism and the memory management software together constitute the architecture
of a virtual memory. When a program starts execution, one or more pages are transferred into main memory
and the page table is set to indicate their position. The program is executed from main memory until it attempts
to reference a page that is still in auxiliary memory. This condition is calledpage fault. When page fault occurs,
the execution of the present program is suspended until the required page is brought into main memory.

Three of the most common replacement algorithms used is the First-In-First – Out (FIFO), Least Recently
Used (LRU) and the Optimal Page Replacement Algorithms.

FIFO
 The FIFO algorithm selects for replacement the page that has been in memory the longest time.
Each time a page is loaded into memory, its identification number is pushed into a FIFO stack.
 FIFO will be full whenever memory has no more empty blocks.
 When a new page must be loaded, the page least recently brought in is removed.
 The FIFO replacement policy has the advantage of being easy to implement.
 It has the disadvantage that under certain circumstances pages are removed and loaded from memory too
frequently.
LRU
 The LRU policy is more difficult to implement but has been more attractive on the assumption that the
least recently used page is a better candidate for removal than the least recently loaded page as in FIFO.
 The LRU algorithm can be implemented by associating a counter with every page that is in main memory.
 When a page is referenced, its associated counter is set to zero. At fixed intervals of time, the counters
associated with all pages presently in memory are incremented by 1.
 The least recently used page is the page with the highest count.
 The counters are often called aging registers, as their count indicates their age, that is, how long ago their
associated pages have been referenced.

Optimal Page Replacement Algorithms

 The optimal page algorithm simply says that the page with the highest label should be removed.
 If one page will not be used for 8 million instructions and another page will not be used for 6 million
instructions, removing the former pushes the page fault that will fetch it back as far into the future as
possible.

In this algorithm, pages are replaced which would not be used for the longest duration of time in the future, i.e.,
the pages in the memory which are going to be referred farthest in the future are replaced.
This algorithm was introduced long back and is difficult to implement because it requires future knowledge of
the program behavior. However, it is possible to implement optimal page replacement on the second run by
using the page reference information collected on the first run.
For Example

Total Page Fault = 6

Initially, all 4 slots are empty, so when 1, 2, 3, 4 came they are allocated to the empty slots in order of their
arrival. This is page fault as 1, 2, 3, 4 are not available in memory.
When 5 comes, it is not available in memory so page fault occurs and it replaces 4 which is going to be used
farthest in the future among 1, 2, 3, 4.
When 1,3,1 comes, they are available in the memory, i.e., Page Hit, so no replacement occurs.
When 6 comes, it is not available in memory so page fault occurs and it replaces 1.
When 3, 2, 3 comes, it is available in the memory, i.e., Page Hit, so no replacement occurs.
Page Fault ratio = 6/12

Improving Cache Performance

There are three ways to improve cache performance:
1. Reduce the miss rate.
2. Reduce the miss penalty.
3. Reduce the time to hit in the cache.

Virtual Memory

 Virtual memory is a concept used in some large computer systems that permit the user to construct
programs as though a large memory space were available, equal to the totality of auxiliary memory.
 Each address that is referenced by the CPU goes through an address mapping from the so-called virtual
address to a physical address in main memory.
 Virtual memory is used to give programmers the illusion that they have a very large memory at their
disposal, even though the computer actually has a relatively small main memory.

Address Space and Memory Space

  An address used by a programmer will be called a virtual address, and the set of such addresses is the
address space.
 An address in main memory is called a location or physical address. The set of such locations is called the
memory space.
 Thus the address space is the set of addresses generated by programs as they reference instructions and
data, the memory space consists of the actual main memory locations directly addressable for processing.
 In most computers the address and memory spaces are identical. The address space is allowed to be larger
than the memory space in computers with virtual memory.
 In a multi-program computer system, programs and data are transferred to and from auxiliary memory
and main memory based on demands imposed by the CPU.

Figure 4.9: Relation between address and memory space in a virtual memory system.

Memory Management Hardware

A memory management system is a collection of hardware and software procedures for managing the various
programs residing in memory.
The memory management software is part of an overall operating system available in many computers.
The basic components of a memory management unit are:
 A facility for dynamic storage relocation that maps logical memory references into physical memory
addresses
 A provision for sharing common programs stored in memory by different users.
 Protection of information against unauthorized access between users and preventing users from changing
operating system functions
 The dynamic storage relocation hardware is a mapping process similar to the paging system. The fixed page
size used in the virtual memory system causes certain difficulties with respect to program size and the
logical structure of programs.
 It is more convenient to divide programs and data into logical parts called segments.
 A segment is a set of logically related instructions or data elements associated with a given name.
 Examples of segments are a subroutine, an array of data, a table of symbols, or a user's program. The
address generated by a segmented program is called a logical address.
 This is similar to a virtual address except that logical address space is associated with variable-length
 segments rather than fixed-length pages.