Final project presentations will be Monday, December 11,
1:30-4 PM, TCL 206
Exam out Tuesday: same ground rules as last time
Before you head out of town: final project progress reports
Lecture assignment recap
Complexity of a file system implementation (see link below)
RAID revisited - a better description is on
Wikipedia
Disk Scheduling Algorithms
Recall: cost of a disk access includes seek time and
rotational latency
We wish to minimize seek time by minimizing the distance the
read/write head has to move in order to service the incoming
requests by reordering requests based on cylinder number
This optimization may be done by the disk, the hardware
controller, or by the operating system
Compare algorithms by examining their performance on a given
request queue
First-Come First-Served (FCFS)
Shortest Seek Time First (SSTF)/Closest Cylinder Next
SCAN or Elevator Algorithm
LOOK Algorithm
Circular Algorithms
Comparing Disk Scheduling Algorithms
SSTF or LOOK are often reasonable for a default algorithm
SCAN and C-SCAN are better for heavily loaded systems
where LOOK is unlikely to save much and SSTF runs the risk of
starvation
performance depends on the frequency and types of requests
we may want to consider some of this when we look next
week at how to organize file systems
FreeBSD's ufs filesystem uses an elevator algorithm (see
/usr/src/sys/ufs/ufs/ufs_disksubr.c)
Hierarchical Storage
Recall our memory hierarchy:
Use tapes and other removeable storage to extend the file system
small and frequently-used files remain on disk
large, old, rarely-used files are archived on tapes
when one of the old files is requested, the file is
brought back onto the disk from the appropriate tape
usually implemented as a jukebox of tapes or removeable
disks
tape latency is typically 1000 times that of a disk
add in a tape robot that has to go fetch a tape and it
is even worse
or worse yet, a human who has to be notified, go to the
"tape room", find the tape, bring it to the drive, load it
Typically found at large supercomputing centers
See link below for an example (HPSS)
Issues to consider:
how to decide when to archive to tape
retrieval from archive may be fully automated or users
may need to explicitly request files from tapes
duplicate tapes? - tapes can be unreliable
when is this worthwhile? Can't we just archive
information manually?
Input/Output Management
one of the primary responsibilities of the OS
wide variety of devices to be handled
provide convenient interface
manage wide variety of device speeds - range from a
few bytes per second from a keyboard to several gigabytes
per second on a fast network interface
organization (files/file system from a disk)
error handling
deliver I/O to the correct process
protection and security
Two common ways to connect an I/O device
port (serial, parallel) ex: mouse, modem, printer,
joystick, scanner
bus (SCSI, USB, PCI) ex: disks, tapes (and now, the
above also)
device controllers often connect directly to the main
bus on behalf of actual devices
The OS provides I/O instructions to control devices:
direct I/O instructions - send out data on a port or
bus: Read/Write chunks of data directly on an I/O Port
with special machine instructions
memory-mapped I/O - read/write memory in special
locations assigned to a device - Can use regular machine
instructions to read and write the portion of memory
reserved for communication with each device
Accessing devices
How do we know when the device needs the attention of
the CPU?
Remember that "I/O Wait" means the process is not
in the ready queue or on the CPU, ideally
Polling: When OS has control of the CPU, it queries
the device - could end up being a busy-wait if the data will
not remain available for long, such as on a port
Interrupts: (recall from CPU scheduling)
CPU Interrupt request line triggered by I/O device
CPU switched to interrupt handler
Maskable to ignore or delay some interrupts
(consider an interrupt being interrupted!)
Interrupt vector to dispatch interrupt to correct
handler (Interrupt Service Routine - ISR)
Interrupt service can be complicated on modern machines
- consider pipelined execution
Direct Memory Access - I/O controller gets data and
puts the results directly in memory at a specified
location
Used to avoid programmed I/O for large data movement
Requires DMA-capable controller
Bypasses CPU to transfer data directly between I/O
device and memory - CPU can be doing other things - avoid
the need to copy things from a device buffer into user
space
Application I/O Interface
I/O system calls encapsulate device behaviors using a
common interface for a wide variety of devices
Device drivers hide differences among I/O
controllers from kernel - same kernel routines can call
functions in specific device drivers without worrying about the
details of the device
Device characteristics
Block devices
"large" blocks of data read/written at once
include disk drives
read, write, seek operations
Raw I/O (kernel) or file-system (user) access
Character devices
include keyboards, mice, serial ports, printers, modems
get, put operations on individual characters
Network Devices:
similar to block and character, but different enough to
be unique
socket interface to separate network protocol from
network operation
other options: pipes, FIFOs, streams, queues, mailboxes
need to deal with large amounts of data rapidly as well
as short interactive traffic
Blocking vs. Nonblocking I/O
Blocking - process suspended (removed from ready/run)
until I/O completed
Easy to use and understand
Insufficient for some needs
Nonblocking - I/O call returns as much as available
User interface, data copy (buffered I/O)
Implemented via multithreading
Returns quickly with count of bytes read or written
Asynchronous - process runs (doing something else)
while I/O executes
Difficult to use
I/O subsystem signals process when I/O completed
need to wait for the data explicitly
overlap I/O with other computation
Kernel I/O Subsystem: beyond just the interface, the kernel
manages devices to improve efficiency
Scheduling
some I/O request ordering via per-device queue
we saw disk scheduling
Buffering - may be needed because of
device speed mismatch (disk to printer, modem to disk)
device transfer size mismatch (gather network packets)
Caching - fast memory holding copy of data
always just a copy
key to performance
has come up before and will come up again
Spooling - hold output for a device
if device can serve only one request at a time
printing, maybe tape I/O
Device reservation - provides exclusive access to
a device
system calls for allocation and deallocation
deadlock avoidance/detection/recovery
Error Handling
OS can recover from disk read, device unavailable,
transient write failures (retry)
switch to another device, if possible
return failure code when I/O request fails
error logs
Bookkeeping and Kernel Data Structures
state info (open files, network connections, etc.)
complex data structures (i.e., Unix buffer cache)
I/O performance is a critical factor in overall system
performance:
reduce number of context switches
reduce data copying
reduce interrupts by using large transfers, smart
controllers, polling
use DMA
balance CPU, memory, bus, and I/O performance for highest
throughput
