[linuxkernelnewbies] W4118 Fall 2009 - Homework 3

Thu, 08 Oct 2009 17:07:16 -0700

http://www1.cs.columbia.edu/~nieh/teaching/w4118/homeworks/hmwk3.html

Homework 3
W4118 Fall 2009
UPDATED: 10/8/2009 at 7:45am EST
DUE: Tuesday 10/20/2009 at 11:59pm EST

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://[email protected]/git/UNI/hmwk3.written (Replace UNI with your own UNI)

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

ssh+git://[email protected]/git/TEAMID/hmwk3 (Replace TEAMID with your own TEAMID)

Individual Non-Programming Problems:

Exercise numbers refer to the course textbook, Operating System Concepts. Each problem is worth 3 points.

  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.
Please complete and submit a private group programming assignment evaluation. For your convenience, the evaluation template to complete is already in your repository for your individual written assignment submission.

Group Programming Problems:

You will be using and modifying the Linux 2.6.27 kernel for this assignment. 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. The README should explain any way in which your solution differs from what was assigned, and any assumptions you made. Refer to the homework submission page on the class web site for additional submission instructions.

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.
      • 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.
      • Wakes up the necessary task.
    • 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 waiters exist for any semaphore before returning.
      • 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. You should not wake up all tasks waiting on a semaphore, but only one at a time (avoiding the thundering herd).
      • Returns -EINVAL if the semaphore no longer exists, or that the task referenced by its pid is gone.

    Your semaphore implementation should satisfy the following additional requirements:

    1. Each task should have its own set of semids, with one exception. Tasks created with the CLONE_SYSVSEM flag should share the same set of semids as their creator, in much the same way that tasks created with the CLONE_FS flag share the same file descriptors as their creator. You will find it very helpful to maintain a semaphore descriptor table to keep track of the semids.
    2. When a semaphore with semid X is closed, tasks that are waiting in sem_down() on this semid X should be woken up, and sem_down() should return -EINVAL.
    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. You will implement a userspace daemon to determine the order in which waiting tasks gain access to the semaphore.
    • The program name 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, ...]

Reply via email to