CS 61C: Great Ideas in Computer Architecture (Machine Structures)

CS 61C: Great Ideas in Computer Architecture (Machine Structures)

CMPT 300 Introduction to Operating Systems IO Sample Questions 1 Dual-Bus Architecture Q: Slide 20 shows one way of having memory-mapped I/O even in the presence of separate buses for memory and 1/0 devices, namely, to first try the memory bus and if that fails try the 1/0 bus. A clever computer science student has thought of an improvement on this idea: try both in parallel, to speed up the process of accessing I/O devices. What do you think of this idea? A: It is not a good idea. The memory bus is surely faster than the I/O bus, otherwise why bother with it? Consider what happens with a

normal memory request. The memory bus finishes first, but the I/O bus is still busy. If the CPU waits until the I/O bus finishes, it has reduced memory performance to that of the I/O bus. If it just tries the memory bus for the second reference, it will fail if this one is an I/O device reference. If there were some way to instantaneously abort the previous I/O bus reference to try the second one, the improvement might work, but there is never such an option. All in all, it is a bad idea. 2 Max Interrupt Rate Q: Suppose that a computer can read or write a memory word in 10 nsec. Also suppose that when an interrupt occurs, all 32 CPU registers, plus the program counter and PSW are pushed onto the stack. What is the maximum number of interrupts per second this machine can process?

A: An interrupt requires pushing 34 words onto the stack. Returning from the interrupt requires fetching 34 words from the stack. This overhead alone is 680 nsec. Thus the maximum number of interrupts per second is no more than about 1.47 million, assuming no actual work is done for each interrupt. 3 Printing Q: A typical printed page of text contains 50 line of 80 characters each. Imagine that a certain printer can print 6 pages per minute and that the time to write a character to the printer's output register is so short it can be ignored. Does it make sense to run this printer using interrupt-driven I/O if each character printed requires an interrupt that takes 50 sec all-in to service?

A: The printer prints 50 80 6 = 24,000 characters/min, which is 400 characters/sec. Each character uses 50 sec of CPU time for the interrupt, so collectively in each second the interrupt overhead is 20 msec. Using interrupt-driven I/O, the remaining 980 msec of time is available for other work. In other words, the interrupt overhead costs only 2% of the CPU, which will hardly affect the running program at all. 4 Interleaving & Skew Q: If a disk has double interleaving, does it also need cylinder skew in order to avoid missing data when making a track-to-track seek? Discuss your answer. A: Maybe yes and maybe no. If the head can make a track-to-track seek in fewer than two

sector times, than no additional cylinder skew is needed. If it cannot, then additional cylinder skew is needed to avoid missing a sector after a seek. 5 Fairness Q: None of the disk-scheduling disciplines, except FCFS, is truly fair (starvation may occur). a. Explain why this assertion is true. b. Describe a way to modify algorithms such as SSTF to ensure fairness. c. Explain why fairness is an important goal in a time-sharing system. d. Give examples of circumstances in which it is

important that the operating system be unfair in serving I/O requests. 6 Fairness Answer A: a. New requests for the track over which the head currently resides can theoretically arrive as quickly as these requests are being serviced. b. All requests older than some predetermined age could be forced to the top of the queue, and an associated bit for each could be set to indicate that no new request could be moved ahead of these requests. c. To prevent unusually long response times. d. Paging and swapping should take priority over user

requests. It may be desirable for kernel-initiated I/O, to take precedence over user-initiated I/O. If the kernel supports realtime process priorities, the I/O requests of those processes should be favored. 7 Disk Scheduling Q: Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 125. The queue of pending requests, in FIFO order, is 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130 Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk-scheduling algorithms?

a. FCFS b. SSTF c. SCAN d. C-SCAN 8 Disk Scheduling Answer Answer: a. The FCFS schedule is 143, 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130. The total seek distance is 7081. b. The SSTF schedule is 143, 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774. The total seek distance is 1745. c. The SCAN schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 130, 86. The total seek distance is 9769. d. The C-SCAN schedule is 143, 913, 948, 1022, 1470,

