Understanding Physical Memory and Address Binding

In operating systems, managing memory efficiently is crucial for optimizing performance and ensuring effective program execution. This article provides an overview of physical memory, logical address spaces, program transformations, and relocation strategies.

Physical Memory

Definition

Physical memory refers to the actual hardware structure known as RAM (Random Access Memory). It consists of a linear sequence of words.

Word Size

• Word: A fixed-size unit of data, typically 1, 2, or 4 bytes.
• Physical Address: An integer in the range [0

Logical Address Space

Definition

The logical address space is an abstraction that facilitates program development and sharing of physical memory.

Logical Address

• An integer in the range [0

Mapping

Before program execution, the logical address space is mapped to a portion of the physical memory, and the program is copied into the corresponding physical memory locations.

Program Transformations

Source Module

• Definition: A program or component written in a symbolic language.
• Purpose: It must be translated by a compiler or assembler into executable machine code.

Object Module

• Definition: The machine-language output generated by a compiler or assembler from a source module.
• Characteristics: An object module may be self-contained and executable. Multiple object modules can be linked together by a linkage editor to form a load module.

Load Module

• Definition: A program or combination of programs that is in a form ready to be loaded into main memory and executed.
• Characteristics: It is the final output that can be executed directly by the computer’s hardware.

Relocation and Address Binding

Logical Address Spaces

During program transformation, compilers, assemblers, and linkers assume logical address spaces starting at address 0, as physical addresses are unknown until load time. Logical addresses for instructions and data can change throughout the transformation process.

Binding of Addresses

The final step in program loading involves binding logical addresses to actual physical addresses in memory.

Program Relocation

• Definition: The process of moving a program component from one address space to another, which can occur between two logical address spaces or from a logical address space to a physical address space.

Types of Relocation

1. Static Relocation: Binds all logical addresses to physical addresses before program execution. The addresses are fixed and do not change during execution.
2. Dynamic Relocation: Postpones the binding of logical addresses to physical addresses until the addressed item is accessed during program execution. This allows for more flexibility, as the program can be moved during execution.

Implementing Dynamic Relocation Using Relocation Registers

Relocation Register

• Definition: A register that holds the physical starting address of a program or component in memory.

Program Components

Programs are generally divided into three main components:

• Code: Contains the program instructions.
• Static Data: Contains constant or fixed data.
• Dynamic Data: Contains data that changes during execution.

Single-Register Scheme

• How it Works: In a simple memory management approach, all three components are combined into one contiguous block. The CPU uses a single relocation register loaded with the program’s starting address. It automatically adds the relocation register’s value to every logical address to compute the corresponding physical address.

Multi-Register Scheme for Flexibility

• How it Works: A more flexible scheme separates the three components, allowing each to be placed in different areas of memory. Three separate relocation registers hold the starting addresses of the code, static data, and dynamic data modules. Each register’s value is added to logical addresses at runtime to obtain physical addresses.

Free Space Management

Memory Fragmentation

As programs are loaded and removed from memory, fragmentation occurs, resulting in varying sizes of free (empty) and occupied areas.

Holes

The operating system tracks these free spaces, or holes, using a linked list to efficiently allocate memory to new program components.

Coalescing Free Space

When a program is removed, any neighboring holes are merged (coalesced) to prevent excessive fragmentation and maintain usable free space.

Search Strategies for Free Space Allocation

1. First-Fit: Starts searching from the beginning of the list, allocating the first hole that fits the request.
2. Next-Fit: Begins each search from the last allocated point, aiming to spread out allocations.
3. Best-Fit: Searches the entire list to find the smallest hole that meets the request size, reducing leftover space.
4. Worst-Fit: Chooses the largest available hole for any request, maximizing the size of remaining holes.

Choosing a Strategy

Simulations show there is no universally best strategy; the effectiveness depends on:

• Average request size relative to memory size.
• Variance in request sizes.

Some strategies perform better when holes are kept sorted by size.

By grasping these concepts of physical memory, logical address space, program transformations, and memory management strategies, you can better understand how operating systems optimize resource allocation for efficient program execution.