1. Memory Management-discussion.pdf

MAIN MEMORY Topics Background Swapping Contiguous Memory Allocation Segmentation Paging Structure of the Page Table Example: The Intel 32 and 64-bit Architectures Example: ARM Architecture Objectives To provide a detailed description of the different ways on organizing a memory hardwa...

MAIN MEMORY Topics Background Swapping Contiguous Memory Allocation Segmentation Paging Structure of the Page Table Example: The Intel 32 and 64-bit Architectures Example: ARM Architecture Objectives To provide a detailed description of the different ways on organizing a memory hardware To provide details on various memory-management techniques Background on Main Memory Consists of large array of words or bytes Program must be brought (from disk) into memory and placed within a process for it to be run Memory unit only sees a stream of addresses + read requests, or address + data and write requests Register access in one CPU clock (or less) Main memory can take many cycles, causing a stall Cache sits between main memory and CPU registers Protection of memory required to ensure correct operation Main Memory or Physical Memory - RAM - Internal memory - Physical memory Basic Concept of Memory Hardware Hardware Address Protection Address Binding Is the process of mapping from one address space to another address space Logical address - address generated by the cpu during the process execution Physical address - is the address where the process was loaded in the memory Address Binding 3 ways for Address binding – Compile time – generates absolute code if uses a priori of the physical address of the code – Load time - Must generate relocatable code if memory location is not known at compile time Relocatable code – software whose execution address can be changed – Execution time - Binding delayed until run time if the process can be moved during its execution from one memory segment to another  Multistep Processing of a User Program From source Count code (when compiled) 14 bytes from beginning of Count module Source code Relocatable address – address that is adjusted for the process that is to be executed (When linked) 74102 Count A B Logical Address Space and Physical Address Space Logical Address - the set of all logical addresses generated by a program Physical Address - refers to the set of all physical addresses that correspond to these logical addresses For compile time and load time address binding – same physical and logical address space For execution time – different physical and logical address spaces Memory Management Unit (MMU) Computer hardware component that handles the memory and caching operations associated with the processor Task: execute runtime mapping from virtual to physical addresses Memory mapping - translates addresses between the CPU and physical memory Example: Base-register scheme  Relocation Register or Base-Register Scheme – Base register = relocation register – Relocation register is added to every address generated by the user process when it is sent to the memory – Implements dynamic loading – Routines are kept on disk in a relocatable load format Dynamic Relocation using a Relocation Register Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne Dynamic Loading Better memory-space utilization loads a routine only when it is called operating system only provides the library routines to implement dynamic loading Static and Dynamic Linking Static Linking - system libraries and program code are combined by the loader into the binary program image – Disadvantage: every program must have its own copy of the system library functions. Dynamic Linking – uses shared libraries when compiling programs – Useful for libraries Swapping Mechanism wherein a process is swapped out of the memory to a backing store. Backing store – fast disk large enough to accommodate copies of all memory images for all users – must provide direct access to these memory images Roll out, roll in – variant in swapping policy – Implemented in higher priority and low priority processes  Swapping Schematic View of Swapping Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne Context Switch Time Involves storing the context or state of a process so that it can be reloaded when execution is resumed Example: user process is 10MB, backing store (hard disk) has a transfer rate =40MB/sec The transfer rate of the 10MB file to and from the memory is: = (10MB ) / (40MB/sec) = ¼ sec or 250 milliseconds If there is an average latency of 8ms, the swap time = 258ms Swapping in and out = 516ms.  Swapping on Mobile Systems Not typically supported – Flash memory based Small amount of space Limited number of write cycles Poor throughput between flash memory and CPU on mobile platform Instead use other methods to free memory – iOS asks apps to voluntarily relinquish allocated memory Read-only data thrown out and reloaded from flash if needed Failure to free can result in termination – Android terminates apps if low free memory, but first writes application state to flash for fast restart Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne Contiguous Memory Allocation The memory must accommodate user processes and the operating system 2 partitions of contiguous memory: resident os and use rprocess The lower memory – where the operating system is locates High memory – for user processes Relocation registers used to protect user processes from each other, and from changing operating-system code and data – Base register contains value of smallest physical address – Limit register contains range of logical addresses – each logical address must be less than the limit register – MMU maps logical address dynamically  Memory Mapping and Protection 500 100040 Hardware Support for Relocation and Limit Registers Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne  Multiple Partition Allocation Multiple-partition allocation – Degree of multiprogramming is limited by the number of partitions – Variable-partition sizes for efficiency (sized to a given process’ needs) – Hole – block of available memory; holes of various size are scattered throughout memory – When a process arrives, it is allocated memory from a hole large enough to accommodate it – Process exiting frees its partition, adjacent free partitions combined – Operating system maintains information about: a) allocated partitions b) free partitions (hole) a b c d Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne Static and Dynamic Memory Allocation Static Memory Allocation - declaring variables before runtime – Example: F1{ int sum =0; ……. } Dynamic Memory Allocation – assigning a memory space during runtime  Dynamic Storage-Allocation Problem Most commonly used strategies: First-fit: Allocate the first hole that is big enough Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size – Produces the smallest leftover hole Worst-fit: Allocate the largest hole; must also search entire list – Produces the largest leftover hole Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne Fragmentation External fragmentation – total memory space exists to satisfy a request, but it is not contiguous – Solution: compaction - possible if dynamic relocation Paging and segmentation Internal Fragmentation - when allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used  First-Fit Memory Allocation Searching for the first available free space – start of the beginning of wholes or where the first-fit search ended Example: Given the following Size Jobs (in order), how would these jobs fit in Jobs Size (KB) 60KB 10KB or be allocated in the four memory A 80 90KB 10KB partitions? B 120 C 180 200KB 80KB D 50 Job C waits 130KB  Best-Fit Memory Allocation allocates the smallest free partition that is close to the actual size of the job or process Given the following Jobs (in order), how Size would these jobs fit in or be allocated in the 60KB 10KB Jobs Size (KB) four memory partitions? A 80 90KB 10KB B 120 C 180 200KB 20KB D 50 130KB 10KB  Worst-Fit Memory Allocation Searching the list for the largest whole Example: Given the following Size Jobs (in order), how would these jobs fit in Jobs Size (KB) 60KB or be allocated in the A 170 90KB 40KB four memory partitions? B 120 C 180 200KB 30KB D 50 130KB 10KB Job C waits Internal Fragmentation Suppose that the following Jobs (in the order below) are to be allocated in these five memory partitions of 200Kb, 100Kb, 500Kb, 300Kb and 450Kb. Use the Best-Fit Algorithm. Jobs Size Size Size Size (Kb) B 200K B 200K 200K D A 65 b D b b (40) (10) B 120 100K A 100K 100K b A(35) F C 280 b b (5) D 40 500K b 500K 500K E 125 b b F 30 300K b 300K 300K C(20) C(20) G 130 b b 450K b 450K E E(325) 450K b G b (195) Segmentation Memory-management scheme that gives the user’s view of the process A program is divided into segments and a segment is a logical unit. Examples: main program, procedure , function, method object, local variables, global variables common block, stack, symbol table, arrays  Segmentation: User’s View of a Program Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne  Logical View of Segmentation 1 4 1 2 3 2 4 3 user space physical memory space Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne Segmentation Main Process Segment Table Memory Segment Size Memory No. address Segment 1 1 200 100 100 2 100 500 200 Segment 2 3 400 300 300 400 Segment 3 500 600 Paging memory-management scheme that permits the physical address space of a process to be noncontiguous Avoids external fragmentation Uses frames and pages breaking physical memory into fixed-sized blocks called frames – Size is power of 2, between 512 bytes and 16 Mbytes breaking logical memory into blocks of the same size called pages Keeps track of all free frames Paging: Address Translation Scheme Division of an address from the CPU: – Page number (p) – used as an index into a page table which contains base address of each page in the physical memory – Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit page number page offset p d m -n n For given logical address space 2m and page size 2n  Paging Hardware Hardware support for Paging Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne  Paging Model of Logical and Physical Memory Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne  Paging Page no. Example 0 1 The size of the page table is 2n , where n=2 and the size of the logical memory is 2m 2 (where m=4). The logical memory has 4 byte-page size and the physical memory 3 of 32 bytes (8 pages). Ex: In the logical memory, “a” or logical address 0 is located in Page 0 and offset 0. “b” or logical address 1 is located in Page 0 and offset 1. What is the physical memory address of “b” or logical address 1? Specific address = (5x4) + 1 = 21 n=2 and m=4 32-byte memory and 4-byte pages Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne  Free Frames Before allocation After allocation Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne  Page Table - Implementation PTBR (Page-Table Base Register) – points to the page table PTLR (Page Table Length Register) – specifies the size of the page table TLB (Translation Look-aside Buffers) - memory cache used to lessen the time to access a user memory location – Also called Associative Memory Two Memory Accesses for data / instructions – Page table – Data / instruction Internal Fragmentation on Paging Example: Page size = 2,048 (size = 2n ) Size of process = 58,800 bytes No. of pages = 28 and excess bytes = 1,456  Internal Fragmentation Example: The following are logical address references (in decimal), what are their page numbers and offsets? Assume that the page size = 1KB a) 2314 b) 9467 c) 900000 d) 55000 Logical Address Page number Offset 2314 2 266 9467 9 251 12000 11 736 1800 1 776 Example: Consider a logical address space of 64 pages of 1024 words each, mapped onto a physical memory of 32 frames. How many bits are in the logical address and physical address? Logical address: pages: 2^6 + 2^10 = 16 bits Physical address: frames: 2^5 + 2^10 = 15 bits Protection Protection in a page environment makes use of protection bits which are associated with each frame. – Valid and invalid bits The bits are placed in a page.  Page: Protection (Valid or Invalid) 8 pages = 16383/2048 Example: A 14-bit address space (where: 214 = 16,384) (address is: 0-16,383) A process is addressed to pages 0- 10,468 Page size = 2KB Process uses 5 pages: 10,468/2048 Pages: 0-4 page 5 = 228 bytes (excess from 10,468%2056) Operating System Concepts, 9th edition Siberscahtz, Gelvin, and Gagne Shared Pages Shares common code (time-sharing environment), reentrant code Similar to threads implementation in sharing the memory space Reentrant code – doesn’t change during execution – Each process : can execute the same code at the same time has its own registers and data storage has its own data Example: Shared Pages Example: A text editor that shares it code to 40 users. Text editor = 150KB code Data space = 50KB Page Table Hierarchical Paging Hashed Page Table Inverted Page Table Hierarchical Paging Referred as Multilevel Paging Page tables are stored in the memory  Two Level Paging Example: - A logical address of 32 bits machine with 4K page size) - Page number -> 20 bits - 10 bit page number - 10 bit page offset - Page offset -> 12 bits 212 Page Offset 10 10 12 Hashed Table Paging Used for address spaces larger than 32 bits Hashed value is the virtual page number The virtual page number are the bits that are not part of the page offset. Each entry in the hash table has a linked list of elements hashed to the same location 3 fields for each element in the hash table – Virtual page number – Value of mapped page frame – Pointer to the next element in the linked list Hashed Table Paging Virtual page 1 Virtual page 2 Inverted Page Tables Maintained by the operating system for all processes Consists of one page table entry for every frame in the memory A single page table represents the paging information of all the processes Decreases memory storage Increases time in searching the table Has only one page table in the system Inverted Page Tables Where: P=page number d = offset Pid = Process ID Examples of Architecture (Memory) Intel 32 Architecture – Has two Implementations segmentation segmentation with paging – Size for each segment: 4GB – 2 Partitions: Partition 1: Up to 8K – private to the process (local) Partition 2: up to 8K (second group) – shared among processes (global) Example ARM (Advanced RISC Machine) Architecture Used in mobile platform chip Uses pages with 4KB and 16 KB pages One-level paging for sections and two-level for smaller pages ARM (Advanced RISC Machine) Architecture 32 bits outer page inner page offset 4-KB or 16-KB page 1-MB or 16-MB ARM Memory Management Unit section End of Presentation References: https://developer.arm.com/docs/den0024/a/the-memory- management-unit Siblerschatz, Galvin, and Gagne. Operating System Concepts (9th Edition)