UNIT – IV:

The Memory Organization: Basic Concepts, Semiconductor RAM Memories, Read-Only

Memories, Speed, Size and Cost, Cache Memories, Performance Considerations, Virtual
Memories, Memory Management Requirements, Secondary Storage
  The main memory is the central storage unit in a computer system.
 Primary memory holds only those data and instructions on which computer is
currently working.
 It has limited capacity and data is lost when power is switched off.
 It is generally made up of semiconductor device.
 These memories are not as fast as registers.
 The data and instruction required to be processed reside in main memory.
 It is divided into two subcategories RAM and ROM.
Memory address map of RAM and ROM
 The designer of a computer system must calculate the amount of memory required for
the particular application and assign it to either RAM or ROM.
 The interconnection between memory and processor is then established from
knowledge of the size of memory needed and the type of RAM and ROM chips
available.
 The addressing of memory can be established by means of a table that specifies the
memory address assigned to each chip.
 The table, called a memory address map, is a pictorial representation of assigned
address space for each chip in the system, shown in table
  To demonstrate with a particular example, assume that a computer system needs 512
bytes of RAM and 512 bytes of ROM.
 The RAM and ROM chips to be used are specified in figures
 Main memory is the central storage unit in a computer system. It is a relatively large
and fast memory used to store programs and data during the computer operation.
 The principal technology used for the main memory is based on semi conductor
integrated circuits. Integrated circuits RAM chips are available in two possible
operating modes, static and dynamic.
• Static RAM – Consists of internal flip flops that store the binary information.
• Dynamic RAM – Stores the binary information in the form of electric charges that are
applied to capacitors.
 Most of the main memory in a general purpose computer is made up of RAM
integrated circuit chips, but a portion of the memory may be constructed with ROM
chips.
 Read Only Memory –Store programs that are permanently resident in the computer
and for tables of constants that do not change in value once the production of the
computer is completed.
 The ROM portion of main memory is needed for storing an initial program called a
Bootstrap loader.
• Boot strap loader –function is start the computer software operating when power is turned
on.
• Boot strap program loads a portion of operating system from disc to main memory and
control is then transferred to operating system.
RAM and ROM CHIP :
• RAM chip –utilizes bidirectional data bus with three state buffers to perform
communication with CPU
 The capacity of 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 read and write inputs are sometimes combined into one line labelled R/W.

 The unit is in operation only when CS1=1 and =0.The bar on top of the
second select variable indicates that this input is enabled when it is equal to 0.
 If the chip select inputs are not enabled, or if they are enabled but the read or write
inputs are not enabled, the memory is inhibited and its data bus is in a high-impedance
state.

 When CS1=1 and =0, the memory can be placed in a write or read mode.
 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.

 A 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 fig.
 The nine address lines in the ROM chip specify any one of the512 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.
Memory Address Map
 The interconnection between memory and processor is then established from
knowledge of the size of memory needed and the type of RAM and ROM chips
available.
 The addressing of memory can be established by means of a table that specify the
memory address assigned to each chip.
 The table called Memory address map, is a pictorial representation of assigned
address space for each chip in the system.
 The component column specifies whether a RAM or a ROM chip is used. The
hexadecimal address column assigns a range of hexadecimal equivalent addresses for
each chip.
 The address bus lines are listed in the third column. The RAM chips have 128 bytes
and need seven address lines.
The ROM chip has 512 bytes and needs 9 address lines

Memory Connection to CPU

 RAM and ROM chips are connected to a CPU through the data and address buses.
 The low order lines in the address bus select the byte within the chips and other lines
in the address bus select a particular chip through its chip select inputs.
 This configuration gives a memory capacity of 512 bytes of RAM and 512 bytes of
ROM.
 Each RAM receives the seven low-order bits of the address bus to select one of 128
possible bytes.
 The particular RAM chip selected is determined from lines 8 and 9 in the address bus.
 This is done through a 2 X 4 decoder whose outputs go to the CS1 inputs in each
