Individual non-programming problems are to be done individually. Group programming problems are to be done in your assigned programming groups. All homework submissions are to be made via Git using similar instructions as for previous homeworks but using the new repository for this homework. You will use an individual repository for submitting the individual non-programming problems, and a group repository for submitting the programming problems. Be aware that commits pushed after the deadline will not be considered. Refer to the homework policy section on the class web site for further details.

The Git repository you will use for the individual non-programming submission is

ssh+git://UNI@os1.cs.columbia.edu/git/UNI/hmwk3.written (Replace UNI with your own UNI)

The Git repository you will use for the group programming submission is

ssh+git://UNI@os1.cs.columbia.edu/git/TEAMID/hmwk3 (Replace TEAMID with your own TEAMID)

Individual Non-Programming Problems:

1. Exercise 6.10

2. Exercise 6.11

3. Exercise 6.12

4. Exercise 6.13

5. Exercise 6.14

6. Exercise 6.37

7. Exercise 7.11

8. Exercise 21.15

9. How and why does the implementation of a spinlock differ between a uniprocessor kernel versus a multiprocessor kernel configuration in Linux?

10. Describe the circumstances under which Linux uses atomic operations, spinlocks, reader-writer locks, and semaphores. Explain why each mechanism is needed.

Group Programming Problems:

Make at least ten commits with Git. The point is to make incremental changes and use an iterative development cycle. Follow the Linux kernel coding style.

Userspace controlled Semaphores. You will implement a system wide, userspace controlled, binary semaphore mechanism. The semaphore construct will be provided by a kernel-level implementation, but the policy for deciding which task to run when there is contention is determined by a userspace daemon that you implement. Given a set of tasks that are waiting on a semaphore, the userspace daemon will pick the task that gets the semaphore when it is available. This problem is worth 70 points.

1. You will implement the semaphore mechanism by adding six system calls:

   int sem_open(const char *name);					/* syscall number: 333 */
   int sem_close(int semid);					/* 334 */
   int sem_down(int semid);					/* 335 */
   int sem_up(int semid);						/* 336 */
   int sem_list(struct sem_info *buf, size_t len, int wait);	/* 337 */
   int sem_grant(const char *name, pid_t pid);			/* 338 */
   
   struct sem_info {
   	int locked; /* 0 is unlocked, 1 is locked */
   	int num_waiters;
   	struct {
   		pid_t	tgid;
   		pid_t	pid;
   	} waiters[]; /* the array size is num_waiters */
   	char name[]; /* semaphore name, null-terminated */
   };
   

   The scope of a semaphore is system wide (i.e. two separate processes may access the same semaphore). Semaphores are uniquely identified by their name. In other words, different processes can refer to the same semaphore by using the same name.
   
   
   • int sem_open(const char *name):
     • Returns a semid (a non-negative integer) associated with the argument name. The semid is a local identifier used by the calling process, much like a file descriptor returned by open().
     • A new semaphore is created if no existing semaphore is associated with name.
     • You may assume that names are smaller than PATH_MAX.
   • int sem_close(int semid):
     • Releases the semid so that it is no longer in use. An unused semid can be reused again through sem_open.
     • If no task references the semaphore anymore that was identified by semid, the semaphore should be removed from the system.
   • int sem_down(int semid):
     • If the referenced semaphore is not locked and there are no tasks already waiting for the semaphore, the function returns with the semaphore locked.
     • Otherwise, the current task sleeps in an interruptible state, until woken up by the userspace daemon or it becomes the only task waiting on the semaphore and the semaphore is unlocked.
     • If the task is interrupted while sleeping, your system call implementation should return -ERESTARTSYS.
   • int sem_up(int semid):
     • Unlock a specific semaphore.
     • Returns -EINVAL if the semaphore wasn't locked.
       Note that a process can unlock a semaphore that another process locked.
   • int sem_list(struct sem_info *buf, size_t len, int wait):
     • Fills the userspace buffer buf of size len (in bytes) with the list of all the semaphores in the system and their waiters and returns the number of sem_info structs written to userspace.
     • If wait is non zero, the current process waits until more than one waiter exists for an unlocked semaphore before returning.
     • If multiple processes are blocked calling sem_list, they should all be woken up when more than one waiter exists for an unlocked semaphore.
     • Returns -ERESTARTSYS if interrupted during the sleep, -EAGAIN if the userspace buffer is too small, the number of sem_info structs written on success.
     • The sem_info structure contains a list of tasks that are waiting on the semaphore. The list should be ordered by earliest arrival time in sem_down(). Note that when a task waiting in sem_down() is interrupted by a signal, this task will be the newest waiter when re-entering sem_down()
   • sem_grant(const char *name, pid_t pid):
     • Allows the task with the given pid to proceed in sem_down() on a given semaphore.
     • Returns -EINVAL if the semaphore is locked or no longer exists, or that the task referenced by its pid is gone.

   Your semaphore implementation should satisfy the following additional requirements:

   1. You should not wake up all tasks waiting on a semaphore, but only one at a time (avoiding the thundering herd).
   2. Each task should have its own set of semids, similar to the idea that each task has its own set of file descriptors. You will find it very helpful to maintain a semaphore descriptor table to keep track of the semids. When a task is created, it should be created with an empty semaphore descriptor table.
   3. When a task exits such that its semids are no longer in use, the referenced semaphores should be implicitly closed, which is the same behavior as close() with file descriptors.
   4. The system calls should return 0 on success unless stated otherwise, or the appropriate error code.
   5. The only kernel synchronization primitives that you are allowed to use for this assignment are spinlocks and atomic counters.
   6. Use the files kernel/usem.c and include/linux/usem.h to implement your semaphore mechanism.

2. We will provide you with a userspace daemon to determine the order in which waiting tasks gain access to the semaphore. You should test your kernel implementation with the provided userspace daemon to make sure it is working properly. The daemon will have the characteristics described below and is available at:

   ssh+git://UNI@128.59.23.135/git/hmwk3.userspace (Replace UNI with your own UNI)
   

   • The program should be semd and take no arguments. The daemon should not go in the background (no fork()). The daemon must not exit when an error occurs, but it should try to keep doing its job at all costs.
     
   • The daemon is responsible for ordering access to a semaphore among waiting tasks by using sem_list() and sem_grant(). When sem_list() returns, the daemon will choose the task to run which has the lowest tgid. If there is a tie, it should pick the oldest waiter. The daemon should print such a line when a decision happens (example with 3 waiters):

     printf("%-20s %d [%d, %d, %d] %d\n", semaphore_name, locked, waiters[0].pid, waiters[1].pid, waiters[2].pid, granted_task);

   • The daemon should print the list of the semaphores in the system when receiving a SIGUSR1 signal (killall -USR1 semd). The line format is (example with 3 waiters):

     printf("%-20s %d [%d, %d, %d]\n", semaphore_name, locked, waiters[0].pid, waiters[1].pid, waiters[2].pid);

     If there are no waiters, [] will be printed instead of [%d, ...]