UNIVERSITY OF HOUSTON Department of Computer Science COSC 4330--Fundamentals of Operating Systems FINAL EXAMINATION July 20, 1995 This exam is closed book. You can have one sheet of notes. 1. Consider the following three processes: process one: process two: process three: __________ P(&beta) __________ __________ __________ P(&delta) prepare(&a); prepare(&b); combine(a, b); V (&gamma) __________ V(&alpha); __________ __________ __________ Add the necessary semaphore calls to guarantee: (a) that process three will never executed until both processes one and two have completed, and (b) neither process one nor process two can be restarted until process three has completed. (4x4 points). process one: process two: process three: P(&alpha); P(&beta); P(&gamma); __________ __________ P(&delta); prepare(&a); prepare(&b); combine(a, b);; V (&gamma); V(&delta); V(&alpha); __________ __________ V(&beta);_ What should be the initial values of the four semaphores? (4x1 points) alpha = _1__ beta = _1__ gamma = _0___ delta = _0__ 2. A virtual memory system restricts the virtual address space of every process to 16 Megabytes. Given that (a) the system page size is four kilobytes, and (b) each page table entry occupies four bytes, what is the maximum size of a page table? (5 points) The maximum number of pages in a process is given by: 16M/4K= 4,096 Since each page table entry occupies 4 bytes, a page tabble will 4,096*4 bytes = 16 Kbytes 3. Which deadlock prevention method should you use whenever you have the choice between denying the hold and wait condition and denying the circular wait condition? (5 points) Denying the circular wait conction should be used because it is the less restrictive technique. Justify your answer in a few lines. (5 points) 4. A small system has a virtual memory with a 32 bit virtual address space and a page size of 4 kilobytes. Assuming that there are normally 50 processes loaded into main memory, give a worst case estimate for the memory space lost due to internal fragmentation? (5 points) In the worst case, the last page of each process would exactly contain one byte. Hence the total waisted space would be equal to 50*4,095 bytes, that is around 200 Kbytes. What would be a more reasonable estimate and why? (5 points) It is more reasonable to assume that ON THE AVERAGE the last page of each process would be HALF FULL. The toal waisted space would then be equal to 50*4,096/2 = 100 Kbytes. 5. What is the major disadvantage of letting the operating system handle TLB misses? (5 points) What should be done to limit the impact of the problem? (5 points) If the OS handles TLB misses, each miss result in TWO CONTEXT SWITCHES. Since TLB missses become so expensive, we should increase the HIT RATIO of the TLB in order to have LESS MISSES. 6. What is the major difference between a signal operation on a monitor condition and a V() operation on a semaphore? (5 points) A signal leaves no trace if no other monitor procedure is ready to catch it using a wait. A V(...) that does not unblock a process doing a V(...) increments by one the value of the semaphore. 7. What are (a) the major advantage and (b) the major disadvantage of inverted page tables? (2x5 points) (a) Inverted page tables occupy less space than conventional page tables since therere is one entry per page frame, that is per page loaded in main memory. (b) Since each page frmae can only belong to one process at a time, it is harder to implement shared meory. 8. Is it likely that we will ever see a virtual memory system that will not have a dirty bit? Briefly justify your answer. (5 points) No, the virtual memory needs to know if a page being expelled must be witten back to disk ("dirty" pagethat has been modified) or can be disposed of ("clean" unmodified pages). 9. What is the main reason for grouping several logical records into one physical record? (5 points) To bring several logical records in memory in a single I/O operation. 10. How does the UNIX file system implement access control lists? (6 points) What is the major limitation of this approach? (4 points) The UNIX access control list of a file contains the three possible rights (read, write or execute) of three groups of users (the owner of the file, all users specified in the "/etc/group" entry associated with the group-ID of the file and all other users). The major disadvantage of the approach is that users cannot create group entries themseleves and must ask the system administrator to create one for them. 11. A well-tuned UNIX file system has a block size of 4 kbytes. Assuming that i-nodes are always cached in main memory, give a rough estimate of the average number of disk accesses per block when accessing sequentially a 512 Mbyte file. (5 points) ____________ disk accesses per block The total size of the file is 512M/4K=128K or 2**17 blocks To access the first 12 blocks will require 1 disk access to fetch the i-node (which will remain cached) and 12 disk accesses to access the blocks themselves. To acccess the next 1024 blocks will require 1 disk access to fetch the first indirect block (which will remain cached ) and 1024 disk accesses to access the blocks themselves. To acccess the remaining (128K - 1024 - 12) blocks will require 1 disk access to fetch the second indirect block (which will remain cached), 127K/1024 =127 disk accesses to access the second level indirect blocks and (127K - 12 )disk accesses to access the blocks themselves. The grand total is: 1 + 12 + 1024 +1 + 1 + 127 + (128K -1024 -12) = 128K + 130 that is more or less 128K. --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. ----------------------------------------------------------------