Digital Logic And Computer Organization UNIT II 2.

0) Introduction
A computer is defined as an electronic data processing machine, which receives and stores a large volume of information in the form of symbols and digits and process them at high speed as per the instructions given and outputs the results with a predefined form.

2.1) Objectives
This chapter deals in detail about the basic structure, functional units, and operational concepts of a computer and memory management in computers. Basic Structure of a computer Software Operating System Memory Memory Organization Memory Unit Random Access Memory(RAM) CMOS Memory(Complementary Metal Oxide Semiconductor Memory) Serial Access Memory Cache Memory Virtual Memory Memory Management

2.2) Content
2.2.1. Basic Structure of a Computer Before a computer can perform any task, it has to be given a detailed set of instructions. This forms the INPUT based on which the computer will perform some PROCESS and gives the result as OUTPUT. This input-process-output (IPO) cycle is an essential concept for understanding the working of any computerized system. INPUT PROCESS OUTPUT The terms Hardware and Software are widely used in conjunction with computers. The hardware consists of the physical components and the software is the set of instructions that are needed to enable the hardware to perform a given set of tasks. The major hardware components of a computer are: Input Devices Output Devices

Page 46

Digital Logic And Computer Organization

Central Processing Unit (CPU)

Arithmetic & Logic Unit

Input Unit

Control Unit

Output Unit

Memory Unit

Figure 1.1: Organization of a computer Figure 4.1: Basic Organization of a computer 2.2.2. Functional Units The functional units of the computer can be divided into following: Input Unit Input Unit is that part of a computer through which the information is fed. The function of the input unit is to read the information contained in the program and transmit to the CPU. The media used for feeding any information may be of different forms depending on the facilities available and the requirements of the situation. To communicate with the computer an input device is needed, one such device is the keyboard. The data and the instruction required for the CPU are provided through the keyboard. The keyboard layout is similar to that of a typewriter with some additional keys. The additional keys are included to perform certain special functions such as loading programs, editing text or controlling the movement of the cursor (blinking indicator). They are classified as function keys, editing keys and cursor control keys. Each key when pressed produces an equivalent binary code, which is mapped into a table and the corresponding character is displayed based on the details in the table. Output Unit The output unit refers to the device used for the display of the processed results. The default output unit is the Monitor, which is also known as the Visual Display unit.

Page 47

Digital Logic And Computer Organization

Central Processing Unit (CPU) The CPU is the heart of the computer system. It links input and output devices. Internally, it consists of a Memory Unit, an Arithmetic Logic Unit and a Control Unit. Memory Unit The Memory Unit of the CPU is the section where the program and data are stored after they are read through the input unit. The primary Memory is the main storehouse of the computer. It stores programs, input values, output values and the intermediate results of processing. Control Unit The Control Unit co-ordinates the entire system. It has direct control over the input and output units. The Control unit controls and coordinates the working of the various units of the computer. It interprets the program instruction and directs the other components to suitably execute them. When a program is fed into the input unit the information is converted into the binary digits. It is then stored in the memory, which cannot be executed directly. It has to be translated into a machine language program, which is executed for processing. Arithmetic and Logic Unit If the processing requires any arithmetic calculation or logical (Comparison) operation to be carried out the control unit transfers data from the memory unit to arithmetic logical unit. The Arithmetic and Logic unit carries out the arithmetic operations such as multiplication, division, addition and subtraction, as well as logical comparison and the results obtained are supplied back to the memory where they are stored in separate location for future retrieval. 2.2.3. Basic operational Concepts To process the data and instructions, the computer needs to store them in some place. The primary memory is only a storage location. No Arithmetic or Logic operations can be done here. All the arithmetic and logic operations are done in the Arithmetic Logic Unit of the CPU, which contains the necessary circuitry (such as the full adder circuit) for these operations. The primary storage locations are identified by a unique address. The size of this storage location varies from computer to computer. Data and instructions are stored as charges in electronic components; the collection of such components and the associated circuitry is termed as memory or storage. Data and instructions are stored in memory in the binary form, the only form the computer understands. Data representation within the computer is in the form of 0s and 1s. These are called BITS, short form of Binary Digits. The 0

Page 48

Digital Logic And Computer Organization

corresponds to the OFF state and the 1 to the ON state. As unit if measurement it is classified as: 4 bits = 1 Nibble 8 bits = 1 Byte 1024 Bytes = 1 Kilobyte (210 bytes) 1024 Kilobytes = 1 Megabyte 1024 Megabytes = 1 Gigabyte Internal Data Operations The internal architecture of the computer determines how and what operations can be performed with the data. These operations are Storing data. Perform arithmetic and logic operations. Test for conditions. Sequence the execution of instructions. Store data temporarily during execution in the defined R/W memory locations. To perform these operations, the computer requires registers, an arithmetic logic unit (ALU) and control logic and internal buses (paths for information flow). 2.2.4. Bus Structures The processor internally performs primarily four operations: 1. 2. 3. 4. Memory Read: Read data from memory. Memory Write: Writes data into memory. I/O Read: Accepts data from input devices. I/O Write: Sends data to output devices.

All these operations are part of the communication process between the processor and peripheral devices (including memory). To communicate with a peripheral (or a memory location), the processor needs to perform the following steps: Step 1: Identify the peripheral or the memory location (with its address). Step 2: Transfer data. Step 3: Provide timing or synchronization signals. The processor performs these functions using sets of communication lines called buses. There are three types of buses namely: the address bus, the data bus and the control bus. Address Bus The address bus is a group of sixteen lines generally identified as A0 to A15. The address bus is unidirectional: bits flow in one direction from the processor to peripheral

Page 49

Digital Logic And Computer Organization

