Memory Management: Algorithms and Techniques

Memory Management Problems and Solutions

Deadlock Scenario

A system has four processes and five allocable resources. The current allocation and maximum needs are as follows:

What is the smallest value of x for which this is a safe state?

The needs matrix is as follows:

• 0 1 0 0 1
• 0 2 1 0 0
• 1 0 3 0 0
• 0 0 1 1 1

If x is 0, we have a deadlock immediately. If x is 1, process D can run to completion. When D is finished, the available vector is 1 1 2 2 1. Now, A has ‘10211’ and ‘11221’ is available which together satisfies maximum need. So, A is finished and now ‘2 1 4 3 2’ is available, which can satisfy C. Once C is done, the available resources are 3 2 4 4 2, which can help B finish. So, x =1 will do.

Memory Compaction

A swapping system eliminates holes by compaction. Assuming a random distribution of many holes and many data segments and a time to read or write a 32-bit memory word of 10 nsec, about how long does it take to compact 128 MB? For simplicity, assume that word 0 is part of a hole and that the highest word in memory contains valid data.

Almost the entire memory has to be copied, which requires each word to be read and then rewritten at a different location.

Reading 4 bytes takes 10 nsec, so reading 1 byte takes 2.5 nsec and writing it takes another 2.5 nsec, for a total of 5 nsec per byte compacted. This is a rate of 200,000,000 bytes/sec. To copy 128 MB (2²⁷ bytes, which is about 1.34 x 10⁸ bytes), the computer needs 2²⁷/200,000,000 sec, which is about 671 msec.

This number is slightly pessimistic because if the initial hole at the bottom of memory is k bytes, those k bytes do not need to be copied. However, if there are many holes and many data segments, the holes will be small, so k will be small and the error in the calculation will also be small.

Bitmap vs. Linked List for Memory Management

Compare the storage needed to keep track of free memory using a bitmap versus using a linked list. The 128-MB memory is allocated in units of n bytes. For the linked list, assume that memory consists of an alternating sequence of segments and holes, each 64 KB. Also assume that each node in the linked list needs a 32-bit memory address, a 16-bit length, and a 16-bit next-node field. How many bytes of storage are required for each method? Which one is better?

The bitmap needs 1 bit per allocation unit. With 2²⁷/n allocation units (i.e., bit count is 2²⁷/n which is of 2²⁴/n bytes) this is 2²⁴/n bytes. The linked list has 2²⁷/2¹⁶ or 2¹¹ nodes, each of 8 bytes, for a total of 2¹⁴ bytes. For small n, the linked list is better. For large n, the bitmap is better. The crossover point can be calculated by equating these two formulas and solving for n. The result is 1 KB. For n smaller than 1 KB, a linked list is better. For n larger than 1 KB, a bitmap is better. Of course, the assumption of segments and holes alternating every 64 KB is very unrealistic. Also, we need n <= 64 KB (note, n is the unit size) if the segments and holes are 64 KB.

Memory Allocation Algorithms

Consider a swapping system in which memory consists of the following hole sizes in memory order: 10 KB, 4 KB, 20 KB, 18 KB, 7 KB, 9 KB, 12 KB, and 15 KB. Which hole is taken for successive segment requests of a.) 12 KB b.) 10 KB c.) 9 KB for first fit? Now repeat the question for best fit, worst fit, and next fit.

First Fit: takes 20 KB, 10 KB, 18 KB. Best Fit: takes 12 KB, 10 KB, and 9 KB. Worst Fit: takes 20 KB, 18 KB, and 15 KB. Next Fit: takes 20 KB, 18 KB, and 9 KB

Virtual Address Translation

For each of the following decimal virtual addresses, compute the virtual page number and offset for a 4-KB page and for an 8 KB page: 20000, 32768, 60000. Assume 0 is the starting index.

For a 4-KB page size the (page, offset) pairs are (4, 3616), (8, 0), and (14, 2656). For an 8-KB page size they are (2, 3616), (4, 0), and (7, 2656).