CST 334 - Week 8

Virtual File Systems

This week I studied the very simple file system (vsfs). The vsfs's on-disk data structure splits up disk space into equal-sized blocks, much like how paging splits up the memory into equal-sized pages. Each block consists of eight 512-byte sectors. The first block is the superblock, which contains information about the file system. The second and third blocks store the inode bitmap and data bitmap, respectively, which are used for free space management of the remaining blocks (which store either inodes or, most commonly, user data). 

Inodes store important information about files on a disk. An inode contains a few direct pointers to blocks of user data, but it also may use an indirect pointer to a block full of direct pointers. Or, in the case of multi-level indexing, it points to a block full of indirect pointers (which can either point to more indirect pointer blocks, or direct ones). When the operating system uses an access method (e.g. open, read, write), the root inode and its data are accessed and read (note 2 operations), and then the inodes for the remainder of the pathname are traversed recursively until the correct inode is found. Recently accessed blocks are cached for faster access. 

The in-memory data structure of the vfsf is a directory tree, starting at the root node. Everything in the virtual file system is thus only a file in essence. Directories are a special type of file which contain links from user created filenames to the underlying low-level filenames in the system. Hard links directly link virtual files to a low-level file, which may have more than one hard link assigned to it. Soft links, in contrast, are similar in concept to shortcuts. These symbolic links indirectly point a virtual file to another virtual file, which would then be hard linked to a low-level file. 

Wrap-Up

Thus concludes my journey through the world of operating systems. Although I enjoyed my time quite a lot, and the knowledge I've gained is invaluable, I am excited to leave the low-level realm (at least for now). Even if I choose not to return, I believe that my deeper understanding of how the system actually works will help me be a better software developer. 

CST 334 - Week 7

RAID?!

Arguably the most fascinating thing I learned this week was about RAID, the redundant array of inexpensive/independent disks. RAID uses more than one hard disk drive to store data, but uses different levels to determine the implementation. RAID level 0, for example, simply creates stripes of data across the disks. This means that a single file can be broke up and spread across all the disks. This creates the potential for faster file access because different parts of the file can be accessed at the same time (in parallel). Unfortunately, RAID 0 does not backup any data, and a loss of one disk can result in major data corruption since files are spread across disks.

The next level is RAID 1, which implements mirroring. This implementation simply writes the same data to two different disks. This way if a disk fails, there is a mirrored disk that can be used to back it up. Similar to RAID 1 is RAID 10 (or 1-0) which combines the striping aspect of RAID 0 with the mirroring of RAID 1. The main downside of RAID 1 (and by extension, 10) is that only half of available disk capacity can be used to store data (because the other half is backup). 

RAID 4 attempts to solve the capacity problem by using a concept known as parity. Parity is a bit complicated, but essentially involves running a XOR function across data blocks and storing the result in a corresponding parity block. If any disk fails, it can be reconstructed by running the XOR function over the data blocks of the surviving disks (including the parity disk). If the failed disk is the parity disk, a new parity disk can be easily created in the same manner it was created originally.

RAID 5 is essentially the same as RAID 4, but the parity blocks are spread across all disks rather than being stored in a single parity disk (this is done for efficiency reasons). Although RAID 4 and 5 allow for N-1 max disk capacity usage, where N is the number of hard disk drives (as opposed to N/2 as seen with RAID 1 and 10), they only allow for failure of a single disk. RAID 6 mirrors the parity information and can therefore support failure of more than one disk.

CST 334 - Week 6

Semaphores

This week we learned about semaphores, a data type consisting of a lock/condition variable combo and an integer. Semaphores can be used like mutex locks if they are initialized to 1. This is known as a binary semaphore. When sem_wait() is called, the value of the semaphore is decreased by 1. If the result is negative, the calling thread is blocked and placed in a waiting list. When sem_post() is called, the semaphore's value is increased by 1 and a thread in the waiting list is allowed to continue. While this may replace the standard mutex, semaphores can be used in even more intricate ways to enable synchronization of concurrent threads (see the producer-consumer problem or reader-writer locks). 

Problems with Concurrency

Two of the most common concurrency bugs come from atomicity violations and order violations. Atomicity violations can be avoided by correctly locking critical code sections, and order violations can be avoided by either using locks (with condition variables) or semaphores to guarantee threads run in a particular order. Another serious, but less common, concurrency issue results from deadlock. Deadlock occurs when a thread holds a resource exclusively while waiting to obtain a resource from another thread, which is in-turn waiting (either directly or in some circular fashion) for the first thread's resource. 

There are many ways to prevent deadlock: through the total ordering or partial ordering of lock acquisition; by acquiring all locks upfront (using a mutex to ensure atomicity); by calling the pthread's trylock() function (which may still result in livelock, where threads get stuck in infinite loops trying to obtain each other's locks); or by using a special hardware compare-and-swap instruction (such as CMPXCHG on x86).