USC CSD Home
 

Projects / Programming Assignments - CSCI 402, Fall 2015, All Sections

You learn operating systems by doing. Modern operating systems are, unfortunately, too complex to envision programming within the context of a semester-long class. In CS402, we will use a stripped-down version of a modern OS which still has all the essentials necessary for understanding the concepts behind the subsystems that constitute today's OSs.

At the beginning of the semester, you are given a skeleton of an operating system with some of the lower-level machine specific parts filled in. In stages, during the course of the semester you are asked to fill in important missing pieces of various subsystems in the OS. The OS is based on the x86 architecture and should, in theory, compile to an image that can be run on a bare x86 machine. For simplicity, however, you will be testing and developing parts of the OS on an x86 emulator called Qemu.

The OS is written in C, so the programming assignments listed below assume familiarity with the C language. If you have not programmed in C before, we encourage you to pick it up on your own as quickly as possible before the semester starts.

You are allowed to do the kernel assignments in teams of 2 to 4 students. Please read carefully the section below on constituting teams.

 
Assignments
(Please note that access to programming assignment related information is restricted.)

Warmup Assignments:

GDB Assignments: Kernel Assignments: (Please be aware that these are extremely difficult and can be very very time-consuming, so you should get started on these assignments as soon as possible.)

 
General Information about Programming Assignments
We will use the following percentages for figuring out your over project grade:
[BC: updated 9/14/2015]      
Warmup 1:   7%  
Warmup 2:   18%  
GDB:   0%  
Kernel 1:   25%  
Kernel 2:   25%  
Kernel 3:   25%  
Looks like the ONLY platform to do the kernel assignments is Ubuntu 12.04 (with QEMU 1.0). We strongly encourage that you install Ubuntu 12.04 on your laptop or desktop as soon as possible. To minimize hardware incompatibility issues, the PREFERRED way is to first install a virtual machine onto your laptop/desktop and then install Ubuntu 12.04 into the virtual machine. (If your CPU is not Intel Core i3 or faster or has 1GB or less memory, running a virtual machine may be too slow and you may have to install Ubuntu 12.04 in such a way that you can dual-boot your machine.) If things are not working out and you cannot get Ubuntu 12.04 installed, please contact the instructor as soon as possible.

The warmup assignments must run on nunki.usc.edu.

 
Group
You are expected to team up in teams of 2 to 4 students for the kernel assignments. All team members must be registered under the same course lecture section. No exceptions! We would not suggest attempting the kernel assignments individually unless you have had significant prior exposure to C programming and working with large software systems.

Here is how teaming will work:

  • You must decide on your project team for doing the kernel assignments before the end of day on 10/4/2015 (two days after warmup 2 is due). Each team member must send the instructor an email listing their team members (and copy all other team members on this e-mail). (It would be acceptable if one person would send such an e-mail to the instructor and copy to all team members and everyone else in the team just do reply-all to confirm that the information is correct.) Please only use USC e-mail addresses (and not gmail addresses).
  • Once the team is formed and the kernel assignments started, the only way you can change your team is by mutually agreed swaps with another team. You can also break up the team if everyone in the team agrees to the breakup. Please keep the instructor informed if swaps or breakups are being done.
  • All students not belonging to a group by the group forming deadline will be assigned a group by the instructor using a randomized algorithm (unless you have indicated that you want to do the kernel assignments by yourself) as follows:
    • form a random list consisting of these students (by a random drawing)
    • assign 4 to a group starting from the beginning of the list
    • remaining students join these randomly formed groups
    • boundary conditions? Let's hope we won't get there.
    We know that this algorithm is far from perfect, that's why it is specified before the semester starts. This way, you can plan how to form teams given that you know our algorithm for assigning teams.
