Files and IO Flashcards by Josh Barbee

All files stored in root directory

Single level directory

How well did you know this?

Not at all

Perfectly

Files stored in tree structure

Hierarchial directory

How well did you know this?

Not at all

Perfectly

Direct copy of a file to another place in directory tree

Hard link

How well did you know this?

Not at all

Perfectly

Sector 0 stores this

Master Boot Record

How well did you know this?

Not at all

Perfectly

Stores start and end of each partition. Used to boot

Master Boot Record

How well did you know this?

Not at all

Perfectly

Each file stored as continuous run of blocks

Contiguous allocation

How well did you know this?

Not at all

Perfectly

Benefits from fast read times and easier to track blocks

Contiguous allocation

How well did you know this?

Not at all

Perfectly

Leads to disk fragmentation and can be expensive to compact

Contiguous allocation

How well did you know this?

Not at all

Perfectly

Each block stores pointer to next block in file, not necessarily same physical block

Linked list allocation

How well did you know this?

Not at all

Perfectly

No external fragmentation, but slow random access

Linked list allocation

How well did you know this?

Not at all

Perfectly

Store linked list as array, with index as physical block and value is next file block. Value of -1 is the last block

Linked list allocation using In-Memory table

How well did you know this?

Not at all

Perfectly

Each directory entry only needs to store starting block number for file

Linked list allocation using In-Memory table

How well did you know this?

Not at all

Perfectly

Entire table must be in memory at same time for faster access than LL

Linked list allocation using In-Memory table

How well did you know this?

Not at all

Perfectly

Store attributes and disk addresses of file blocks

I-nodes

How well did you know this?

Not at all

Perfectly

Only needs to be in-memory when file accesses

I-nodes

How well did you know this?

Not at all

Perfectly

Dependent on number of files open at once

I-nodes

How well did you know this?

Not at all

Perfectly

Each directory entry points to fixed portion, with length of entry and data

Directory implementation

How well did you know this?

Not at all

Perfectly

I-node stores file length, attributes and file name in memory

Directory implementation with contiguous memory

How well did you know this?

Not at all

Perfectly

I-nodes stores file names in a heap, pointed to by file entry

Directory implementation with heap

How well did you know this?

Not at all

Perfectly

Used to guard against lost files during crashes

Journaling file system

How well did you know this?

Not at all

Perfectly

Keep a list of actions before taking them, then perform actions

Journaling file system

How well did you know this?

Not at all

Perfectly

Operations should be ________ to ensure that actions can be replayed without harm

idempotent

How well did you know this?

Not at all

Perfectly

a measure of state change

idempotent

How well did you know this?

Not at all

Perfectly

Each file has many blocks, leading to more seeks and rotation delay

Smaller blocks in disk

How well did you know this?

Not at all

Perfectly

Waster space within blocks, but better transfering

Larger blocks in disk

Start at block 0 of disk. Write every block to output disk and stop during last block.

Physical dump

Also copies bad blocks, which can cause corruption

physical dump

Cannot restore individual files

physical dump

Start at specific directory and recursively dump all files and directories since last modified

logical dump

Easier to restore specific file

logical dump

Start at root, mark bit for modified files and all directories

logical dump - phase 1

walk tree, unmark directories without any modified files

logical dump - phase 2

go through i-nodes and dump marked directories

logical dump - phase 3

Stores collection of blocks that are kept in memory for frequent access

caching

Some blocks may not actually be referenced twice within a short interval (anti-temporality)

issue with caching

Blocks likely not needed again are placed at front of queue, and blocks needed again are at back of queue

caching, addressing temporality

If reading block k to cache, read in k + 1 if block not already in cache

block read ahead

Can store all i-nodes at beginning of disk. Requires half rotation for any seek on average

Reducing disk arm motion

Put all i-nodes in middle of disk, instead of start, reducing average seek between i-node and block by factor of two

Alternative approach to reducing disk arm motion

Divide disk into groups, each with own i-nodes, blocks, free list

Approach to reducing disk arm motion

Stores information in fixed blocks. Transfers are fixed blocks

Block devices

