Chapter 11, Silberschatz and Galvin

    5. Will the file ever change size? If so, will it get bigger or smaller? How big is the file? What access patterns exist for the file?

    7. This scheme is different from the standard contiguous allocation method in that files need not end up contiguous on disk, but that's the goal. It's different from the usual linked implementation in that the linked pieces of the file may be different sizes.

    9. Caches help improve performance by allowing a much shorter access time for a (potentially frequently used) subset of the data. Why not just use a cache for everything if it's so wonderful? Because caches are typically more expensive storage than their backing stores, because management overhead may go up dramatically with size, and because caches often have different volatility characteristics than their backing stores.

Chapter 12, Silberschatz and Galvin

    4. Blocking I/O should be used for quick-to-develop applications, since it is easier to understand; and for uses such as databases and disk management utilities which rely on data consistency. Non-blocking I/O should be used for user interfaces which need to display data while waiting for keyboard or mouse input; video applications which read frames from disk while simultaneously decompressing and displaying the output, and in general for multithreaded programs in which one thread can continue to make progress while another waits for I/O.

    8. DMA increases concurrency by allowing devices and memory to communicate with each other without involving the CPU. Therefore the CPU can continue to accomplish other useful work while the DMA takes place. It complicates hardware design because the CPU is no longer involved in each communication, so now we have to worry what happens if the network interface is talking to memory at the same time that the CPU is talking to memory.

    9. Here's a quick implementation of virtual clocks for kernel and application timer requests. There's no need to use all three timer channels so I just use one here. One way of using three channels might be to have one just for the system clock, one for kernel requests, and one for application requests. Then the handlers could be given different priorities: the system clock handler would always run and the OS clock handler would probably also always run, but if the application timer goes off when the system is overloaded, the handler might choose to drop some of the timer events from its queue without servicing them, or delay their service.

    typedef struct timer_event {
    time_t when;        // the next time this timer should go off
    func_t what;        // what function should be run
    time_t interval;    // what time to set the next timer; 0 if
                        //    non-repeating
}* timer_event_t;

queue_t timerq;
extern time_t now;

timer_event_t create_timer_event(time_t delay, func_t fn, time_t interval) {
    timer_event_t te = (timer_event_t) malloc(sizeof(struct
                                              timer_event));
    te->when = now + delay;
    te->what = fn;
    te->interval = interval;
    return te;
}

void set_timer(time_t delay, func_t fn) {
    // insert a new timer_event_t into the queue in sorted order,
    // sorting on the time when the function should next be run
    queue_priority_insert(create_timer_event(delay, fn, 0));
}

void set_repeating_timer(time_t interval, func_t fn) {
    queue_priority_insert(create_timer_event(interval, fn, interval));
}

void timer_interrupt_handler() {
    timer_event_t first = timerq->first;  // grab the next timer to go off
    if(first->when > now) {               // if it's time to do it...
        queue_dequeue(first);             // ...remove it from the queue
        if(first->interval != 0) {        // if it's a repeating timer...
	    first->time += interval;      // ...set its time to an
                                          //        interval from now
            set_repeating_timer(first);   // ...and put in back in the
                                          //        queue
        }
        run(fn);                          // finally, run the
                                          //    requested function
    }
}
    I've glossed over something in my pseduocode. How is the requested function actually run? Is it run in the context of the interrupt handler? Probably not. Probably, each timer event also has a process or thread associated with it, and the requested function will be run in the context of the requesting thread, by messing with that thread's stack to make it look like that thread has called the requested function.

    10. If device speeds stay the same while the CPU gets faster, then it takes more CPU cycles for the device to do the same old work. Thus if the CPU has to wait for the device to do that work, more CPU cycles are being wasted. Therefore we would like device speeds to scale with CPU speed.

