Memory Allocation Strategies PDF

Module 5 Memory Management  Module 5 Contiguous Memory Location 22/09/24 2  Module 5 Introduction  The computer's memory must hold both the operating system (which controls the computer) and the various programs...

Module 5 Memory Management  Module 5 Contiguous Memory Location 22/09/24 2  Module 5 Introduction  The computer's memory must hold both the operating system (which controls the computer) and the various programs (or processes) that users are running.  The memory is typically divided into two main sections: one for the operating system and one for user processes.  Often, several user processes are running at the same time. This means the system needs to decide how to allocate the available memory to these processes. 22/09/24 3  Module 5 Contiguous Memory Location In contiguous memory allocation, each process is assigned a single, continuous section of memory and these sections are placed next to each other. 22/09/24 4  Module 5 Memory Protection When the CPU scheduler selects a process for execution, the dispatcher loads the relocation and limit registers. Every address generated by a CPU is checked against these registers The relocation-register scheme provides an effective way to allow the operating system’s size to change dynamically. 22/09/24 5  Module 5 Memory Protection 22/09/24 6  Module 5 Memory Location - Fixed/Static Partitioning  In this m eth od , the memory is divided into fixed-size blocks before any processes are loaded.  A problem arises when a process doesn't perfectly fit into a block. This leaves u n u sed gaps called "fragm en ts," which can waste memory.  Fragm en tation m akes it harder to allocate memory to new processes, and it can reduce the overall available memory. 22/09/24 7  Module 5 Memory Location - Dynamic Partitioning  One of the simplest methods of allocating memory is to assign processes to variably sized partitions in memory, where each partition may contain exactly one process.  The operating system keeps track of which parts of memory are available and which are occupied using a memory table. 22/09/24 8  Module 5 Memory Location - Dynamic Partitioning Figure: Variable partition. 22/09/24 9  Module 5 Memory Location - Dynamic Partitioning  Initially, all memory is considered one large "hole" that can be divided into smaller holes as needed.  When a process arrives, the system searches for a hole that's big enough to fit it. If the hole is too large, it's split into two parts.  When a process finishes, its memory is returned to the set of holes, which can then be merged with adjacent holes to create larger ones. 22/09/24 10  Module 5 Memory Location - Dynamic Partitioning  The dynamic storage allocation problem involves effectively managing memory by satisfying requests for memory blocks of varying sizes from a list of available memory blocks (holes).  A hole is a block of contiguous memory that is currently unoccupied. It's available for allocation to processes or other data structures. 22/09/24 11  Module 5 Dynamic Storage Allocation Problem How to satisfy a request of size n from a list of free holes? Three strategies first-fit, best-fit, and worst-fit strategies are the ones most commonly used to select a free hole from the set of available holes. 22/09/24 12  Module 5 Dynamic Storage Allocation Problem First fit. Allocate the first hole that is big enough. Searching can start either at the beginning of the set of holes or at the location where the previous first-fit search ended. For example, suppose we have the following memory partitions: | 10 KB | 20 KB | 19 KB | 25 KB | 30 KB | Now, a process requests 18 KB of memory. The OS starts searching from the beginning and finds the first free partition of 20 KB. It allocates the process to that partition and keeps the remaining 2 KB as free memory. 22/09/24 13  Module 5 Dynamic Storage Allocation Problem Best fit. Allocate the smallest hole that is big enough. We must search the entire list, unless the list is ordered by size. For example, suppose we have the following memory partitions: | 10 KB | 20 KB | 19 KB | 25 KB | 30 KB | Now, a process requests 18 KB of memory. The OS starts searching from the beginning and finds the partition of 19 KB. 22/09/24 14  Module 5 Dynamic Storage Allocation Problem Worst fit. Allocate the largest hole. Again, we must search the entire list, unless it is sorted by size. For example, suppose we have the following memory partitions: | 10 KB | 20 KB | 19 KB | 25 KB | 30 KB | Now, a process requests 18 KB of memory. The operating system searches for the largest free partition, which is 30 KB. It allocates the process to that partition and keeps the remaining 12 KB as free memory. 22/09/24 15  Module 5 Fragmentation  First Fit is fast and simple to implement  first-fit and best-fit strategies for memory allocation suffer from External fragmentation  External fragmentation exists when there is enough total memory space to satisfy a request but the available spaces are not contiguous 22/09/24 16  Module 5 Fragmentation  Statistical analysis of first fit, reveals that, even with some optimization, given N allocated blocks, another 0.5 N blocks will be lost to fragmentation.  That is, one-third of memory may be unusable. This property is known as the 50-percent rule.  This will increase the overhead so as to keep track of this holes  To avoid, break the physical memory into fixed-sized blocks and allocate memory in units based on block size 22/09/24 17  Module 5 Fragmentation  With this approach, the memory allocated to a process may be slightly larger than the requested memory. The difference between these two numbers is internal fragmentation — unused memory that is internal to a partition.  One solution to the problem of external fragmentation is compaction. The goal is to shuffle the memory contents so as to place all free memory together in one large block 22/09/24 18  Module 5 Fragmentation  Another possible solution to the external-fragmentation problem is to permit the logical address space of processes to be noncontiguous, thus allowing a process to be allocated physical memory wherever such memory is available.  This is the strategy used in paging, the most common memory- management technique for computer systems. 22/09/24 19  Module 5 Contiguous Memory Allocation Schemes – Problem 1 Suppose you have a memory with the following free blocks: 12KB, 6KB, 14KB, 19KB, 21KB. Four processes arrive that require 10KB, 4KB, 7KB, and 18KB of memory, respectively. Using the different allocation techniques, how the process would be allocated to memory. 04-10-2024 20  Module 5 Contiguous Memory Allocation Schemes – Problem 1 – First Fit Process Process Block Availability Can Occupy Block Size Block Status Memory Wastage No. Size No. Status Process ? B1 12KB Yes B2 6KB Yes B3 14KB Yes B4 19KB Yes B5 21KB Yes 04-10-2024 21  Module 5 Contiguous Memory Allocation Schemes – Problem 1 - First Fit Process Process Block Availability Can Occupy Process Block Block Size Memory Wastage No. Size No. Status ? Status P1 10KB B1 12KB Yes Check 10