Teorija
Literatura: Stallings, Operating Systems: Internals and Design Principles, 9. izd., pogl. 11 (odj. 11.5, Linux u odj. 11.9); alternativno Tanenbaum & Bos, Modern Operating Systems, pogl. 5 (4. izd. odj. 5.4.1 i 5.4.3).Reading: Stallings, Operating Systems: Internals and Design Principles, 9th ed., ch. 11 (sec. 11.5, Linux in sec. 11.9); alternatively Tanenbaum & Bos, Modern Operating Systems, ch. 5 (4th ed. sec. 5.4.1 and 5.4.3).
Parametri pristupa disku
Podaci na disku leže na track (staza); iste staze svih ploča čine cylinder (cilindar), a ovdje je dovoljna jedna ploča. Da bi pročitala sektor, disk arm (ruka diska) pomiče head (glava) na stazu: to je seek time (vrijeme traženja) Ts. Zatim se čeka da sektor dođe pod glavu, rotational delay (rotacijsko kašnjenje), u prosjeku pola okretaja 1/(2r), pa slijedi transfer time (vrijeme prijenosa) b/(rN) za b bajtova od N na stazi. Zbroj je access time (vrijeme pristupa): Ta = Ts + 1/(2r) + b/(rN).
Disk performance parameters
Data on a disk lies on tracks; the same tracks of all platters form a cylinder, and one platter is enough here. To read a sector, the disk arm moves the head to the track: this is the seek time Ts. Then the sector has to rotate under the head, the rotational delay, on average half a revolution 1/(2r), followed by the transfer time b/(rN) for b bytes out of N on a track. The sum is the access time: Ta = Ts + 1/(2r) + b/(rN).
Slijedno ili nasumično
Stallingsov disk ima Ts = 4 ms, 7500 okretaja u minuti (okretaj traje 8 ms) i 500 sektora po stazi. Datoteka od 2500 sektora zauzima 5 susjednih staza: uz sequential access (slijedni pristup) prva staza traje 4 + 4 + 8 = 16 ms, a svaka sljedeća 4 + 8 = 12 ms, ukupno 64 ms. Uz random access (nasumični pristup) svaki sektor plaća traženje i rotaciju: 2500 × 8,016 = 20.040 ms, oko 313 puta sporije. Redoslijed zahtjeva zato vrijedi optimizirati: raspoređivanje diska skraćuje ukupno traženje.
Sequential or random
Stallings's disk has Ts = 4 ms, 7500 rpm (one revolution takes 8 ms) and 500 sectors per track. A file of 2500 sectors occupies 5 adjacent tracks: with sequential access the first track takes 4 + 4 + 8 = 16 ms and each following one 4 + 8 = 12 ms, 64 ms in total. With random access every sector pays the seek and the rotation: 2500 × 8.016 = 20,040 ms, about 313 times slower. The order of the requests is therefore worth optimizing: disk scheduling shortens the total seek.
FIFO, PRI, LIFO i SSTF
Zahtjevi čekaju u request queue (red zahtjeva). Stallingsova tablica 11.3 dijeli politike na one koje biraju prema podnositelju (FIFO, PRI, LIFO) i one koje biraju prema traženoj stazi. FIFO je pravedan, ali ruka skače po cijelom disku (498 staza, prosječna seek length (duljina traženja) 55,3). PRI gleda samo prioritet, a LIFO prvo poslužuje najnoviji zahtjev. SSTF (Tanenbaum: SSF) bira najbliži zahtjev i daje 248 staza, ali daleki zahtjev može čekati neograničeno: starvation (izgladnjivanje).
FIFO, PRI, LIFO and SSTF
Requests wait in the request queue. Stallings's Table 11.3 divides the policies into those that select according to the requestor (FIFO, PRI, LIFO) and those that select according to the requested track. FIFO is fair, but the arm jumps across the whole disk (498 tracks, average seek length 55.3). PRI looks only at the priority, and LIFO serves the newest request first. SSTF (Tanenbaum: SSF) picks the nearest request and gives 248 tracks, but a distant request can wait indefinitely: starvation.
SCAN i C-SCAN
SCAN (Tanenbaum: elevator algorithm, algoritam dizala) pomiče ruku u jednom smjeru i poslužuje sve zahtjeve na putu, pa se okreće. Stallingsov primjer koristi profinjenje LOOK: ruka se okreće kod zadnjeg zahtjeva, ne na rubu diska (250 staza; do ruba 280). C-SCAN poslužuje samo u jednom smjeru, a zatim se vraća na drugi kraj: povratni skok 184 → 18 (166 staza) ulazi u Stallingsov zbroj od 322. Tako čekanje ovisi manje o položaju zahtjeva na disku.
SCAN and C-SCAN
SCAN (Tanenbaum: the elevator algorithm) moves the arm in one direction and serves every request on the way, then reverses. Stallings's example uses the LOOK refinement: the arm reverses at the last request, not at the edge of the disk (250 tracks; 280 to the edge). C-SCAN serves in one direction only and then returns to the other end: the return sweep 184 → 18 (166 tracks) is part of Stallings's total of 322. This way the wait depends less on where a request lies on the disk.
Zaglavljena ruka, N-step-SCAN i FSCAN
Ako novi zahtjevi stalno stižu na stazu na kojoj je glava, SSTF, SCAN i C-SCAN ostaju ondje: arm stickiness (zaglavljena ruka). N-step-SCAN dijeli red na podredove od N zahtjeva i SCAN-om prazni jedan po jedan; novi zahtjevi idu u nove podredove. FSCAN ima dva reda: dok se jedan poslužuje, novi zahtjevi čekaju u drugom. U scenariju „Zaglavljena ruka” zahtjev A uz SSTF završava u 175 ms, a uz FSCAN u 55 ms. N = 1 daje FIFO, a velik N daje SCAN.
Arm stickiness, N-step-SCAN and FSCAN
If new requests keep arriving for the track the head is on, SSTF, SCAN and C-SCAN stay there: arm stickiness. N-step-SCAN divides the queue into subqueues of N requests and empties them one at a time with SCAN; new requests go into new subqueues. FSCAN has two queues: while one is being served, new requests wait in the other. In the “Arm stickiness” scenario request A finishes at 175 ms with SSTF and at 55 ms with FSCAN. N = 1 gives FIFO, and a large N gives SCAN.
HDD naspram SSD-a i Linux
SSD (solid-state drive) nema ruku ni ploču, pa je pristup gotovo jednak za svaki blok: redoslijed prestaje mijenjati vrijeme (0,9 ms za devet zahtjeva uz svaku politiku). Linux zato za SSD često koristi jednostavan raspoređivač ili nijedan, a za diskove politike tipa dizala s rokovima (Stallings opisuje Linuxov elevator i raspoređivač s rokovima). Zahtjev dolazi od upravljačkog programa, blok bira datotečni sustav, a više diskova i priručnu memoriju pokazuje RAID i priručna memorija. Vidi i Tehnike U/I te Put jednog poziva.
HDD versus SSD, and Linux
An SSD (solid-state drive) has no arm and no platter, so access takes almost the same time for every block: the order no longer changes the time (0.9 ms for nine requests with every policy). For an SSD, Linux therefore often uses a simple scheduler or none, and for hard disks elevator-type policies with deadlines (Stallings describes the Linux elevator and the deadline scheduler). The request comes from the device driver, the block is chosen by the file system, and several disks and a cache are shown on the RAID and disk cache page. See also I/O techniques and Journey of a call.