The issue we address in this lecture is the efficient use of memory. The issue arises because of inefficiencies inherent in the way memory is allocated for arrays. When you declare an array of size 1000, all 1000 memory locations are reserved for the exclusive use of that array. No matter how many values you actually store in the array, you will always use 1000 memory locations. The same memory allocation strategy is used for most implementations of strings. I will use the term static allocation to refer to this memory allocation strategy, in which all the memory that a data structure might possibly need (as specified by the user) is allocated all at once without regard for the actual amount needed at execution time. The opposite strategy, dynamic allocation, involves allocating memory on an as-needed basis.
There always is an absolute maximum of memory that can be allocated: this is simply the amount of memory that is physically available on your computer (more precisely, the amount of memory that is addressable by your computer). No allocation strategy can get around this. The difference between static and dynamic allocation is illustrated by the following example.
With dynamic allocation, I will not even have to think about how many people might join the class, or how long their names might be. I can just as easily accommodate 30 people with 100-character names and 300 people with 10-character names.
The key idea is to regard all the available memory as a large global
pool that can be used for any purpose whatsoever. When you need
memory, you ask for just the amount you need; it is given to you from
the global pool and is marked as being no longer `free' so that a
subsequent request for memory does not allocate this same block again
for a different purpose. Memory allocation is done by some sort of
procedure call; in C,
malloc(n) allocates a block
of memory of size n bytes.
It is your responsibility to return memory to the global pool when you are finished with it; when you do so it will be marked `free' again and be available for other uses (you might get it again the next time you request some memory).
To continue our class-names example, we imagine that all the available memory is one large array to be used as a global pool:
We use gray shading to indicate the regions of memory that belong to the global pool, i.e. which are free. At present, all of it is free.
Now, if the user needs memory to store the name JOE, he must
requests enough space to store the string
"JOE". As it
happens, in C, all strings must be terminated by a special character
called `NUL' whose code is 0 and which is written
Therefore, the user needs 3 bytes to store
E, plus an additional byte for NUL.
Thus he requests 4 bytes by calling
Suppose he is given the first 4 bytes from the pool; then memory would now look like this:
The memory allocator keeps track of what memory is free and what memory has been allocated. It now knows that the 4 bytes which it gave to the user are no longer free; they are no longer in the global pool. This we represent visually by the fact that these bytes are no longer shaded gray.
The question marks now visible indicate that we do not know in what state the bits of this block of memory really are.
Note: Why not? (1) what's a valid initialization? (2) It is inefficient to initialize large blocks, especially when the next thing the user does is overwrite this initialization with the useful values s/he really wanted to put in.A memory allocator typically makes no guarantee about this issue. The block of memory which is allocated and returned to the user must be presumed to contain garbage. It is the responsibility of the user to then initialize this block properly so that its contents become meaningful.
In the present case, the user simply copies the string
"JOE" into it:
You can see that it takes up exactly the space that is needed for it. The rest of memory can be used to store the other names.
Suppose the next name is MARYJANE: 8 characters + 1 NUL. The user asks for 9 bytes and copies the string into them:
You may wonder why this new block is not contiguous with the previous one. The reason is that, in general, it won't be. This, mainly for two reasons:
where the arrows point to the start of the blocks allocated to the user. In the following, we are going to ignore these details.
What to remember
If the user now says he is finished with the name JOE, the corresponding block of memory is returned to the global pool and becomes free:
For example, suppose you free up a location before you're actually finished with it. Then further access to the location will either cause a run-time error (memory violation) or, what is worse (but more common), you will get access to a location that is being used for some completely unrelated purpose.
Trouble also occurs if you forget to free up some space. If you do this, you are losing the advantages of dynamic allocation. And in some circumstances - e.g. if you were writing the program that manages the space on a disk drive - this could be disastrous.
There are no surefire safeguards against these problems, you must be very careful when writing programs to return memory when you are finished with it, but not before.
Suppose that after using dynamic allocation for a while memory becomes fragmented thus:
and that we need to obtain a block this big:
If only the remaining free blocks were contiguous, we'd have enough room, but, in the present configuration, it looks like we are doomed. There are several possible solutions to this problem. The one we will study is based on the insight that a large data structure does not necessarily have to be allocated in one single contiguous chunk of memory. Instead it might be decomposed into smaller components that are somehow linked together in a chain.
Each component in this chain can very well be allocated in a different region of the global pool. Thus, when using linked data structures, fragmentation becomes much less of a problem.