RAM chip.
 Thus, when address lines 8 and 9 are equal to 00, the first RAM chip is selected.
 When 01, the second RAM chip is select, and so on. The RD and WR outputs from
the microprocessor are applied to the inputs of each RAM chip.
 The selection between RAM and ROM is achieved through bus line 10. The RAMs
are selected when the bit in this line is 0.
 The ROM when the bit is 1. Address bus lines 1 to 9 are applied to the input address
of ROM without going through the decoder.
 The data bus of the ROM has only an output capability, whereas the data bus
connected to the RAMs can transfer information in both directions.

Associative Memory
 The time required to find an item stored in memory can be reduced considerably if
stored data can be identified for access by the content of the data itself rather than by
an address.
 A memory unit accessed by content is called an associative memory or content
addressable memory (CAM).
 CAM is accessed simultaneously and in parallel on the basis of data content rather
than by specific address or location
• Associative memory is more expensive than a RAM because each cell must have
storage capability as well as logic circuits
• Argument register –holds an external argument for content matching.
• Key register –mask for choosing a particular field or key in the argument word

 It consists of a memory array and logic for m words with n bits per word.
 The argument register A and key register K each have n bits, one for each bit of a
word.
 The match register M has m bits, one for each memory word. Each word in memory is
compared in parallel with the content of the argument register.
 The words that match the bits of the argument register set a corresponding bit in the
match register.
 After the matching process, those bits in the match register that have been set indicate
the fact that their corresponding words have been matched.
 Reading is accomplished by a sequential access to memory for those words whose
corresponding bits in the match register have been set.
 The key register provides a mask for choosing a particular field or key in the
argument word.
 The entire argument is compared with each memory word if the key register contains
all l' s. Otherwise, only those bits in the argument that have l's in their corresponding
position of the key register are compared.
 Thus the key provides a mask or identifying piece of information which specifies how
the reference to memory is made.
 To illustrate with a numerical example, suppose that the argument register A and the
key register K have the bit configuration shown below.
 Only the three leftmost bits of A are compared with memory words because K has 1's
in these positions.
 Word 2 matches the unmasked argument field because the three leftmost bits of the
argument and the word are equal.

 The relation between the memory array and external registers in an associative
memory is shown in Fig.
 The cells in the array are marked by the letter C with two subcripts.
 The first subscript gives the word number and the second specifies the bit
position in the word. Thus cell Cij is the cell for bit j in word i.
 A bit Ai in the argument register is compared with all the bits in column j of the array
provided that Ki = 1.
 This is done for all columns j = 1, 2, . . . , n. If a match occurs between all the
unmasked bits of the argument and the bits in word i, the corresponding bit M1 in the
match register is set to 1.
If one or more unmasked bits of the argument and the word do not match, M1 is
cleared to 0
 The internal organization of a typical cell Cij is shown in Fig.
 It consists of a flip-flop storage element Fij and the circuits for reading, writing, and
matching the cell.
  The input bit is transferred into the storage cell during a write operation.
 The bit stored is read out during a read operation.
 The match logic compares the content of the storage cell with the corresponding un
masked bit of the argument and provides an output for the decision logic that sets the
bit in Mi

Match Logic
 The match logic for each word can be derived from the comparison algorithm for two
binary numbers.
 First, neglect the key bits and compare the argument in A with the bits stored in the
cells of the words.
 Word i is equal to the argument in A if Aj=Fij for j=1,2,…..,n.
 Two bits are equal if they are both 1 or both 0. The equality of two bits can be
expressed logically by the Boolean function
, ,
X j= A j F ij + A J F iJ

 where xj = 1 if the pair of bits in position j are equal ; otherwise , xj =0.

 For a word i is equal to the argument in A we must have all xj variables equal to 1.
 This is the condition for setting the corresponding match bit Mi to 1. The Boolean
function for this condition is
 Mi = x1 x2 x3…… xn
 We now include the key bit Kj in the comparison logic.
 The requirement is that if Kj = 0, the corresponding bits of A; and f1; need no
