Memory Management Strategies in Operating Systems | OS Tutorials

In an environment that supports dynamic memory allocation, the memory manager must keep a record of the usage of each allocatable block of memory. This record could be kept by using almost any data structure that implements linked lists. The memory manager keeps a free list pointer and inserts entries into the lists in some order conducive to its allocation strategy. Several strategies are used to allocate space to the processes that are competing for memory. Some of these strategies are –

Memory Management Strategies

Best Fit Allocation Strategy

• The allocator places a process in the smallest block of unallocated memory in which it will fit.
• We can also describe it as: allocate the smallest hole that is big enough. We must search the entire list, unless the list is kept ordered by size. This strategy produces the smallest leftover hole.
• Problem: 1. It requires an expensive search of the entire free list to find the best hole. 2. More importantly, it leads to the creation of lots of little holes that are not big enough to satisfy any request. This situation is called fragmentation and is a problem for all memory management strategies, although it is particularly bad for best-fit.
• Solution: One way to avoid making little holes is to give the user a bigger block than it asked for. For example, we might round all requests up to the next larger multiple of 64 bytes. That does not make the fragmentation go away; it just hides it. Unusable space in the form of holes is called external fragmentation.

Example Based on Best Fit Algorithm

• For the partition of 100 K, 500 K, 200 K, 300 K and 600 K as shown in Figure 2(a), place the processes of size 212 K, 417 K, 112 K and 426 K according to the best fit algorithm.
• Solution: The given situation is an example of static partitioning. Since the best fit algorithm allocates the smallest free partition that is big enough to accommodate a process and that results in the smallest unused memory fragment.

So, P_1, having size 212K, will be suitably allocated in the partition 300 K size. Similarly, for process P_2, having size 417, partition 500 is suitable; for process P₃, 200 K size, and for process P_4, 600K size is perfectly suitable.

Hence, Table 1 gives the total fragmentation of 433K on applying the best-fit algorithm.

First Fit Allocation Strategy

• Another strategy is first fit, which simply scans the free list until a large enough hole is found. Generally, it allocates the first hole that is big enough.
• First fit is better than the best-fit algorithm because it leads to less fragmentation.
• Problem: Small holes tend to accumulate near the beginning of the free list, making the memory allocator search farther and farther each time.
• Solution: Apply Next fit Algorithm.
• Example: Based on First fit Algorithm
• For the partition of 100 K, 500 K, 200 K, 300 K, and 600 K as shown in Figure 3, place the processes of size 212 K, 417 K, 112 K, and 426 K according to the first fit algorithm.
• Solution: If we apply first fit to the same data, then memory allocation is as shown in Figure 3 (a & b).

• For process P₁ (212 K), the first suitable partition is 500K, as we move from 0; hence, 212K will be allocated, leaving 288K memory as a hole.
• Process P₂ (417 K) is allocated to partition 600K as we move down, resulting in 183K memory as a hole.
• Process P₃ (112 K) is allocated to partition 200 K, resulting in 88K memory as a hole.
• Similarly, process P₄ (426 K) will not find any free partition to accommodate, hence it will wait until either P₂ or P₁ is swapped out from the memory.

Hence, the first fit algorithm gives total fragmentation of 559K, as shown in Table 2.

Next Fit Allocation Strategy

• A minor variation of first fit is next fit. It works the same way as first fit, except that it keeps track of where it is whenever it finds a suitable hole.
• The first fit approach tends to fragment the blocks near the beginning of the list without considering blocks further down the list.
• The problem of small holes accumulating is solved as it starts each search where the last one left off, wrapping around to the beginning when the end of the list is reached.

Worst Fit Allocation Strategy

• Allocates the largest hole. It always takes the largest available hole, so that the new hole will be big enough to be useful.
• We must search the entire list unless it is sorted by size. This strategy produces the largest leftover hole, which may be more useful than the smaller leftover hole from a best-fit approach.

Example based on Worst Fit Algorithm

• For the partition of 100 K, 500 K, 200 K, 300 K and 600 K as shown in Figure 4, place the processes of size 212 K, 417 K, 112 K and 426 K according to change this in other examples fit algorithm.
• Solution: Since, according to the worst fit algorithm, the OS allocates the largest free partition, leaving a large amount of memory as a free hole of memory (wasted fragment).

• For process P₁ of 212 K, a partition of 600 K is allocated since it is the largest free partition, leaving 388 K as a fragment hole.
• Process P₂ (417 K) allocates the partition of 500 K (i.e., the largest free partition), leaving 83 K as a fragment hole.
• Process P₃ (112K) allocates the 200 K partition, leaving 118 K as a fragment hole.
• Process P₄ (426K) will have to wait, since no partition is left. It will wait until partition 1 (500 K) or partition 4 (600 K) is freed.

Hence, the worst-fit algorithm will result in Total Fragmentation of 589K, as shown in Table 3.

Quick Fit Allocation Strategy

• Another allocation algorithm is quick-fit, which maintains separate lists for some of the more common sizes required.
• With quick fit, finding a hole of the required size is extremely fast, but it has some disadvantages.

Disadvantage of Quick Fit

• When a process terminates or is swapped out, finding its neighbour to see if a merge is possible and it is expensive.
• If merging is not done, memory will quickly fragment into a large number of small holes into which no processes fit.

External and Internal Fragmentation

• All the algorithms discussed so far suffer from external fragmentation. Processes being loaded and removed from memory result in memory space broken into small pieces.
• External fragmentation exists when enough total memory space exists to satisfy a request, but it is not continuous; storage is fragmented into a large number of small holes.
• Internal fragmentation is the difference between the requested memory and the allocated memory. Memory that is internal to a partition but is not being used.
• 50-Percent Rule: Depending on the total amount of memory storage and the average process size, external fragmentation may be either a minor or a major problem.
• Statistical analysis of first fit, for instance, reveals that with some optimization given N allocated blocks, another 0.5 N blocks will be lost due to fragmentation.
• Hence, one-third of memory may be unusable. This property is known as the 50 percent rule.

Allocation Algorithms

The problem here is finding the appropriate hole to meet a request for memory. We want to be able to grant as many requests as possible, but just like CPU scheduling, our enemy is uncertainty. These are analogous to CPU scheduling algorithms (in terms of linked lists):

• First Fit – satisfy the request with the first hole that can be used. Always start from the head of the list. (Average time N/2 – O(N))
• Next Fit – satisfy the request with the first hole that can be used. Start where the last search left off. (Average time N/2, but maybe more even memory utilization O(N))
• Best Fit – pick the hole with the closest size to the request. (O(N) – with a sorted list – implies O(N) time to insert a new hole, which we do on every allocation)
• Worst Fit – pick the hole that worst matches the request. Why? Best fit can result in a lot of small holes that are useless. Worst fit keeps big holes around. (Avg time is O(N/2) if we keep the list sorted (O(1) to find the hole and O(N) to insert it).
• Quick Fit – keep a list of common sizes and allocate from it.