[Operating System] Memory Management

Background

• Types of memories in computer systems
  • Processor registers
  • Cache memory
  • Main memory
  • Auxiliary memory (보조기억장치)
• Notes
  • Block
    • Data transfer unit between primary memory and secondary storage
    • Size: 1 ~ 4 KB (128B ~ 8MB)
  • Word
    • Data transfer unit between primary memory and CPU
    • Size: 16 ~ 64 bits

Cache

• CPU register access time
  • Generally takes 0~1 cycles of the CPU clock
• Memory access time
  • Generally takes 50~200 cycles of the CPU clock
  • CPU normally needs to stall during the memory access
  • Intolerable because of the frequency of memory accesses
• Cache memory
  • Used to accommodate the speed differentia
• Intel Core i7 cache :

CPU-memory performance gap

Address binding

• Compile-time binding
  • When it is known at compile time where the process will reside in memory, then absolute code can be generated
  • Changing the starting location requires recompilation
  • MS-DOS .COM-format programs

• Load-time binding
  • When it is not known at compile time where the process will reside in memory, then the compiler must generate relocatable code
  • Final binding is delayed until load time
  • Changing the starting location requires reloading or relocation of the user code

• Run-time binding
  • Processes can be moved during its execution from one memory location to another
  • Special hardware is required
  • Used in most general-purpose operating systems
  • Run-time mapping from logical(virtual) address to physical address is performed by a hardware device called MMU(Memory Management Unit)

• Notes
  • Logical address (relative address, virtual address)
    • An address generated by the CPU
  • Physical address
    • An address seen by the memory unit
    • An address loaded into MAR
  • Relocation register (base register)
    • Holds the allocation address (smallest physical address)
  • Limit register
  • Contains the range of logical addresses

Dynamic linking

• Linking is postponed until execution time
• Usually used with system libraries
  • Without this facility, each executable on a system must include a copy of its library
    • Wastes both disk space and main memory
• Uses stub concept
  • Included in the image for each library routine reference
  • Small piece of code that indicates how to locate or load the appropriate library routine (in memory or from the library)
  • Replaces itself with the code that contains the address of the routine and executes the routine
    • At the next time that the code segment is reached, the library routine is executed directly without further dynamic linking

• Code sharing
  • All processes that use a library execute only one copy of the library code
• Supports the concept of shared libraries
• Requires help from the OS

Overlay structure

• Keep in memory only those instructions and data that are needed at any given time
• Example) Assembler
  • Symbol table(1MB), Common routines(2MB), Pass-1(3MB), Pass-2(4MB)
  • Primary memory size: 8MB

Swapping

• A process can be swapped temporarily out of memory to a backing store (swap device(swap file system))

Notes on swapping

• Time quantum vs swap time
  • Time quantum should be substantially larger than swap time (context switch time) for efficient CPU utilization
• Pending I/O
  • If I/O is asynchronously accessing the user memory for I/O buffers, then the process cannot be swapped
  • Solutions
    • Never swap a process with pending I/O
    • Execute I/O operations only into kernel buffers (and deliver it to the process memory when the process is swapped in)

• Swap device (swap file system)
  • Swap space is allocated as a chunk of disk
    • Contiguous allocation of the process image
    • Fast access time

Ordinary file system
Discontiguous allocation of the file data blocks
Focuses on the efficient file system space management

Memory Management

Contiguous Memory Allocation

• Basic policies
  • Each process (context) is contained in a single contiguous section of memory
• Policies for memory organization
  • Number of processes in memory
    • Affects multiprogramming degree
  • Amount of memory space allocated for each process
  • Memory partition methods
    • Fixed(static) partition multiprogramming
    • Variable(dynamic) partition multiprogramming

Uniprogramming

• Only 1 process in memory
• Simple memory management scheme

Issue-1

• Program-size > memory-size
  • Uses overlay structure
  • Requires support from compiler/linker/loader

