Operating Systems - Memory Management PDF

Operating Systems & Computer Architecture CT049-3-1-OS&CA Ver: VE Memory Management  Learning Outcomes At the end of this section, YOU should be able to: Describe Paging and Segmentation Perform page replacement calculations using...

Operating Systems & Computer Architecture CT049-3-1-OS&CA Ver: VE Memory Management  Learning Outcomes At the end of this section, YOU should be able to: Describe Paging and Segmentation Perform page replacement calculations using various Page Replacement Algorithms Module Code & Module Title Slide Title SLIDE 2  Topics we will cover Memory Management Logical and Physical Memory Memory Partitioning Virtual Memory Demand Paging Demand Segmentation Page fault Page replacement Page replacement algorithms First In First Out Least Recently Used Optimal Module Code & Module Title Slide Title SLIDE 3  Virtual Memory Separation of user logical memory from physical memory. Allows for large virtual memory to be provided for programmers even though physical memory is small. Programmers do not have to worry about space and writing overlay codes. Virtual memory implemented using demand paging or demand segmentation. Module Code & Module Title Slide Title SLIDE 4  Paging Physical memory is broken into fixed-sized blocks called frames. Logical memory is also broken into blocks of the same size called pages. When a process is executed, its pages are loaded into any available memory frame from the backing store. Module Code & Module Title Slide Title SLIDE 5  Paging page 0 0 1 0 page 1 1 4 1 page 0 page 2 2 3 2 page 3 3 7 3 page 2 logical memory page table 4 page 1 5 6 7 page 3 physical memory Module Code & Module Title Slide Title SLIDE 6  Demand Paging A process resides in secondary memory, usually a disk. When a process needs to be executed, it is paged to memory. The whole process is not paged, only pages that are needed are brought in. A pager decides which pages to bring into memory. Advantages:- – avoid reading pages that will not be used – decreases paging time – decreases physical memory needed Module Code & Module Title Slide Title SLIDE 7  Demand Paging Memory Secondary Storage Program A Swap Out 0 1 2 3 4 5 6 7 8 9 10 11 Program B 12 13 14 15 Swap In 16 17 18 19 Module Code & Module Title Slide Title SLIDE 8  Demand Segmentation What is Segmentation? – Segmentation is a memory-management scheme that supports a user view of memory. – A logical address space is a collection of segments. Each segment has a name and a length. – The addresses specify both the segment name and the offset within the segment. Module Code & Module Title Slide Title SLIDE 9  Demand Segmentation Most efficient virtual memory storage method. Needs significant amount of hardware requirements. Not all paging systems use segmentation. Instead of allocating pages in memory, allocate segments. Segment descriptors keeps track of segments. Module Code & Module Title Slide Title SLIDE 10  Demand Segmentation Figure 8.24 pg 275 0000 stack segment 3 1400 Limit Base segment 0 0 1000 1400 symbol 2400 subroutine 1 400 6300 table 3200 2 400 4300 segment 0 segment 4 3 1100 3200 segment 3 4 1000 4700 4300 main segment 2 SQRT Segment table 4700 program segment 4 segment 1 segment 2 5700 6300 Physical memory 6700 segment 1 Logical address space Module Code & Module Title Slide Title SLIDE 11  Shared Segmentation 0 Limit Base editor 43062 0 25286 43062 segment 0 1 4425 68348 editor data 1 segment table process P1 segment 1 68348 data 1 72773 logical memory process P1 editor Limit Base segment 0 90003 0 25286 43062 data 2 1 8850 90003 98553 data 2 segment table process P2 1298553 segment 1 physical memory logical memory process P2 Sharing of segments in a segmented memory system Module Code & Module Title Slide Title SLIDE 12  Quick Review Questions 1. How does demand paging work? 2. How does demand segmentation work? Module Code & Module Title Slide Title SLIDE 13  Follow Up Assignment 1. What is the difference between demand paging and demand segmentation? Module Code & Module Title Slide Title SLIDE 14  Page Fault A page fault occurs when:- – a process tries to use a page that is not in memory. – an operating system interrupt occurs as a result of trying to access a missing page. Module Code & Module Title Slide Title SLIDE 15  Steps in Handling Page Fault operating 3 locate page on backing store system reference 1 2 trap i backing load M store 6 page table Free restart frame instruction 5 4 reset bring in page memory table page program physical execution memory Module Code & Module Title Slide Title SLIDE 16  Page Fault Steps in handling a page fault:- – locate the missing page – find free memory frame – copy into physical memory – reset the page table – restarts the instructions Module Code & Module Title Slide Title SLIDE 17  Page Replacement What if there are no free frames? – find a frame that is not currently being used and free it. – use a page replacement algorithm to find a free frame. Module Code & Module Title Slide Title SLIDE 18  Page Replacement How to free a frame? – find a frame not currently used. – copy its contents to disk. – change the page table to indicate that the page is no longer in memory. – newly free frame can be used to store the page that resulted in the page fault. Module Code & Module Title Slide Title SLIDE 19  Page Replacement The string of memory reference is called a reference string. For a given page, we need to consider only the page number, not the entire address. Module Code & Module Title Slide Title SLIDE 20  Page Replacement For example, if we trace a particular process, we might record the following address sequence:- 0100, 0432, 0101, 0612, 0102, 0103, 0104 0101, 0611, 0102, 0103, 0104, 0101, 0610 0102, 0103, 0104, 0102, 0609, 0102, 0105 which at 100 bytes per page is reduced to the following reference string 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 Module Code & Module Title Slide Title SLIDE 21  Page Replacement frame valid-invalid bit swap 2 change to 1out O i invalid victim page O F v 4 F victim reset page 3 F table for new page swap desired backing page in store page table physical memory Module Code & Module Title Slide Title SLIDE 22  Page Replacement In the previous example page O was previously loaded into memory. Page O is now no longer needed. Page F needs to be brought into physical memory. As page O is no longer needed it becomes the victim page and is replaced with page F. Module Code & Module Title Slide Title SLIDE 23  Page Replacement Algorithms Every operating system has its own unique page replacement algorithm. In selecting a particular algorithm we want the one with the lowest page fault rate. Types of page replacement algorithms:- – First In First Out – Optimal – Least Recently Used Module Code & Module Title Slide Title SLIDE 24  First In First Out Simplest page replacement algorithm. Easily implemented. Algorithm uses the age of the page as the criteria to perform page replacement. The age of the page is the amount of time the page has spent in memory. Oldest page is the victim. All other pages are lined up in the order of highest page to be sacrificed. Module Code & Module Title Slide Title SLIDE 25  First-in-first-out (FIFO) reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1 Number of Page Faults : 15 Perform an Analysis of the First-In-First-Out (FIFO) Algorithm for the following string of memory reference addresses. Assume that there are three frames available within the memory for holding pages. Module Code & Module Title Slide Title SLIDE 26  First-in-first-out (FIFO) The disadvantage of this technique is that the oldest page could be very much in demand. When the oldest page is replaced there will be an immediate page fault. FIFO suffers from BELADY’S ANOMALY. Module Code & Module Title Slide Title SLIDE 27  BELADY’S ANOMALY BELADY was one of the pioneers of modern operating systems who did extensive studies on Page Replacement schemes. On the basis of logical thinking, as the number of memory frames are increased, the number of page faults decreases. But BELADY, after conducting extensive experiments, found that for certain memory reference strings, as the number of memory frames are increased the number of page faults increases. BELADY’S observations contradicted the commonly accepted dogma, and instead of ‘burning him on the stake’, his results were classified as BELADY’S ANOMALY. Module Code & Module Title Slide Title SLIDE 28  First-in-first-out (FIFO) 16 14 12 number of page faults 10 8 6 4 2 0 1 2 3 4 5 6 7 number of frames page-fault curve for FIFO replacement on a reference string Module Code & Module Title Slide Title SLIDE 29  Optimal Results from Belady’s anomaly resulted in a search for a new algorithm. An algorithm that provides the lowest page fault with a fixed number of frames. Does not suffer from Belady’s anomaly. Replaces the page that will not be used for the longest period of time. Difficult to implement, requires future knowledge of the reference string. Module Code & Module Title Slide Title SLIDE 30  Optimal Algorithm reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 Replace the page that will not be Number of Page Faults: 9 used for the longest period of time Perform an Analysis of the Optimal Algorithm for the following string of memory reference addresses. Assume that there are three frames available within the memory for holding pages. Module Code & Module Title Slide Title SLIDE 31  Least Recently Used Associates each page with time of when the page was last used. When a page needs to be replaced, the page that has not been used the for the longest period will be chosen. Technique of looking backwards. Module Code & Module Title Slide Title SLIDE 32  Least Recently Used reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7 Number of Page Faults: 12 Perform an Analysis of the Least recently used for the following string of memory reference addresses. Assume that there are three frames available within the memory for holding pages. Module Code & Module Title Slide Title SLIDE 33  Thrashing A condition where there is high page replacement activity. A process spends more time replacing pages than processing. Causes CPU utilisation to drop. System throughput reduces and page fault rate increases. Module Code & Module Title Slide Title SLIDE 34  Thrashing A process is thrashing if it is spending more time paging than executing. CPU Utilisation degree of multiprogramming Module Code & Module Title Slide Title SLIDE 35  Question 1. You are given the following memory references:- 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6 How many page faults would occur for the 3 different replacement algorithms, assuming the system has various settings of three, four and five frames? Module Code & Module Title Slide Title SLIDE 36  Summary of Main Teaching Points Virtual memory system is implemented using a technique called demand paging or demand segmentation, this allows for a process larger then the system physical memory to be executed. Demand paging only brings in pages i that are needed into memory. Demand segmentation allocated memory in segments. Demand paging and demand segmentation takes the responsibility of from the programmer to code using techniques for overlays, fixed or variable partitions. Module Code & Module Title Slide Title SLIDE 37  Summary of Main Teaching Points Page faults occur when a page that is needed is found in memory. Page replacements are based on trying to find free frames. Page replacement algorithms are used when there exists no free frames. The page replacement algorithms are first in first out, optimal and least recently used. – First in first out replaces the oldest page. – Optimal replaces the page that is least likely to be used. – Least recently used replaces the page that is has not been used recently. Thrashing occurs when page replacement activities occurs more then process execution. Module Code & Module Title Slide Title SLIDE 38  END Q&A Module Code & Module Title Slide Title SLIDE 39