Concepts of Memory Management

Chapter Objectives

Module Objectives

Upon completion of this chapter, students should be able to:

• Describe the objectives of multiprogramming memory allocation.

• Describe code compilation, linking, and loading processes.

• Describe how memory allocation schemes such as best-fit and first-fit work.

• Compare and contrast basic memory allocation techniques such as paging and memory segmentation.

• Describe the operation principles of each memory allocation technique.

• Given a scenario, identify the appropriate memory allocation technique.

Introduction

• The operating system (OS) plays a critical role in managing main memory (RAM).

• This vital function is managed by the memory management subsystem.

• This unit will address basic concepts of memory management in this module and delve into virtual memory in the subsequent module.

• In the early days of computing, specifically during batch programming, programs accessed the full range of physical addresses directly.

  • The OS would sequentially load jobs, run them, and unload them as needed.

• The advent of multiprogramming transformed this process, allowing multiple processes to reside in memory simultaneously.

Objectives of Memory Management Subsystem

To support secure multiprogramming and multiprocessing, the memory management subsystem must implement effective strategies for memory sharing. This encompasses the following objectives:

1) Allocation/Relocation

• Programmers may not know which programs will occupy main memory at runtime.

• The memory management subsystem allocates memory spaces to processes accordingly.

• Active processes can be swapped in and out of main memory to enhance processor utilization and may need relocation to different memory segments.

2) Protection

• Running processes must obtain authorization to access specific memory locations for read/write operations.

• Memory references from a process must be validated during execution, with mechanisms for relocation providing corresponding support for protection.

3) Sharing

• Sharing enhances the efficiency of process access, allowing multiple processes to utilize a single copy of a program rather than requiring separate copies.

• Memory management must facilitate controlled access to shared memory areas without undermining protection.

• Mechanisms must also sustain relocation functionalities that support sharing.

4) Logical Organization

• Physical memory is inherently organized linearly (using physical addresses).

• In contrast, programs are developed in modules capable of independent execution utilizing program-generated logical addresses (often referred to as virtual addresses), differing from the utilized physical addresses.

• The memory manager ensures the correct mapping between logical and physical addresses through paging and segmentation.

• The memory management unit (MMU), a hardware component, assists with the translation of logical to physical addresses.

5) Physical Organization

• Memory consists of two storage levels: primary (RAM) and secondary (e.g., hard drives, flash drives).

• The memory management subsystem is tasked with transferring data between these two levels.

6) Virtual Memory

• Through relocation, sharing, and logical and physical organization, a process perceives its address space as contiguous and continuous temporally; however, this is not reflected physically.

• Physical addresses often become available to a process on an intermittent basis at disparate locations, yet processes assume continuous access to a cohesive logical address space.

• This principle defines virtual memory, which will be elaborated upon in Module 3-2.

From Code to Running Process

A) Main Memory Hardware

• CPU can only manipulate and access data in main memory or within CPU registers.

• Certain CPU commands necessitate the memory addresses of data before the CPU can process it.

• Each executed program and accessed file must be copied from storage devices into the main memory, where designated addresses are assigned.

B) From Source Code to In-Memory Image

Understanding memory management necessitates knowledge of how human-readable source code in high-level languages (HLL), such as C++ or Java, transitions into a binary format in a computer's memory. This process unfolds as follows:

Linking and Loading Concepts

High-level language programs undergo a three-stage processing sequence:

1. Stage 1:

   • The HLL source program is compiled, resulting in object code.

   • This object code may suffice for generating a relocatable process, depending on the program. However, since many programs are compiled in segments, this code frequently must connect with other object modules.

   • The compiler also places stubs where runtime libraries may be linked.

2. Stage 2:

   • All object modules possessing adequate linking information for static linking are processed.

   • The linking editor generates relocatable code while preserving the stubs from the compiler for library linking.

3. Stage 3:

   • The final step involves arranging and substituting the stubs with run-time library code, resulting in a complete relocatable code.

   • Upon completion of these three stages, an executable is formed, and the program, once in the main memory, becomes a running process.

Compiler Generated Bindings and Logical Address

• Before executing a process in memory, the CPU generates an address that allows references to program components and instruction execution.

• This address, referred to as a logical address or virtual address, is distinct from where the program is physically housed.

• The compiler first translates the source code from C++ or Java into assembly code, which consists of instructions executable by the CPU.

• For instance, if there's a variable v in program P and the compiler assigns v a fixed address, this allocation is termed binding.

• Compilers generate relocatable code, signifying that the program can reside anywhere in physical memory.

Physical Address

• The physical address denotes where a program's component resides in memory.

• Logical and physical addresses align in compile-time and load-time address-binding but diverge in the execution-time binding scheme.

Definitions Relevant to Memory Partitioning Schemes

Dynamic Loading

• Enhances memory utilization by avoiding the load of unused routines, which is particularly useful for handling large code segments that occur infrequently without requiring special OS support, relying instead on program design.

Dynamic Linking

• Delays linking until execution, utilizing a stub to locate the correct memory-resident library routine, necessitating OS involvement to confirm if the routine is within the process's memory address space.

Limit Register

• Stores the value defining the range of a physical address space, with the Base Register maintaining the smallest legal physical memory address.

• For instance, if the Base Register holds 2001234 and the Limit Register holds 1231234, permissible addresses range from 2001234 through 3232468, inclusive.

Swapping

• In scenarios where memory does not suffice for running process P2, a resident process, say P1, may be halted, removed from memory, and placed into secondary storage to create space for P2.

