Access to programming assignments is restricted. These specs are private and you do not permissions to post/display these specs and your work based on these specs in a public place.

It goes without saying that if you change an assignment, you will not get credit for it.

Programming Assignments:

• PA1: add system calls to xv6, due 11:45PM, 6/3/2025. Electronic submissions only.
• PA2: kernel level threads, due 11:45PM, 7/1/2025. Electronic submissions only.
• PA3: mutex & condition variable, due 11:45PM, 7/1/2025. Electronic submissions only.
• PA4: MFQ scheduler, due 11:45PM, 7/15/2025. Electronic submissions only.
• PA5: memory management and copy-on-write, due 11:45PM, 7/29/2025. Electronic submissions only.

Late submissions will receive severe penalties. Please see the late policy. Please also be familar with the policy about using your "free late days".

We will use the following percentages for figuring out your overall grade for your programming assignments:

PA 1:

8%

PA 2:

23%

PA 3:

23%

PA 4:

23%

PA 5:

23%

All programming assignments must compile and run on a standard 32-bit Ubuntu 16.04 system running inside a virtual machine or inside an AWS Free Tier instance. One major advantage of using a virtual machine is that you can install as many copies as you want. For example, you can have one 32-bit Ubuntu 16.04 Linux system for development, one standard 32-bit Ubuntu 16.04 Linux system for final testing (and keep this virtual machine as "clean" as possible), one for doing experiments or whatever, etc.

We strongly encourage that you install a standard 32-bit Ubuntu 16.04 system on your laptop or desktop as soon as possible. To minimize hardware incompatibility issues, the PREFERRED way is to first install a virtual machine hypervisor platform (i.e., VirtualBox or UTM) onto your laptop/desktop and then install Ubuntu 16.04 into the virtual machine or create an AWS Free Tier instance.

Please note that a 32-bit Ubuntu 16.04 system would, once in a while, offer you to "upgrade" the system to the next release. You must NOT do that (or run the "do-release-upgrade" command). If you do that, you will not be running Ubuntu 16.04 any more and you may have to reinstall a brand-new standard 32-bit Ubuntu 16.04 system again.

The New Mac

Apple threw us a curve at the end of 2020 by switching to a non-Intel/AMD CPU for their new Macs. These systems are so new, it's not clear if VirtualBox would work on such a system. Even if VirtualBox works on such a system, it's not clear if you can run a 32-bit Ubuntu 16.04 system inside of it. If you have such a system, please take a look at what options you have.

It's imperative that you backup your code when you are doing a major programming assignment.

Use BitBucket

BitBucket is probably better than using DropBox because it combines version control and backup: BitBucket is like github.com in that it combines version control and backup. The main difference is that private projects on bitbucket.com stays private. You must NOT use GitHub.com even if it says that your repository is private. GitHub.com will make a private repository public automatically if you do not pay to keep it private! So, please do NOT use GitHub for this class. No matter what the GitHub.com website says, don't believe them because private code on it can magically become public for unknown reasons.

1. Create an academic account on BitBucket. You must use your USC email address.

2. You must make sure to make your git repository private. When you create a new repository, by default, the repository would be private. So, don't change that! If for some reason it's showing "public", select "private" before you create the repository). Failing to do so would be considered cheating (since you are allowing other students to cheat from you) and can lead to very serious consequences. If you cannot make your git repository private, you should NOT use BitBucket!

3. For a repository, you can change its settings and you can make the repository public. Please don't do that! If a prospective employer asks you to do that, you must tell them that you are not allowed to do that because you have agreed to the USC student conduct code when you were a student at USC and the USC student conduct code says that you must not cheat off other students and you must not knowingly allow other students to cheat off of you. You can email them a private copy of your code and you must not include anything you do not have rights to distribute.

A student had made the following comment about some advantages of using bitbucket.org:

I'm not sure if it is clearly stated on the website, but Bitbucket also comes with Jira that allows you to track the progress of features/bugs in your repo. You can basically create an entry stating issues associated with a certain commit and track them. You can also breakdown features of what you're implementing and assign them easily to different collaborators (easy to track and write a detailed breakdown contribution for grading too!). If you're an experienced swdev and are familiar with agile/scrum then this is a big plus over Github. If you decide to work in a group then this will allow you to collaborate/communicate more efficiently.

Once you have created a repository, say, "pa1", you can do the following on your laptop in a terminal:

