How Bad is External Fragmentation under a First-Fit Algorithm?


Sometimes I read about operating systems, because I want to know how my computer works. I’ve run Linux distributions as my primary OS for about 10 years, so having a familiarity with these concepts allows me to greatly customize and optimize my system. One topic that the general public is probably interested in is “What is fragmentation, and why am I supposed to defrag my computer sometimes?”

What I’m going to describe is not how memory management is actually done on any modern operating system, but it will give a feel for why fragmentation happens (and what this even is). I realized this really simple algorithm would be easy to program a simulation for, so we can see just how bad it can get.

The first-fit algorithm is exactly what it sounds like. You visualize memory as a bar that fills up. Each program has a size, and you look for the first hole big enough for it to fit. Here’s a picture I made to illustrate:

What’s going on? You download the blue program, and it goes into the first area no problem. You download the red, and the first available hole is right next to the blue. Same for the green. Then you realize you don’t want the red anymore, so you delete it. This leaves a hole. When you download the purple program your memory management notices the hole and tries to fit it there. Woops. The hole was too small, so it moves on to find the first hole that it fits in (hence the name “first-fit algorithm”). Eventually you may delete the green as well, and something might go in the big hole leftover from the red and green, but it probably won’t fill the whole thing.

Once these holes start appearing, they are hard to get rid of. This is external fragmentation. I wrote a simulation of this to see just how bad it can get. Although the program does nothing more than the simple thing I just showed, it is kind of long and confusing, so let’s take it one step at a time.

from matplotlib import pyplot as pp
import numpy as np
import random

def randomSize():
	return random.randint(1,10)

def randomTime():
	return random.randint(1,20)

class Program(object):
	def __init__(self):
		self.size = randomSize()
		self.position = -1
		self.time = randomTime()
		
	def getSize(self):
		return self.size
	def getPosition(self):
		return self.position
	def getTime(self):
		return self.time

	def decrement(self):
		self.time -= 1

I made two classes. The first one allowed me to pretend like I was downloading some program. Each program came with a random size from 1 to 10, the position where it was placed into memory, and the amount of time until I deleted it (a random number from 1 to 20). I’m still really confused about whether or not it is proper python style to use getter methods rather than just directly accessing attributes…

class Memory(object):
	def __init__(self, size):
		self.size = size
		self.contents = []

	def getContents(self):
		return self.contents
	def numPrograms(self):
		return len(self.contents)
	def getSize(self):
		return self.size

	def checkHole(self, i, p):
		return p.getSize() <= self.contents[i+1].getPosition() - (self.contents[i].getPosition() + self.contents[i].getSize())

	def addProgram(self, p):
		n = self.numPrograms()
		tmp = 0
		if n == 0:
			self.contents.append(p)
			p.position = 0
		elif n == 1:
			if self.contents[0].getPosition() >= p.getSize():
				p.position = 0
				self.contents.append(p)
			else:
				self.contents.append(p)
				p.position = self.contents[0].getSize()
		else:
			if self.contents[0].getPosition() >= p.getSize():
				p.position = 0
				self.contents.append(p)
				tmp = 1
			if tmp == 0:
				for i in range(n-2):
					if self.checkHole(i,p):
						self.contents.append(p)
						p.position = self.contents[i].getPosition() + self.contents[i].getSize()
						tmp = 1
						break
			if tmp == 0:
				if p.getSize() <= self.getSize() - (self.contents[n-1].getPosition() + self.contents[n-1].getSize()):
					self.contents.append(p)
					p.position = self.contents[n-1].getPosition() + self.contents[n-1].getSize()

	def sort(self):
		self.contents = sorted(self.getContents(), key=lambda p: p.getPosition())

	def removeProgram(self):
		for p in self.getContents():
			if p.getTime() == 0:
				self.contents.remove(p)

I’m sorry that this is probably the worst python code you’ve ever seen. This class is just the stick of memory. It has a total size that we will take to be 100 in our simulations and it has a list of the programs that are currently in memory (the programs keep track of their positions). I made a helper function that checks whether or not a given program fits into the hole between the i-th and (i+1)-th programs.

Originally I thought this helper function would make the code much simpler, but it is almost entirely useless which is why this looks so bad. Then I made the function that adds a program into the memory. This just looks for the first available hole to stick it into. Unfortunately, I ended up not seeing a slick uniform way to do it and cobbled together something by cases. I check the hole before the first program separately and the hole after the last program separately.

I made a sort method, because when I appended a new program to the list it was just stuck at the end despite having a position that could be in the middle. This just orders them by position. Lastly, I have a program that gets removed if enough time has passed.

def simulate(memSize, numTimeSteps):
	m = Memory(memSize)
	tmp = 0
	for i in xrange(numTimeSteps):
		m.addProgram(Program())
		for p in m.getContents():
			p.decrement()
		m.removeProgram()
		m.sort()
	for p in m.getContents():
		tmp += p.getSize()
	print float(tmp)/memSize
	memArray = []
	for i in xrange(len(m.getContents())-1):
		memArray.extend([1 for j in range(m.getContents()[i].getSize())])
		memArray.extend([0 for j in range(m.getContents()[i+1].getPosition()-(m.contents[i].getPosition() + m.contents[i].getSize()))])
	memArray.extend([1 for j in range(m.getContents()[m.numPrograms()-1].getSize())])
	memArray.extend([0 for j in range(100- len(memArray))])
	x = [i for i in range(100)]
	ymin = [0 for i in range(100)]
	a = np.array(memArray)
	pp.vlines(x, ymin, a)
	pp.ylim(0,1)
	pp.show()
	
simulate(100, 100)

Lastly I just simulate for 100 time steps. At each time step I try to stick in one randomly generated program. I then make all the time-to-deletion parameters decrease. I check whether any are 0 and remove those. I sort the list, and then repeat.

Here are some of the final results:

frag1

This one had 66% memory use, so external fragmentation led to about 34% waste.

frag2

This one was slightly better at 69% use.

frag3

This one was quite a bit worse at 43% use and hence 57% waste. The full code can be found here. It might be fun to play around with different sizes of memory and lengths of time to delete stuff. Fragmentation will obviously not be a huge problem if the amount of space you try to use is sufficiently less than your total memory.

On the other hand, as these simulations show, the answer to the title question is that it can be pretty bad. These simulations are actually accurate (if my textbook is correct), because you can mathematically prove that the expected space you waste with this algorithm is roughly 33% (I ran a lot more simulations than I showed you and this was what I usually saw).

There is no need to fear, though. Old operating systems did use some variant on this, but all modern operating systems use something called “paging” which completely avoids external fragmentation (there is something called internal fragmentation that I didn’t talk about). I hope you enjoyed this change of pace. I had fun doing it. It may look like it was a lot of work, but the program was done in one sitting. If anyone knows how to make an “animation” where you can watch the whole process unfold that might be cool. I googled a bit, and couldn’t find an obvious way to do it.

Update 5/17/14: I pushed a cleaned up version of this code to github. It is amazing what one night of sleeping on something will do. I got rid of most of the indices using itertools, and I realized that the proper helper function was to just make a method that returns the right endpoint of the position of a program in memory. Then finding a hole size was just subtracting and could be reused everywhere.

Just for fun, I decided I would “prove” to you that this algorithm is only bad when you use a sufficiently large amount of memory (i.e. probably never on a modern computer!). Here’s such a simulation result where your programs are too small for the wasted space to ever matter:

frag4

Advertisements

One thought on “How Bad is External Fragmentation under a First-Fit Algorithm?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s