1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
|
## 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.
### 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.
|