1. Change directory (using the "cd" command) to your "pa1" directory then do the following only once:

       git init
       git remote add origin https://YOURACCOUNTNAME@bitbucket.org/billcheng/pa1.git

2. Add files to the repository. For example:

       git add *.c *.h Makefile *README.txt
       git commit -m 'Initial commit'
       git push -u origin master --tags

3. After you have made changes to some of the files, you can do the following to update the repository:

       git commit -a
       git push origin master --tags

   You should do the above at least once a day so that what's on your laptop do not get too much out of sync with the repository.

The above are just some examples to get you started quickly. To learn more about "git", please please read the free online book, Pro Git, mentioned in the textbooks section of our course description web page.

Use Shared Folder For Backups

A quick and easy to to backup is to copy all your files into the shared folder, i.e., the folder you are sharing with the host system. You should make this as easy as possible. Let's say that you put all your code in the folder called cs402 in the home directory of your Ubuntu 16.04 system. Assuming that your shared folder is in /Shared-ubuntu (suggested in the Ubuntu 16.04 installation instruction and additional instructions and you should change it if the location of your shared folder is different). Then you just need to do the following to make a backup:

    cd
    tar cvzf cs402-backup-`date +%m%d%y`.tar.gz cs402
    cp cs402-backup-`date +%m%d%y`.tar.gz /Shared-ubuntu
    ls -l cs402-backup-`date +%m%d%y`.tar.gz

Please copy and paste the above command and not try to copy it visually (watch out for the "backquote" characters). The above command create a file called cs402-backup-MMDDYY.tar.gz where MMDDYY is the current month, day, and year.

Other

You can also use something that comes with the system. If you are running Mac OS X, you can probably use iCloud to back up your code. If you are running Windows, you can probably use OneDrive to back up your code. You can also use Google Backup & Sync to backup your files.

Below are some very important information and requirement about our programming assignments. Please read them carefully so you understand all the rules we will stick to. If you are not sure about something, please send an email to the instructor for clarification.

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. You are not permitted to use any 3rd-party multithreading and networking/socket libraries (even if you explicitly ask the grader to install them before grading).

   On 32-bit Ubuntu 16.04, if a package you want to use is not on the list of approved packages, you must send an email to the instructor to ask the instructor to ADD that package to the list of approved packages and wait for approval. Also, only packages from the standard repository will be permitted (i.e., asking to use something like the "add-apt-repository" command to install packages from a non-standard repository will not be permitted).

   Here is the list of approved packages for this course:

   • cscope
   • dos2unix
   • git
   • gitk
   • git-core
   • libssl-dev
   • qemu
   • tcsh
   • tmux
   • valgrind
   • vim
   • xorriso

   If you would like to use a package that's not in the above list, please ask the instructor for approval. If the instructor approves, the list above will be updated!

   The best way to make sure that you have a standard 32-bit Ubuntu 16.04 system is to install from the virtual appliance for our class. Once you have set up such a "standard" system, please do not install any additional packages or make any major upgrades to make sure that you stay compatible with the "standard" system.

3. For warmup assignments, the final (submitted) program must run on a 32-bit Ubuntu 16.04 system since that's the only platform our graders are allowed to use for grading. Please note that we can ONLY grade your submission from a grader's 32-bit Ubuntu 16.04 system. It would be a good idea to test your program in another student's system to make sure that it runs everywhere. Also, regrades can only be done from a grader's 32-bit Ubuntu 16.04 system.

4. For any programming assignment, please do not hardcode any directory path in your code! If you hardcode something like "/home/YOURACCOUNTNAME/..." (where YOURACCOUNTNAME is the name of your account on your 32-bit Ubuntu 16.04 system) in your code to access something in your home directory, since the grader cannot change your code during grading, you may end up getting a very very low score. So, please make sure you are not doing this. Please understand that this is your responsibility.

   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 doing it outside of your code is much cleaner.

   By the way, Linux/Unix file system path can be as long as 256 bytes. So, if you have a char-array variable that will hold a file system path, make sure it's at least 256 bytes in size.

