Notes for CSC 256/456, 13 March 2000 ff Has everybody seen the new assignment in the newsgroup? reading assignment: skim chapter 12 read chapter 13 carefully skim chapter 14 ----------------------- INPUT/OUTPUT DEVICE MANAGEMENT, ESP. DISKS Classification of devices Block Devices - devices that are addressable in fixed block sizes. Examples include magnetic and optical disks, and magnetic tape. Character Devices - devices that deal with characters (or bytes) in sequence; they are not addressable per se. Examples include terminals and most printers. (In fact, any device not obviously block oriented is usually classified as a character device.) Dramatic range of bandwidths (keyboard does a few bytes per second; DLT does hundreds of MB/s Some devices (e.g. disk) can sensibly be shared among users; others (e.g. keyboard, laser printer) can't. Tape is usually not shared, because seek times are so long. Some devices are read-only or write-only; others are both. OSes work hard to hide device differences behind a uniform interface (file system); that's the subject of the next set of notes. Note that some of the info on tertiary media in chap. 14 is already dated. Magneto-optical disks have been surplanted by pure optical RW disks (CD-RW and DVD-RAM). I/O Software Overview Recall the distinction between busy-wait and interrupt-driven I/O. Busy-wait I/O on modern machines is mainly limited to bootstrapping. user-level software library routines such as printf and spooling daemons generally implemented via a (shared) library in the application device-independent software (i.e. file system) uniform view of buffering, naming, protection, error handling may be in the kernel (typical monolithic system) or in a user-level server (microkernel system) device driver top half translates high-level I/O commands (eg, write a page to disk) to device-specific commands for the bottom half, records the pending work in the shared data structures and then blocks. interrupt handlers (bottom half) gets work from the top half, gives commands to the device, and fields interrupts. BUFFERING serves to stage information for a device to smooth out transfer rates or block sizes, or to ensure copy semantics CACHING serves to exploit temporal and spatial locality (buffering and caching can share data structures) SPOOLING serves to make a non-shared output device look shared Types of interaction Devices on modern machines are memory-mapped, meaning that their control registers appear in physical address space (a portion of PAS called I/O space). Ancient machines sometimes had special I/O instructions. programmed I/O CPU baby-sits the device -- moves data through the processor registers. DMA (direct memory access) device can be told where data is to go to/come from. It then interacts with memory itself, without processor help. Note that this requires that we "wire-down" any memory being used by the device, so it doesn't get paged out! Scatter/gather some DMA devices are capable of reading and writing blocks consisting of several chunks in different locations. This is great for adding headers to things without copying to larger buffers. Channel controllers some mainframes have programmable I/O controllers that can do complicated things like search through indices. Often they have separate I/O buses, to avoid interfering with processor(s) devices v. controllers Basically the device holds the data; the controller is the electronics that controls the device(s). Many controllers can handle 2, 4 or even 8 identical (or similar) devices. The OS device driver talks to the controller. A good controller doesn't wait for a device to seek; it starts the seek and gets back in touch with the OS. If there are operations that can be done on other device(s), it can start them concurrently. For disks, this means you get *overlapped seeks* on different devices. (Note that the OS can overlap seeks itself if devices are on different controllers, but the controller has to help if it has several devices). ----------------------- Disk hardware overview A single disk device may consist of multiple disk surfaces. A disk surface is flat and round and is divided into tracks. Each track is divided into fixed-size sectors (usually from 8 to 32). Disks are accessed by read/write heads. Ancient fixed head disks or drums had a separate head for each track. Multiple heads are expensive; however, there is no seeking. Modern moving head disks have a single head which moves in and out to reference different tracks on a single surface. The read/write heads for multiple surfaces are connected by an "arm" and move together. The set of tracks referenced by a particular position of the arm are called a "cylinder". A disk address consists of (drive, cylinder, surface, sector). Positioning consists of: 1. seek time to move the head to the correct track 2. rotational delay (latency) to rotate the sector under the head 3. transfer time to transfer the data Historically, seek time dominated, but heads have now become so small and light that rotational time is important again. Many (most?) disks incorporate a full-track buffer to mitigate rotational latency for sequential access. We assume that requests to use the disk may arrive faster than they can be serviced (bursty). Therefore, at any point in time, there may be a number of outstanding requests for a disk. We would like to service those requests in such a way as to minimize the total time needed. If there are two requests in the same cylinder, for example, we'd like to get them both before seeking again. Formatting low-level (usually at factory) divide surfaces into marked tracks and sectors; identify and lock out bad blocks partitioning (at system configuration time) create logical disks that use part of a physical disk; can organize information in different partitions differently (e.g. a Linux FS and an NT FS on the same physical device) Some OSes can create logical partitions that span physical disks, but that's a higher-level SW convention, not a matter of device-level format FS formatting (what happens when you erase a floppy or hard-disk partition) creates the on-disk data structures needed by the FS ----------------------- Disk Scheduling Scheduling algorithms to minimize seek time FCFS: service requests as they arrive. susceptible to long seeks, decreasing disk performance simulation results show good performance under light load, but saturation is reached quickly SSTF: service request with the shortest seek time from current position. better throughput and lower mean waiting time, higher variance. subject to starvation of requests at the extremes of the disk. non-optimal, especially under light load. Example: on track 53, with requests 14,37,65,67,98,122,124,183 SSTF seeks 236 tracks. Satisfying 37,14,65,67... seeks 208 tracks. (Note, however, that seek time is not linear, due to acceleration and deceleration) SCAN/LOOK: (elevator algorithm) disk head sweeps back and forth over all cylinders, changing direction only at the extremes. LOOK is same as SCAN except that it changes direction when there are no more requests to be satisfied in the current direction. does not discriminate (starve) individual requests gives non-uniform wait time for requests a request to track 0 must wait for a scan from track 1 to track N and back; a request for track N/2 need only wait for half as long. Note: if the disk head starts at an extreme of the surface and the request queue is static (within a scheduling interval), SCAN is equivalent to SSTF. Note: simulations show that under heavy load, SCAN and SSTF have similar performance. C-SCAN/C-LOOK: similar to SCAN/LOOK, except that the head moves back to track 0 from track N. (C is for "cyclic") gives more uniform wait time for individual requests For lightly loaded disks, use FCFS or LOOK. For heavily loaded disks, use C-LOOK. Note: transparent substitution of good blocks for bad blocks by intelligent controllers can cause poor performance by our disk scheduling algorithm! Not *too* bad if replacement sectors are chosen nearby. Many modern controllers can take a batch of requests and do their own scheduling. That's fine if the OS doesn't care about order for other reasons (priority, ordering for stability). If the OS cares, it has to send individual requests and get acknowledgments. Scheduling algorithms to minimize rotation (latency time) Such algorithms were once used in fixed head disks and drums, now basically extinct. They have become interesting again (seek times on some modern disks are dropping under rotational delays) but are typically implemented in the controller, not the OS. SLTF: shortest latency time first accesses the sector closest to the current head position. Also note: many modern high-performance disks have a full-track buffer in the controller. This lessens the need for rotational scheduling: once one sector of a track has been read, the rest is in fast memory. (I don't think anybody buffers whole cylinders, however, so rotational scheduling across tracks still matters.) If the disk is fast enough that full-track buffering makes sense but the controller doesn't do it, you can do it in the device driver, but it doesn't work as well, because then you have to use a CPU-intensive copy loop to move data into the user application when it asks for it, where with a controller-implemented buffer the movement can happen via DMA. More interesting than rotational scheduling is rotational *layout*: it can make sense to lay out contiguous bytes in non-contiguous sectors. This is important, for example, if memory or bus bandwidth is less than disk bandwidth. If you can't suck up the next sector right after the first one comes in, you'll have to wait another rotation if they're contiguous, but you can get it a lot sooner if they're interleaved with other stuff. << draw picture >> Again, this doesn't matter if your controller has full-track buffering, but it does if you do the buffering in the device driver. ----- Note that all the above discussion addresses the best way to access data once we know its physical address. A related (and perhaps more interesting) problem is to figure out which physical locations to use for which data. This is a file system topic. Coming up. ============================= RAID (redundant arrays of inexpensive disks) Fairly new idea (last dozen years or so). Improves disk bandwidth, though not latency. Spreads data across multiple disks so that they can all transfer in parallel. Scattering across disks may be at the bit or word level (as in the "data vault" for the TMC Connection Machine 2), or at the block level (as in the RAID devices now offered by many manufacturers). You can now buy RAID devices for personal computers! Note that block-level interleaving is a win only if you want to read more than one block at a time. Big problem with RAID: failures. If you have 50 disks, each of which has a .001 chance of failing this week, and if failure rates are independent, then the odds that all your disks stay up is .999^50 ~= .95. That's one chance in 20 of a failure. Without redundancy, that single failure takes a piece of *every* file. Different practical RAID schemes introduce redundancy in different ways. Data vault uses a Hamming code to represent each 32-bit word with 38 bits spread across 38 disks, with single-bit recovery. Simplest redundancy is mirroring; fancier schemes use more space-efficient parity encoding. Maintaining parity sectors is expensive if you read and write single sectors. It's not bad if you read and write whole sector groups at one time. RAID 0 data striping, no redundancy RAID 1 mirrored disks (100% overhead) RAID 2 data-vault style: nibble-level striping, synchronized writes RAID 3 block-level striping, parity disk, synchronized writes RAID 4 like RAID 3, but non-synchronized RAID 5 scattered parity other extensions from various vendors ============================= Stable storage Conventions for writing disk to ensure that logically coherent operations are atomic. Typical method is to use a log describing operations. To perform an operation, you first write (as a single contiguous operation) a description of what you're going to do. That happnes atomically, because if the write fails halfway through the partity will (almost certainly) be bad. Then you start performing the operation. If you die halfway through, boot-time checks can look to see how much actually happened, and start the op over again if it didn't all get done.