Detailed Study Notes on Main Memory from Operating Systems

Chapter 8: Main Memory

Overview

  • Purpose of Main Memory

    • Programs must be brought from disk into memory and organized within a process for execution.
    • Main memory and CPU registers are the only storage units that can be accessed directly by the CPU.

  • Memory Access Characteristics

    • Memory unit handles a continuous stream of addresses and either read requests (address) or write requests (address + data).
    • Register access occurs in one CPU clock cycle or less.
    • Accessing main memory may take several cycles, potentially causing a CPU stall.

  • Memory Protection

    • Memory protection ensures correct operation by preventing a process from accessing memory allocated to other processes or the operating system (OS).

Base and Limit Registers

  • Definition
    • A pair of base and limit registers defines the logical address space for a user program.
  • Memory Access Validation
    • The CPU verifies every memory access attempt in user mode to ensure it falls within the limits set by the base and limit registers.

Logical vs. Physical Address Space

  • Definitions

    • Logical Address
    • Generated by the CPU, also known as virtual address.
    • Physical Address
    • The actual address seen by the memory unit.

  • Address Binding

    • In compile-time and load-time address-binding schemes, logical and physical addresses are identical.
    • In execution-time address-binding schemes, logical and physical addresses can differ.

  • Address Space Definitions

    • Logical Address Space
    • Set of all logical addresses generated by a program.
    • Physical Address Space
    • Set of all physical addresses accessible by a program.

Memory-Management Unit (MMU)

  • Functionality
    • The MMU is a hardware device that maps virtual addresses to physical addresses at runtime using several possible methods.
    • A simple method involves adding a relocation register's value to each address generated by the user process.
  • Relocation Register
    • Referred to as the base register, it enables dynamic address relocation, allowing user programs to work with logical addresses while the MMU manages the translation.

Dynamic Relocation Using Relocation Register

  • Rouine Loading
    • Routines are not loaded until they are called, allowing for better memory utilization since unused routines remain unloaded.
    • All routines should be kept on disk in a relocatable load format, particularly useful for handling infrequent cases that require substantial code.
  • OS Support
    • No specific OS support is required; implementation relies on program design, although the OS can provide libraries to facilitate dynamic loading.

Swapping

  • Definition
    • Swapping refers to temporarily moving a process out of main memory to a backing store and bringing it back for continued execution. This allows total process memory space to exceed available physical memory.
  • Backing Store
    • A fast disk capable of accommodating copies of all memory images for all users must provide direct access to these memory images.
  • Roll Out, Roll In
    • This swapping variant is used in priority-based scheduling. Lower-priority processes can be swapped out to facilitate the execution of higher-priority processes.
  • Transfer Time
    • The major contributor to swap time is the transfer time, which is directly proportional to the amount of memory swapped.
  • Ready Queue
    • The OS maintains a queue of processes that are ready to run, each with an associated memory image on disk.

Contiguous Allocation

  • Memory Allocation
    • Main memory is shared between the OS and user processes, necessitating efficient allocation of this limited resource.
  • Technique
    • Contiguous allocation divides memory into two segments:
    • Resident OS, located in low memory and containing the interrupt vector.
    • User processes in high memory, each residing in a single contiguous block of memory.
  • Purpose of Relocation Registers
    • Protects user processes from one another and from accessing OS code and data directly.

Multiple-partition Allocation

  • Degree of Multiprogramming
    • Limited by the number of available partitions.
  • Variable-partition Sizes
    • Allocating memory in variable sizes based on process needs increases efficiency.
  • Hole Definition
    • A hole is a block of available memory that can be filled by incoming processes. Holes of various sizes exist throughout memory.
  • Memory Management
    • The OS keeps track of allocated and free (hole) partitions accordingly. When a process exits, its memory is freed, and adjacent free partitions may be combined for larger allocations.

Dynamic Storage-Allocation Strategies

  • Algorithms

    • First-fit
    • Allocates the first hole that fits the request.
    • Best-fit
    • Allocates the smallest available hole that fits; requires searching through the entire list unless pre-sorted. Produces minimal leftover space.
    • Worst-fit
    • Allocates the largest hole; also requires a full search. Generates the largest leftover space.

  • Efficiency

    • First-fit and best-fit generally outperform worst-fit in execution speed and storage utilization.

