Memory Management

• Memory management


  Various ways to manage the primary storage of a computer
• Memory management strategies


  • Multiple Fixed Partitions
  • Multiple Variable Partitions
  • Buddy System
  • Swapping
  • Overlay
  • Simple Paging
  • Simple Segmentation
  • Segmentation with Paging
• Hole


  A block of available memory, unused space in memory
• Region


  A partition or division of a user memory
• Contiguous allocation


  Continuous allocation, whole process is stored continuously in adjacent location
• Non-contiguous allocation


  Process may be subdivided into small portions to fit in a hole which may be found in different locations inside the primary memory
• Multiple Fixed Partitions


  1. Divides the user memory into several regions of fixed sizes

  2. Minimal operating system overhead

  3. Encounters internal fragmentation

  4. Maximum number of processes accepted is based on the number of partitions
• Popular Allocation Algorithms


  • First Fit
  • Next Fit
  • Best Fit
  • Worst Fit
• Internal fragmentation


  Wasted spaces not used within a specific partition
• External fragmentation


  A partition that was not used because the process may be too big to fit the partition or the partition maybe too small to fit any process
• Memory compaction is a solution to use wasted space, where free spaces are merged together to create a bigger space that may now fit a process
• First Fit Allocation Algorithm

  1. Search for the first hole which is big enough to fit the process, search always starts with the first region

  2. Produces high internal fragmentation

  3. Small holes tend to accumulate in the first few regions
• Next Fit Allocation Algorithm

  1. Search for the first hole which is big enough to fit the process, search starts from the last hole allocated

  2. Better than First Fit, small holes are not accumulated in the first few regions
• Best Fit Allocation Algorithm

  1. Search for the smallest unused hole available in which it will fit

  2. Produces the smallest internal fragmentation

  3. More complex algorithm used, higher overhead
• Worst Fit Allocation Algorithm

  1. Search for the largest unused hole available in which it will fit

  2. Produces the largest internal fragmentation

  3. High overhead
• Memory compaction is often called "burping the memory"
• Worst Fit Allocation Algorithm

  1. Regions occupied by each job

  2. Compute internal fragmentation, external fragmentation, total fragmentation, and memory utilization
• First Fit Allocation Algorithm

  Compute internal fragmentation, external fragmentation, total fragmentation, and memory utilization at different time steps
• CPU Scheduling Algorithm - First Come First Served
• Memory Allocation Strategy - First Fit
• Memory Management Strategy - Multiple Fixed Partition
• Multiple Variable Partition, also known as Dynamic Partition, views the memory as one big hole and allocates the memory based on the size of the process
• Memory Management Strategy - Multiple Variable Partition
• One of the problems encountered in Multiple Variable Partition strategy is external fragmentation
• Paging


  Allocate the physical memory to processes in fixed size pages called frames
• Segmentation


  Allocating memory using variable length blocks called segments
• Segmentation with Paging


  Combines the principle of using segmentation and paging to provide the efficiency of paging and the protection and sharing capabilities of segmentation
• Segmentation


  Dividing a process into several length blocks called segments
• Segmentation


  1. Divide process into several segments

  2. Load segments into a variable partition that is non-contiguous

  3. Gets rid of internal fragmentation

  4. Improvement of multiple variable partition or dynamic partitioning
• Segmentation with Paging


  1. Break down logical address of a segment to segment number and segment offset

  2. Segment offset is further divided into a page number and page offset

  3. Segment table entry contains the address of the segment's page table

  4. Hardware implementation adds logical address's page number bits to page table address to locate page table entry

  5. Physical address is formed by appending page offset to page frame number specified in page table entry
• Swapping


  Technique that permits a computer system to execute programs that are larger than the primary storage
• Swapping


  1. Operating system copies part of process found in secondary storage into primary storage

  2. When other part of process is needed, it exchanges a portion of data in primary storage (swap out) with a portion of data in secondary storage (swap in)

  3. Choice on which process to swap out and which to swap in is made by medium term scheduler
• Overlaying


  Permits a process to execute even though it is larger than the primary storage
• Overlaying


  1. Programmer defines two or more overlay segments within the program such that no two overlay segments need be in memory at one time

  2. Operating system takes charge in swapping overlay segments, thus limiting the physical size of the process in primary memory

  3. Only keeps in memory those data and instructions needed at any given time
• Overlaying is implemented by the programmer and compiler which may be complex and very time consuming task
• Buddy System


  Memory management technique that splits memory by half until a best fit for a specific request is met
• Buddy system is comparatively easier to implement than paging, has little external fragmentation and little overhead trying to do compaction of memory but, it encounters a lot of internal fragmentation
• Memory management


  The functionality of an operating system which handles or manages primary memory and moves processes back and forth between main memory and disk during execution
• Memory Manager Jobs


  • Maintain the list of which parts of the memory are in use and which parts are not used
  • Allocate memory to a process if required
  • Deallocate memory when the process is complete
  • Manages swapping between main memory and secondary memory
• Contiguous Allocation


  Each process is contained in a single contiguous block of memory