• The halted process is described as getting swapped out, and the OS later retrieves this process for continuation, termed swap in.

• More details on swapping will appear in the processor management module.

Fixed Partition Memory Allocation

• In fixed partition memory allocation, physical memory is divided into fixed-size partitions characterized as follows:

  1. Physical memory is divided into fixed partitions.

  2. Base register is a hardware requirement.

  3. Physical Address = Virtual Address + Base Register.

  4. Base register is loaded by the OS at the time of process switching.

  5. Each partition remains equal in size and does not vary.

  6. No partition may be shared among multiple processes.

Provision for Protection

• The Memory Management Unit (MMU) ensures that each process accesses only its designated partition.

Advantages

• Simple implementation and quick context switching.

Problems

• Internal Fragmentation: Occurs when the fixed-size memory allocated exceeds the requirements of a process, leaving unused memory.

• Partition Size: A limitation exists due to fixed partition sizing, which may lead to inefficiencies for larger processes.

• Contiguous Allocation: A single process cannot be segmented among multiple non-contiguous partitions; complete programs must be loaded into memory.

Dynamic Partition Allocation Schemes

Dynamic partition allocation represents a natural progression from fixed size allocation characterized by:

• Physical memory is divided into variable-sized partitions.

• Base register and limit register are required as hardware.

• The virtual address space must be smaller than available physical address space to avoid protection faults.

  • Physical Address = Virtual Address + Base Register.

  • The limit register is crucial for protection; an exception fault will occur if (Physical Address > Base + Limit).

Advantages

• No internal fragmentation occurs as only the required memory is allocated for a given process.

Problems

• External Fragmentation arises due to job loading and unloading, resulting in empty fragmented memory locations.

• The entire program must still be loaded into memory for execution.

Best-fit and First-fit Allocation Schemes

To minimize external fragmentation, specific dynamic size allocation algorithms were developed to address multiple program sizes and varying empty memory slots.

a) Best-fit

• Assigns a program to the memory space that yields the smallest remaining empty space.

  • For example, if programs P1 (80 KB) and P2 (90 KB) compete for a 100-KB memory block, P2 is the better fit with just 10 KB of leftover space.

b) First-fit

• The OS scans through empty memory spaces and assigns the first adequate block found.

  • Best-fit requires more computational resources due to the continuous evaluations for the best fit, whereas First-fit offers quick matching yet typically results in more fragmentation.

Paging Allocation

Paging is characterized as follows:

• Logical memory is segmented into equally sized tables, with physical memory comprised of similarly sized frames.

• Paging resolves the external fragmentation issue by using fixed-size units, providing a seamless virtual address space ranging from 0 to N.

• A Page Mapping Table (PMT) is utilized to monitor the physical locations of pages, maintained invisibly by the OS.

Address Translation

• The virtual address is bifurcated into the virtual page number (VPN) and an offset.

• The VPN acts as an index within the page table to determine the Page Frame Number (PFN).

• The physical address thus resolves as PFN::offset.

• Protection is ensured as programs cannot reference memory outside their Virtual Address Space (VAS).

Paging Advantages

• Effortless memory allocation via a free list of fixed-size chunks, eliminating external fragmentation issues.

• Facilitates the management of program chunks due to uniform size, employing a valid bit to indicate references to swapped pages.

Problems

• There exist minor internal fragmentation accessories, particularly within the last frame occupied by a program.

• Memory reference overhead leads to two references per address lookup: one for the page table and another for the memory itself.

• The size of the memory required to maintain the page table can be significant, and the complete program must reside in memory prior to execution.

Segmentation-Based Allocation

Segmentation is a memory-sharing methodology wherein a single process's virtual address space is fragmented into segments potentially situated in non-contiguous areas of physical memory:

• Segment borders are shaped by the program's logical functional blocks rather than arbitrary sizes found in paging.

• As a result, segments correspond logically to functional groupings such as code procedures or data arrays.

Characteristics of Segmentation

• Virtual addresses format as .

• Natural extension of variable-sized partitions permits multiple segments per process.

• Hardware support is facilitated through multiple base/limit pairs indexed via a segment table.

Problems

• Impediments to Efficient Memory Usage: Larger segment tables lead to elevated overhead.

• More demanding hardware requirements necessitate keeping segments in main memory with hardware cache for speed enhancement.

• The complete program is required to be loaded for execution.

Summary and Comparison

Each memory allocation technique discussed holds distinct advantages and disadvantages. The principal concerns include fragmentation, inefficiency, and overheads. Figure 3-1.8 presents a summary contrasting various techniques explored throughout this chapter. Only simple solutions are analyzed here, which cannot adequately accommodate contemporary demands for multiprogramming and multiprocessing. Future modules will present advanced methodologies enabling virtual memory.

Comparison of Basic Memory Allocation Techniques

References

1. PCP Bhatt/IISc, Bangalore, "Operating Systems/Memory management Lecture Notes," [Online]. Available: https://nptel.ac.in/courses/Webcourse-contents/IISc-BANG/Operating%20Systems/pdf/LectureNotes/Mod%204LN.pdf [Accessed Aug. 14, 2019].

2. Alex C. Snoeren, "CSE 120: Principles of Operating Systems," University of California San Diego, [Online]. Available: https://cseweb.ucsd.edu/classes/sp08/cse120/lectures/120-sp08-l10.pdf [Accessed Aug. 14, 2019].