10-File Systems

1 .Operating Systems 1 10. File Systems 10.1 Basic Functions of File Management 10.2 Hierarchical Model of a File System 10.3 User’s View of Files Logical File Organization Operations on Files 10.4 File Directories Hierarchical Organizations Operations on Directories Implementation 10.5 Basic File System Opening and Closing of Files 10.6 Physical Organization Methods Contiguous, Linked, Indexed Organization Management of Free Storage Space

2 .Operating Systems 2 Basic Functions of File Management Present logical (abstract) view of files and directories Accessing a disk is very complicated: 2D or 3D structure, track/surface/sector, seek, rotation, … Hide complexity of hardware devices Facilitate efficient use of storage devices Optimize access, e.g., to disk Support sharing Files persist even when owner/creator is not currently active (unlike main memory) Key issue: Provide protection (control access)

3 .Operating Systems 3 Hierarchical Model of FS Physical device organization: m ap file data to disk blocks Directory management : map logical name to unique Id, file descriptor Basic file system : o pen/close files

4 .Operating Systems 4 What is a File: User’s View File name and type Valid name Number of characters Lower vs upper case, illegal characters Extension Tied to type of file Used by applications File type recorded in header Cannot be changed (even when extension changes) Basic types: text, object, load file, directory Application-specific types, e.g., .doc, . ps , .html

5 .Operating Systems 5 User View of Files Logical file organization Most common: byte stream Fixed-size or variable-size records Addressed Implicitly (sequential access to next record) Explicitly by position (record#) or key a) Fixed Length Record b) Variable Length Record c) Fixed Length with Key d) Variable Length with Key

6 .Operating Systems 6 Other File Attributes Ownership Size Use t ime of creation, last access, last modification Disposition p ermanent or temporary Protection w ho can access and what type of access Location b locks of data on disk where file is stored i mportant for performance n ot of interest to most users

7 .Operating Systems 7 Operations on Files Create/Delete Open/Close Read/Write (sequential or direct) Seek/Rewind ( sequential) Copy (physical or just link) Rename Change protection Get properties Each involves parts of Directory Management, BFS, or Device Organization GUI is built on top of these functions

8 .Operations on Files Operating Systems 8

9 .Operating Systems 9 Directory Management Directory : hierarchical structure to keep track of files Main issues: Shape of data structure (e.g. tree , shortcuts, …) What info to keep about files Where to keep it? ( in directory ?) How to organize entries for efficiency?

10 .Operating Systems 10 File Directories Tree-structured Simple search, insert, delete operations Sharing is asymmetric (only one parent)

11 .Operating Systems 11 File Directories DAG-structured Symmetric s haring, but … What are semantics of delete ? Any parent can remove file: dangling references Only last parent can remove it: Need reference count

12 .Operating Systems 12 File Directories DAG-structured Allow cycles ? If cycles are allowed: Search is difficult (infinite loops) Deletion needs garbage collection (reference count not enough)

13 .Operating Systems 13 File Directories Symbolic links (shortcuts) Compromise to allow sharing but avoid cycles For read/write access: Symbolic link is the same as actual link For deletion : Only symbolic link is deleted

14 .Operating Systems 14 File Directories How to uniquely name a file in the hierarchy? Path names Concatenated local names with delimiter: ( . or / or \ ) Absolute path name: start with root ( / ) Relative path name: Start with current directory ( . ) Notation to move upward in hierarchy ( .. )

15 .Practice navigation Shortest absolute path for F4, F8 Relative paths when D3 is working directory Relative paths when D7 is working directory Repeat without symbolic links Operating Systems 15

16 .Operating Systems 16 Operations on File Directories GUI vs commands Create/delete List: sorting, wild cards, recursion, information shown Change (current, working) directory Move Rename Change protection Create/delete link (symbolic) Find/search routines

17 .Operating Systems 17 Implementation of Directories What information to keep in each entry All descriptive information Directory can become very large Searches are difficult/slow Only symbolic name and pointer to descriptor Needs an extra disk access to descriptor Variable name length? Example : BFS

18 .Operating Systems 18 Implementation of Directories How to organize entries within directory Fixed-size entries: use array of slots Variable-size entries: use linked list (like BFS) Size of directory : f ixed or expanding Example: Windows 2000 w hen # of entries exceeds directory size, expand using B + - trees

19 .Revisit file operations Assume: descriptors are in a dedicated area directory entries have name and pointer only create find free descriptor, enter attributes find free slot in directory, enter name/pointer rename search directory, change name delete search directory, free entry, descriptor, and data blocks copy l ike create, then find and copy contents of file change protection search directory, change entry Operating Systems 19

20 .Operating Systems 20 Basic File System Open/Close files Retrieve and set up information for efficient access: get file descriptor manage open file table File descriptor ( i-node in Unix) Owner id File type Protection information Mapping to physical disk blocks Time of creation, last use, last modification Reference counter

21 .Operating Systems 21 Basic File System Open File Table (OFT) keeps track of currently open files o pen command: Search directory for given file Verify access rights Allocate OFT entry Allocate read/write buffers Fill in OFT entry Initialization (e.g., current position) Information from descriptor (e.g. file length, disk location) Pointers to allocated buffers Return OFT index

22 .Operating Systems 22 Basic File System c lose command: Flush modified buffers to disk Release buffers Update file descriptor file length, disk location, usage information Free OFT entry

23 .Operating Systems 23 Revisit file operations read command assume file is open for sequential access buffered read: current block kept in r/w buffer copy from buffer to memory until: desired count or end of file is reached: update current position, return status or end of buffer is reached: write the buffer to disk (if modified) read the next block continue copying u nbufered read: read the entire block containing the needed data from disk

24 .Operating Systems 24 Revisit file operations write command (buffered) write into buffer when full, write buffer to disk if next block does not exist (file is expanding): allocate new block update file descriptor update bit map (free space on disk) update file length in descriptor seek command set current position as specified by parameter read block containing current position into buffer rewind command analogous to seek but position is zero

25 .Operating Systems 25 Basic File System Example: Unix Unbuffered access fd =open( name,rw ,…) stat=read( fd,mem,n ) stat=write( fd,mem,n ) Buffered access fp = fopen ( name,rwa ) c= readc ( fp ) // read one char

26 .Operating Systems 26 Physical Organization Methods Contiguous organization Simple implementation Fast sequential access (minimal arm movement) Insert/delete is difficult How much space to allocate initially External fragmentation

27 .Operating Systems 27 Physical Organization Methods Linked Organization Simple insert/delete, no external fragmentation Sequential access less efficient (seek latency) Direct access not possible Poor reliability (when chain breaks)

28 .Operating Systems 28 Physical Organization Methods Linked Variation 1: Keep pointers segregated May be cached Linked Variation 2: Link sequences of adjacent blocks, rather than individual blocks

29 .Operating Systems 29 Physical Organization Methods Indexed Organization Index table: sequential list of records Simplest implementation: keep index list in descriptor Insert/delete is easy Sequential and direct access is efficient Drawback: file size limited by number of index entries