Memory Management: Paging, Segmentation, and Registers

Main Memory

• Key techniques for memory management are described, including paging and segmentation.
• Detailed information on the Intel Pentium is provided, which supports pure and segmented paging.

Background

• Programs need to me moved from disk into memory to be executed within a process.
• CPU can directly access the main memory and registers, which are the only storage it can access.
• The memory unit reads/writes requests as streams of addresses and data.
• Registers can typically be accessed in one CPU clock or less.
• Main memory access takes many cycles and, hence can cause a stall.
• Cache memory exists between the main memory and CPU registers.
• Memory requires protection to ensure correct operation.

Base and Limit Registers

• A pair of base and limit registers defines the logical address space.
• The CPU verifies that every memory access is within the base and limit registers when in user mode.

Address Binding

• Address binding can happen at three stages: compile time, load time, and execution time.
• Programs are placed on disk in an input queue, ready to be brought into memory for execution..
• In the source form, addresses are symbolic.
• In compiled code, addresses bind to relocatable addresses.
• The linker or loader binds relocatable addresses to absolute addresses.
• Each binding maps one address space to another.

Binding of Instructions and Data to Memory

• If the memory location is known in advance, absolute code can be generated at compile time.
• If the memory location is unknown at compile time, relocatable code must be generated at load time.
• The execution time binding is delayed until run time if the process can be moved during execution from one memory segment to another.

Logical vs. Physical Address Space

• Memory management requires that each logical address space is bound to a separate physical address space.
• The logical address (virtual address) is generated by the CPU.
• The physical address is an address that is seen by the memory unit.
• Logical and physical addresses are the same during compile and load times where address-binding schemes are used.
• Logical and physical addresses differ in the execution-time address-binding scheme.
• The set of all logical addresses generated by a program is the logical address space.
• The set of all physical addresses generated by a program is the physical address space

Memory-Management Unit (MMU)

• The MMU is a hardware device that maps virtual to physical addresses at run time.
• When the value in the relocation register is added to every address generated by a user process, this is a simple scheme.
• The base register is called a relocation register.
• MS-DOS on Intel 80x86 used four relocation registers.
• The user program works with logical addresses, but never sees the real physical addresses.
• When a reference is made to the location in memory, execution-time binding occurs.
• Logical addresses are bound to physical addresses.

Dynamic Relocation

• A routine gets loaded whenever it is called
• Memory-space utilization is improved and the unused routine is not loaded.
• Routines are kept on disk in a relocatable load format.
• Effective strategy when large amounts of code handle infrequently occurring cases.
• It can be implemented through program design.
• The OS can also provide libraries to implement dynamic loading.

Dynamic Linking

• Static linking combines system libraries and program code into a binary program image during loading
• Dynamic linking postpones the linking process until execution time.
• A small piece of code(stub), locates the appropriate memory-resident library routine.
• The stub replaces itself with the address of the routine, and the routine executes.
• Patching system libraries also use dynamic linking.
• Versioning might be needed.
• System also known as shared libraries

Swapping

• A process can be swapped temporarily out of memory to a backing store, then brought back in for execution.
• Backing store must provide direct access to memory images and be large enough to store copies of all memory images for all users.
• Total physical memory space of processes can exceed physical memory.
• In priority-based scheduling, 'roll out, roll in' , a lower-priority process is swapped out so a higher-priority one can be loaded and executed.
• Transfer time is a major part of swap time, and is proportional to the amount of memory swapped.
• A system maintains a ready queue of ready-to-run processes which hold respective memory images.
• Swapping may be enabled or disabled depending on usage and memory allocation.

Context Switch Time including Swapping

• Process needs to be swapped out and a target process needs to be swapped if next processes to be put on CPU is not in memory.
• Context switch time can be very high.
• Example shows how for 100MB process swapping to hard disk with transfer rate of 50MB/sec:
  • Swap out time of 2000 ms occurs.
  • Total context switch swapping component time is 4000ms (4 seconds) including swap in of same sized process.
• Can reduce if reduce size of memory swapped by knowing how much memory is really being used.
• System calls to inform OS of memory use via request_memory() and release_memory().

Swapping Constraints

• Processes with pending I/O cannot be swapped out as I/O would occur to wrong process.
• Always transfer I/O to the Kernel Space, then to I/O devices by using a technique known as double buffering.

Swapping on Mobile Systems

• Swapping is not typically supported on mobile system due to flash memory being based
• Mobile systems mainly use flash memory for storage with a small amount of space and a limited amount of write cycles.
• Instead, other methods are used to free memory if low on space.
  • iOS requests apps to voluntarily relinquish allocated memory, and read-only data can be thrown out and reloaded from flash if needed.
  • Android terminates apps if low free memory, but saves the application state to the flash for a fast restart.

Contiguous Allocation

