Projects / Programming Assignments - CSCI 402, Fall 2012, TuTh Section

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 or 3. Please read carefully the section below on constituting teams.

Warmup Assignments:

• Warmup Assignment 1 (doubly-linked circular list in C), due 11:45PM, 9/14/2012. Electronic submissions only.
• Warmup Assignment 2 (token bucket emulation in C), due 11:45PM, 10/12/2012. Electronic submissions only.

• Kernel Assignment 1 (processes and threads), due 11:45PM, 11/9/2012. Electronic submissions only.
• Kernel Assignment 2 (VFS layer), due 11:45PM, 11/30/2012. Electronic submissions only.
• Kernel Assignment 3 (virtual memory), due 11:45PM, 12/7/2012. Electronic submissions only (this is an extra credit assignment).

Warmup 1:		12.5%
Warmup 2:		17.5%
Kernel 1:		35%
Kernel 2:		35%
Kernel 3:		17.5%	This is an extra credit assignment

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

    ~csci551b/bin/cs402calc 80 20 30 50

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

    ~csci551b/bin/cs402calc 80 0 50 50

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

    ~csci551b/bin/cs402calc 80 0 0 100

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.

Here is how teaming will work:

• [BC: updated 10/11/2012] You must decide on your project team for doing the kernel assignments before the end of day on 10/14/2012. Each team member should send the instructor an email listing their team members (and copy all other team members on this e-mail).
• 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. Please keep the TA informed if swaps 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 3 to a group starting from the beginning of the list
  • remaining students join these randomly formed groups (this is the only case where we may have 4-student 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.

• 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.

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 or g++/cxx, make, etc.) Please read the programming FAQ if you need a refresher on C file I/O and bit/byte manipulications.

2. Late submissions will receive severe penalties. Due to clock skews, electronic submissions of programming assignments will be accepted within 15 minutes after the specified deadlines without penalties. If you submit with the next 24 hours, you will receive 80% of your grade. Although in the first 50 minutes of this period, you will only lose 1% of your grade every 2 minutes. You will receive a score of zero after the first 24 hours (and your assignment will not be graded).

3. 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 keep your receipts/tickets.

4. 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.

5. 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.

• Here is my understanding of X. Am I right (or is this correct)?
  (You can do this for just about everything and in many different ways. I do not have the bandwidth to deal with too many questions like this.)

  The type of questions you should ask is, "this doesn't make sense to me for the following reasons".

• Here is what I am thinking of or doing... is it acceptable (or is this okay)?
  (What you are really asking is whether you will receive full credit or not. Wouldn't it be great if you can ask this during exams? It's not an appropriate question for assignments for the same reason it is not appropriate for exams. Although there is a difference between programming assignments and exams, but since you are asking about grading, it's inappropriate.)

  You should try your best and not trying to cut corners! You should also consult the grading guidelines!

• I don't understand X. Could you explain X to me?
  (It's your responsiblity to come to lectures and ask questions during lectures if there is something you do not understand.)

There is one exception to the rule for using code you did not write... Code given to the entire class in a class taken by you is permitted, provided that you cite such code properly. 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.
     */

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

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.

Chances are that you have corrupted memory. This usually means that you have corrupted memory a while back. It just happened that when you call free(), the corrupted memory caused a bus error or the execution of an illegal instruction. Bus errors and illegal instructions are basically the same thing as segmentation faults.

How does one corrupt memory? 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 */

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. I have not tried this tool and I do not know if it's suitable for our programming assignments. But I've heard good things (e.g., easy to use) and bad things about it (e.g., it only runs on Linux). Please try it at your own risk. Also, if you want to give it a try, incorporate it in your programs as early as possible. Don't start learning it when bugs are happening and deadlines are approaching.