comparison. Only when Kj= 1 must they be compared. This requirement is achieved
by ORing each term with K ,J , thus:
  When Kj = 1, we have K ,J = 0 and x; + 0 = xj .

 When Kj = 0, then K ,J = 1 and xj + 1 = 1.

 A term (xj + K ,J ) will be in the 1 state if its pair of bits is not compared. This is
necessary because each term is ANDed with all other terms so that an output of 1 will
have no effect.
 The comparison of the bits has an effect only when Kj = 1.
 The match logic for word i in an associative memory can now be expressed by the
following Boolean function:

 Each term in the expression will be equal to 1 if its corresponding Kj = 0.

 If Kj = 1, the term will be either 0 or 1 depending on the value of Xj.
 A match will occur and Mi will be equal to 1 if all terms are equal to 1.
 If we substitute the original definition of xj, the Boolean function above can be
expressed as follows:

where π is a product symbol designating the AND operation of all n terms. We need m such
functions, one for each word i = 1, 2, 3, . . . , m
CACHE MEMORY
 Effectiveness of cache mechanism is based on a property of computer programs called
“locality of reference”
 The references to memory at any given time interval tend to be confined within a
localized areas
 Analysis of programs shows that most of their execution time is spent on routines in
which instructions are executed repeatedly These instructions may be – loops, nested
loops , or few procedures that call each other
 Many instructions in localized areas of program are executed
 • repeatedly during some time period and reminder of the program is accessed
infrequently This property is called “Locality of Reference”.
 Locality of reference is manifested in two ways :
1. Temporal- means that a recently executed instruction is likely to be executed again
very soon. The information which will be used in near future is likely to λ be in use
already( e.g. reuse of information in loops)
2. Spatial- means that instructions in close proximity to a recently executed instruction
are also likely to be executed soon • If a word is accessed, adjacent (near) words are
likely to be accessed soon ( e.g. related data items (arrays) are usually stored together;
instructions are executed sequentially )

 The main memory can store 32k words of 12 bits each. The cache is capable of
storing 512 of these words at any given time.
 For every word stored , there is a duplicate copy in main memory.
 The CPU communicates with both memories. It first sends a 15 bit address to cache.
If there is a hit, the CPU accepts the 12 bit data from cache.
 If there is a miss, the CPU reads the word from main memory and the word is then
transferred to cache.
 When a read request is received from CPU, contents of a block of memory words
containing the location specified are transferred in to cache
 When the program references any of the locations in this block , the contents are read
from the cache Number of blocks in cache is smaller than number of blocks in main
memory
 Correspondence between main memory blocks and those in the cache is specified by a
mapping function
 Assume cache is full and memory word not in cache is referenced
 Control hardware decides which block from cache is to be removed to create space for
new block containing referenced word from memory
 Collection of rules for making this decision is called “Replacement algorithm ”
Read/ Write operations on cache
Cache Hit Operation
• CPU issues Read/Write requests using addresses that λ refer to locations in main
memory
 • Cache control circuitry determines whether requested word currently exists in cache
• If it does, Read/Write operation is performed on the appropriate location in cache
(Read/Write Hit )
Read/Write operations on cache in case of Hit
• In Read operation main memory is not involved.
• In Write operation two things can happen.
1. Cache and main memory locations are updated λ simultaneously (“ Write Through ”)
OR
Update only cache location and mark it as “ Dirty or Modified Bit ” and update main
memory location at the time of cache block removal (“ Write Back ” or “ Copy Back ”)
Read/Write operations on cache in case of Miss Read Operation
• When addressed word is not in cache Read Miss occurs there are two ways this can be dealt
with
1. Entire block of words that contain the requested word is copied from main memory to
cache and the particular word requested is forwarded to CPU from the cache ( Load
Through ) (OR)
2. The requested word from memory is sent to CPU first and then the cache is updated
( Early Restart )
Write Operation
• If addressed word is not in cache Write Miss occurs
• If write through protocol is used information is directly written in to main memory
• In write back protocol , block containing the word is first brought in to cache , the desired
word is then overwritten.
Mapping Functions
• Correspondence between main memory blocks and those in the cache is specified by a
memory mapping function
• There are three techniques in memory mapping
1. Direct Mapping
2. Associative Mapping
3. Set Associative Mapping
Associative mapping:
In this mapping function, any block of Main memory can potentially reside in any cache
block position. This is much more flexible mapping method.
 The associative memory stores both address and content(data) of the memory word.
