Operating Systems Prof. Practice Final Exam Page 1 Name________________________________
PLEASE WRITE YOUR NAME ON ALL SHEETS. Please start your answer for each question on the sheet where the question appears. You may use the backs of the question sheets to continue your answers. You may also use the blank sheet at the end to fur- ther continue your answers. Scrap paper is available. Good Luck!
1A (4 points). Define the seek time for a disk access.
1B (6 points). Assume a disk with 400 cylinders is accessing cylinder 50 and just accessed cylinder 51 a few miliseconds ago. Fur- ther assume that the FIFO queue of pending requests is
Copyright By PowCoder代写 加微信 powcoder
20, 60, 220, 250, 190.
What order will the pending requests be satisfied using the Circular Scan disk-scheduling policy? Using the SSTF disk-scheduling algorithm?
1C (5 points). What are the advantages of ¡®¡®direct memory access (DMA)¡¯¡¯ over ¡®¡®programmed I/O¡¯¡¯.
1D (10 points). MS-DOS uses a linked list of disk blocks for each file. The links are stored in an in-memory FAT (File Allocation Ta- ble) not in the blocks themselves. Unix uses an ¡®¡®inode¡¯¡¯ based system that we studed in class. Assume each system uses disk blocks of size 512 bytes. Consider a 1MB (i.e., 2048 block) file stored using each of these methods. What is required to read the last byte using each method? What is required to insert a new block (i.e., 512 new bytes) at the front of the file in each system? Make espe- cially clear all I/Os that are required.
Operating Systems Prof. Practice Final Exam Page 2 Name________________________________
2A (5 points). Draw a resource allocation graph (also called a reusable resource graph) that represents a deadlock state. Your graph must contain at least two resources and at least two tasks. Each resource must contain 3 units.
2B (5) points). Of course when execution started there were no arcs in the resource allocation graph. Give a scenario starting from this initial condition of no arcs and ending in the graph you gave for 2A. That is, tell what requests and releases occur and in what order. For this part you should assume a naive (i.e., optimistic) resource manager that grants every request as soon as it can.
2C (5 points). Recall that the Banker¡¯s algorithm for resource allocation never enters a deadlocked state like the one in part A. Con- sider the scenario you gave for part B and tell at what point the Banker¡¯s algorithm will depart from the scenario. That is, indicate the first request that the Banker¡¯s algorithm will refuse to grant that the optimistic manager did grant. Assume each process has a claim (not a request) for 3 units of each resource.
2D (5 points). Explain in detail why the Banker¡¯s algorithm refused to grant the request you noted in part C.
2E (5 points). Assume S and T are binary semaphores and one process X consists of the following four statements.
P(S); P(T); V(T); V(S)
There are two other processes. Process Y, which is identical to X, and process Z which is
P(T); P(S); V(S); V(T)
Would it be safer to run X and Y together or to run X and Z together? Relate your answer to the Coffman/Havender conditions for deadlock.
Operating Systems Prof. Practice Final Exam Page 3 Name________________________________
3A (5 points). Draw the standard diagram showing the five states a process can be in and the transitions between these states. Label the states and transitions (i.e., the nodes and arcs of your diagram.)
3B (5 points). Which arc(s) in your diagram change the NUMBER of processes in the system?
3C (5 points). Which processor scheduling algorithm results in the shortest average waiting time.
3D (5 points). Consider a system where all processes run for a fixed time T and then block for I/O (i.e., each CPU burst requires time T). A process switch requires time S, which is considered wasted time. For round robin scheduling with quantum Q give a formula for the CPU efficiency when Q>T. The CPU efficiency is the time the CPU is doing useful work (not process switching) divided by the total time. You may assume there are always processes in the ready list.
3E (5 points). Define, but do NOT solve, the producer-consumer problem.
Operating Systems Prof. Practice Final Exam Page 4 Name________________________________
4. Assume a system has demand paging with a page size of 4000 bytes, but does NOT have segmentation. Assume all page table entries (PTEs) are 1 word (4 bytes) long. Also assume the system does NOT have a TLB (translation lookaside buffer).
A (5 points). Define page and page frame.
B (5 points). How large (in bytes) is the page table for a 64,000,000 byte process?
C (10 points). Describe the actions that occur for a reference to byte 54321. Be sure to indicate any memory references that must occur and any I/O operations that might occur.
D (5 points). Consider a computer with four page frames and a process with 8 pages. Assume the pages are referenced in the follow- ing order 6127372163. Which of these references will cause page faults if the LRU page replacement algorithm is used. Assume the 4 frames are initially invalid, i.e. contain no pages.
Operating Systems Prof. Practice Final Exam Page 5 Name________________________________
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com