Individual written problems are to be done individually. Group programming problems are to be done in your assigned programming groups. The deadline for group programming problems applies to both CVN and non-CVN students. All homework submissions are to be made via the submit programs. Refer to the homework policy page on the class web site for further details.

Individual Written Problems:

1. Exercise 7.8

2. Exercise 7.11

3. Exercise 8.2 (5 pts)

4. Exercise 9.3 (5 pts)

5. Why does Solaris 2 implement multiple locking mechanisms? Under what circumstances does it use spinlocks, blocking semaphores, conditional variables, and readers-writers locks? Why does it use each mechanism?

6. A file is to be shared among different processes, each of which has a unique number. THe file can be accessed simultaneously by serveral processes, subject to the following constraint: The sum of all unique numbers associated with all the processes currently accessing the file must be less than N. On paper only, write a monitor to coordinate access to the file.

7. In the Linux 2.4.2 kernel, what is the difference between how a spin lock is implemented for a uniprocessor versus a multiprocessor?

Group Programming Problems:

Programming problems are to be done in your assigned groups using the VM that has been assigned to your group. For all programming problems you will be required to submit source code, a README file documenting your files and code, and a test run of your programs. In addition, you should submit a cover sheet using either homework_work.txt or homework_nonwork.txt, depending on whether or not the programming assignment is completely working or not. For source code submissions, you only need to submit new source code files that you created and kernel source code files that you changed. You should clearly indicate your names, email addresses, and assigned group number on your submission. Each group is required to submit one writeup for the programming assignment.

The image of the kernel you build for this assignment should be vmlinuz.hmwk4. Grading for this assignment will be done based on vmlinuz.hmwk4. The kernel you use for this assignment should be the Linux 2.4.2 kernel you built and installed as part of Homework #2.

Background

The purpose of this assignment is to gain a deeper understanding of concurrent programming, including issues such as synchronization, communication, and threading. For this assignment we will be instituting a simple IPC mechanism (a message box), adding synchronization to it, and then writing some programs to test its efficiency. Finally we will compare the efficiency of this approach to that of a common thread library, pthreads.

1. (20 pts.) For this part, we will be adding a small ipc mechanism to the kernel, a message box. This message box is defined as follows (the elipses represent fields you will have to add): typedef struct _mailBox { void * data; int size; ... /* other control fields to enable synchronization and the like */ } mailBox; This mailBox can store messages of varying sizes and allow processes to read and write these messages. Your kernel will store a global mailBox array, containing 128 separate mailBoxes. To prove a user-interface to your mailBox array you must add the following system call: int mailBoxCtl(int opcode, union mailBoxParam * info); union mailBoxParam is to be defined as: union mailBoxParam { int size; struct _boxInfo { int box; void * message; } boxInfo; }; This system call is called where opcode is one of the following arguements:
   1. MAIL_BOX_INIT
      When this is the first argument, the kernel initializes a slot in a mailBox array to handle messages of size size. The array should contain 128 slots for mailBox structures and, once all slots have been initialized, the ENOMEM error should be returned whenever mailBoxInit is called. In addition, if size is less than one, EINVAL should be returned. Otherwise, the index number of the mailBox should be returned.
   2. MAIL_BOX_WRITE
      With this argument, your system call writes a message to the mailbox indicated by box. message should point to an area of memory of the size with which the mailbox was initialized. It the memory is invalid in any way, an error of EFAULT should be returned. If box is not the index of an initialized box, an error of EINVAL should be returned. Otherwise, a zero should be returned to indicate success.
   3. MAIL_BOX_READ
      With this argument, your system call reads from the mailbox box data that is copied to message. If it cannot successfully copy the amount of data that the mailbox was initialized to store the size of, an error of EFAULT should be returned. If box points to an invalid box, EINVAL is returned. Otherwise, a zero should be returned to indicate success.
   4. MAIL_BOX_DESTROY
      With this argument, your system call de-initializes the message box stored in slot box of the mailBox array. If box is the index of an uninitialized mailBox, EPERM is returned. If box is less than zero or more than 127, EINVAL should be returned. Otherwise zero should be returned to indicate success. Note that message should be set to NULL here.
   This part has two additional requirements:
   1. Since your mailBox should handle messages of arbitrary sizes, you must be able to dynamically allocate memory within the kernel. kmalloc is your best way of doing this. It operates similarly to malloc, with several differences: it operates in kernel space and takes a second argument to indicate priority. Its prototype is as follows: void * kmalloc (size_t size, int priority); In most cases (and in all cases for this assignment), this priority is going to be GFP_KERNEL, and for this assignment GFP_KERNEL is the correct priority. However you will want to check out the man page on kmalloc for more information, as well as the device drivers section on kmalloc..
      In order to free all memory allocated by kmalloc, you will want to use the kfree command, which operates in the same way as free.
   2. All pointers passed between user and kernel space must be appropriately verified through use of the copy_to_user or copy_from_user functions. Their prototypes are as follows: unsigned long copy_to_user(void *to, const void * from, unsigned long count); and unsigned long copy_from_user(void *to, const void * from, unsigned long count); These functions behave like memcpy, the main difference being that they verify that the user pointer is pointing to a location within the user's memory space. Whenever these functions fail, they return non-zero values. If this occurs, an error of EFAULT should be returned. Some examination of system calls (such as sched_setscheduler and sched_getscheduler) can make it pretty clear how these functions are utilized.
