completed lec 20,21,22 -- still need lec 23
[kspaans/CS350] / lec19-0714.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{July 14, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle 
9
10 \section*{Lecture 19 -- Disk Drives}
11 The unit of access is a \textbf{block} (or sector) of a set size (usually
12 512 bytes). Therefore the disk, or block device, can be thought of as an array
13 of blocks. Internally though, the hard drive has geometry: sectors, tracks,
14 platters, cylinders. The way it all works (spinning platters with moving
15 read/write heads) has performance implications for the kernel. For example,
16 sequential access is more efficient than random access. Knowing these details,
17 and having information out where the data is on disk means the kernel can
18 optimize requests to the disk drive for performance. This is similar to how
19 the kernel masks the block size from user programs who are perfectly allowed
20 to request single bytes.
21
22 \subsection*{Seek Latency}
23 Read/write heads have to \textbf{seek} to the correct cylinder on the platter
24 before data can be read. This implies seek latency for most kinds of requests.
25 We can model seek latency linearly, assuming that moving across $n$ cylinders
26 takes $nt$ time no matter where the heads are on the platter.
27
28 \subsection*{Sectors per track}
29 Some hard drives have the same number of sectors per track on the inside and
30 outside of the platter. These are called constant linear density drives or
31 something like that. Other drives do not have a constant number of sectors
32 per track. They will have a higher density towars the outside of the platter,
33 and therefore higher transfer rates on that part of the disk.
34
35 \subsection*{Rotational Latency}
36 Rotational Latency is the amount of time the read/write heads have to wait
37 until the desired sectors are below them. We can expect the average rotational
38 latency to be half of the rotation time of the disk $\frac{1}{2 \omega}$
39 ($\omega$ is the number of rotations per second of the disk).
40 Transfer time is directly related to the number of sectors that need to be read
41 and the speed at which the disks are spinning. The service time, the amount of
42 time for hardware to respond to a kernel's request, is the sum of seek,
43 rotational and transfer times.
44
45 \subsection*{Disk Head Scheduling}
46 Many requests for data on the hard disk can get queued up because the kernel
47 and CPU move much faster than the disk. The kernel or the hardware can decide
48 to reorder requests for optimal seek or rotational latency (depending on what
49 kind of info we know about the hard drive). First-Come-First-Served is a
50 strategy that is fair, but does not optimize anything. Shortest Seek Time First
51 can reduce seek latency, but can cause starvation. Better strategies are LOOK
52 and SCAN. LOOK will seek towards new requests only in on direction until no
53 more requests are in that direction, then it will seek in the other direction.
54 SCAN works similarly, but will seek all the way to the edge of the platter
55 before turning around. These strategies are kind of like scheduling an elevator
56 in a building. LOOK and SCAN are biased against requests nearer the edge of the
57 platter, because requests there will possible have to wait for the read/write
58 head to seek and read across two full radii of the platter. There are circular
59 versions of both LOOK and SCAN. They seek in only one direction, but return to
60 the opposite edge when they reach the end of their seeking. They will reduce
61 the average wait time for requests on any cylinder to be the same.
62 \end{document}