Chapter 13, Silberschatz and Galvin

    1. Assertion: only FCFS is fair; starvation may occur.
    a. This is true because all of the other algorithms look at all currently pending requests and service the "best one" first, according to some metric having nothing to do with arrival time. If new requests keep arriving that are "better" than some old request, then the old request will never be serviced.
    b. To make something like SCAN fair, take the requests in batches of, say, 10. Out of the current batch of ten, implement SCAN, and then start again on the next batch. However, if you only have 7 pending requests, go ahead and do SCAN on those 7 without waiting for 3 more.
    c. Fairness is important in a time-sharing system because two users who paid the same amount for access to the system may get different levels of service. When the losing user finds out, he'll probably want his money back.
    d. When should the I/O system be unfair in servicing requests? When that unfairness can work for the greater good of the system. For instance, if an I/O must occur right away in order to be useful (while playing video, for instance), then unfairness is important. Also, unfairness might actually be the policy of the system. For instance, if the policy is, "Faculty I/O requests are always serviced before student I/O requests," then starvation is OK.

    2. a. FCFS order will be as listed. Total distance traveled = (1470-143) + (1470-86) + (1470-913) + (1774-913) + (1774-948) + (1509-948) + (1509-1022) + (1750-1022) + (1750-130) = 1327 + 1384 + 557 + 861 + 826 + 561 + 487 + 728 + 1620 = 8351.
    b. SSTF order will be as follows: 143, 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774. The total distance traveled will be 13 + 44 + 827 + 35 + 74 + 448 + 39 + 243 + 224 = 1947.
    c. SCAN order will be 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86. The total distance traveled will be 770 + 35 + 74 + 448 + 39 + 243 + 224 + (3225 + 4869) + 44 = 9971. The very large term near the end accounts for the disk head moving all the way to the end of the disk before turning in the other direction.
    d. LOOK order will be 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86. The total distance traveled will be 770 + 35 + 74 + 448 + 39 + 243 + 224 + 1644 + 44 = 3521.
    e. C-SCAN order will be 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130. The total distance traveled will be 770 + 35 + 74 + 448 + 39 + 243 + (3225 + 4999 + 86) + 44 = 10187. The very large term near the end accounts for the disk head moving all the way to the end of the disk, all the way back to the beginning, and then forward again.

    3. a. The seek time is proportional to the square root of the seek distance because when we solve the acceleration equation provided in the question for time, we end up square-rooting the distance. More intuitively, it takes time for the disk head to get up to speed, so short seeks take nearly as long as long seeks.
    b. Seek time as a function of seek distance. Take the form of the equation provided, plug in (.5 ms, .5 cyl) and (9 ms, 2500 cyl) and solve simultaneously. Because the acceleration and deceleration are equal and opposite, we want to solve the equations for only the first half of the motion, the accelerating part, because we know that the second half of the motion will mirror it exactly. Solving simultaneously, I get: t = .447 ms + .171 ms/cyl^(1/2) * L^(1/2).
    Warning: I have a degree in math. That means I'm incapable of solving basic arithmetic and algebra problems. I would not be at all surprised if this analysis is wrong. Don't worry, this won't be on the final.
    c. This part doesn't sound like any fun at all. =) I know you are all capable of plugging numbers into formulas, so I will leave this one as an exercise to the reader.
    d. Ditto.

    13. It's important to balance load so that I/O throughput is maximized. If load is unbalanced, and if the most heavily loaded disk is saturated, then some bandwidth will be wasted and system performance will degrade.
    14. If you store code pages in swap space, then there exist two copies of the pages on disk: one in the original file and one in swap space. This is a waste of space. In addition, the first time the code page is replaced, it will need to be written to swap space; if we used the original file as backing store instead, the code page could just be discarded.
    On the other hand, there are more levels of indirection in a file system lookup than a swap space lookup, so finding the page again when it is needed may take longer (though, realistically, most of this information is likely to be cached). Also, if someone overwrites or deletes the program in the original file system, the running instance of that program may be hosed, depending on the OS and the VM implementation. For instance, overwriting a running program's file in Solaris causes big problems (though deleting it is OK -- the file system will keep a copy of the program around "under the covers" until it's not needed any more).