File systems

Modern disk drives:  can be read and written, and you have random access, meaning any part of the disk is about as easy to get to as any other.

We usually organize disk into "blocks".  A block can be thought of as a piece of the disk that can be accessed easily and quickly.  We don't usually read and write a byte at a time from a disk, we read a whole block into memory and then extract the byte we need from that.   A block might be 4096 bytes (say).

Often, the very first block on the disk will be used a "boot control block."  When you boot the computer, it will go to that first block and see how to load up the operating system.  (There might be a pointer in the first block to the location of the OS software on the disk.)

Volume control block:  may say how many blocks are in the volume (the disk), the size of the blocks, where the free blocks are and how many and where the file control blocks and how many.

File control block:  contains information about the file other than the actual contents of the file.  Permissions, various date/times.  Creation date/time, access date/time, modification date/time, perhaps other information.  What it exactly stores depends on the file system itself.  Also a pointer to the contents of the file.

Filenames are stored as part of the directory structure.  Each directory entry contains a list of the files within that directory AND a pointer to that file's control block.  Linked List is one way to do it; it is a very easy thing to implement.  Downside:  You may to traverse the whole list to find the file you are looking for.  If it's a long list, that can take a long time.

Remember:  if you want to add a new file to the directory, you first have to make sure that that filename is not already in use, which means every time you add a new file, you have to scan the whole linked list.

Hash Table:  some file systems do use a hash table.  Hash table upside:  locating a specific file is pretty easy and fast.  You hash the name you're looking for and check that entry in the hash table.  Downside of a hash table:  doing a complete scan of everything in there can be tricky or slow depending on how you implement the hash table.

Database:  red-black tree or a B-tree.  Can easily answer the question is this file there?  If you write a B-tree correctly, you can merge it with a linked list, and so it will the question What's in there? quickly, too.  Locate the file tree*.txt .  Also, the red-black tree/linked list combination will keep the file entries in alphabetical order.  And yet, I don't know any file system that does it this way.

But however you keep track of your directories.  You have some way to access the files.  Now some file systems (like EXT4) treat the directories as no different from other files.  They have a flag in the file control block to indicate that they are directories.  Other file systems (like NTFS) treat directories as distinctly different from other files, so that the system calls involving directories are completely different from the system calls involving other files.

Storing file content:  one way is to use contiguous file storage.  All the blocks containing the file are next to each other.  If you start reading the first byte of a file, you can just keep moving forward on the disk until you reach the last byte of the file without jumping.

Downside of contiguous file storage:  you need to know the size of the file at the time you create it, so that you can find a section of the disk large enough to contain it.  If you do know or can guess the size of the file before it's created, then that aspect of it is OK; you still have to find a portion of the disk large enough to contain the file.

This system does not handle changes in the file size.  Files growing.  Files shrinking.  But how often does that happen?  In my day to day life, the only files I have that regularly change size are my databases.

If you don't store files contiguously, you can store them in fragments.  One way to do this after each file block, store a pointer to the location on the disk of the following block.  Block1-->Block2-->Block3-->...-->EOF.

Big downside:  You've just lost random access.  Let's say I want to jump around in the file.  I'm in Block1 and I want to jump to a location in Block4.  Well, I have no idea where Block4 is.  I follow the pointer to Block2.  I follow that pointer to Block3.  I follow that pointer to Block4, and then I jump to where I need in Block4.

So, another way to do this is indexing.  I have an index to all the blocks.  If I need to jump to Block4, I don't have to go to the intervening blocks, I just check the index for Block 4.  You can think of an index as an array of pointers to all of the blocks.  An index is also easily "cached".

Cache:  Caching is when you store part of the disk in memory so that you don't have to read that part of the disk over and over.