devices. The processor uses the address bus to perform the first function: identifying a peripheral or a memory location. In a computer system, each peripheral or memory location is identified with a binary number, called an address and the address bus is used to carry a 16-bit address. The number of address lines of the processor determines its capacity to identify different memory locations (or peripherals). The processor with its sixteen address lines is capable of addressing 216 = 65536 (generally known as 64K) memory locations. Generally 1K memory is determined by rounding off 1024 to the nearest thousand; similarly, 65536 is rounded off to 64000 as a multiple of 1K. Most 8-bit microprocessors have sixteen address lines. The number of address lines is arbitrary; it is determined by the designer of a microprocessor based on such considerations as availability of pins and intended applications of the processor. For example, the MOS Technology MCS 6515 microprocessor has twelve address lines and is capable of addressing 4K (212 = 4096) memory. Another example is the Motorola 68000, which has 23 address lines.

Figure 4.2: The Bus Structure Data Bus The data bus is a group of eight lines used for data flow. These lines are bidirectional data flow in both directions between the processor and peripheral devices. The processor uses the data bus to perform the second function: transferring data. The eight data lines enable the processor to manipulate 8-bit data ranging from 00 to FF (28 = 256 numbers). The largest number that can appear on the data bus is 11111111 (25510). The data bus determines the word length and the register size of a microprocessor; thus the 8085/8080A microprocessor is called an 8-bit microprocessor. Microprocessors such as the Intel 8086, Zilog Z8000 and Motorola 68000 have sixteen data lines; thus they are known as 16-bit microprocessors. Page 50

Digital Logic And Computer Organization

Control Bus The control bus is comprised of various single lines that carry synchronization signals. The processor uses such lines to perform the third function: providing timing signals. These are individual lines that provide a pulse to indicate the processors operation. The processor generates specific control signals for every operation (such as Memory Read or I/O Write) it performs. These signals are used to identify a device type with which the processor intends to communicate.

Figure 4.3: Memory Read Operation To communicate with a memory for example, to read an instruction from a memory location the processor places the 16-bit address on the address bus. The address on the bus is decoded by an external logic circuit and the memory location is identified. The processor sends a pulse called Memory Read as the control signal. The pulse activates the memory chip and the contents of the memory location (8-bit data) are placed on the data bus and brought inside the microprocessor. Bus protocols For each bus there is a standard, which defines how devices communicate on the wires. On some systems the address and data signals may be multiplexed onto the same physical lines. Standard System Busses are: Page 51

Digital Logic And Computer Organization

ISA/EISA NuBus VMEBus SBUS PCI Bus Bus Bandwidth The maximum rate at which information can be transmitted on a bus can be calculated by considering the width of the bus in bytes and the minimum amount of time needed to transfer each packet. For example, PCI bus is 32bits wide with a clock rate of 33MHz and can transfer one word on every cycle. Therefore peak bandwidth = 132MB/sec. Techniques for increasing bus bandwidth are to have separate address and data signals and allow Block transfers, that is, multiple words can be transferred in one operation rather than multiple, separate read/write operations. Bus arbitration In some systems (e.g. multiprocessors) it is possible to have multiple devices on the bus at the same time that may want to generate read and write operations to I/O devices. In these situations it is essential to have a scheme to decide who should be granted control of the bus. Issues in Bus Arbitration are: Fairness - Ensuring that no device is unfairly excluded from bus access. Priority - Allowing high priority bus masters preferential access to the wires. Device Drivers Most operating systems have specialized code for handling the task of interfacing to I/O devices. These programs are called device drivers. User programs must access the I/O devices through the drivers rather than explicitly accessing the device ports themselves. Bus Configuration The device drivers locate the addresses of the I/O devices on the system by two methods: The IO addresses of some devices are hardcoded into the programs. The bus self configures at boot time and the Operating system figures out where the addresses reside and informs the device drivers.

Page 52

Digital Logic And Computer Organization

Bus Adapters Many systems are organized with a hierarchy of buses to support various types of devices. The interface between various types of system busses is handled with bus adapter units. 2.2.5. Software Software is a program or set of instruction, which is required to use the computer. Many types of software are available for various applications. The software development field is so advanced that day-by-day existing software are becoming outdated as new software are coming in the market. Softwares are broadly classified into two types namely System Software and Application Software. These two types of software are discussed below: System Software Software that is required to control the working of hardware and aid in effective execution of a general user's applications are called System Software. This software performs a variety of functions like file editing, storage management, resource accounting, I/O management, database management etc. Some of the examples of system software are DOS (Disk Operating System, Windows, BASIC, COBOL and PC Tools). This is developed by System Programmers. System Software can be further categorized into the following three types. System Management Software (Operating System, Operating Environments) System Development Software (Language Translators, Application Generators, CASE Tools) System Software Utilities System Management Software The System Management software, which involves operating system, is discussed in detail in section 1.6. System Development Software The System Development Software are discussed below. Language Translators: Language Translators are categorized into three types. Assemblers: Assemblers translate the Assembly language code (source program) into Machine language code (object program). After assembling, a linker program is used to convert the object program into an executable program. The Microsoft assembler

Page 53

Digital Logic And Computer Organization

program (MASM) and Borland Turbo assembler program (TASM) are two popular assemblers. Interpreters: Instructions of a high level language are coded in many statements. At the time of their execution, they are converted statement by statement into machine code, by using system software, called interpreters. For example, programs written in BASIC language are executed by using BASICA or QWBASIC. Interpreters programs written in some fourth generation languages, like dBASE III plus are also executed using dBASE interpreter. Compilers: In contrast to interpreters, compilers provide faster execution speed. Compilers do not translate and execute the instructions at the same time. They translate the entire program (source code) into machine code (object code) using linker; the object code is converted into executable code. Compilers are widely used in translating codes of high level languages (e.g. COBOL, FORTRAN, PASCAL, etc) and fourth generation languages (dBASE IV, Foxpro etc). As compared to interpreters or assemblers, compilers are preferred in development of application software. System Software Utilities System Software Utilities support the operation of a computer. They provide many features including file management capabilities, data compression, diagnostic routines, virus detection and removal, text editing, performance, monitoring and spooling. Some of the important types of utilities are discussed below. File Management Utilities: These utilities provide file management capabilities like copying, comparing, searching, listing and sorting the files. Although these features are offered by many operating systems, utility programs provide better user-friendly environment along with some additional features. NORTON utilities and PC Tools are the most commonly used file management utilities. Data Compression Utilities: These utilities compress or decompress files that are stored on floppy and hard disks. As compressed files take up very less space on disks, data compression utilities are widely used during copying of data from hard disks to floppy disks. PKZIP/PKUNZIP programs are commonly used examples of data compression utilities. Diagnostic Utilities: These utilities can detect bugs (errors in hardware/software) in computers. For instance, the problem of floppy and hard disks can easily be detected by a popular utility program called Norton Disk Doctor (NDD). QAplus and Disk Manager (DM) are other examples of utilities that can detect and remove any bugs in storage devices, software and other components of computers.

