Unit 5: Data Communication and Operating Systems PDF

BASIC CONCEPTS Maximum size of memory that can be used in any computer is determined by addressing mode. If MAR is k-bits long then → memory may contain upto 2K addressable-locations If MDR is n-bits long, then → n-bits of data are transferred between the memory and processor....

BASIC CONCEPTS Maximum size of memory that can be used in any computer is determined by addressing mode. If MAR is k-bits long then → memory may contain upto 2K addressable-locations If MDR is n-bits long, then → n-bits of data are transferred between the memory and processor. The data-transfer takes place over the processor-bus (Figure). The processor-bus has 1) Address-Line 2) Data-line & 3) Control-Line (R/W‟, MFC – Memory Function Completed). The Control-Line is used for coordinating data-transfer. The processor reads the data from the memory by → loading the address of the required memory-location into MAR and → setting the R/W‟ line to 1. The memory responds by → placing the data from the addressed-location onto the data-lines and → confirms this action by asserting MFC signal. Upon receipt of MFC signal, the processor loads the data from the data-lines into MDR. The processor writes the data into the memory-location by → loading the address of this location into MAR & → setting the R/W‟ line to 0. 3-1  Memory Access Time: It is the time that elapses between → initiation of an operation & → completion of that operation. Memory Cycle Time: It is the minimum time delay that required between the initiation of the two successive memory-operations. 3-1 COMPUTER ORGANIZATION RAM (Random Access Memory) In RAM, any location can be accessed for a Read/Write-operation in fixed amount of time, Cache Memory It is a small, fast memory that is inserted between → larger slower main-memory and → processor. It holds the currently active segments of a program and their data. Virtual Memory The address generated by the processor is referred to as a virtual/logical address. The virtual-address-space is mapped onto the physical-memory where data are actually stored. The mapping-function is implemented by MMU. (MMU = memory management unit). Only the active portion of the address-space is mapped into locations in the physical-memory. The remaining virtual-addresses are mapped onto the bulk storage devices such as magneticdisk. As the active portion of the virtual-address-space changes during program execution, the MMU → changes the mapping-function & → transfers the data between disk and memory. During every memory-cycle, MMU determines whether the addressed-page is in the memory.If the page is in the memory. Then, the proper word is accessed and execution proceeds. Otherwise, a page containing desired word is transferred from disk to memory. Memory can be classified as follows: 1) RAM which can be further classified as follows: i) Static RAM ii) Dynamic RAM (DRAM) which can be further classified as synchronous & asynchronousDRAM. 2) ROM which can be further classified as follows: i) PROM ii) EPROM iii) EEPROM & iv) Flash Memory which can be further classified as Flash Cards & Flash Drives.  3-28 4 SEMI CONDUCTOR RAM MEMORIES INTERNAL ORGANIZATION OF MEMORY-CHIPS Memory-cells are organized in the form of array (Figure 8.2). Each cell is capable of storing 1-bit of information. Each row of cells forms a memory-word. All cells of a row are connected to a common line called as Word-Line. The cells in each column are connected to Sense/Write circuit by 2-bit-lines. The Sense/Write circuits are connected to data-input or output lines of the chip. During a write-operation, the sense/write circuit → receive input information & → store input info in the cells of the selected word.  The data-input and data-output of each Sense/Write circuit are connected to a single bidirectional data-line. Data-line can be connected to a data-bus of the computer. Following 2 control lines are also used: 1) R/W 🡪 Specifies the required operation. CS 🡪 Chip Select input selects a given chip in the multi-chip memory-system 5 RAM– Random Access memory ∙ Memory cells can be accessed for information transfer from any desired random location. ∙ The process of locating a word in memory is the same and requires of locating a word in memory is the same and requires an equal amount of time no matter where the cells are located physically in memory thus named 'Random access'. ∙ Integrated RAM are available in two possible operating modes, Static and Dynamic Static RAM (SRAM) ∙ The static RAM consists of flip flop that stores binary information and this stored information remains valid as long as power is applied to the unit. ∙ Memories consist of circuits capable of retaining their state as long as power is applied are known. ∙ Two inverters are cross connected to form a latch (Figure 8.4). ∙ The latch is connected to 2-bit-lines by transistors T1 and T2. ∙ The transistors act as switches that can be opened/closed under the control of the word-line. ∙ When the word-line is at ground level, the transistors are turned off and the latch retain its state. Read Operation ∙ To read the state of the cell, the word-line is activated to close switches T1 and T2. ∙ If the cell is in state 1, the signal on bit-line b is high and the signal on the bit-line b‟ is low. ∙ Thus, b and b‟ are complement of each other. ∙ Sense/Write circuit → monitors the state of b & b‟ and → sets the output accordingly. Write Operation ∙ The state of the cell is set by → placing the appropriate value on bit-line b and its complement on b‟ and → then activating the word-line. This forces the cell into the corresponding state. ∙ The required signal on the bit-lines is generated by Sense/Write circuit. 6  CMOS Cell Transistor pairs (T3, T5) and (T4, T6) form the inverters in the latch (Figure 8.5). In state 1, the voltage at point X is high by having T5, T6 ON and T4, T5 are OFF. Thus, T1 and T2 returned ON (Closed), bit-line b and b‟ will have high and low signals respectively. Advantages: 1) It has low power consumption.The current flows in the cell only when the cell is active. 2) Static RAMs can be accessed quickly. It access time is few nanoseconds. Dynamic RAM (DRAM) ∙ The dynamic RAM stores the binary information in the form of electrical charges and capacitor is used for this purpose. ∙ Since charge stored in capacitor discharges with time, capacitor must be periodically recharged and which is also called refreshing memory. Fig: DRAM structure ∙ The address line is activated when the bit value from this cell is to be read or written. ∙ The transistor acts as switch that is closed i.e. allowed current to flow, if voltage is applied to the address line; and opened i.e. no current to flow, if no voltage is present in the address line. 7 For DRAM writing ∙ The address line is activated which causes the transistor to conduct. ∙ The sense amplifier senses the content of the data bus line for this cell.  ∙ If the bus line is low, then amplifier will ground the bit line of cell and any charge in capacitor is addressed out. ∙ If data bus is high, then a +5V is applied on bit line and voltage will flow through transistor and charge the capacitor. For DRAM reading ∙ Address line is activated which causes the transistor to conduct. ∙ If there is charge stored in capacitor, then current will flow through transistor and raise the voltage in bit line. The amplifier will store the voltage and place a 1 on data out line. ∙ If there is no charge stored in capacitor, then no current will flow through transistor and voltage bit line will not be raised. The amplifier senses that there is no charge and places a 0 on data out line. SRAM versus DRAM ∙ Both volatile ∙ Power needed to preserve data Static RAM o Uses flip flop to store information o Needs more space o Faster, digital device o Expensive, big in size o Don't require refreshing circuit o Used in cache memory Dynamic RAM o Uses capacitor to store information o More dense i.e. more cells can be accommodated per unit area o Slower, analog device o Less expensive, small in size o Needs refreshing circuit o Used in main memory, larger memory units 8 READ ONLY MEMORY (ROM) Both SRAM and DRAM chips are volatile, i.e. They lose the stored information if power is turned off. Many application requires non-volatile memory which retains the stored information if power is turned off. For ex: OS software has to be loaded from disk to memory i.e. it requires non-volatile memory. Non-volatile memory is used in embedded system. Since the normal operation involves only reading of stored data, a memory of this type is calledROM. At Logic value ‘0’ Transistor(T) is connected to the ground point(P). Transistor switch is closed & voltage on bit-line nearly drops to zero (Figure ). At Logic value ‘1’ open.The bit-line remains at high voltage.  To read the state of the cell, the word-line is activated. A Sense circuit at the end of the bit-line generates the proper output value. To read the state of the cell, the word-line is activated. A Sense circuit at the end of the bit-line generates the proper output value Read only memory (ROM) contains a permanent pattern of data that cannot be changed. A ROM is non-volatile that is no power source is required to maintain the bit values in memory. While it is possible to read a ROM, it is not possible to write new data into it. The data or program is permanently presented in main memory and never be loaded from a secondary storage device with the advantage of ROM. A ROM is created like any other integrated circuit chip, with the data actually wired into the chip as part of the fabrication process. It presents two problems o The data insertion step includes a relatively large fixed cost, whether one or thousands of copies of a particular ROM are fabricated. o There is no room for error. If one bit is wrong, the whole batch of ROM must be thrown out. 9 TYPES OF ROM Different types of non-volatile memory are 1) PROM 2) EPROM 3) EEPROM & 4) Flash Memory (Flash Cards & Flash Drives) PROM (PROGRAMMABLE ROM) PROM allows the data to be loaded by the user. Programmability is achieved by inserting a ―fuse‟ at point P in a ROM cell. Before PROM is programmed, the memory contains all ―0‟s. User can insert ― 1‟s at required location by burning-out fuse using high current-pulse. This process is irreversible. Advantages: 1) It provides flexibility. 2) It is faster.  3) It is less expensive because they can be programmed directly by the user. EPROM (ERASABLE REPROGRAMMABLE ROM) EPROM allows → stored data to be erased and → new data to be loaded. In cell, a connection to ground is always made at „P‟ and a special transistor is used. The transistor has the ability to function as → a normal transistor or → a disabled transistor that is always turned „off‟. Transistor can be programmed to behave as a permanently open switch, by injecting charge into it. Erasure requires dissipating the charges trapped in the transistor of memory-cells. This can be done by exposing the chip to ultra-violet light. Advantages: 1) It provides flexibility during the development-phase of digital-system. 2) It is capable of retaining the stored information for a long time. Disadvantages: 1) The chip must be physically removed from the circuit for reprogramming. 2) The entire contents need to be erased by UV light. EEPROM (ELECTRICALLY ERASABLE ROM) Advantages: 1) It can be both programmed and erased electrically. 2) It allows the erasing of all cell contents selectively. Disadvantage: It requires different voltage for erasing, writing and reading the stored data. FLASH MEMORY In EEPROM, it is possible to read & write the contents of a single cell. In Flash device, it is possible to read contents of a single cell & write entire contents of a block. Prior to writing, the previous contents of the block are erased. Eg. In MP3 player, the flash memory stores the data that represents sound. Single flash chips cannot provide sufficient storage capacity for embedded-system. Advantages: 1) Flash drives have greater density which leads to higher capacity & low cost per bit. 10 2) It requires single power supply voltage & consumes less power. There are 2 methods for implementing larger memory: 1) Flash Cards & 2) Flash Drives 1) Flash Cards One way of constructing larger module is to mount flash-chips on a small card. Such flash-card have standard interface. The card is simply plugged into a conveniently accessible slot. Memory-size of the card can be 8, 32 or 64MB. Eg: A minute of music can be stored in 1MB of memory. Hence 64MB flash cards can store an hour of music. 2) Flash Drives Larger flash memory can be developed by replacing the hard disk-drive. The flash drives are designed to fully emulate the hard disk. The flash drives are solid state electronic devices that have no movable parts. Advantages:  1)They have shorter seek & access time which results in faster response. 2)They have low power consumption..‟. they are attractive for battery driven application. 3) They are insensitive to vibration. Disadvantages: 1) The capacity of flash drive (1GB). 2) It leads to higher cost per bit. 3) Flash memory will weaken after it has been written a number of times (typicallyat least 1 million times). SPEED, SIZE COST The main-memory can be built with DRAM (Figure ) Thus, SRAM‟s are used in smaller units where speed is of essence. The Cache-memory is of 2 types: 1) Primary/Processor Cache (Level1 or L1 cache) It is always located on the processor-chip. 2) Secondary Cache (Level2 or L2 cache) It is placed between the primary-cache and the rest of the memory. The memory is implemented using the dynamic components (SIMM, RIMM, DIMM). The access time for main-memory is about 10 times longer than the access time for L1 cache. 11 CACHE MEMORIES The cache is a small and very fast memory, interposed between the processor and the main memory. Its purpose is to make the main memory appear to the processor to be much faster than it actually is. The effectiveness of this approach is based on a property of computer programs called locality of reference. Analysis of programs shows that most of their execution time is spent in routines in which many instructions are executed repeatedly. These instructions may constitute a simple loop, nested loops, or a few procedures that repeatedly call each other. The actual detailed pattern of instruction sequencing is not important—the point is that many instructions in localized areas of the program are executed repeatedly during some time period. There are 2 types of called locality of reference. ∙ Temporal locality of reference ∙ Spatial locality of reference Temporal locality of reference means that a recently executed instruction is likely to be executed again very soon. Spatial locality of reference means that instructions close to a recently executed instruction are also likely to be executed soon. 12 Conceptually, operation of a cache memory is very simple. The memory control circuitry is designed to take advantage of the property of locality of reference. Temporal locality suggests that whenever an information item, instruction or data, is first needed, this item should be brought into the cache, because it is likely to be needed again soon. Spatial locality suggests that instead of fetching just one item from the main memory to the cache, it is useful to fetch several items that are located at adjacent addresses as well. The term cache block refers to a set of contiguous address locations of some size. Another term that is often used to refer to a cache block is a cache line. Consider the arrangement in Figure. When the processor issues a Read request, the contents of a block of memory words containing the location specified are transferred into the cache. Subsequently, when the program references any of the locations in this block, the desired contents are read directly from the cache. Usually, the cache memory can store a reasonable number of blocks at any given time, but this number is small compared to the total number of blocks in the main memory. The correspondence between the main memory blocks and those in the cache is specified by a mapping function. When the cache is full and a memory word (instruction or data) that is not in the cache is referenced, the cache control hardware must decide which block should be removed to create space for the new block that contains the referenced word. The collection of rules for making this decision constitutes the cache’s replacement algorithm. Cache Hits: The processor does not need to know explicitly about the existence of the cache. It simply issues Read and Write requests using addresses that refer to locations in the memory. The cache control circuitry determines whether the requested word currently exists in the cache. If it does, the Read or Write operation is performed on the appropriate cache location. In this case, a read or write hit is said to have occurred. 13 The main memory is not involved when there is a cache hit in a Read operation. For a Write operation, the system can proceed in one of two ways. In the first technique, called the write-through protocol, both the cache location and the main memory location are updated. The second technique is to update only the cache location and to mark the block containing it with an associated flag bit, often called the dirty or modified bit. The main memory location of the word is updated later, when the block containing this marked word is removed from the cache to make room for a new block. This technique is known as the write-back, or copy-back, protocol. The write-through protocol is simpler than the write-back protocol, but it results in unnecessary Write operations in the main memory when a given cache word is updated several times during its cache residency. The write-back protocol also involves unnecessary Write operations, because all words of the block are eventually written back, even if only a single word has been changed while the block was in the cache. The write-back protocol is used most often, to take advantage of the high speed with which data blocks can be transferred to memory chips. Cache Misses A Read operation for a word that is not in the cache constitutes a Read miss. It causes the block of words containing the requested word to be copied from the main memory into the cache. After the entire block is loaded into the cache, the particular word requested is forwarded to the processor. Alternatively, this word may be sent to the processor as soon as it is read from the main memory. The latter approach, which is called load-through, or early restart, reduces the processor’s waiting time somewhat, at the expense of more complex circuitry. When a Write miss occurs in a computer that uses the write-through protocol, the information is written directly into the main memory. For the write-back protocol, the block containing the addressed word is first brought into the cache, and then the desired word in the cache is overwritten with the new information. 14  The Cache-memory stores a reasonable number of blocks at a given time. This number of blocks is small compared to the total number of blocks available in main-memory. Correspondence b/w main-memory-block & cache-memory-block is specified by mapping-function. Cache control hardware decides which block should be removed to create space for the new block. The collection of rule for making this decision is called the Replacement Algorithm. The cache control-circuit determines whether the requested-word currently exists in the cache. When the processor attempts to read a word of memory, a check is made to determine if the word is in the cache. If so, the word is delivered to the processor. If not, a block of main memory, consisting of fixed number of words is read into the cache and then the word is delivered to the processor. The locality of reference property states that over a short interval of time, address generated by a typical program refers to a few localized area of memory repeatedly. So if programs and data which are accessed frequently are placed in a fast memory, the average access time can be reduced. This type of small, fast memory is called cache memory which is placed in between the CPU and the main memory. When the CPU needs to access memory, cache is examined. If the word is found in cache, it is read from the cache and if the word is not found in cache, main memory is accessed to read word. A block of word containing the one just accessed is then transferred from main memory to cache memory. The write-operation is done in 2 ways: 1) Write-through protocol & 2) Write-back protocol. Write-Through Protocol Here the cache-location and the main-memory-locations are updated simultaneously. Write-Back Protocol This technique is to → update only the cache-location & → mark the cache-location with associated flag bit called Dirty/Modified Bit. The word in memory will be updated later, when the marked-block is removed from cache. During Read-operation If the requested-word currently not exists in the cache, then read-miss will occur. To overcome the read miss, Load–through/Early restart protocol is used. Load–Through Protocol The block of words that contains the requested-word is copied from the memory into cache. After entire block is loaded into cache, the requested-word is forwarded to processor. During Write-operation If the requested-word not exists in the cache, then write-miss will occur. 15  1) If Write Through Protocol is used, the information is written directly into main-memory. 2) If Write Back Protocol is used, → then block containing the addressed word is first brought into the cache & → then the desired word in the cache is over-written with the new information. CACHE MAPPING The transformation of data from main memory to cache memory is referred to as memory mapping process. Because there are fewer cache lines than main memory blocks, an algorithm is needed for mapping main memory blocks into cache lines. There are 3 types of cache mapping 1) Direct Mapping 2) Associative Mapping 3) Set-Associative Mapping DIRECT MAPPING The block-j of the main-memory maps onto block-j modulo-128 of the cache (Figure ). When the memory-blocks 0, 128, & 256 are loaded into cache, the block is stored in cache-block 0. Similarly, memory-blocks 1, 129, 257 are stored in cache-block 1. The contention may arise 1) When the cache is full. 2) When more than one memory-block is mapped onto a given cache-block position. The contention is resolved by allowing the new blocks to overwrite the currently resident-block. Memory-address determines placement of block in the cache. Example : Main memory size = 2 16 words Main memory ( MM) is divided into blocks of equal size. Each block contains 16 words.( 16= 24) Total number of blocks in main memory =(2 16 /2 4 ) = 2 12= 4096 ( MM block number ranges from 0 to 4095) Cache memory is small in size But it is also divided into blocks of same size as MM blocks. Let cache memory size be 2 11 words Cache block size = MM block size= 16 words = 2 4 16 Number of cache blocks = (211 / 2 4) = 2 7=128 (CM block number ranges from 0 to 127)  The memory-address is divided into 3 fields: 1) Low Order 4 bit field Selects one of 16 words in a block. 2) 7 bit cache-block field 7-bits determine the cache-position in which new block must be stored. 3) 5 bit Tag field 5-bits memory-address of block is stored in 5 tag-bits associated with cache-location. As execution proceeds, 5-bit tag field of memory-address is compared with tag-bits associated with cache-location. If they match, then the desired word is in that block of the cache. Otherwise, the block containing required word must be first read from the memory. And then the word must be loaded into the cache. Advantages Simplest type of mapping Fast as only tag field matching is required while searching for a word. 17 It is comparatively less expensive than associative mapping. Disadvantage: ∙ It is less flexible. ∙ its performance is degraded if two or more blocks that map to the same location are used alternately ASSOCIATIVE MAPPING  The memory-block can be placed into any cache-block position. (Figure). 12 tag-bits will identify a memory-block when it is resolved in the cache. Tag-bits of an address received from processor are compared to the tag-bits of each block of cache. This comparison is done to see if the desired block is present. It gives complete freedom in choosing the cache-location. A new block that has to be brought into the cache has to replace an existing block only if the cache is full. The memory has to determine whether a given block is in the cache. In associative method, The block position is not pre-determined. If the cache is full and if new blocks are brought into the cache,then the cache-controller must decide which of the old blocks has to be replaced. 1. Least Recently used (LRU) o replace that block in which has been in cache longest with no reference to it. When a block is to be overwritten, the block with longest time w/o being referenced is over-written. This block is called Least recently Used (LRU) block & the technique is called LRU algorithm o Probably the most effective method 2. First in first out (FIFO) o replace that block which has been in the cache longest 3. Least-frequently-used (LFU) o replace that block which has experienced the fewest references or hits 4. Random o replace a random block Example : Main memory size = 2 16 words Main memory ( MM) is divided into blocks of equal size. Each block contains 16 words.( 16= 24) Total number of blocks in main memory =(2 16 /2 4 ) = 2 12= 4096 ( MM block number ranges from 0 to 4095) Cache memory is small in size But it is also divided into blocks of same size as MM blocks. Let cache memory size be 2 11 words Cache block size = MM block size= 16 words = 2 4 18 Number of cache blocks = (211 / 2 4) = 2 7=128 (CM block number ranges from 0 to 127) The complexity of an associative cache is higher than that of a direct-mapped cache, because of the need to search all 128 tag patterns to determine whether a given block is in the cache. To avoid a long delay, the tags must be searched in parallel. A search of this kind is called an associative search. Advantage: It is more flexible than direct mapping technique. Disadvantage: Its cost is high. SET-ASSOCIATIVE MAPPING The blocks of the cache are grouped into sets, and the mapping allows a block of the main memory to reside in any block of a specific set. Hence, the contention problem of the direct method is eased by having a few choices for block placement. At the same time, the hardware cost is reduced by decreasing the size of the associative search. It is the combination of direct and associative mapping. (Figure). The blocks of the cache are grouped into sets. The mapping allows a block of the main-memory to reside in any block of the specified set. Example : Main memory size = 2 16 words Main memory ( MM) is divided into blocks of equal size. 19 Each block contains 16 words.( 16= 24)  Total number of blocks in main memory =(2 16 /2 4 ) = 2 12 = 4096 ( MM block number ranges from 0 to 4095) Cache memory is small in size But it is also divided into blocks of same size as MM blocks. Let cache memory size be 2 11 words Cache block size = MM block size= 16 words = 2 4 Number of cache blocks = (211 / 2 4) = 2 7=128 (CM block number ranges from 0 to 127) The cache has 2 blocks per set, so the memory-blocks 0, 64, 128…….. 4032 maps into cache set ―0‟. The cache can occupy either of the two block position within the set. 6 bit set field Determines which set of cache contains the desired block. 6 bit tag field The tag field of the address is compared to the tags of the two blocks of the set. This comparison is done to check if the desired block is present. The cache which contains 1 block per set is called direct mapping. A cache that has k blocks per set is called as―k-way set associative cache‟. Each block contains a control-bit called a valid-bit. The Valid-bit indicates that whether the block contains valid-data. The dirty bit indicates that whether the block has been modified during its cache residency. Valid-bit=0 : When power is initially applied to system. Valid-bit=1 : When the block is loaded from main-memory at first time. If the main-memory-block is updated by a source & if the block in the source is already exists in thecache, then the valid-bit will be cleared to ―0‟. If Processor & DMA uses the same copies of data then it is called as Cache Coherence Problem In set associative method, The block position is not pre-determined. ∙ If the cache is full and if new blocks are brought into the cache,then the cache-controller must decide which of the old blocks has to be replaced. 1. Least Recently used (LRU) Replace that block in the set which has been in cache longest with no reference to it. When a block is to be overwritten, the block with longest time w/o being referenced is over-written. This block is called Least recently Used (LRU) block & the technique is called LRU algorithm o Probably the most effective method 2. First in first out (FIFO) o Replace that block in the set which has been in the cache longest 3. Least-frequently-used (LFU) o Replace that block in the set which has experienced the fewest references or hits 4. Random 20 o Replace a random block in the set  Advantages: 1) Contention problem of direct mapping is solved by having few choices for block placement. 2) The hardware cost is decreased by reducing the size of associative search. REPLACEMENT ALGORITHMs In direct mapping method,the position of each block is pre-determined and there is no need of replacement strategy. In associative & set associative method,The block position is not pre-determined. If the cache is full and if new blocks are brought into the cache,then the cache-controller must decide which of the old blocks has to be replaced. 1. Least Recently used (LRU) o replace that block in the set which has been in cache longest with no reference to it. When a block is to be overwritten, the block with longest time w/o being referenced is over-written. This block is called Least recently Used (LRU) block & the technique is called LRU algorithm 21 o Probably the most effective method 2. First in first out (FIFO) o replace that block in the set which has been in the cache longest 3. Least-frequently-used (LFU)  o replace that block in the set which has experienced the fewest references or hits 4. Random o replace a random block in the set PERFORMANCE CONSIDERATION Two key factors in the commercial success are 1) performance & 2) cost. In other words, the best possible performance at low cost. A common measure of success is called the Price l Performance ratio. Performance depends on → how fast the machine instructions are brought to the processor & → how fast the machine instructions are executed. To achieve parallelism, interleaving is used. Parallelism means both the slow and fast units are accessed in the same manner. INTERLEAVING The main-memory of a computer is structured as a collection of physically separate modules. Each module has its own 1) ABR (address buffer register) & 2) DBR (data buffer register). So, memory access operations may proceed in more than one module at the same time (Fig ). Thus, the aggregate-rate of transmission of words to/from the main-memory can be increased. The low-order k-bits of the memory-address select a module. While the high-order m-bits name a location within the module. In this way, consecutive addresses are located in successive modules. Thus, any component of the system can keep several modules busy at any one time T. 22 This results in both → faster access to a block of data and → higher average utilization of the memory-system as a whole. To implement the interleaved-structure, there must be 2k modules;  Otherwise, there will be gaps of non-existent locations in the address-space. Hit Rate & Miss Penalty The number of hits stated as a fraction of all attempted accesses is called the Hit Rate. The extra time needed to bring the desired information into the cache is called the Miss Penalty. High hit rates well over 0.9 are essential for high-performance computers. Performance is adversely affected by the actions that need to be taken when a miss occurs. A performance penalty is incurred because of the extra time needed to bring a block of data from a slower unit to a faster unit. During that period, the processor is stalled waiting for instructions or data. We refer to the total access time seen by the processor when a miss occurs as the miss penalty. Let h be the hit rate, M the miss penalty, and C the time to access information in the cache. Thus,the average access time experienced by the processor is tavg = hC + (1 − h)M VIRTUAL MEMORY. In most modern computer systems, the physical main memory is not as large as the address space of the processor. For example, a processor that issues 32-bit addresses has an addressable space of 4G bytes. The 23 size of the main memory in a typical computer with a 32- bit processor may range from 1G to 4G bytes. If a program does not completely fit into the main memory, the parts of it not currently being executed are stored on a secondary storage device, typically a magnetic disk. As these parts are needed for execution, they must first be brought into the main memory, possibly replacing other parts that are already in the memory. These actions are performed automatically by the operating system, using a scheme known as virtual memory. Application programmers need not be aware of the limitations imposed by the available main memory. They prepare programs using the entire address space of the processor Under a virtual memory system, programs, and hence the processor, reference instructions and data in an address space that is independent of the available physical main memory space. The binary addresses that the processor issues for either instructions or data are called virtual or logical addresses. These addresses are translated into physical addresses by a combination of hardware and software actions. If a virtual address refers to a part of the program or data space that is currently in the physical memory, then the contents of the appropriate location in the main memory are accessed immediately. Otherwise, the contents of the referenced address must be brought into a suitable location in the memory before they can be used. Figure shows a typical organization that implements virtual memory. A special hardware unit, called the Memory Management Unit (MMU), keeps track of which parts of the virtual address space are in the physical memory. When the desired data or instructions are in the main memory, the MMU translates the virtual address into the corresponding physical address. Then, the requested memory access proceeds in the usual manner. If the data are not in the main memory, the MMU causes the operating system to transfer the data from the disk to the memory. Such transfers are performed using the DMA scheme. Summary It refers to a technique that automatically move program/data blocks into the main-memory wh en they are required for execution (Figure ). The address generated by the processor is referred to as a virtual / logical address. The virtual-address is translated into physical-address by MMU (Memory Management Unit). During every memory-cycle, MMU determines whether the addressed-word is in the memory. If the word is in memory.Then, the word is accessed and execution proceeds.Otherwise, a page containing desired word is transferred from disk to memory.Using DMA scheme, transfer of data between disk and memory is performed 24 VIRTUAL MEMORY ADDRESS TRANSLATION All programs and data are composed of fixed length units called Pages (Figure). The Page consists of a block-of-words. The words occupy contiguous locations in the memory. The pages are commonly range from 2K to 16K bytes in length. Cache Bridge speed-up the gap between main-memory and secondary-storage. Each virtual-address contains 1) Virtual Page number (Low order bit) and 2) Offset (High order bit).  Virtual Page number + Offset : specifies the location of a particular word within a page. Page-table: It contains the information about → memory-address where the page is stored & → current status of the page. Page-frame: An area in the main-memory that holds one page. Page-table Base Register: It contains the starting address of the page-table. Virtual Page Number + Page-table Base register: Gives the starting address of the page if that pagecurrently resides in memory. Control-bits in Page-table: The Control-bits is used to 1) Specify the status of the page while it is in memory. 2) Indicate the validity of the page. 3) Indicate whether the page has been modified during its stay in the memory. TRANSLATION LOOKASIDE BUFFER (TLB) The Page-table information is used by MMU for every read/write access (Figure). The Page-table is placed in the memory but a copy of small portion of the page-table is located within MMU. This small portion is called TLB (Translation LookAside Buffer). TLB consists of the page-table entries that corresponds to the most recently accessed pages. 25 TLB also contains the virtual-address of the entry.  When OS changes contents of page-table, the control-bit will invalidate corresponding entry in TLB. Given a virtual-address, the MMU looks in TLB for the referenced-page. If page-table entry for this page is found in TLB, the physical-address is obtained immediately. Otherwise, the required entry is obtained from the page-table & TLB is updated. Page Faults Page-fault occurs when a program generates an access request to a page that is not in memory. When MMU detects a page-fault, the MMU asks the OS to generate an interrupt. The OS → suspends the execution of the task that caused the page-fault and → begins execution of another task whose pages are in memory. When the task resumes the interrupted instruction must continue from the point of interruption. If a new page is brought from disk when memory is full, disk must replace one of the resident pages.In this case, LRU algorithm is used to remove the least referenced page from memory. A modified page has to be written back to the disk before it is removed from the memory. In this case, Write–Through Protocol is used. 26 SECONDARY-STORAGE The semi-conductor memories do not provide all the storage capability. The secondary-storage devices provide larger storage requirements. Some of the secondary-storage devices are: 1) Magnetic Disk 2) Optical Disk & 3) Magnetic Tapes. MAGNETIC DISK Magnetic Disk system consists of one or more disk mounted on a common spindle. A thin magnetic film is deposited on each disk (Figure 8.27).  Disk is placed in a rotary-drive so that magnetized surfaces move in close proximity to R/W heads. Each R/W head consists of 1) Magnetic Yoke & 2) Magnetizing-Coil. Digital information is stored on magnetic film by applying current pulse to the magnetizing-coil. Only changes in the magnetic field under the head can be sensed during the Read-operation. Therefore, if the binary states 0 & 1 are represented by two opposite states, then a voltage is induced in the head only at 0-1 and at 1-0 transition in the bit stream. A consecutive of 0‟s & 1‟s are determined by using the clock. Manchester Encoding technique is used to combine the clocking information with data. R/W heads are maintained at small distance from disk-surfaces in order to achieve high bit densities. When disk is moving at their steady state, the air pressure develops b/w disk-surfaces & head. 27 This air pressure forces the head away from the surface. The flexible spring connection between head and its arm mounting permits the head to fly at thedesired distance away from the surface. Winchester Technology Read/Write heads are placed in a sealed, air–filtered enclosure called the Winchester Technology. The read/write heads can operate closure to magnetic track surfaces because unsealed assemblies are absent. Advantages the dust particles which are a problem in  It has a larger capacity for a given physical size. The data intensity is high because the storage medium is not exposed to contaminating elements. The read/write heads of a disk system are movable. The disk system has 3 parts: 1) Disk Platter (Usually called Disk) 2) Disk-drive (spins the disk & moves Read/write heads) 3) Disk Controller (controls the operation of the system.) ORGANIZATION & ACCESSING OF DATA ON A DISK Each surface is divided into concentric Tracks (Figure ). Each track is divided into Sectors. The set of corresponding tracks on all surfaces of a stack of disk form a Logical Cylinder. The data are accessed by specifying the surface number, track number and the sector number. The Read/Write-operation start at sector boundaries. Data bits are stored serially on each track. Each sector usually contains 512 bytes. Sector Header --> contains identification information. It helps to find the desired sector on the selected track. ECC (Error checking code)- is used to detect and correct errors. An unformatted disk has no information on its tracks. The formatting process divides the disk physically into tracks and sectors. The formatting process may discover some defective sectors on all tracks. Disk Controller keeps a record of various defects. The disk is divided into logical partitions: 1) Primary partition 28 2) Secondary partition Each track has same number of sectors. So, all tracks have same storage capacity. Thus, the stored information is packed more densely on inner track than on outer track. Access Time There are 2 components involved in the time-delay: 1) Seek time: Time required to move the read/write head to the proper track. 2) Latency/Rotational Delay: The amount of time that elapses after head is positioned overthe correct track until the starting position of the addressed sector passes under the R/W head. Seek time + Latency = Disk access time Typical Disk  One inch disk-weight = 1 ounce, size -> comparable to match bookCapacity -> 1GB Inch disk has the following parameter Recording surface=20 Tracks=15000 tracks/surface Sectors=400. Each sector stores 512 bytes of data Capacity of formatted disk=20x15000x400x512=60x109 =60GBSeek time=3ms Platter rotation=10000 rev/minLatency=3ms Internet transfer rate=34MB/s Secondary Memory The devices that provide backup storage are called external memory or auxiliary memory. It includes serial access type such as magnetic tapes and random access type such as magnetic disks. Magnetic Tape A magnetic tape is the strip of plastic coated with a magnetic recording medium. Data can be recorded and read as a sequence of character through read / write head. It can be stopped, started to move forward or in reverse or can be rewound. Data on tapes are structured as number of parallel tracks running length wise. Earlier tape system typically used nine tracks. This made it possible to store data one byte at a time with additional parity bit as 9th track. The recording of data in this form is referred to as parallel recording. Magnetic Disk A magnetic disk is a circular plate constructed with metal or plastic coated with magnetic material often both side of disk are used and several disk stacked on one spindle which Read/write head available on each surface. All disks rotate together at high speed. Bits are stored in magnetize surface in spots along concentric circles called tracks. The tracks are commonly divided into sections called sectors. After the read/write head are positioned in specified track the system has to wait until the rotating disk reaches the specified sector under read/write head. Information transfer is very fast once the beginning of sector has been reached. Disk that are permanently attached to the unit assembly and cannot be used by occasional user are called hard disk drive with removal disk is called floppy disk. 29 Optical Disk The huge commercial success of CD enabled the development of low cost optical disk storage technology that has revolutionized computer data storage. The disk is form from resin such as polycarbonate. Digitally recorded information is imprinted as series of microscopic pits on the surface of poly carbonate. This is done with the finely focused high intensity leaser. The pitted surface is then coated with reflecting surface usually aluminum or gold. The shiny surface is protected against dust and scratches by the top coat of acrylic. Information is retrieved from CD by low power laser. The intensity of reflected light of laser changes as it encounters a pit. Specifically if the laser beam falls on pit which has somewhat rough surface the light scatters and low intensity is reflected back to the surface. The areas between pits are called lands. A land is a smooth surface which reflects back at higher intensity. The change between pits and land is detected by photo sensor and converted into digital signal. The sensor tests the surface at regular interval. DVD-Technology ∙ Multi-layer ∙ Very high capacity (4.7G per layer) ∙ Full length movie on single disk ∙ Using MPEG compression ∙ Finally standardized (honest!) ∙ Movies carry regional coding ∙ Players only play correct region films DVD-Writable ∙ Loads of trouble with standards ∙ First generation DVD drives may not read first generation DVD-W disks ∙ First generation DVD drives may not read CD-RW disks