1509, 1750, 1774, 4999, 86, 130. The total seek distance is 9813. 9 Disk Size I Consider a disk with Disk Arm Platter parameters Cylinders 1024 Platter Platters (heads)16 Sectors per track 63 Each sector is 512 bytes Platter

What is the maximum size of the disk? A: 1024 * 16 * 63 * 512 = 582 Mb 10 Disk Size II Consider a disk with 16 platters (heads) and 400 cylinders. It is divided into four 100-cylinder zones with the cylinders in different zones containing 160, 200, 240, 280 sectors, respectively. Each sector is 512 bytes, average seek time between adjacent cylinders is 1 ms, and the disk rotates at

7200 RPM. Calculate (a) disk size (b) max data transfer rate. (Note that we consider physical geometry here, not virtual geometry, hence each zone may contain different number of sectors.) 11 Disk Size II Solution (a) The size of a zone is platters cylinders sectors/track bytes/sector.

Capacity of zone 1: 16 100 160 512 = 131072000 bytes Capacity of zone 2: 16 100 200 512 = 163840000 bytes Capacity of zone 3: 16 100 240 512 = 196608000 bytes Capacity of zone 4: 16 100 280 512 = 229376000 bytes Sum = 131072000 + 163840000 + 196608000 + 229376000 = 720896000 (b) The maximum data transfer rate will be when the cylinders in the outermost zone (zone 4) are being read/written. In that zone, in one second, 280 sectors are read 120 times (7200 RPM is 120 rotations/sec). Thus the max data rate is 280 120 512 = 17,203,200 bytes/sec. 12 Disk Performance I Q: Consider a disk with the following parameters:

12000 RPM, Data transfer rate of 40 MB/s Average seek time of 8 ms Disk block size of 4 KB What is the average time to read a random block from the disk? A: (note that the disk needs to rotate for half a revolution on average to get to a random block on disk, hence in the 3 rd term.) Tread=Seek+Rotational+Transfer Time=8+2.5+0.1=10.6 ms 13 Disk Performance I Q: Given the same parameters as before, assume that the operating system has exploited locality by grouping related blocks together in the file system. As a result, the typical access pattern is not as

random as before. It typically retrieves 10 blocks sequentially at a time. What is the average time to read a single block now? A: Compute the time for reading 10 blocks (since there is only 1 seek and 1 rotational for those 10), then divide by 10 for a single block read. Tread10=Seek+Rotational+Transfer Time=8+2.5+1.0=11.5 ms Tread=11.5 ms/10=1.15 ms 8 14 Disk Performance II Q: Consider a disk with the following parameters: 7200 RPM Average seek time of 8 ms Sector size=disk block size=0.5 KB 160 sectors per track

Q: Estimate the max sustained transfer rate of this disk. A: The disk rotates at120 times per second (7200RPM/ 60), and each rotation transfers a track of 80 KB (0.5KB*160). Thus, the max sustained transfer rate can be approximated as 9.6 MB/s (120*80 KB) or 9.6 KB/ms. 15 Disk Performance II Q: Estimate the number of I/Os per second and the effective transfer rate for a random-access workload that reads an individual sector that may be anywhere on the disk. A: Average rotational delay is (1/2)*(1000/120)=4.167

ms. Transfer time for 1 sector is 0.5KB/9.6KB/ms=0.052ms Tread=Seek+Rotational+Transfer=8+4.167+0.052=12.21 9 ms Number of IOs (transfers) per second is 1/(0.012219)=81.8. Since each transfer is 0.5 KB (1 sector), the effective transfer rate is 40.9 KB/s. 16 Disk Performance II Q: Calculate the number of random-access I/Os per second and transfer rate for I/O sizes of 4 KB, 8 KB, and 64 KB. A: For reads of size 4 KB, 8 KB, and 64 KB, the corresponding I/Os per second are calculated as before, e.g., for a read of 4 KB, transfer time is 4KB/9.6KB/ms=0.417 ms