Page 54

Digital Logic And Computer Organization

Text Editing Utilities: These utilities are used to create, edit and print the non-document texts such as programs, data etc. Norton Editor (NE) is the most common example of text editor. Most operating systems, including DOS, also has in-built text editor program. Spooling Utilities: In multi-user/networking environment, the input and output devices are generally slow. In such an environment, the processing of computer is also slowed down. To control the computer from being showed down, the spooling programs are used. Spooling (Simultaneous Peripheral Operations Online) program is used to buffer data for the printer and remote batch terminals. This program sends the output to the disk and printer does not interact with CPU during printing. Spooling utilities are used mainly in computer systems with multi-user/networking environment. Application Software Whenever an organization purchases computers, besides an operating system certain application softwares are also required to be purchased. This software is needed for general purpose like word processing, database management, spreadsheets etc which are known as Application Software. Some of the importance of different application software is given below: Word Processor Packages Word processors are application software which are used for word processing. Word processing is the most widely used technique for typing, editing, storing, formatting, manipulating and printing documents with the assistance of a computer and printer. It is the most efficient means of generating documents electronically. Database Management Packages A Database is a logical term used to refer to a collection of organized and related information. A Database Management System is a system that allows you to access the data in a Database. In any Business, certain piece of information about Customer, Product, Price and so on are called database. Shortly Data Base Management System is defined as software that organizes and maintains the data in a database for providing the information. Spreadsheet Packages Business applications require a lot of calculation work. In a manual system, it is done on a sheet of paper with rows and columns, which are called a 'spreadsheet'. Spreadsheet packages use the concept of an electronic spreadsheet. An electronic spreadsheet is a very big sheet consisting of thousands of rows and columns which are used to store information in the memory of a computer. Like databases, electronic spreadsheets have now become an essential tool in developing a computerized management information system.

Page 55

Digital Logic And Computer Organization

Office Automation Packages Word processors, spreadsheets and Database Management Packages are generally called office Automation Packages/Software Tools or office suites. MS Office and Lotus SmartSuite are two most popular examples of office Automation Packages. Microsoft office (MS-Office) Professional is a package that contains five powerful general-purpose application packages. It includes Word, Excel, PowerPoint, Access and Mail. Lotus Smart Suite is another popular office Automation package that contains five powerful application packages. It includes word Pro, Lotus 1-2-3, Freelance Graphics, Approach and Organizer. Corel Office, an office suite contains Word Perfect, Quattra Pro, Paradox, Corel Draw, Netscape Navigator, Presentations, Corel Flow, Sidekick and other application packages. Sidekick is the first popup program (TSR- 'Terminate and Stay Resident' in memory) used for editing programs and non-document files. Operating System Operating system is a set of programs, which provides an easy to use interface between the users and the computer system and manages the computer resources in order to achieve a maximum efficiency of the computer system. An operating system is a part of the system software and has become an integral part of a computer system. In short, an operating system acts as a manager of both hardware and software resources of a computer system and facilitates the execution of application programs. Thus, an operating system is computer software that controls the hardware, manages the system, resources and executes the programs in response to users commands. The software resources of a computer system include compilers, assemblers, loaders, linkers etc and it is the operating system that makes these resources available to an application program. These software resources are complex programs supplied by the manufacturer and are a part of the system software. The operating system is also a part of the system software and consists of programs, also called routines. An operating system contains I/O routines, memory management routines, scheduling routines, command interpreter routines and routines to invoke other programs of the system software as and when required by an application program. Another important program included in an operating system is an EDITOR, which enables the user create and edit the application programs. Now, if an application program requires the use of the computer system resources, it has to communicate its requirement of resources to the operating system, which provides these resources to the application program.

Page 56

Digital Logic And Computer Organization

2.2.6. Memory The memory unit is called by different names such as storage, internal storage or main memory. A memory or store is required in a computer to store programs and the data processed by programs. A memory is made up of a large number of cells, with each cell capable of storing one bit. The cells may be organized as a set of addressable words, each word storing a sequence of bits. Various memory organizations can be classified on the basis of their storage capacity, the method of storing and retrieving data, the time needed to store and retrieve data and the cost per bit of storage. As the speed of data retrieval increases, the cost per cell also goes up. In a computer system, a hierarchy of storage systems is provided. At the top of the hierarchy is a very high-speed, high-cost, low-capacity memory and at the bottom a lowspeed, low-cost, high-capacity memory. The speed and capacities at various levels are chosen so that for a given budget one gets a well-balanced system which meets application requirements. Logical View From logical point of view, memory is just an array of words where information can be stored. Each location has a unique address. The logical view of memory hierarchy is cache - primary memory - secondary memory. Physical Structure Most of memory holds multiple banks of memory chips. There are two ways to organize memory banks. high-order interleave: using leading bits of memory address to identify memory banks. low-order interleave: using trailing bits of memory address to identify memory banks. For example, in a 2-MB memory system, 16 of 256-K 4-bit memory unit is used. For each of the memory bank, 18 address lines are needed, another three is needed for selecting eight banks. So the total number of address lines is 21. When it is high-order interleave, each bank has consecutive addresses. In this case, it is easy to do concurrent processing (multiple functional units can access different bank of memory at the same time). When it is low-order interleave, consecutive addresses are in alternative banks, so each device will need to access all four banks. Low-order interleave is useful when the memory cycle is significantly longer than the CPU cycle. If CPU were much faster than memory and a high-order interleave is used, then for consecutive memory access, the CPU would have to wait until the previous memory access complete. If low-order interleave is used, then consecutive memory locations are in different banks and they can be accessed at the same time.

