Written homework assignments are often designed to give you some practice answering exam-type questions. They are due at the beginning of class. I do not accept late written homework assignments. However, I encourage you to try them before exams even if you do not submit them for grading.

For all written homework assignments you are welcome, and encouraged, to work in small groups (2-4 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, please submit a single joint write-up of your group's solution with all your names on it.

Hand written write-ups are fine. We have latex and openoffice that you can use to create documents on our system, and of course Word and googledocs are other options. If you want to learn some latex here is a link to some documentation and also to some example files you can copy over and try out: latex examples and references.

Here are some problems from some of the book chapters we have recently covered. You do not need to submit solutions to these, they are just for your own practice:

1. Chapt 10: 1, 5, 9, 11, 18, 19
2. Chapt 11: 10
3. Chapt 12: 1 (answer for contiguous, linked, FAT, Unix inode), 3, 15, 16
4. Chapt 15: 1

Answer the following questions from the textbook:

1. 8.4 (assume a word is 4 bytes)
2. 8.11
3. 8.20
4. 8.25 (you can leave your answer as an expression, and assume 1 level of page table unless a problem gives you enough information to deduce that there must be more than on level...this problem does not)
5. 8.29
6. 9.3
7. 9.8
8. 9.15
9. 9.27
10. 9.34

For problems with decimal addresses, first convert the addresses to hex or binary, and you can leave your answers in hex or binary. You can use gdb to convert between representations:

$ gdb
(gdb) p/x 1234      # print decimal value 1234 as hex
(gdb) p/t 1234      # print decimal value 1234 as binary
(gdb) p/d 0x1234    # print hex value 1234 as decimal
(gdb) p/d 0b10110   # print binary value 10110 as decimal

Answer the following questions:

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 tobacco, 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.
   
   NOTE:
   this is a different version than the one we did in class.

   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 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 trying to read must wait because there is now a writer now waiting.

   In this version starvation of readers or 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?).

3. Use semaphores to solve the Sleeping Barber Problem.
   This is the problem that you started in class last week. Here is a link to its decription: Sleeping Barber

Here are a couple more problems to try (you do not need to submit these):

1. Use monitors to solve the Sleeping Barber Problem.
   

2. Use binary semaphores only to solve the Producer-Consumer problem. The solution in class used counting semaphores to block threads. When using binary semaphores only, you often need to add some state to decide when to block or not. Also, think very carefully about race conditions between a woken-up thread and any other thread: you don't want another consumer thread to get in and take the item that another blocking consumer thread was just woken up to take.

Answer the following questions:

1. In Piazza are questions for each of the in-class groups to answer about your scheduling policy. There are a few distinct questions you should answer. Each group member could take ~1 of these to answer first. Every group member should add to the group's write-up. If it seems complete by the time you add your part, add some commentary about why you agree with other posts (and explain your reasoning).

   If you were part of the mega-group on Wednesday, break back up into your original groups for the write-up.

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

3. 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:
   1. ave. waiting time
   2. ave turn-around time
   3. throughput
   4. total number of context switches
   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
   

4. Do the following problems from the textbook:
   1. 3.2 (and draw the process hierarchy tree)
   2. 4.4
   3. 4.7
   4. 4.11
   5. 6.4
   6. 6.5

Linked Lists in Linux

Examine Linux's support for linked lists. The interface is defined in the Linux source directory in include/linux/list.h. 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;
};

For the following questions, write code fragments just by hand; you do not need to sumbit code that compiles and runs.

USING ONLY FUNCTIONS AND MACROS from list.h to manipulate the list parts (and don't use the __ versions of functions), 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 and initialize two new empty lists, list1 and list2

2. write a for loop (in C) that adds 3 new elements to the end of the list1 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 list1 list and add them to the front of the list2 list