Preview only show first 10 pages with watermark. For full document please download

Cs 423 – Operating Systems Design Lecture 4 – Processes And




CS 423 – Operating Systems Design Lecture 21 – Disk Devices and Timers Klara Nahrstedt Fall 2011 Based on slides by YY Zhou and Andrew S. Tanenbaum CS 423 - Fall 2011 Overview  Administrative announcements ◦ Midterm – Wednesday, October 12 in class!!  Disk Devices ◦ Performance Improvements  Timers CS 423 - Fall 2011 Disk Performance Improvements  Getting first byte from disk read is slow ◦ high latency  Improve disk performance ◦ Parallelize access (RAID) ◦ Schedule requests to speed up disk access  Schedule requests to shorten seeks ◦ Move some disk data into disk controller (ondisk caching) or main memory – file system caching 10/9/2011 3 RAID • • • • Use parallel processing to speed up CPU performance Use parallel I/O to improve disk performance, reliability (1988, Patterson) Design new class of I/O devices called RAID – Redundant Array of Inexpensive Disks (also Redundant Array of Independent Disks) Use the RAID in OS as a SLED (Single Large Expensive Disk), but with better performance and reliability 10/9/2011 4 RAID (cont.) RAID consists of RAID SCSI controller plus a box of SCSI disks  Data are divided into strips and distributed over disks for parallel operation  RAID 0 … RAID 5 levels  RAID 0 organization writes consecutive strips over the drives in round-robin fashion – operation is called striping  RAID 1 organization uses striping and duplicates all disks  RAID 2 uses words, even bytes and stripes across multiple disks; uses error codes, hence very robust scheme  RAID 3, 4, 5 alterations of the previous ones  10/9/2011 5 Kernel Components Affected by Block Device Op. VFS (Virtual File System) Disk Caches Disk Filesystem Disk Filesystem Disk Filesystem Mapping Layer Generic I/O Block Scheduler Block Device Driver Layer Layer Block Device Driver 10/9/2011 6 Disk Scheduling  Which disk request is serviced first? ◦ ◦ ◦ ◦ ◦ ◦  FCFS Shortest seek time first Elevator (SCAN) LOOK C-SCAN (Circular SCAN) C-LOOK Looks familiar? 10/9/2011 7 FIFO (FCFS) order  Method ◦ First come first serve  Pros 0 53 199 ◦ Fairness among requests ◦ In the order applications expect  Cons ◦ Arrival may be on random spots on the disk (long seeks) ◦ Wild swing can happen  Analogy: ◦ Can elevator scheduling use FCFS? 98, 183, 37, 122, 14, 124, 65, 67 10/9/2011 8 SSTF (Shortest Seek Time First)  Method ◦ Pick the one closest on disk ◦ Rotational delay is in calculation  0 53 199 Pros ◦ Try to minimize seek time  Cons ◦ Starvation  Question ◦ Is SSTF optimal? ◦ Can we avoid starvation?  Analogy: elevator 98, 183, 37, 122, 14, 124, 65, 67 (65, 67, 37, 14, 98, 122, 124, 183) 10/9/2011 9 Elevator (SCAN)  Method ◦ Take the closest request in the direction of travel ◦ Real implementations do not go to the end (called LOOK)  0 53 199 Pros ◦ Bounded time for each request  Cons ◦ Request at the other end will take a while 98, 183, 37, 122, 14, 124, 65, 67 (37, 14, 0, 65, 67, 98, 122, 124, 183) 10/9/2011 10 C-SCAN (Circular SCAN)  Method ◦ Like SCAN ◦ But, wrap around ◦ Real implementation doesn’t go to the end (C-LOOK)  0 53 199 Pros ◦ Uniform service time  Cons ◦ Do nothing on the return 98, 183, 37, 122, 14, 124, 65, 67 (65, 67, 98, 122, 124, 183, 199, 0, 14, 37) 10/9/2011 11 LOOK and C-LOOK SCAN and C-SCAN move the disk arm across the full width of the disk • In practice, neither algorithm is implemented this way • More commonly, the arm goes only as far as the final request in each direction. Then, it reverses direction immediately, without first going all the way to the end of the disk. • These versions of SCAN and C-SCAN are called LOOK and C-LOOK • 10/9/2011 12 Group Discussion Questions  The disk scheduling algorithm that may cause starvation is: ◦ FCFS or SSTF or C-SCAN or LOOK ??  From the list of disk-scheduling algorithms (FCFS, SSTF, SCAN, CSCAN, LOOK, C-LOOK), SSTF will always give the least head movement for any set of cylinder-number requests to the disk scheduler: ◦ True or False ??  The cylinder numbers on a disk are 0,1,…10. Currently, there are five cylinder requests on the disk scheduler queue in the following order: 1,5,4,8,7 and the head is located at position 2 and moving in the direction of increasing block numbers. The time to serve a request is proportional to the distance from the head to the cylinder number requested. If T(X) is the time it takes to service the requests currently in the queue using scheduling algorithm X, then: ◦ ◦ ◦ ◦ T(SSTF) < T(SCAN) < T(FCFS) or T(FCFS) < T(SSTF) < T(SCAN) or T(SSTF) < T(FCFS) < T(SCAN) or None of the above??? 10/9/2011 13 History of Disk-related Concerns  When memory was expensive ◦ Do as little bookkeeping as possible  When disks were expensive ◦ Get every last sector of usable space  When disks became more common ◦ Make them much more reliable  When processor got much faster ◦ Make them appear faster 10/9/2011 14 On-Disk Caching  Method ◦ Put RAM on disk controller to cache blocks  Seagate ATA disk has .5MB, IBM Ultra160 SCSI has 16MB  Some of the RAM space stores “firmware” (an OS) ◦ Blocks are replaced usually in LRU order – What are the pros and cons of on-disk caching? 10/9/2011 15 Disk Block Caches • • • • Main memory rather than disk may hold disk blocks 85% or more of all I/O requests by file system and applications can be satisfied by disk block cache BSD UNIX provides a disk block cache as part of the block-oriented device software layer It consists of between 100 and 1000 individual buffers. 10/9/2011 16 Disk I/O Summary • • • Disk is an important I/O device Disk must be fast and reliable Error Handling is important; check checksum, called ECC (Error Correcting Code) – Track a bad sector – Substitute a spare for the bad sector – Shift all sectors to bypass the bad one • • RAID protects against few bad sectors, but does not protect against write errors laying down bad data Stable Storage may be needed 10/9/2011 17 Clocks and Timers • Hardware clocks (also called timers) – give the current time – give the elapsed time – set a timer to trigger operation X at time T Programmable interval timer - hardware to measure elapsed time and trigger operations • This mechanism is used by the scheduler, disk I/O subsystem, network subsystem • Give examples where/when/how CPU scheduler uses timers. • 10/9/2011 18 Clock Hardware • Older/simpler clocks – tied to the 110 or 220 volt power line and cause interrupt on every voltage cycle at 50-60 Hz. • Current clocks consist of three components: – a crystal oscillator – a counter – a holding register. – Feature: • The quartz crystal generates a periodic signal of very high accuracy (several hundred MHz). This signal is fed into the counter which counts down to zero. When the counter is zero, it causes CPU interrupt. The holding register is used to load the counter. 10/9/2011 19 Programmable Clock    Modes of programmable clocks: ◦ one-shot mode: when the clock starts (started explicitly by the software), it copies the register value into the counter, decrements the counter, causes an interrupts when counter is zero, and stops ; ◦ square-wave mode: when the clock starts, it copies the register value into the counter, decrements the counter, causes an interrupts when counter is zero, and then automatically the holding register value is copied into the counter, and the whole process repeats (i.e., there is no explicit start of the clock by the software) The periodic interrupts are called clock ticks. Programmable clock chips usually contain two or three independently programmable clocks. 10/9/2011 20 Clock Issues Battery-powered backup clocks  Some clocks drift and need to be resynchronized. ◦ manually resynchronize the clocks. ◦ get the current time from a remote host which carries the UTC (Universal Coordinated Time ), formally known as Greenwich Mean Time).  NTP (Network Time Protocol) is a standard protocol to re-synchronize clocks between two networked systems (regularly the system administrators re-synchronize all clocks in our machines using NTP).  10/9/2011 21 Clock Software Clock hardware generates interrupts at known intervals.  The clock hardware is served by the clock driver software.  Functions of the clock driver: ◦ Maintaining the time of day ◦ Preventing processes from running longer than they are allowed to ◦ Accounting for CPU usage ◦ Handling alarm system call made by the user process ◦ Providing watchdog timers for parts of the system itself ◦ Doing profiling, monitoring and statistics gathering  10/9/2011 22 Clock Overflow Time of the day(real clock): requires incrementing a counter at each clock tick.  One difficulty is the overflow of the counter (e.g., a 32-bit counter overflows in two years).  What are the possible solutions to the overflow problem?  10/9/2011 23 Other Functions  Preventing processes from running too long ◦ whenever a process is started, the scheduler initializes a counter to the value of that process' quantum in clock ticks. As the clock ticks, the counter is decremented, and when counter is zero, the clock driver calls the scheduler to set up another process.  CPU accounting ◦ The system should start a second timer (different from the main timer). Whenever the process starts, the second timer starts counting. When a process stops, the timer can be read out to tell how long the process has run. When a process is interrupted, the timer value should be stored and when the process restarts, the timer value should be restored.  Simpler way to do CPU accounting ◦ currently running process keeps a field in the process table entry. At every clock tick, this field in the current process is incremented, ie. every clock tick is ``charged'' to the process running at the time (problems might arise if many interrupts occur). 10/9/2011 24 Timer for Individual Process  Providing timers (alarm) to requests from processes in order to give a warning after a certain time interval ◦ If the clock driver had enough clocks, it could set a separate clock for each request. This is not the case.  Simulate virtual clocks with a single physical clock. ◦ maintain (a) table in which the signal time for all pending times is kept, and (b) a variable giving the time of the next one. When time of day is updated, the driver checks for the closest signal to occur. Once it has, the table is searched for the next one to occur. 10/9/2011 25 Watchdog Timer and Profiling A timer is set, and when the timer goes off, instead of causing signal as it is the case for user signals, the clock driver calls a procedure supplied by the caller.  Use it for profiling  ◦ Build histogram of the program counter and see where it is spending its time. ◦ Debugging 10/9/2011 26 Soft Timers  Software-based timer, called soft timer, is a timer which ◦ sets to the requested frequency as needed ◦ is checked by the kernel when entries are made for other reasons such as system calls, TLB misses, page faults, I/O interrupts, CPU going idle. ◦ If the soft timer has expired, the scheduled event is performed (e.g., packet transmission) with no need to switch to kernel mode. ◦ The kernel resets the soft timer again to go off. The kernel copies the current clock value to the timer and adds the timeout interval to it.  Soft timer can avoid interrupts ◦ the frequency of kernel entries is so frequent that the kernel can check on the soft timer and schedule the events without sending an interrupt. 10/9/2011 27 Linux Timekeeping Architecture  Linux carries several time-related activities: ◦ Updates the time elapsed since system startup ◦ Updates the time and data ◦ Determines for each CPU quanta ◦ Updates resource usage statistics ◦ Checks whether the interval of time associated with each software timer elapsed. 10/9/2011 28 Timing Measurements • Real Time Clock (RTC) – Independent of CPU and other chips – Continues to tick on small battery – Capable to issues periodic interrupts on IRQ8 at frequency 2Hz to 8,192 Hz • Time Stamp Counter – Interface register that allows access to clock signal counter • Programmable Interval Time (PIT) – Similar to alarm clock – it is used to issue timer interrupts on IRQ0 at frequency 1000 Hz – Time interval is called tick 10/9/2011 29 Timing Measurements • CPU Local Timer – similar to PIT – can issue one shot or periodic interrupts • High Precision Event Timer (HPET) – New timer chip (Intel&Microsoft) – Includes up to 8 32-bit or 64-bit independent counters – HPET is expected to replace PIT • Power Management Timer 10/9/2011 30 Data Structures of Timekeeping Architecture • • Examples of some of the 80x86 architecture Timer object – Identifies timer source and Supports four standard methods • Method that records exact time (invoked by timer interrupt handler) • Method that returns time elapsed since last tick • Method that returns number of nsec since kernel init • Method that waits for a given number of “loops” • Jiffies variable – Counter that stores number of ticks since system started • Xtime variable – Stores current time and date 10/9/2011 31 Software Timers • Timer – software facility that allows functions to be invoked at some future moment, after a given time interval elapsed – Time-out facility • Linux has two types of timers – Dynamic timers – Interval timers • • Dynamic timers may be dynamically created and destroyed Interval timers – these timers cause UNIX signals to be sent periodically to the process 10/9/2011 32 System Calls Related to Timing Measurements • time() – Returns number of elapsed seconds since midnight of January 1, 1970 • gettimeofday() – Returns structure ‘timeval’ – number of elapsed microseconds in the last second and seconds since midnight January 1, 1970 • Sleep(), usleep() – Puts process to sleep for certain amount of seconds, microseconds, respectively Other timers (alarm, setitimer…) • Group activity: • – Write a pseudo-code where you calculate in a loop multiplication of a number x with itself and you return the result after 100 microseconds 10/9/2011 33 Timer Summary • • • Always check what is the timer resolution on your platform since too many components depend on it Linux kernel implements POSIX timers by means of dynamic timers Linux also supports Delay Functions – if software timers are useless (in case kernel must wait for a short time period – few ms, the kernel makes use of udelay() or ndelay()) 10/9/2011 34