If you have not worked in a team on programming projects before, please be aware of the following:
  • More is not necessarily better: having more people on the team also increases the coordination overhead.
  • In many teams, some of the contributors start to assume a passive role, leaving others to assume the larger burden of the work. To avoid this, you should have frequent team meetings, carefully delineated programming responsibilities, and internal deadlines that help ensure that everyone does their part on time.
  • It's very risky to work with someone you don't know. You are strongly encourage to "work with" other students when you are doing the warmup assignments. "Work with" means to work together at a high level (i.e., not coding). When it comes time to write code for the warmup assignments, you must do it completely independently. This way, you can learn the habits of potential teammates.
Finally, and this is very important... If you cannot form a team of your own and end up in a team that cannot get the kernel assignments to work (because there are problem members of the group), is this unfair to you? No! Because you did have options. Given that you know that this is the rule, what should you do? You should either (1) form your own team and do it as early as you can, or (2) do the kernel projects yourself. If you cannot form your own team and didn't want to do the kernel assignments yourself, we cannot grade you differently given our fairness policy.
 
How To Find Partners?
If you don't belong to a team and would like to join an existing team or find other students in your section to form a new team, please visit this new page that I have created. Since this page is new this semester, if you see any error messages, please let me know as soon as possible.
 
Grading for Group Projects
For kernel (group) projects, half the grade is "team grade" (where everyone gets the same score) and half is "individual grade". In the README file your team will submit, you must (1) specify how to split the points (in terms of percentages and must sum to 100%) and (2) give a brief justification about the split. If you don't specify anything, we would take it as an equal-share split.

We would like to encourage that everyone contributed equally to the team (or at least for you to declare as so in your README file). Therefore, your scores are maximized when you have an equal-share split. There may be penalty for not dividing the scores equally. The actual equations we will you to determine the scores is a bit involved. The basic idea is to use "standard deviation" to measure how skew the amount of sharing is going on. When you have an equal-share split, the standard deviation is zero, that corresponds to an upper bound (i.e., no penalty). When you have a completely skewed distribution (e.g., 0/0/100 split), you would get the highest standard deviation and the most penalty. To make things easier to figure out, we have provided a program on nunki.usc.edu/aludra.usc.edu for you to run. The syntax is:

    ~csci551b/bin/cs402calc grade p1 p2 ...
where grade is the grade the grader gave and p1, p2, ... are percentages. For example, if the grader gave 80 points and the breakdown is 20/30/50%, you should run:
    ~csci551b/bin/cs402calc 80 20 30 50
The output (among a bunch of other information) would show that the final scores for the 3 students will be 55.695, 63.5425, and 79.2375. So, the person who contributed the most did not get 80 points. A small penalty here.

If the grader gave 80 points and the breakdown is 0/50/50%, you should run:

    ~csci551b/bin/cs402calc 80 0 50 50
The output would show that the scores will be 40, 70, and 70. In this case, it's more apparent that there are penalties for not being able to figure out how to share responsibilities among 3 students. So, may be it's not worthwhile to assign such percentages!

If the grader gave 80 points and the breakdown is 0/0/100%, you should run:

    ~csci551b/bin/cs402calc 80 0 0 100
The output would show that the scores will be 40, 40, and 80. In this case, the 3rd student did all the work and should get all the 80 points. The other two students did not contribute to the team and got "free rides".

It's totally up to your team to decide how you want to assign the splits. If there are disagreements, the instructor will have to interview the team members (and ask questions such as, "What do this code do?") and make a decision.

 
Backup and Collaboration
It's imperative that you backup your code when you are doing a major programming assignment. For the kernel assignments, it's also imperative that your team have a reasonable way to collaborate and share code (and be able to modify them individually and then merge the changes). If you have Ubuntu 12.04 installed, you can install git for collaboration and version control and Dropbox as your personal cloud where you can backup your source code and documentation.

Use DropBox

The following was by Pradeep Nayak, who took CS 402 in Fall 2012.
---------- Forwarded message ----------
From: Pradeep Nayak
Date: Thu, Oct 18, 2012 at 11:55 AM
Subject: [usc-cs402-f12: 822] Using Dropbox to manage and backup your code!
To: usc-cs402-f12@googlegroups.com

