Operating Systems • CS 438

Test 4, 13 November 2014


This test has six questions, all of which should be answered. The test runs the entire class period, starting at 7:25 and ending at 9:15. When you finish the test, you may leave.

Always justify answers unless the question explicitly states it’s not necessary. Some questions require reasonable assumptions in order to be answered. In such cases the answer should clearly state the assumptions made.
  1. Keeping in mind that giving an example of X is not defining X, briefly (in one or two sentences, 25 to 30 words total) define:

    • Sustained bandwidth

    • Programmed I-O

    • Block-level striping

    • The Sockets interface

    • Boot block

    • Interval timer


    • Sustained bandwidth:
    The steady-state bandwidth (transfer rate) achieved during an extended I-O operation.

    • Programmed I-O:
    CPU-specific

    • Block-level striping:
    Spreading contiguous data across several disks by breaking the data into blocks and writing successive data blocks to the same disk block on successive disks.

    • The Sockets interface:
    An operating-system supported interface to the networking subsystem.

    • Boot block:
    A disk sector containing code that is read in to primary store and executed as part of system boot-up.

    • Interval timer:
    A register that receives some number of ticks, decreases the number periodically, and triggers an interrupt when the number reaches 0.

    The answers, approximately verbatim, and in no particular order:

    1. • Sustained bandwidth:
      The amount of data the device transfer divided by the amount of time the transfer took.

      • Programmed I-O:
      A type of communication method that uses the DMA to communicate across devices in order to avoid wasting CPU with interrupts.1

      • Block-level striping:
      A type of parallel data storage/retrieval method that spreads sequential blocks of data across multiple hard[?] disks.

      • The Sockets interface:
      An interface used for network communication that drivers can use to obfuscate complicated network actions.

      • Boot block:
      The section of the hard disk/secondary storage that contains the code for loading in the operating system.

      • Interval timer:
      A register used for timing.2

      1: Mostly the opposite, but without DMA.

      2: Used how?

    2. • Sustained bandwidth:
      When the flow of data remains at a constant speed.

      • Programmed I-O:
      The information3 that passes4 between the system and storage device that is used by the system.

      • Block-level striping:
      Removing small sections of data from a disk at the block level.5

      • The Sockets interface:
      The connections6 made between the system and the storage device.

      • Boot block:
      The section of the disk that first gets loaded.

      • Interval timer:
      A mechanism that records the amount of time between device I-O operations.

      3: Any particular kind of information, or just information in general?

      4: Passes in a particular direction?

      5: What happens to the removed data? Where does it go? Why is it removed?

      6: What kind of connections?

    3. • Sustained bandwidth:
      Open channel of data flow staying at a specific average, little variation.

      • Programmed I-O:
      [ no answer ]

      • Block-level striping:
      Place pages across entire blocks.

      • The Sockets interface:
      [ no answer ]

      • Boot block:
      [ no answer ]

      • Interval timer:
      [ no answer ]

    4. • Sustained bandwidth:
      Refers to the amount of data that can be sent/received/written retrieved at a time.7

      • Programmed I-O:
      Hardcoded commands8 for the CPU/system to start;9 simulated input to receive identical output result.10

      • Block-level striping:
      Designation of a sector before and around the data11 for future data of a similar nature.12

      • The Sockets interface:
      Polling on a socket13 for specific information to be sent to and from a process.

      • Boot block:
      Starting section of disk holding all data necessary to get the core of the system running. Allows OS to be “up” prior to loading extraneous drivers, data.

      • Interval timer:
      Timer based off systemCLK that is usually used in a polling scenario, to check for something (ex: keypress) in the last interval (ex: 1000 ms).

      7: Over many times, hence “sustained”.

      8: Hardcoded where?

      9: To start what?

      10: Output result identical to what?

      11: Which data? Where is the data?

      12: Data similarity determined how?

      13: If a definition contains the phrase it's trying to define, it's probably not a good definition.

    5. • Sustained bandwidth:
      Consistent14 throughput between device to computer connection.

      • Programmed I-O:
      The part of the OS that handles devices connected to the computer, and how they interact with the OS.15

      • Block-level striping:
      Block i in a sequence gets stored in disk i mod n. Reduces per-disk queuing.16

      • The Sockets interface:
      [ no answer ]

      • Boot block:
      [ no answer ]

      • Interval timer:
      [ no answer ]

      14: Not the best word to use; “long-term average” is more to the point.

      15: Way too broad a definition.

      16: Perhaps, unless the request is in start+length form.

  2. Explain the costs and benefits of disk striping.


    Disk striping breaks up a contiguous data sequence and stores the pieces on a set of disks. Disk striping's chief benefit is parallelism: it turns a single large disk I-O operation into a set of n concurrent I-O operations, effectively increasing the transfer bandwidth by n when there are n disks in the set. The costs are the cost of the extra disks and the increased complexity of read and write operations.

    The answers, approximately verbatim, and in no particular order:

    1. Disk striping is the process of breaking up information to be stored on multiple disks rather than on one “big, fast disk.” The reason for striping is because producing a big, fast disks are expensive.1 So, one
        benefit
      is that it allows for cheaper disk space by providing a mechanism to tie together a RAID (redundant array of inexpensive disks).2 Since the data is organized among several disks, disk striping can cause reading and writing to the disks to take longer than it would if there was a single disk.3 These performance costs can be categorized into latency, which is now long it takes to get to the first bit, and delay which is how long it takes to get to the last bit. The exact latency and delay differences depend on the type of disk striping being used.4

      1: Maybe marginally more expensive, but not fundamentally so unless the sizes are extreme.

      2: But doesn't RAID at its own costs?

      3: Wouldn't parallel I-O increase performance in most cases?

      4: Possibly true; what examples would illustrate the claim?

    2. The benefit is that it clears a lot of space on the disk. The cost is that the data on the disk is lost.5

      5: Doesn't sound practical in that case.

    3. Disk striping provides an easier method in which the disk can be accessed for free pages.
    4. Disk striping can increase the read and write rate of data access in the secondary storage n times the speed of a single disk, where n is the number of disks stripped across. However, striping may cost more money to implement, as it requires at least two disks to implement without mirroring, though, no space is lost, so two 500 GB HDDs stripped together would make a 1 TB partition. However, each added disk increases the failure rate by an exponential factor.6 This7 can be remedied by adding additional disk for mirroring and parity, but these would inherently increase cost and take up valuable I-O ports, limiting the amount of [?] space that the system can use.

      6: A multiplicative factor, which combine to an exponential increase under independence assumptions.

      7: Which this?

    5. Dedicate sector to similar data, leaves empty “gaps” to be filled in later.8 This is inefficient space-wise, but should benefit future seek times.

      8: Nope, not even close. This reads like some quasi buddy-allocation policy.

  3. A DMA controller C uses physical addresses in all aspects of its operation. Describe how the operation would have to change for C to use virtual addresses.


    The DMA C would have to map virtual address to physical addresses and pin the virtual-physical mapping information so the storage-management subsystem won't try to page out the otherwise unused pages.

    The answers, approximately verbatim, and in no particular order:

    1. For the DMA controller to use virtual addresses it would have to go through a separate controller1 that linked C's virtual addresses with the systems physical addresses.2

      1: Any particular kind of controller?

      2: Any other coordination required?

    2. [ no answer ]
    3. [ no answer ]
    4. Assuming the following address scheme of a DMA: [ diagram ] then in the given example the DMA would be using a single memory address, such as AA1016 in the source pointer and the destination pointer.3 In order to accommodate the change to virtual addresses, the pointer must be changed to also include the offset of the function,4 so the same length pointer5 would now be [ diagram ]. The physical implementation of “number of bytes to transfer” would also have to change, as the bytes may not be sequential, instead spread across the memory in different settings with other programs in between.6

      3: Is the single memory address virtual or physical?

      4: Which function?

      5: Length pointer? What's that?

      6: Is non-sequential layout in page frames something that's visible at the virtual-address level?

    5. [ no answer ]
  4. A colleague of yours is designing computing system hardware and is trying to decide between using polling or interrupt-driven I-O. Recognizing your expertise in operating systems, you colleague asks you to identify some performance characteristics that would help make the decision. What do you suggest. In addition to identifying the characteristics, don't forget to indicate how the decision would be made.


    The most important characterization is CPU utilization. If utilization is low, CPU cycles are cheap to free, depending on how low, and spending them on polling would not be a problem. Otherwise CPU cycles are expensive because of high demand, and interrupt-driven I-O is more cost-effective than is polling.

    The answers, approximately verbatim, and in no particular order:

    1. [ no answer ]
    2. Polling is a technique where the CPU continually1 checks for the status of a device to determine when it is free to be used by a new process.2 This technique definitely would work, but it hogs the CPU and prevents other processes from being executed until the device is free to use again.3 Due to polling's over-use of the CPU I would advise my colleague against using it.4 Interrupt-driven I-O is where the device informs the CPU of its status. This technique prevents the need of the CPU to continually5 monitor a device's status. Interrupt I-O is also fairly easy to implement,6 and is reliable if implemented property.7 It is for these reasons that I would suggest my colleague use interrupt driven I-O.

      1: “Periodically” is a more accurate description.

      2: Or when the device is done performing an operation.

      3: Or whatever.

      4: But what if your colleague's system doesn't have much CPU demand otherwise?

      5: Or periodically.

      6: Oh? Easier than polling? Really?

      7: As is true of anything.

    3. I would suggest using interrupt-driven I-O for better performance,8 so the I-O would be done only when requested,9 instead of polling all the devices.10

      8: By what performance measure?

      9: I-O is usually done only when requested, although the requests can come from outside the system.

      10: Would this suggestion hold under all circumstances?

    4. Importance of hardware activities[?]: more or less critical than system processes.

      Speed of system reaction: Immediate vs soon.11

      Say HW is important, but not critical, with fast-as-possible responses.12 Pick polling with a high rate; this allows system to not drop concurrent actions and react to HW input/action at a fast speed.

      11: Some kind of measure of latency, yes?

      12: Responses to what? By what?

    5. The decision would be made based on the time of devices being polled and the transfer rates [?], access times, and amount of data needed in addition to knowing the amount of time the CPU needs to implement a context switch. Polling is great if there few devices, the devices respond quickly to requests, or the overhead of context switches from interrupts would be much too big in relation to expected response time. Interrupt-driven I-O would be better in systems with a large or [?] number of devices or devices that have large access times relative to the time it takes the CPU to context switch, as in those system it would be better for the CPU to move on to other [?] turn keep checking for a response, or check every register for a response from devices that takes a long time to respond.
  5. Which of the disk-arm schedulers would you expect to have the smallest variance in response time? Justify your choice.


    Seek time and rotational latency are the two main components of response-time variance. Seek time costs more in time than does rotational latency, and disk-arm schedulers have almost no influence over rotational latency. Under these assumptions, seek time is the most important component of the response-time variance.

    Because FCFS scheduling minimizes disk-arm travel, it should have smaller response-time variance among the disk-arm schedulers. FCFS can cause starvation, but that will effect service time, not response time.

    The answers, approximately verbatim, and in no particular order:

    1. C Scan scheduling would have the smallest variance in wait time1 because the arm is always going to go from one end to the other2 hitting all requests3 along the way. Overall, the starvation rate4 would at max be one full sweep away, the starvation chances are slower than the worst-case scenario of shortest seek time next or scan elevator and the response overall would be quicker than FCFS.

      1: The question asks about the variance in response time, not wait time.

      2: One end of what to the other?

      3: All the requests? Or maybe just some of them having some property?

      4: The question isn't about starvation.

    2. Of all the disk-arm schedulers I would expect circular scan to have the smallest variance in response time. The reason for this is because the SSTN technique causes starvation,5 which can greatly vary response time, and regular scan can cause uneven service times6 since it allows the disk arm to travel in both directions. Circular scan is consistent since it only travels in one direction, so a process can expect the disk to respond in a predictable amount of time when it is utilizing circular scan.

      5: But perhaps it is because of starvation that SSTN may have a low response-time variance.

      6: But perhaps bounded time-to-service?

    3. Assuming variance refers to max variance instead of average[?] variance,7 and that the read speed of a file is negligible compared to the physical moving and stopping of the disk arm, then LOOK has the smallest max variance. All algorithms except for FCFS have a theoretical minimum response time8 + if the head is already in position for a read. Therefore, the program with the smallest variance would have + - (max response time).9 For each of the file systems max response time (m) equals (n = time for disk movement).

      SCAN: max addressable memory locations x + x2, assuming the disk head starts at address 1 and needs to read address 0 with a velocity to the center of the disk.10

      C-SCAN: max addressable memory locations11 x + + + speed to 0 address, assuming the same as above.

      LOOK: equivalent to SCAN.

      SSTF: ∞, assuming that incoming addresses are always smaller12 distributed from the head through the requested address.

      FCFS: (max number of requests in queue - 1) + (time for head to move from address 0 to max addressable) x t,13 assuming the request is at the end of the systems ability to schedule addresses.14

      FCFS may have a lower variance than C-SCAN, but unfortunately that is dependent on the ratio of schedule address queue to disk size.15

      7: This is a terrible assumption because neither the maximum nor average variance is a quantity that makes sense on anything other than an arithmetic level.

      8: How does this statement make sense? Different disk-arm schedulers have different response times, so how can they all have the same minimum?

      9: What does this mean?

      10: What is being described by this sentence?

      11: What are “max addressable memory locations”? What are they measuring? Why?

      12: Incoming addresses are smaller than what? And what's an incoming address?

      13: What is this equation describing? How does it make sense to add a queue size and a time?

      14: What does it mean for a request to be “at the end of the systems ability to schedule addresses”?

      15: How does such a ratio have any meaning?

    4. The ones16 that do not rely on any kind of input function.17

      16: Which ones?

      17: Hard to imagine a useful activity that can function without any kind of input.

    5. Disk-arm scheduler that uses the vertical slice of the disk18 would have a faster response time;19 This method may not be as efficient as using a block.

      18: A vertical slice of the disk? What's that? A cylinder? And don't all disk-arm schedulers use a vertical slice of the disk?

      19: Faster is not what the question's asking about.

  6. Starvation is possible using any disk-arm scheduler. Devise a general mechanism of avoiding starvation in disk-arm schedulers.


    An unending sequence of I-O requests for sectors in the same track can cause all disk-arm schedulers except FCFS to starve processes issuing requests for other tracks. Rotational starvation can be dealt with the same way seek starvation was: limit I-O behavior per track by allowing only sector operation (read or write) per track visit, or ordering the sector operations so that once an operation on sector i has been performed, only operations on sectors j > i can be performed.

    The answers, approximately verbatim, and in no particular order:

    1. Starvation is not possible in FCFS systems, or any disk scheduler that uses SCAN or C-SCAN.
    2. A mechanism that keeps track of the amount of time since the last operation,1 and if it reaches a limit it could send an interrupt or restart the process2 to avoid starvation.3

      1: Is this answer confusing starvation with deadlock?

      2: What process?

      3: But wouldn't the restarted process, whichever process that may be, just go back to the previous circumstances in which starvation was occurring?

    3. [ no answer ]
    4. In order to avoid starvation in a disk-arm scheduler, the OS would need to put a priority level on the processes that need to access the disk.4 All of the disk-arm schedulers that we have discussed only create a priority level that is based off of how close the arm is to a cylinder on the disk. In order to avoid starvation the OS could assign priority that is an intelligent combination5 of the proximity to the disk arm6 and how long the process has been waiting on a response from the disk.7 By factoring in the time that a process has been waiting there would not be any significant starvation.

      4: But priority can cause starvation too.

      5: “Intelligent” means what?

      6: Proximity of what to the disk arm?

      7: Is the priority dynamic? Suppose a process has several requests in the queue (possible with asynchronous I-O); what then?

    5. The easiest way to prevent starvation even if it isn't likely to happen would to have a second disk arm and divide the sectors in half.8

      Or a c-scan scheduling with the two arms going in opposite directions.9 More plausibly, smaller disks, but even more of them, reduces the length in which the arm must travel. There would be less room for data but the rate to retrieve that data would be extremely fast.10

      More realistically11 you could have the data of one disk duplicated to another and they would have two different schedulers, or c-scan in opposite directions, however the overhead on it would be too costly since every bit would have to be written twice with the same address.12

      8: In half which way: radially or circumferentially?

      9: What?

      10: Does this paragraph have anything to do with starvation?

      11: ?

      12: But wouldn't the bits be written in concurrently?


This page last modified on 2014 November 25.