COT 4600 Operating Systems Fall 2009 Dan C Marinescu Office HEC 439 B Office hours Tu Th 3 00 4 00 PM Lecture 23 Attention project phase 4 due Tuesday November 24 Final exam Thursday December 10 4 6 50 PM Last time Performance Metrics Chapter 5 Random variables Elements of queuing theory Today Methods to diminish the effect of bottlenecks batching dallying speculation I O systems the I O bottleneck Multi level memories Memory characterization Multilevel memories management using virtual memory Adding multi level memory management to virtual memory Next Time Scheduling 2 Methods to diminish the effect of bottlenecks Batching perform several requests as a group to avoid the setup overhead of doing one at a time f fixed delay v variable delay n the number of items n f v versus f nv Dallying delay a request on the chance that it will not be needed or that one could perform batching Speculation perform an operation in advance of receiving the request speculative execution of branch instructions speculative page fetching rather than on demand All increase complexity due to concurrency The I O bottleneck An illustration of the principle of incommensurate scaling CPU and memory speed increase at a faster rate than those of mechanical I O devices limited by the laws of Physics Example hard drives The average seek time AST AST 8 msec average rotation latency ARL rotation speed 7200 rotation minute 120 rotations second 8 33 msec rotation ARL 4 17 msec A typical 400 Gbyte disk 16 383 cylinders 24 Mbyte cylinder 8 two sided platters 16 tracks cylinder 24 16 MBytes track 1 5 Mbyte track The maximum rate transfer rate of the disk drive is 120 revolutions sec x 1 5 Mbyte track 180 Mbyte sec The bus transfer rates BTR ATA3 bus 3 Gbytes sec IDE bus 66 Mbyte sec This is the bottleneck The average time to read a 4 Kbyte block AST ARL 4 180 8 4 17 0 02 12 19 msec The throughput 328 Kbytes sec Lecture 23 5 I O bottleneck If the application consists of a loop read a block of data compute for 1 msec write back and if the block are stored sequentially on the disk thus we can read a full track at once speculative execution of the I O we have a write though buffer so that we can write a full track at one batching then the execution time can be considerably reduced The time per iteration read time compute time write time Initially 12 19 1 12 19 25 38 msec With speculative reading of an entire track and overlap of reading and writing Read an entire track of 1 5 Mbyte reads the data for 384 1 500 4 iterations The time for 384 iterations Fixed delay average seek time 1 rotational delay 8 8 33 msec 16 33 msec Variable delay 384 compute time data transfer time 384 1 12 19 5065 msec Total time 16 33 5 065 5 081 msec Lecture 23 6 Lecture 23 7 Disk writing strategies Keep in mind that buffering data before writing to the disk has implications if the system fails then the data is lost Strategies Write through write to the disk before the write system call returns to the user application User controlled write through a force call At the time the file is closed After a predefined number of write calls or after a pre defined time Lecture 23 8 Communication among asynchronous sub systems polling versus interrupts Polling periodically checking the status of an I O device Interrupt deliver data or status information when status information immediately Intel Pentium Vector Table 9 Interrupts used for I O and for exceptions CPU Interrupt request line triggered by I O device Interrupt handler receives interrupts To mask an interrupt ignore or delay some interrupts Interrupt vector to dispatch interrupt to correct handler Based on priority Some non maskable 10 DMA Bypasses CPU to transfer data directly between I O device and memory it allows subsystems within the computer to access system memory for reading and or writing independently of CPU disk controller graphics cards network cards sound cards GPUs graphics processors also used for intra chip data transfer in multi core processors Avoids programmed I O for large data movement Requires DMA controller 11 12 Device drivers and I O system calls Multitude of I O devices Character stream or block Sequential or random access Sharable or dedicated Speed of operation Read write read only or write only Device driver layer hides differences among I O controllers from kernel I O system calls encapsulate device behaviors in generic classes 13 Block and Character Devices Block devices e g disk drives tapes Commands e g read write seek Raw I O or file system access Memory mapped file access possible Character devices e g keyboards mice serial ports Commands e g get put Libraries allow line editing 14 Network Devices and Timers Network devices Own interface different from bloc or character devices Unix and Windows NT 9x 2000 include socket interface Separates network protocol from network operation Includes select functionality Approaches vary widely pipes FIFOs streams queues mailboxes Timers Provide current time elapsed time timer Programmable interval timer for timings periodic interrupts ioctl on UNIX covers odd aspects of I O such as clocks and timers 15 Blocking and non blocking I O Blocking process suspended until I O completed Easy to use and understand Insufficient for some needs Non blocking I O call returns control to the process immediately User interface data copy buffered I O Implemented via multi threading Returns quickly with count of bytes read or written Asynchronous process runs while I O executes I O subsystem signals process when I O completed 16 Synchronous Asynchronous 17 Kernel I O Subsystem Scheduling Some I O request ordering using per device queue Some OSs try fairness Buffering store data in memory while transferring to I O device To cope with device speed mismatch or transfer size mismatch To maintain copy semantics 18 19 Kernel I O Subsystem and Error Handling Caching fast memory holding copy of data Always just a copy Key to performance Spooling holds output for a device that can serve only one request at a time e g printer Device reservation provides exclusive access to a device System calls for allocation and de allocation Possibility of deadlock Error handling OS can recover from disk read device unavailable transient write failures When I O request fails error code System error logs hold problem reports 20 I O Protection I O instructions are priviledged Users make system calls 21 Kernel Data Structures for I O handling Kernel keeps state info for I O