As professor mentioned in class, it's important to back up your code.I already use Dropbox for a lot of other things, hence using that as an example here. If you don't have a dropbox account, you can create one by using this link : http://db.tt/oLKgb3hw :-)

We will be using Dropbox to version control your code with git and also backing it up on Dropbox.

Things you need installed before you start:

  1. You need git first! A simple way to install this would be sudo apt-get install git
  2. Setup Dropbox for Ubuntu:https://www.dropbox.com/install?os=lnx. If you followed the default install procedure i.e (I agree to license terms -> Next ->.. Finish) you would be able to see a folder called Dropbox under /home//Dropbox where username is the current user you are logged in to the machine
Lets get started:
  1. Set up a bare central repository on Dropbox. This is the place where you would be backing up your code along with version control
            cd ~/Dropbox
            mkdir kernel-project.git
            cd kernel-project.git
            git init --bare
  2. Clone your remote repository on to your home directory. This is where you would be working on your project, committing changes etc.
            cd ~
            git clone ~/Dropbox/kernel-project.git

    You would now see a folder called kernel-project in your home directory.

  3. Lets make the first commit:
            cd ~/kernel-project
            echo "Hello World" > foo.txt
            git add .
            git commit . -m "First Commit"

    Now you have committed the changes to your local repository. Next step is to push your code to Dropbox

  4. Push code to Dropbox. Make sure you are in the kernel-project folder
            git push origin master
    So if your Dropbox is already running in background it would update your changes to Dropbox cloud. If not, the next time open Dropbox it would sync your changes on to the Dropbox servers.
Also, git is awesome to use when you are working on a collaborative project like this.

Useful resources:

Some people have reported problems with hosting their git repository on dropbox. The has two problems, one of them is more serious than the other
  1. git runs garbage collection and updates its indexes every now and then. When dropbox is used, it may partially update an index and not other parts of the disk and any mistimed sync will cause damage to repo and loss of the index. This has seen been reported enough times that there is really no doubt that this does happen!
  2. Unless people use different branches, or don't work on the files in the sames time. They are nullifying any collaboration going on.

Use GitHub

This is probably better than using DropBox because it combines version control and backup:
  1. Create GitHub account and a BitBucket Account
  2. Add your @usc.edu email address to their account and verify the email
  3. Apply for:
  4. Use one or both services are remotes for your repository and those will act as backup.
  5. You must make sure to make your git repository private (when you create a new repository, you must select private immediately). Failing to do so would be considered cheating and can lead to very serious consequences. If you cannot make your git repository private, you should NOT use GitHub!
There are more suggestions! Here's one from Lishi Jiang, who is taking CS 402 in Spring 2014.
---------- Forwarded message ----------
From: Lishi Jiang
Date: Wed, Feb 26, 2014 at 4:49 PM
Subject: [usc-cs402-s14: 563] use GitHub for kernel assignment
To: usc-cs402-s14@googlegroups.com

Hi all,

Just want to share my experience with git/GitHub today.
First, unpack weenix-assignment-2.0.0.tar.gz. Open weenix-assignment-2.0.0/weenix.

    $ git init
Before start, set up your account
    $ git config --global user.name "John Doe"
    $ git config --global user.email johndoe@example.com
