Memory Management in Operating Systems

🖥️ Memory Management in Operating Systems

💡 Modern operating systems manage memory by creating an abstraction layer that allows processes to operate as if they are allocated contiguous memory, even when they are fragmented across physical RAM.

Logical Address Space

• Logical Address Space: The range of addresses that a process can access. This space is often larger than the available physical RAM, allowing for more efficient memory management.

• RAM Fragmentation: Modern operating systems can have processes spread throughout RAM. The CPU accesses these processes without being aware of their fragmented locations.

• Memory Access: The CPU translates logical addresses to physical addresses through a mapping managed by the operating system.

⚡ Key Fact: Logical address space can be significantly larger than physical RAM, allowing for more efficient memory utilization.

Process Swapping

• Process Swapping: The technique of temporarily moving inactive processes from RAM to a disk space to free up memory for active processes.

• Swapping Mechanism: This is typically implemented using a swap space on secondary storage. For example, Windows uses a special swap file, while Unix systems may use a dedicated swap partition.

• Efficiency Concerns: Swapping can be costly in terms of time, as accessing disk storage is much slower than accessing RAM.

📝 Definition: Swapping — The process of moving data from RAM to disk to free up memory for other processes.

Memory Partitioning

• Memory Partitioning: The division of RAM into fixed-size or variable-size segments, each designated for different types of processes (e.g., user processes, system operations).

• Fixed Partitions: Each partition is allocated a specific size and label, which can lead to inefficient memory use if processes do not fit perfectly into these partitions.

• Challenges: The main issues with fixed partitioning include poor RAM utilization and external fragmentation, where free memory is scattered in small chunks.

❓ Quick Check: What are the two main types of fragmentation that can occur in memory management?

📊 Memory Management: Paging and Segmentation

💡 Efficient memory management techniques like paging and segmentation optimize how processes access memory, impacting performance and resource utilization.

Paging

• Paging: A memory management scheme that eliminates the need for contiguous allocation of physical memory. It divides the logical memory into fixed-size blocks called pages.
• Page Table: The operating system maintains a page table that keeps track of the mapping between logical pages and physical frames in RAM.
• Associative Memory: To speed up access times, an associative memory (or cache) is used to store frequently accessed page table entries, reducing the time taken to access memory.

⚡ Key Fact: Without associative memory, the access time for paging can double due to the need for two memory accesses.

Segmentation

• Segmentation: Unlike paging, segmentation divides the logical address space into variable-sized segments based on the logical grouping of data, such as functions or data structures.
• Segment Table: Each process has a segment table that holds information about the segments, including their base addresses and lengths, allowing the operating system to manage memory more flexibly.
• Dynamic Allocation: Segments can be loaded into any available memory location, allowing for non-contiguous memory allocation, which can lead to better memory utilization.

📝 Definition: Segment Table — A data structure used in segmentation to keep track of the base address and length of each segment in a process's logical address space.

Comparison of Paging and Segmentation

• Memory Utilization: Paging can lead to internal fragmentation due to fixed-size pages, while segmentation reduces this issue by allowing variable-sized segments.
• Access Time: Both methods require validity checks, but segmentation requires an additional check for offset validity, which can impact performance.
• Logical Address Structure: In paging, the logical address consists of a page number and offset, while in segmentation, it consists of a segment number and offset within that segment.

❓ Quick Check: What is the main advantage of segmentation over paging in terms of memory allocation?

🖥️ Understanding Virtual Memory Management and Page Replacement

💡 Virtual memory allows systems to run larger applications than physical memory can accommodate, utilizing demand paging for efficient memory management.

Virtual Memory Basics

• Virtual Memory: A memory management capability that creates an illusion of a larger memory space by using disk space.
• Demand Paging: A technique where pages are loaded into RAM only when they are needed, enhancing efficiency.
• Page Fault: An event that occurs when a program accesses a page not currently mapped to physical memory.

⚡ Key Fact: Virtual memory allows multiple processes to run simultaneously, improving multitasking capabilities.

Page Replacement Strategies

• Page Replacement: The process of swapping out a page in RAM for a new page from virtual memory when RAM is full.
• FIFO (First-In-First-Out): Chooses the oldest page in memory to replace, but can lead to the Belady anomaly where increasing memory can increase page faults.
• Optimal Algorithm: Selects the page that will not be used for the longest period in the future, though it is impractical to implement.

📝 Definition: Belady's Anomaly — A phenomenon where increasing the number of page frames results in an increase in the number of page faults.

Implementing Page Replacement

• Victim Selection: The OS must decide which page to evict when RAM is full. It can use global or local strategies.
• Local Replacement: Focuses on selecting a victim page from the currently running process, minimizing overhead.
• Global Replacement: Considers all pages in RAM, potentially leading to increased complexity.

❓ Quick Check: What is the difference between local and global page replacement strategies?

📚 Data Storage Systems and Algorithms

💡 Understanding data storage systems is crucial for efficient data management and retrieval in operating systems.

Page Replacement Algorithms

• Least Recently Used (LRU): This algorithm selects the page that has not been used for the longest time, based on the idea that if it hasn't been needed so far, it likely won't be needed soon.

