UNIVERSITY OF HOUSTON Department of Computer Science COSC 4330--Fundamentals of Operating Systems FINAL EXAMINATION December 15, 1994 This exam is closed book. You can have one sheet of notes. 1. Many computer systems have a decrement and branch if zero instruction like DBZ reg, addr that decrements the contents of register reg and branches to the address addr if the new value of the register is equal to zero. Use this instruction to provide a solution to the mutual exclusion problem that is not based on Peterson's algorithm. You can write your solution in any pseudo- assembly code you want but you should comment your code. Your pseudo-assembly code for entering the critical section (10 points) Your pseudo-assembly code for leaving the critical section: ( 5 points) Which register value(s) indicate that no process is inside the critical section? (5 points) [THIS QUESTION WILL NOT BE ASKED AGAIN: IT IS IMPOSSIBLE TO SHARE REGISTERS BETWEEN PROCESSES.] 2. What is wrong with the following implementation of a producer/consumer pair? (10 points) semaphore mutex = 1; semaphore nempty = NSLOTS; semaphore nfull = 0; producer() consumer() { { struct xyz item; struct xyz item; for(;;) { for(;;) { produce(&item); P(&nempty); P(&mutex); P(&mutex); P(&nfull); take(item); put(item); V(&mutex); V(&mutex); V(&nfull); V(&nempty); consume(item); } } } /* producer */ } /* consumer */ The producer process should not do the P(&mutex) before doing the P(&nfull) because it will result in a deadlock any time the producer will attempt to put one more item in a buffer that is already full. 3. Would it be a good idea to let some monitor procedures preempt other monitor procedures that are already in the monitor in order to provide faster service for high-priority processes? (4 points for the yes or no answer and 6 points for its justification) It would be a TERRIBLE idea because the preempted procedure could be in the middle of something critical. The whole idea of monitors is based on the premise that a monitor procedure should always keep control of the monitor unless it does an operation on a condition. 4. A computer system has 32 bit addresses and a maximum process address space of 64 Megabytes. Given that one page table entry occupies four bytes, what is the minimum page size that guarantees that page table size will never exceed 128 kilobytes? (10 points) The minimum page size is _________________________bytes If the page table size is never to exceed 128 Kbytes, the number of page table entries cannot exceed 2**17/4 = 2**15. This means the page number cannot occupy more than 15 bits. A process address space of 64 Megabytes or 2**28 bytes means that virtual addresses will occupy 28 bits. Since the page number cannot occupy more than 15 bits, the page offset should occupy AT LEAST 13 bits. The minimum page size is thus 2**13 = 8 Kilobytes. 5. How could you simulate the dirty bit on an architecture that lacks it? (10 points) I would simulate it by software as Berkeley Unix simulates the page referenced bit: Whenever a data page is fetched in main memory, the virtual memory will mark the page as READ-ONLY but note somewhere than the page is writable. When the process will attempt to write into the page for the first time, the MMU will detect an addressing exception and generate an interrupt. The the exception handler will then mark the page as readable AND WRITABLE instead of aborting the process. When it will be time to expel the page, we will be able to detect if it is still READ-ONLY (and thus "clean") or it has been modified and has become "dirty." What would be the cost of your solution ( 5 points) Two additional context switches per writable page being brought into main memory. 6. Which user processes will continue to be able to access a file after the owner of the file has made the file inaccessible to all user processes? ( 5 points) Those that had already opened the file and have not yet closed it. 7. Describe a page replacement policy that was specifically designed to accommodate real-time processes. (10 points) VMS allocates to each process a fixed-size partition that it manages using a FIFO policy. The pages expelled by the FIFO policy are put at the end of a large global queue from which they can be reclaimed. Having a fixed partition for each process allowed them to allocate to each real-time process enough page frames to keep the whole address space of the process in main memory and guarantee that none of its pages would ever be expelled. 8. What is the condition called thrashing and when does it occur? (10 points) Thrashing happens when there are too many processes in main memory, these processes are always stealing pages from each other and most processes are in the waiting state because the paging device cannot keep up with all page requests. 9. What would happen to the performance of a UNIX file system if the i-nodes were not cached in main memory and why? ( 10 points) Each read or write tot he disk would then require at least two disk accesses: one to get the block address from the i-node and the second to read it or write into it. --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. ----------------------------------------------------------------