diff options
| -rw-r--r-- | doc/assignment3.md | 67 |
1 files changed, 67 insertions, 0 deletions
diff --git a/doc/assignment3.md b/doc/assignment3.md index 07a3e87..4d9e8e8 100644 --- a/doc/assignment3.md +++ b/doc/assignment3.md @@ -199,9 +199,76 @@ Assignment 3 1. To create a new file, an application program calls on the logical file system. Describe the steps the logical file system takes to create a file. + Two steps are necessary to create a file. + 1. Find space in the file system for the file. 1. Create an entry for the new file in the directory. + There are different type of allocation methods such as contiguous allocation, + linked allocation, and indexed allocation. + + Contiguous allocation requires that each file occupy a set of contiguous + blocks on the disk. Disk addresses define a linear ordering on the disk. + With this ordering, assuming that only one job is accessing the disk, + accessing block `b + 1` after block `b` normally requires no head movement. + When head movement is needed the head need only move from one track to the + next. Thus, the number of disk seeks required for accessing contiguously + allocated files is minimal, as is seek time when a seek is finally needed. + The directory entry for each file indicates the address of the starting + block and the length of the area allocated for this file. + + Accessing a file that has been allocated contiguously is easy. + For sequential access, the file system remembers the disk address + of the last block referenced and, when necessary, reads the next block. + + Contiguous allocation has some problems, however. One difficulty is finding + space for a new file. The system chosen to manage free space determines + how this task is accomplished. This problem can be seen as a particular + application of the general dynamic storage-allocation problem. + + Linked allocation solves all problems of contiguous allocation. With linked + allocation, each file is a linked list of disk blocks; the disk blocks may + be scattered anywhere on the disk. The directory contains a pointer to the + first and last blocks of the file. Each block contains a pointer to the + next block. + + To create a new file, we simply create a new entry in the directory. + With linked allocation, each directory entry has a pointer to the first + disk block of the file. There is no external fragmentation with linked + allocation, and any free block on the free-space list can be used to + satisfy a request. A file can continue to grow as long as free blocks + are available. Consequently, it is never necessary to compact disk space. + + Linked allocation does have disadvantages, however. The major problem is + that it can be used effectively only for sequential-access files. To find + the ith block of a file, we must start at the beginning of that file and + follow the pointers until we get to the ith block. Each access to a pointer + requires a disk read, and some require a disk seek. Consequently, it is + inefficient to support a direct-access capability for linked-allocation + files. + + Another disadvantage is the space required for the pointers. If a pointer + requires 4 bytes out of a 512-byte block, then 0.78 percent of the disk is + being used for pointers, rather than for information. Each file requires + slightly more space than it would otherwise. + + Linked allocation cannot support efficient direct access, since the + pointers to the blocks are scattered with the blocks themselves all over + the disk and must be retrieved in order. Indexed allocation solves this + problem by brining all the pointers together into one location: + the index block. + + Each file has its own index block, which is an array of disk-block addresses. + The ith entry in the index block points to the ith block of the file. + The directory contains the address of the index block. To find and read the + ith block, we use the pointer in the ith index-block entry. + + Indexed allocation supports direct access, without suffering from external + fragmentation, because any free block on the disk can satisfy a request for + more space. Indexed allocation does suffer from wasted space, however. The + pointer overhead of the index block is generally greater than the pointer + overhead of linked allocation. + 1. How is a hash table superior to a simple linear list structure? What issue must be handled by hash table implementation? A hash table allows for `O(1)` lookup for directory entries by using a hash function with a low collision rate. |