Examples of Page Replacement and Deadlock Prevention in Operating Systems

Problem 1: Page Replacement with Different Algorithms

Consider demand paging. You are given the following reference string, page replacement policy and the number of frames available. Calculate the number of page faults in each case. a. Reference String: 7 10 9 8 6 7 9 10 6 8 7 10 8 9 9 7 6 8 Algorithm: LRU # of frames: 4 b. Reference String: same as (a) Algorithm: Optimal # of frames: 4 c. Reference string: 9 10 11 12 9 10 13 9 10 11 12 13 Algorithm: FIFO # of frames: 3 d. Reference string: same as (d) Algorithm: FIFO # of frames: 4 To answer the question, write down the # of page fault, and also copy the reference string and circle all references that causes a page fault. Notice that we assume no pages exists in the frames in the beginning, thus, the initial pages being loaded into the frames should count as page faults. Another way to look at it is to assume page faults = number of times a page need to be loaded into main memory (assume nothing is there in the first place). 2. (6 points) Define “random writes” on a file to be operations where random pages of a file get updated. (E.g. the updates will be to page 1, then page 39, then page 27 etc.). Performance on random writes on large files on solid state drives has been shown to deteriorate quickly when the number of random writes on a file increases (especially if the drive is near full capacity). Suggest a reason why. 3. (6 points) Consider deadlock prevention by assigning priority to resources and requiring that resources need to be request in increasing order of priority. Will the method still works if we allow multiple resources to have the same priority (and change “increasing” to “non- decreasing”)? Why not?