Paging in Memory Management

Paging

• A memory management technique where processes are divided into fixed-size units called pages.
• Main memory is also divided into fixed-size units called frames.
• One page is stored in one frame.
• Pages are only loaded into memory when needed, otherwise they reside in secondary storage.
• Frame sizes are defined by the operating system.
• Page size must be equal to frame size for efficient mapping.
• Example:
  • System with 16KB memory, frame size of 1KB, resulting in 16 frames.
  • Four 4KB processes (P1, P2, P3, P4) each divided into 1KB pages.
  • Initially, all frames are empty.
  • Processes P2 and P4 are moved to the waiting state, freeing 8 frames.
  • A new process P5 (8KB, 8 pages) waiting in the ready queue can be loaded into the available frames.

Advantages of Paging

• Reduces external fragmentation.
• Simple to implement.
• Efficient due to the equal page and frame sizes.
• Makes swapping processes easier.

Disadvantages of Paging

• Requires extra memory for the page table.
• Not suitable for systems with small RAM.

Segmentation

• Memory management technique where memory is divided into variable-sized units called segments.
• Segments can be allocated to processes, and do not need to be contiguous in memory.
• Segmentation doesn't create internal fragmentation but may create external fragmentation.
• Example:
  • Process divided into code, data, and stack segments of different sizes.
  • Each segment can be stored anywhere in memory.

Segment Characteristics

• Variable sized partitioning scheme.
• Secondary memory and main memory are divided into partitions of unequal sizes.
• Partition sizes depend on the length of modules.
• Partitions in secondary memory are called segments.

Segment Table

• Stores information about each segment of a process.
• Two columns:
  • Size or length of the segment.
  • Base address or starting address of the segment in main memory.
• Stored as a separate segment in main memory.
• The Segment Table Base Register (STBR) stores the base address of the segment table.
• Limit indicates the length or size of the segment.
• Base indicates the base address or starting address of the segment in main memory.

Translating Logical Address into Physical Address

• CPU-generated logical addresses have two parts: segment number and offset.
• Segment number is mapped to the segment table.
• Offset is compared to the limit address.
• If offset is less than the limit, the address is valid.
• Valid address: base address of the segment + offset = physical address.

Fixed-Size Partitioning

• Divides memory into fixed-size partitions.
• Partitions may or may not be the same size, but the size of each partition is fixed.
• Partitions are allocated to processes as they arrive.
• Example:
  • 15KB memory divided into fixed-size partitions.

Advantages of Fixed-Size Partitioning

• Simple and easy to implement.
• Supports multiprogramming as multiple processes can be stored in main memory.

Disadvantages of Fixed-Size Partitioning

• Internal Fragmentation: occurs when a process is smaller than the allocated partition, wasting memory within the partition.
• Limitation on process size: a process larger than the maximum partition size cannot be loaded.
• External Fragmentation: occurs when there are enough free spaces in memory but they are not contiguous, preventing the allocation of a larger process.
• Degree of multiprogramming is limited and fixed.

Variable-size Partitioning (Dynamic Partitioning)

• Overcomes the drawbacks of static partitioning, particularly internal fragmentation.
• Partition sizes are not declared initially.
• Partitions are created dynamically when a process arrives, the size of the partition is equal to the size of the process.
• No internal fragmentation as there is no wasted space within partitions.

Advantages of Variable-size Partitioning

• No internal fragmentation.
• Dynamic degree of multiprogramming.
• No limitations on process size, partitions are allocated dynamically to accommodate any process size.

Disadvantages of Variable-size Partitioning

• External Fragmentation: occurs when free spaces in memory are not contiguous, preventing the allocation of a larger process. This is a major issue.
• Difficult to implement: requires dynamic memory allocation at runtime, making it more complex.

Non-Contiguous Memory Allocation

• Allows parts of a process to be stored in non-contiguous memory locations.

Advantages of Segmentation

• No internal fragmentation
• Average segment size is larger than the actual page size, potentially leading to less fragmentation.
• Less overhead, as the segment table is smaller than a page table.
• Easier to relocate segments than entire address spaces.
• Segment table is smaller than a page table in paging.

Disadvantages of Segmentation

• Can have external fragmentation.
• Difficult to allocate contiguous memory to variable-sized partitions.
• Costly memory management algorithms.

Virtual Memory

• Allows a computer to use secondary storage as if it were part of main memory.
• Uses hardware (MMU – Memory Management Unit) and software to operate.
• When an application is in use, data from that program is stored in RAM.
• The MMU maps logical addresses to physical addresses and automatically translates addresses.
• If RAM space is needed for something else (e.g. loading a page), data is swapped from RAM to virtual memory.
• The memory manager keeps track of the shifts between physical and virtual memory.
• When data is needed again, the MMU uses a context switch to resume execution.

Demand Paging

• Loads a page into memory only when it's actually needed (on demand).
• Triggered by a page fault (when the CPU tries to access a page not currently in memory).
• Example:
  • CPU tries to access a page not in memory.
  • An interrupt is generated, indicating a memory access fault.
  • The OS puts the interrupted process in a blocking state.
  • The OS finds the required page in the logical address space.
  • The required page is brought from logical address space to physical address space (page replacement algorithms are used to decide which existing page to replace).
  • Page table is updated accordingly.
  • Process resumes execution.