???

(CHECK SLIDESHOW)

Representation of File Directory

???

Directed Acyclic Structure

Implementation of File Directory

Besides name, data, and metadata, the filesystem must track:

• Size
• Type
• Location
• Protection
• Use

File Control Block

Where to store this is an important design issue.

• If you store attributes directly, you could slow down the search.

File Control Block: Data structure that encapsulates are relevant attributes of a process.

• Stored separately from the file directores
• Tradeoff: Store critical attributes in the directory, but have other attributes in the FCB via pointer.

TODO There are three approaches

1. Fixed-Size Array of ???
   • Limited size.
   • Random-access (fast search).
2. Variable-Length Array of ???
   • ???
3. Variable-Length Array of ???
   • ???

Internal Structure

Operations on Files

Open a File

Open File Table: Data structure that tracks all files currently in use.

• Allows for efficient access.

Open File Operation: Prepares a file for efficient access by TODO

Whenever you update a file, you never update just a block. Everything wr.t. the file in memory has to be erased and re-added.

Close a File

Close file reverses the effects of the open operation by saving the state of the file in the FCB and freeing the OFT entry.

Steps:

1. If the current content is modified, write the change.
2. Update file lenght in FCB
3. Free OFT entry
4. Return status of the close operation to caller

Allocation

Contiguous Allocation

Definition — Sector: The smallest physical unit of memory (?).

• A sector is hardware-level and can vary depending on manufacterer.
• TODO Like, smallest addressable?

A contiguous disk block is allocated via sector.

TODO details of operation, from 8.5.1

Access is really fast because we have random-access.

• But, we can’t easily expand the file! You may have to wholly deallocate and reallocate elsewhere.
• Also, fragmentation becomes a problem.

Linked Allocation

Linked Block Allocation Scheme: Rather than looking for contiguous blocks, we just go for whatever blocks are available.

• Each block of the file has a pointer to the next block, allowing the OS to traverse.

Pros:

• Easy to expand.
• No fragmentation.

Cons:

• Linked list is way slower than an array (no random-access, slow traversal).
• Decrease reliability of disk, if a disk block is damaged, the rest of the file may be lost.
• Considerable waste of disk space (tons of pointers).

Clustered Allocation

Combination approach, we will allocate whatever contiguous clusters we can, but the entire file doesn’t need to be contiguous.

• The last block of a cluster points to the starting block of the next cluster.
  • We also have to pass around length of the cluster as well.

This still has the issue of being really weak to hardware failure of a single block.

???

Aside — Both of these methods below also mitigate loss of a block (no longer breaks the chain)

File Allocation Table

TODO Definition, and 8.5.7

The FCBs must be loaded somehow, but having them all in memory might be too costly/impossible.

• Rather than have the blocks in memory hold a lot of information, we’ll have the FAT be the in-between.
• The FAT is just an array of numbers, where each number is just a pointer to the next ???.

TODO It’s like how in scaled partial pivoting we could introduce a pivot array to make swapping faster (spacetime tradeoff).

Indexed Allocation

inodes, a very smart way of allocation.

Rather than a FAT, we have index tables bridge the FCB and disk blocks.

TODO I did not understand the explanation. Something something 1-level 2-level and it allows massive allocation?

• Something something the FCB has pointers for the first n (e.g., 10) blocks, which eliminates cost for small files. The next m blocks will need a 1-level inode thingamajib, which incurs penalty. Additional levels can be added.
• It’s like, the FCB will have pointers to each level? So the cost of jumping to a level 1 or level 2 are the same???

Free Space Management

Bitmap: Data structure that represents the allocation status of a disk.

• Each bit represents one disk block. 0 means free.
• If system architecture doesn’t support individual bits (e.g., only works with bytes, which is most hardware), we set/reset/search for individual bits by doing bitwise logical operations on the word containing the target bit

TODO Okay but like, why we are maintaining a bitmap? How how do you use this?

???

Programmed I/O

Programmed I/O: Style of I/O programming where the CPU does everything.

• It runs the device driver and copies all the data between the I/O controller and main memory.

TODO “Programmed I/O with Polling” table:

(TODO NOTE TO SELF: All methods use the same registers, so I’ve moved the table here)

TODO Explanations of all three methods are quite unclear.

With Polling

Generic interface to device controller consists of:

Good for: Fast operations (e.g., mouse)

Cons:

• Stays busy.
• Not feasible with operating systems that support multi-programming (TODO is this true ???)

With Interrupts

Rather than keeping the CPU busy checking the busy flag over-and-over, the process will block itself and the I/O device will send an interrupt on its own.

• Basically, everything else is the same, except the CPU no longer checks the busy flag once

Good for: Slow operations (e.g., printer)

With Direct-Memory Access

There’s a DMA controller that passes the buffer contents to main memory, offloading the work from the CPU.

Data Buffering and Caching

Buffer: Register or area of main memory that holds data generated by a producer and is removed later by a consumer.

• Purpose is to decouple the producer from the consumer in time.

Example — a printer will have a buffer to sync its speed (TODO what?)

Raw Input Mode: TODO

Cooked Input Mode: TODO

Example: Suppose you type: “t e s t x

In Raw Input mode, the application would get this sequence of characters and have to parse it.

In Cooked Input mode, the application would simply get “text”

TODO I don’t understand how or why this happens.

Buffer Swapping

Technique that allows operations of a producer and consumer to overlap by using two buffers.

• Provided that producer and consumer are the same speed, they can use two buffers and write/read to their respective buffers, and swap buffers once they’ve both terminated.

Circular Buffer

Like buffer swapping, but for if they are different speeds.

• spacetime tradeoff

Error Correction

TODO

Hamming Code

Bad Block

Bad block (bad sector) is a storage block that’s no longer reliable due to physical damage.

• When we write a block, we compute the ECC. When we read the block, we re-compute the ECC and check against the stored ECC.
• Sometimes errors are temporary and are solved just by repeating an operation.
• TODO something something ??? spare sectors on a track?

Methods:

1. Sector Remapping: For the bad block, jump to a spare sector.
   • When you hit a bad sector, you have to jump to the spare sectors, then jump back; which can be bad due to rotational latency.
2. Sector Slipping: Push everything forward past the bad sector
   • Cost: Shifting every sector is very time consuming.
   • But, everything is now consecutive.

Stable Storage

Stable Storage: Approach to data management that uses redundance along with a strict protoocl for reading, writing, and error recovery.

• Guarantees all data remaisn consistent in the presence of media and crash failures.
• Uses two independent disks, A and B, which contain identical copies of data.

everything is atomic

we keep shadow copies of things

so like RAID?

RAID

A set of disks is

Since probability of media failure increases rapidly with the number of disks, redundancy is used to decrease the probability of data loss.

• Redundant data can range from one parity bit per block, to full duplication (the type determines how many errors can be detected and corrected).

TODO