Operating Systems Memory Management Quiz

COMP2211 Operating Systems: Memory Management

• Course: COMP2211 Operating Systems
• Instructor: Mantas Mikaitis
• University: University of Leeds
• Semester: 1, 2024
• Week: 9, Lectures 15 and 16

Objectives

• Discuss the need for memory management in operating systems.
• Introduce the concept of paging.
• Introduce virtual memory.

Reading List

• Primary texts are Operating System Concepts (10th edition, 2018) and xv6 (4th edition, 2024).
• Specific chapter assignments are provided for each week, and some chapters are to be re-read.

Part I: Description of the Problem

• CPU can only directly access registers and main memory with cache in between.
• Programs are loaded from disk to memory in a process' memory structure.
• CPU requests either address and read requests or address, data, and write requests.
• Register access takes 1 clock cycle.
• Main memory (e.g., LD/ST instructions) takes multiple cycles, causing stalls in the CPU.
• Cache improves performance by reducing stall times.

Introduction

• Illustrates a hierarchical memory structure with decreasing access times in a descending order starting with registers and cache, then followed by main memory, nonvolatile memory and secondary storage, then tertiary storage like hard-disk drives, optical disks, and magnetic tapes.

Memory Protection

• Processes should only access their address space to prevent them to impact each other (or the operating system).
• Each process' memory is limited by a limit register.
• Addresses must fall within the base and limit range.
• Error occurs if the address goes beyond base+limit range

Base and Limit Registers

• These registers can only be accessed by privileged instructions in kernel mode.
• Only the OS can modify these registers to protect users from modifying the size of the address space.

Address Binding

• Programs on disk must be moved into memory for execution.
• Addresses are represented before the placement decision is made.
• Source programs have symbolic addresses, which the compiler binds to relocatable addresses relative to a reference address.
• The linker or loader binds the relocatable addresses to absolute addresses.
• Address binding can occur at compilation time, loading time, or execution time.
• Execution time binding is the most common implementation in modern operating systems.

Logical and Physical Address Spaces

• Logical address is generated by the CPU.
• Physical address is used by the memory unit.
• Logical and physical address spaces are separate.
• Compile-time and load-time binding result in equivalent logical and physical addresses.
• Execution-time binding separates logical and physical spaces.

Memory-Management Unit (MMU)

• The MMU uses a relocation register (base register) to translate virtual addresses to physical addresses.
• User processes never see the actual physical addresses.
• The MMU performs execution-time address binding during memory accesses.

Dynamic Loading

• Entire programs do not need to be in memory during execution.
• Only parts of a program are loaded when needed.
• Improved memory usage by delaying loading of unused code and data.
• Programs are stored as relocatable load format on disk.

Dynamic Linking

• System libraries and program code are combined into a binary executable at execution-time.
• Commonly used with system libraries to load them only when needed.
• Allows sharing system libraries among processes (DLLs or shared libraries)
• Helps versioning as updated libraries can be used without recompiling programs.

Part II: Contiguous Memory Allocation

• OS and processes share memory, requiring contiguous allocation for concurrent execution.
• Memory is partitioned into two areas for operating system and processes.
• Processes are stored as single, contiguous blocks in memory.
• Protection is needed to prevent processes from interfering with each other or the operating system.

Memory Allocation

• Track free and occupied partitions.
• Initially, all memory is a single free block.
• Allocate variable-size partitions as needed.
• Memory holes of variable sizes form when processes exit.

Memory Allocation Methods (e.g., first-fit, best-fit, worst-fit)

• First-fit: allocate the first available block large enough to satisfy the request.
• Best-fit: allocate the smallest block that satisfies the request.
• Worst-fit: allocate the largest block that satisfies the request.

Internal Fragmentation

• Extra, unused space within an allocated block, arises from fixed partition sizes

External Fragmentation

• Memory space not contiguous for satisfying a memory request because of the existence of small, unused memory blocks.

Reducing External Fragmentation (Compaction)

• Shuffle memory contents to merge free holes into one large contiguous area.
• Requires dynamic relocation and updating relocation registers.

Part III: Paging

