This exam is open-book, open-notes, open-computer, open-Internet, but closed-other-people. You may, however, ask Jeff Ondich questions.

1. (10 points) As we have seen, a binary semaphore can be used to give a process or thread exclusive access to memory it shares with other processes or threads. Binary semaphores can also be used for various kinds of synchronization in the absence of shared memory.

   For this problem, you will use as many binary semaphores as you see fit to force a particular kind of synchronization between three threads.

   To get started, take a look at mutexTester.c. This program shows you how to spawn a child thread and how to allocate and manipulate a mutex_t variable (that is, a binary semaphore).

   Now write your own program that spawns two child threads, say Child 1 and Child 2. Each thread (including the parent thread) should then enter an infinite loop, printing an identifying message such as "Hi, I'm Child 1." The trick is that your program should print out the identifying messages in the order: Parent, Child 1, Parent, Child 2, Parent, Child 1, Parent, Child 2, etc. You may use as many mutex_t variables as you wish, but no other local or global variables of any kind.

   Please submit a paper copy of your code with your exam, and an electronic copy via HSP. You should feel free to make your identifying messages more interesting than mine.
   
   

2. (10 points) [Adapted from problems in Chapter 7 of Computer Organization and Design, 2nd edition David Patterson and John Hennessy, Morgan Kaufmann 1998.] Suppose that we are using a 2-level page table system in which each second-level page table takes up exactly one page, and that we have a 32-bit virtual address space with 4KB pages and 4 bytes per page table entry.
   • How many bytes will each program need to use to store the first-level page table (which must always be in memory)?
   • Assuming that exactly one second-level page table is in memory and exactly half of its entries are valid, how many bytes of memory in our virtual address space actually reside in physical memory?
   • Why must the first-level page table always be in memory? What would happen if it weren't?
   
   
   
3. (10 points) There is a file in my account called thisfile.txt (more precisely, /private/Net/turing/disk1/Accounts/fac/jondich/tmp/thisfile.txt).
   • Describe what happens within the file system when I execute the UNIX command "cp thisfile.txt thatfile.txt" while in my tmp directory.
   • Do the same for the command "mv thisfile.txt thatfile.txt". Assume that I do the mv command after the cp.
   To provide you with more information about the UNIX file system, i-nodes, etc., I have put The Design of the UNIX Operating System by Maurice J. Bach on closed reserve at the library, and another copy of Bach and Advanced Programming in the UNIX Environment by W. Richard Stevens on reserve in the Math Skills Center.
   
   
4. (6 points) Were you paying attention to those presentations? Match the following statements to the operating systems to which they apply.

   BeOS DOS MacOS NeXTStep/Rhapsody VMS Windows 95 Windows NT

   Based on the CMU Release 2.0 of the Mach operating system. Any process can kill any other process. A process can use at most 1Mb of memory, of which about a third is reserved for device drivers and other OS-related stuff. Most dynamic memory allocation uses "handles" (pointers to pointers) to enable the OS to compact the "heap." Uses a 2-level paged virtual memory system. Page states include "valid," "bad," "free," "in transition," and "standby." Started development in 1990. A process called PIXSCAN messes with other processes' priorities to try to optimize scheduling.