operating system mod3

3.1 MEMORY MANAGEMENT

Memory management deals with the management of primary memory, which consists of an array of bytes or words, each with its own address. The operating system (OS) is responsible for the following functions related to memory management:

• Keeping track of the status of each memory location.
• Determining the memory allocation policy.
• Implementing memory allocation techniques.
• Implementing de-allocation techniques.

Address Binding

• Definition: Refers to the process of associating a program's logical addresses to physical addresses in memory.
• Programs are stored on secondary storage as binary executable files.
• When executed, they are brought into the main memory and organized into a process. The collection of processes waiting in secondary storage to enter main memory forms the input queue.
• A process is fetched from the queue and placed in main memory, where it fetches instructions and data. Upon termination, it returns the allocated memory space.
• The process goes through various stages with addresses represented in different ways:
     - Source program: Uses symbolic addresses.
     - Compiler: Converts symbolic addresses to relocatable addresses.
     - Loader: Converts relocatable addresses to absolute addresses.
• Binding steps can occur at several times:
     - Compile time: If the process’s memory location is known, absolute code is generated. If the static address changes, recompilation is needed.
     - Load time: If the memory location is unknown, relocatable code is generated, and binding is deferred until load time.
     - Execution time: If the process moves during execution, binding is delayed until runtime, utilizing special hardware.

Logical Address vs. Physical Address

• Logical address (or virtual address): Generated by the CPU.
• Physical address: The address seen by the memory unit loaded into the memory register.
• Logical address space: Set of logical addresses generated by a program.
• Physical address space: Set of physical addresses corresponding to logical addresses.
• The mapping between virtual and physical addresses at runtime is handled by the Memory Management Unit (MMU), which uses a base register (or relocation register) that adds its value to the address generated by the user process before memory access.

Dynamic Re-location

• Dynamic Relocation: Perform address mapping from virtual to physical addresses at runtime, invisible to the user, allowing partially executed processes to move within memory without affecting their execution.

Dynamic Loading

• Loads routines into physical memory only when called, resulting in better memory utilization as unused routines remain unloaded.
• The calling routine checks if the desired routine is already in memory. If not, it prompts the loader to load it and updates the program's address table if required.

Dynamic Linking and Shared Libraries

• Dynamic Linking: Only the main program is initially loaded in memory. Procedures are loaded only upon request and linked at runtime.
• Each referenced routine contains a stub that determines its loading and manages memory presence.
• This permits library updates, allowing multiple versions to coexist, where older programs run with their specific linked versions.

3.1.1 Swapping

Swapping: Technique to temporarily remove inactive processes from memory, saving them to a backing store before bringing in a new process.

• Swapping can occur in a multi-programming environment under CPU scheduling schemes (e.g., round robin). Higher-priority processes can swap out lower-priority ones.
• The swapped process usually returns to its previous memory location unless address binding dictates otherwise (load time vs. runtime).

Swapping Conditions:

1. A process must remain completely idle to be swapped.
2. Other factors prevent swapping if the process is waiting for an I/O operation.

3.1.2 Contiguous Memory Allocation

This method splits main memory into fixed-size partitions, each containing a single process:

• The degree of multiprogramming correlates to the number of partitions.
• OS manages a table indicating free and occupied partitions.
• When a process terminates, its partition becomes available for another process.
• Processes are selected from the input queue to occupy any free partition.
• Large free holes in memory can be split for allocation.

Allocation Strategies

1. First fit: Allocates the first sufficiently large hole; scans memory from the beginning.
2. Best fit: Chooses the smallest hole that meets the requirement, resulting in minimal waste.
3. Worst fit: Allocates the largest hole available, which can reduce fragmentation but may lead to inefficient use of memory.

• Popular memory allocation strategies include first fit and best fit; however, both suffer from fragmentation.

Memory Protection

Memory Protection: Used to safeguard the OS and processes from unauthorized accesses. It employs