• Previous methods require contiguous memory, leading to fragmentation.
• Paging solves this by allowing processes to view memory contiguously despite fragmented physical memory.
• The MMU and OS collaborate to provide this method.

Basic Paging Method

• Divide physical memory into fixed-size blocks called frames.
• Divide virtual memory into fixed-size blocks called pages.
• Allocate frames to map pages to physical memory locations.
• Page tables map virtual addresses to physical addresses.
• CPU generates page number(p) and offset(d) to access required memory location. -Entry p in page table contains a base address of the corresponding frame.
• Offset d locates the specific memory address within the frame.

Hardware Support

• MMU performs translation of logical addresses to physical addresses using page tables stored in memory.
• The MMU utilizes page tables to perform translations more efficiently.

Paging Example

• Demonstrates mapping of a process's logical memory to physical memory frames.
• Illustrates the mapping process in a table format.

Page sizes

• Pages are commonly 4 or 8 KB in size.
• Some systems offer options for larger page sizes known as huge pages.

Frame allocation for Paging

• Process arrival with specific page size requirements.
• Allocate frames.
• Assign frame numbers to pages using the page table.

Paging Implementation

• Create page table for each process.
• Process Control Block (PCB) stores the page table address.
• Hardware page tables use high-speed registers.

Translation Lookaside Buffers (TLBs)

• Fast associative memory to store page mappings between virtual and physical addresses.
• TLBs speed up address translation, checking for existing mappings before accessing the page table.

Memory Protection with Pages

• Page tables include read/write restrictions.
• A valid bit indicates the page is in the process' logical address space.
• An invalid bit indicates the page is outside of the logical address space.

Protection with Pages: Page-table Length Register (PTLR)

• PTLR stores page table size for memory protection.

Shared Pages

• Paging allows efficient code sharing between processes.
• Reentrant code does not modify itself.
• Processes can share pages for the same code.

Hierarchical Paging

• Split large page tables into multiple levels to reduce size.
• This arrangement is typical for large address spaces.
• It uses multiple levels of page tables for improved efficiency.

Hierarchical Paging Address Translation

• Illustrates a two-level hierarchical page table structure for 64-bit architectures.
• Shows address resolution using multiple page tables.

Part IV: Memory Swapping

• Swapping copies processes between main memory and backing store (disk) when memory is full.
• Provides more RAM appearance.
• Swapping allows process continuity while not simultaneously residing in main memory.

Swapping with Paging

• Processes can be swapped between memory and backing store at the page level.
• The OS manages page swapping to maintain efficient system operation.

Swapping in mobile systems

• Mobile operating systems (e.g., iOS) might not support page swapping due to flash memory limitations.
• Limitations include space limitations and flash memory degradation.

Part V: Virtual Memory

• Virtual memory extends logical address space beyond physical memory size.
• Combines physical memory and backing store.
• Creates the illusion of a larger memory space.

Virtual Memory: Introduction

• Memory management that makes the logical memory seem larger than the physical memory. Instructions are stored and retrieved as needed from backing storage as requested by processes.
• Programs have a larger logical view of memory compared to the physical memory size.
• Increased program size, more programs running simultaneously, and less I/O are benefits. Memory is not necessarily contiguous but seen as such by processes.

Virtual Memory and the Heap

• Heap grows upwards.
• Stacks grow downwards.
• Memory holes occur in the space between the stack and heap.

Virtual Memory and Shared Pages

• Processes have shared memory in their virtual spaces.
• Shared pages are present identically in all participating processes’ physical memory region.

Part VI: Page Replacement

• The OS handles page replacement when no free frames are available for the page.
• Processes are terminated.
• Swapping copies entire processes into memory to free up frames.

General Page Replacement Algorithm

• Find desired page location in backing storage.
• Identify a victim page.
• Copy victim's contents to backing storage.
• Update page and frame tables.
• Fill free frame with desired page.

Page-replacement Algorithms

• FIFO (First-In, First-Out), OPT (Optimal), and LRU (Least Recently Used)

Demand Paging

• Strategy to load (bring in) pages into physical memory just when they are needed.
• Helps manage memory effectively. Improves efficiency because it loads pages of a program only when needed.