7

Memory management must meet the following requirements:

• Relocation

• Protection of the memory of processes

• Sharing of memory

• Logical organisation • Physical organisation

It must be possible to execute a program from any location in memory

Processes must not write to or read from each other’s memory without permission. This also applies to the access of processes to the memory of the operating system.

Systems must allow processes to share physical memory.

Logical memory organisation

• Memories are physically organised in one-dimensional address spaces.

• Programs are organised in a different manner (text, data, stack sections).

• Programs use functionalities that are stored in libraries. It is not necessary to store them in multiple locations in memory (e.g. DLL files in Windows or shared libraries in Unix-like systems).

Physical memory organization

• Available physical main memory is usually not large enough to accommodate all processes completely and simultaneously.

• Mass storage devices can be used1 for storing main memory contents that are currently not needed and to give processes the illusion that more memory (physical main memory) is available.

• Data must be exchanged between main memory and mass storage devices.

The term refers to three mechanisms:

Logical Addressing

logical (virtual) addresses of a process are translated to available physical addresses so that every process can use its entire address space

Backing Store

this provides the illusion of having more memory than is actually available

Page file (Windows) or Swap Space (Unix-like)

Access Rights

Processes and OS may only write to or read from each others (physical) memory in a controlled manner

The logical (virtual) address space comprises all the addresses that the processor can specify

The code section holds the process instructions it does not start at address 0

Usually the lowest address (0) or highest is reserved for the OS

The Stack and Data section are dynamic and grow towards each other

Logical addressing can be implemented in two different basic principles:

• Segmentation

• Paging

2. Paging

• Divides logical memory into fixed-size pages and physical memory into frames of the same size.

• The logical address consists of a page number and an offset within that page.

• Pages are mapped to frames using a page table.

Advantages

• Eliminates external fragmentation.

• Simplifies memory allocation and management.

• Supports virtual memory, allowing processes to use more memory than physically available.

Disadvantages

• Can introduce internal fragmentation (unused space in the last page).

• Requires page tables, which can consume memory for large address spaces.

A page table provides information for the MMU on the allocation of pages to frames.

• The total virtual memory that is needed by all processes is usually larger than the available physical memory.

• The mass storage device has a file that is used to provide more (virtual) memory than is available as physical main memory. (Page file in Windows and swap space in Unix/Linux operating systems)

• This can be– but is not necessarily– the entire address space of a processor.

• Moved pages are stored in the page file in sequential order.

MMU analyses the field and generates exceptions to access an address which is not in main memory

The exception service routine transmits this information to the backing store management, which moves the page from the mass storage device to main memory

Therefore it might be necessary to remove pages -> page replacement

Page Replacement Algorithms

FIFO (First-In, First-Out)

• Strategy: The oldest page in memory is replaced first.

• Pro:

  • No page is kept in memory permanently.

• Con:

  • A frequently used page may be replaced and then immediately reloaded, causing inefficiency.

LFU (Least Frequently Used)

• Strategy: Replaces the page with the fewest references. Tracks how many times each page is used.

• Pro:

  • Frequently used pages are kept in memory.

• Con:

  • A page may remain in memory indefinitely after a period of heavy use, even if it’s no longer needed.

LRU (Least Recently Used)

• Strategy: Replaces the page that has not been used for the longest time. Tracks the recency of usage rather than frequency.

• Pro:

  • No pages persist unnecessarily; frequently used pages stay in memory.

• Con:

  • Requires additional hardware or software support to track recent usage efficiently.

1. The Program Status Word (PSW) indicates whether a process is executing in privileged mode or user mode, determining its access to restricted operations.

2. At the page level, additional access rights (such as read, write, and/or execute) are enforced based on privilege levels, defined in the page tables.

3. The Memory Management Unit (MMU) manages these access rights.

   • If a process violates its assigned access rights (e.g., a user process tries to write to a protected page), the MMU detects the violation and triggers an exception.

4. These exceptions are handled by the operating system, which can take appropriate action (such as terminating the process or handling a page fault).

Multi-level paging is a hierarchical paging system used to manage large logical address spaces, typically in systems with 32-bit or 64-bit architectures.

Instead of using one large page table, the page table is split into multiple levels, which reduces memory overhead and allows for efficient management of sparse address spaces.

Why Multi-Level Paging Is Needed

• In a single-level paging system, the entire page table must be kept in memory, which can be very large.

• For example:

  • A 32-bit system with 4 KB pages needs a page table with 1 million entries (4 bytes each ➔ 4 MB table).

• Multi-level paging solves this by dividing the page table into smaller pieces, loaded only when needed.