This permits any location in cache to store any word from main memory.
 The diagram shows three words presently stored in the cache. The address value of 15
bits is shown as a five-digit octal number and its corresponding 12-bit word is shown
as a four-digit octal number.
 A CPU address of 15-bits is placed in the argument register and the associative
memory is searched for a matching address.
 If address is found, the corresponding 12-bit data is read and sent to the CPU. If no
match occurs, the main memory is accessed for the word.

Direct mapping
A particular block of main memory can be brought to a particular block of cache memory.
So, it is not flexible.
 The CPU address of 15 bits is divided into two fields. The nine least significant bits
constitute the index field and remaining six bits form the tag field.
 The main memory needs an address that includes both the tag and the index bits.
 The number of bits in the index field is equal to the number of address bits required to
access the cache memory.
 The direct mapping cache organization uses the n- bit address to access the main
memory and the k-bit index to access the cache.
 Each word in cache consists of the data word and associated tag.
 When a new word is first brought into the cache, the tag bits are stored alongside the
data bits.
 When the CPU generates a memory request, the index field is used the index field is
used for the address to access the cache.
 The tag field of the CPU address is compared with the tag in the word read from the
cache.
 If the two tags match, there is a hit and the desired data word is in cache.
 If there is no match, there is a miss and the required word is read from main memory.
 The index field is now divided into two parts: Block field and The word field.
 In a 512 word cache there are 64 blocks of 8 words each, since 64X8=512.
 The block number is specified with a 6 bit field and the word with in the block is
specified with a 3-bit field.
 The tag field stored within the cache is common to all eight words of the same block.

Set-associative mapping
In this method, blocks of cache are grouped into sets, and the mapping allows a block
of main memory to reside in any block of a specific set. From the flexibility point of
view, it is in between to the other two methods.
 The octal numbers listed in Fig. are with reference to the main memory contents.
 When the CPU generates a memory request, the index values of the address is used to
access the cache.
 The tag field of the CPU address is then compared with both tags in the cache to
determine if a match occurs.
 The comparison logic dines by an associative search of the tags in the set similar to an
associative memory search thus the name “Set Associative”.
 Replacement Policies
 • When the cache is full and there is necessity to bring new data to cache , then a
decision must be made as to which data from cache is to be removed
 • The guideline for taking a decision about which data is to be removed is called
replacement policy Replacement policy depends on mapping
 • There is no specific policy in case of Direct mapping as we have no choice of block
placement in cache Replacement Policies
 In case of associative mapping
 • A simple procedure is to replace cells of the cache in round robin order whenever a
new word is requested from memory
 • This constitutes a First-in First-out (FIFO) replacement policy
 In case of set associative mapping
 • Random replacement
 • First-in First-out (FIFO) ( item chosen is the item that has been in the set longest)
 • Least Recently Used (LRU)( item chosen is the item λ that has been least recently
used by CPU)

VIRTUAL MEMORY
 Early days memory was expensive – hence small
 Programmers were using secondary storage for overlaying
 Programmers were responsible for breaking programs in to overlays , decide where to
keep in secondary memory, arranging for transfer of overlays between main memory
and secondary memory
 In 1961 Manchester University proposed a method for performing overlay process
automatically which has given rise to the concept of Virtual memory today
Virtual Memory - Background
• Separate concept of address space and memory locations
• Programs reference instructions and data that is independent of available physical
memory Addresses issued by processor for Instructions or Data are called Virtual or
Logical addresses
• Virtual addresses are translated in to physical addresses by a combination of Hardware
and Software components Types of Memory
• Real memory
• Main memory
• Virtual memory
• Memory on disk
• Allows for effective multiprogramming and relieves the user of tight constraints of main
memory
Address Space and Memory Space
 Address used by a programmer is called virtual address and set of such addresses is
