Operating System Memory Management

Main Memory

• Main memory supports both operating system and user processes
• Memory is a limited resource, so efficient allocation is crucial
• Contiguous allocation is one early approach
• Memory is divided into partitions: resident OS (low memory, interrupt vector), user processes (high memory)
• Each process is in its own contiguous section

Protection

• Processes need protection from each other and the OS
• Base and limit registers define a process' logical address space
• The CPU checks every memory access to ensure it's within the base/limit range
• Instructions to load those registers are usually privileged

Address Binding

• Programs can be bound to memory addresses at different stages: compile time, load time, or execution time
  • Compile time: Addresses known at compile time.
  • Load time: Addresses known at load time.
  • Execution time: Addresses are determined at run time.
• Binding methods map symbolic addresses to absolute addresses

Multistep Processing

• Source program/code is first compiled, or assembled
• Then object modules are written
• Object modules are linked together
• The resulting executable load module is loaded by the loader

Logical vs Physical Address Space

• Logical (virtual) address is generated by the CPU
• Physical address is used by the memory unit
• In compile-time and load-time, the logical and physical addresses are the same.
• They differ in execution time.
• Logical address space is the set of all logical addresses generated by a program.
• Physical address space is the set of all physical addresses generated by a program

Memory-Management Unit (MMU)

• Hardware that maps logical to physical addresses at runtime
• This is a generalization of the base-register scheme (the relocation register)
• Used to protect user processes from each other

Dynamic Loading

• The entire program isn't loaded into memory at once
• Routines loaded only when needed
• Improves memory usage

Dynamic Linking

• Linking of libraries is postponed until execution time
• Uses stubs to locate routines
• Implementation of shared libraries

Contiguous Allocation (cont.)

• Relocation registers needed to protect user processes from each other and from changing operating system code/data
• Base register contains smallest physical address
• Limit register contains the range of logical addresses
• Allows for dynamic mapping of logical to physical addresses

Variable Partition

• Multiple partitions of variable sizes
• Holds OS and user programs
• Free memory areas (holes)
• The OS maintains a record of free blocks of memory

Dynamic Storage Allocation

• Methods (First-fit, best-fit, worst-fit) to satisfy requests for memory allocation sized 'n' bytes
• First-fit: fastest, but doesn't necessarily minimize leftover space
• Best-fit: minimizes leftover space, but slowest.
• Worst-fit: allocates the largest hole, producing the largest leftover hole.

Fragmentation

• External fragmentation: Memory space exists, but it is not contiguous.
• Internal fragmentation: Assigned memory is larger than needed.
• Compaction: Attempts to reduce external fragmentation by moving memory blocks

Paging

• Physical address space of a process can be noncontiguous
• Improves external fragmentation
• Divides physical memory into fixed-sized blocks
• Divides logical memory into blocks of same size

Address Translation

• CPU-generated address divided into page number and page offset
• Page number is used as an index to a page table
• Page offset is combined with the base address to define the physical memory address

Paging Hardware

• Logical to physical address mapping
• Page table hardware

Paging Model

• Logical memory and physical memory are divided into pages
• Logical page number corresponds to a specific physical frame

Paging Example

• Showcases logical and physical address mapping with page table lookup

Paging - Calculating internal fragmentation

• Calculates internal memory wasted due to paging.

Free Frames

• Free frames stored in a free-frame list
• Allocation occurs using the free-frame list
• Free frames are added back to free-frame list upon deallocation

Implementation of Page Table

• Page table kept in main memory
• Page-table base register (PTBR) and length register (PTLR)

Translation Look-Aside Buffer (TLB)

• Special fast-lookup hardware cache
• Maps logical to physical addresses

Hardware

• Associative memory is used for parallel search
• Address translation uses page number and the associative register
• Page number in register, frame number returned
• Otherwise, search in memory page table

Paging Hardware with TLB

• A diagram showing the steps involved in the TLB lookup

Effective Access Time

• Calculating effective access time considering hit ratio.

Memory Protection

• Mechanisms used for memory protection
• Valid-invalid bit in the page table

Valid or Invalid Bit

• Valid: indicates the page is in the process' logical address space
• Invalid: indicates the page isn't in process' logical address space

Shared Pages

• One copy of read-only code shared amongst multiple processes
• Improves efficiency and reduces memory usage
• Multiple processes can access the shared memory

Shared Pages Example

• Example of how page tables for shared code/data are organized

Structure of the Page Table

• Memory structures for paging
• Dividing page tables into smaller units
• Hierarchical paging, hashed page tables, inverted page tables

Two-Level Paging

• Dividing a 32-bit logical address into two page numbers and an offset
• Mapping to page tables

64-bit Logical Address Space

• When 64-bit logical addresses are involved

Three-Level Paging

• A variant of multilevel page table structure
• Addresses are broken down into three page numbers

Hashed Page Tables

• Hashing virtual page numbers to virtual page entries in a hash table.

Inverted Page Table

• Only one entry per physical page instead of per virtual page for a process.

Oracle SPARC Solaris

• Example of a modern 64-bit operating system

Swapping

• Moving processes between memory and a backing store.
• Total physical memory space needed for processes may exceed physical memory.
• Methods to accommodate processes

Swapping (cont.)

• Swapping issues (address binding).
• Swapping variants found in operating systems like UNIX, Linux, and Windows

Context Switch Time

• Time for switching a process to another.
• Including the swap in/out times if necessary
• Increased context switching time

Context Switch time and Swapping (cont.)

• Constraints on swapping
• Considerations for pending I/O
• Use of double buffering

Swapping on Mobile Systems

• Differences in memory management to accommodate flash-based memory, limited cycles, low throughput

Swapping with Paging

• Swapping processes that require paging.

Example: The Intel 32 and 64-bit Architectures

• Dominant processors used in modern computing.
• Typical architectures used for 32-bit and 64-bit systems

Example: The Intel IA-32 Architecture

• Supports both segmentation and segmentation with paging.
• Details about how segments are handled in the architecture

Example: The Intel IA-32 Architecture (cont.)

• CPU generating logical addresses.

Logical To Physical Address Translation

• The transformation steps from a logical address to a physical address in IA-32 architecture.

Intel IA-32 Segmentation

• The segmentation unit in a 32-bit Intel processor.

Intel IA-32 Paging Architecture

• Page directory, page table layout.

Intel IA-32 Page Address Extensions (PAE)

• Increasing address space.

Intel x86-64

• Typical architecture for the 64-bit systems.

Example: ARM Architecture

• Describes the mobile platform chip architecture.
• Methods for paging, TLBs, and memory allocations.

End of Chapter 9

This quiz covers key concepts related to main memory management in operating systems, including memory allocation, protection, and address binding. Understand how processes interact with memory and the importance of efficient memory usage. Test your knowledge on how operating systems ensure process protection and handle memory addresses.