Page 57

Digital Logic And Computer Organization

Memory Cell Cells used to fabricate a random access memory are made (in current technology) with semiconductor flip-flops. Cells used in serial access memories of large size (tens of megabytes) are magnetic dipoles on movable magnetizable surfaces. Magnetic surface recording itself may be organized in different configurations such as hard disks, floppy disks and tapes. A memory cell may be defined as a device which can store a symbol selected from a set of symbols and may be characterized by the following properties: The number of stable states in which it can be placed. Whether a cell can store a symbol indefinitely even when power is turned off. Whether, after reading a symbol from a cell, the stored symbol is retained in the cell or disturbed. The time taken to read a symbol from a cell and the time to write a new symbol in it. Whether a symbol, once written, can only be read and not changed. The number of stable states in which a cell can be placed determines the number of distinct symbols it can store. Each stable state may be assigned to represent a symbol. Thus if a cell be placed in ten stable states, each state may be used to represent one symbol and so the cell can store a decimal digit. If a cell can be placed in only one out of two stable states, then it may be used to store a binary digit. If a symbol can be stored in a cell indefinitely without continuous supply or energy, it is known as a non-volatile cell. On the other hand, if the symbol stored in a cell disappears when no energy is supplied, it is known as a volatile cell. Normally, reading a symbol from a cell should leave it undisturbed. Such a cell is known as one where readout is non-destructive. If the symbol is erased, as a consequence of reading, the readout is said to be destructive. The time taken to read a symbol from a cell is called read-time and the time taken to write a symbol write-time. If in a memory cell, information is permanently written and can only be read, then it is known as a read-only cell. 2.2.7. Memory Organization Memory cells fabricated using current technology can be placed in one out of two stable states. These cells are called binary cells and each cell can store a binary digit. One of the two stable states is used to represent the binary 0 and the other the binary 1. Figure 4.4 depicts a storage cell. The cell has an input data line on which the symbol to be written is sent to the cell. In order to write this symbol in the cell, a write-control signal is sent to the cell via the write-line. If the content of a cell is to be read, a read-control signal is sent on the read-line and the content of the cell may be sensed on the output data line.

Page 58

Digital Logic And Computer Organization

Figure 4.4: Storage cell By appropriate variation in the interconnection of binary memory cell it is possible to organize different types of memories. The individual cells are non-volatile and reading is non-destructive. The simplest organization of a set of cells is shown in Figure 4.5. In this organization, three cells are interconnected in such a way that the write-control lines of all the cells are connected together. The read-control lines are also connected together. The bits to be written in each cell is fed to the appropriate input data lines. When the write-signal is applied to the write-control line, these bits are written in the individual cells. The previous content in cells are automatically erased when the new information is written. In order to read the contents of the cells, a read signal is applied to the common read-line. The contents of the cells appear on the respective output data lines. The contents of individual cells are not erased by the read-operation as reading from these cells is assumed to be non-destructive. This interconnection of cells is called a register. This register stores three bits.

Figure 4.5: 3-Bit Register A group of registers may be interconnected to form a memory. Consider a memory that stores four words of three bits each. In this organization, the input data lines of the first bit of all four register are connected together. Similarly, the input data lines of the second bits are connected together and those of the third are also connected together The output lines of each of the bits of the registers are also connected together. Thus there are four Page 59

Digital Logic And Computer Organization

write-lines, one for each 3-bit register and four read-lines. In order to write data in this memory, the register in which the data is to be written is specified. If data is to be written in the second register, a signal is sent on the write-line of this register. The data to be written is placed on the input lines. Each of the four registers has one read-line and one write-line. At a time it is possible to either read from or write in a register. Each register in the memory should have a unique identification so that the appropriate register may be selected for writing or reading. Each pair of read/write lines corresponding to a register are identified by the binary code 00,01,10 and 11. The identification code of each register corresponding to a word in the memory is known as its address. If a memory has eight words, the binary codes 000, 001,010,011,100,101,110 and 111 will uniquely address these lines. In order to select an appropriate word in a memory, for either reading or writing, it is necessary to specify the address of the word. This address is usually specified as a binary number and is placed in a register called a memory address register (abbreviated MAR). A selector circuit is connected to MAR which selects the appropriate read or write-control line based on the contents of MAR and on whether read or write is specified. The data read from the memory or that to be written in the memory is placed in a register called a memory data register (abbreviated MDR). This register receives the outputs of read-lines during read operation. For write-operation, the data to be stored in the memory is placed in this register. In practice the number of bits stored in memories is much larger than that shown in this example. The block diagram of a memory, which is capable of storing 64KB is shown in Figure 4.6. Observe that 64K = 216. Thus the number of bits in MAR is 16. The memory will be made up of 64K words with each word storing eight bits, that is one byte. The MDR will be an 8-bit register. The selector block in Figure 4.6 will select a read or writeline corresponding to the word to be read or written. Observe that the address of the word to be read or written will be placed in MAR. The data read from the memory will be placed in MDR.

Figure 4.6: Block diagram of 64 KB memory

Page 60

Digital Logic And Computer Organization

If the number 173 = (10101101)2 = (AD)16 is to be written in the memory in address (1111110101011010)2 = (FD5A)16 then the number (AD)16 is entered in MDR and the address (FD5A)16 in MAR. The write signal is initiated. The number in MDR, namely, (AD)16 will be written in location (FD5A)16 replacing the data in that location. In order to read the contents of a word whose address is (AB34)16, this address (1010101100110100)2 is placed in MAR. A read-signal is initiated. A copy of the data stored in (AB34)16 is retrieved and placed in MDR. If the cells used in the memory are destructive-readout then the contents in the specified address will be cleared to zero. In this case, whatever is read from the memory would, however, be available in MDR to be written back in the memory.

