CSCI 350 Fall 2001 Final

Statistics: Before the 12-point curve...

mean     85.000 / 120
stddev   20.195
median   80.000 / 120
midrange 76.250-102.500

#   avg
1   8.46 / 10
2   8.15 / 10
3   8.54 / 10
4   6.23 / 10
5   4.23 / 10
6   7.31 / 10
7   6.31 / 10
8   8.54 / 10
9   5.77 / 10
10  8.00 / 10
11  8.85 / 10
12  4.62 / 10

  1. [10 pts] A user process runs on the CPU when the CPU is in protected mode. But, to access the disk, the CPU must be in unprotected mode. What CPU feature safely allows the user process to request access to the disk, without giving the user process direct access?

    The CPU has an instruction for issuing a software interrupt, which simultaneously jumps the CPU into trusted operating system code and changes into unprotected mode.

  2. [10 pts] The Minix operating system is structured into four layers. Describe what occupies each of them.

  3. [10 pts] For a typical hard disk, retrieving a sector from the platter is basically a three-step operation. Describe the procedure. (You don't have to have exactly three steps - but I have three specific steps I'm looking for.)

    1. The disk controller moves the disk arm to the correct cylinder.

    2. The disk controller waits for the correct sector to rotate around to beneath the arm.

    3. The disk controller begins receiving bytes from the appropriate head and saving them into a buffer.

  4. [10 pts] Give an example of an operating systems issue that we have resolved using the concept of indirection. Describe the issue, and explain how we used indirection to solve it.

    There are many possible answers. The most popular ones were:

    1. Virtual memory uses indirection in order to provide the illusion of a larger memory space than there exists. It uses indirection by interpreting each memory address as an index into a table, which contains the true memory address where the memory lies.

    2. Interrupts use indirection to restrict which pieces of unrestricted code a user process can access. By identifying each interrupt handler in a table, the OS can ensure that the user process will only jump to valid procedures. It uses indirection by taking an interrupt number, looking up that entry of the table, and jumping to the address identified in the table.

  5. [10 pts] In Assignment 6, you used Pthreads to ensure that the server would manage only up to MAX_CLIENTS clients at any single time. How would you do this using semaphores instead?

    Be as explicit as possible, naming specific semaphores you would use, and saying exactly where you would do the DOWN and UP operations.

    Define a single semaphore, clients_left, whose initial value is MAX_CLIENTS. Each time, before spawning a new thread, run down(clients_left). And, each time a client finishes, execute up(clients_left).

  6. [10 pts] Consider the following basic code fragments illustrating a potential solution to Part C of Assignment 6.
    int             count        = 0;
    pthread_mutex_t count_lock   = PTHREAD_MUTEX_INITIALIZER;
    pthread_cond_t  thread_avail = PTHREAD_COND_INITIALIZER;
    void* serveClient(void *arg_p) {       int main(int argc, char **argv) {
      // receive request                     // start the server listening
                                             while(true) {
      // send response to client               // accept connection from client
      // before we finish, tell ``main'' it    // wait until # client threads is low
      // can go (if indeed it was waiting)     pthread_mutex_lock(&count_lock);
      --count;                                 ++count;
      pthread_cond_signal(&thread_avail);      while(count > MAX_CLIENTS) {
                                                 pthread_cond_wait(&thread_avail, &count_lock);
    }                                          }
                                               // start thread to service client
    This code has a bug: The ``main'' thread could sometimes end up waiting when in fact there are fewer than MAX_CLIENTS clients. Explain how this could happen, and explain how to fix the bug.

    Suppose the server tests whether count is more than MAX_CLIENTS, and - before it executes pthread_cond_wait(), execution transfers into the client process. Suppose further that the client executes --count; and pthread_cond_signal() and finishes. When control transfers back to the server, it must execute its next instruction, the call to pthread_cond_wait(), which will make it start waiting, even though a client has just finished.

    The solution is to put the --count; and pthread_cond_signal() call between a call to pthread_mutex_lock(&count_lock) and a call to pthread_mutex_unlock(&count_lock).

  7. [10 pts] The relocation problem arises in multiprocessing systems where the operating system decides where to place each program's memory just before it is executed. We saw that modern CPUs typically include a feature on the chip to address the relocation problem. Describe the feature.

    Modern CPUs winclude the concept of a segment register. When the OS loads the program into memory, it will simply set the segment register to be the first address where the program is stored. Each time the user process accesses a memory address, the CPU automatically adds the contents of the segment register to the requested address to get to the actual memory address.

  8. [10 pts] Name three pieces of data found in a typical page table entry.

  9. [10 pts] Describe the technological trends that motivate the proposal of log-structured filesystems. (There are two major factors.) Be sure to explain how they make log-structured filesystems potentially more attractive than traditional filesystems.

    First, disk seek time has not improved much over the years, especially when compared to CPU time. Thus the disk is becoming more and more of a bottleneck. Second, memory space has improved dramatically, and this has led to larger disk caches, and so cache misses have become more infrequent, and a larger fraction of disk accesses have been requests to write to the disk (not read from it, since those requests are handled from cache when possible).

    Log-structured filesystems optimize for the write case - by continually writing at the end of the log, the disk doesn't have to seek for the writes. Reads become more cumbersome, since they can involve large jumps all over the disk (files become very fragmented), but block reads are less important than they once were.

  10. [10 pts] Describe the four layers of the TCP/IP protocol stack.

  11. [10 pts] Imagine you are writing an HTTP server in C++ under Unix. (That shouldn't stretch your imagination too much - that was Assignment 6.) Say you have already connected to an HTTP client, received its request, opened the file, and loaded it into a buffer. What specific Unix system call would you use to send the buffer to the client?


  12. [10 pts] What motivates the introduction of RPC for communication between computers?

    Defining and implementing protocols for communicating between computers is tedious and error-prone. RPC attempts to hide this process of defining a protocol from the programmer, instead abstracting each request for a computer to do something as a simple procedure call.