COMP 2432 Operating Systems Written Assignment 2 Submission to BlackBoard Deadline: 15 April 2022
1. Page Replacement.
Consider the following reference string of length 25 generated by a process for which 3 memory frames are allocated for a process with 7 pages, 0, 1, 2, 3, 4, 5, 6. Indicate the content of the frames after each page indicated by the reference string is accessed, including the page fault. How many page faults are generated from the reference string? Answer the question based on 3 different page replacement algorithms: (a) FIFO, (b) Optimal, and (c) LRU based on stack implementation. Show the content of the stack for (c). For Optimal, there could be multiple possible answers.
0 13 5 2 4 3 2 5 6 5 12 10 2 4 1 6 2 4 3 2 6 4
Copyright By PowCoder代写 加微信 powcoder
Repeat the question with 4 memory frames.
(d) Consider the case with 3 memory frames. One would expect that when a reference string is made longer through inserting an item in between (like Question 4 in Tutorial 10), the performance could remain or get worsen. Is it possible to insert one item in the reference string that will instead reduce the number of page faults for LRU? If possible, indicate your reference string. If not possible, say so. Is it possible to insert one item in the reference string that will reduce the number of page faults for FIFO? If possible, indicate your reference string. Is it possible to insert one item in the reference string that will reduce the number of page faults for both FIFO for LRU? If possible, indicate your reference string. If not possible, say so.
2. Alternative Page Replacement.
Optimal looks into the future. LRU attempts to approximate Optimal by putting a mirror at the current moment and uses the history to predict the unknown future. Kevin notices that history repeats itself that they are bringing misery to all their villain bosses. He suggests that year 2022 should look like year 2012; then year 2023 could be predicted from year 2013; thus 2031 can be predicted from 2021; finally, 2032 can be predicted from 2022. This prediction is based on a 10-year cycle. However, he does not know how to predict 2033, since 2023 is in future. Stuart suggests that since 2013 has been used to predict 2023, he suggests to use older information of 2003 to wrap around to predict 2033, and use 2004 to predict 2034, and so on. This is depicted in the diagram below, making use of a past 10-year period to predict a future 10-year period.
2003 … 2011 2012 2013 … 2021 2022 2023 … 2031 2032 2033 …
Bob comes and asks a question that he cannot use information of 1999, since all historical information before 2000 had been destroyed by the Millennium Bug that he himself released accidentally in one of their actions with the villains. Kevin replies that this prevents prediction beyond year 2042 and that year 2043 cannot be predicted. But that does not matter, since Unix systems will face a problem in 2038 anyway. In general, prediction can be based on a period of P (P-year cycle) and P = 10 (10-year cycle) in this example. This observation is applied to approximate Optimal in this KBS algorithm, named in honor of the three. Please watch out that the history used to predict the future will change over time.
Apply KBS algorithm on the reference string in Question 1 for 3 memory frames, by selecting P = 9 and P = 4 respectively. Indicate the page faults. Repeat the question with 4 memory frames. Note that both LRU and KBS are similar in philosophy, in that LRU attempts to approximate Optimal by considering “history is like a mirror” and KBS attempts to approximate Optimal by considering “history repeats itself”. How does KBS compare with LRU in terms of page fault performance in this case? Note that it is helpful as a working step to write down the “predicted future” for each page reference in determining the frame to be replaced.
3. Deadlock Avoidance.
(a) Show that the request Req1 on the left side can be granted with respect to the resource allocation state with deadlock avoidance. Give a possible safe sequence after the pretended allocation and indicate the number of possible safe sequences.
(b) After the request by P1 is satisfied, another process Px apologizes that it makes a mistake in under- reporting its maximum need in one of the resource types X by one. Due to communication noise in the network, only the type of the resource X under-reported is received by the operating system, and the identity of Px is corrupted. However, the operating system can still mange to conclude that the corrected resource allocation state upon adjusting for this under-reporting remains safe. Determine the possible resource type X. Explain how you arrive at your answer.
(c) After a while, Px comes back and reports to the operating system that its original report on maximum need was correct and that the mistake of under-reporting is a false alarm. Back comes another report by process Py apologizing that it over-reports its maximum need on resource D by 1, but under-reports its maximum need in another resource Y (Y D) by one. Knowing the identify of Py, the operating system is happy to conclude that the corrected resource allocation state upon adjusting for the combined over- reporting and under-reporting remains safe. Determine the possible identities of Py. Explain how you arrive at your answer.
Q3 Allocation Max Q4 Allocation Request ABCDABCD ABCDABCD
P0 2 3 2 2
P1 2 0 1 0
P2 1 0 1 1
P3 2 4 3 2
P4 1 0 0 1
P5 0 1 1 1
Avail 1111 Req1 0 1 0 0
4. Deadlock Detection.
4 3 3 5 P0 3 3 3 3 P1 2 0 1 2 P2 4 5 6 7 P3 2 3 2 2 P4 1 1 1 2 P5
2 3 2 2 2 1 1 0 1 0 1 1 2 4 3 2 1 0 0 2 1 1 1 1
1 2 3 4 4 3 2 1 2 0 1 2 1 2 2 1 2 3 2 2 1 0 0 1
(a) Show that the resource allocation state on the right side is not involved in a deadlock. Indicate the number of possible completion sequences.
(b) Suppose that a process Px reports to the oprating system that it has made a mistake in its request: there should be one fewer B and one more C in the original request. The operating system has to announce a bad news that the system is now deadlocked. Determine the identity of Px and explain your answer.
(c) Px apologizes for its false alarm and that its original requests are correct. Now another process Py reports an even worse mistake: there should be two fewer Y and two more Z in the original request. The operating system regrets to announce that there is now a deadlock, and resource type A is involved in this mis- reporting case by Py to yield a deadlock. Determine the identity of Py and explain your answer. Note that you can eliminate some candidates. Py cannot be P5, since Y cannot be A, B, C or D (impossible to have two fewerY).Similarly,ifPy isP0,YcannotbeAbutmightbeB,CorD.IfPy isP1,YcannotbeD.IfPy isP2, Y cannot be B or C.
Avail 1 1 0 1
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com