Purpose The purpose of this assignment is to help you learn more about page repl
ID: 3712454 • Letter: P
Question
Purpose
The purpose of this assignment is to help you learn more about page replacement strategies.
Brief Introduction
You have devised a new page-replacement algorithm that you think may be optimal. In some test cases, Belady’s anomaly occurs. Is the new algorithm optimal? Explain your answer.
Segmentation is similar to paging but uses variable-sized “pages”.
Define two segment-replacement algorithms based on FIFO and LRU page-replacement schemes for segmentation. Remember that since segments are not the same size, the segment that is chosen to be replaced may not be big enough to leave enough consecutive locations for the needed segment. Consider strategies for systems where segments cannot be relocated, and those for systems where they can.
Explanation / Answer
No. An optimal algorithm will never suffer from Belady’s anomaly because according to the definition an optimal algorithm replaces the page that will not be used for the longest time. Belady’s anomaly occurs when a page-replacement algorithm removes a page that will be needed in the near future. An optimal algorithm is not supposed to select such a page.
a. FIFO. Search for the first segment that is large enough to accommodate the incoming segment. If relocation can not be done and no one segment is large enough, select a combination of segments such that their memories are contiguous, which are “closest to the first of the list” and which can accommodate the new segment. If relocation can be done, rearrange the memory so that the first N segments large enough for the incoming segment are contiguous in memory. Add remaining space to the free-space list in both cases.
b. LRU. Search the segment that has not been used for the longest period of time and which is large enough, adding any remaining space to the free space list. If no segment is large enough, select a combination of the “oldest” segments that are contiguous in memory (if relocation is not available) and that are large enough. If relocation is available, rearrange the oldest N segments so that they become contiguous in memory and replace those with the new segment.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.