Chapter 8 2 Memory Management Chapter 8 Memory Management Chapter 8 1 Background Swapping Contiguous Allocation Chapter 8 2 Paging Chapter 8 3 Segmentation Segmentation with Paging Operating System Concepts 8 2 Silberschatz Galvin and Gagne 2005 Paging Paging is a memory management scheme where the physical address space does not have to be contiguous That is your executable may be broken up into different parts and exist in different parts of memory during its execution Storage is non contiguous Paging avoids the fragmentation problems of contiguous memory allocation schemes and swapping with spaces in the backup store Backup stores too had problems similar to memory issues except that access was much slower While older implementations of paging schemes relied on the hardware newer approaches especially with 64 bit microprocessors closely integrate the operating system with the hardware as we shall see Basic idea of paging Divide physical memory into fixed sized blocks called frames size is power of 2 between 512 bytes and 16384 16M bytes Divide logical memory into blocks of same size called pages Backup stores are configured the same way Operating System Concepts 8 3 Silberschatz Galvin and Gagne 2005 Page Introduction Basic Methods To run a program of size n pages need to find n free frames and load program Set up a page table to translate map logical to physical addresses Internal fragmentation could as we are aware be found on the last page but more later on this topic Of course we need to be able to map every address in a program from a page number p and a page offset d displacement into a physical frame plus a displacement Address generated by the CPU as part of development of an address is divided into Page number p used as an index into a page table which contains base address of each page in physical memory and a Page offset d displacement into the page that when combined with base address define the physical memory address that is sent to the memory unit Operating System Concepts 8 4 Silberschatz Galvin and Gagne 2005 Address Translation Architecture Can readily see how this mapping occurs in this figure The page number is used as an index into the page table Displacement is merely added Page size is dependent upon the computer s architecture Mapping a reference from a logical page and offset into a physical page number frame and offset is reasonably easy Operating System Concepts 8 5 Silberschatz Galvin and Gagne 2005 Paging Example Easy example from book Assume each page 4bytes and physical memory is 32 bytes eight pages Can see that logical address 0 is page 0 offset 0 Using the page table we can readily see that logical address 0 maps to frame 5 Logical address 3 d page 0 offset 3 maps to physical address frame 5 5 4 3 23 d Now logical address 4 e is page 1 offset 0 Page 1 maps to frame 6 So logical address 4 maps to physical address 24 6 4 0 Logical address 13 n is found in page 3 which maps to frame 2 and address 13 then maps to 4 2 1 frame 2 plus 1 or logical 9 Operating System Concepts 8 6 Silberschatz Galvin and Gagne 2005 Paging more Can readily see that any free frame can be mapped to by any page We have no external fragmentation but the last page may not completely fill a frame internal fragmentation The average amount of internal fragmentation will clearly be one half of one page per process This suggests that we select a small page size However the more pages we have the more management is needed Generally speaking page sizes have grown over time as everything seems to be getting larger database processes etc Today most pages sizes lie between 8K and 4MB depending on data stored by the pages For the page table itself each entry is usually four bytes long For a system with 4 byte page table entry a 32 bit entry can point to one of 2 32 physical page frames If each page frame is 4K then a system with 4 byte entries can address 2 44 bytes or 16TB of physical memory Operating System Concepts 8 7 Silberschatz Galvin and Gagne 2005 Paging Continued For new processes of n pages there must be n frames available If available they are allocated to the process See next page for figure example A user s view of his program is that there is one single space which contains address translation hardware to map logical pages into physical memory User is totally unaware of this and the mapping is controlled by the OS This mapping is clear from the figure on the next slide A page table for each process must be maintained for each process Thus the page table is also part of the process often contained in the PCB This naturally does slightly increase context switch time a bit but not much Operating System Concepts 8 8 Silberschatz Galvin and Gagne 2005 Paging Example Operating System Concepts 8 9 Silberschatz Galvin and Gagne 2005 Free Frames Discuss this Before allocation Operating System Concepts After allocation 8 10 Silberschatz Galvin and Gagne 2005 Implementation of Page Table Hardware Support The page table is kept in main memory Most operating systems allocate a page table to a process So when a process resumes it must reload the user registers and the page table values from the stored user page table in the PCB Easiest way to implement a page table is via a set of very high speed registers so that the address translations can be done very quickly Since every memory access requires the use of the page table the speed of the hardware is essential Clearly the ability to access load and modify page table registers are privileged instructions Further this is a good solution if the page table is small e g 256 entries Unfortunately many large systems allow for a page table to be in the order of one million entries Operating System Concepts 8 11 Silberschatz Galvin and Gagne 2005 Implementation of Page Table Hardware Support larger machines So for large systems with huge page tables the page table is kept in main memory and a page table base register PTBR points to the page table for a specific process This PTBR points to the page table so when a process is resumed only the contents of this register must be reloaded into the CPU for address translation This substantially reduces context switching time The PTBR is maintained in the process PCB The PTBR will then point to that portion of the page table appropriate to the executing process But there is a problem with this approach Every data instruction access requires two memory accesses One for the page table and one for the