UNIVERSITY OF HOUSTON Department of Computer Science COSC 4330--Fundamentals of Operating Systems FINAL EXAMINATION December 11, 1995 This exam is closed book. You can have one sheet of notes. 1. For each of the statements below, indicate in one sentence whether or not the statement is true or false, and why (5 points each): Peterson's solution to the mutual exclusion problem assumes that machine language instructions cannot be interrupted FALSE, it does not make ANY assumptions about the underlying hardware. Monitors are easier to integrate in an existing programming language than semaphores. FALSE, you can add semaphores to any language by adding a few system calls but you need almost a new programming language to support monitors. UNIX allows each user to select the block size of his or her files. FALSE, UNIX does not even let the user know the block size of his or her files. Without a memory management unit, processes that are swapped out and later brought back into main memory must always return to the memory location they were occupying before they were swapped out. TRUE because the starting address of the process is hard-coded in all absolute address constants. The initialization statement of a monitor is executed every time a new monitor procedure is started. FALSE, it is only executed once when the monitor itself is started. 2. Why is it a good idea to use busy waits instead of kernel- supported semaphores to ensure mutual exclusion for very short critical sections when we know that access conflicts are very unlikely? (5 points) Using busy waits is essentially betting that there will be no wait at all. In this case we will save the four context switches resulting from the two calls to P() and V(). The overhead will be of course larger if the process has to wait because a process doing busy waits will generate a LOT of busy waits. We just hope that there will be not too many of them because the critical section is very short. 3. If you had to write a monitor solution to the readers and writers problem, how many monitor procedures would you define (2 points) and what would be the tasks allocated to each procedure? (8 points) We must have at least three procedures because the read operation cannot be a monitor procedure without executing in mutual exclusion. As a result the reads must be performed OUTSIDE the monitor. The two possible solutions are -- three procedures, namely, write(), get_read_lock() and release_read_lock(); -- four procedures, namely, get_write_lock(), get_read_lock(), release_write_lock() and release_read_lock(). Their names SHOULD be self-explanatory. o. Given the six following page replacement policies: Global FIFO Clock Denning's Working Set Global LRU Mach VMS indicate the policies: (a) using a page-referenced bit: (5 points) (b) requiring too much special hardware: (5 points) (c) preventing thrashing: (5 points) (a) Clock, (b) Global LRU, Denning's Working Set (c) Denning's Working Set 5. Consider a System V UNIX file system with 13 block addresses in each i-node and a block size of 1 kilobyte. How many blocks of each file can be accessed: (a) directly from the i-node: (3 points) (b) using one level of indirection: (3 points) (c) using two levels of indirection: (3 points) (d) using three levels of indirection: (3 points) Comment briefly on your answer to (d): (3 points) (a) 10 blocks (b) 1024/4 = 256 blocks (c) (1024/4)*(1024/4) = 2**16 = 64 or 65,536 blocks (d) one is tempted to say (1024/4)**3=2**24= 16,777,216 blocks but a UNIX file cannot have more that 4 GIGABYTES, that is 4 M blocks of 1 kilobyte each. Hence the correct answer is: 4 M - 64K - 256 - 10 blocks, or if you prefer: 4,194,304 - 65,536 - 256 - 10 = 4,128,502 that is a little more that 4,000,000 blocks. 6. Why is it rarely possible to prevent deadlocks involving messages? (10 points) To prevent deadlocks, we must deny one of the four necessary conditions for deadlocks. We cannot deny the mutual exclusion nor the no preemption condition because they would amount to forcing a sender to send a message. Denying the hold-and-wait condition is also unrealistic because it will require each process to receive all its messages at once. The only condition that can be denied is the circular wait condition. However denying it requires that all messages move only in one direction. 7. What is an inverted page table? (5 points) Why is it so difficult to implement shared pages on systems using an inverted page table? ( 5 points) An inverted page table has one page table entry per page frame. The page table size is then bounded by the size of the physical memory and not by the size of the process address spaces. It is very hard to implement shared pages using an inverted page table because each page frame can only belong to one single process. 8. You have a UNIX file that should be readable and writable by you, readable by your friend Allison, and inaccessible by anyone else. What do you need to do to have these restrictions enforced by the UNIX file system? (10 points) You give tot the owner of the file the rights to read the file and write into it. You ask the system administrator to create a group containing your friend and nobody else. You change the group of your file to this group and give to the group the right to read the file. You do not give any rights to the other users. --IMPORTANT----IMPORTANT----IMPORTANT----IMPORTANT----IMPORTANT-- Please do not try to answer these questions by yourself BEFORE having a clear idea of what's on the test for which you are studying. Materials covered in each test DO VARY from semester to semester because the pace of the course can change, some materials are be added and other deleted almost every semester. ----------------------------------------------------------------