Computer Science | Binghamton University



Notes on File Systems – annotations to “File-System Implementation” slides by Silberschatz.

5/13/01-updated12/4/03+

These are commentary notes (annotations) used in the “File System Implementation” Silberschatz pdf notes (second set of notes posted on the website). These are not complete, they should be read in conjunction with the posted slides themselves. These comments are for material actually mentioned in class.

A file is a meaningful set of data to be stored on a non-volatile media: must be mapped to physical storage – typically a disk.

File control block: all the information about a file accessed on opening a file from the directory information and stored in the “Open File table” see below.

Directory Structure (Stallings Table 12.2, p. 537, and also p. 481 Bottom):

The directory maps symbolic names to logical or physical disk addresses. When the file is “opened”, the directory structure is searched for file information and copied to the “open file table”. The key information is a pointer to the file itself. The open file table is faster to access than the directory which must be searched. An index into this table to the directory information of the file which was opened (file control block) is returned to the user as a file descriptor in UNIX or a handle in some other OS’s. The index is faster to use than searching the original directory.

Layered architecture to file system implementation:

A typical but not unique possibility:

Application

Logical file system:

Use directory structure and symbolic names. Output is a logical block address

File organization module:

Translate Logical block address to physical address.

Free space management here

Basic file system

Issue generic high level commands to device driver (physical block addresses).

I/O Control

Device driver: data transfer between memory and disk. Input is high-level commands, and output is low-level hardware commands to device controller.

Device controller

Hardware interface between the device driver (OS) and the device itself.

Typically an adapter card in a bus on the mother board.

Low level logic controlling the device

Physical devise

Comments related to contiguous allocation:

Reference: p. 546, Stallings

Sequential and direct (random) access supported

Directory points to start of space and gives a size of file.

Wasteful use of space – same problem as in dynamic memory allocation for contiguous processes: external fragmentation. Need algorithms like best fit, worst fit, etc. Need for de-fragmentation – tedious processes

Advantage: fast with minimal seeks.

Pre-allocation usually results in over allocation and internal fragmentation if not all used. Sometimes “extents” are used to link in extra chunks of pre-allocated space when original used up.

Comments related to Linked allocation:

Solves external fragmentation problem.

Each physical block contains a pointer to the next block in addition to the data. Pointer not seen by the user – wasteful of space due to need for pointers.

Directory points to first block

No need to declare size of file.. File grows as long as there is free blocks on disk.

Disadvantage is it is slow due to having to follow pointers across tracks. Also pointer corruption can causer lost data. In the absence of FAT (see below) linked allocation cannot support efficient direct access.

Variation of Linked allocation: File Allocation Table (FAT) see below.

File-Allocation Table (FAT) – by N. Guydosh, modified 12/15/01

• This is an important variation of the “linked allocation” method, and is an important approach for PC users to understand.

• Used by DOS based systems and OS/2

• FAT is a section of the disk at the beginning of a partition

• The FAT has an entry for each disk block in the partition

• FAT itself is indexed by the block number of a block in a partition – the block may be allocated or unused.

• If the FAT entry corresponds to an unused block (not in any file) then the entry is 0 – the index still points to an unused block in the partition.

• If a FAT entry corresponds to an allocated block for some file, then its index is the next block in the file AND the next FAT entry. If this is the last block in the file, then it value would be a code for end of file.

• The directory entry for a file contains the block number of the first block in the file. It points to both this first data block in the file and the first entry in the FAT for this file. That is, this first entry contains the block number of the first (next) data block in the file, and also serves as the pointer to the first entry in the FAT for this file (has two roles).

• In general, the FAT is a linked list linked by the entries themselves. As with the pointer in the directory (above), an entry in the FAT serves two purposes: it points to the next FAT entry, while simultaneously pointing the next physical block on the disk. The index of this entry points to the “current” block associated with this entry. The FAT is sort of a map of the blocks making up the file it represents. The FAT chain terminates on a special “end of file” (EOF) entry.

• Combines file allocation and free-space management into one scheme.

• Unallocated (unlinked) entries in the FAT contain the index of zero.

• To add a block to a file, simple find the first zero entry, make the old EOF block point to the new block and also to the new entry which gets marked EOF.

• Since the fat is at the beginning of the partition, it is prone to excessive head movement in accessing blocks (between the FAT and the DATA), thus it is usually cached in memory to prevent head excessive head seeking.

• The FAT approach provides good random access and has the usual problems of an indexed approach – lost pointer problems, etc.

Reference: Silberschatz, “Operating System Concepts”, 6th ed. , pp. 425-426, and fig 12.7 (below) for an example.

[pic]

Comments related to Indexed allocation:

Rather than “chasing pointers” all over the disk as in linked allocation, put all pointers together into a single (or multiple) index block.

No external fragmentation and good random access, but inefficient use of space for small files – not all pointer locations in an index block get used.

For large files, use multiple index blocks: let the last pointer in an index block point to the next index block. Also multilevel index blocks used analogous to multilevel page tables in virtual memory. By adding levels, the number of index pointers could be made extremely large. See Silberschatz pp. 383-384.

Comments related UNIX I-Node scheme

Uses a mixture of direct index blocks and multi level blocks – see p. 555 Stallings.

Comments related Free-space management:

Bit map schemer:

A bit vector has a bit for every block on disk

Bit = 0 means it is occupied

Bit = 1 means it is free

Need ability to do bit level searching and processing to search the bit string for the first free block from left to right. Bit vector is many words.

Calculation of first free block # :

(#bits/word) * (# of leading zero words) + offset of 1st (high order) bit which is not 0

Also the maintaining of a “freelist” may be done. This is a linked list of free blocks. Pointers can be moved between freelist to allocated blocks and vice versa depending on the allocation scheme – works especially well with the linked allocation scheme. The text unjustifiably criticizes this method as inefficient due to the need for transverse the list. We should never have to transverse the list. As long as we have a pointer to the first block in the list, we need only to access the first block: Take the first block if you need a new block, or add a free block the head of the list.

Tracking of free blocks can also be done with linked index blocks much the same as was done for indexed file allocation. In addition, rather than managing individual blocks (or clusters), we could manage contiguous sequences of blocks, needing only the address of the first block in a sequence and a count of the number of blocks: a counting approach (page 432).

Efficiency and performance: see PPT slides for chapter 12.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download