================================================================= Assignment #09 - Boolean Logic, Memory, and Internet ================================================================= - Ian! D. Allen - idallen@idallen.ca - www.idallen.com Answers by: Ian Allen Chuan Jin (thanks!) 0. What is the date of your second midterm test? Wednesday March 31, 2010 *** Boolean Section *** Recall that "NOT x" can be written in text using the "prime" mark: x' 1. True/False: (xy)' == x'y' In English: "NOT(red AND jello) == NOT red AND NOT jello" ? FALSE: (xy)' == x' + y' 2. True/False: (x + y)' == x' + y' In English: "NOT(red OR jello) == NOT red OR NOT jello" ? FALSE: (x + y)' == x'y' 3. Using deMorgan, write a simplified expression for the Boolean complement of the logic function F(a,b,c) = a(b' + c) F'(a,b,c) = (a(b' + c))' : complement = a' + (b' + c)' : deMorgan = a' + (b')'c' : deMorgan = a' + bc' : identity 4. Using deMorgan, write a simplified expression for the Boolean complement of the logic function F(a,b,c) = a + (b'c) F'(a,b,c) = (a + (b'c))' : complement = a'(b'c)' : deMorgan = a'(((b)')'+ c') : deMorgan = a'(b + c') : identity = a'b + a'c' : distribute (optional) 5. Show that x = xy + xy' using a Boolean truth table. x y xy xy' xy + xy' ---------------------------------------------------- 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 1 6. Prove that x = xy + xy' using a chain of simple Boolean Identities. xy + xy' = x(y + y') = x(1) : identity = x : identity 7. Construct a Boolean function F(a,b) that implements the XOR operator using only AND, OR, and NOT logic. (The truth table for the simple function should be the same as the XOR truth table.) F(a,b) = a ^ b : this is XOR = ab' + ba' : Solution 1: using only AND, OR, and NOT = (a + b)(ab)' : Solution 2: using only AND, OR, and NOT 8. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "Call the delete routine unless: the product_id is zero or the product_class is 'important'." if ( ! (id == 0 || class == 'important' ) ) delete(); use deMorgan to get if ( id != 0 && class != 'important' ) delete(); 9. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "A record is one where the modify_date date is less than a year old and the account_balance is bigger than zero. If the record is NOT current, call the delete routine." if( ! ( md < YEAR && bal > 0 ) ) delete(); use deMorgan to get if ( md >= YEAR || bal <= 0 ) delete(); *** Memory Section *** 10. What do the acronyms RAM and ROM stand for? RAM = Random-Access Memory ROM = Read-Only Memory 11. Is the BIOS in your computer stored in RAM or ROM? In ROM (probably in EEPROM). 12. 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 13. 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. 14. 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. 15. 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. 16. 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. 17. What is the basic feature that Virtual Memory enables? It enables programs to run that are larger than the available memory. 18. 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. 19. 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 processor 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. 20. 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. 21. 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 Page Faults. 22. What is virtual memory "thrashing"? The active part of a program doesn't fit in the physical memory available, so that the program is constantly generating Page Faults and not getting any useful work done. 23. With reference to Chapter 6 Slides 46-47, describe what happens when the CPU generates the 13-bit address 1004h: That address refers to Virtual Page "100", which 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, and then update the page table. *** Internet Section *** 24. IPv4 addresses are stored as 32-bits and sent around the Internet in Big Endian format, where each of the four "quads" is stored in its own byte. Encode the dotted-quad IP address 129.65.33.17 as a 32-bit hexadecimal number as it would be sent on the Internet: 129 = 81h 65 = 41h 33 = 21h 17 = 11h 129.65.33.17 = 81412111h (Big-Endian) 25. Which of the following URLs are always identical to the URL http://idallen.com/address.html: a) HTTP://idallen.com/address.html b) http://IDALLEN.COM/address.html XXX not this one: http://idallen.com/ADDRESS.HTML XXX 26. Which of the following email addresses are always identical to the email address idallen@idallen.ca: XXX not this one: a) IDALLEN@idallen.ca XXX b) idallen@IDALLEN.CA 27. Which of the following cannot ever be valid dotted-quad IP addresses? a) 1.2.3.4 b) 0.0.0.0 c) 192.0.32.10 XXX INVALID d) 292.0.32.10 XXX e) 255.255.255.255 XXX INVALID f) 255.255.255.256 XXX 28. True/False: If two machines with IP addresses 192.0.32.10 and 192.0.32.11 are on the same network, they will always have similar DNS names, e.g. host1.example.com and host2.example.com . FALSE: Adjacent addresses do not necessarily mean similar DNS names. 29. True/False: If two machines have similar DNS names, e.g. host1.example.com and host2.example.com, their IP addresses will always be on the same or similar networks, e.g. 192.0.32.10 and 192.0.32.11. FALSE: Similar names do not necessarily mean similar network addresses. 30. How many bits are used to store the new IPv6 Internet addresses? 128 bits. The square root of the number of atoms in the universe. 31. In Class Notes file 140_attack.txt: Decode the obfuscated IP address assigned in hexadecimal to the $perm variable into standard Internet numeric dotted-quad form. $perm="\x32\x30\x33\x2e\x35\x39\x2e\x31\x32\x33\x2e\x31\x31\x34"; 2 0 3 . 5 9 . 1 2 3 . 1 1 4 Give the dotted-quad IP address here: 203.59.123.114 209 = CBh 59 = 3Bh 123 = 7Bh 117 = 72h Give the 32-bit hexadecimal form here: 0xCB3B7B72 (Big-Endian) *** Using the Course Linux Server *** 32. Use the "whois" command to find out who owns the above IP address. In what country is that IP address registered? $ whois 203.59.123.114 [...] country: AU 33. The attack email listed in 140_attack.txt is said to come from an IP address provided by Verizon. Give the "host" and "whois" command lines that show this to be true, including only the relevant lines of output from each command: $ host modaintl.com modaintl.com has address 68.236.170.186 $ whois 68.236.170.186 Verizon Internet Services Inc. VIS-68-236 (NET-68-236-0-0-1) [...] 34. The Perl script being fetched for the attack is said to come from a German IP address. Give the "host" and "whois" command lines that show this to be true, including only the relevant lines of output from each command: $ host linux-echo.de linux-echo.de has address 217.160.205.164 $ whois 217.160.205.164 [...] Country: DE 35. Use the "traceroute" command to trace the packet routes between this machine and the German address. (The trace may not be able to trace all the way to the destination - some trace points will be asterisks instead of host names.) Copy and paste the traceroute here: $ whois 217.160.205.164 [...] Country: DE $ traceroute 217.160.205.164 traceroute to 217.160.205.164 (217.160.205.164), 30 hops max, 60 byte packets 1 * * * 2 * * * 3 vl-201.gw03.rchrd.phub.net.cable.rogers.com (66.185.90.113) 15.671 ms 16.243 ms 16.334 ms 4 ge0-0-0.gw01.rchrd.phub.net.cable.rogers.com (66.185.83.181) 15.909 ms 15.930 ms 15.979 ms 5 xe6-1-2.gw02.bloor.phub.net.cable.rogers.com (69.63.248.157) 25.298 ms 25.436 ms 25.484 ms 6 69.63.250.134 (69.63.250.134) 21.746 ms 12.944 ms 16.537 ms 7 69.63.248.97 (69.63.248.97) 38.313 ms 38.464 ms 38.369 ms 8 eqx-ny3.tlx.nyc.us.oneandone.net (206.223.131.23) 38.332 ms 40.215 ms 43.549 ms 9 te-3-3.bb-b.cr.chi.us.oneandone.net (74.208.6.81) 51.370 ms 51.431 ms 51.205 ms 10 ae-0-0.bb-a.cr.chi.us.oneandone.net (74.208.1.53) 47.460 ms 40.207 ms 43.258 ms 11 so-2-0.bb-b.fra3.fra.de.oneandone.net (212.227.120.13) 154.962 ms 154.831 ms 151.592 ms 12 ae-2.bb-d.fra3.fra.de.oneandone.net (212.227.120.44) 148.646 ms 146.566 ms 151.185 ms 13 te-2-3.bb-d.bs.kae.de.oneandone.net (212.227.120.29) 154.358 ms 154.826 ms 148.941 ms 14 te-2-1.gw-distp-a.bs.ka.oneandone.net (212.227.116.210) 148.819 ms 150.677 ms 154.357 ms 15 * * * 16 * * * 17 * * * 18 * * * 19 * * * 20 * * * 21 * * * 22 * * * 23 * * * 24 * * * 25 * * * 26 * * * 27 * * * 28 * * * 29 * * * 30 * * * -- | 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/