Written Homework

Written homework assignments are primarily to give you some practice answering exam-like 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 the midterm even if you do not submit them.

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 3
Due: Monday November. 21, before 11:30 (the beginning of class)

Do the following Paging, Segmentation, and Virtual Memory problems from the textbook:
  1. 7.13
  2. 7.17
  3. 7.18
  4. 7.20
  5. 7.21
  6. 7.23
  7. 8.5
  8. 8.8
  9. 8.28
  10. 8.35
There are lots of ways to convert values between binary, decimal and hexidecimal. One way is using gdb's print command with formating specified. gdb can also evaluate expressions. Hexidecimal values need the prefix 0x, and binary need 0b. Here are some examples:
(gdb) print/x  1234          # print out decimal value 1234 as hexidecimal
$1 = 0x4d2

(gdb) print/t  1234          # print out decimal value 1234 as binary
$2 = 10011010010

(gdb) print/d 0x4d2          # print out hexidecimal value 4d2 as decimal
$3 =  1234

(gdb) p/d 0b10011010010      # print out binary value 10011010010 as decimal
$4 =  1234

(gdb) print/t 0x4d2 >> 3     # print out binary result of bit shifting 4d2 right by three
$5 = 10011010

(gdb) print/x 0x4d2 + 100    # print out hexidecimal result of adding decimal 100 to hex 4d2
$6 = 0x536

(gdb) print/x 0x4d2 + 0x100  # print out hexidecimal result of adding hexidecimal 100 to hex 4d2
$7 = 0x5d2

Homework 2
Due: Friday October. 28, 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 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

Homework 1
Due: Monday 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 workload and the scheduling policy you came up with (what is the algorithm, how does it work.) The second paragraph should 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? are there parts of other group's policies that you could add to yours to make it better?

  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 (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
  4. 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 the 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