COP4610 FINAL

file

a named collection of blocks

file header

associates the file with its disk sectors

what are the four file system components?

storage (disk) management, naming, protection, reliability

storage (disk) management

organizes storage blocks into files

naming

provides file names and directories to users, instead of tracks and sector numbers

protection

keeps information secure from users

reliability

protects information loss due to system crashes

what are the three ways to access a file?

sequential access, random access (direct access), and content based access

sequential access

bytes are accessed in order

random access (direct access)

bytes are accessed in any order

content based access

bytes are accessed according to restraints on byte contents

give example: most files are small, and most references are to small files

e.g. .login and .c files

give example: large files use up most disk space

e.g. mp4 files

bad news for file system designers

large files account for most of the bytes transferred between memory and disk

what are the 6 disk allocation policies?

contiguous, link-list, segment-based, indexed, multilevel indexed, hashed

contiguous allocation

files are stored contigously on disk

what is the process for contiguous allocation?

a) specify the file size

b) search the disk allocation bitmap for consecutive free blocks

what are the pros to contiguous allocation?

• fast sequential access

• ease of computing random file locations

what are the cons in contiguous allocation?

• external fragmentation

• difficulty in growing files

linked-list allocation

each file contains a pointer to the next block, with a special marker indicating the file’s end

what is linked-list allocation used in?

used in MS-DOS file systems, File Attribute System (FAT)

what is a pro of linked-list allocation?

files can grow dynamically with incremental block allocation

what are 3 cons of linked-list allocation?

• sequential access may suffer

• horrible random access performance

• unreliable due to broken pointers

indexed allocation

uses a preallocated index to directly track file block locations

what is a pro of indexed allocation?

files can grow dynamically with incremental block allocation

what are 3 cons in indexed allocation?

• sequential access may suffer

• horrible random access performance

• unreliable to due broken pointers

segment-based allocation

uses a segment table to allocate multiple contiguous regions of blocks

what is a pro to segment-based allocation?

relaxes the requirement of large contiguous disk regions

what are 2 cons to segment-based allocation?

• fragmentation is greater than 100%

• random access is slower compared to pure contiguous allocation

multi-level indexed allocation

some index entries point to index blocks instead of data blocks

single indirect block

contains pointers to data blocks

double indirect block

contains pointers to single indirect blocks

triple indrect block

contains pointers to double indirect blocks

what is a pro to multi-level indexed allocation?

optimized for both small and large files

what are 3 cons to multi-level indexed allocation?

• requires multiple disk accesses for triple indirect blocks

• file size is capped by the number of pointers

• arbitrary file size boundaries between levels

hashed allocation

allocates disk blocks based on a hash of the block content

what are 2 pros to hashed allocation?

• file blocks with the same content can share the same disk block, saving storage

• good for backups and archival storage

what is a con to hased allocation?

poor disk performance

i_node

under UNIX, a file header is stored in a data structure

directory

stores a collection of file and/or directories

name collisions

multiple files with the same names

absolute path name

consisting the path from the root directory ‘/’ to the file

path resolution

many levels of directory lookups

what are the 5 different ways to organize a name space?

flat name space, hierarchical name space, relational name space, contextual name space, content-based name space

flat name space

each URL provides a unique name

hierarchical name space

within individual websites

relational name space

can search the internet via search engines

contextual name space

page ranked according to relevance

content-based name space

you can find your information without knowing the exact file names

metadata

data about data
free blocks, directories, file headers, indirect blocks

fsck

file system consistency check and repair when crash occurs

log

a journal that is never erased

what is the two-phase locking process?

1. acquire all locks

2. perform updates and release all locks

striping

writes data across multiple drives

i.e. 1st block stored on disk 1, 2nd block stored on disk 2

what are the three characteristics of a transaction?

atomic, serializable, durable

atomic

all operations either happen or they do not (no partial operations)

serialiable

transactions appear to happen one after the other

durable

once a transaction happens, it is recoverable and can survive crashes

how many level of RAID (redundant array of independent disks)?

0-5

raid level 0

striping, no redundancy

striping, no redundancy

uses block-level striping across multiple disks

raid level 0 striping, no redundancy pro and cons

pros: high performance

cons: no redundancy—disk failure results in total data loss

raid level 1

mirrored disks

mirrored disks

each disk has a mirror (duplicate copy)

raid level 1 mirrored disks pros and cons

pros:

• reliability is doubled (can survive a single disk failure)

• faster rea access (can read from either copy)

cons:

• slower write (must write to both disks)

• expensive and inefficient (requires double the storage)

raid level 2

memory-style ECC - Error Correction Code

memory-style ECC - Error Correction Code

some disks store ECC (error correction code) instead of data

raid level 2 ECC pros and cons

pros:

• more efficient thatn full mirroring

• can correct errors, not just detect them

cons:

• still fairly inefficient compared to other RAID levels

raid level 3

bit-interleaved parity

bit-interleaved parity

used bit-level striping across disks, with one parity disk storing error correction data

raid level 3 bit-interleaved parity pros and cons

pros:

• more efficient than RAID 1 and 2

cons:

• the parity disk does not contribute to bandwidth, limiting performance

raid level 4

block-interleaved parity

block-interleaved parity

similar to RAID 3, but data is interleaved in blocks instead of bits

raid level 4 block-interleaved parity pros and cons

pros:

• more efficient data access than RAID 3

cons:

• the parity disk can become a bottleneck

• small writes are inefficient

raid level 5

block-interleaved distributed-parity

block-interleaved distributed-parity

spreads parity data evenly across all disks instead of a single parity disk

raid level 5 block-interleaved distributed-parity

pros:

• no single parity disk bottleneck

• all disks contribute to read performance

cons:

• small writes require 4 I/Os, reducing efficiency

security

policy of authorizing accesses

protection

the actual mechanisms implemented to enforce the specialized policy

access matrix

describes who can do what

access control list (ACL)

security mechanism that stores all permissions for all users with each object

what is the analogy used for access control list (ACL)?

ACLs are like a guard at a door checking a list of people allowed to enter

how does an AC: control access?`

checks if a user’s permission match those stored for an object before granting access

how does UNIX implement access control?

UNIX specifies file permissions based on three categories:

1. owner (user)

2. group

3. world (everyone else)

capability list

stores all the objects that a process can access, defining its permissions

what is a common analogy for a capability list?

keys — having a key means you have the right to access the corresponding object.

In the key analogy for capability lists, what does owning a key represent?

Having the right to access a resource (like an object or memory page).

What is an example of a capability list in operating systems?

Page tables

How do page tables represent a capability list?

Each process has a list of memory pages it is allowed to access.

What are the three main goals of security?

Data confidentiality, data integrity, and system availability.

What is the goal of data confidentiality in security?

Ensuring that secret data remains secret and is not accessed by unauthorized users.

What is the goal of data integrity in security?

Preventing unauthorized users from modifying data.

What does system availability mean in terms of security?

Ensuring that no one can make the system unusable or deny access to legitimate users.

What are the three main components of security?

Authentication, Authorization, and Enforcement.

What is the purpose of authentication in security?

To determine who the user is.

What does authorization do in a security system?

It determines who is allowed to do what.

What is the role of enforcement in security?

It ensures users can only do what they are allowed to do.

In the Kerberos protocol, what does Key(xy) represent?

A shared secret key needed for secure communication between entities x and y.

What is the main benefit of public key encryption?

It separates authentication from secrecy.

What two keys are used in public key encryption?

A public key and a private key.