read about disk-scheduling algorithms

1 files changed, 19 insertions, 1 deletions

diff --git a/doc/assignment3.md b/doc/assignment3.md
index 0ed297a..5ae1f59 100644
--- a/doc/assignment3.md
+++ b/doc/assignment3.md
@@ -185,9 +185,27 @@ Your answer for each question should be about 150 words. (100 marks total)
 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. (8 marks)
   1. Find space in the file system for the file.
   1. Create an entry for the new file in the directory.
+
 1. How is a hash table superior to a simple linear list structure? What issue must be handled by hash table implementation? (8 marks)
 
-Hash collisions
+  A hash table allows for `O(1)` lookup for directory entries by using a hash function with a low collision rate.
+  A collision occurs when two different value produce the same hash code.
+  When collisions occur hash table implementations usually fallback to using a form of chaining
+  or open addressing. Chaining will typically store collisions as some form of list such as a linked list.
+  Open addressing will use a form of probing to find a starting slot to search from until it finds a match.
+  In both of these forms the # of entries to evaluate is less than a full linear scan unless a poor quality hash function
+  is used.
+
+  A linear scan will start from the start of a list and seek through the list to find a match.
+  If the list is stored in a sorted form or as a balanced binary search tree then a
+  linear scan has a best case search time of `O(logn)` (base 2).
+  If the data cannot be sorted and/or stored in a binary search tree then a linear scan can have a worst case of `O(n)` which can be
+  much slower for larger file systems.
+
+  A hash table is superior due to the constant time lookup for directory entries with a good quality hash function.
+  Using a hash function will require more CPU but reduces the # of I/O operations needed against the disk to find
+  the desired inode.
+
 1. What are the factors influencing the selection of a disk-scheduling algorithm? (8 marks)
 1. Explain the disadvantage(s) of the SSTF scheduling algorithm. (8 marks)
 1. Explain the concepts of a bus and a daisy chain. Indicate how these concepts are related. (8 marks)