School of Computing. Dublin City University.
My big idea: Ancient Brain
Problems like with contiguous memory allocation.
What happens if file grows? Has to be rewritten into larger slot. Takes ages.
tar -cf file.tar $homeGrows from 0 k to 10 G in a minute or two.
Like with paging in memory, disk is divided into blocks.
Create new file. Will get one block allocated for it: $ echo 1 > newfile See how much space allocated for it (one block). $ du -h newfile 1.0K
File is held in a collection of blocks scattered over the disk.
If file needs more blocks, it can take them from anywhere on disk that blocks are free.
# compare actual file size with blocks used for i in * do ls -ld $i du -h $i done
-rwxr-xr-x 1 me mygroup 857 Jun 27 2000 synch 1.0K synch -rwxr--r-- 1 me mygroup 1202 Oct 25 2013 profile 2.0K profile -rwxr-xr-x 1 me mygroup 1636 Oct 28 2009 yo.java 2.0K yo.java -rwxr--r-- 1 me mygroup 2089 Oct 8 00:03 flashsince 3.0K flashsince -rwxr-xr-x 1 me mygroup 9308 Oct 19 2010 yo.safe 10K yo.safe
Unlike in memory, where contiguous allocation is dead, in files it has made a bit of a comeback.
The reason is that there is a lot of disk space and it is cheap, but the speed of read/writing disk has not increased so much - indeed it has got far worse relative to CPU speed.
To write a contiguous file to disk you don't have to jump the disk head around the disk. You just keep writing after the last location you wrote - the head is in the correct position.
So modern systems try to use contiguous allocation for small files, only use non-contiguous for large files. To achieve this, they may allocate more space than possibly needed. Some wasted disk space is worth it if it makes disk I/O a lot faster.