called address space
 Address in main memory is called a location or physical address and set of such
locations is called the memory space
 The Address Space is allowed to be larger than the memory space in computers with
virtual memory
 In a multiprogram computer system, programs and data are transferred to and from
auxiliary memory and main memory based on demands imposed by the CPU.
 Suppose that program1 is currently being executed in the CPU.
 Program1 and a portion of its associated data are moved from auxiliary memory into
main memory as shown in fig.
 Portions of programs and data need not be in contiguous locations in memory since
information is being moved in out, and empty spaces may be available in scattered
locations in memory.
 To map a virtual address of 20 bits to a physical address of 15 bits.
 The mapping is a dynamic operation, which means that every address is translated
immediately as a word is referenced by CPU.
 The mapping table may be stored in a separate memory.
 In first case, an additional unit is required as well as one extra memory access time.
 In the second case, the table takes space from main memory and two accesses to
memory are required with program running at half speed.
 A third alternative is to use an associative memory.

Address Mapping Using Pages

 The physical memory is broken down into groups of equal size called blocks, which
may range from 64 to 4096 word each.
 The term page refers to groups of address space of the same size.
 Portions of programs are moved from auxiliary memory to main memory in records
equal to the size of a page.
 The term “page frame” is sometimes used to denote a block.

 a virtual address has 13 bits. Since each page consists of 1024 words, the high order
three bits of virtual address will specify one of the eight pages and the low order 10
bits give the line address within the page.
 The organization of the memory mapping table in a paged system is shown in Fig.
 The memory page table consists of eight word , one for each page.
 The address in the page table denotes the page number and the content of the word
gives the block number where that page is stored in main memory.
 The table shows that pages 1,2,5 and 6 are now available in main memory in blocks
3,0,1 and 2, respectively.
MEMORY MANAGEMENT HARDWARE
 A memory management system is a collection of hardware and software procedure 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:
1. A facility for dynamic storage relocation that maps logical memory references into
physical memory addresses
2. A provision for sharing common programs stored in memory by different users
3. Protection of information against unauthorized access between users and preventing
users from changing operating system functions
 A segment is a set of logically related instructions or data elements associated with a
given name.
 Segment may be generated by the programmer or by the operating System.
 The address generated by segmented program is called a logical address.
 The logical address may be larger than the physical memory address as in virtual
memory, but it may also be equal, and sometimes even smaller than the length of the
physical memory address.
Segmented –Page Mapping
The property of logical space is that it uses variable-length segments. The length of each
segment is allowed to grow and contract according to the needs of the program being
executed.
Translation Lookaside Buffer
• The mapping tables may be stored in two separate small memories or in main memory.
A memory reference from the CPU will require three access to memory.
1. One to fetch the page table
2. One to fetch the data
3. From main memory
• To overcome this problem a high-speed cache is set up for page table entries.
• Called a Translation Lookaside Buffer (TLB).
 • Contains page table entries that have been most recently used. • If page table entry is
present (TLB hit), the frame number is retrieved and the real address is formed.
• If page table entry is not found in the TLB (TLB miss), the page number is used to
index the process page table.
• First checks if page is already in main memory If not in main memory a page fault is
issued The TLB is updated to include the new page entry.
Numerical Example
 Consider the 20 bit logical address specified in Fig. (a).
 The 4 bit segment number specifies one of 16 possible segments.
 The 8 bit page number can specify up to 256 pages, and the b-bit word field implies a
page size of 256 words.
 The physical memory shown in Fig (b) consists of 220 words of 32 bit each.
 The 20 –bit address is divided into two fields: a 12-bit block number and an 8 bit
word number.
Thus, physical memory is divided into 4096 blocks of 256 words each

 Consider a program loaded into memory that requires five pages.

 The operating system may assign to this program segment 6 and pages 0 through 4, as
