QMCS 360 Class Notes # 18	Dr. Rick Smith Quantitative Methods and Computer Science
Dr. Smith Home | Research | Classes | Blackboard | Cryptosmith | QMCS Home | UST A-Z | UST Home last update: Thursday, November 17, 2005

Status on scheduling software

Deadline for spring CIG grants

Outline

File System Requirements

• Typical requirements

• • Provide a way to "name" collections of disk blocks ("files")

• • Keep track of free space on the hard drive

• Possible requirements

• • Simplicity of implementation

• • Scalability options

• • • Hard drive size

• • • File size

• • • Range of file names

• • Hierarchical name space

• • Name space linking

• • Redundancy and recoverability

• Internal file structure possibilities

• • Simple sequential

• • Block oriented addressing (based on hard drive capabilities)

• • Record oriented addressing (gets complicated)

Examples

• FORTH

• • Memorized disk structure

• • First few blocks set aside for binary image of the operating system

• • Remaining blocks are readable ASCII text

• • Users access disk blocks numerically

• RT-11

• • Flat file structure - no hierarchy

• • Directory is a fixed size file at the start of the device

• • • Limited number of files in directory, based on the directory's allocated size

• • • Limited file name size based on directory structure

• • • Each file is a contiguous set of disk blocks

• • • Free space identified by directory entries with blank names

• • File size and hard drive size limited by offsets in the directory structure

• RAX

• • Free space management separated from file directory structure

• • Free space management

• • • Disk formatted into "data sets" and "space sets"

• • • "Space sets" are sets of specially formatted disk blocks allocated in groups

• • • Each space set has a pair of link fields separate from the data fields

• • • "Data sets" are virtual hard drives containing up to 65K "space sets"

• • • Each space set is part of a linked list of blocks (Figure 5-8)

• • • • Linked list of free blocks

• • • • Linked list of blocks in each file

• • • A given space set is addressed by a pair of numbers: (data set #, space set #)

• • File directory is a 2-level hierarchy

• • • File entry contains name, access permissions, size in # space sets, link to starting space set

• • Design supports sequential access but not direct access

• • Files may contain space sets from any data sets

• • Some peripheral notes

• • • Designed to let RAX files live "inside" a standard IBM file structure - itself too hard to use with a high capacity timesharing system

• • • Sequential access met requirements of the mid-70s academic computing environment

• • • Large user community shared a single file name space - collisions happened

• • • File names doubled as the names of executable programs - made Trojan horses really simple

• Classic Unix i-nodes

• • Like RAX, separates space management from file directory structure, except:

• • • True hierarchical directory structure

• • • Support for direct access

• • • Files don't span virtual/logical disk volumes

• • Space management - I-nodes

• • • Free and allocated chunks of disk space are tracked through i-nodes

• • • I-nodes maintained in a sequential area at start of hard drive

• • • Each i-node is of fixed size

• • • • Accessed by number, indexed into "table" at start of hard drive

• • • • Header indicates file size, permissions, # links (described later)

• • • • Rest of i-node is a list of blocks in the file, indexed by address

• • • • In larger files, each block address is "indirect" (Fig 5-10)

• • • • • single indirect = pointed block contains block addresses

• • • • • double indirect = pointed block is a single indirect block itself

• • • • • This approach provides best performance for small files, scalable for large files

• • • For free space - keep a linked list of single indirect blocks

• • Directory

• • • Each directory entry associates a file name with an i-node (indicated by number)

• • • Directory entry has 2 parts

• • • • I-node number

• • • • String indicating file name

• • • A directory entry can point to another directory - build hierarchy that way (Figure 5-7)

• • • A device's directory always starts with the file in i-node 2 - the "root" directory

• • • Linking - 2 or more directory entries can point to a single i-node

• • • • I-node must keep a count of links

• • • • Semantic distiction from "symbolic" links

• • • • • "Hard" link points to an allocated set of disk blocks

• • • • • • If you delete and recreate with same name, an old link is no longer valid

• • • • • • New file probably has a new i-node number

• • • • • "Soft" or symbolic link points to a file name regardless of location

• • • • • • Link is still valid if you delete and recreate file with same name

• • Multiple devices, one directory

• • • When you mount another file system, you attach it to the existing tree at some node at or below the root

• LOCK

• • Critical requirement - multilevel security

• • Yielded flat file system with randomly assigned names (serial numbers)

• • For Unix interoperability - implemented Unix directories that linked to flat file names, similar to i-nodes

• • Unix directory access was restricted according to multilevel access policy