diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/10.md | 75 | ||||
| -rw-r--r-- | doc/assignment3.md | 1 |
2 files changed, 76 insertions, 0 deletions
@@ -173,3 +173,78 @@ cylinders_queue = [98, 183, 37, 122, 14, 124, 65, 67] 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. + +### Selecting a Disk-Scheduling Algorithm + +How the fuck do we choose the best one? + +SSTF is common and has natural appeal because it increases performance over FCFS. +SCAN and C-SCAN perform better for systems that place a heavy load on the disk, +because they are less likely to cause a starvation problem. + +For any particular list of requests, we can define an optimal order of retrieval, +but the computation needed to find an optimal schedule may not justify the savings +over SSTF or SCAN. + +With any scheduling algorithm performance depends heavily on the number and types of +requests. + +E.g. + +If the queue usually has just one outstanding request. Then all scheduling algorithms +behave the same, because they have only one choice of where to move the disk head; +they all behave like FCFS scheduling. + +Requests for device service can be greatly influenced by the file-allocation method. +A program reading a contiguously allocated file will generate several requests that +are close together on disk, resulting in limited head movement. + +A linked or indexed file may include blocks that are widely scattered on the disk, +resulting in greater head movement. + +The location of directories and index blocks is also important. +Since every file must be opened to be used, and opening a file requires searching +the directory structure, the directories will be accessed frequently. + +Suppose that a directory entry is on the first cylinder and a file's data are +on the final cylinder. In this case, the disk head has to move the entire width +of the disk. + +If the directory entry were on the middle cylinder, the head would have to move +only one-half the width. Caching the directories and index blocks in main +memory can also help to reduce disk-arm movement, particularly for read +requests. + +Because of these complexities, the disk-scheduling algorithm should be written +as a separate module of the operating system, so that it can be replaced +with a different algorithm if necessary. Either SSTF or LOOK is a reasonable +choice for the default algorithms. + +The scheduling algorithms described here consider only the seek distances. + +For modern disks, the rotational latency can be nearly as large as the +average seek time. It is difficult for the operating system to schedule for +improved rotational latency because modern disks do not disclose the +physical location of logical blocks. Disk manufacturers have been alleviating +this problem by implementing disk-scheduling algorithms in the controller +hardware built into the disk drive. + +If the operating system sends a batch of requests to the controller, +the controller can queue them and then schedule them to improve both +the seek time and the rotational latency. + +If I/O performance were the only consideration, the operating system would +gladly turn over the responsibility of disk scheduling to the disk hardware. + +In practice the OS may have other constraints on the service order for requests. + +Demand paging may take priority over application I/O and writes are more urgent +than reads if the cache is running out of free pages. +It may be desirable to guarantee the order of a set of disk writes to make the +file system robust int he face of a system crash. +What could happen if the operating system allocated a disk page to a file and +the application wrote data into that page before the operating system had +a chance to flush the file system metadata block to disk. +To accommodate such requirements an operating system may choose to do its own +disk scheduling and to spoon-feed the requests to the disk controller, one by +one, for some type of I/O. diff --git a/doc/assignment3.md b/doc/assignment3.md index 5ae1f59..1864f70 100644 --- a/doc/assignment3.md +++ b/doc/assignment3.md @@ -208,6 +208,7 @@ Your answer for each question should be about 150 words. (100 marks total) 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) + Starvation 1. Explain the concepts of a bus and a daisy chain. Indicate how these concepts are related. (8 marks) 1. What are the three reasons that buffering is performed? (6 marks) |