CSCI 350 Fall 2001 Midterm

Statistics: before the 10-point curve...

mean     66.188 (1059.000/16)
stddev   13.168
median   65.500
midrange 57.000-77.000

#   avg
1	6.625 / 8
2	4.375 / 8
3	6.625 / 8
4	5.438 / 8
5	5.75  / 8
6	6.75  / 12
7	3.125 / 8
8	3.5   / 8
9	4.125 / 8
10	6.375 / 8
11	5     / 8
12	6.25  / 8
13	2.25  / 15 (bonus)

  1. [8 pts] Describe two distinct aspects that distinguish a microkernel architecture for an operating system from a monolithic architecture? Do not simply list two sides of the same issue.
  2. [8 pts] In serious operating systems, user processes run on the CPU with restricted permissions: Their access to memory and I/O devices is severely limited. And of course they can't willy-nilly gain unrestricted permissions - that would be a gaping security hole.

    But sometimes a process nonetheless needs to access an I/O device (like the disk), even though it cannot access it directly. What CPU feature allows it to accomplish this?

    A software interrupt puts the system into unrestricted mode. It also jumps the CPU into operating system code, so that the operating system can govern access to the device.

  3. [8 pts] Recall that the OS is suspended while the CPU runs a process, so it is not able to do anything during this time. So how is the operating system able to preempt a running computational process when its quantum has expired?

    The operating system can schedule an interrupt with the clock. When the clock sends its interrupt, control will transfer into the operating system, and the OS can suspend the computational process at this time.

  4. [8 pts] We saw in class Peterson's approach to locking via shared-memory access. What about this approach caused us to investigate direct OS support of locking instead?

    Peterson's approach involved busy-waiting, so that processes using it would be wasting the CPU while they want to get a lock.

  5. [8 pts] Every interrupt handler must contain some assembly code. That is, we cannot expect to write the entire interrupt handler in C. Why?

    The interrupt handler will need to suspend the running process, and to do that it needs to save all the process's registers into memory. Access to specific machine registers is not available in portable languages like C.

  6. [12 pts] In class we saw the reader-writer problem, where we have a piece of data that has both read locks and write locks. Any number of processes should be acquire a read lock, but neither read locks nor new write locks are allowed when a process has acquired a write lock.

    Say we want to enable a process to upgrade its lock - that is, we want to permit a process with a read lock to acquire a write lock. When a process does this, new processes trying to get a write lock should have to wait.

    You may assume that upgrades are extremely rare: No more than one reader will upgrade its lock at a time. Your solution should prevent a process attaining a write lock while a process is trying to upgrade its read lock. Your solution need not worry about starvation as a result of a continuous stream of readers.

    I've given you the code we saw in class, which you may modify as you find it necessary.

    void lock_read() {                      void lock_write() {
       down(count_lock);
       if(count == 0) down(data_lock);          down(data_lock);
       ++count;
       up(count_lock);
    }                                       }
    
    void unlock_read() {                    void unlock_write() {
        down(count_lock);
        --count;
        if(count == 0) up(data_lock);           up(data_lock);
        if(count == 1 && wants_upgrade) {
            up(upgrade_sig);
            down(upgrade_obtained);
        }
        up(count_lock);
    }                                       }
    
    void upgrade_lock() {
        wants_upgrade = true;
        down(upgrade_sig);
        --count;
        up(upgrade_obtained);
    }
    
  7. [8 pts] A professor, on learning that Minix does not buffer messages between processes, decides that it would be a nice assignment to have students add message buffering to Minix. Thus processes will rarely have to block when sending a message. However, the professor finds that there is no improvement in system performance with this modification.

    Console our disappointed professor with an explanation of why there was no improvement.

    In user processes and servers, Minix programs always immediately receive a message from the process to which they send a message. Being able to circumvent the send doesn't help with the subsequent receive. (Minix tasks don't always do a receive from a process after the send, but there's no speedup here, either, since the process will always be ready to receive the message the task sends.)

  8. [8 pts] An OS salesperson advertises that a new version of the OS implements the elevator algorithm for scheduling disks, a vast improvement over the old version's first-in, first-out algorithm. An excited student purchases the new operating system, and runs a test: The student's test process chooses 1,000 random locations on the disk and accesses each of them. The student finds that both versions of the OS perform identically.

    Console our disappointed student with an explanation of why there was no improvement.

    Disk scheduling is only helpful when you might have multiple requests for the disk simultaneously. In the student's program, the process blocks each time the process makes the request, until the request is fulfilled. At no time is the disk trying to fulfill multiple requests from the process at the same time, so the scheduling algorithm is irrelevant.

  9. [8 pts] Explain how direct memory access (DMA) is distinct from memory-mapped I/O access.

    DMA works with memory addresses as instructed by instructions running on the CPU, whereas memory-mapped I/O works with fixed memory addresses specified by the hardware designer. Generally, the memory addresses are fixed with memory-mapped I/O, but mobile with DMA.

  10. [8 pts] In CGA text mode, each character is stored in memory, and the CGA display reads from memory. A naive technique for scrolling involves copying every character on the screen to a new location, but that makes scrolling the screen an expensive operation. How can scrolling be implemented to make it faster?

    The CPU can tell the display to begin reading characters to display at the memory location of what was previously the second line of the screen.

  11. [8 pts] Say we have a disk spinning at 10,000 rotations per minute. The disk has 1,048 cylinders, 4 heads, 252 sectors per track, and 512 bytes per sector. What is the maximum number of bytes per second that a disk head be able to transfer to the controller? (Just show me the expression you'd type into the calculator.)

    10,000 / 60 * 252 * 512

  12. [8 pts] Say we have a 1024×768 display that can handle 224 colors. It refreshes the screen 70 times a second. How many bytes per second should the display be able to read from memory? (Again, I'm just looking for an expression.)

    1,024 * 768 * 3 * 70

  13. [15 pts] (Bonus question) A professor wishes to cross Minnesota Street, with cars coming from the east and the west. Each car, when it approaches the pedestrian, calls either lock_east() or lock_west(). When it passes the pedestrian, it calls unlock_east() or unlock_west(). The pedestrian calls lock_both() on reaching the street, and calls unlock_both() on crossing it.

    Use semaphores to prevent cars from continuing east or west while the professor crosses the street. Your approach should give priority to the cars - they should only block when the professor will enter the street immediately.

  14. a. List the semaphore(s) that your implementation uses, along with their initial values.

    
    count_lock, initially 1, to lock when we want to access count variables
    east_lock, initially 1, to lock when somebody has eastbound lane
    west_lock, initially 1, to lock when somebody has westbound lane
    check_again, initially 0, to signal when it's worth checking lanes again
    
  15. b. List shared variables (if any) that your implementation uses.

    
    east_count, initially 0, counting cars going eastbound with lock
    west_count, initially 0, counting cars going westbound with lock
    waiting, initially false, tracking whether to signal to check lanes
      again
    
  16. c. Insert your code into the below templates.

    
    void lock_east() {          void lock_west() {
        down(count_lock);           down(count_lock);
        if(east_count == 0)         if(west_count == 0)
            down(east_lock);            down(west_lock);
        east_count++;               west_count++;
        up(count_lock);             up(count_lock);
    }                           }
    
    void lock_both() {
        waiting = true;
        while(true) {
            down(count_lock);
            if(east_count + west_count == 0) {
                down(east_lock);
                down(west_lock);
                up(count_lock);
                waiting = false;
                return;
            }
            up(count_lock);
            down(check_again);
        }
    }
    
    void unlock_east() {              void unlock_west() {
        down(count_lock);                 down(count_lock);
        --east_count;                     --west_count;
        if(east_count == 0)               if(west_count == 0)
            up(east_lock);                    up(west_lock);
        if(waiting)                       if(waiting)
            up(check_again);                    up(check_again);
        up(count_lock);                   up(count_lock);
    }                                 }
    
    void unlock_both() {
        up(east_lock);
        up(west_lock);
    }