Figure 4.7: Defining access time and write time in a memory Assume that at time t0 the address from which data is to be retrieved is placed in MAR and at time the t1 required data is available in MDR. The elapsed time (t1 - t0) is known as the access time of the memory. The access time is usually slightly larger than the readtime of individual cells in the memory. If data is to be written in the memory, the data is placed in MDR and the address in MAR at time t2 and a write-signal is initiated. If the writing operation is completed at time t3 then the elapsed time (t3 - t2) is called the write time.

Page 61

Digital Logic And Computer Organization

2.2.8. Memory Unit Memory unit is that component of a computer system, which is used to store the data, instructions and information before, during and after processing by ALU. It is actually a work area (physically a collection of integrated circuits) within the computer, where the CPU stores the data and instructions. It is also known as a Main/Primary/Internal Memory. It is of the following three types. Read Only Memory (ROM) Random Access Memory (RAM) Complementary Metal Oxide Semiconductor Memory (CMOS) Read Only Memory Read Only Memory is an essential component of the memory unit. The computer has no intelligence or memory and requires instructions, which are given by the user. Whenever the computer is switched on, it searches for the required instructions. The memory, which has these essential instructions, is known as Read Only Memory (ROM). The memory is permanent and is not erased when the system is switched off. ROM contains a number of programs (set of instructions). The most important program of ROM is the Basic Input Output System (BIOS), which activates the hardware such as keyboard, monitor, floppy disk etc in communicating with the system and application software. Types of ROM There are many types of ROM available for microcomputers like Mask ROM, PROM, EPROM, EEPROM and EAPROM. Mask ROM: Mask ROM is the basic ROM chip. In this type of ROM, the information is stored at the time of its manufacturing. PROM: PROM stands for the Programmable Read Only Memory and information is stored by programmers after its manufacturing. It also cannot be altered or erased later on. EPROM: EPROM stands for Erasable Programmable Read Only Memory. It is similar to PROM, but its information can be erased later on by ultra violet and it can be reprogrammed. EEPROM: EEPROM stands for Electrical Erasable Programmable Read Only Memory. It is similar to EPROM, but its information can be erased by using a high voltage current. EAPROM: EAPROM stands for Electrically Alterable Read Only Memory. Information stored in EAPROM can be altered later.

Page 62

Digital Logic And Computer Organization

Random Access Memory (RAM) Random Access Memory (RAM) is another important component of the Memory Unit. It is used to store data and instructions during the execution of programs. Contrary to ROM, RAM is temporary and is erased when the computer is switched off. RAM is a read/write type of memory and that can be read and written by the user/programmer. As it is possible to randomly use any location of this memory it is known as Random Access Memory. Types of RAM There are two types of RAM used in PCs - Dynamic and Static RAM. Dynamic RAM (DRAM): The information stored in Dynamic RAM has to be refreshed every few milliseconds, otherwise it is erased. DRAM has a higher storage capacity and is cheaper than static RAM. Static RAM (SRAM): The information stored on Static RAM need not be refreshed, but it remains stable as long as power supply is provided. SRAM is costlier but has higher speed than DRAM. Complementary Metal Oxide Semiconductor Memory Complementary Metal Oxide Semiconductor (CMOS) Memory is used to store the system configuration, date, time and other important data. When the computer is switched on, BIOS matches the information of CMOS with the peripheral devices and displays error in case of mismatching. There are RAMs in which data words are permanently written during fabrication. A word can later be read from the memory by specifying its address. The contents of the word cannot, however, be altered. Such a memory is called a ROM. Reading from a ROM should be non-destructive. The memory also should be non-volatile. An important application of a ROM is to store tables, which do not change. Code conversion is another important application. If the ASCII code of a character is placed in the MAR of the ROM which has information written in it, during manufacture in a factory, is known as a factory programmed ROM. Such factory programming is feasible only in cases where the demand for such programmed ROMs is large. Example cited above would be suitable for factory programming. For more specialised uses where a user may like to store his own special functions or program, it is preferable to fabricate a ROM on which a user can write these. Such ROMs are available and are called Programmable ROM(PROM). Programming is normally done using special writing circuits. In such a case the time taken to write information is long, but the read-time will be relatively small.

Page 63

Digital Logic And Computer Organization

PROM is not a flexible memory as the information in it cannot be altered. There are applications where one may like to store a program in a ROM which would normally not change but under some unforeseen conditions one may like to alter it. Erasable and reprogrammable ROMs have been fabricated to meet this requirement. Information in such a ROM is erased by shining strong ultra-violet light through a window. After the ROM is exposed to ultra-violet light all bits are erased and become 0. The following chart summarizes all the information.
Memory

Read-Write

Read-Only

ROM

PROM

EPROM

EAPROM

Figure 4.8: Memory classification Serial Access Memory Consider the organization of memory cells shown in figure 4.9. In this organization the output of a cell is the input to the next cell. A read-signal places the contents of each of the cells on the respective output lines. A write-signal following this read-signal will store these bits in the respective next cells. One read-write pair of signals would thus shift the contents of the cells right by one cell position and the bit stored in the rightmost cell appear on the output line. A sequence of read-write signals will serially shift the contents of the register. After three read-write (namely, shift) signals the output will be 0. As the bits stored in the cells appear serially (that is one after another) at the output, this memory is called a serial access memory. If the output of the shift register is connected to its input, each shift-signal will circularly shift the contents of the memory. A series of shift-signals will keep the contents of the memory circulating.
Read
0 Input

Output

Write Read Input

After one Read/Write Cycle 0 1

Output =1 Write

Figure 4.9: A serial access memory

Page 64

Digital Logic And Computer Organization

