Defragmentation Algorithm

File Allocation Table (FAT System)

A file allocation table (FAT) is a table that an operating system maintains on a hard disk that provides a map of the clusters (the basic units of logical storage on a hard disk) that a file has been stored in. When you write a new file to a hard disk, the file is stored in one or more clusters that are not necessarily next to each other; they may be rather widely scattered over the disk. A typical cluster size is 2,048 bytes, 4,096 bytes, or 8,192 bytes.

Defragmentation?

When a file is accessed, the Operating System uses the FAT table to identify all the clusters that need to be accessed to retrieve the content of the file. The more scattered the clusters are the longer it will take for the Operating System and Hard drive to retrieve the content of the file. This is why, if you hard drive is based on a FAT systems, it is recommended to use a defragmentation utility to try to reorganise how all the files are stored by trying to move the content of clusters of a single file into consecutive clusters. Defragmenting your hard drive once every six months should hence have a positive impact on the performance of your computer.

On this graphic, each square represents a cluster of the hard drive and each colour represents a file.

Did you know?

With the introduction of more powerful computers and operating systems, as well as the development of more complex file systems for them, FAT is no longer the default file system for usage on Microsoft Windows computers.

FAT file systems are still commonly found on floppy disks, flash and other solid-state memory cards and modules (including USB flash drives), as well as many portable and embedded devices such as digital cameras.

Defragmentation Algorithm

The File Allocation Table is a linked list where each entry contains the cluster number, the file name and a pointer to identify the next cluster used by the file.

Cluster #	File Name	Pointer
0	File A	1
1	File A	2
2	File A	5
3	File B	4
4	File B	x
5	File A	6
6	File A	x
…	…	…

Let’s check this Python trinket to see how the File Allocation Table was implemented using a Python list of lists.

Challenge 1: Hard Drive Stats

Assuming that the standard cluster size is 4KB, complete the displayStats() procedure to:

• Calculate and display the total size of the hard drive (in KB).
• Calculate and display the total used space of the hard drive (in KB).
• Calculate and display the total free space of the hard drive (in KB).
• Calculate and display the total used space of the hard drive as a percentage of the total disk space.

Challenge 2: Defragmentation Algorithm

Your challenge consists of completing this code by writing the code for defragmentation() procedure that will group all the clusters of a file into consecutive clusters.