Third go to GitHub, create a private repo online. (very easy, free for students, goto https://education.github.com/)
    $ git add .
    $ git commit -m 'First commit, all files original.'
    $ git remote add origin http://github.com/username/private_repo_name.git
    $ git push origin master
it will require your username and password. Then the original project is on the GitHub.
After the setup. You can add collaborators in your repo settings online.
Then other teammate can fork the repo and clone the repo from their account, send the pull request. If the original repository is private, the forked repository will also be private.
 
General Guidelines for Programming Assignments
  1. The class programming assignments will be C code to be developed on a UNIX environment. No other programming language will be accepted and your program must compile and run with a Makefile as is. You must be familiar with the UNIX development environment (vi/pico/emacs, cc/gcc, make, etc.) Please read the general programming FAQ if you need a refresher on C file I/O and bit/byte manipulications.

  2. For the warmup assignments, you should use your USC accounts and preferably work on the Solaris machines via ssh for testing. The final (submitted) program must run on nunki.usc.edu because we are going to test it in that environment. Please note that we can only grade your submission from the grading account on nunki.usc.edu. It would be a good idea to test your program in another student's account to make sure that it runs everywhere. By the way, you should not do the whole program development there, as nunki is a general purpose server - under heavy use by many students. But you should definitely test your program there. Please also note that regrades can only be done from the grading account on nunki.usc.edu.

  3. For the warmup assignments, please do not hardcode any directory path in your code! If you hardcode something like "/home/scf-..." or "/auto/home/scf-..." in your code to access something in your home directory and the grader cannot access these directories during grading, we will not be able to make changes to the overall filesystem on nunki. You may only get a score of 1 point as a result of this. So, please make sure you are not doing this. All path should be specified externally, as far as your code is concerned.

    The only path that you can hardcode is probably "/tmp", and even that is not a great idea. What you can do is to define such a path as a compile time variable and pass it to your program. For example, you can use the following to define TMPDIR to be equal to "/tmp":

        gcc ... -DTMPDIR=\"/tmp\" ...
    Then in your code, you can do:
        char tmpfile[256];
    
        snprintf(tmpfile, sizeof(tmpfile), "%s/XXXXXX", TMPDIR);
        ... mkstemp(tmpfile) ...
    Basically, using a compile time variable is the same as doing the following in your code:
        #define TMPDIR "/tmp"
    The difference is that you are doing it outside of your code, and this is cleaner.

  4. We will make grading guidelines available at least one week before an assignment is due. We will grade based on the grading guidelines (may be with minor adjustments). The general rule is that you do not get credit for simply coding. You only get credit for getting your code to work correctly according to the spec. (Please do not ask the grader to look at your code so you can get more points because you have done a lot of coding and your code looks like it should work. If your code is close to working, it's your responsiblity to get your code to work.)

  5. Late submissions will receive severe penalties. Please see the late policy.

  6. All submissions will be timestamped by the submission server and receipts (known as tickets) will be issued. Whether your submission arrived to the server by the deadline is determined by the timestamp. Please do not delete your receipts/tickets from your home directory on nunki.usc.edu.

  7. If you sign up late for this class, you are still required to turn in all the programming assignments on time or you will receive a score of zero for the applicable assignments. No exceptions! This requirement also applys to students on the wait list.

  8. You must follow the Electronic Submission Guidelines when you submit programming assignments. Please note that this is a fairly new procedure and very different from previous procedures. Please make sure you read the output of the bsubmit program carefully. It should look similar to the sample output given on the bsubmit page. The timestamped upload ticket issued by the Bistro server is a proof that the server has received your submission (and you do not need additional proof such as an e-mail confirmation). You should also verify what you have submitted is what you intended to submit by following the Verify Your Submission procedure. Please note that it is your responsibility to ensure that you have submitted valid submissions and that you have received timestampted upload tickets for them.
 
Using Code Written by Other People
You must NOT submit code you (or your group) did not write yourself (or yourselves). You have committed plagiarism if you submit work done by others and claim that it's your own work. It should be clear that you cannot use code written by other students in a previous semester no matter what.

There are two exceptions to the above rule:

  1. Code fragments done by yourself for another class or given to you as class resource in another class (which you have taken and completed) must be cited explicitly. Just mention that you got some code in another class in your README file is no good. You must surround such source code by the following comment blocks:
        /*
         * Begin code I did not write.
         * The code was given to the (class information) in
         *     (semester, year) at (institution name).
         * If the source code requires you to include copyright, put copyright here.
         */
        [ code you did not write yourself ]
        /*
         * End code I did not write.
         */
    If you decide to make changes to this type of source code, you should change the phrase "This code was given to ..." to "This code was derived from code that was given to ...".

  2. You are allowed to use code given to you as part of this class (i.e., from textbook or lectures). You do not need to cite such code.
 
Modifications after Deadline
You are allowed to submit modifications via e-mail to the instructor, up to 24 hours after the submission deadline. The first 3 lines of modifications are free of charge within this time frame. Additional modifications cost 3 points per line (each submission is worth 100 points).

One line (128 characters max) of change is defined as one of the following:

  • Add 1 line before (or after) line x of file y
  • Delete line x of file y
  • Replace line x of file y by 1 line
  • Move line x of file z to before (or after) line y
where x and z are line numbers and y is a specified file. Please also mention what line z looks like so I can verify that I have made the modification at the right place.

Afterwards, additional modifications cost 12 points per line until 7 days past the submission deadline. After 7 days past the submission deadline, an additional modification costs 30 points per line.

Please note that this applies to source code, Makefile, and README files.

Just want to be very clear about this... The free 3 lines of changes are only applicable if you submit them within 24 hours of the submission deadline. Also, a "modification" is NOT considered a "new submission". So, sending a "modification request" will not change the timestamp of the submission we grade.

 
Segmentation Faults and Bus Errors
I often get questions regarding segmentation faults and bus errors. Sometimes, these occue when one calls library functions such as malloc() or free(). Some students think this is some kind of a system bug. Well, it's often not. I will try to answer this type of questions here once and for all.

Chances are that you have corrupted memory (or have corrupted the memory allocation chain). Memory corruption means that a memory location got modified in a bad way and you have no idea when it happened or how it happened. It's as if it has gone bad all by itself. But since it really cannot go bad all by itself, it just be your code that somehow corrupted memory! When you notice that memory corruption has occurred, this usually implies that you have corrupted memory a while back. It just happened that when you call malloc() or free(), the corrupted memory caused a bus error or the execution of an illegal instruction. By the way, bus errors and illegal instructions are basically the same thing as segmentation faults.

How does one corrupt memory (or corrupt the memory allocation chain)? You can write beyond an allocated memory block. You can free the same object twice. You can free an object that was not allocated. You can write to an object that's already freed. These bugs are hard to find because most of the them you only see that there is problem long time after you have corrupted memory. If you have access to a professional/expensive debugging tool, it may be helpful. Otherwise, you just need to do binary search and see where the bug(s) might be. There's no magical cures in debugging memory corruption bugs, not even for professionals! I, unfortunately, do not have any magic tricks that can help anyone find memory corruption bugs.

One thing you might try is to temporarily turn off memory deallocation (if you suspect that you have freed the same object twice or freed an object that was not allocated). You can do the following to define free() as a no-op in a common header file when you are debugging:

    #ifdef DEBUGGING_MEMORY_CORRUPTION
    #ifdef free
    #undef free
    #endif /* free */
    #define free
    #endif /* DEBUGGING_MEMORY_CORRUPTION */
Then use -DDEBUGGING_MEMORY_CORRUPTION are a commandline argument when you run gcc to enable this code.

As your code gets more and more complicated, you may get more of these bugs. This is one reason why you want to keep your code nice and clean.

If you develop your code on a Linux machine, you can try valgrind. If you have installed Ubuntu 12.04 on your laptop/desktop, you should give it a try. Just prefix your commandline by "valgrind" (or "valgrind --tool=exp-sgcheck") and read the output carefully. Figure out why valgrind is complaining and fix EVERYTHING it's complaining about. Although valgrind cannot catch every memory corruption bug, it does a pretty good job. For warmup programs, it's worthwhile to make your code runs on both Linux and Solaris because you can use valgrind to look for bugs on Linux. This way, you won't have to look for all your bugs on Solaris which can be more painful!

If you have installed Ubuntu 12.04 on your laptop/desktop, just use the following command to install valgrind:

    sudo apt-get install valgrind

If your program is memory-corruption free and you just want to look for memory leaks, you can run your program by prefixing it with "valgrind --leak-check=full" and see what valgrind has found for you.

 

[Last updated Sat Sep 19 2020]    [Please see copyright regarding copying.]