====================================================== Assignment #08 - Bitwise, Boolean, Memory (cache, virtual) ====================================================== - Ian! D. Allen - idallen@idallen.ca - www.idallen.com Read *all* the words in this assignment. Goal: Demonstrate mastery of bitwise and boolean operations. Demonstrate understanding of virtual memory paging. Available online: Wednesday November 2, 2011 Deliverables: One correctly-named plain text file uploaded to Blackboard. Upload due date: Upload answer file before 10:00 (10am) on Saturday November 12, 2011 Late assignments or wrong file names may or may not be marked. Answers will be posted shortly after the due date/time and discussed in class, if there are any questions about the answers. Submission method: Create a plain text file using the *exact* name: assignment08.txt Upload the file via the Assignment08 "Upload File" facility in Blackboard. Use "Attach File" and "Submit" to upload your plain text file. No wordprocessor documents. Do not send email. Use only "Attach File". Use the *exact* file name given above. Upload only one single file of plain text, not HTML, not MSWord. No fonts, no word-processing. Plain text only. Did I mention that the format is plain text (VIM/Nano/Pico/Gedit or Notepad)? NO WORD PROCESSOR, PDF, RTF, or HTML DOCUMENTS ACCEPTED. No marks are awarded for submitting under the wrong assignment number. Not all assignments will be marked. See the Week 1 Notes for details. Answers will be posted after the due date/time so that you can check your answers before coming to class and ask questions about the answers in class. Please check your answers (and my answers!). I go over each assignment in class if there are questions about the answers. No questions means no review - I'll presume you know the material. Questions similar to ones on these assignments will appear on your tests and exams. DO THIS: Edit this file and answer the following questions underneath each question, showing the method or formula you used to get the answer. Many of the questions already give you the answer - you must show the full method you use to generate that answer. Upload the file containing the question, methods, formulas, and answers before the due date. Some of the answers below will require reading the links published in the weekly course notes. Full marks are awarded only if you show your method, the same method you will have to use on your midterm test and final exam. Marks are awarded for original work, not for cut-and-paste. Any answers that are found to be cut-and-paste from some other document will require you to resubmit the entire lab as hand-written (and may result in a charge of plagiarism or academic fraud as well). Do your own thinking; write your own answers. ============================================================================== 1. What is the date for your Second Midterm Test? You may use a simple calculator on your Second Midterm Test. No phones or PDA devices. You will not need a calculator; the math will be simple powers of two. From the Course Home Page: CST8281: Wednesday November 9 12noon - B370 2. What is the date, time, and room number of your Final Exam? From the Course Home Page: CST8281: Friday December 16 08h30 (08:30am to 11am) - T130 - Final exam *** Bitwise Operators Section: AND OR XOR NOT *** 3. For eight-bit numbers x=66h and y=3Ch give answers in binary and hex: a) What is x|y? _________(2) = ___________h ? b) What is x&y? _________(2) = ___________h ? c) What is x^y? _________(2) = ___________h ? d) What is ~y? _________(2) = ___________h ? e) What is ~x? _________(2) = ___________h ? x=66 = 0110 0110 y=3C = 0011 1100 a) What is x|y? 0111 1110(2) = 7Eh b) What is x&y? 0010 0100(2) = 24h c) What is x^y? 0101 1010(2) = 5Ah d) What is ~y? 1100 0011(2) = C3h e) What is ~x? 1001 1001(2) = 99h 4. For any value x, what is the bit pattern that results from x | ~x ? "All bits on". e.g. in 4 bits if x=0101 then ~x=1010 and x|~x = 1111 5. For any value x, what is the bit pattern that results from x^x ? "All bits off." In other words, always zero. 6. For any values x and y, explain what happens after the following two sequential XOR operations, e.g. try x=5,y=10 (or other values) and see what happens to x after you do these two XOR operations in this order: x = x^y x = x^y How has x changed after each of the above two operations? Does this result depend on the values of x and y? No change in value of "x" after two operations; no dependence on the values of "x" and "y". The second XOR cancels the first one. XOR is a cheap and quick "file obscuring" operation to perform on the bytes of a file to obscure the contents of the file. 7. For any values x and y, explain what happens after the following three sequential XOR operations, e.g. try x=5,y=10 (or other values) and see what happens to x and y after you do these three XOR operations in this order: x = x^y y = x^y x = x^y How have x and y changed after the above three operations? Does this result depend on the values of x and y? The values of "x" and "y" trade places; no dependence on the values of "x" and "y". This is a (slow) way to exchange the values of two variables without requiring a third, temporary variable. 8. Java integers (including constants) are 32 bits. Give the values of "i" in 32-bit hexadecimal after each of these Java statements: ( Hint: 0 = 00000000h as 32-bit hexadecimal ) int i = 0xF0 | 0xF000; i = 0000F0F0h a) int i = ~0x80000000; i = _________________h ? b) int i = ~0x12345678; i = _________________h ? c) int i = ~1; i = _________________h ? d) int i = ~0; i = _________________h ? e) int i = ~0xF; i = _________________h ? f) int i = ~0xFFFF; i = _________________h ? g) int i = ~0xFFFFFFFF; i = _________________h ? Hint: Make sure you operate on all 32 bits in every line above. int i = 0xF0 | 0xF000; i = 0000F0F0h a) int i = ~0x80000000; i = 7FFFFFFFh b) int i = ~0x12345678; i = EDCBA987h c) int i = ~1; i = FFFFFFFEh d) int i = ~0; i = FFFFFFFFh e) int i = ~0xF; i = FFFFFFF0h f) int i = ~0xFFFF; i = FFFF0000h g) int i = ~0xFFFFFFFF; i = 00000000h *** Boolean Section - see 03.ppt *** 9. What is the opposite (the inverse of, the "NOT" of) these conditions: if ( i != 0 ) ? opposite: if ( i == 0 ) a) if ( i > 0 ) ? opposite: _____________________ ? b) if ( i < 0 ) ? opposite: _____________________ ? if ( i == 0 ) ? opposite: if ( i != 0 ) a) if ( i > 0 ) ? opposite: if ( i <= 0 ) b) if ( i < 0 ) ? opposite: if ( i >= 0 ) NOTE! that the opposite of ">" is "<=". NOTE! that the opposite of "<" is ">=". 10. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "Call the add routine unless: the cost is greater than zero or the colour is 'tan'." Note that "unless X" means "IF NOT X" (the logical complement). if ( ! ( cost > 0 || colour == tan ) ) call add(); : original if ( !(cost > 0) && !(colour == tan) ) call add(); : deMorgan if ( cost <= 0 && colour != "tan" ) call add(); : complement 11. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "In Gondor, you lose (cannot renew) your driving license if your age is 32 or older or you have more than 40 demerit points. Call the renew() function if this is not true. (Write a simplified IF statement that calls renew() if you are allowed to renew.)" lose = age >= 32 || demerit > 40 renew = NOT lose if ( NOT lose ) call renew() : original if ( ! ( age >= 32 || demerit > 40 ) ) call renew(); : substitute if ( !(age >= 32) && !(demerit > 40) ) call renew(); : deMorgan if ( age < 32 && demerit <= 40 ) call renew(); : complement 12. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "In Shire, you lose (cannot renew) your driving license if your age is more than 40, or you have 11 or more demerit points. Call the renew() function if this is not true. (Write a simplified IF statement that calls renew() if you are allowed to renew.)" LOSE = AGE > 40 || POINTS >= 11 renew = NOT LOSE if ( NOT LOSE ) call renew() : original ! LOSE = ! ( AGE > 40 || POINTS >= 11 ) : substitute ! LOSE = !(AGE > 40) && !(POINTS >= 11) : deMorgan ! LOSE = AGE <= 40 && POINTS < 11 : complement if ( AGE <= 40 && POINTS < 11 ) call renew() : substitue 13. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "A purchase is classified as "stale" if the price is $50 or more and the invoice is 80 days or more. Call the classify routine if the size is 10 or more litres and the order is not stale." stale = price >= 50 AND invoice >= 80 NOT stale = NOT ( price >= 50 AND invoice >= 80 ) = price < 50 OR invoice < 80 if ( size >= 10 AND NOT stale ) CALL classify(); if ( size >= 10 AND ( price < 50 OR invoice < 80 ) ) CALL classify(); - the parentheses are required, since AND has precedence 14. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "An order is classified as "priority" if the cost is more than $10 or the invoice is less than 90 days. Call the notify routine if the cost is more than $10 and the order is not priority." Find the bug in the above logic. What is wrong? As a programmer, what would you tell your boss about this specification? priority = cost > 10 OR invoice < 90 NOT priority = NOT ( cost > 10 OR invoice < 90 ) = cost <= 10 AND invoice >= 90 if ( cost > 10 AND NOT priority ) CALL notify(); if ( cost > 10 AND cost <= 10 AND invoice >= 90 ) CALL notify(); Observe that "cost > 10 AND cost <= 10" is a case of "A AND NOT A", which can never be true. The notify() routine will never execute. The specification is wrong. Go tell your boss you figured that out. 15. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "Call the DEL routine unless: the COST is not zero or the STATUS is not 'first'." Note that "unless X" means "IF NOT X" (the logical complement). if ! ( COST != 0 || STATUS != first ) call DEL : original if !(COST != 0) && !(STATUS != first) call DEL : deMorgan if COST == 0 && STATUS == first call DEL : complement 16. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "Call the UPDATE routine unless: the COST is less than zero and the TYPE is not 'oval'." Note that "unless X" means "IF NOT X" (the logical complement). if ! ( (COST < 0) && TYPE != oval ) call UPDATE : original if !(COST < 0) || !(TYPE != oval) call UPDATE : deMorgan if COST >= 0 || TYPE == oval call UPDATE : complement 17. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "A STALE sale is one where the DATE is greater than or equal to four years old and the COST is bigger than or equal to one. If the sale is NOT STALE, call the SEND routine." STALE = DATE >= 4 && COST >= 1 : original if ! STALE call SEND : original ! STALE = ! ( DATE >= 4 && COST >= 1 ) : substitute ! STALE = !(DATE >= 4) || !(COST >= 1) : deMorgan ! STALE = DATE < 4 || COST < 1 : complement if DATE < 4 || COST < 1 call SEND : substitute *** Miscellaneous Section *** 18. Define the term "word" as it is used in computer architecture. [See Wikipedia: Word (computing)] A word is the typical native "integer" type used in the CPU, i.e. the collection of bits used by a particular processor to represent its basic integer numeric form. 32-bit processors have 32-bit words (integers); 64-bit processors have 64-bit words (integers). Processors can still do mathematics on larger and smaller integers, but it may require more (often much more) CPU or extra instructions. 19. Put an "X" beside all the 32-bit sign/magnitude negative numbers: 600A3B65h 900000E2h AA0000EFh B9000037h F000675Ah E9900000h 200A7654h 600A3B65h X-900000E2h X-AA0000EFh X-B9000037h X-F000675Ah X-E9900000h 200A7654h 20. The IEEE 754 floating-point number 6EDCBA89h is positive. Without converting, give the hexadecimal for the same number, only negative. Turn on the sign bit: 6EDCBA89h --> EEDCBA89h 21. Without converting, put an "X" beside all the IEEE 754 negative numbers: 600A3B65h 900000E2h AA0000EFh B9000037h F000765Ah 200A7654h E9900000h 600A3B65h X-900000E2h X-AA0000EFh X-B9000037h X-F000765Ah 200A7654h X-E9900000h 22. The following hexadecimal memory dump contains two big-endian four-byte two's-complement integers, starting at address 101. What decimal values do these two big-endian four-byte integers have? ADDRESS: ---------- MEMORY BYTES ---------- 100: 00 01 DF 5E 86 FE 20 A1 7A 00 00 11 13 02 00 4F 3A F1 ... Integer 1: 01 DF 5E 86 = 01DF5E86 -> positive number = +31415942 decimal Integer 2: FE 20 A1 7A = FE20A17A -> negative number (PANIC) -> use hex flip table -> 01DF5E85 -> add 1 -> 01DF5E86 = 31415942 decimal -> put a minus sign in front -> -31415942 23. The following hexadecimal memory dump contains two little-endian four-byte two's-complement integers, starting at address 102. What decimal values do these two little-endian four-byte integers have? ADDRESS: ---------- MEMORY BYTES ---------- 100: FF 01 DE 5E 86 FE 20 A1 79 61 62 63 64 FF C4 F4 A3 1F ... Integer 1: DE 5E 86 FE -> reverse -> FE 86 5E DE = FE865EDEh -> negative -> use hex flip table -> 0179A121 -> add 1 -> 0179A122h = 24748322 decimal -> put a minus sign in front -> -24748322 Integer 2: 20 A1 79 61 -> reverse -> 61 79 A1 20 = 6179A120h -> positive -> 6179A120h = 1635361056 decimal 24. The following is a partial hexadecimal memory dump of the boot sector of an MS-DOS disk (MS-DOS means an Intel-based PC - what byte order?): 0000: EB 3C 90 4D 53 44 4F 53 35 2E 30 00 02 04 01 00 0010: 02 00 04 00 00 F8 F6 00 13 00 20 00 11 00 00 00 Read the above dump and give the hexadecimal and decimal values of the following unsigned integer items of different widths (sizes in bytes). The size of the integer is to the right of the offset, separated by a slash. The name of the item is also given below. Offset/Size: type of item: value in hex, value in decimal ----------- ------------------------------------------------ 000Bh/2: bytes per sector: 00 02 -> 0200h = 512 decimal a) 000Dh/1: sectors per allocation unit (cluster): ____________? b) 0010h/1: number of copies of FAT: ____________? c) 0011h/2: number of root directory entries: ____________? d) 0016h/2: number of sectors per FAT: ____________? e) 0018h/2: number of sectors per track: ____________? f) 001Ah/2: number of heads: ____________? Offset/Size: type of item: value in hex, value in decimal ----------- ------------------------------------------------ 000Bh/2: bytes per sector: 00 02 -> 0200h = 512 decimal a) 000Dh/1: sectors per allocation unit (cluster): 04h = 4 decimal b) 0010h/1: number of copies of FAT: 02h = 2 decimal c) 0011h/2: number of root directory entries: 00 04 -> 0400h = 1024(10) d) 0016h/2: number of sectors per FAT: F6 00 -> 00F6h = 246 decimal e) 0018h/2: number of sectors per track: 13 00 -> 0013h = 19 decimal f) 001Ah/2: number of heads: 20 00 -> 0020h = 32 decimal 25. Looking at the previous question, note the size of each integer (in bytes) and answer these questions (all integers are unsigned): a) What is the maximum number of root directory entries possible? b) What is the maximum number of sectors per allocation unit possible? max root entries (2 bytes) is (2**16)-1 = FFFFh = 65535 decimal max sectors/alloc (1 byte) is (2**8)-1 = FFh = 255 decimal 26. The eight-character ASCII text string "12345678" is stored in memory starting at location zero. (These are eight ASCII characters.) See http://easycalculation.com/hex-converter.php a) Give the eight hexadecimal character bytes as stored in memory: 31h 32h 33h 34h 35h 36h 37h 38h b) Interpret these eight bytes as two 32-bit two's complement integers in little-endian form and give their two decimal values: Integer 1: 31 32 33 34 -> 34333231h = 875770417 decimal Integer 2: 35 36 37 38 -> 38373635h = 943142453 decimal c) Interpret these eight bytes as four 16-bit two's complement integers in big-endian form and give their four decimal values: Integer 1: 3132h = (positive) 12594 decimal Integer 2: 3334h = (positive) 13108 decimal Integer 3: 3536h = (positive) 13622 decimal Integer 4: 3738h = (positive) 14136 decimal d) Add one to each of the four big-endian integers from (c) and give the resulting changed ASCII text string (eight ASCII characters): 3132h + 1 = 3133h 3334h + 1 = 3335h 3536h + 1 = 3537h 3738h + 1 = 3739h ASCII: 31 33 33 35 35 37 37 39 -> "13355779" *** Computer Basics Section - see 01.ppt *** 27. What is the modern version of Moore's Law? "the density of silicon chips doubles every 18 months" 28. Why can't Moore's law continue indefinitely? At some point the wires and components get close to the size of molecules and stop working. 29. What is the "von Neumann bottleneck"? "The limited throughput (data transfer rate) between the CPU and memory compared to the amount of memory. In most modern computers, throughput is much smaller than the rate at which the CPU can work. This seriously limits the effective processing speed when the CPU is required to perform minimal processing on large amounts of data. The CPU is continuously forced to wait for needed data to be transferred to or from memory. Since CPU speed and memory size have increased much faster than the throughput between them, the bottleneck has become more of a problem, a problem whose severity increases with every newer generation of CPU." http://en.wikipedia.org/wiki/Von_Neumann_architecture 30. What are some ways to work around the "von Neumann bottleneck"? Use on-chip registers and cache memory, separate paths for instructions and data, multiple processors. *** Memory Section - see 06.ppt *** 31. Cache memory is faster than main memory. Why not make all the memory in the computer cache memory? Cache has to fit on the CPU die. That increases the die size and reduces chip yield, driving up prices. It's too expensive. 32. Expand these acronyms into words: RAM, ROM, PROM, EPROM, EEPROM, ROTFL RAM - Random Access Memory ROM - Read-Only Memory PROM - Programmable Read-Only Memory EPROM - Erasable Programmable Read-Only Memory EEPROM - Electrically Erasable Programmable Read-Only Memory ROTFL - or ROFL: Roll On The Floor, Laughing (Internet slang) 33. Is the BIOS in your computer stored in RAM or ROM? In ROM (probably in EEPROM). 34. Put these in increasing order of access time (faster to slower) and indicate beside each type of device approximately what its access time is: Magnetic Tape Access time: Main Memory Access time: Level 2 Cache Access time: Optical Disk Access time: Registers Access time: Level 1 Cache Access time: Fixed Hard Disk Access time: Registers Access time: 1ns - 2 ns Level 1 Cache Access time: 3ns - 10ns Level 2 Cache Access time: 25ns - 50ns Main Memory Access time: 30ns - 90ns Fixed Hard Disk Access time: 5ms - 20ms Optical Disk Access time: 100ms - 5s Magnetic Tape Access time: 10s - 3m 35. 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. 36. 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".) 37. 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. 38. 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 than a loop that generates cache misses and has to access main memory (through the vonNeumann bottleneck). 39. What is the basic feature that Virtual Memory enables? It enables programs to run that are larger than the available physical memory. 40. 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. 41. What is a "page fault"? 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. 42. 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. 43. 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. 44. 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. 45. What is a "working set" for a program using virtual memory? The set of pages that need to be in memory to prevent thrashing. The minimum number of pages that must be in memory, not on disk, to let the program get useful work done. 46. With reference to Chapter 6 Slides 46-47, describe what happens when the CPU generates the 13-bit Virtual Address 1FCCh: 1FCCh = 0001 1111 1100 1100(2) or 1111111001100(2) as just 13 bits The first three bits 111(2) of the 13-bit Virtual Address 1FCCh give the Page Number, so Virtual Address 1FCCh 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 from memory 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 1FCCh will be redirected, again using row 7 of the Page Table, to some physical memory frame. 47. 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. Full marks are awarded only if you show your method, the same method you will have to use on tests and exams. Marks are awarded for original work, not for cut-and-paste. Any answers that are found to be cut-and-paste from some other document will require you to resubmit the entire lab as hand-written (and may result in a charge of plagiarism or academic fraud as well). Do your own thinking; write your own answers. -- | 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/