Commit dcb2fda
Changed files (2)
doc
doc/10.md
@@ -0,0 +1,175 @@
+
+## Disk Scheduling
+
+One of the responsibilities of the operating system is to use the hardware efficiently.
+For disks this means having fast access time and large disk bandwidth.
+For magnetic disks, the access time has two major components.
+
+The `seek time` is the time for the disk arm to move the heads to the cylinder
+containing the desired sector.
+
+The `rotational latency` is the additional time for the disk to rotate the
+desired sector to the disk head. The disk `bandwidth` is the total number
+of bytes transferred, divided by the total time between the first request
+for service and the completion of the last transfer.
+
+We can improve the access time and bandwidth by managing the order in which
+disk I/O requests are serviced.
+
+Whenever a process needs I/O to or from the disk, it issues a system call to
+the OS. The request specifies several pieces of information:
+
+* Whether this operation is input or output
+* What the disk address for the transfer is
+* What the memory address for the transfer is
+* What the number of sectors to be transferred is
+
+
+If the desired disk drive and controller are available, the request can be
+serviced immediately. If the drive or controller is busy, any new requests for
+service will be placed in the queue of pending requests for that drive.
+
+For a multiprogramming system with many processes, the disk queue may often
+have several pending requests. Thus, when one request is completed, the OS
+chooses which pending request to service next. How does the OS make this
+choice? Any one of several disk scheduling algorithm can be used.
+
+### First Come, First Served (FCFS) Scheduling
+
+The simplest form of disk scheduling is the first-come, first-served (FCFS) algorithm.
+The algorithm is intrinsically fair, but it generally does not provide the
+fastest service.
+
+Example:
+
+```plaintext
+Queue for I/O to blocks on cylinders:
+
+cylinders_queue = [98, 183, 37, 122, 14, 124, 65, 67]
+
+ HEAD
+ |
+ V
+ 0 14 37 53 65 67 98 122 124 183 199
+ |-----|--------|------|--|--|------------|---|---|-----------------------|-------|
+ 01| x
+ 02| x
+ 03| x
+ 04| x
+ 05| x
+ 06| x
+ 07| x
+ 08| x
+ 09| x
+```
+
+This produces a total of head movements of `640` cylinders.
+The swing from 122 to 14 back to 124 shows the waste.
+
+### Shortest Seek Time First (SSTF) Scheduling
+
+It seems reasonable to service all the requests close to the current head
+position before moving the head far away to service other requests.
+This assumption is the basis for the `shortest-seek-time-first` algorithm
+
+The SSTF algorithm selects the request with the least seek time from the
+current head position. i.e. it chooses the next pending request closest to the
+current HEAD position.
+
+```plaintext
+Queue for I/O to blocks on cylinders:
+
+cylinders_queue = [98, 183, 37, 122, 14, 124, 65, 67]
+
+ HEAD
+ |
+ V
+ 0 14 37 53 65 67 98 122 124 183 199
+ |-----|--------|------|--|--|------------|---|---|-----------------------|-------|
+ 01| x
+ 02| x
+ 03| x
+ 04| x
+ 05| x
+ 06| x
+ 07| x
+ 08| x
+ 09| x
+```
+
+This results in a total head movements of `236`.
+
+SSTF scheduling is a form of shortest-job-first (SJF) scheduling.
+This may cause starvation of some requests.
+Although, this algorithm is better than FCFS it is still not optimal.
+
+### SCAN/LOOK Scheduling
+
+In the SCAN algorithm, the disk arm starts at one end of the disk and
+moves toward the other end, servicing requests as it reaches each
+cylinder, until it gets to the other end of the disk. At the other
+end the direction of head movement is reversed and servicing continues.
+The head continuously scans back and forth across the disk.
+
+This is sometimes called the `elevator algorithm`, since the arm behaves
+just like an elevator in a building. First servicing all the requests
+going up and then reversing to service requests going down.
+
+```plaintext
+Queue for I/O to blocks on cylinders:
+
+cylinders_queue = [98, 183, 37, 122, 14, 124, 65, 67]
+
+ HEAD
+ |
+ V
+ 0 14 37 53 65 67 98 122 124 183 199
+ |-----|--------|------|--|--|------------|---|---|-----------------------|-------|
+ 01| x
+ 02| x
+ 03| x
+ 04| x
+ 05| x
+ 06| x
+ 07| x
+ 08| x
+ 09| x
+```
+
+SCAN will actually go to 0 and the end. LOOK will check to see if it can switch
+to the other direction instead of going to the end if it doesn't need to.
+
+### C-SCAN/C-LOOK Scheduling
+
+Circular Scan (C-Scan) scheduling is a variant of SCAN designed to provide a more uniform
+wait time. Like SCAN, C-SCAN moves the head from one end to another servicing requests
+along the way.
+When the head reaches the other end it immediately returns to the beginning of the disk
+without servicing any requests on the return trip.
+This essentially treats the disk as a cylinder list that wraps around from the final cylinder
+to the first one.
+
+```plaintext
+Queue for I/O to blocks on cylinders:
+
+cylinders_queue = [98, 183, 37, 122, 14, 124, 65, 67]
+
+ HEAD
+ |
+ V
+ 0 14 37 53 65 67 98 122 124 183 199
+ |-----|--------|------|--|--|------------|---|---|-----------------------|-------|
+ 01| x
+ 02| x
+ 03| x
+ 04| x
+ 05| x
+ 06| x
+ 07| x
+ 08| x
+ 09| x
+```
+
+C-SCAN will actually go back to 0 once it reaches the end.
+C-LOOK will check to see what the next smallest cylinder is when it reaches the
+max cylinder in the queue.
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)