1.Virtual Memory Implementation: Working Set Consider a page reference string 0, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, … 100,000 references The size of the working set is 2 pages. Page thrashing Fault Rate Enough to Available M hold the working set Always allocate enough memory to hold the working set of a program (Working Set Principle) Disk cache Modern computers allocate up a large fraction of the main memory as file cache. Similar principles apply to disk cache that drastically reduces the miss penalty.
2. Address Translation Using TLB !"#$%%%%%%%%&''($)% Page table base + register 16-512 entries TLB M Set-associative or fully associative cache No match Page table is the *+,-.%%%%% &''($)% direct map in the main memory TLB is a set-associative cache that holds a partial page table. In case of a TLB hit, the block number is obtained from the TLB (fast mode). Otherwise (i.e. for TLB miss), the block number is obtained from the direct map of the page table in the main memory, and the TLB is updated.
3.Multi-level Address Translation Example 1: The old story of VAX 11/780 30-bit virtual address (1 GB) per user Page size = 512 bytes = 29 Maximum number of pages = 221 i.e. 2 million Needs 8 MB to store the page table. Too big! Solution? Store the page table in Virtual Memory. Thus, page table is also paged!
4.Example: Two-level address translation Page table base register p.0 of page table p.1 of page table p.2 of page table p.3 of page table Page table of page table (Directory) p.0 p.1 p. i Physical Memory M Virtual address space 12 9 9 Directory Offset in Offset Entry page table in page Virtual Address
5.Memory management Unit A memory management unit (MMU), is a hardware unit responsible for handling accesses to memory requested by the processor. Its functions include translation of virtual addresses virtual to physical addresses, memory protection and cache control. MMU Memory Disk Controller CPU DISK
6.Error Detection and Correction Transmission or reading errors can corrupt data. If the extent of the damage is known, then error detection codes can detect if the data has been corrupted. Using special type of error-correction codes, we can even correct errors. Parity Checking for single error detection A B C P Parity Checker The parity-bit generator generates a P so that the number of 1’s in the transmitted data is odd (or even). The parity checker checks this in the received data. How will you design (1) a parity-bit generator, and (2) a parity checker?
7.Hamming Code Hamming code not only detects if there is an error, but also locates where the error is, and subsequently corrects it. Here is an example: 1 0 1 1 1 1 0 7 6 5 4 3 2 1 The 4-bit data (1 0 1 1) to be sent is placed in bit positions 7, 6, 5, 3 of a 7-bit frame. The remaining bit positions are reserved for error-correction bits, and their values are chosen so that there is odd parity for bit combinations (4, 5, 6, 7), What is special about these sets of bits? (2, 3, 6, 7), and (1, 3, 5, 7).
8.The receiver, upon receiving the 7-bit data, computes the parities of the above bit combinations, and reports the result using three bits b2, b1, b0 as follows: Odd parity for bits 4, 5, 6, 7 ! b2 = 1 else b2 = 0. Odd parity for bits 2, 3, 6, 7 ! b1 = 1 else b1 = 0. Odd parity for bits 2, 3, 6, 7 ! b0 = 1 else b0 = 0. If b2 b1 b0 = 000 then there is no error, otherwise, the decimal equivalent of b2 b1 b0 reports the position of the corrupt bit. To correct the error, the receiver flips that bit. Question 1. The above implementation works for single errors only. Can you figure out why it works? Question 2. Can you generalize it to 32-bit data?