Disk Scheduling: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
n: number of requests | $n$: number of requests | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 16: | Line 16: | ||
|- | |- | ||
| [[FCFS (Disk Scheduling Disk Scheduling)|FCFS]] || 1979 || $O(n)$ || $O({1})$ | | [[FCFS (Disk Scheduling Disk Scheduling)|FCFS]] || 1979 || $O(n)$ || $O({1})$ || Exact || Deterministic || | ||
|- | |- | ||
| [[SSTF (Disk Scheduling Disk Scheduling)|SSTF]] || 1979 || $O(n | | [[SSTF (Disk Scheduling Disk Scheduling)|SSTF]] || 1979 || $O(n \log n)$ with binary tree || $O(n)$ || Exact || Deterministic || [https://www.geeksforgeeks.org/program-for-sstf-disk-scheduling-algorithm/?ref=lbp Space] | ||
|- | |- | ||
| [[SCAN (Disk Scheduling Disk Scheduling)|SCAN]] || 1979 || $O(n | | [[SCAN (Disk Scheduling Disk Scheduling)|SCAN]] || 1979 || $O(n \log n)$ || $O(n)$ || Exact || Deterministic || [https://www.geeksforgeeks.org/scan-elevator-disk-scheduling-algorithms/?ref=lbp Space] | ||
|- | |- | ||
| [[LOOK (Disk Scheduling Disk Scheduling)|LOOK]] || 1979 || $O(n | | [[LOOK (Disk Scheduling Disk Scheduling)|LOOK]] || 1979 || $O(n \log n)$ || $O(n)$ || Exact || Deterministic || | ||
|- | |- | ||
| [[C-SCAN (Disk Scheduling Disk Scheduling)|C-SCAN]] || 1979 || $O(n | | [[C-SCAN (Disk Scheduling Disk Scheduling)|C-SCAN]] || 1979 || $O(n \log n)$ || $O(n)$ || Exact || Deterministic || | ||
|- | |- | ||
| [[C-LOOK (Disk Scheduling Disk Scheduling)|C-LOOK]] || 1979 || $O(n | | [[C-LOOK (Disk Scheduling Disk Scheduling)|C-LOOK]] || 1979 || $O(n \log n)$ || $O(n)$ || Exact || Deterministic || | ||
|- | |- | ||
|} | |} | ||
Revision as of 08:22, 10 April 2023
Description
When disk requests arrive at the disk device, they are queued for service and a disk scheduling algorithm is used to decide which of a waiting queue of disk requests to serve next.
Parameters
$n$: number of requests
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| FCFS | 1979 | $O(n)$ | $O({1})$ | Exact | Deterministic | |
| SSTF | 1979 | $O(n \log n)$ with binary tree | $O(n)$ | Exact | Deterministic | Space |
| SCAN | 1979 | $O(n \log n)$ | $O(n)$ | Exact | Deterministic | Space |
| LOOK | 1979 | $O(n \log n)$ | $O(n)$ | Exact | Deterministic | |
| C-SCAN | 1979 | $O(n \log n)$ | $O(n)$ | Exact | Deterministic | |
| C-LOOK | 1979 | $O(n \log n)$ | $O(n)$ | Exact | Deterministic |
Time Complexity Graph
Space Complexity Graph
Time-Space Tradeoff
