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 these instructions. 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.

Individual Non-Programming Problems:

1. Exercise 2.6

2. Exercise 2.16

3. Exercise 3.3

4. Exercise 3.7

5. Exercise 3.10

6. Exercise 4.9

7. Exercise 4.11

8. Read the Linux source code and construct a state diagram to represent the relevant states that a process may be in at any given time. For each state, give the exact name used for the state in the source code.

9. Describe what happens in the Linux kernel when a timer interrupt occurs. Be sure to list the procedures that are called and explain the function of each.

10. Describe what happens in the Linux kernel when a fork system call occurs. Be sure to list the procedures that are called and explain the function of each.

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.

1. Read/Write Limit System Call (30 Pts.)

   Changing the default behavior of a system call to cause it to behave in a different though legitimate way can be a useful way to test whether programs that use that system call are written correctly. You will change the behavior of read and write for this purpose.

   1. Implement a system call set_limit to set a maximum limit on the number of bytes that can be read or written for the read and write system calls on the caller; new processes should inherit the limit of their parent. The system call prototype is as follows:

      #define READ 0
      #define WRITE 1
      int set_limit(int fun, size_t max_bytes);
      //fun : function - READ or WRITE
      //max_bytes : Setting limit on number of bytes to read or write per call
      

      Your system call should be numbered 251. Your system call should store the value of either max_read_bytes or max_write_bytes depending on the first argument passed to set_limit. The default value for these variables are set to zero so that other processes just ignore the limit value. Return zero on success and negative error on failure.

      HINT: task_struct is present in include/linux/sched.h. Retain max_read_bytes and max_write_bytes values on fork(), changes to be made in kernel/fork.c.

   2. Modify the read and write system calls as follows. If the number of bytes passed is greater than the limit, then read or write bytes should be set equal to the maximum limit, and the call should return the limit value. Otherwise, retain the default behavior.

   3. Write a user space program to test the above behavior. Call set_limit for write and read with different limits. The test program should take the following command line arguments:

      read_value
      write_value
      command (ex cat, cp...)
      any other arguments required for the command
      

      Test your cp program from Homework 1. Do you see any abnormal behavior? Explain why or why not.

2. See the Scheduling of Tasks System Call (40 Pts.)

   Operating systems such as Linux give the illusion of being able to run multiple processes at the same time by multiplexing the CPU among multiple processes at a fine granularity. You will create a system call so you can see how often Linux switches the CPU among different processes.

   1. Implement a system call schedinfoto create an ordered list of the sequence of tasks that have been run on the CPU. The system call prototype is as follows:

      int schedinfo(struct slice_info __user *si_buf, size_t len);
      

      struct slice_info is used to represent an instance of a task being run on the CPU. It indlcates which task was run, when it started running, and when it stopped running. It is defined as follows:

      struct time_span
      {
         struct timeval start;
         struct timeval end;
      };
      
      struct slice_info
      {
         pid_t pid;                    /* pid, not tgid, of the task */
         char comm[16];                /* task common name */
         struct time_span slice_span;  /* array containing slice timing info */
      };
      

      Your system call should be numbered 285. The function to implement the system call should be in a new file kernel/schedinfo.c. It should fill a userspace buffer with a struct slice_info array sorted such that:

      si_buf: A pointer to the userspace buffer to fill.

      len: The length of the buffer in bytes.

      si_buf[i].slice_span.start >= si_buf[i+1].slice_span.start

      It should return the number of struct slice_info that got written in the buffer when successful. Otherwise, it should return -EFAULT if a userspace memory access failed, or -EAGAIN if the buffer was too small to write the struct slice_info of every task. You should understand what these error codes mean. You only need to report the requested information for tasks that still exist in the system. Tasks that have already terminated and have been cleaned up can be ignored.

      The system call only needs to work assuming a single CPU. You should make sure the settings of your VM are configured to use one CPU only.

      There are many ways to implement this functionality. You may not assume any fixed limit on the number of possible times a task can be executed, but you should discard data that is too old to avoid unbounded memory consumption. We recommend that you keep the slice timing information of each task in a list within its task_struct using the kernel list manipulation functions. Slice timing information that refers to a task execution that occurred more than a minute ago can be discarded.

      There are two kernel functions that you should examine carefully to help you implement the requested functionality. schedule() determines when tasks are run on the CPU and you will need to insert some code in this function. migrate_live_tasks() gives an example of how to iterate through the list of tasks, and you should use that code as a template. The read_lock() and read_unlock() functions prevent another process from modifying the task list while you are reading it. schedinfo should fill the userspace buffer (if big enough) with all the struct slice_span that are non-zero from every process.

   2. Create a user program readtask that takes no arguments and prints the scheduling information. If the provided buffer to schedinfo is too small, the program should not fail, but retry with a larger buffer. How this userspace buffer grows is your choice. For each struct slice_info received, it should print a line of this format:

      printf("[%d]\t%-16s -- %8dus to %8dus (%8dus)\n", si->pid, si->comm, st->start - now , st->end - now, st->end - st->start);
      

      "now" is the time right before calling schedinfo. You may use timersub (man timersub). If st->end is equal to 0 because the corresponding task is currently running, print 0 instead of now - st->end. Units are microseconds (us).