1.7 I/o devices and file systems  (Page 4/9)

Modern file systems must address four general problems:

• Disk Management: efficient use of disk space, fast access to files, sharing of space between several users.
• Naming: how do users select files?
• Protection: all users are not equal.
• Reliability: information must last safely for long periods of time.

Disk Management: how should the disk sectors be used to represent the blocks of a file? The structure used to describe which sectorsrepresent a file is called the file descriptor.

Contiguous allocation: allocate files like segmented memory (give each disk sector a number from 0 up). Keep a free list of unusedareas of the disk. When creating a file, make the user specify its length, allocate all the space at once. Descriptor contains location and size.

• Advantages: easy access, both sequential and random. Simple. Few seeks.
• Drawbacks: horrible fragmentation will preclude large files, hard to predict needs. With interleaved user requests, still cannot eliminate allseeks.

Linked files: In file descriptor, just keep pointer to first block. In each block of file keep pointer to next block. It can alsokeep a linked list of free blocks for the free list.

• Advantages: files can be extended, no fragmentation problems. Sequential access is easy: just chase links.
• Drawbacks: random access is virtually impossible. Lots of seeking, even in sequential access.
• Example: FAT (MSDOS) file system.

Array of block pointers: file maximum length must be declared when it is created. Allocate an array to hold pointers to all theblocks, but do not allocate the blocks. Then fill in the pointers dynamically using a free list.

• Advantages: not as much space wasted by overpredicting, both sequential and random accesses are easy.
• Drawbacks: still have to set maximum file size, and there will be lots of seeks.

DOS FAT allocation table: A single File Allocation Table (FAT) that combines free list info and file allocation info. In filedescriptor, keep pointer to first block. A FAT table entry contains either (1) the block number of the next block in the file, (2) a distinguished "end offile" (eof) value, or (3) a distinguished "free" value.

• Advantages/Disadvantages: similar to those mentioned above for linked file.

None of these is a very good solution: what is the answer? First, and MOST IMPORTANT: understand the application. How are filesystems used?

• Most files are small.
• Much of the disk is allocated to large files.
• Many of the I/O's are made to large files.

Thus, the per-file cost must be low, but the performance of large files must be good. File systems must allow reasonably fastrandom access, extensibility.

Unix and demos disk allocation

Storage Management: For a given file, how the does OS find the blocks contained in that file? The data structure that decribes thecontents of file is generically called a file descriptor. We will see several other names, as we study about file systems.

The file descriptor information has to be stored on disk, so it will stay around even when the OS does not.