Examples of Dynamic Storage Allocation

  • Memory Partitions Available
    • Sizes: 200 KB, 400 KB, 600 KB, 500 KB, 300 KB, 250 KB.
  • Block Allocation Sequence
    • Size Requests in order: 360 KB, 210 KB, 470 KB, 490 KB.
First-Fit Example
  • Allocations
    1. 360 KB Block → 400 KB Partition
    2. 210 KB Block → 600 KB Partition
    3. 470 KB Block → 500 KB Partition
    4. 490 KB Block → Unable to allocate (no available partition available).
Best-Fit Example
  • Allocations
    1. 360 KB Block → 400 KB Partition
    2. 210 KB Block → 250 KB Partition
    3. 470 KB Block → 500 KB Partition
    4. 490 KB Block → 600 KB Partition.
Worst-Fit Example

  • Allocations

    1. 360 KB Block → 600 KB Partition
    2. 210 KB Block → 500 KB Partition
    3. 470 KB Block → Unable to allocate (no partitions available).

  • Resource Utilization Notes

    • Demonstrating that utilizing an optimal allocation strategy can often save additional operations when faced with resource limitations.

Fragmentation

  • External Fragmentation
    • Occurs when total memory is available for a request but is not contiguous (free holes scattered).
  • Internal Fragmentation
    • Memory allocated may exceed requested memory, resulting in unutilized space within the allocated partition.
  • Fragmentation Analysis
    • An analysis determined that roughly 0.5 of N allocated blocks lead to fragmentation losses.
Reducing External Fragmentation via Compaction
  • Compaction Technique
    • Compacts memory by rearranging contents to create larger contiguous blocks of free memory, requiring dynamic relocation for execution time rearrangements.

Segmentation

  • Segmentation as a Memory Management Scheme
    • Supports a user’s perspective of memory by dividing a program into segments of varying sizes, such as:
    • Main program
    • Procedures and functions
    • Objects
    • Local and global variables
    • Stack segments and symbol tables

Segmentation Architecture

  • Logical Address Structure
    • Consists of a two-tuple:
    • Segment Table
    • Maps logical addresses to physical locations, containing entries providing base (starting physical address) and limit (length of segment).
  • Register Functions
    • Segment-table base register (STBR) which points to the segment table location, and segment-table length register (STLR) indicating the number of segments allocated.
    • A segment number s is legal if s < STLR.
Protection Mechanisms in Segmentation
  • Protection Bits
    • Include validation bits in segment table entries to indicate legality and allowed access flags (read/write/execute permissions).
    • Offers code-sharing capabilities at the segment level; differing lengths require efficient dynamic allocation strategies.

Paging

  • Definition of Paging
    • Allows the process's physical address space to be non-contiguous, thus avoiding external fragmentation and issues with variable-sized memory sections.
    • Physical memory is divided into fixed-sized blocks (frames), with sizes being powers of 2 (between 512 bytes and 16 Mbytes).
    • Logical memory is likewise divided into pages of the same size.

Address Translation Scheme in Paging

  • Address Breakdown
    • An address generated by the CPU is split into:
    • Page Number (p) - Index used in the page table to find the base address of each page.
    • Page Offset (d) - Combined with the base address to create the physical address sent to the memory unit.
    • Logical address space size 2^m and page size 2^n.

Page Table Implementation

  • Location and Structure
    • The page table resides in main memory, with the page-table base register (PTBR) indicating its location.
    • Page-table length register (PTLR) shows the page table’s size. With every data access needing two memory accesses: one for the page table and one for the data instruction.

Associative Memory for Paging

  • Functionality of Associative Memory
    • It allows a parallel search for address translation. If the page number p is located in the associative register (TLB), the corresponding frame number is retrieved; if not, it falls back to the page table in memory for resolution.

Memory Protection with Paging

  • Protection Bits Implementation
    • Protection bits associated with each memory frame can specify allowed access (read-only, read-write).
    • A valid-invalid bit signifies if the page is in the legal address space, with violations resulting in a kernel trap.

Shared Pages

  • Concept
    • Shared code refers to one copy of read-only code accessible among multiple processes (e.g., text editors), enhancing memory efficiency.
    • Private data mean each process retains its own copy of data, where private code and data can occupy any location in the logical addressing space.

Address-Translation Scheme Visuals

  • Logical to Physical Address Translation
    • Diagrams illustrate the hierarchical organization of the page tables and address translations, highlighting relationships between logical and physical memory segments.