• The main memory must support both the OS and the user processes.
• Contiguous allocation is one early method, which must allocate limited resources efficiently.
• The main memory is usually split into two partitions, the resident OS and the user processes.
• The resident OS is located low in memory with an interrupt vector.
• User processes are held in high memory.
• Each process is contained in a single contiguous section of memory.

Contiguous Allocation (Cont.)

• Relocation registers protect user processes from each other and prevent them from changing OS code and data.
• The base register contains the smallest physical address value.
• The limit register contains the range of logical addresses, in which each logical address must be less than the limit register.
• The MMU maps the logical address dynamically.
• Transient kernel code and changing kernel size can be allowed.

Multiple-Partition Allocation

• The degree of multiprogramming is limited by the number of partitions.
• Variable-partition sizes are used for efficiency which are sized according to a given process' needs.
• A hole is a block of available memory where holes of various sizes are scattered throughout memory.
• When a process arrives, it is allocated memory from a large enough hole.
• When a process exits, it frees its partition, and adjacent free partitions are combined.
• The OS maintains information about allocated and free partitions (hole).

Dynamic Storage-Allocation Problem

• First-fit: Allocate the first hole that is big enough
• Best-fit: Allocate the smallest hole that is big enough
• Prodcues the smallest leftover hole
• Worst-fit: Allocate the largest hole
• Produces the largest leftover hole
• First-fit and best-fit are better than worst-fit in terms of speed and storage utilization.

Fragmentation

• External Fragmentation: Total memory exists to satisfy a request, but it is not contiguous.
• Internal Fragmentation: Allocated memory may be slightly larger than requested memory. The size difference is internal to a partition but is not being used.
• First-fit analysis shows that 0.5 N blocks are lost to fragmentation given N blocks allocated.

Fragmentation (Cont.)

• Compaction can reduce external fragmentation.
• Shuffle memory contents to place all free memory together in one large block
• Compaction is possible if relocation is dynamic and done at execution time.
  • Latch job in memory while it is involved in I/O
  • Do I/O only into OS buffers
• Backing store has the same fragmentation problems

Segmentation

• Supports a user view of memory via memory-management scheme.
• A program's collection of segments can be used to view the program.
  • main program
  • procedure
  • function
  • method
  • local variables, global variables
  • common block
  • stack
  • symbol table
  • arrays

Segmentation Architecture

• Logical address consists of a two tuple: <segment-number, offset>
• Segment table maps two-dimensional physical addresses, where each entry has
  • Base - contains the starting physical address where the segments reside in memory
  • Limit - specifies the length of the segment
• Segment-table base register (STBR) points to the segment table's location in memory
• Segment-table length register (STLR) indicates the number of segments used by a program
• a segment number s is legal if s STLR

Segmentation Architecture (Cont.)

• Protection by using a validation bit to indicate illegal segment
• Can also have protection with read/write/execute privileges
• Protection bits associated with segments, code sharing occurs at segment level
• Segments vary in length, memory allocation is a dynamic storage-allocation problem

Paging

• The physical address space of a process can be noncontiguous. The process is allocated physical memory whenever it is available.
• Avoids external fragmentation
• Avoids problem of varying sized memory chunks
• Physical memory is divided into fixed-sized blocks called frames.
• Size is power of two, and can be between 512 bytes and 16 Mbytes
• Logical memory is divided into blocks of the same size called pages.
• All free frames are tracked.
• To run a program with a size of N pages, N free frames are required to load the program.
• Set up page table to translate logical to physical address.
• Backing store likewise split into pages.
• Can still have internal fragmentation.

Address Translation Scheme

• The CPU generates an address divided into:
  • Page number (p) - used as an index into a page table which contains the base address of each page in physical memory
  • Page offset (d) - combined with base address to define the physical memory address that is sent to the memory unit
• Given logical address space 2^m and page size 2^n

Paging (Cont.)

• Calculating internal fragmentation:
  • Given page size = 2,048 bytes, process size = 72,766 bytes, 35 pages + 1,086 bytes;
  • Internal fragmentation of 2,048 - 1,086 = 962 bytes
  • Worst case fragmentation = 1 frame - 1 byte
  • On average fragmentation = 1 / 2 frame size
• But each page table entry takes memory to track
• Page sizes growing over time
• Solaris supports two page sizes, 8KB and 4MB
• Process view and physical memory now very different
• By implementation process can only access its own memory

Implementation of Page Table

• Page table is kept in main memory
• Page-table base register (PTBR) points to the page table
• Page-table length register (PTLR) indicates the size of the page table
• Every data/instruction access requires two memory access in scheme:
  • One for the page table and one for the data / instruction
• The two memory access problems can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs)

Implementation of Page Table (Cont.)

• Some TLBs store address-space identifiers (ASIDs) in each TLB entry – uniquely identifies each process to provide address-space protection for that process
  • Otherwise need to flush at every context switch
• TLBs typically small (64 to 1,024 entries)
• On a TLB miss, value is loaded into the TLB for faster access next time
  • Replacement policies must be considered
  • Some entries can be wired down for permanent fast access

