Submission Instructions:

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. 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 using the SUBMIT program. Refer to the homework submission page on the class web site for additional submission instructions.

Non-Programming Problems:

1. Exercise 8.1

2. Exercise 8.3

3. Exercise 9.2

4. Exercise 9.5

5. Exercise 9.6

6. Exercise 9.7

7. Exercise 9.8

8. Exercise 9.10

9. Exercise 9.12

10. Exercise 9.16

Programming Problems:

For this assignment you will add to the Linux kernel a new synchronization mechanism, a reader-writer lock that supports priority inheritance. You will learn about wait queues and some of the synchronization primitives that the kernel provides. Finally you will construct a test program "proving" that your method works.

1. (20 pts.) Add to the Linux kernel a system call, rwlock, that provides a reader-writer lock. It should consist of the following prototype: int rwlock(int key, int action) The actions taken by the system call vary according to the action parameter:

   EVENT_CREATE: A new event is created. This event is a reader-writer lock that guarantees mutual exclusion for certain critical sections. If the parameter key is a number between 1 and 126 a new event is created with this value as its id number. If key is zero, then the kernel allocates the first unused id that it finds. If the inputed key value is a number above 126 or below 0, the system call returns an error code of -EINVAL. If there are no free slots -EAGAIN is returned. If the value of key matches a preexisting event, the system call returns -EBUSY. Otherwise the value of the new id is returned, signifying the key to be used in the future

   EVENT_DESTROY: An event is destroyed. If the parameter key matches a previously created event with no processes waiting on it, this event is de-allocated and a zero is returned to indicate success. If there are processes waiting on this event, -EBUSY is returned. If this event does not exist, your system call should return -EINVAL.

   READ_WAIT: A process wants shared access to a critical section protected by key. If nobody is using this resource - or the resource is only read-locked - then the system call returns zero to indicate success and the process is free to proceed. If the event is write-locked, the process is then put to sleep and made to wait for the event to be unlocked. Keep in mind that once the event is unlocked, you must make sure that correct lock operation is ensured among waiting processes and new processes that arrive. Also, if a waiting process is awakened (through a signal or an interrupt) and it is unsafe to proceed into the critical section, then you must put the process back to sleep. Otherwise, the system call returns zero and your process may proceed. As usual, if key refers to a non-existant event, you must return -EINVAL.

   READ_SIGNAL: Once a process is done reading data from its critical section it should call rwlock with this value. If key does not exist -EINVAL is returned. If key refers to an event to which our process does not have shared access, -EPERM is returned. Otherwise a zero is returned to indicate success, and the event is one step closer to not being read-locked (you will probably want to keep track of the number of readers). If the process making this system call unlocks the event, the appropriate processes are awakened. Ideally, you will test the type of lock requested by the first process in the waitqueue. If it is a readlock (this case should not typically occur, as readers do not block on readlocks), then you are to wake up every process requesting a readlock and allow them to proceed. Otherwise, if the process requests a writelock, you are to wake up only that one process.

   WRITE_WAIT: This value indicates that a process wants to have exclusive access to a critical section. If the event is protected by either a read-lock or a write-lock, this requesting process is put to sleep. As with READ_WAIT, if the sleeping process is awakened, it must ensure that is is safe to proceed. If it is not safe, it goes back to sleep on the waitqueue. Otherwise a zero is returned to indicate sucess. As usual, if key refers to an event that does not exist, -EINVAL is returned.

   WRITE_SIGNAL: This value indicates that a process is done needing exclusive access to its critical section. As with READ_SIGNAL the appropriate waiting processes are awakened and a zero is returned to indicate success. If the first process waiting requests a readlock, then you should wake up every process on the waitqueue requesting a readlock. Otherwise, the first process waiting is requesting a writelock, and you should only wake up that one process.
   If the value of key refers to a non-existent event then -EINVAL is returned. If key refers to an event to which our process does not have exclusive access, -EPERM is returned.

   LOCK_STATUS: This action indicates that you are to return one of 4 values indicating the lock's status: CREATED, UNCREATED, READ_LOCKED and WRITE_LOCKED. If the key value is out of range, you are to return -EINVAL here as well.

   Note: For all other action values your system call should return -EINVAL.

2. (10 pts.) Write a test program to demonstrate the effectiveness of your synchronization techniques. Your program should do the following things:
   1. Fork two readers and two writers.

   2. Have the first writer create a 10 megabyte file and fill it with the letter 'a'.

   3. Have the readers try to read the file but block while the writer finishes writing.

   4. Have the writer finish writing and then have the readers able to read the file.

   5. Have the second writer try to fill the file with the letter 'b' but block while waiting for the readers to finish their reading.

   6. Have the readers finish reading and the second writer begin writing.

   All file access should be syncronized through use of your system call as in the following example (of course you will be responsible for error handling as well):

   if (!newkey) newkey = rwlock(0, EVENT_CREATE); rwlock(newkey, READ_WAIT); read(fd, buffer, amount_to_read); rwlock(newkey, READ_SIGNAL);

3. (20 pts.) Add priority inheritance to your reader-writer lock. Any process that has locked access to a critical section has its priority temporarily elevated to that of the highest priority process waiting on the relevant event. You will have to add to task_struct extra fields to save the policy, priority and rt_priority of any boosted process. In addition these values must be restored once the process is no longer waiting on the event.

4. (10 pts.) Write a test program to demonstrate your implementation of priority inheritance. Your program should do the following things:
   1. Have a process create a 10 megabyte file and fill it with the letter 'a'.

   2. Have a realtime process run and do something unrelated to this file, so the writer is unable to finish.

   3. Have a seond realtime process request access to the file. The writer should inherit its priority, be scheduled for execution, and finish writing.

   Once again, every access to this file should be synchronized by your system call.

hints:

1. Start early and ask us any questions that you have.
2. Most of your sleeping processes should be put on a wait_queue. This is a circular linked list that has pointers to other processes. A good deal of your wait_queue manipulations will be governed by the sleep_on and __wake_up functions (defined in kernel/sched.c).
3. The above statement has a slight falsehood in it. The __wake_up function wakes up every single process on the wait_queue. You will want to have a separate version that has been tweaked to only wake processes up in accordance with the rwlock system call's requirements. Therefore, you don't have to worry about waking up seven writers only to put six back to sleep.
4. There are electronic man pages for wake_up and sleep_on. Please consult them for the proper syntax.
5. Start out by having you system call work with the general wake_up function. Afterwards, replace it with your special version.
6. Since linux's list primitives are not too helpful for implementing a user-list (not to be confused with a wait queue) here is the structure for one: struct user_list { struct user_list * next; struct user_list * prev; struct task_struct * task; }; And here are functions to manipulate it: void add_to_userlist (struct user_list * list, struct task_struct * task) { struct user_list * local_list, * nav_list; local_list = (struct user_list *)kmalloc(sizeof(struct user_list), GFP_KERNEL); local_list->next = list; local_list->task = task; local_list->prev = list->prev; nav_list = list->prev; list->prev = local_list; nav_list->next = local_list; } And here's another: void remove_from_userlist (struct user_list * list, struct task_struct * task) { struct user_list * next; next = list->next; while (next != list) { if (next->task == task) { next->prev->next = next->next; next->next->prev = next->prev; kfree(next); break; } next = next->next; } }