Tread=Seek+Rotational+Transfer=8+4.167+0.417=12.6 ms Number of IOs (transfers) per second is (respectively for 4, 8, 64 KB) 1/(0.0126), 1/(0.013), and 1/(0.019). Thus we get 79.4, 76.9, and 52.6 transfers per second, respectively. Transfer rates are obtained from 4, 8, and 64 times these I/ O rates, giving 318 KB/s, 615 KB/s, and 3366 KB/s, respectively. 17 Disk Performance II Q: If multiple requests are in the queue, a scheduling algorithm such as SCAN should be able to reduce the average seek distance. Suppose that a random-access workload has I/O size of 8 KB, the average queue length is 10, and the scheduling algorithm reduces the average

seek time to 3 milliseconds. Now calculate the I/Os per second and the effective transfer rate. A:Tread=Seek+Rotational+Transfer=3+4.167+0.83= 8 ms, so we obtain 125 I/Os per second. From 8 KB per I/O we obtain 1000 KB/s. 18

Recently Viewed Presentations

  • IA Modifications to eJMAPS

    IA Modifications to eJMAPS

    Prepares passes for SASI/ASI signature. Maintains discipline within the classroom. Answers classroom phone; takes required action. Assists Flight Commander with inspection. Leads Flight during drill practice. Collects textbooks at the end of class on Wednesday (7th Pd) Discusses issues/concerns with...
  • Osjetljivost različitih genotipova beta-laktamaza ...

    Osjetljivost različitih genotipova beta-laktamaza ...

    Da bi se kvantificirala interakcija između testiranih supstanci izračunava se FIC index prema slijedećoj formuli: FIC = MICA/B/MICA + MICB/A/ MICA. Prema dobijenim rezultatima određuje se totalni, parcijalni sinergizam ili antagonizam između ispitivanih supstanci.
  • How to look at bacteria & Gram Staining

    How to look at bacteria & Gram Staining

    Steps for Gram Staining... Step 1. Make a slide of cell sample to be stained. Heat fix the sample to the slide by carefully passing the slide with a drop or small piece of sample on it through a Bunsen...
  • Citation Sandwich - marshall.k12.mn.us

    Citation Sandwich - marshall.k12.mn.us

    MLA Work Cited Citation. A MLA Work Cited citation goes in your Works Cited page (aka bibliography) in the back of your essay. For example: Colvel, Abraham. "Shakespeare's Language." The English Journal12 Dec. 1997. 3 Feb. 2007.
  • A3 PROBLEM SOLVING TOOL: Date:  Contact:  BACKGROUND /

    A3 PROBLEM SOLVING TOOL: Date: Contact: BACKGROUND /

    The right hand column of this A3 form embeds Deming's PDCA or PDSA cycle Plan: Solutions / Countermeasures Do: Action Plan Study and Act: Metrics / Follow-up Problem Solving Process Understand and verify the problem: * * A3 PROBLEM SOLVING...
  • The Use of Rollback to Prevent Incorrect Operation of ...

    The Use of Rollback to Prevent Incorrect Operation of ...

    The Migration of Functionality to the Network Edge Dave Marples [email protected] What do you mean? As customers require more and more functionality from their communications infrastructure so current vendors with their largely proprietary systems are unable to meet their needs...
  • WEST NILE ENCEPHALITIS - Texas A&M University

    WEST NILE ENCEPHALITIS - Texas A&M University

    Arial Arial Unicode MS Tahoma Times New Roman Wingdings Default Design Default Design Default Design Default Design Anthrax Control Program Objectives Reportable Bacterial disease Worldwide distribution Endemic to U.S. Triangle of Uvalde, Ozona, Eagle Pass, TX Affects numerous animal species...
  • Religion in a global context - WordPress.com

    Religion in a global context - WordPress.com

    Fundamentalism. Anthony Giddens: Traditionalists who which to seek to the . basics. or . fundamentals. of their faith. Literal interpretation that provides all the answers. They are . intolerant. of other views and refuse to engage in dialogue. It is...