Memory Fragmentation
In OS/161 with the
DUMBVM, I've noticed that it runs out of memory after we've run a few programs, and then we can't run any more programs. Why is that?
Let's look at that… We'll explore how the system might locate processes in the machine's physical memory.
Actually, we'll come up with some options that are a good deal smarter than
DUMBVM. We'll return to discussing whatDUMBVMreally does at the end.
Memory Allocation Demo
In the demo below, we begin with three processes in the system. You can simulate the arrival of a new process and the departure of an existing one by clicking the “Add & Finish Process” button. Begin by just clicking that button repeatedly until it stops working.
There is XXXXX of free memory in the system.
The next process is...
The system is ready!
Fragmentation
Assuming that you left the seed at the default of 12345, when the “Add & Finish Process” button stops working…
Poor Process 10, it wants MORE space than is available in any one block, but there's plenty of space overall.
-
I tried the seed
123456and it ran out of memory even faster!
When we have chunks of free space scattered around, we call it fragmentation. There are actually two types of fragmentation:
- External fragmentation — free space is scattered around and can't be used to satisfy a request for a large block of memory.
- Internal fragmentation — a block of memory is allocated to a process, but the process doesn't use all of it. The unused space is wasted.
We're mostly concerned with external fragmentation here, so when we say fragmentation, we'll mean external fragmentation.
This feels like a game! I wanna be able to play around with it more!
-
Well, let me show you a few tricks.
Bonus: More Fun with the Simulator
It's not required, but if you want to play around with the simulator more, here are some additional features. Clicking on
- A process — it will finish and free up its memory.
- The operating system — it will start the next process (if there's space).
- A free space — it will change the next upcoming process to be of a random size that is at most as big as the free space you clicked on.
-
Oh, yeah! I'm having so much fun with this!
Meh. You're just clicking around randomly. I think you're easily amused.
I notice that we always put the new process at the beginning of the free space. Maybe there's a better way to do this?
-
We'll explore that next!
Broader Context
Hay! Before you do that, is this like what happens when we allocate heap memory for a program? Like in C++ when you call
newanddelete, ormallocandfreein C?-
Yes, it's essentially the exact same problem.
Well, there is one difference. We might call
mallocto allocate 4 bytes or 40 megabytes, which is a difference of seven orders of magnitude. Although your programs might vary in size, they don't vary that much.-
True. And people also really care about the performance of
mallocandfreebecause they happen so often, so there's actually a lot of research on how to do it well. Even today, there are plenty of open questions about how to do it best. 
And a nice implementation of
mallocandfreemight tell you if you've screwed up and tried to free memory that wasn't allocated.-
That's a bit more than we're thinking about here.
-
Ask Prof. Melissa about it and she'll talk your ear off!
Strategies for Choosing a Free Block
Often there are multiple places we could put a new process in memory. We'll look at four strategies for choosing where to put a new process:
- First Fit: Put the new process in the first block that's big enough. (This is what we've been doing so far.)
- Best Fit: Put the new process in the smallest block that's big enough.
- Worst Fit: Put the new process in the largest block that's big enough.
- Next Fit: Put the new process in the first block that's big enough, starting from where we left off last time.
Click
then Set the seed back to 12345, and scroll back to the demo. Try out each of these strategies. Which one seems to work best for this seed? What about for other seeds?
-
I think I can see why we might choose best fit, but I'm at a loss to explain why anyone would choose worst fit.
-
Meh. Worse is better. That's my new mantra.
-
Let's explain why each of these strategies might be chosen.
First Fit
First fit is the simplest strategy. It's easy to implement and it's fast because we don't have to search through all the free blocks to find a best (or worst) one. Also, although it's more relevant to heap allocation than our process-based memory allocation example, first-fit is likely to put recent allocations next to each other, which improves locality, and that can be good for cache performance.
But as we've seen, first fit can lead to more fragmentation than best fit.
Best Fit
Best fit is the most efficient strategy in terms of memory usage. It tries to minimize the amount of wasted space. However, it can be slower than first fit because we have to have a way to find the smallest block that's big enough.
Worst Fit
In some cases, best fit can actually cause significant fragmentation, because we can end up with tiny slivers of free space that are too small to be useful. Worst fit tries to avoid this issue by putting the new process in the largest block, creating the biggest possible leftover block. The downside is that if you need a big block later on, you might not have one available.
Random Fit
-
Hay! That wasn't one of the options!
For every strategy we've seen so far, there's a pathological series of allocations and deallocations that can lead to a lot of fragmentation and cause a lot of wasted space.
Random fit is a strategy where we just pick a free block at random. By acting randomly, we can avoid the pathological cases that can cause problems for the other strategies. It will never be good, but, statistically speaking, it will never be terrible either.
Next Fit
Next fit is a variation of first fit. It's like first fit, but we remember where we left off last time, and start searching from there. This approach can help us avoid the problem of always putting new processes at the beginning of memory, which can increase the chance of fragmentation. Like first fit, it's fast, easy to implement, and can be good for locality. We could also argue that it is likely to approximate random fit to some extent.
-
So which one is best?
-
There's never a simple answer to that question. It depends on the situation and what you're optimizing for.
In Practice
First fit and next fit are common choices because they're simple and fast. If memory is tight, best fit might be a good choice.
An Experiment
I ran a quick experiment with the simulator to see how the different strategies compared, doing 10 million runs with each strategy. Here are the results, where we measure how many clicks of the button it took to run out of memory:
| Fit | Average | StdDev | Min | Max |
|---|---|---|---|---|
| First | 5.8209 | 5.2580 | 1 | 84 |
| Best | 6.3922 | 5.9362 | 1 | 101 |
| Worst | 5.7638 | 5.1216 | 1 | 80 |
| Next | 6.1621 | 5.5810 | 1 | 83 |
We can see that in this example, best fit is certainly better, but not by a huge amount. Next fit is definitely a big improvement for a tiny bit of extra complexity. Worst fit is actually the worst, but not by much.
Of course, this is just one tiny experiment where we only ever have at most four processes. But it shows you can always choose to run a quick experiments to explore the questions you have (as well as checking the literature, of course).
-
Meh. How about we just make all the processes the same size? Boom! Problem solved!
-
Although you might not have meant that seriously, it's actually a good point. We won't have external fragmentation if all the processes are the same size, because there will be no leftover space. But, on the other hand, we might have internal fragmentation if the processes don't use all the space they're given.
-
Why not compact the memory? Then we can coalesce all the free space into one big block.
-
Well, in the case of heap-memory allocation, the C and C++ languages just aren't allowed to move your data around like that—it has to stay where it was put. But some other languages, such as Java, can do that because programs are never told exactly where in memory their data really lives, so a Java garbage collector is allowed to move things around to make memory more efficient.
-
And what about processes? Can we move them around?
-
To think about that, we'll have to dive deeper into how processes live in memory. Let's do that next!
-
Hay! Before we move on to a new page, you promised you'd tell us how OS/161 really allocates memory.
-
Okay.
PostScript: OS/161's DUMBVM
FWIW, DUMBVM is really dumb. It uses a strategy called bump allocation. There isn't a list of free areas of memory, just a pointer that says “this is the beginning of free memory”. When a process asks for memory, DUMBVM “bumps” the free-memory pointer up by the size of the request and gives the process the memory that was there. The pointer only ever bumps forward, never back. Quickly enough, all memory is exhausted and no more processes can be run.
Bump allocation is the fastest and simplest memory allocation strategy:
- Allocate: Just bump the pointer.
- Deallocate: Do nothing (waste the memory).
-
OMG! That's so dumb!
-
Actually, when it comes to heap allocation, if you have a program that allocates memory and never needs to free it (or frees everything it allocated all at once), bump allocation is perfectly fine. It's fast and simple, and it doesn't have the overhead of keeping track of free memory. It's just not very flexible.
(When logged in, completion status appears here.)