Assignment 2 (30 marks) Due: October 23, 2008 (11:59pm)

The purpose of this assignment is to provide you with detailed knowledge about processes, priorities, and the role of CPU scheduling in the Linux operating system. You will do so via a combination of systems-level programming in the OS kernel, as well as some application-level programming using some new or modified kernel system calls. The intention is for you to do your development and testing in a UML environment, but if you have root (superuser) access to your own dedicated Linux system, you are welcome to try your luck there!

The Wizard of OS: Rebooted

In its storied past, the Department of Computer Science was famous for its skits, plays, and theatrical productions at department parties, events, and reunions. One of the most brilliant ever was called The Wizard of OS (pronounced "Oss", where "OS" stands for "Operating Systems"). In this 1999 Broadway-style musical production, an evil system administrator exerted his will upon helpless system users, making them beg for their meagre annual printing allocations and every extra Megabyte of disk storage space.

While this evil sysadmin met an untimely (yet appropriate) demise, let us imagine a sequel, wherein such an evil system administrator is reborn (rebooted?) again today. In particular, you will play the lead role as a Linux system administrator, and you will use the ultimate power of Linux CPU scheduling to exert your will upon your hapless users.

There are three users on your system: Ari, Barrie, and Carey (A, B, and C, for short). You don't like Ari at all, and you would like this user to get very low scheduling priority, and thus lousy user-perceived system performance. Barrie is a regular user, who should get normal system performance. Carey is a user who coincidentally assigns your CPSC 457 grade, and thus you want to offer superior system performance to this user.

A Simple Spin Loop Program (2 marks)

In C, write a simple "spin loop" program that does nothing except consume lots of CPU cycles. Your program may look a bit like this:
i := 0;
while i < BIG_NUMBER do
    begin
        i := i + 1
    end
Adjust the value of BIG_NUMBER so that this program takes about 10 seconds to execute on a typical lightly-loaded Linux system. Show sample output using a command like: date ; ./looper ; date

Three User Accounts (3 marks)

Using your root (superuser) priviliges, create three user accounts on your Linux system, namely one each for users A, B, and C. Establish a user id, password, home directory, and shell for each. Copy your spin loop program to the home directory for each user. Verify that each user obtains similar system performance when executing the spin loop program, either individually or all at the same time.

Modifying the CPU Scheduler (10 marks)

Modify the CPU scheduler in the kernel so that it gives substandard treatment to processes created by user A (5 marks), and preferred treatment to processes created by user C (5 marks). Conceptually, you want to add a few lines of code to the CPU scheduling routines that look something like this:
  if UserID == A
  then priority = LOW
  else if UserID == C
            then priority = HIGH
            else priority = NORMAL /* the default Linux scheduling priority */
Your job is to decide where these lines of code go, and in which file, as well as what LOW and HIGH mean for the Linux CPU scheduler.

Compile and run your new Linux kernel. Verify that the priority levels for processes created by A, B, and C differ as intended. Hopefully, the spin loop execution times for users are perceptibly different as well, especially when they are running their processes concurrently. If not, feel free to tweak the scheduling a bit further.

The Superuser Interface (10 marks)

Write a C program that provides a command-line interface for the superuser to adjust the process priority levels for particular users to any level at any time. Call your program "victimize". (Note that writing this program may require adding or modifying some kernel system calls to suit your nefarious purpose.)

The "victimize" command can take up to three parameters, like this:
      ./victimize userid prioritylevel frequency

The first parameter (userid) is mandatory. It specifies either the name (e.g., Ari) or integer userid of the user to be affected. The second parameter (priority level) is also mandatory. It specifies a specific priority level that should be used for any future processes created by the specified user. The third (optional) parameter specifies the frequency (or interval) at which the process priority penalty should be invoked. For example, an interval of 1 means every single process created by that user, while an interval of 2 means every second process created by that user (e.g., odd-numbered ones, but not even-numbered ones), and an interval of 10 means every 10th process created by that user. The default value of frequency (if unspecified) is 1. In pseudo-code, this roughly means something like:
    if (UserID == A) && ((pid % frequency) == 0)
    then special treatment
    else normal treatment

Test your program and verify that it is effective in achieving its goals. For example, show the execution time of user A's spin loop program both before and after you adjust the priority level, as well as before and after you reset user A's priority to normal.

The User Interface (5 marks)

The final step of your evil master plan is to conceal your wrongdoings from the users. Modify the ps command in some way so that when invoked by user A (or C), the priority and status of processes appears to be perfectly normal, yet when invoked by you (root) it shows the actual priority level. You can probably do this either via shell programming, C programming, or kernel system calls (your choice). Show that the ps output for user A and user C differ in the desired way from the true ps output for the root user.

Bonus (5 marks): Extend your evil wrongdoing to handle the "nice" command, so that no matter what starting priority level is specified by the user, your victimize command overrides it and gives you ultimate control over the scheduling priority of user processes.

Bonus (1 mark): Who played the starring role as the evil system administrator in the Wizard of OS? (Hint: He still works on the U of C campus, but has been banished from the Department of Computer Science.)

Bonus (1 mark): Which current Computer Science faculty member(s) played a vital role in defeating the evil system adminstrator in the Wizard of OS?

Submitting Your Solution

Use the submit command to send your assignment solution to your TA. Among the materials submitted, please include any kernel files that you modified (e.g., fork.c, sched.c, unistd_32.h, syscall_table_32.S), along with a brief description of what you did, what works, and what does not. Also include the output from a sample terminal session to show that your kernel works as intended. This can be captured quite easily using the script command inside UML, like this:
    script ass2.out     (starts a terminal session script)
    who     (to show who is logged in)
    w     (to show who is logged in and what they are doing)
    ps -el | grep looper     (to show what relevant processes are running)
    cat /proc/12345/sched     (to see details of ari's process)
    cat /proc/12346/sched     (to see details of barrie's process)
    cat /proc/12347/sched     (to see details of carey's process)
    ps -el | grep looper     (to show what relevant processes are still running)
    ps -u ari     (to see what processes ari is running)
   
    any other commands that you think are worthwhile for your TA
   
    (control-D)     (ends the terminal session script)