2.2.9. Cache Memory When CPU access a piece of information in memory, there is a high possibility that this data will be accessed again. Rather than bringing this from memory all the time, it is saved in a special, high-speed, on chip memory for CPU to use it later. This is called temporal locality or cache. When a piece of data is accessed, it is also very likely that the data in nearby memory location will be accessed. This is called spatial locality. Each cache consists of a number of cache entries. Each cache entry consists of two parts: some cache memory and an address tag which specifies memory location of the cache entry. If a piece of information that CPU needs to access is found in cache, it is said a cache hit; otherwise it is a cache miss. The contents of a cache entry will stay in cache memory until a write instruction is received. Cache structure and organization Every cache has two sub-systems, a tag subsystem which holds the memory addresses and determines whether there is a match for a requested datum; a memory subsystem which holds and delivers the data. Both memory and cache are divided into refill lines. Refill lines are the unit of data transfer. Size of refill lines are all equal and generally contain n words, where n is a power of 2. Typical cache refill lines have between 4 and 64 bytes. The reason to have this refill line instead of accessing each individual word is to make use of spatial locality Cache memory uses different mapping techniques for mapping main memory addresses into its own local addresses. Associative cache: memory address is held in tag; all the tags have to be searched through to find an element; the memory content can be put an any line of cache Direct mapped cache: partitions main memory into K columns of N refill lines per column. When ith line in kth column is needed from memory, it will check the ith line in cache first, if it is kth column and it is valid, then use it, otherwise, bring it from memory to cache. It is a fixed mapping. Set associative cache: it is a hybrid of the two. Main memory is divided into regions. Line of memory can go to any cache lines in that block. Sector-mapped cache: memory and cache are both divided into equal-size sectors. Any memory sector can be mapped into any cache sector. Inside a sector, tag memory uses validity bits to indicate which memory units are in use and which are not. How does cache operate? When a read request is received, the cache is checked first to see if the entry is there. If it is there, it is a hit and process is finished. If it is not there, a memory read is issued and the information is brought into cache. When a write request is received, different approaches can be taken.

Page 65

Digital Logic And Computer Organization

write-through: The information is written to both memory and cache write-back: The information is written to cache only. The modified cache block is written to main memory only when instructed to do so (e.g. being replaced or process terminates). A dirty bit has to be used here to indicate that the entry in cache is different from the one in main memory. 2.2.10. Virtual Memory The interface between a cache memory and main memory is almost always managed by hardware, but the interface between main memory and backing storage is usually largely in software.This was done by allowing to execute program, which is not entirely in the main memory. It is done by introducing the concept of virtual memory. Virtual memory is the kind of secondary storage that is specially treated by OS. Virtual memory provides another interface between logical and physical addresses. The part of code, currently executed is still to be placed into main memory, but the whole process can reside in virtual memory. From user point of view virtual/physical memory are indistinguishable. It is OS task to provide mapping between logical and physical addresses and ensure bringing needed parts of process into main memory. This approach is more complicated, but has definite benefits: Almost no constraints on program size. The degree of multiprogramming is almost unlimited. CPU utilization increases. Less swapping is needed to start/run process so, each program runs faster. Virtual memory can be implemented through demand segmentation or demand paging. In a virtual memory system, the overlay management is moved from the programmer to the operating system and the hardware . Segmentation In addition to the sizes of the primary and secondary memory devices, three key questions must be answered to obtain a complete description of any virtual memory system. The first of these is: What are the units of transfer between main memory and the backing storage device? This has two common answers, pages or fixed size blocks of information and segments or variable sized blocks. Typically, the page size used in a virtual memory system is a small multiple of the sector size of the backing storage device. When segments are used, each segment is typically a logical unit such as the code for a procedure or a particular data object. The second question is: What causes a transfer from backing storage to main memory? Demand transfers are those which are initiated by an attempt of a program to access a page or segment which is not currently in main memory, while anticipatory transfers are

Page 66

Digital Logic And Computer Organization

those made by the system in anticipation of a user demand. Some systems also allow a user program to request a transfer in anticipation of a specific later need. The final question is: What policy is used to select objects in main memory which are to be moved back to the backing store when the space they occupy is needed for other pages or segments? There are a number of replacement policies, ranging from random replacement to least-recently used replacement. The choice of an appropriate replacement policy is one of the key variables determining the performance of a virtual memory system, since the premature replacement of a page or segment which is still being used can significantly slow the system. Paging When the virtual address space is broken up into pages, the term page frames or just frames is conventionally used to refer to the areas in main memory which may hold pages and the term may also be used to refer to locations in secondary memory (disk) that hold pages, particularly if the page size is not one sector and if pages may move from one disk address to another during the life of a program.
L o g ic a l a d d re s s P h y s ic a l a d d re s s

C P U

P h y s ic a l m e m o r y

p f

p a g e t a b le

Figure 4.10: Paging Hardware The hardware support for paging is illustrated in Figure 4.10. Every address generated by the CPU is divided into two parts: a page number (p) and a page offset (d). The page number is used as an index into a page table. The page table contains the base address of each page in physical memory. This base address is combined with the page offset to define the physical memory address that is sent to the memory unit. The paging model of memory is shown in Figure 4.11. The page size (like the frame size) is defined by the hardware. The size of a page is typically a power of 2 varying between 512 bytes and 8192 bytes per page, depending on the computer architecture. The selection of a power of 2 as a page size makes the

Page 67

Digital Logic And Computer Organization

translation of a logic address into a page number and page offset particularly easy. If the size of logical address space is 2m and a page size is 2n addressing units (bytes or words), then the high-order m-n bits of a logical address designate the page number and the n low-order bits designate the page offset. Thus, the logical address is as follows: Page number Page offset

P d m-n n Where p is an index into the page table and d is the displacement within the page. When we use a paging scheme, we have no external fragmentation: Any free frame can be allocated to a process that needs it. However, we may have some internal fragmentation. If Process size is independent of page size, we expect internal fragmentation to average one-half page per process. This consideration suggests that small page sizes are desirable. However, there is quite a bit of overhead involved in each page-table entry and this overhead is reduced as the size of the pages increase. Also, disk I/O is more efficient when the number of data being transferred is larger. frame numbers
page 0 page 1 page 2 page 3

0 1

1 4

0
page 0

1
3

2
7

2
page 2

3 page tables

3
page 1

logical memory

4 5
page 3

6 7 physical memory Figure 4.11: Paging model of logical and physical memory

Page 68

Digital Logic And Computer Organization

