Skip to main content

13. Memory Management 2

04/11/22

Relocation and Protection​

Principles​

  • Relocation: when a program is run, it does not know in advance which partition/addresses it will occupy
    • The program cannot simply generate static addresses that are absolute
    • Addresses should be relative to where the process has been loaded
    • Relocation must be solved in an operating system that allows process to run a changing memory locations
  • Protection: once you can have two programs in memory at the same time, protection must be enforced

Address Types​

  • A logical address is a memory address seen by the process
    • It is independent of the current physical memory assignment
    • Its relative to the start of the program
  • Physical address refers to an actual location in main memory
  • The logical address space must be mapped onto the machines physical address space

Approaches​

  1. Static 'relocation' at compile time: a process has to be located at the same location every single time
  2. Dynamic relocation at load time
    • Offset is added to every logical address to account for its physical location in memory
    • Slows down the loading of a process, does not account for swapping
  3. Dynamic relocation at runtime

Base and Limit Registers​

  • Two special purpose registers are maintained in the CPU (the MMU), containing a base address and limit
    • The base register stores the start address of the partition
    • The limit register holds the size of the partition
  • At runtime:
    • The base register is added to the logical(relative) address to generate the physical address
    • The resulting address is compared against the limit register
  • This approach requires hardware support (was not always present in the early days!)

Dynamic Partitioning​

  • Fixed partitioning results in internal fragmentation (inside the blocks)
    • An exact match between the requirements of the process and the available partitions may not exist
    • The partition may not be used entirely
  • Dynamic partitioning
    - A variable number of partitions of which the size and starting address can change over time
    - A process is allocated the exact amount of contiguous memory it requires, thereby preventing internal fragmentation

Swapping​

  • Swapping holds some of the process on the drive and shuttles processes between the drive and main memory as necessary
  • Reasons for swapping:
    • Some processes only run occasionally
    • Have more processes than partitions
    • A process's memory requirements have changed
    • The total amount of memory that is required for the process exceeds the available memory

Difficulties​

  • The exact memory may not be known in advance (heat and stack grow dynamically)
  • External fragmentation:
    • Swapping a process out of memory will create 'a hole'
    • A new process may not use the entire 'hole', leaving a small unused block
    • A new process may be too large for a given a 'hole'
  • The overhead of memory compaction to recover holes can be prohibitive and requires dynamic relocation

Allocation Structures​

Bitmaps​

  • Simplest data structure that can be used in a form of bitmap
  • Memory is split into blocks.(e.g 4kb size)
  • To find a hole(128K) then a group of 32 adjacent bits set to 0 must be found, typically a long operation.
  • Trade-off exists between the size of the bitmap and the size of blocks exists
    • The size of bitmaps can become prohibitive for small blocks and may make searching the bitmap slower
    • Larger blocks may increase internal fragmentation
  • Bitmaps are rarely used for this reason

Linked List​

  • A more sophisticated data structure is required to deal with a variable number of free and used partitions
  • Each link contains data items, e.g. start of memory block, size, free/allocated flag
  • The allocation of processes to unused blocks become non-trivial

Summary​

Internal fragmentation - Inside the blocks External fragmentation - outside the block