CSCI 3753 Final

Disk Storage

Files and file systems are stored in non-volatile permanent/secondary storage, like magnetic disks, solid-state or flash drives.

What does a disk consist of?

A disk consists of an array of magnetic platters, each one subdivided into concentric tracks. Each track is then subdivided into sectors (512B - 4KB). The collection of the same track (radius) across different platters forms a logical cylinder.

What does an I/O operation consist of?

Any I/O operation consists of mechanically moving the arm to position the read/write head to the correct track, and mechanically rotating the disk so that the correct sector rotates under the read/write head.
The delay of mechanically moving the arm to position the R/W head to the correct track is called the seek time, while the rotational latency describes the time required to mechanically rotate the disk, positioning a sector under the R/W head.

Disk Access Latency

The total delay to read or write to this disk is calculated by the sum of the seek time, rotational latency and transfer time. The transfer time of the data will be significantly less than the seek time or rotational latency, therefore any technique that can reduce seek time or rotational latency is a big win in terms of improving disk access times. For this purpose, we introduce disk scheduling.

What is Disk Scheduling?

Disk scheduling is done by the OS to schedule I/O requests arriving for the disk. It's also known as I/O scheduling, and it's really important because:

• Multiple I/O requests may arrive by different processes and only one I/O request can be served at a time by the disk controller. Thus other I/O requests need to wait in the waiting queue and need to be scheduled.

• Two or more requests may be far from each other so can result in greater disk arm movement.

• Hard drives are one of the slowest parts of the computer system and thus need to be accessed in an efficient manner.

List some Disk Scheduling Algorithms.

There are many disk scheduling algorithms, some popular examples being:

• First Come First Serve (FCFS)

• Shortest Seek Time First (SSTF)

• SCAN

• CSCAN

• LOOK

• CLOOK

First Come First Serve Scheduling

FCFS is the simplest disk scheduling algorithm there is. The concept behind it is very straightforward - service the requests in the order they arrive in the disk. Of course, there are advantages and disadvantages to using FCFS.

Advantages:

• Every request gets a fair chance, meaning no starvation

• No indefinite postponement Disadvantages:

• It doesn't try to optimize seek time at all

• May not provide best possible service

Shortest Seek Time First Scheduling

SSTF's idea is to service the requests with the shortest seek time first. So, the seek time of every request is calculated in advance in the queue, then these requests are scheduled according to these calculations. As a result, the request nearest the disk arm goes first. This is a significant improvement over FCFS as it decreases average response time and increases throughput.

Advantages:

• Average Response Time decreases

• Throughput increases Disadvantages:

• Potential for Starvation

• Overhead to Calculate Seek Time

