====================================================== Assignment #05 - Shifts, Dumps, Characters, and Memory ====================================================== - Ian! D. Allen - idallen@idallen.ca - www.idallen.com 0. What is the date of your second midterm test? Thursday November 4 - Week 9 - Midterm #2 of 2 (20%) Calculators *are* permitted but will not be necessary. *** Numeric Section *** 1. Show that Christmas == Halloween by converting DEC 25 (Christmas) to OCT 31 (Halloween), i.e. show that DECimal 25 is equal to OCTal 31 Convert 25(10) to octal by subtracting powers of eight (octal): The biggest power of eight that fits into 25 is 8**1, and we can get three of them to fit, leaving one remainder. Answer: 31(8) 25 -24 = 3 x 8**1 --- 1 - 1 = 1 x 8**0 --- 0 25(10) = 31(8) 2. In a 16-bit word, unsigned, what is the decimal value of the top bit? (What is the decimal value of an unsigned binary 16-bit number that has only the highest bit set?) Bit 0 is 2**0 so bit 15 is 2**15 which is 32,768 (a famous number). 3. True/False: The most negative two's complement number has only the sign bit turned on and all the other bits are zeroes. True. -64 = 100000(2) in 6 bits, -1024 = 1000000000(2) in 10 bits, etc. 4. True/False: Two's complement -1 is always "all bits on". True. If you add one to it, you get zero - all bits off. 5. True/False: Decimal 0.00012 x 10**41 fits in IEEE 754 single precision floating point. We need to normalize the number to see if the exponent fits: 0.00012 x 10**41 = 1.2 x 10**37 which fits in 10**38 - TRUE. 6. True/False: Decimal 100.0 x 10**37 fits in IEEE 754 single precision floating point. We need to normalize the number to see if the exponent fits: 100.0 x 10**37 = 1.00 x 10**39 which exceeds 10**38 - FALSE. 7. What is the byte ordering of Intel-based computers? Intel x86 and x86_64 computers are all Little-Endian. 8. The following hexadecimal memory dump contains two big-endian three-byte two's-complement integers, starting at address 215. What decimal values do these two big-endian three-byte integers have? ADDRESS: ---------- BIG-ENDIAN MEMORY BYTES ------------ 200: 65 6E 76 20 5F 4C 45 56 45 4C 20 24 5F 74 65 6D 210: 70 0A 65 6E 64 00 01 0A FF FD F5 28 20 24 3F 70 220: 72 6F 6D 70 74 20 29 20 74 68 65 6E 0A 09 69 66 230: 20 28 20 22 24 70 72 6F 6D 70 74 22 20 21 3D 20 240: 22 22 20 29 20 74 68 65 6E 0A 09 09 69 66 20 28 At 215 we see three bytes 00 01 0A followed by three bytes FF FD F5. Big-endian means we do *NOT* reverse the bytes: 00010Ah and FFFDF5h 00010Ah is positive (sign bit is off) - just convert it to decimal 00010Ah = A ** 16**0 + 1 * 16**2 = 10 + 256 = 266 decimal FFFDF5h is negative (sign bit is on) - use the hex bit flip table FFFDF5h -> bit flip to 00020A and add one to get 00020B 00020Bh = B ** 16**0 + 2 * 16**2 = 11 + 512 = 523 decimal (or note that 20Bh is 101h more than 10Ah above and add 257 to 266) -> so the answer is -523 decimal (a negative number) 9. What happens mathematically to the value of a binary number if you "shift" the bits to the right one place by deleting the rightmost binary digit, e.g. 1100 --> 0110 The value is halved. Any fractional remainder is thrown away. 10. What happens to the range of values possible in a word if you increase the word length by one bit, e.g. from eight bits to nine bits or from 100 bits to 101 bits? The range of possible values doubles. For example, 10 bits holds 2**10 values (1024 values) and 11 bits holds 2**11 values (2048 values). 11. What happens to the value of an unsigned binary number if you "shift" the bits to the left two places by adding two binary zeros after the rightmost binary digit, e.g. 11001(2) --> 1100100(2) The value doubles twice, i.e. quadruples (multiply by four). Every left shift multiplies the value by 2 (the base). 12. What happens to the value of an unsigned octal number if you "shift" the number to the left one place by adding one octal zero after the rightmost octal digit, e.g. 0177(8) --> 01770(8) The value is multiplied by 8 (the base). 13. What happens to the value of a hexadecimal number if you "shift" the number to the left one place by adding one hex zero after the rightmost hex digit, e.g. 0xABF --> 0xABF0 The value is multiplied by 16 (the base). 14. What is the difference between a Logical Right Shift and an Arithmetic Right Shift? Logical Right Shift adds binary zeroes on the left, e.g. 100100 LSR 1 bit = 010010 Arithmetic Right Shift (ASR) duplicates the Sign Bit on the left, e.g. 100100 ASR 1 bit = 110010 15. Of what use is an Arithmetic Right Shift? Arithmetic Right Shift can be used on two's complement numbers. A bit shift right divides both positive and negative numbers by two. 16. Is it still true that shifting a binary number left one bit multiplies it by two, if the number is a negative two's complement number? Yes, iff the doubled value can be represented in the number of bits. Consider 4-bit two's complement: 1111(2) = -1(10) shifted left becomes 1110 = -2(10) 1110(2) = -2(10) shifted left becomes 1100 = -4(10) 1101(2) = -3(10) shifted left becomes 1010 = -6(10) 1100(2) = -4(10) shifted left becomes 1000 = -8(10) 1011(2) = -5(10) shifted left becomes 0110 = +6(10) [too big] The left shift doubles the number only if the doubled number is small enough to be represented in the available number of bits. 17. Is it still true that shifting a binary number right one bit divides it by two, if the number is a negative two's complement number? Mostly, iff the shift is an Arithmetic Right Shift that preserves the Sign Bit. Consider 4-bit two's complement: 1000(2) = -8(10) arithmetic shifted right becomes 1100 = -4(10) 1000(2) = -8(10) logical shifted right becomes 0100 = +4(10) (WRONG) Note that +1 shifted right becomes zero, but -1 (all bits on) arithmetic shifted right remains -1 (all bits on). *** Character Section *** 18. The nine-character upper-case ASCII text string "ABCDEFGHI" is stored in memory starting at address location zero. a) Give the nine hexadecimal bytes stored in memory at location zero: 000: 41h 42h 43h 44h 45h 46h 47h 48h 49h See http://easycalculation.com/hex-converter.php b) Interpret just four bytes starting at address location 1 as two 16-bit two's complement integers in big-endian form and give their two decimal values: Big-endian means we do *NOT* have to reverse each of the two bytes: Integer 1: 4243h = (positive) 16963 decimal Integer 2: 4445h = (positive) 17477 decimal c) Interpret just six bytes starting at zero as two 24-bit two's complement integers in little-endian form and give their two decimal values: Little-endian means we have to reverse each of the three bytes: Integer 1: 43 42 41 -> 434241h = (positive) 4407873 decimal Integer 2: 46 45 44 -> 464544h = (positive) 4605252 decimal d) Interpret just four bytes starting at address location 2 as two 16-bit two's complement integers in big-endian form, and add one to each of these big-endian integers in memory. Give the resulting changed nine-character ASCII text string in memory (Hint: only two of the ASCII characters change): Before: 000: 41h 42h 43h 44h 45h 46h 47h 48h 49h = ABCDEFGHI Big-endian Integer 1: 4344 + 1 = 4345 Big-endian Integer 2: 4546 + 1 = 4547 After: 000: 41h 42h 43h 45h 45h 47h 47h 48h 49h = ABCEEGGHI 19. Under what operating system was the following ASCII text file created? How do you know? 4B 68 6D 74 77 0A 51 6E 62 6C 72 5B 20 0A 0A line ends = LF (or NL) = Unix/Linux/BSD/Solaris/AIX/etc. 20. What type of operating system produced the following ASCII text (in hex)? How do you know? 43 40 53 31 32 33 32 0D 0A 0D 0A is CR+LF which means DOS/Windows 21. Under what operating system was the following text file created? How do you know? 4D 6A 6F 76 79 0D 53 6F 64 6C 74 5D 22 0D 0D line ends = CR = Apple Macintosh 22. What advantage does UTF-8 have over Unicode for English text? UTF-8 encodes plain English exactly the same was that ASCII does - one byte per character. Unicode takes two bytes for every character, even plain English. 23. True/False: Plain English text, encoded as ASCII, is identical to the same Plain English text encoded as UTF-8. True. That's why UTF-8 is so popular in North America. 24. Encode the following four ASCII characters in hexadecimal using 8-bit Even Parity: a) A b) a c) B d) b 8 bit even parity ensures that the count of the number of "one" bits in a seven bit sequence is an even number by either turning on or leaving off the most significant bit (eighth bit): A = 0x41 = 0100 0001, MSB off for even parity = 0100 0001 = 0x41 a = 0x61 = 0110 0001, MSB on for even parity = 1110 0001 = 0xE1 B = 0x42 = 0100 0010, MSB off for even parity = 0100 0010 = 0x42 b = 0x62 = 0110 0010, MSB on for even parity = 1110 0010 = 0xE2 25. Encode the following four ASCII characters in hexadecimal using 8-bit Odd Parity: a) A b) a c) B d) b 8 bit odd parity ensures that the count of the number of "one" bits in a seven bit sequence is an odd number by either turning on or leaving off the most significant bit (eighth bit): The parity bit is the exact opposite of the previous answer, because we want the count of "1" bits in the byte to be odd: A = 0x41 = 0100 0001, MSB on for odd parity = 1100 0001 = 0xC1 a = 0x61 = 0110 0001, MSB off for odd parity = 0110 0001 = 0x61 B = 0x42 = 0100 0010, MSB on for odd parity = 1100 0010 = 0xC2 b = 0x62 = 0110 0010, MSB off for odd parity = 0110 0010 = 0x62 26. The following ASCII byte is received from a system that generates 8-bit Even Parity: 0xA4 Is there an error in the byte? How do you know? Error, because 0xA4 = 1010 0100 -> which is odd parity (has three "1" bits set), not even. Since even parity expects the count of the 1 bits to be an even number this byte must be an error because the count of 1 bits in A4h is an odd number (3 bits are "1"). 27. The following ASCII byte is received from a system that generates 8-bit Odd Parity: 0xA7 Is there an error in the byte? How do you know? No Error, because 0xA7 = 1010 0111 -> which has an odd number of "1" bits set and is thus correct for odd parity. Odd parity expects the count of the 1 bits to be an odd number. (5 bits are "1"). 28. You look into memory and see the hexadecimal value 40h. Based on what you know in this course so far, what different things might this 40h represent? - an EBCDIC space - an ASCII '@' symbol - the decimal value 64 in unsigned binary, 8-bit two's complement, or sign-magnitude, or one's complement (sign bit is off) - the excess-127 number -63 (e.g. an IEEE754 exponent) *** Memory Section *** 29. What do the acronyms RAM, ROM, and EEPROM stand for? RAM = Random-Access Memory ROM = Read-Only Memory EEPROM = Electrically Erasable Programmable Read Only Memory 30. Is the BIOS in your computer stored in RAM or ROM? In ROM (probably in EEPROM so that you can update it). 31. Put these in increasing order of access time (faster to slower) and indicate beside each type of device approximately what its access time is: Registers 1ns - 2 ns Level 1 Cache 3ns - 10ns Level 2 Cache 25ns - 50ns Main Memory 30ns - 90ns Fixed Hard Disk 5ms - 20ms Optical Disk 100ms - 5s Magnetic Tape 10s - 3m 32. Define "a cache hit": Finding and retrieving an instruction or item of data from the cache, instead of having to go to the slower memory or to the disk. 33. Define "a cache miss": The instruction or item of data is not in the cache, requiring access to the slower memory or to the disk. (Usually, fetching the item from the slower storage causes a copy to be left in the cache for subsequent fast access. This is "Temporal Locality".) 34. List and briefly describe the three Principles of Locality: Temporal locality - Recently-accessed data elements tend to be accessed again "soon" in time. Spatial locality - Accesses tend to cluster in the same area, which might be area of memory or area of disk. Sequential locality - Instructions and data tend to be accessed sequentially. 35. With reference to cache size, why is a small loop of code often faster than a large loop? A small loop may fit in the cache, which means it will execute more quickly in faster cache memory than a loop that generates cache misses and has to execute in slower main memory. 36. What is the basic feature that Virtual Memory enables? It enables programs to run that are larger than the available physical memory. 37. What is the difference between a Physical Address and a Virtual Address? A Physical Address is the address inside the hardware memory. A Virtual Address is the address generated by the program inside the address space of the program. The Virtual Address space is usually much larger than the Physical address space. 38. What is a "page fault"? Describe what happens. When the processor tries to map a Virtual Address to a Physical address, it finds that the Virtual address is not mapped to any Physical page - that part of the program is still on disk and is not in memory yet. The operating system has to pause the program, fetch the program page from disk, put the page into physical memory, update the page tables, then let the process continue executing. 39. How much slower (orders of magnitude) is a page fault compared to an ordinary memory access that does not cause a page fault? Milliseconds vs. Nanoseconds - 1,000,000 or six orders of magnitude. Since the operating system also has to intervene to load the missing page into memory, the cost of a Page Fault is actually much larger than this. 40. With reference to virtual memory, why is a small program often faster than a large program? A small program may fit in the available physical memory, so that the most-used parts of the program can execute without causing many Page Faults. Small programs are less likely to cause Page Faults. 41. What is virtual memory "thrashing"? The active part of a program (or many simultaneously executing programs) doesn't fit in the physical memory available, so that the program is constantly generating Page Faults to bring in new code or data and not getting any useful work done. The system is spending most of its time moving pages between memory and disk. 42. With reference to Chapter 6 Slides 46-47, describe what happens when the CPU generates the 13-bit Virtual Address 1800h: 1800h = 0001 1000 0000 0000(2) or 1100000000000(2) as just 13 bits The first three bits 110(2) of the 13-bit Virtual Address 1800h give the Page Number, so Virtual Address 1800h refers to Virtual Page six because 110(2) = 6(10). Looking in the Page Table at row 6, we see that Virtual Page 6 is located in Memory Frame 2 (binary 10(2)), so the 13-bit Virtual Address 1800h has the three-bit Virtual Page 6 (110(2)) changed to the two-bit Memory Frame (Physical Page) 2 (10(2)). 13-bit VIrtual Address 1800h becomes 12-bit Physical Address 800h to address physical memory. 43. With reference to Chapter 6 Slides 46-47, describe what happens when the CPU generates the 13-bit Virtual Address 1C00h: 1C00h = 0001 1100 0000 0000(2) or 1110000000000(2) as just 13 bits The first three bits 111(2) of the 13-bit Virtual Address 1C00h give the Page Number, so Virtual Address 1C00h refers to Virtual Page seven because 111(2) = 7(10). Looking in the Page Table at row 7, we see that Virtual Page 7 is not mapped to any Memory Frame - the Valid Bit is turned off for row 7. This Virtual Page has no Physical Page assigned to it. A Page Fault is generated, and the processor must go to the disk to load the missing page into physical memory somewhere, possibly evicting some other page to make space. When the page is loaded into memory from disk, the page table for row 7 is updated to indicate which Physical Memory frame is being used to hold that page. Then, the program is re-started at the point where the Page Fault occurred, and now the Virtual Address 1C00h will be redirected, again using row 7 of the Page Table, to some physical memory frame. 44. The code that the operating system uses to service Page Faults cannot itself reside in Virtual Memory - it must always remain in actual Physical Memory. Why can't it be in Virtual Memory? If the code that services Page Faults is in Virtual Memory, then it might happen that some of that service code is evicted to disk from physical memory to make space for other code. When that other code generates a Page Fault, it will call the virtual memory service code, but that service code isn't in memory, which generates another Page Fault, which calls the virtual memory service code that is not in memory, which generates another Page Fault, etc. The virtual memory handling code must always be in physical memory, because if it isn't in physical memory ready to run then it can't be called to put itself in memory when needed by a Page Fault. -- | Ian! D. Allen - idallen@idallen.ca - Ottawa, Ontario, Canada | Home Page: http://idallen.com/ Contact Improv: http://contactimprov.ca/ | College professor (Free/Libre GNU+Linux) at: http://teaching.idallen.com/ | Defend digital freedom: http://eff.org/ and have fun: http://fools.ca/