shown in Fig (a).
 the total logical address range for the program is from hexadecimal 60000 to 604FF.
 when the program is loaded into physical memory , it is distributed among five blocks
in physical memory where the operating system finds empty spaces.
 The correspondence between each memory block and logical page number is then
entered in a table as shown in Fig (b)

MEMORY PROTECTION
 Memory protection can be assigned to the physical address or the logical address.
 The protection of memory through the physical address can be each block done by
assigning to each block in memory a number of protection bits that indicate the type
of access allowed to its corresponding block.

The base address field gives the base of the page table address in segmented page
organization. Protecting the programs residing in memory
1. Full read and write privileges: no protection
2. Read only : write protection
3. Execute only : program protection
4. System only : operating system protection
Secondary Storage
Auxiliary Memory :
Magnetic Tape: Magnetic tapes are used for large computers like mainframe computers
where large volume of data is stored for a longer time. In PC also you can use tapes in the
form of cassettes. The cost of storing data in tapes is inexpensive. Tapes consist of
magnetic materials that store data permanently. It can be 12.5 mm to 25 mm wide plastic
film-type and 500 meter to 1200 meter long which is coated with magnetic material. The
deck is connected to the central processor and information is fed into or read from the
tape through the processor. It’s similar to cassette tape recorder.
Magnetic tape is an information storage medium consisting of a magnetisable coating on
a thin plastic strip. Nearly all recording tape is of this type, whether used for video with a
video cassette recorder, audio storage (reel-to-reel tape, compact audio cassette, digital
audio tape (DAT), digital linear tape (DLT) and other formats including 8-track
cartridges) or general purpose digital data storage using a computer (specialized tape
formats, as well as the above mentioned compact audio cassette, used with home
computers of the 1980s, and DAT, used for backup in workstation installations of the
1990s).
 Magneto-optical and optical tape storage products have been developed using many of
the same concepts as magnetic storage, but have achieved little commercial success.
Magnetic Disk: You might have seen the gramophone record, which is circular like a
disk and coated with magnetic material. Magnetic disks used in computer are made on the
same principle. It rotates with very high speed inside the computer drive. Data is stored
on both the surface of the disk. Magnetic disks are most popular for direct access storage
device. Each disk consists of a number of invisible concentric circles called tracks.
Information is recorded on tracks of a disk surface in the form of tiny magnetic spots. The
presence of a magnetic spot represents one bit and its absence represents zero bit. The
information stored in a disk can be read many times without affecting the stored data. So
the reading operation is non-destructive. But if you want to write a new data, then the
existing data is erased from the disk and new data is recorded. For Example-Floppy Disk.
The primary computer storage device. Like tape, it is magnetically recorded and can be
re-recorded over and over. Disks are rotating platters with a mechanical arm that moves a
read/write head between the outer and inner edges of the platter's surface. It can take as
long as one second to find a location on a floppy disk to as little as a couple of
milliseconds on a fast hard disk. See hard disk for more details.
The disk surface is divided into concentric tracks (circles within circles). The thinner the
tracks, the more storage. The data bits are recorded as tiny magnetic spots on the tracks.
The smaller the spot, the more bits per inch and the greater the storage.
Sectors
Tracks are further divided into sectors, which hold a block of data that is read or written
at one time; for example, READ SECTOR 782, WRITE SECTOR 5448. In order to
update the disk, one or more sectors are read into the computer, changed and written back
to disk. The operating system figures out how to fit data into these fixed spaces. Modern
disks have more sectors in the outer tracks than the inner ones because the outer radius of
the platter is greater than the inner radius
Optical Disk: With every new application and software there is greater demand for
memory capacity. It is the necessity to store large volume of data that has led to the
development of optical disk storage medium.
Optical disks can be divided into the following categories:
1. Compact Disk/ Read Only Memory (CD-ROM
2. Write Once, Read Many (WORM)
3. Erasable Optical Disk