COS122 Tutorial 7 - Oct 5-6, 2023.pdf

TUTORIAL 7 CHAPTER 8 EUNICE N K HAMMOND COS 122 | OPERATING SYSTEMS CHAPTER 8 VIRTUAL MEMORY  TUTORIAL OUTLINE  Virtual Memory  Memory Management Policies  Fetch Policy  Placement Policy  Replacement Policy Algorithms  Cleaning Policy  Tutorial 7 Questions & Solutions...

TUTORIAL 7 CHAPTER 8 EUNICE N K HAMMOND COS 122 | OPERATING SYSTEMS CHAPTER 8 VIRTUAL MEMORY  TUTORIAL OUTLINE  Virtual Memory  Memory Management Policies  Fetch Policy  Placement Policy  Replacement Policy Algorithms  Cleaning Policy  Tutorial 7 Questions & Solutions Chapter 8  See links at the end for further reading VIRTUAL MEMORY  A storage allocation scheme in which secondary memory can be addressed as though it were part of main memory.  Useful for user programs with small physical memory BENEFITS  Can write large programs  Less I/O, thus faster & easier swapping  More physical memory available Real world scenarios, Virtual Memory, Tutorialspoint  Error handling code  Over sized arrays Chapter 8 HELPFUL LINK ON THE CONCEPT OF VIRTUAL MEMORY https://www.indeed.com/career-advice/career-development/virtual- LINK: memory#:~:text=Example%20of%20virtual%20memory&text=A%20business%20o wner%20uses%20their,and%20a%20content%20management%20system VIRTUAL MEMORY TERMINOLOGY Chapter 8 QUESTION 1 Chapter 8 How does the use of virtual memory improve system utilisation? QUESTION 1: SOLUTION Chapter 8 The use of virtual memory improves system utilisation in the following ways: a. More processes may be maintained in main memory: The use of virtual memory allows the loading of only portions of a process into the main memory. Therefore, more processes can enter the system, thus resulting in higher CPU utilisation. b. A process may be larger than all of main memory: The use of virtual memory theoretically allows a process to be as large as the disk storage available, without taking heed of the size of the main memory. MEMORY MANAGEMENT POLICIES FETCH POLICY PLACEMENT POLICY REPLACEMENT POLICY CLEANING POLICY Chapter 8 MEMORY MANAGEMENT POLICIES FETCH POLICY determines when a page should be brought into main memory Two alternatives: Demand Pre- paging paging - a page is brought into - pages other than the one demanded main memory only when by a page fault are brought in a reference is made to a - efficient if pages are stored in a location on that page contiguous manner - inefficient if the pages brought in are not referenced Chapter 8 MEMORY MANAGEMENT POLICIES PLACEMENT POLICY Important design issue for segmentation Irrelevant for paging Determines where in real memory a process piece is to reside Chapter 8 MEMORY MANAGEMENT POLICIES REPLACEMENT deals with the selection of a page in main memory to POLICY be replaced when a new page must be brought in Replacement Policy Algorithms LEAST FIRST-IN OPTIMAL RECENTLY CLOCK FIRST-OUT USED Chapter 8  REPLACEMENT POLICY ALGORITHMS e.g. 2, 3, 4, 2, 5, 2, 4, 3,… 2 2 2 2 2 3 3 3 5 Optimal 4 4 4 … F Selects for replacement that page for which the time to the next reference is the longest. Chapter 8  REPLACEMENT POLICY ALGORITHMS CHALLENGE difficulty in implementation Least Recently Used (LRU) Possible solution: tag each page with the time of its last reference; replaces the page in memory that has by the principle of locality not been referenced for the longest time PROBLEM overhead the page least likely to be referenced in the near future Chapter 8  REPLACEMENT POLICY ALGORITHMS replace the page that simplest to implement has been in memory but performs the longest relatively poorly First-In-First-Out (FIFO) treats the page frames allocated to a process as a circular buffer, and pages are removed in round-robin style Chapter 8 REPLACEMENT POLICY ALGORITHMS Clock requires the association of an additional bit with each frame, referred to as the use bit Chapter 8  REPLACEMENT POLICY ALGORITHMS Clock When a page is first loaded: use bit = 1 When the page is subsequently referenced (after the reference that generated the page fault): use bit = 1 When a page is replaced, the pointer is moved to the next frame When a page needs to be replaced, the OS scans the buffer to find a page with a use bit = 0 Each time a frame with use bit = 1 is encountered, it resets it to 0 A frame with use bit = 0 will be the candidate as a replacement for the incoming page If all the frames have a use bit = 1, then the pointer will make one complete cycle through the buffer, set all the use bits to 0, and stop at its original position. It will replace the page in that frame (original position). Chapter 8  REPLACEMENT POLICY ALGORITHMS Clock Incoming Page to replace: Page 727 Start at Frame 2 | Page 45 Use = 0 Use bit = 1, set to 0 Use = 0 Next Frame 3 | Page 191 Use bit = 1, set to 0 Next: Frame 4 | Page 556 Use bit = 0, CANDIDATE FOR SWAP! Chapter 8  REPLACEMENT POLICY ALGORITHMS Clock Chapter 8 REPLACEMENT POLICY ALGORITHMS Chapter 8 MEMORY MANAGEMENT POLICIES CLEANING opposite of the fetch policy POLICY concerned with determining when a modified page should be written out to secondary memory Two alternatives: Demand Pre- Cleaning Cleaning A page is written out to secondary Allows that pages can be memory only when it has been written out in batches selected for replacement Chapter 8 QUESTION 2 Chapter 8  QUESTION 2: SOLUTION – A. FIFO Chapter 8 String: a, b, d, c, b, e, d, b, d, b, a, c, b, c, a, c, f, a, f, d. FIFO: replace the page that has been in memory the longest Assumptions: 3 frames, all initially empty Page Stream Address a b d c b e d b d b a c b c a c f a f d a a a a c c c c c d d d d b b b b b b b Frames b b b b b e e e e e a a a a a a f f f d d d d d d b b b b c c c c c c a a Faults F F F F F F F F F F  QUESTION 2: SOLUTION – A. FIFO Chapter 8 FINAL TABLE (FIFO) Page Stream Address a b d c b e d b d b a c b c a c f a f d a a a c c c c c d d d d b b b b b b b d Frames b b b b e e e e e a a a a a a f f f f d d d d d b b b b c c c c c c a a a Faults F F F F F F F F F F  QUESTION 2: SOLUTION – B. OPTIMAL Chapter 8 String: a, b, d, c, b, e, d, b, d, b, a, c, b, c, a, c, f, a, f, d. OPTIMAL: replaces the page for which the time to the next Assumptions: 3 frames, all initially empty reference is the longest. Page Stream Address a b d c b e d b d b a c b c a c f a f d a a a a c c e e e e e a a a a a a a a a Frames b b b b b b b b b b b b b b b b f f f d d d d d d d d d d c c c c c c c c Faults F F F F F F  QUESTION 2: SOLUTION – B. OPTIMAL Chapter 8 FINAL TABLE (OPTIMAL) Page Stream Address a b d c b e d b d b a c b c a c f a f d a a a c c e e e e e a a a a a a a a a d Frames b b b b b b b b b b b b b b b f f f f d d d d d d d d d c c c c c c c c c Faults F F F F F F  QUESTION 2: SOLUTION – C. LEAST RECENTLY USED (LRU) String: a, b, d, c, b, e, d, b, d, b, a, c, b, c, a, c, f, a, f, d. LRU: replace the page that is least likely to be referenced in the near future Assumptions: 3 frames, all initially empty Page Stream Address a b d c b e d b d b a c b c a c f a f d a a a a c c c d d d d d c c c c c c c c Frames b b b b b b b b b b b b b b b b f f f d d d d e e e e e a a a a a a a a a Faults F F F F F F F Chapter 8  QUESTION 2: SOLUTION – C. LRU Chapter 8 FINAL TABLE (LRU) Page Stream Address a b d c b e d b d b a c b c a c f a f d a a a c c c d d d d d c c c c c c c c d Frames b b b b b b b b b b b b b b b f f f f d d d e e e e e a a a a a a a a a a Faults F F F F F F F QUESTION 2: COMPARISON Chapter 8 FIFO vs OPTIMAL vs LRU Page Faults: FIFO has highest number of page faults and Optimal has the lowest. Page faults in FIFO occur more frequently since the pages that are in the memory for the longest time are replaced without regarding the fact that they may have been used quite frequently Since this problem is overridden in LRU, the latter shows a better performance. QUESTION 3 Chapter 8 QUESTION 3: SOLUTION – 3 FRAMES Chapter 8 Assumptions: 3 frames, all initially empty FIFO: replace the page that String: A; B; C; D; A; B; E; A; B; C; D; E has been in memory the longest Page Stream Address A B C D A B E E A B C D EE A A A A D D D E E E E E Frames B B B B A A A A A C C C C C C B B B B B D Faults F F F F F F 1 2 3 4 5 6 7 8 9 9 transfers QUESTION 3: SOLUTION – 4 FRAMES Chapter 8 Assumptions: 4 frames, all initially empty FIFO: replace the page that String: A; B; C; D; A; B; E; A; B; C; D; E has been in memory the longest Page Stream Address A B C D A B E E A B C D EE A A A A A A A E E E E D Frames B B B B B B B A A A A C C C C C C C B B B D D D D D D D C C Faults F F F F F F 1 2 3 4 5 6 7 8 9 10 10 transfers REFERENCES  HTTPS://WWW.TUTORIALSPOINT.COM/OPERATING_SYSTEM/OS_VIRTUAL_MEMORY.HTM  HTTPS://WWW.GEEKSFORGEEKS.ORG/VIRTUAL-MEMORY-IN-OPERATING-SYSTEM/  HTTPS://WWW.STUDYTONIGHT.COM/OPERATING-SYSTEM/VIRTUAL-MEMORY FURTHER READING:  HTTPS://WWW.INDEED.COM/CAREER-ADVICE/CAREER-DEVELOPMENT/VIRTUAL- MEMORY#:~:TEXT=EXAMPLE%20OF%20VIRTUAL%20MEMORY&TEXT=A%20BUSINESS%20OWNER%20USES%20THEIR,A ND%20A%20CONTENT%20MANAGEMENT%20SYSTEM. THANK YOU. QUESTIONS? [email protected]