|
File Structure None
|
tarix | 07.11.2018 | ölçüsü | 2,61 Mb. | | #78616 |
|
None: - File can be a sequence of words or bytes
Simple record structure: - Lines
- Fixed Length
- Variable Length
Complex Structure: - Formatted documents
- Relocatable load files
Who decides?
File Access Methods Sequential Access - Based on a magnetic tape model
- read next, write next
- reset
Direct Access - Based on fixed length logical records
- read n, write n
- position to n
- relative or absolute block numbers
Directory Structure Collection of nodes containing information on all files
Information in a Device Directory File name: File Type: Address: Current Length Maximum Length Date Last accessed (for archiving) Date Last updated (for dumping) Owner ID Protection information
Directory Operations Search for a file Create a file Delete a file List a directory Rename a file Traverse the file system
Objectives for a Directory System Make it efficient Make file (and directory) naming convenient - Allow 2 users to have the same name for different files
- Allow the same file to have more than 1 name
Allow logical grouping of files - All word processing files together
- All c++ files together
- etc.
Alternative Directory Structures Single-Level Directory Issues:
Alternative Directory Structures
Tree-Structured Directory
File System Structure A data structure on a disk that holds files Disk Storage attributes: - Allows direct access to any given block of information
- Supports re-writing in place (copy block, modify, rewrite)
Organized in Layers: - Application Programs
- Logical file system
- file-organization module
- basic file system
- I/O control
- devices
File System Organization Devices - Peripheral equipment- disk drives, tapes, etc.
I/O Control Basic File System - Requires knowledge of physical device (track, cylinder, head, etc.)
- Manages data transfer at block level (buffering, placement)
File System Organization File-organization Module - Maps logical block structure of file to physical block structure of disk
- Includes free space manager
Logical file system - Manages file directory information
- Provides security, protection
Applications - Maintains basic data about the file
- Allows users to access file information
File System Structure Access to File - file control block (generic)
- file descriptor (UNIX)
- file handle (Windows)
File System Requirements - boot mechanism
- file system information
- file information
- file data
Allocation Methods Contiguous Allocation Each file occupies a set of contiguous blocks on the disk. - May be increased using file extensions
Advantages: - Simple to implement
- Good for random access of data
Disadvantages - Files cannot grow
- Wastes space
Contiguous Allocation
Allocation Methods Linked Allocation Each file consists of a linked list of disk blocks. Advantages: - Simple to use (only need a starting address)
- Good use of free space
Disadvantages: - Random Access is difficult
Linked Allocation
Linked Allocation
Allocation Methods Indexed Allocation Collect all block pointers into an index block. Advantages: - Random Access is easy
- No external fragmentation
Disadvantages
Indexed Allocation
Indexed Allocation
UNIX File System File Types Regular File Directory Block-oriented Device Character-oriented Device Symbolic Link
UNIX File Ownership
open -- read -- write -- close fdesc = open (*filename, r / w / a / +); n = read (fdesc, buff, 24); n = write (fdesc, buff, 24); lseek (fdesc, 100L, L_SET); (L_SET, L_CUR, L_END) close (fdesc);
Concurrent File Access From separate processes - OPEN generates a new file descriptor.
- Allows independent access to the same file.
- No inherent blocking in access
From parent / child processes - fork duplicates all active file descriptors.
- all processes access a common “current” pointer
File locking
UNIX File Sharing - unrelated processes -
UNIX File Sharing - related processes -
UNIX i-node
UNIX i-node
UNIX i-node
I-node File Sizes
Disk Drive Layout (simplified)
Sample filesystem: Creating the directory “testdir”
Sample filesystem: Creating the directory “testdir”
Sample filesystem: Creating the directory “testdir”
Sample filesystem: Creating the directory “testdir”
Sample filesystem: Creating the directory “testdir”
Sample filesystem after creating the directory “testdir”
Viewing directory structure ls –ai / ls –ai /home - 1730 .
- 2 . .
- :
- 199 rcotter
Linux File System Structure Linux uses a Virtual File System (VFS) - Defines a file object
- Provides an interface to manipulate that object
Designed around OO principles - File system object
- File object
- Inode object (index node)
Primary File System - ext2fs - Supports (or maps) several other systems (MSDOS, NFS (network drives), VFAT (W95), HPFS (OS/2), etc.
Virtual Filesystem A kernel software layer that handles all system calls related to a standard UNIX filesystem. Supports: - Disk-based filesystems
- IDE Hard drives (UNIX, LINUX, SMB, etc.)
- SCSI Hard drives
- floppy drives
- Network filesystems
- Special filesystems
VF Example inf = open (“/floppy/test”, O_RDONLY, 0); outf = open (“/tmp/test”, O_WRONLY|O_CREATE|O_TRUNC, 0600); do { cnt = read(inf, buf, 4096); write (outf, buf, cnt); } while (cnt); close (outf); close (inf);
Virtual file system Model Superblock object - metadata about a mounted filesystem
inode object - general information about a specific file
file object - information about process and open file interaction
dentry object - directory entry information
Virtual Filesystem and Processes
Ext2fs History Minux extfs ext2fs - 1994
Ext2fs Blocks 1k default 2k, 4k possible choice based on file sizes
Ext2fs Disk Data Structures Each Block Group contains: - A copy of the Super Block
- A copy of the group of block group descriptors
- A data block bitmap (for this group)
- An inode bitmap (for this group)
- A group of inodes (for this group)
- Data blocks
Disk Data Structures SuperBlock - Contains metadata about the block group
- # free blocks,
- # free inodes,
- block size,
- times (last mount, last write),
- check status,
- blocks to pre-allocate,
- alignments, etc. (~38 items)
Disk Data Structures Block Groups - Block group limited to 8 * block size by data block bitmap.
- 1k block limited to 8,192 blocks or 8 mbytes per block group. 4k block = 128 mbytes
- block numbers for bitmaps, start of tables, etc.
Disk Data Structures Inode Table - Inodes - 128 bytes
- File type and access rights
- owner
- length
- timestamps (last access, last change, etc.)
- hard links counter
- pointers to data blocks,
- etc.
Disk Data Structures Items cached in memory on filesystem mount - Superblock - always cached
- Group descriptor - always cached
- Block bitmap - fixed limit - most recent only
- Inode bitmap - fixed limit - most recent only
- Inode - dynamic
- Data block - dynamic
File Blocks Grouped Physically and logically Inodes distributed throughout disk Pre-allocation of free blocks to minimize frag.
Summary Features Fast Symbolic Links pre-allocation of data blocks file-updating strategy immutable files or append only files
Journal File Systems Designed to speed file system recovery from system crashes. Traditional systems use an fs recovery tool (e.g. fsck) to verify system integrity As file system grows, recovery time grows. Journal File Systems track changes in meta-data to allow rapid recovery from crashes
Journal File System Uses a version of a transaction log to track changes to file system directory records. If a system crash occurs, the transaction log can be reviewed back to a check point to verify any pending work (either undo or redo). For large systems, recovery time goes from hours or days to seconds.
Journal File System - Examples XFS - Commercial port by SGI (IRIX OS)
- Based on 64 bit system (ported to 32 bit)
- Supports large systems 2TB -> 9 million TB
- Uses B+trees for improved performance
- Journals file system meta-data
- Supports Quotas, ACLs.
- Supports filesystem extents (contiguous blocks)
Journal File System - Examples JFS - Commercial Port by IBM. Used in OS/2
- 64 bit system ported to 32 bits.
- Journal support of meta-data.
- System Size 2TB -> 32PB
- Built to scale on SMP architectures
- Uses B+trees for improved performance
- Supports use of extents.
Journal File System - Examples ReiserFS - Designed originally for Linux (32 bit system)
- Supports file systems to 2TB -> 16TB
- Journal support of meta-data
- Btree structure supports large file counts
- Supports block packing for small files
- No fixed inode allocation - more flexible.
Journal File System - Examples Ext3fs - Simple extension of ext2fs that adds journaling
- All virtual file system operations are journaled.
- Other limitations of ext2fs remain.
Journal File System - Examples ext4fs - Next generation of file system development, incorporating improvements and changes to ext3fs.
- Journalling filesystem
- Improvements is journal checksumming
- Larger file systems – 1 MTB (exabyte)
- Delayed block allocation, multi-block allocator
- Allows files to be written as contiguous sequences of blocks: improves read performance of streaming data files.
- Poses the risk of lost data if system crashes before data is written.
- Use of extents
- Large (<= 128 MB) contiguous physical blocks.
Free Space Management Bit Vector management One bit for each block Use bit manipulation commands to find free block - block size = 4096 = 2 12
- disk size = 1 gigabyte = 2 30
- bits = 2 (30-12) = 2 18 = 32k bytes
Free Space Management Bit vector (advantages): - Easy to find contiguous blocks
Bit vector (disadvantages): - Wastes space (bits allocated to unavailable blocks)
Issues: - Must keep bit vector on disk (reliability)
- Must keep bit vector in memory (speed)
- cannot allow memory != disk (memory = 1, disk = 0)
Free Space Management Linked List management - Use linked list to identify free space
Advantages: Disadvantages: - harder to identify contiguous space.
Issues: - Must protect pointer to free list
Free Space Management
Example File Systems CD-ROM - ISO 9660
- Rock Ridge
- Joliet
MS-DOS
Summary File Structures Directory Structures File System Implementation File System Management Example File Systems
Questions Two primary access methods are used to manage files. Discuss these two methods, including which types of physical devices each is normally associated with. What is the difference between a tree structured file directory and an acyclic graph directory? Please give an example Operating System used today that uses each. Discuss 3 ways in which files might be allocated to file stores (disks). What are the advantages or disadvantages of each? How might a file system manage its free space so that it can easily assign space for a new file when needed? Give at least 2 approaches. What can an OS designer to improve the efficiency of a file system? What factors should be considered? How do those affect the efficiency of the system? Discuss at least 2 mechanisms that might be used to ensure the recovery of information stored in a file system.
Dostları ilə paylaş: |
|
|