• High Variance of Response Time (it favors the requests closest to the disk arm

SCAN Scheduling

SCAN is also known as the "elevator algorithm". Similar to elevators, it goes in one direction, servicing every request in its path, then reverses its direction only when it hits the end of the disk.

Advantages:

• High throughput

• Low variance of response time

• Average response time Disadvantages:

• Long wait time for requests in locations just visited by the disk arm

CSCAN Scheduling

As we've seen, SCAN scans the path again after it's already been scanned when it reverses direction. This might be a problem since it may be possible that too many requests are waiting at the other end or there may be zero or few requests pending at the scanned area. So, in CSCAN, instead of reversing directions, we go to the other end of the disk and start servicing from there. This algorithm is super similar to SCAN, but the disk arm moves in a circular fashion, hence the name CSCAN (Circular SCAN).

Advantages:
- Provides More Uniform Wait Time than SCAN

LOOK Scheduling

This algorithm is similar to the SCAN disk scheduling algorithm except for the difference that the disk arm in spite of going to the end of the disk goes only to the last request to be serviced in front of the head and then reverses its direction from there only. Thus it prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.

Quizlet doesn't let me post a diagram for this algorithm for some reason, so:
https://media.geeksforgeeks.org/wp-content/uploads/20190830184834/fcfs-1.png

CLOOK Scheduling

We introduce CLOOK Scheduling for the same reason we introduced CSCAN Scheduling. Basically, CLOOK is to LOOK what CSCAN is to SCAN. In CLOOK, the disk arm in spite of going to the end goes only to the last request to be serviced in front of the head and then from there goes to the other end's last request. Thus, it also prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.

Advantages:

• Maximizes locality and resource utilization Disadvantages:

• Can seem a little unfair to other requests and if new requests keep coming in, it can cause starvation to the old and existing ones.

What's Flash Memory?

Flash memory is a type of EEPROM (electronically erasable programmable read only memory) - bits are stored in an electronic chip, not on a magnet medium like a disk. Flash memory is a distinct type of EEPROM, which is programmed and erased in large blocks, electrically - no mechanical parts. It's non-volatile, and generally faster than magnetic disks - it was named after its capability to erase a block of data "in a flash."

What are the primary uses of Flash Memory?

Flash memory is most commonly used in SSDs (Solid State Drives), Memory Cards, USB Flash Drives, Smartphones, Digital Cameras, etc.

Advantages and Disadvantages of Flash Memory against Magnetic Disks

Advantages:

• Much faster access

• More resistant to kinetic shock, intense pressure, water immersion, etc.

• More compact and lighter

• Lower power

Disadvantages:

• More costly per byte

• Limited lifetime

• Erases are costly

Note: Most systems nowadays use SSDs instead of HDDs, and HDDs are quickly becoming obsolete, so clearly the pros outweigh the cons in this situation

NAND and NOR Flash Memory

The 2 biggest types of non-volatile flash memories are NAND and NOR. They differ in their use of logic gates - one using NAND gate, the other using NOR. Consumer electronic devices typically use both of these flashes, NAND for multimedia file storage and NOR for code/app storage. Here's a full table of the differences between them:
https://www.embedded.com/wp-content/uploads/contenteetimes-images-design-embedded-2018-fl-1-t1.jpg

NAND Flash Memory

NAND flash has a smaller and less expensive memory cell area. It must be written in units of blocks, it's good for secondary storage where files don't mind being read out in large chunks/words, and it has a slower random byte access. It also has short erasing and programming times, and a longer lifetime.

NOR Flash Memory

Compared to NAND flash, NOR has a bigger memory cell area. It's byte accessible, which means it's good for ROM-like program storage where instructions need to be read out on a byte-size granularity, it has faster random byte access, longer erasing and programming times, and a shorter write time.

Organizing Flash Memory

Flash memory is typically divided in blocks/sectors. There can be many pages per block, for example 16 blocks per flash, 64 pages per block, and 4 KB per page \=\> 4 MB of flash, and the last 12-16 bytes of each page are reserved for error detection/correction and bookkeeping.

Operations on Flash Memory

Reads and writes in flash memory occur on a sub-page level granularity. You could read a byte (NOR) or a word (NAND), and under certain conditions you can write a byte (NOR) or word (NAND). Erases occur only on a sector level granularity. This is a key property and drawback to flash memory, i.e. the price we pay for quickly erasing a large amount of information in a "flash" is that it can be done only in large chunks or sectors.
Most operations proceed as normal. To read a byte or word of data, we need to specify which page we want to read from and what offset in that page to start reading, and the same goes for writing with the minor difference that we need to write on a clean page (that has not been written to since the last erase). Rewriting over memory usually requires an extra block/sector erase step.

Characteristics of Flash Memory

Unlike magnetic disks, rewriting over memory in flash requires an extra erase step. In magnetic disks, you can rewrite over any block that's previously been written to by simply changing the magnetization of the bits of the disk.
If we want to preserve the existing information on the other pages, and we just want to rewrite the one page, we'd have to read the entire sector into memory, rewrite in RAM over the space corresponding to the page we want to rewrite, then erase the entire sector and copy the modified sector from RAM back to flash, meaning that rewrites are slow in Flash Memory.
Another characteristic of Flash Memory is that it has a limited write lifetime (memory wear), where as magnetic disks can be rewritten indefinitely. NOR Flash can withstand 100,000 (10^5) write-erase cycles before becoming unreliable, and NAND Flash can withstand 1,000,000 (10^6) write-erase cycles before becoming unreliable.

Wear Leveling Solution

To extend the life of flash memory chips, write and erase operations are spread out over the entire flash memory. The idea here is to do a the following 2 things:

• Keep a count in 12-16 byte trailer of each page of how many writes have been made to that page, and choose the free page with the lowest write count

• Randomly scattering data over the entire flash memory span

Many of today's flash chips implement wear leveling in hardware.

RAID

RAID stands for Redundant Array of Inexpensive Disks. Disks are cheap these days, and attaching an array of disks to a computer brings several advantages:

• Faster read/write access by having multiple reads/writes in parallel

• Data is striped across different disks, e.g. each bit of a byte is striped onto a different disk

• Better fault tolerance/reliability - if one disk fails, a copy of the data could be stored on another disk. RAID has different levels with increasing redundancy. There's RAID0, RAID1, RAID 1 + 0 (RAID10), RAID2, RAID3, RAID4, RAID5, RAID6, etc.

RAID0

RAID0 is data striping with no redundancy. It has fast parallel reads and fast parallel writes, but it provides no fault tolerance.

RAID1

RAID1 mirrors each disk. We have redundancy here, but we don't get the parallel performance of RAID0. We can, however, get limited read speedup by submitting the read to all mirrors and taking the first data result. We also have slower writes here, but the OS can mask this by delaying writes.

RAID10

RAID10 combines RAID0 and RAID1. It first mirrors each disk, then stripes. It can recover from any single disk failure, and it can recover from 2 or more disk failures given that 2 disks that mirror the same data don't fail.

RAID2

RAID2 puts Error Correction Code (ECC) bits on other disks. Error correction codes are more compact than just copying the data, and provide strong statistical guarantees against errors, e.g. a crashed disk's lost data can be corrected with the redundant data stored in the ECC disks.

RAID3

RAID3 implements bit-interleaved parity. For each bit at the same location on different disks, compute a parity bit that's stored on a parity disk. Parity calculation can slow writes, so it's implemented in hardware.

RAID4

RAID4 implements block-interleaved parity. For each block at the same location on different disks, compute a parity block that's stored on a parity disk. This is very similar to RAID3.

RAID5

RAID5 implements block-interleaved distributed parity. Every disk here has both data and parity blocks instead of 1 disk like in RAID4. This avoids overuse of RAID4's parity disk, and is the most common parity RAID system.

RAID6

RAID6 implements a dual-parity system (in contrast to RAID5's single-parity system). In RAID5, data is distributed across all the disks in the array and an additional parity block is stored on one of the disks. If one disk fails, the data can be reconstructed from the remaining disks and the parity information. However, if two disks fail at the same time, data loss can occur.
In RAID6, two parity blocks are stored, which provides greater protection against data loss in case of simultaneous disk failures. With RAID6, up to two disks can fail and the data can still be reconstructed.

How many RAID Implementation Methods are there?

There are 3 methods to implement RAID - Software, Hardware and Firmware-based implementation.

Software-Based RAID

Software-Based RAID is implemented by plugging in disks to your computer bus and implementing RAID management in software in the OS kernel. The RAID software layer here sits above the device drivers, it's cost effective and easy to implement, but it's not that efficient. In Linux, we use the mdadm package to manage RAID arrays, and we cannot boot from RAID.

Firmware/Driver-Based RAID

Firmware/driver-based RAID setup means using a special hardware device called a RAID controller to combine multiple hard drives into a single system that can store data more efficiently and provide better performance.
This RAID controller has its own software (firmware) and drivers that allow it to automatically recognize and integrate any new hard drives that are plugged into the computer.
The RAID instructions are stored in the firmware of the controller, so the computer doesn't need any special software to run the RAID system.
With this method, we can, in fact, boot from RAID. During startup/boot, the RAID is essentially kick-started by the firmware.

Hardware-Based RAID

Hardware-based RAID involves connecting multiple disks to a standalone unit with a RAID controller, which presents the disks as a single device to the computer. This type of RAID implementation is expensive but highly efficient, and the file system does not need to know about RAID to use and benefit from the array. The connection between the RAID controller and computer is typically through a SCSI interface.

Human Perspective of a File

A file is a logical storage unit to store some semantically related information.

OS Perspective of a File

A file is a sequence of bytes that is mapped by the OS to a section of a physical storage device like a disk or a flash. Each byte is addressable by its offset from the beginning of the file, and it is up to the application to interpret these file data bytes.

What does a file consist of?

A file consists of data and attributes. Some important attributes include name, size, protection info(read/write/execute), timing info(when the file was created, last modified, last accessed, etc.), location on permanent storage, and some operating systems even support file types and file creators, indicating which application created the file (for example MS Word, Adobe Acrobat, etc.).
The attributes are usually collected together and stored in a file header or file control block, also known as an inode (UNIX).

What is a directory?

A directory is a set of logically associated files and sub-directories.

How are files organized within directories?

Organizing files within a directory is an essential task to ensure that files are easily accessible, identifiable, and manageable. There are three primary ways to organize files within a directory:

• Flat Namespace

• Two-Level Namespace

• Hierarchical Namespace

Flat Namespace

In this organization method, all files are located in a single directory. This method is straightforward and easy to implement. However, it can become challenging to manage when there are a large number of files, making it difficult to locate a specific file.

Two-Level Namespace

In this organization method, each user is given their own flat directory, and all their files are located in that directory. This method is useful in multi-user environments, such as shared servers or cloud storage systems, where each user can have their own private workspace.

Hierarchical Namespace

This organization method is the most commonly used method. In this method, the files and directories are organized in a tree-like structure, where each directory can contain files or subdirectories. Each file/directory appears as an entry in exactly one other directory, forming a tree structure. This method is useful for organizing files based on their attributes, such as file type, date, or relevance, and makes it easy to locate and manage files.

How do applications interact with the OS file system?

A file system is a way the operating system organizes and stores files on a disk. When an application needs to access a file, it uses an API to make a request to the operating system. The operating system's file manager takes over, interacting with the file system driver, which communicates with the hardware to read and write data to and from the disk using a file system format. The file system manager also provides other services such as file locking and security to ensure that the data is stored and retrieved correctly and protected from unauthorized access. Summarized, we take 3 steps:

• An app makes a file call via an API

• The call is translated into a system call that invokes the OS' file manager

• OS then turns these calls into disk reads/writes

Sharing Files/Directories

There are 3 options for sharing files and directories:

• Symbolic Links: A symbolic link is a special type of file that serves as a pointer to another file or directory on the system.

• Duplicating Directories: Duplicating directories involves creating a copy of the original directory and placing it in a shared location. This approach is less flexible than symbolic links and can be difficult to maintain consistency across multiple copies of the same directory.

• Setting Permissions: Setting permissions involves controlling which users or groups have access to a file or directory. The owner of a file or directory can set read, write, and execute permissions for the owner, group, and others.

Symbolic Link Sharing

A symbolic link is a special type of file that serves as a pointer to another file or directory on the system. When a user accesses a symbolic link, the system redirects them to the location of the actual file or directory. Symbolic links are a flexible way to share files or directories, as they allow users to access the same file or directory from multiple locations on the system. They are easy to implement, and allow convenient sharing of files/directories. They can also create loops, but these loops are easily dealt with since symbolic links are identifiable as distinct from files.

Mounting File Systems

A file system is a method used by an operating system to organize and store files on a disk. Sometimes, it is necessary to access files on different disks or partitions from within the same directory structure. Mounting a file system enables this functionality. When a file system is mounted, it is made available to the operating system as a new directory, called a mount point, within the existing directory structure. All the files and directories on the mounted file system are then accessible from the mount point as if they were part of the original directory structure.

Virtual File Systems

In general, the mounted file system could be of a different type than the current OS file system. A Virtual File System (VFS) layer provides an abstraction for file representation and manipulation. It defines a common model for files and directories and abstract operations on them. The VFS layer translates these abstract operations into specific read/write operations that are understood by each mounted file system. This allows applications to interact with different file systems using a uniform interface, regardless of the specific implementation of each file system.

Multiple File Systems

A typical disk can have multiple partitions, and each partition may contain a separate file system with its own directory structure to keep track of its files. Additionally, each file system may span multiple disks (such as in the case of RAID). Other I/O devices, such as a USB flash drive, may also contain their own file systems. When sharing files across different file systems and devices, it is necessary to mount these file systems so that they can be accessed within the current directory structure. This allows files from different partitions and devices to be accessed as if they were in the same directory.

Disk Partition

The OS can partition a disk into one or more groups of cylinders. The OS treats each of these partitions as their own, separate disk. A partition editor is used to manipulate partitions on the disk. Different partitions are used for different purposes - some store OS code, some are used for swap space, user files, etc.
A multi-boot system means a system that has multiple partitions, with each partition containing a different operating system. This allows the user to choose which operating system to boot when the computer is powered on or restarted.

Volumes

A volume is a single accessible storage area with a single file system. One or more partitions may take up a volume. A volume may be spread across different disk partitions on different disks, like, for example, in RAID disk systems.

File System Implementation

File system elements are stored on both non-volatile storage like flash or disks, and volatile storage like RAM.

How are file systems stored on the disk?

On the disk, the entire file system is stored, including 5 main elements:

• its entire directory tree structure

• each file's header/control block/inode

• each file's data

• a boot block, typically the first block of a volume that contains info needed to boot an OS from this volume (and empty if there's no OS to boot)

• a volume control block that contains volume or partition details

How are file systems stored in RAM?

In main memory (RAM), the OS file manager maintains only a subset of open files and recently accessed directories. Memory is used as a cache to improve performance. All the information is available for a fast search of memory, rather than a slow search of disk, e.g. for a file's FCB. The 4 main file system components stored in RAM are:

• Recently accessed parts of the directory structure

• A system-wide open file table (OFT) that tracks process-independent info of open files such as the file header and an open count of the number of processes that have a file open

• A per-process open file table that tracks all files that have been opened by a particular process

• A mount table of devices with file systems that have been mounted as volumes

What happens when a process calls open() to set up access to a file?

The following procedural steps are followed:

• The directory structure is searched for the requested file. This is fast if it's already in memory. Otherwise, directories have to be retrieved from disk and cached for later access.

• Once the file name is found, the directory entry contains a pointer to the file control block on disk. We retrieve the FCB from the disk, copy the FCB into the system's open file table which acts as a cache for future file opens, and we increment the open file counter for this file in the system OFT.

• Add an entry into the per-process OFT that points to the file's FCB in the system OFT.

• Return a file descriptor or handle to the process that called open(). Some operating systems use mandatory locks on open files so that only 1 process at a time can use an open file (this is the case in Windows), while others allow optional locks or advisory locks so that users have control over synchronizing access to files (which is the case in UNIX).

What happens when a process calls close() on a file?

The following steps are followed:

• Remove the entry from the per-process OFT

• Decrement the open file counter for this file in the system OFT

• If the counter's value is 0, then write back to disk any metadata changes to FCB such as its modification date. Note that there may be inconsistencies between FCB on disk and FCB in memory - file system designers need to be aware of this.

Directory Implementation

Directory implementation refers to how the files and directories are organized and stored within a file system. Two common methods are the linear list and the hash table.
In the linear list method, each directory is essentially a list of files, and searching for a file requires a linear search through the list, which can be slow. Creating or deleting a file also requires searching the entire list. However, keeping a sorted list in memory can improve performance.
In the hash table method, the file name is hashed, and each directory only needs to search a short linked list corresponding to that hash value, greatly reducing search time. Linux ext3 and ext4 file systems use a variant called HTree, which is a hashed B-tree that further improves lookup performance.

File Allocation

File allocation refers to how file data is stored on disk by dividing it into equally sized blocks. We have a few methods of file allocation, namely:

• Contiguous File Allocation

• Linked File Allocation

• File Allocation Table (FAT)

• Indexed Allocation

• Multilevel Index Allocation

• Modified Multilevel Index Allocation used in UNIX and Linux

Contiguous File Allocation

Contiguous file allocation is a method of file allocation in which each file occupies a contiguous block of disk space, meaning that the entire file is stored in a single, contiguous section of the disk. If a file is n blocks long, its addresses on disk will span from some number b to b+n-1. This method is simple and efficient for accessing files, since blocks are all allocated near each other on the disk. There are a few problems with this method - there's external fragmentation; we may not know a file's size in advance, so we might need to copy it to a larger chunk if the file exceeds allocation; a file may eventually need a lot of space but it grows at a slow rate, so allocating a lot of space to it wastes allocation. This last part is known as the "slow growth problem".

Fixed-Size Blocks in Contiguous Allocation

To solve all of these problems, we can implement fixed-size blocks. They solve external fragmentation, address the problem of not knowing the size of a file in advance (you just allocate more blocks on an as-needed basis), and solves the problem of slow growth.
When using fixed-sized blocks for file allocation, a data structure is needed to keep track of where each file is located on the disk. This data structure is used to store the starting block number of each file and is updated as files grow or shrink. The data structure must be flexible enough to accommodate the growth of a file, as additional blocks may need to be allocated to the file over time.

Linked Allocation

In linked allocation, files are represented as linked lists of disk blocks. To add to a file, the linked list is modified either in the middle or at the tail, depending on where we wish to add a block. To read from a file, the linked list is traversed until reaching the desired data block.
Linked Allocation solves every problem of contiguous allocation, and its advantage is that it needs minimum bookkeeping overhead to record where a file is located on disk. Another advantage is support for inserting data in the middle of a file - inserting blocks in the middle of a linked list.
Its problems, however, include: performance of random access is slow for reads/writes; readability is fragile (if 1 pointer is in error or corrupted, then we lose the rest of the file completely after that pointer).

File Allocation Table (FAT)

FAT is an important variation of linked lists. It was used in the stone age (in MS-DOS and Win 95/98) before it was replaced by NTFS which is the basis of Windows file systems from NT through Vista and Windows 7. Here, instead of embedding the pointers in the linked list with the file data blocks themselves, we separate the pointers out and put them in a special table (FAT) located at a section of the disk at the beginning of the volume. Random access read/write times are faster than pure linked lists, since the pointers are all co-located in the FAT near each other at the beginning of the disk volume, but it's still relatively slow, as we still have to traverse the linked list.

How is the FAT organized?

Entries in the FAT point to other entries in the FAT, but their values are interpreted as the disk block number. The unused blocks in the FAT are initialized to 0, and linked lists for files are terminated by EOF. Allocating a new block is simple, all we need to do is find the first 0-valued block. FAT-16 and FAT-32 refer to the size of the addresses used in FAT.

Indexed Allocation

Indexed allocation is a file allocation method in which all pointers to a file's data blocks are collected into a list or table called an index block, which can be stored in any block on disk, and index j into the list or index block retrieves a pointer to the j-th block on disk, making it more flexible than FAT. Also unlike FAT, index is just a linear list of pointers.
The advantages here are that there's no internal fragmentation, size of the file doesn't need to be known in advance, slow growth is efficiently supported and we don't have to traverse a linked list for random reads/writes. The problem with this is we need to know how large the index block should be. If it's too small, we don't have entries for large files. If it's too big, we have a lot of wasted entries. Luckily, we can solve this by implementing multilevel index allocation.

Multilevel Index Allocation

Multilevel index allocation is a file allocation method that uses multiple levels of index blocks to provide pointers to the data blocks on disk, allowing for a larger addressable space and more efficient use of disk space as unused second-level index blocks do not need to be allocated. In this method, the first-level index block provides a pointer to the second-level index blocks, and indexing into the second-level index block retrieves a pointer to the actual file block on disk. This method can support very large file sizes. However, here, accessing small files takes just as long as accessing large files. We have to go through the same number of levels of indexing and disk operations.

UNIX Variation of Multilevel Index Allocation

The UNIX (and Linux) file system uses a hybrid indexing scheme that combines direct, single-level indirect, double-level indirect, and triple-level indirect blocks to accommodate both small and large files efficiently. For small files, the direct pointers are used to store the data blocks of the file, while for larger files, the indirect pointers allow for expansion of the index block to span a large number of disk blocks. This approach minimizes wasted memory for small files while allowing for efficient storage and retrieval of large files.

Suppose we have 15 entries in the index block. The first 12 point to direct blocks, the 13th points to a 1-level indirect block, the 14th points to a 2-level indirect block, and the 15th points to a 3-level indirect block. For small files, this approach only uses a small index block of 15 entries, so there is very little wasted memory. For large files, the indirect pointers allow expansion of the index block to span a large number of disk blocks. UNIX stores this hybrid index block with the file inode.

Free Space Management

Another aspect of file system management is managing the free space. The file system needs to keep track of what blocks of the disk are free, and what blocks are not. For that, we can keep a free-space "list". There are a few approaches we can take:

• Bit Vector or Bit Map

• Linked List

• Grouping

• Counting

Bit Vector (Bitmap) Free Space Management

Bit Vector or Bitmap is a free space management approach where each block is represented by a bit and all bits are concatenated into a bit vector that indicates whether a block is allocated or free, making it simple and easy to implement and search, but the size of the bit vector can become quite large. An allocated block bit is not set, an unallocated block bit is set. Linux ext2fs uses a version of this approach.

Linked List Free Space Management

In the Linked List approach of managing free space, all free blocks are linked together to form a list, which keeps track of only the free blocks, making it faster than the Bitmap approach as it finds the first free block immediately. It's also less wasteful than Bitmap since Bitmap keeps track of both free and allocated blocks, so its overhead is larger than Linked Lists if memory is mostly allocated. However, the problem with this approach is that traversing the free list is slow if a large number of free blocks need to be allocated all at once, which hopefully occurs infrequently.

Grouping Free Space Management

The grouping approach for free space management is a variant of the linked list approach where each list block contains n-1 pointers to free blocks, and the last pointer points to the next list block with more free pointers. This allows for faster allocation of larger numbers of free blocks all at once.

Counting Free Space Management

Counting is a free space management technique that uses a grouped linked list with a field added to each pointer entry indicating the number of free blocks immediately after the block pointed to. This allows for even faster allocation of a large number of free blocks.

File System Performance

To improve file system performance, several approaches can be taken both in memory and on disk. In memory, caching FCB information and directory entries can speed up access, as well as hashing the directory tree to quickly locate entries. On disk, indexed allocation is generally faster than linked list allocation for file data, and counting, grouped, or linked list approaches can optimize the free block list for faster allocation of large numbers of files. In addition to the caching and allocation approaches, there are a few other potential optimizations for improving file system performance:

• The disk controller can have its own cache to store frequently accessed file data and FCBs.

• Read ahead: if the OS detects sequential access, it can read not only the requested block but also several subsequent blocks into the main memory cache in anticipation of future reads.

• Asynchronous writes: Delay writing of file data removes disk I/O wait time from the critical path of execution. This allows a disk to schedule writes efficiently, grouping nearby writes together. May avoid a disk write if the data has been changed again soon. Note that in certain cases, synchronous writes may be preferred, e.g., when modifying file metadata in the FCB on an open() call.

• Cache file data in memory.

• Smarter layout on disk: Keep an inode/FCB near file data to reduce disk seeks, and/or file data blocks near each other.

Reliability/Fault Recovery

In general, if the OS crashes due to a hardware/software failure, we need to be able to recover gracefully. The file system needs to be engineered to ensure reliability and fault recovery. For example, asynchronous writes introduce the problem of maintaining consistency between the file system on disk and the writes cached in RAM. If there's a system failure, the cached writes may be lost. Also, even if all writes are synchronous, there is still a consistency problem - e.g. a file create() involves many operations on the file system, and maybe interrupted at any time in mid-execution.
One approach we could take here is have the file system run a consistency checker.

Consistency Checking

The file system often runs a consistency checker like fsck in UNIX or chkdsk in MSDOS. In linked allocation, this checker would check each linked list and all FCBs to see if they are consistent with the directory structure. Similar checks would be performed for indexed allocation. Additionally, the checker would also check each allocated file data block to ensure that its checksum is valid. However, this approach has several disadvantages. It is heavyweight and takes a long time to check the entire file system. Furthermore, while it can help detect errors, it doesn't necessarily help correct or recover from them. So, we want a solution that helps us recover from file system failures, and for that we introduce log-based recovery.

Log-Based Recovery

To recover from file system failures, log-based recovery is used. The operating system maintains a log or journal on disk of each operation on the file system, which is consulted after a failure to reconstruct the file system. Each operation on the file system is written as a record to the log on disk before the operation is actually performed on data on disk. This is called write-ahead logging. The log contains a sequence of statements about what was intended in case of a crash. Some file systems only write changes to the metadata of a filesystem to the log, e.g. file headers and directory entries only (NTFS), and not any changes to file data. Linux ext3fs can be parameterized to operate in three modes:

• Journal mode: both metadata and file data are logged.

• Ordered mode: only metadata is logged, not file data, and it's guaranteed that file contents are written to disk before associated metadata is marked as committed in the journal.

• Writeback mode: only metadata is logged, not file data, and there is no guarantee that file data is written before metadata. This is the riskiest and least reliable mode.

Security and Protection

Security and protection are broad, deep and crucial topics when we're talking about operating systems. They ensure the safety and privacy of data and systems. The OS provides authentication and authorization mechanisms to verify the identity of users and restrict access to resources, as well as confidentiality that can be maintained through encryption, availability through measures to detect and mitigate attacks, and integrity through techniques like checksums and digital signatures to make sure data hasn't been tempered with.

Authorization

After a user's successful authentication through login and password, the operating system must determine what files and services the user or process is allowed to access. This is achieved by assigning the user or process to a protection domain that specifies the resources it can access. A domain is a collection of access rights that includes an ordered pair of an object and a set of rights, such as read, write, execute, and print privileges. In Unix, each user is associated with a domain, and object and access rights can be collected into an access matrix. The access matrix is a table that defines the access permissions of each user to various system resources, which helps to ensure that only authorized users can access particular files and services.

Access Matrix

An access matrix is a table that defines the access permissions of each user to various system resources in order to ensure that only authorized users can access specific files and services.

Access Matrix Implementation

There are 3 ways we'll look at to implement access matrices. These 3 implementations are implementing it as a single global table, implementing it as an access control list (ACL), and implementing it as a capability list.

Access Matrix as a Single Global Table Implementation

The access matrix can be implemented as a single global table that defines the access permissions of each user to various system resources. However, this approach can be challenging because the table can be large and difficult to keep in memory, and it can be time-consuming to exploit relationships between entries or change access permissions. Additionally, the matrix may be very sparse, with few entries filled in, making it difficult to compress efficiently. One solution is to use virtual memory-like demand paging to keep only active portions of the access matrix in memory.

Access Matrix as an ACL Implementation

An alternative implementation of the access matrix is as an access control list (ACL), where each column of the matrix defines access rights to a specific object, such as a file. The access permissions are stored in the ACL with the file, allowing empty entries to be discarded, which saves space. When a process attempts to access the file, the system searches the ACL for the appropriate permissions. Both UNIX and Windows NT/2000 about 5000 years ago used a form of ACL, with access permissions stored in the File Control Block (FCB). This approach makes it easy to determine the access rights for a given file, but determining the set of access rights across a domain can be challenging.

Access Matrix as a Capability List Implementation

Another implementation of the access matrix is as a capability list, where each row of the matrix defines access permissions for a specific user or domain. A capability list is created for each user or domain and consulted whenever a process in that domain attempts to access a file. This approach also allows for the compression of empty entries. However, a new data structure must be created to store per-user capability lists, which can be more complex than ACLs that exploit existing data structures such as File Control Blocks (FCBs). This implementation makes it easy to determine the access rights across a given domain but challenging to determine the access rights for a particular file. The Hydra and Mach operating systems use capability lists. Anyone know what they are? No, because they don't exist - they're older than God himself.

UNIX Protection Mechanisms

UNIX-style operating systems implement ACLs for file protection, which can be viewed using the "ls -lg" command. The file permissions are displayed in the format "-rwxrwxrwxs filename", where the last bit "s" represents the sticky bit. If set, only the directory's owner or creator can delete or rename files. The sticky bit is commonly set in directories such as /tmp to prevent normal users from deleting other users' files. The "chmod" command is used to change file permissions for files that the user owns, for example, "chmod 700 foo.txt".

Program Threats

Program threats refer to various ways in which programs can cause security breaches. This includes writing programs that create security breaches, such as Trojan horses, which are code segments that misuse the environment, such as supervisor mode. Trap doors (more commonly known as backdoors) are left by programmers as holes in the software that only they can use, while logic bombs are programs that initiate security incidents under specific circumstances.

Stack and Buffer Overflow

Another program threat that's common is the programmer's neglect to code bounds checking on an input field for a program that runs in supervisor mode. This causes an overflow that overwrites the return address with the address of the exploit code, allowing the attacker to execute their own code. The attacker can then write a simple set of code on the next space on the stack, such as spawning a shell, to gain control of the system.
Diagram:
https://www.researchgate.net/profile/Yves-Younan-2/publication/244151700/figure/fig2/AS:669562185981963@1536647473694/Stack-based-buffer-overflow-using-indirect-pointer-overwriting.png

Viruses

Viruses are another form of malicious software, usually embedded into another, legitimate program. They're self-replicating, and they're designed to infect other programs. Viruses can spread through various means such as emails, spams, macros, etc. and are usually introduced into a system through a dropper, which is a type of trojan horse that inserts the virus into the system.

Worms

Worms are self-replicating processes that use the spawn mechanism to duplicate themselves, using up system resources and potentially locking out other processes. In other words, worms are similar to viruses in the sense that they're designed to duplicate themselves and are designed to spread, but the key difference is that worms don't need to be attached to a host program to infect a system. Instead, they use network vulnerabilities to automatically spread from system to system, without the need for user intervention, where as viruses typically need some sort of user action. Once a worm infects a system, it can use up system resources and cause various types of damage, such as stealing sensitive information or launching a denial-of-service attack.

What are the 6 classic properties of Security?

The 6 classic properties of security include:

• Confidentiality

• Authentication

• Authorization

• Integrity

• Non-repudiation (verification that an event actually took place)

• Availability

Note: we're primarily focusing on the first 3.

Confidentiality

Confidentiality is the practice of keeping sensitive information secure and private. One way to achieve confidentiality is through encryption, which involves converting plaintext into ciphertext using a cryptographic algorithm and a secret key. Only authorized individuals who possess the correct key can decrypt the ciphertext back into plaintext. Modern cryptography uses keys to encrypt and decrypt, and the algorithm for encryption or decryption does not need to be kept secret. However, the input must be statistically random to avoid frequency cryptanalysis. In the case of files, the encryptor and decryptor are usually the same person, while in the case of communication, they are different people.

Symmetric Key Cryptography

Symmetric key cryptography is a type of encryption where the same key is used for both encryption and decryption. This approach has been used throughout most of the history of cryptography with standards such as AES and Triple-DES. Encrypted file systems like EFS and EncFS use symmetric key cryptography, where the key used to encrypt and decrypt files is stored in encrypted form and requires a passphrase to be entered at run time to decrypt the key. The main advantage of symmetric key cryptography is its speed and simplicity, but it requires secure key distribution and management to maintain confidentiality. This method has largely been replaced by asymmetric key cryptography in modern times.

When the decryptor is physically separate from the encryptor, as in a secure remote login, how does the decryptor securely obtain the key K?

To securely obtain the key K when the decryptor is physically separate from the encryptor, a common approach is to securely transport the key to the destination. However, there is no guarantee that a spy won't intercept the key. This is known as the classic symmetric key distribution problem. In such scenarios, the spy could copy the key without letting the decryptor or encryptor know and then eavesdrop on all future encrypted communications, which is a serious security threat. Therefore, additional security measures such as key exchange protocols and public key cryptography are used to address these challenges.

Diffie-Hellman Key Exchange

Diffie-Hellman key exchange is a method of securely distributing a symmetric key over a public network. It was invented in the 1970s by Diffie and Hellman, and it involves endpoints exchanging public quantities with each other and then calculating a shared symmetric key from these publicly exchanged quantities. The keys calculated are the same. The Diffie-Hellman key exchange has the property that even though an attacker could eavesdrop on all the public communications, it cannot calculate the symmetric key. Therefore, this method solves the classic symmetric key distribution problem, and it was the foundation for public key cryptography.

Public Key Cryptography

Public key cryptography, also known as asymmetric cryptography, uses two mathematically related keys - a public key and a private key - to encrypt and decrypt information. The public key is known to everyone, while the private key is only known to the owner. When a message is sent, it is encrypted with the recipient's public key and can only be decrypted by the recipient's private key. This provides confidentiality, as even if someone intercepts the encrypted message and has the public key, they cannot decrypt the message without the private key. Examples of public key cryptography algorithms include RSA and Diffie-Hellman (typically not used in this way).

SSL/TLS and SSH Approach of Confidentiality

Secure Sockets Layer (SSL) and its successor Transport Layer Security (TLS) are cryptographic protocols used for secure communication over the internet. Similarly, Secure Shell (SSH) is a protocol used to encrypt remote login sessions and other network services. All of these use a hybrid public key + symmetric key approach to encrypt remote communication between computers. During the initial exchange of information, the client and server use public key encryption to establish a secure communication channel and to exchange a session key. Once the session key is established, the communication switches to symmetric encryption using the shared session key.
This approach solves the key distribution problem of symmetric encryption and the computational expense of asymmetric encryption, making it a widely used approach for secure communication.

Authentication

Authentication is the process of verifying the identity of a user or entity. It involves confirming the validity of provided credentials or information to grant access or permission. An example of this is typing in your password. The OS checks whether it matches your account's password, and if so, you're authenticated and allowed to proceed.

How does the OS store passwords?

The main problem with storing passwords is how to do it securely. If passwords are stored in plaintext, anyone with root privilege can access them. If passwords are encrypted, the encryption key can be compromised. However, it is not necessary to be able to decrypt a stored password value, which opens up the possibility for more secure solutions.
To securely store passwords, systems often use hashed passwords, which are created by applying a one-way function, such as a cryptographic hash function, to the password. This produces a fixed-size output string, known as a hashed value or message digest, that cannot be reversed to reveal the original password. Examples of hash functions include MD4, MD5, SHA-1, SHA-2, and others. The OS then only needs to store the hashed values. When a user enters a password, the OS hashes that password and compares it to the hashed value it already stores.

Attacks Against Hashed Passwords

An attacker could try to guess your password using common words, or, more realistically, they could attempt a brute force attack on your password. A brute-force attack is an attempt to discover a password by systematically trying every possible combination of letters, numbers, and symbols until you discover the one correct combination that works. Common tools for this are examples like John the Ripper, Aircrack-ng, Hashcat, etc. Now, the OS has to protect its users, so it has to come up with some solutions. Some solutions include blocking or slowing down access after too many failed login attempts, forcing users to change the password frequently, forcing users to choose hard-to-guess passwords, etc.

Linux Password Mechanisms

Earlier versions of Unix (or, I guess, Linux - at least be consistent with the title and the text...) used to keep user account information, including hashed passwords, in a text file called "/etc/passwd". This file was used by many tools, but it needed to be world-readable, which was a security risk. Additionally, in earlier versions, hashed values were also world-readable, making it easier to launch a brute-force attack. To address these issues, newer versions of Unix use a shadow password mechanism, where the hashed passwords are stored in a separate file that is only accessible by privileged users.

Shadow Passwords

The Shadow Password mechanism in Linux allows the account information to be stored in the /etc/passwd file with the password stored as a single "x" character, making it compatible with other tools. However, the hashed password and other sensitive information are stored in a separate file called /etc/shadow, which is only readable by the root account, enhancing the security of the password storage system. The passwords are hashed using a cryptographic hash algorithm such as MD5 or SHA-1.

Passwords on Linux

We've already established that Linux Passwords are stored in /etc/shadow, and in /etc/passwd as a single "x" character. Hashed passwords in Linux will use a "salt" value, to prevent attacks using pre-computed tables such as Rainbow tables. For that reason, a hashed password might look something like:

smithj:$6$ABCD1234$JnCx/.NCi4315V0AONxuVpUIRvPivoQjLzY0M28iYkOJU/FwVhXE4Me2f72fldvGEOpnTAB7IuVrsVfwpT/XT/:38478:0:99999:5:::

The first part, 'smithj' is the user for which the password is being stored. The first part, $6$ indicates the hashing algorithm (SHA-512 in this case according to the internet), and after it comes the salt value. In this case, it's ABCD1234. Then, we have the hashed password.
The crypt() function is a POSIX C library function used to compute the hash of user account passwords. More info about crypt() here:
https://man7.org/linux/man-pages/man3/crypt.3.html