2. (10 pts.) Add synchronization your mailBox array. This consists of two mini tasks:
   1. Surround all mailBox initializations and destructions with a global spinlock. Usage of spinlocks is described is described in detail here. The main thing you can take from that section are the three functions: spin_lock_init(spinlock_t * lock); /* initializes spin locks */ spin_lock(spinlock_t * lock); /* try to grab lock, otherwise spin */ spin_unlock(spinlock_t * lock); /* free spinlock and let others try to grab it */ These functions are all you need to provide mutual exclusion for your entire mailBox array.
   2. Add to each mailBox structure an individual wait queue structure, which will allow you to synchronize access to it. More information on doing this can be found at the device drivers book's wait_queue section. From that section you will find the following functions useful: init_wait_queue(wait_queue_head_t * head); /* initialize wait queue */ sleep_on(wait_queue_head_t * head); /* sleep on wait queue if already blocked */ wake_up(wait_queue_head_t * head); /* wake up processes sleeping on wait queue */ In order to lock your mailBox (so a process can perform a test-and-set on its contents), you need to add two additional opcodes to your system call:
      1. MAIL_BOX_LOCK
         With this opcode, the system call takes a mailBox number as its input and blocks until it is able to get exclusive access to the appropriate mailBox, in which case it returns zero. If the mailBox number is out of the appropriate range, EINVAL is returned. EPERM is returned if the mailBox has not yet been initialized. Note that message should be set to NULL here.
      2. MAIL_BOX_UNLOCK
         With this opcode, your system call takes a mailBox number as its input and wakes up all processes waiting to get exclusive access to the appropriate mailBox, and returning the value of zero. If the mailBox number is out of the appropriate range, EINVAL is returned. EPERM is returned if the mailBox has not yet been initialized yet, or if it has not been locked by the process issuing the system call. Note that message should be set to NULL here.
   3. (15 pts.) As you probably remember from your math classes the Fibonacci sequence, which appears throughout nature, is a simple recurrence. It is defined as follows: Fib(1) = 1 Fib(2) = 1 Fib(n) = Fib (n - 1) + Fib(n - 2) The first 8 Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, and 21. For this question you will use your new system call to help you recursively compute Fibonacci numbers through a simple test program. Your test program should compute the nth Fibonacci number, where n is a parameter to your program, through use of a recursive function fib (which returns the Fibonacci number corresponding to its input).

      This sounds easy, but on each recursive call to fib, your program should fork a new process. This process should calculate its result (using fib and recursively forking additional processes if necessary) and then input into a mailBox its result. Note that it is possible either for all processes to share one mailBox which stores all results, or for you to create one mailBox for each new process. Benchmark your program with different values from 1 to 100. How long does it take it to solve the problem? Is there a point at which you can no longer initialize new mailBox structures or fork new processes? What Fibonacci number is interminably long to calculate for your program? Your analysis should include specific benchmarks of arbitrary numbers as well as casual observations.

   4. (15 pts.) Use the pthread library to benchmark the same Fibonacci problem from question 3. You can find some documentation on pthreads here, here, and here. You should be sure to use mutexes to protect all data shared between your threads. In addition, make your implemention match (in terms of the general strategy) that used for problem 3. This means that you should have the same sort of critical sections, and a similar arrangement of functions. You should note that you will not need to use your system call for this problem and can even design it outside your vm (but be sure that your final results are from within your vm).

      Pthreads for linux is implemented through kernel-level threads (based on clone). However, since linux's context switch time is extremely fast (and clone is a lightweight fork where two processes share memory space) they are close in performance to user-level threads. Do the same tests you did for question 3. Is this implementation significantly faster than your the other, with your system call. Why or why not? Where do you believe some bottlenecks lie? Your homework writeup should include all analysis.

   Notes:
   • It is possible to use a technique such as memoization to construct a linear time recursive solution to the Fibonacci problem. It is fine if you do this, but then be sure to use it for both the fork and the pthread methods so your benchmarks remain consistent. There is also a constant-time method for generating Fibonacci numbers (which does not utilize recursion) but you may not use that.
   • In line with this, you should be sure that your basic strategy is the same for both pthreads and forking solutions, the main differences being the style of synchronization (mutexes vs. wait queues) and the method of ipc (shared memory vs. your mailBox). But the way you fork processes and wait for them should be similar to how you are create threads and join with them.
   • It is important that you any fields that must be initialized in the mailBox array are initialized at boot time. This is done through the do_basic_setup() function which is briefly mentioned in the booting section of Linux Kernel 2.4 Internals.
   • Make your changes gradually. After implementing something, reboot and test it out before implementing something new.
   • Remember to back up your code regularly.