Disk Scheduling: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Problem Description== File systems must be accessed in an efficient manner, especially with hard drives, which are the slowest part of a computer. As a computer deals with multiple processes over a period of time, a list of requests to access the disk builds up. For efficiency purposes, all requests (from all processes) are aggregated together. The technique that the operating system uses to determine which requests to satisfy first is called disk scheduling. == Bou...") |
No edit summary |
||
| (6 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== | {{DISPLAYTITLE:Disk Scheduling (Disk Scheduling)}} | ||
== 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 == | ||
{| class="wikitable" style="text-align:center;" width="100%" | |||
{| class="wikitable sortable" style="text-align:center;" width="100%" | |||
| | ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference | ||
| | |||
| | |- | ||
| [[FCFS (Disk Scheduling Disk Scheduling)|FCFS]] || 1979 || $O(n)$ || $O({1})$ || Exact || Deterministic || | |||
|- | |||
| [[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 \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 \log n)$ || $O(n)$ || Exact || Deterministic || | ||
| | |||
| | |||
|- | |- | ||
| | | [[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 \log n)$ || $O(n)$ || Exact || Deterministic || | ||
| | |||
| | |||
|- | |- | ||
| | |} | ||
== Time Complexity Graph == | |||
[ | [[File:Disk Scheduling - Time.png|1000px]] | ||
[ | |||
Latest revision as of 10:09, 28 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