When a process arrives in the system to be executed, its size, expressed in pages, is examined. Each page of the process needs one frame. Thus, if the process requires n pages, there must be at least n frames available in memory. If there are n frames available, they are allocated to this arriving process. The first page of the process is loaded into one of the allocated frames and the frame number is put in the page table for this process. The next page is loaded into another frame and its frame number is put into the page table and so on. When a user attempts to address a page or segment which is not currently in some frame in main memory, that event is called a page fault. The term segment fault can be defined similarly, but there is nothing corresponding to a 'segment frame' because there is no standard segment size. Most modern systems combine paging and segmenting; thus, each segment consists of one or more pages. This is particularly useful when the maximum size of a segment is such that bringing an entire segment into main memory would be difficult. A second advantage of this is that it eliminates the need to allocate variable sized blocks of main memory to hold entire segments. When paging and segmenting are combined, the virtual address issued by a user program consists of a segment number and an integer offset within that segment and the system interprets the offset as consisting of two fields, the first giving the page number within that segment and the second giving the desired word in that page, as shown in Figure 4.12. segment number view ____________ |____________| segment number system view or address --- user view _______________________________________________ ____ |_______________|_______________| ___________________| segment number system view page number address within page --address within segment --- user

_______________________________ |___________|___________________| page number address within page ---

Figure 4.12: Paged, segmented virtual addresses Paging versus Segmenting

Page 69

Digital Logic And Computer Organization

The hardware being used largely determines whether a virtual memory system uses paging or segmenting. If virtual memory is to be used, the hardware must provide some facilities for translating virtual addresses. This address translation hardware is responsible for detecting attempts by a program to access objects which are currently on secondary memory and it isolates programs from any knowledge of the physical addresses actually being used to store objects in main memory. When segmented memory is used, each memory address issued by the user program must consist of the identity of a segment and the offset of the desired item within that segment, as shown in Figure 4.13. segment number segment address within

____________ ____________________ |____________| | ____________________| Figure 4.13: A segmented virtual address When paged memory is used, each memory address issued by the user program is typically interpreted as a single integer by that program, but the hardware breaks the address into two fields. The most significant field is the page number, while the least significant field is the word (or byte) number within that page, as is shown in Figure 4.14. address --- user view _______________________________ |___________|___________________| page number system view address within page ---

Figure 4.14: A paged virtual address For example, a 16 bit virtual address may be broken into an 8-bit page number, selecting one of 256 addressable pages and an 8-bit specification of the byte desired from that page. Unlike segments, pages are all of the same size and user data and program structures are usually placed in memory without regard to how those structures are broken up into pages. Independently of whether paged or segmented memory is used, it is conventional to refer to pages and segments as components of the user's address space, as opposed to referring to them as units of storage in memory or on disk. Thus, a particular page or segment may reside in main memory at some times and on disk at other times. The place where the segment is stored does not change its identity and the segment may be moved from one place to another many times during the execution of a program. 2.2.11. Memory Management

Page 70

Digital Logic And Computer Organization

When applications begin to be loaded into memory, they are loaded in block sizes determined by the operating system. If the block size is 2 KB then every process that is loaded will be given a chunk of memory that is a multiple of 2 kilobytes in size. Applications will be loaded in these fixed block sizes, These blocks and boundaries help to ensure that applications will not be loaded on top of one another's space. In most computers it is possible to add memory beyond the original capacity. A processor can only access memory one location at a time, so the vast majority of RAM is unused at any moment. Since disk space is cheap compared to RAM, then moving information in RAM to hard disk intelligently can greatly expand RAM space at no cost. This technique is called Virtual Memory Management. Multiple Partitions In order to be executed each process is to be brought to the physical (main) memory. First approach is to bring the whole process in using swapping. This approach has several limitations: Program size is limited to at most size of memory If process uses space for data, the limit is even smaller: the programmer/user should be aware of both memory size and possible size of data The degree of multiprogramming is limited by size of memory divided by average size of process Fragmentation makes actual degree of multiprogramming even smaller CPU/device usage is affected by fragmentation Disk storage is only one of the memory types that must be managed by the operating system and is the slowest. Ranked in order of speed, the memory in a computer system is: High-speed cache -- This is fast, relatively small amounts of memory that are available to the CPU through the fastest connections. Cache controllers predict which pieces of data the CPU will need next and pull it from main memory into high-speed cache to speed system performance. Main memory --The RAM that is measured in megabytes in a computer. Secondary memory --This is most often some sort of rotating magnetic storage that keeps applications and data available to be used and serves as virtual RAM under the control of the operating system. The operating system must balance the needs of the various processes with the availability of the different types of memory, moving data in blocks called pages between available memory as the schedule of processes dictates.

Page 71

Digital Logic And Computer Organization

Virtual memory can be implemented through demand segmentation or demand paging. In a virtual memory system, the overlay management is moved from the programmer to the operating system and the hardware Overlay and Protection Overlays is when a single program is running in memory, parts of the program can be overlayed. The memory system would have to provide an overlay address register for efficient execution. When multiple programs are allowed in memory, one possible solution is to allocate memory as needed and do garbage collection later. This type of solutions require relocation. If relocation is to be supported, the hardware would have to provide relocation hardware and memory protection hardware. When multi-programming is allowed, memory protection among different programs becomes tricky. Most of the time, software (such as operating systems) is used to provide such service. Memory Design Issues Memory Speed vs. CPU Speed: High speed memories are available at lower price, so more high speed memory can be used to build large cache, multiple register sets, large stores of microprograms. Both memory and CPU are getting faster. From 60s to 80s, they increase at about the same rate (memory is about 10 times slower than CPU). Lately, CPU speed increases at a faster speed. This is due to such technologies as pipeline. Users keep requesting larger and larger memory. Structural wise, memory technology has not had a fundamental changes. The speed gap increases. Memory address space: The amount of memory available to a computer is increasing at a very high speed. In the 60s when IBM introduced System/360, its 24-bit address space seemed huge, just as the 32 bits in the early 80s. Speed-cost tradeoffs: Slow, inexpensive devices for main memory Fast device for cache Very fast, expensive devices for registers and control store