• A relocation register (specifying the smallest physical address)
• A limit register (defining the range of logical addresses).
• The MMU maps logical addresses dynamically using values from these registers.
• Each address generated is checked against these registers to protect programs from errors and unauthorized modifications.

Fragmentation

Two types exist:

1. Internal Fragmentation: Wasted space within a block due to allocation sizes exceeding request sizes.
2. External Fragmentation: Sufficient memory exists, but it's not contiguous, leading to multiple small holes.

• Compaction can mitigate external fragmentation when dynamically relocating is possible at runtime.
• Allowing non-contiguous logical address spaces can also address external fragmentation issues.

3.1.3 Segmentation

Segmentation conceptualizes memory as a collection of variable-sized segments (code, data, stack, heap, etc.):

• Each segment comprises a name and a length, with logical addresses denoted by a combination of segment identifiers and offsets.
• Implemented using a segment table with base and limit entries.
• Hardware checks protected bits associated with segments to restrict illegal memory access and allows for shared segments among processes.

Segmentation Advantages

• Eliminates fragmentation and allows for dynamic segment growth and dynamic linking.
• Segmentation is visible to programmers and enhances protection and sharing.

Segmentation vs. Paging

3.1.4 Paging

Paging is a memory management scheme allowing the physical address space of a process to be non-contiguous:

• Physical memory is divided into frames and logical memory into pages of equal size, facilitating easy swapping between physical memory and backing store.

Paging Elements

1. Logical Address: Divided into page number and page offset; the page table stores each page's base address.
2. Example:
      - Adapting an 8-page process with a page size of 4 bytes shows how logical addresses map to physical addresses based on frames.
3. Hardware Support: Can involve page tables in main memory instead of dedicated registers when large, employing Translation Lookaside Buffer (TLB) for quicker access to frequently used page entries.

Paging Protection

• Each frame in the page table is marked with protection bits (read-write, read-only) to manage access effectively.
• A valid-invalid bit states if a page is in a process’s logical address space, preventing illegal memory access attempts.

3.1.5 Structure of Page Table

Strategies for large logical address spaces include:

1. Hierarchical Paging: Divides the page table into smaller pieces for easier management.
2. Hashed Page Table: Utilizes hashing to manage larger address spaces within linked lists for efficient page lookups.
3. Inverted Page Tables: Contains a single entry for each physical page with information allowing effective process identification and space utilization.
4. Shared Pages: Common code sections can be efficiently shared memory-wise, reducing the excessive memory footprint.

3.2 Virtual Memory

Virtual memory optimizes RAM by allowing processes to access memory spaces larger than physical memory limits:

• Loads only the necessary portions of a process, enhancing efficiency and improving CPU utilization.
• Enables sharing and modularity in processes.

Demand Paging

In demand paging, not all pages swap in together; they load into memory only when needed:

• This approach reduces unnecessary loading and utilizes the page table with invalid bits for efficiency.
• Paging operations and page faults are managed through systematic I/O operations.

Performance of Demand Paging

• Increased page fault rates lead to system slowdowns; metrics assess the impact of various access times based on fault frequencies. Performance is heavily contingent on maintaining a low page fault rate through effective management strategies.

Page Replacement Strategies

When available frames run low, replacement strategies include FIFO, optimal replacement, and LRU algorithm approaches.

• Considerations for dirty bits and non-accessed pages develop tailored page swapping solutions for performance enhancement.

Frame Allocation Strategies

These compare local and global replacement approaches, focusing on how processes utilize shared frames while preventing thrashing scenarios:

1. Private or Shared: Local replacement restricts page swaps to a process's designated pages while global considers system-wide frame utilization.
2. Minimum Frame Allocation: Sets strict limits to guarantee processes receive enough pages to function efficiently, considering multiple instruction access across pages to avoid excessive page faults.

Memory-Mapped Files

Using memory-mapping allows files to map directly into a process's address space, enhancing access speed significantly and enabling efficient file handling, including shared states between processes while utilizing demand paging protocols.