Issue-2

• Kernel protection
  • Boundary register

Issue-3

• Low system resource utilization
• Low system performance
• Solution
  • Multiprogramming → FPM or VPM

FPM

• FPM: Fixed Partition Multiprogramming
  • Divide memory into several fixed-size partitions
  • One process $\leftrightarrow$ one partition
    • One process can use only one partition
    • One partition can be used by only one process
  • When number of partitions = k
    • Maximum multiprogramming degree = k
  • IBM OS/360 MFT

FPM Example

Data structure for FPM: Example

Program reloacation

Protection method

• Loading the relocation and limit registers
  • During context switching
  • By the dispatcher
  • Using a special privileged instruction
    • Allows the OS to change the value of the registers
    • Prevents user programs from changing the registers

Fragmentation

: Waste of storage space

• Internal fragmentation
  • Exists when the memory space allocated is larger than the requested memory
• External fragmentation
  • Exists when enough total memory space exists to satisfy the request, but it is not contiguous

• Both types of fragmentation exist in FPM

Summary

• Several fixed partitions in memory
• Simple memory management
• Low memory management overhead
• May cause poor resource utilization
• Internal/external fragmentation

VPM

• VPM: Variable Partition Multiprogramming
  • Initially, all memory is available as a single large block of available memory (hole, partition)
  • Memory partition state dynamically changes as a process enters or exits the system
  • No internal fragmentation in a partition
  • Contiguous allocation

• Example

Placement strategies

• First-fit
  • Start searching at the beginning of the state table
  • Allocate the first partition that is big enough
  • Simple and low overhead
• Best-fit
  • Search the entire state table
  • Allocate the smallest partition that is big enough
  • Long search time
  • Can reserve large size partitions
  • May produce many small size partitions
  • External fragmentation
• Worst-fit
  • Search the entire state table
  • Allocate the largest partition available
  • May reduce the number of small size partitions
• Next-fit
  • Similar to first-fit method
  • Start searching from where the previous search ended
  • Circular search the state table
  • Uniform use for the memory partitions
  • Low overhead

Coalescing holes

• Merge adjacent free partitions into one large partition

Storage compaction

• Shuffle the memory contents to place all free memory together in one large block (partition)
• Done at execution time
  • Can be done only if relocation is dynamically possible
• Consumes so much system resources
  • Consumes long CPU time

Discontiguous Memory Allocation

• Paging
• Segmentation

Paging

• Memory management scheme that permits the physical address space of a process to be noncontiguous
• Implemented by closely integrating the hardware and operating system

Basic method

• Frames (page frames)
  • Breaking physical memory into fixed-size blocks
• Pages
  • Breaking logical memory into blocks of the same size
  • Page size
    • Typically power of 2
    • 512B ~ 16MB (typically 4KB ~ 8KB)
• Logical address
  • v = (p, d)
    • p: page number
    • d: page offset (displacement)
• Address mapping
  • Logical address → physical address
  • Hidden from the user and controlled by the OS
  • Uses page table
    • A page table for each process

• Paging hardware and address mapping

• Page table implementation
  • Dedicated CPU registers
  • TLB (Translation Look-aside Buffer)
• See [Virtual Memory Organization]

Segmentation

Basic concept

• View memory as a collection of variable-sized segments
• View program as a collection of various objects
  • Functions, methods, procedures, objects, arrays, stacks, variables, and so on
• Logical address
  • v = (s, d)
    • s: segment number
    • d: offset (displacement)

• Normally, when the user program is compiled, the compiler automatically constructs segments reflecting the input program
  • Code
  • Global variables
  • Heap
  • Stacks
  • Standard library

address mapping

Summary

• Contiguous memory allocation
  • Uniprogramming
  • Multiprogramming
    • FPM
    • VPM
• Discontiguous memory allocation
  • Paging
  • Segmentation

Intel Pentium Architecture (For your self-study)

…