Linked list and busy bit table

Advanced Operating System Notes (File Systems)

Although I’ve covered file systems in previous courses, including graduate introduction of operating systems, I really enjoy learning more about this concept in a little depth.  The file system’s module is packed with great material, the material introducing a high level introduction of file system and then jumps into the deep end unveils what an operating system does behind the scenes.

Main Take Aways

  • The high level purpose of a file system provides three key abstractions: file, filename and directory tree.
  • A developer can interface with the file system in two ways: a position based (i.e. cursor) and a memory based (i.e. block)
  • C function strol converts a string to a long
  • Mmap system calls maps a file on the file system to a contiguous block of memory (the second method a developer can interface with a file systeme)
  • FAT (file allocation table) glues and chains disk blocks together. It is essentially a linked list (persisted as a busy bit vector table) that is great for sequential reads (i.e. traversing the linked list) but awful for random access (i.e. to get to the middle, need to traverse from head)
  • EXT linux file system is based on inodes and improves random access using 12 direct pointers (13th pointer provides first level of indirection, 14th pointer second level of indirection, 15th pointer third level of direction)
  • Learned about the buffer cache (i.e. write-through) and how we a journal can help stabilize the system while maintaining decent performance
Linked list and busy bit table
Linked list and busy bit table

File System Concept

Summary

Universal interface of file system contains three key abstractions: file, filename, and directory tree)

Access Rights

Summary

Learned why we need the execute bit on directories: this permission affects whether you can pass through the directory)

Quiz: Permission Error

Summary:

again, cannot cat underneath the directory because on the directory itself, because we lack the execute bit)

Developer’s Interface

Summary

Two ways to interface with file: cursor (i.e. position based strategy) or as a block of memory)

Quiz: Sabotage

Summary

Learned that there’s a function called strtol that converts a string to long, and then I also opened up the man pages for fcnt)

MMAP

Summary

Can treat a file like a memory buffer and then persist memory map to file by calling munmap).

Quiz: Shuffle

Summary

Skipping over quizzes for writing C code … I do this enough at work)

Allocation Strategies

There's a linked list approach and a busy bit vector (similar trade offs with standard data structures: linked list vs array)
There’s a linked list approach and a busy bit vector (similar trade offs with standard data structures: linked list vs array)

Summary

Block represents continuous amount of space on disk, analogous to a page in virtual memory. We can keep track of said block using either free list or busy bit vector. In next sections, we’ll explore how FAT accomplishes the following: simple & fast, flexible in size, efficient use of space, fast sequential access and fast random access)

File Allocation Table

Summary

FAT is the glue that chains the blocks together. Directory files capture hierarchy and starting blocks for the files)

Quiz: Values in FAT

(Summary: We can identify the starting blocks by eliminating any block that has another block pointing to it. Also I’m curious if defragmenting improves the linked list somehow or the FAT table, moving sectors closing together?)

File Allocation Table continued

Summary

Great for sequential access like copy files to a USB drive. But fallen out of popularity due to poor random access given to hit the middle, we need to traverse the entire linked list)

Inode Structure

Journaling offers a mechanism to make the unified buffer cache more robust
Journaling offers a mechanism to make the unified buffer cache more robust

Summary

Instead of Fat table, we have an inode that contains metadata and 15 pointers., the first 12 are direct, 13 is first layer of indirection, 14 is the second layer (contains 2 levels) and 15 contains three levels.

Quick : Data Blocks

Summary

to get the maximum size without second level of indirection, we take 4 times 12 then multiply 1024 * 4 (i.e. 1024 contains number of entries))

Inode Structure

Summary

When compared to FAT, Inode offers much better performance for random access memory)

Buffer Cache

Summary

We buffer disk data in something called a unified buffer cache. I learned that if you want to really persist to disk, call fsync: otherwise, data sitting in unified buffer cache may get lost. Also, this is the reason why OS warns you not to remove storage device without ejecting them first. I had no idea that’s the reason why. Again, how neat)

Journaling

Journaling offers a mechanism to make the unified buffer cache more robust
Journaling offers a mechanism to make the unified buffer cache more robust

Summary

Very neat idea to handle the trade off of using the unified buffer cache. By adding a journal, we have robustness but trade off is that for every write there is another write. So two writes. But this journaling mechanism offers a nice trade off of only writing dirty pages to disk when its more convenient)

Direct Memory Access

Summary

Hardware optimization: Direct Memory Access. This way, CPU does not need to copy data over the bus. Disk controller can access memory directly)

Quiz

Summary

Compare Buffer Cache, Journaling, and DMA)