CIS 307: Storage Management

Storage Management is treated in Tanenbaum, Chapter 3. Here I want to mention the topics that I expect students to know before getting into Virtual Memory. Essentially, to study pages 74 to 88, and to review algorithms for storage management. Be sure to study and understand:

• the 50% percent rule [The number of holes is 50% of the number of segments in the case that allocation is of variable size blocks]
• the unused memory rule [f = k/(k+2), where f is fraction of space lost to holes and k is the size of a hole, relative to the average segment size], and
• the relation between memory size and degrees of multiprogramming [if p is the probability that a process is doing IO, and n is the degree of multiprogramming, then the CPU utilization is 1 - p**n]

Storage Management Algorithms

You should know how to use bit-maps for both fixed and variable size blocks. You should know how to use simple lists for fixed size blocks in main memory, and how to use shallow trees in secondary memory (fixed size). [The Unix file system will give us an example of such trees.] You should also know how to manage variable size blocks in main memory using appropriate lists or the Buddy system. Finally, you should have some understanding of garbage collection and its algorithms.

Fragmentation

Internal Fragmentation:

Suppose you are in a paged Virtual Memory, with pages, say, of size p. Then, if we are given a program of size S, we will require Ceiling(S/p) pages. That is, we will waste

p*Ceiling(S/p) - S bytes

This is called Internal Fragmentation.

External Fragmentation:

Suppose you are in a Segmented Virtual Memory. Then storage is allocated in variable size blocks. This results in the creation of holes of unallocated memory that are smaller than requests for new segments. These holes are essentially wasted storage (unless we compact storage). This we call External Fragmentation. Tanenbaum (page 88) discusses the Fifty percent Rule and the Unused Memory Rule. It is easy to see using those results, that in most situations external fragmentation is more wasteful than internal fragmentation. In fact, assuming that we have n segments, each of size s, then using the 50% rule the number of holes is n/2 for a loss (external fragmentation) of n/2*h, where h is the average size of a hole. The loss due to internal fragmentation is on average n*p/2, where p is the size of a page. Thus external fragmentation will be worse than internal fragmentation whenever the average size of holes is greater than a page.