• Most Frequently Used (MFU): This method chooses the page that has been used the most, under the assumption that frequently accessed pages will continue to be accessed in the future.

• Delayed Algorithm: In this approach, a page is marked as a victim but is not immediately removed from RAM. Instead, it is retained for one more cycle, allowing for potential reactivation if needed.

⚡ Key Fact: The Delayed Algorithm helps avoid anomalies in FIFO by keeping recently used pages available for immediate access.

Collection Systems

• Data Structure: Data is stored in collections that occupy a specific number of units (bytes). Each collection can be viewed as a set of logical or physical records.

• Logical vs. Physical Records: Logical records represent data meaningfully (e.g., names), while physical records are the actual bytes stored on the disk. Understanding this distinction is essential for data organization.

📝 Definition: Collection System — A set of rules that governs how data is stored and organized on a storage medium.

Attributes of Collections

• Symbolic Name: Each collection should have a recognizable name, such as "practice_1," which aids in identification.

• Type of Collection: Different types of collections (e.g., files) are indicated through extensions like .png or .exe, which helps the operating system understand how to handle the data.

• Location and Size: The location refers to the disk address where the collection is stored, while size can be measured in bytes or blocks, influencing how data is accessed and managed.

❓ Quick Check: What are the two main types of records in a collection system?

📊 Data Structure Management in File Systems

💡 This section explores the complexities of managing data structures in file systems, focusing on access methods, deletion strategies, and protection mechanisms.

Connection Types

• Symbolic Links: These links store a pointer to a collection located elsewhere, allowing for flexible referencing without duplicating data.

• Hard Links: Unlike symbolic links, hard links create multiple directory entries for the same data, enabling access from various paths without data duplication.

• Deletion Strategies: The challenge arises when deleting collections that can be accessed via multiple paths. Strategies include deleting when any link is removed, keeping the collection until all links are deleted, or maintaining a reference count to track active connections.

⚡ Key Fact: Hard links are easier to implement but harder to maintain compared to symbolic links.

Protection Mechanisms

• Attribute-based Protection: File systems use attributes to define what actions users can perform on collections. Traditional systems require extensive user access lists, which can be inefficient.

• Unix Grouping: Unix simplifies protection by categorizing users into three groups: owners, group members, and others, each with customizable access levels (read, write, execute).

📝 Definition: Access Control — A method of restricting access to files based on user permissions and roles.

Storage Implementation

• Multi-layered Support: Operating systems provide multi-layered support for file systems, activating specific functions at each layer when accessing data.

• Data Access Process: When opening a collection, the OS checks its existence and permissions, followed by calculating the disk address for reading or writing data.

• Direct Memory Access (DMA): This mechanism allows data transfer from disk to memory without CPU involvement, enhancing efficiency.

❓ Quick Check: What are the three user groups in Unix systems that determine access levels?

File Control Block (FCB)

• FCB Overview: The FCB contains essential information about a collection, detailing what operations the processor can perform.

• Mounting Process: Data carriers are typically mounted during OS loading or when a media device is inserted, establishing a hierarchy for data access.

• Storage Methods: Collections can be stored in a contiguous manner, linked lists, or through paging techniques, each with its advantages and drawbacks regarding access speed and fragmentation.

📊 Key Stat: Contiguous storage allows for optimal access time due to minimal movement of read/write heads on disks.

💾 Advanced Data Storage Schemes and Disk Scheduling Algorithms

💡 This section explores complex data storage schemes and disk scheduling algorithms essential for efficient data management and retrieval.

Three-Level Storage Scheme

• External Index Block: This block is divided into smaller parts when it exceeds cluster size. Each part can fit into a cluster, allowing for efficient data access.

• Data Retrieval Process: The retrieval follows a sequence: read the external external index block, then the external index block, followed by data from the sub-block, and finally access the actual data.

• Pointer Structure: Each external external index block contains n pointers, which in turn lead to n data entries within the indexed data structure.

⚡ Key Fact: This three-level scheme allows for optimal storage of both small and large data collections.

Combined Storage Scheme

• Inode Allocation: Each collection is assigned a unique inode that stores the index block location and data pointers, facilitating efficient data management.

• Direct Pointers: The first 512 KB of data is stored using direct pointers, while larger collections utilize indirect pointers to manage data efficiently.

• Double Indirection: If a collection exceeds the direct pointer capacity, a double indirect scheme is employed, allowing for multiple levels of pointers leading to data.

📝 Definition: Inode — A data structure on a filesystem that stores information about a file or directory.

Disk Scheduling Algorithms

• First-In-First-Out (FIFO): The first request to arrive is the first to be processed, which can lead to inefficient disk head movements.

• Shortest Seek Time First (SSTF): Prioritizes requests based on their proximity to the current disk head location, minimizing movement but can starve requests further away.

• Elevator (SCAN) Algorithm: Moves the disk head in one direction, servicing requests until it reaches the end, then reverses direction. This method optimizes access time but can have delays at the edges.

❓ Quick Check: What is the primary disadvantage of the SSTF algorithm in disk scheduling?

📊 Key Stat: The elevator algorithm can significantly reduce average seek time compared to FIFO, especially in systems with high request rates.