5. 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). We will grade based on the posted grading guidelines. To make sure that students cannot hard-code solution values mentioned in the grading guidelines into their code, the grading guidelines that the grader will be used for grading will use have different numeric values, commandline arguments, and test data files. Therefore, you should expect that we will change the testing data for grading. To the best of our effort, we will not change the grading script/procedure (although we may make minor changes if we discover bugs in the grading script or important things that we forgot to test).

   The general rule about grading is that you do not get credit for effort. You only get credit for getting your code to work correctly according to the spec and grading guidelines and produce the correct output. You need to learn how to use the debugger (and ask for help if you don't know how) to find bugs in your code even though some bugs can be extremely difficult to find. (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 correctly, it's your responsiblity to get your code to work correctly and produce the correct output.)

   Please understand that all the requirements mentioned in the spec and grading guidelines are serious requirements for all programming assignments. If you have a minor bug that causes a lot of tests to fail, you may end up losing a lot of points. (Therefore, for starters, don't name your executable to be anything other than the one mentioned in the spec and grading guidelines.) For the same mistake in your code, you may get points deducted over and over again (i.e., do expect "double jeopardy", "triple jeopardy", etc.).

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

7. All submissions will be timestamped by the submission server (i.e., a Bistro server) and receipts (known as upload tickets) will be issued. Whether your submission arrived to the server by the deadline is determined by the timestamp. Please do not delete any email that contains a submission ticket.

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

9. 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 procedures from other classes. When you make a submission, you will get an email containing a ticket and you should read the ticket carefully. It should look similar to the sample output given on the Bistro 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). 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. Please understand that a file system timestamp can be easily forged. The only kind of timestamp that we can accept is a timestamp in a ticket issued by a Bistro server under my control.

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. As clearly in spelled out in the academic integrity policy of this class, if you have a copy of any of our programming assignments written by someone else, looking at the code or running the code is considered cheating, let alone copying code from it.

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.

You are allowed to submit modifications via email to the instructor, up to 24 hours after the submission deadline (and preferably after the submission deadline). The first 3 lines of modifications are free of charge within this time frame if the submission is on time. 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 y to before (or after) line z

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. When you are adding a line, it would also be useful to mention what the line immediately above and below it look like.

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

Please note that this applies to source code, Makefile, and README files. Please understand that the grader is NOT allowed to modify your source code or Makefile during grading.

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

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. If you see something like "stack smash", it's another form of memory corruption bug (unless you really try to "smash the stack").

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. You can write to a portion of a stack space that is no longer valid. 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". We will talk about all this when we go over "dynamic storage allocation" in Ch 3 of the textbook.

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. My advise is to write your code very carefully and understand what every line of your code is doing and make sure that your code won't corrupt memory! It's much better to avoid creating nasty bugs than to debug and this good habit can save a lot of your time that you would have spent in debugging!

One thing you might try is to include the following commandline argument when you run gcc to compile your code:

    -fsanitize=address

The above enables AddressSanitizer to catch certain memory corruption bugs. It's not a cure-all, so please do not exactly that it will find all your memory corruption bugs.

Another 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 as a commandline argument when you run gcc to use this trick.

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.

On Linux, one very useful tool for finding memory corruption bugs is valgrind. If you have installed Ubuntu 16.04 on your laptop/desktop, you should give it a try. Just prefix your commandline by "valgrind" (or "valgrind --tool=exp-sgcheck" if simply running "valgrind" doesn't print any error messages, although this feature is experimental and may not work right) and read the output carefully. Figure out why valgrind is complaining and fix only the first bug it complains about. Although valgrind cannot catch every memory corruption bug, it does a pretty good job for relatively straight-forward memory corruption bugs. For more details, please see the warmup1 FAQ item about valgrind. By the way, from what I can tell, it seems to catch the same memory corruption bugs as using the address sanitization options in g++.

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. Please understand that, for programming assignments, there is absolutely no requirement that you don't have memory leaks. My recommendation is that you should ignore memory leak information from valgrind and only run valgrind when you suspect that you have memory corruption bugs and hope that valgrind can help.

If you have bugs that seems impossible to find and you have tried everything, the last resort is simply to do a code review and review every line of your code and make sure that they are not causing memory corruption. This is another good reason why you want to keep your code nice and clean.

Recently, I have heard about two more memory debuggers (although I have not tried them).

• cppcheck - Static analysis of C/C++ code. Checks for: memory leaks, mismatching allocation-deallocation, buffer overrun, and many more. To install on Ubuntu, do

      sudo apt-get install cppcheck

• libefence - Helps you detect two common programming bugs: software that overruns the boundaries of a malloc() memory allocation and software that touches a memory allocation that has been released by free().

      sudo apt-get install electric-fence

I haven't tried them. I'm hoping that they may be useful.