2/26/2018 Practice Midterm Answers
Practice Midterm Answers
My answers are somewhat short, I would expect yours to be a little more detailed, but NOT very much more detailed.
1A. Draw the process state diagram from the notes. This diagram contains nodes (i.e. circles) labeled with the possible states for a process. It also contains arcs (i.e. arrows) showing the various state transitions possible. Label the nodes and arcs (for example one node should be labeled running and one arc should be labeled schedule.
Copyright By PowCoder代写 加微信 powcoder
1B. Shortest Job First and Preemptive Shortest First have a very favorable property. What is it? Why are they impractical for general purpose operating systems? Even if they were practical, they also have an unfavorable property that would make them unsuitable purpose systems. What is it? What would you add to these scheduling algorithms to alleviate this unfavorable property.
They minimize average turnaround/response time.
General purpose systems do not know in advance how long the process will run before blocking/terminating (called the cpu burst time in the scheduling lab).
They can easily starve processes with long burst times.
Some form of priority aging.
1C. Some arcs change the NUMBER of processes in the system. Which arcs are these and what system calls do they correspond to.
The arcs are create and terminate and the system calls (in unix) are fork() and exit(). 2A. Define, but do NOT solve the Readers Writers problem.
Two classes of processes.
Readers, which can work concurrently.
Writers, which need exclusive access.
Must prevent 2 writers from being concurrent.
Must prevent a reader and a writer from being concurrent. Must permit readers to be concurrent when no writer is active.
2B. Some systems simply treat the readers writers problems as critical section problems and hence the implementation simply use P and V. What requirement of the Readers Writers problem does this implementation not satisfy?
Just using P and V does not permit readers to be concurrent even when there is no writer present.
3. Consider the following set of processes) run using RR scheduling with q=3. All times are in milliseconds and context switching takes zero time. The CPU time (column TWO is the total time required for the process. The creation time (column THREE) is the time when the process is created. So P1 is created when the problem begins and P2 is created 4 milliseconds later. If ties occur use the lab 2 tie-breaking
file:///allan/gottlieb/courses/os202/exams/mid/practice/practice-midterm-long-ans.html 1/4
2/26/2018 Practice Midterm Answers
rule. After P0 has run for 5ms it blocks for 9ms and never blocks again. After P1 has run for 4ms it blocks for 6ms and never blocks again. P2 never blocks. At what time did does each process finish.
Process CPU Start Blocks Time Time after/for
P0 10 0 5 9 P1 11 4 4 6 P2 9 4 never
We did this one in class. Here is the detailed diagram from the notes. As shown, P0 finishes at 23, P1 at 30 and P2 at 21.
4A. 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.
4B. 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 4A. 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.
PQ 1 Request 3 units of R
5 Request 1 unit of S
Request 3 units of S
Request 1 unit of R
file:///allan/gottlieb/courses/os202/exams/mid/practice/practice-midterm-long-ans.html 2/4
2/26/2018 Practice Midterm Answers
4C. Recall that the Banker’s algorithm for resource allocation never enters a deadlocked state like the one in part A. Consider 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. Don’t forget that whenever you deal with Banker’s algorithm or (un)safe states, the claims of each process are important.
P claims 3 units of R and one of S Q claims 3 units of S and one of R
In line 4 of the scenario the manager granted the request of Q for 3 units of S. The banker would not grant this request. 4D. Explain in detail why the Banker’s algorithm refused to grant the request you noted in part C.
The banker pretends to grant the request and checks if the resulting state is safe. At this imagined point, all units have been allocated. From the claims the banker sees that P can request a unit of S, which the banker doesn’t have, and Q can request a unit of R, which the banker doesn’t have. So the banker cannot guarantee that all processes will complete. Indeed, in this case the banker cannot guarantee that any process will terminate.
5A. Draw a reusable resource graph that represents an UHsafe state that is NOT deadlocked. (Hopefully you remembered that the claims of the processes are important).
Same claims as in part 4C. The diagram, which follows, is the one that the banker examines when deciding whether to grant the request in 4C and 4D. More specifically, this is the state that would occur IF the banker decided to grant Q’s request for 3 units of S. However, since the state is UNsafe, the banker decides NOT to grant the request.
5B. Process A is already written and requests the printer, the plotter, the tape drive, and the robotic arm, in that order. You need to develop processes B and C. Both need the printer and the arm, B needs the tape drive, and C needs the plotter. What order should the requests be made? Why.
B should request the printer, tape, and arm in that order C should request the printer, plotter, and arm in that order
This way all the processes request the resources in order. That is the order is printer, plotter, tape, arm and each process requests what it needs in that order.
6. Consider a system containing a total of 12 units of resource R and 24 units of resource S managed by the banker’s algorithm. There are three processes P1, P2, and P3. P1’s claim is 0 units of R and 12 units of S, written (0,12). P2’s claim is (8,15). P3’s claim is (8,20). Currently P1 has 4 units of S, P2 has 8 units of R, P3 has 8 units of S, and there are no outstanding requests.
i. What is the largest number of units of S that P1 can request at this point that the banker will grant?
ii. If P2 instead of P1 makes the request, what is the largest number of units of S that the banker will grant?
iii. If P3 instead of P1 or P2 makes the request, what is the largest number of units of S that the banker will grant?
i. P1 has claim for another 8 so that is the max in theory. We must check if it is safe. If 8 are given to P1, the banker is down to 4 but can be sure that P1 will finish at which
Process claim has needs
file:///allan/gottlieb/courses/os202/exams/mid/practice/practice-midterm-long-ans.html 3/4
2/26/2018 Practice Midterm Answers
point the banker will have (4,16). This is enough to finish P2 and then the banker has
(12,16) and can finish P3. So the answer is 8.
ii. P2 has claim for another 15, but the banker has only 12 so 12 is the most in theory. Is it
safe? The banker would have (4,0) left so couldn’t guarantee any finish. Not safe. The same reasoning holds for 11, 10, …, 5. If the banker give P2 4, then P2 needs (0,11) and the banker has (4,8) left. The banker can guarantee P1 finishes. Now the banker has (4,12), which is enough for P2 and then the banker can finish P3. So the answer is 4.
iii. P3 has a claim for 12 more and the banker has 12 so that is the theoretical max. Is it
safe? The banker would have (4,0) left and couldn’t finish anyone. Not safe. The same reasoning holds for 11, 10, …, 5. If the banker gives P3 4, then P3 needs (8,8) and the
banker has (4,8). That is enough to finish P1 and then the banker has (4,12) but that is
not enough for either P2 (needs (0,15)) or P 3 (needs (8,8)). The same reasoning holds
for 4, 3, and 2. But if the banker gives 1 to P3, then the banker has (4,11) left. It can
finish P1 and then have (4,15), which can finish P2 and then it can finish P3 So the answer is 1.
7. Fill in the blanks with the appropriate technical term or phrase.
i. When a linker converts a relative address to the corresponding absolute address, we say it is ____________ the relative address.
ii. A program in execution is called ____________.
iii. The processor scheduling algorithm resulting in the smallest average waiting time is ____________.
iv. A directed graph with processes represented as circles, resources represented as squares, and requests and allocations represented as
arcs is called ____________.
v. The Banker’s algorithm ensures that the system is always in ____________
i. When a linker converts a relative address to the corresponding absolute address, we say it is RELOCATING_ the relative address.
ii. A program in execution is called A PROCESS.
iii. The processor scheduling algorithm resulting in the smallest average waiting time is SHORTEST JOB FIRST.
iv. A directed graph with processes represented as circles, resources represented as squares, and requests and allocations represented as
arcs is called A REUSABLE RESOURCE GRAPH.
v. The Banker’s algorithm ensures that the system is always in A SAFE STATE
Allan 1 (0,12) (0,4) (0,8)
P2 (8,15) (8,0) (0,15)
P3 (8,20) (0,8) (8,12)
Total (8,12)
Avail (4,12)
file:///allan/gottlieb/courses/os202/exams/mid/practice/practice-midterm-long-ans.html 4/4
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com