Defrag Part 2
As promised, the second part of the defrag simulator.
Here I added some __str__ overrides to help with debugging but it mostly went very smoothly once I decided on the algorithm and how
it would be run. In the previous post I worked on randomly scattering chunks of files all over the disk and in this part we need
to start bringing them back together.
I kept the FileChunk and File classes but they are not strictly necessary since I went with the approach to just each chunk in turn and try to move it into it's corresponding sector. If there is already a chunk in that spot, I move it to a free space at the end of the disk and then wait for that particular chunk to be moved when we come to it later.
Defrag
Since there is no real timer callbacks available in processing, I elected to run the defrag function on every time through the draw function, picking the next chunk to handle and doing something with it. Next time through the defrag function we just pick up the next chunk and work with that.
sector_width = 30
sector_height = 30
class File:
def __init__(self, id, starting_index):
self.id = id
self.chunks = []
size = int(random(5, 15))
for i in range(size):
chunk = FileChunk(id, starting_index + i)
self.chunks.append(chunk)
def size(self):
return len(self.chunks)
def parts(self):
return self.chunks
def draw(self):
print(self.id) #, self.length())
class FileChunk:
def __init__(self, file_id, index):
self.file_id = file_id
self.index = index
def __str__(self):
return ("file %i chunk %i" %(self.file_id, self.index))
def draw(self):
print(self.file_id, self.index)
SECTOR_FREE = 'free'
SECTOR_ALLOCATED = 'allocated'
SECTOR_TEMPORARY = 'temp'
class DiskSector:
def __init__(self, id):
self.id = id
self.chunk = None
self.status = SECTOR_FREE
def __str__(self):
if self.chunk is not None:
return ("sector %i chunk %i" %(self.id, self.chunk.index))
return ("sector %i" %(self.id))
def allocated(self):
return self.chunk is not None
def unallocated(self):
return self.chunk is None
def allocate(self, part):
print('allocating', str(part), 'to', str(self))
self.chunk = part
print('allocated', str(part), 'to', str(self))
def deallocate(self):
print('deallocating', str(self))
chunk = self.chunk
self.chunk = None
print('deallocated', str(chunk), 'from', str(self))
def current_status(self, text):
self.status = text
def draw(self, x, y):
stroke(255)
if self.chunk is not None:
# assume out of step
fill(255, 0, 0)
# in correct place?
if self.chunk.index == self.id or self.status == SECTOR_ALLOCATED:
fill(0, 255, 0)
else:
if self.status == SECTOR_FREE:
fill(240, 240, 240)
if self.status == SECTOR_TEMPORARY:
fill(129, 151, 237)
square(x, y, sector_width)
textAlign(CENTER, CENTER)
id = ''# str(self.id)
if self.chunk is not None:
id = str(self.chunk.index)
fill(50)
text(id, x + (sector_width / 2), y + (sector_height /2 ))
class FileAllocationTable:
def __init__(self, length):
self.sectors = []
for i in range(length):
self.sectors.append(DiskSector(i))
def unallocated_sectors(self):
return [ i for i, x in enumerate(self.sectors) if x.unallocated()]
def draw(self):
border = 5
x = border
y = border
# layout across and down the screen
for i in range(len(self.sectors)):
sector = self.sectors[i]
sector.draw(x, y)
x += sector_width + 1
# move down the screen?
if x >= (width - sector_width):
x = border
y += sector_height + 1
def scatter(self, files):
for file in files:
for part in file.parts():
index = self.pick_random_index_from(self.unallocated_sectors())
sector = self.sectors[index]
sector.allocate(part)
def pick_random_index_from(self, indices):
randomIndex = int(random(len(indices)))
return indices[randomIndex]
def highest_unallocated_sector_index(self):
return self.unallocated_sectors()[-1]
def move_chunk(self, from_sector, from_status, to_sector, to_status):
print('moving chunk from', from_sector, 'to', to_sector)
fromSector = self.sectors[from_sector]
print('from', str(fromSector))
toSector = self.sectors[to_sector]
print('to', str(toSector))
toSector.allocate(fromSector.chunk)
toSector.current_status(to_status)
fromSector.deallocate()
fromSector.current_status(from_status)
def defrag(self, sector_index, chunk_index):
try:
print('defrag', str(sector_index), str(chunk_index))
# find lowest
sector = self.sectors[sector_index]
print('considering', str(sector))
if sector.allocated():
print('allocated sector', str(sector))
if sector.chunk.index == chunk_index:
# good don't need to move it
print(str(sector), 'in correct place')
else:
print('going to move', sector.chunk.index)
# move it to the end
endIndex = self.highest_unallocated_sector_index()
print('temp moving to end index', endIndex)
self.move_chunk(sector_index, SECTOR_FREE, endIndex, SECTOR_TEMPORARY)
# find the sector with the matching file index
# move it to this spot and deallocate it from
# current spot
print('looking for item', str(chunk_index), 'to put into', str(sector_index))
for i in range(len(self.sectors)):
nextSector = self.sectors[i]
if nextSector.allocated() and nextSector.chunk.index == chunk_index:
self.move_chunk(i, SECTOR_FREE, sector_index, SECTOR_ALLOCATED)
else:
# need to find one to move here.
print('looking for item', str(chunk_index), 'to put into', str(sector_index))
for i in range(len(self.sectors)):
nextSector = self.sectors[i]
if nextSector.allocated() and nextSector.chunk.index == chunk_index:
self.move_chunk(i, SECTOR_FREE, sector_index, SECTOR_ALLOCATED)
except exception as e:
print(e)
I also added some colouring to the temporarily displaced files to make it easier to see progress in terms of chunks that are still to be processed, those that are in place, and those that have been moved to make way for others.
Glue
I made the frame rate increase slightly to make the animation work a bit better. I also added quite a lot of "I am here" debug statements since it didn't take much to completely break the sketch and leave me with a blank canvas.
def setup():
global fat, files
size(1000, 800)
fat = FileAllocationTable(800)
files = []
number_of_files = int(random(10, 75))
index = 0
for i in range(number_of_files):
file = File(i, index)
files.append(file)
index += file.size()
fat.scatter(files)
frameRate(5)
sector_index = 0
chunk_index = 0
def draw():
global sector_index, chunk_index
fat.draw()
if sector_index < 800:
print('defragging', sector_index)
fat.defrag(sector_index, chunk_index)
sector_index += 1
chunk_index += 1
I keep track of the current/next chunk to process using the index variables in the draw function.