While taking this exam, you may use books, computers, the Internet, your own brain, and divine inspiration (if any is available to you). Don't talk to people other than me about the content of the exam.
Have fun.
(4 points) One Linux file system uses i-nodes that contain 10 direct block pointers, 1 single-indirect block pointer, 1 double-indirect block pointer, and 1 triple-indirect block pointer. If each block is big enough to hold 1024 32-bit block pointers, what is the largest file size supported by this file system?
(8 points) Suppose we have a paged virtual memory system that uses 64-bit virtual addresses and 4KB pages.
Suppose each process has a simple one-level page table, each of whose entries requires 48 bits. How big is this page table? Do you foresee any problems with this system?
Suppose we use a two-level page table, with second-level tables that take up one page apiece, and whose entries are 48 bits long. If the top-level page table entries are also 48 bits long, how big is the top-level table? Keeping in mind that the top-level page table must be kept in physical memory, do you see any problems with this system?
Try again, this time with a three-level hierarchy. The second and third-level tables will take up one page apiece, and will consist of 48-bit entries. The top-level table will consist of 48-bit entries, too. How big is the top-level table? How many second-level tables are there? (At runtime, most of the second-level tables will not really exist, of course, but it's good to know how many there are in principle.) Has this system solved our problem?
One more time. Let's scrap the hierarchical page table altogether and try an inverted page table (see section 9.4.4 of your book).
(12 points) Tell me an input story. Pick one: mouse or keyboard. Then walk me through the sequence of events that occurs when the a mouse button gets clicked or a key gets pressed. The more detailed and precise your tale, the better (though I am not expecting more than a page or two). Provide citations for Linux code and any other sources you use.
(15 points) Using the POSIX threads library, write a 2-thread program for Linux. Once the thread spawning is done, the first thread (T1) should wait for user input. T1 should produce no output, but should shut down the whole process once the user types a q or a Q. T2 should take no input, but should generate a list of prime numbers starting at 2 and going as high as it can in the time allowed. From the user point of view, this program will generate primes until told to quit. From the source code point of view, there will be two independent pieces of code, each nearly trivial, and each with a separate responsibility.
POSIX threads, also known as pthreads, are available on our Linux systems. They are documented to one degree or another in lots of places, though I have yet to find a web site that strikes me as the authoritative home of pthreads. Recall the threads example I demonstrated in class a few weeks ago. You can get a list of man page topics with the command "apropos pthread". I also like the tutorial Getting Started With POSIX Threads, by Tom Wagner and Don Towsley. If you need more ideas, search the web and let me know if you find something good.
The quality of your prime number generation is immaterial. Make it correct, but don't worry about making it fast.
(2 points) It's almost summer time, which means it's time for me to start watching movies. Any suggestions? (Extra appreciation if you have some favorites that would be interesting for the whole family, which includes a 10-year-old and a 14-year-old.)
(10 points) The Therac-25 incident is one of the worst disasters in the history of software. You can learn all about it in An Investigation of the Therac-25 Accidents, Nancy Leveson and Clark S. Turner, IEEE Computer, Vol. 26, No. 7, July 1993, pp. 18-41. (Here's another link to the same paper.) If you wish, you may also look for other information on Therac-25 in books or on the Web.