Commit cc49b48

@@ -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.