Page 72

Digital Logic And Computer Organization

2.3) Revision Points

Comparison between serial and random access memories Sr. Serial Access Memories Random Memories No. 1. Use serial access method Use random access method. 2. Memory is recognized into units of daa, called Each storage location in the memory has records. Records are accessed sequentially. If an unique address and it can be accessed current record is 1, then in order to read record N, independently of the other locations. it is necessary to read physical records 1 through n-1 3. Memory access time is dependent on the position Memory access time is independent of of storage location storage location being accessed 4. The time required to bring the desired location Memory access time is less into correspondence with a read-write head increses effective access time, so serial access tends to be slower than random access. 5. Cheaper than random access memories Random access memories are comparatively costly 6. Nonvolatile memories May be volatile or nonvolatile depending on physical characteristics. 7. Magnetic tape is an example of serial access Semiconductor memories are random memories. access memories.

Technology Semiconductor RAM Semiconductor ROM Magnetic (Hard) disk Optical disk

Storage Type Access Method Alterability Electronic Electronic Magnetic Optical Random Random Semirandom Semirandom Semirandom Semirandom Read / Write Read only Read / Write Read only Read / Write Read / Write

Permanence Volatile Non-volatile Non-volatile Non-volatile Non-volatile Non-volatile

Typical access time tA 10 ns 10 ns 50 ns 100 ms 100 ms 1 s Depend on access location

CD-ROM Erasable optical Optical disk Magnetic tape Magnetic

Page 73

Digital Logic And Computer Organization

In creasin g size

P cesso ro r

R isters eg P ary rim C ache L1

In creasin g s peed

In creasing co p b st er it

S econ ary d C ache L 2 M ain M o em ry M n ag etic D isk seco d n ary M o em ry

Memory hierarchy is adopted to achieve good price/performance ratio. Techniques that automatically swaps program and data blocks between main memory and secondary storage device are called Virtual memory. The addresses that processor issuesto access either instruction or data are called virtual or logical addresses. The memory management unit translates virtual address into physical addresses The technique of getting the desired page in the main memory is called demand paging. To support demand paging and virtual memory processor has to access page table which is kept in the main memory. To avoid the access time and degradation of performance, a small portion of the page table is accommodated in the memory management unit. This portion is called Translation Lookaside Buffer(TLB)

Comparison between different Mapping techniques: No. Direct mapping Associative Mapping 1 Each block from the A block of data from main memory has main memory can be only one possible placed into any location in the cache block cache. position. 2 Needs only one comparison Cache hit ratio Needs comparison with all tag bits Cache hit ratio has Page 74

Set associative mapping A block of data from main memory can go into a particular block location of any direct-mapped cache. Needs number of comparisons equal to number of blocks per set. The effect of

Digital Logic And Computer Organization

decreases if processor needs to access same memory location from two different pages of the main memory frequently. Main memory address is divided into three fields: TAG, BLOCK and WORD Searching time is less no effect if processor needs tp access same memory location from two different pages of the main memory frequently Main memory address is divided into two fields: TAG and WORD Searching time is more reduction in the cache hit ratio in case of frequent access to the two different pages of the main memory is reduced. Main memory address is divided into three fields: TAG, SET and WORD Searching time increases with number of blocks per set.

2.4) Intext Questions

1. Explain the fucntional units of a computer. 2. Expalin the major types of buses. 3. Explain the major types of memory classifications. 4. Explain the cache memory in detail. 5. What are the differences among sequential access, direct access and random access? 6. How does the principle of locality relate to the use of multiple memory levels 7. Explain the virtual memory in detail. 8. Describe briefly the memory management.

2.5) Summary
The major hardware components of a computer are - Input Devices, Output Devices and Central Processing Unit (CPU) Input Unit is that part of a computer through which the information is fed. The output unit refers to the device used for the display of the processed results. The Memory Unit of the CPU is the section where the program and data are stored after they are read through the input unit. Page 75

Digital Logic And Computer Organization

The address bus is a group of sixteen lines generally identified as A 0 to A15. The address bus is unidirectional: bits flow in one direction from the processor to peripheral devices. The data bus is a group of eight lines used for data flow. These lines are bidirectional data flow in both directions between the processor and peripheral devices. The signals on the I/O Memory Bus can be divided into three categories - Address lines, Data lines and Control Signals. Memory cells fabricated using current technology can be placed in one out of two stable states. One of the two stable states is used to represent the binary 0 and the other the binary 1. There are many types of ROM available for microcomputers like Mask ROM, PROM, EPROM, EEPROM and EAPROM. There are two types of RAM used in PCs - Dynamic and Static RAM. Every cache has two sub-systems, a tag subsystem which holds the memory addresses and determines whether there is a match for a requested datum; a memory subsystem which holds and delivers the data.

2.6) Terminal Exercises

1. Consider a cache consisting of 256 blocks of 16 words eac, for a total of 4096(4K) words, and assume that the main memory is addressable by a 16 bit address and it consists of 4 K blocks. How many bits are there in each of the TAG, BLOCK/SET and WORD fields for different mapping techniques?

2.7) Supplementary Materials

1. Computer organization & architecture, William Stallings, Pearson Education

2.8) Assignments
1. A set associative cache consists of 64 lines, or slots, divided into four line set. Main memory contains 4 K blocks of 128 words each. Show the format of main memory addresses.

2.9) Reference Books

1. V. Carl Hamacher, Z Vonko G.Vranesic, Safwat G.Zaky, Computer Organization, McGraw Hill International Edition, Fourth Edition, 1996.

Page 76

Digital Logic And Computer Organization 2.10) Learning Activities

A two-way set associative cache has lines of 16 byes and a total size of 8 KB. The 64 MB main memory is byte addressable. Show the format of the main memory addresses.

2.11) Keywords
RAM ROM Static RAM Dynamic RAM Memory hierarchy Direct mapping Set associative mapping Demand paging Cache Associative mapping Virtual memory Segmentation

Page 77