Associative Memory

• Uses parallel search
• Address translation (p, d)
  • If p is in associative register, get frame # out
  • Otherwise get frame # from page table in memory

Effective Access Time (EAT)

• Access time effectiveness involves time unit (&), hit ratio (α), and number of associative registers
• Effective Access Time (EAT) = (1 + ε) α + (2 + ε)(1 – α) = 2 + ε - α
• For example:
  • Associative Lookup = & time unit is typically less than 10% of memory access time
  • Consider a = 80%, ε = 20ns for TLB search, 100ns for memory access
  • EAT = 0.80 x 100 + 0.20 x 200 = 120ns
  • Consider a more realistic hit ratio is approximately equal to 99%.
  • EAT = 0.99 x 100 + 0.01 x 200 = 101ns

Memory Protection

• Memory protection is implemented by associating a protection bit with each frame to indicate if read-only or read-write access is allowed
  • Can also add more bits to indicate page execute-only, and so on
• Valid-invalid bit attached to each entry in the page table:
  • “valid” indicates that the associated page is in the process' logical address space, and is thus a legal page
  • "invalid” indicates that the page is not in the process' logical address space
  • Or use page-table length register (PTLR)
• Any violations result in a trap to the kernel

Shared Pages

• Shared code
  • One copy of read-only (reentrant) code shared is shared among processes
  • Similar to multiple threads sharing the same process space
  • Also useful for interprocess communication if sharing of read-write pages is allowed
• Private code and data
  • Each process keeps a separate copy of the code and data
  • The pages for the private code and data can appear anywhere in the logical address space

Structure of the Page Table

• Straightforward methods make memory structures for paging can get huge
  • Consider a 32-bit logical address space as on modern computers
  • Page size of 4 KB (2^12)
  • Page table would have 1 million entries (2^32 / 2^12)
  • If each entry is 4 bytes, 4 MB of physical address space / memory for page table alone
  • That amount of memory used to cost a lot
  • Don't that that contiguously in main memory
• Hierarchical Paging
• Hashed Page Tables
• Inverted Page Tables

Hierarchical Page Tables

• Break up the logical address space into multiple page tables
• A simple technique is a two-level page table
• Page the page table

Two-Level Paging Example

• A logical address (on 32-bit machine with 1K page size) is divided into:
  • a page number consisting of 22 bits
  • a page offset consisting of 10 bits
• Since the page table is paged, the page number is further divided into:
  • a 12-bit page number
  • a 10-bit page offset

64-bit Logical Address Space

• Even two-level paging scheme not sufficient
• If page size is 4 KB (2^12)
  • Then page table has 2^52 entries
  • If two level scheme, inner page tables could be 2^10 4-byte entries
• Address would look like: outer page, inner page, and page offset
  • Outer page table has 2^42 entries or 2^44 bytes
• One solution is to add a 2nd outer page table
• But in the following example the 2nd outer page table is still 2^34 bytes in size
  • And possibly 4 memory accesses to get to one physical memory location

Inverted Page Table

• All physical pages are tracked, as opposed to each process having a page table and keeping track of all possible logical pages.
• There is one entry for each real page of memory.
• With information about the process that owns a page, the virtual address of that particular page is virtually stored in that particular real memory location.
• Time is used to search the table when a page reference occurs despite the decreased memory needed.
• A hash table is used to limit the search to one - or to a few page-table entries.
• A TLB can accelerate accesses.

Example: The Intel IA-32 Architecture

• Supports both segmentation and segmentation with paging.
  • Each segment can be 4 GB
  • Up to 16 K segments per process.
    • Divided into two partitions
      • First partition of up to 8 K segments are private to process (kept in local descriptor table (LDT)).
      • Second partition of up to 8K segments shared among all processes (kept in global descriptor table (GDT)).
• Selector given to segmentation unit - Which produces linear addresses
• Linear address given to paging unit - Which generates physical address in main memory - Paging units form equivalent of MMU - Pages sizes can be 4 KB or 4 MB

Intel x86-64

• A current generation Intel x86 architecture.
• 64 bits is ginormous (>16 exabytes)
• In practice only implement 48 bit addressing.
  • Has page sizes of 4 KB, 2 MB and 1 GB.
• Four levels of paging hierarchy.
• PAE can be also used for the reason that virtual addressed can be 48 bits and physical addresses can be 52 bits.

Example: ARM Architecture

• Dominant mobile platform chip used in many Apple and Google Android devices
• Modern, energy efficient, 32-bit CPU
• Uses of 4 KB and 16 KB pages.
• Uses 1 MB and 16 MB pages segments which are termed sections.
• One-level paging for sections, two-level for smaller pages.
• Two levels of TLBs
  • Outer level has two micro TLBs (one data, one instruction).
  • Inner is single main TLB
• First inner is checked. On miss outers are checked, and on miss page table walk performed by CPU