Written Homework

Written homework assignments are primarily to give you some practice answering exam-like questions. They are due at the beginning of class, and I will not accept late written homework assignments.

For this assignment, and all written homework assignments, you are welcome, and encouraged, to work in small groups (2 or 3 students) either trying to solve the problems together or trying to verify each other's solutions prior to submitting them. If you solve the problems as a group, you should submit your own write-up of the assignment and list the other students you worked with.

Homework 1
Due: Friday Sept. 26, before 11:30 (the beginning of class)

Answer the following questions:
  1. Write 2 paragraphs about your group's scheduling policy from the in-class exercise. The first paragraph should describing your group's scheduling policy (what is the algorithm, how does it work). The second paragraph provide an analysis of your policy's strengths and weaknesses: it what ways is it good, and why?; it what ways may it not be so good, and why?; why do you think it is a good policy for your system's workload?

  2. In a sentence or two: what is short-term, long-term, and medium-term scheduling?

  3. What is an interrupt driven system? Describe what happens when the CPU gets an interrupt (say from a disk device).

  4. For each of the scheduling policies, (1) RR w/ time slice of 2, (2) preemptive SJF, and (3) FCFS, draw the Gantt chart and compute (a) ave. waiting time, (b) ave turn-around time and (c) throughput given the following set of processes arrival times in the ready queue and their CPU burst sizes: 
            process         arrival time            CPU burst size
        -------         ------------            --------------
          P1              0                        10
          P2              3                         4
          P3              4                         6
          P4              5                         8
          P5              6                         4
  5. Show the code fragment (not a whole function) for a shell to execute the following command. You DO NOT need include in your answer any command line parsing code, just hardcode in any strings that represent path names or command line arguments (this is not a question to test your string parsing capabilities, it is a question about process creation and IPC): 
              $ cat foo | grep blah

Homework 2
Due Monday Oct. 20 before class

This homework is designed to give you some practice solving synchronization problems before the midterm.

Do the following problems:

  1. Use semaphores to solve the Cigarette Smoker Problem.
    There are three smokers, and one agent. Each smoker has one of the three ingredients necessary for smoking; one has matches, one has tabacco, and one has paper. Smokers continuously roll a cigarettes and smoke it, but they first need all three ingredients to do so. The agent places two of the three ingredients on the table, and the smoker with the remaining ingredient picks them up and smokes. Write a solution to synchronize the agent and the smokers.

  2. Use monitors to solve the Readers-Writers problem.
    In this problem there are multiple reading and writing process that are trying to access a shared buffer. Multiple readers can simultaneously read the buffer, but only a single writer can write at a time (and no readers can read while a writer is writing). You should solve a slightly different version of the Readers-Writers problem then the one we solved in class. In this version a reader must block if a writer is waiting (even if currently there are other readers reading). When it is safe for a reader to read, it can wake up any other readers that have been waiting to read too, but if a writer comes along while these readers are reading, then any subsequent reader that wants to read must wait because there is now a writer now waiting. When a current writing writer is done writing, either a waiting writer can go next or a waiting reader can go next (you don't care which one, just handle them in a FCFS kind of way). If a waiting reader gets to go next, it will wake up all readers who are also waiting to read. However, readers that come along after this set of readers wake up and read will block if there are any writers waiting to write. In this version starvation of readers and writers is not possible.
    (hint: think about boundary cases, does the first reader need to do anything differently than subsequent readers, or does the last reader need to do anything differently than the first to stop reading, does the writer need to do anything special before or after it writes?).
For additional practice, try some of the problems we did in class implementing the ones we did using semaphores with monitors and the ones with monitors with semaphores.

Homework 3 (extra credit, but you should do this)
Due: Friday Oct. 31, before 11:30 (the beginning of class)

  • Linked Lists in Linux

    Examine Linux's support for linked lists. The interface is defined in include/linux/list.h, and uses of lists can be found throughout the kernel source. In particular, look at code that moves task_struct structs from list to list.

    Assume that the following struct definition exits: 

    struct test_struct {
    int x;
    struct list_head  list;
};
    USING ONLY FUNCTIONS AND MACROS from list.h, for each of the following operations: (1) list the C code fragment that performs the operation AND (2) draw a picture of memory that is the result of performing the operation if it changes either list in either way from the previous operation (label all fields in all structs and show their values, draw pointers fields as arrows to what they point to not as numeric address values):

    1. declare two empty lists named test1 and test2

    2. write a for loop (you may use a C for loop for this) that adds 3 new elements to the end of the test1 list (their data fields should have values 0, 5, 10). Make calls to kmalloc to dynamically allocate space for the 3 new test_struct elements.

    3. iterate through the list elements printing out their data fields

    4. remove all elements from the test1 list and add them to the front of the test2 list
    Look at existing kernel code that uses list to help you answer these questions.

    Homework 4
    Due: Monday Nov. 10, before 11:30 (the beginning of class)

    1. Do the following problems from the book (pp. 352-353):
      1. 8.17
      2. 8.18
      3. 8.19
      4. 8.20
      5. 8.23
    2. On a system with 1KB pages (1KB is 2 to the 10 bytes) and 1GB of logical address space (1GB is 2 to the 30 bytes), how many levels of page tables are needed if the outer most page table fits on a single page and if page table entries are 8 bytes (8 bytes are 2 to the 3 bytes)?

    Homework 5
    Due: Monday Dec. 8, before 11:30 (the beginning of class)

  • Do the following problems from the book:
    1. 10.11 (p.458)
    2. 11.3 (pp. 500-501)
    3. 11.11
    4. 11.12
    5. 11.15
    6. 12.16 (p.548)