Stream of character. Not addressable and no support for seeking

character devices

Each controller for I/O device is assigned a unique memory address in same physical memory as rest of computer

memory mapped i/o

Requires that I/O memory not be cached

memory mapped i/o

Requires hardware to have DMA controller. Allows hardware to directly read and write memory without blocking

direct memory access

CPU programs DMA controller by setting registers to desired memory location

direct memory access - step 1

DMA controller initiates transfer via read request from DMA to disk controller

direct memory access - step 2

Disk controller writes from disk to main memory

DMA - step 3

Disk controller sends ACK to DMA controller to

DMA - step 4

DMA controller interrupts CPU to notify transfer complete

DMA - step 5

Interrupt that leaves machine in well-defined state

precise interrupt

interrupt that leaves machine in undefined state

imprecise interrupt

- PC must be saved in known place - All instructions before PC must fully execute - No instructions after PC executed - Execution state at current PC is known

precise interrupt

- User level I/O software - Device independent I/o software - Device drivers - Interrupt handlers - Hardware

I/O software layers

For each class of driver, OS defines set of functions that driver must support

Uniform interfacing for device drivers

Request a buffer of blocks rather than a single block

Buffering in I/O

Solution to buffer being read/written to at the same time

double buffering

Should be able to determine what to do in case of I/O errors. If cannot, should pass to device-independent I/O software

Error reporting

- Accept read / write requests from software - Must initialize device if required - Manage power and logging of device

Roles of device driver

Must assume that multiple calls can be made into driver code before first one finishes

reeentrant code

Cannot make system calls, except for limited subset

drivers

Organized into cylinders, each contains as many tracks as vertically-stacked heads. Tracks divided into sectors, with variable number of sectors

organization of magnetic disks

Disk controller informs OS with number of cylinders, heads, and sectors

Dealing with multi-zone sectoring approach

Disk sectors numbered consecutively starting at 0

logical block addressing

Each disk divided into strips of k sectors each. Write to consecutive strips over drives in round-robin fashion

Raid 0

Duplicate all disks. No performance gain or parallelism. Still uses sector stripping

Raid 1

Works on word memory size basis. Use hamming code/ECC to ensure bytes are properly stored. Requires devices to be synchronized

Raid 2

Single parity bit for each data word, written to dedicated parity drive

Raid 3

Strip-for-strip copy written onto parity drive. Protects against loss of drive, but bad for small updates

Raid 4

If one sector lost or changed, must recalculate parity for all relevant sectors

Raid 4

Distribute parity bits over all devices, but do not store parity bits for own sector on device

Raid 5

Store extra copy of parity bits on each block. Use two strips rather than one. Slightly more fault-tolerant, but less storage

Raid 6

Stores bit pattern to allow hardware to recognize start of sector, as well as number of cylinders and sectors

Preamble of disk

Used to recover from read errors

ECC section of disk

Each sector on track is offset from previous track

Cylinder skew

RPM = 10,000, 30 sectors, track-to-track seek time of 800 microseconds

40 seconds of cylinder skew

Sectors may be too close to each other, causing excess seek time

Interleaving of sectors

- Seek time - Rotation delay - Data transfer time

Factors of speed / time to write to disk

Disk executes requests to read from sector one at a time

First-come-first serve

Handle request to closest sector next

Shortest seek first

Can lead to starvation depending on sectors being read

Shortest seek first

SSF, but can only go in one direction at a time. If no pending requests, flip direction

Elevator scheduling

- Stable writes - Stable reads - Crash recovery

Requirements for stable storage

After write, the data read out = data written. Keep trying to write sector until valid one found

stable writes

Reading data and checking ECC leads to correct EC

stable reads

able to overwrite bad sector from one disk with good sector from other disk

crash recovery

Copy value of holding register into counter and decrement counter at each pulse. When counter is 0, throw an interrupt by CPU. Must be manually restarted

One-shot mode

Holding register copied automatically when clock reaches 0 and process repeats.

Square wave mode

Linked list of actions to take at certain ticks. each node in ll stores number of ticks until next action. decrement ll on each tick

connecting multiple clocks