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 (or you can do them by yourself). Please read carefully the section below on forming teams.
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.
We will use the following percentages for figuring out your overall grade for your programming assignments:
All programming assignments must compile and run on a standard 32-bit Ubuntu 16.04 Linux system running inside a virtual machine on VirtualBox/VagrantBox. 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.
Looks like the ONLY working platform to do the kernel assignments is a 32-bit Ubuntu 16.04 (or Ubuntu 12.04). We strongly encourage that you install a standard 32-bit Ubuntu 16.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 hypervisor platform (i.e., VirtualBox) onto your laptop/desktop and then install Ubuntu 16.04 into the virtual machine. (If your CPU is slower than an Intel Core i3 and it has only 1GB of 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 this is the case, please contact the instructor as soon as possible to make sure that you are doing this correctly since setting things up like this can be very tricky and error-prone.)
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 from scratch again.
You are expected to team up in teams of 2 to 4 students for the kernel assignments (or you can do them by yourself). You can team up with students registered in any section. We generally would not recommend attempting the kernel assignments individually unless you have had significant prior exposure to C programming and debugging and working with large software systems.
Here is how team forming will work:
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 page. If you are considering to be kernel partners with another student, I strongly urge that you work with each other on warmup assignments before committing to be kernel partners.
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 (i.e., for failing to work as a team). 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 "cs402calc.txt" program that you can run on your Ubuntu 16.04 system. The syntax is:
chmod 755 cs402calc.txt cs402calc.txt 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:
cs402calc.txt 80 20 30 50The 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:
cs402calc.txt 80 0 50 50The 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:
cs402calc.txt 80 0 0 100The 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.
When I calculate your final class grade at the end of the semester, I will "normalize" each assignment grade according to the average and standard deviation for each grader and extrapolate your grade according to the overall class average and standard deviation. This "normalization" only applies to the grader-dependent part of your grade (i.e., without early/late submission extra credit and penalties and without class Google Group extra credit for kernel assignments. (If the overall score you get for an assignment is X, your early/late submission extra credit is Y percent, and your class Google Group extra credit for kernel assignments is Z, your grader-dependent part of the score is (X - Z) / ((100+Y)/100). After normalization of the grader-dependent part of your score, if your score is W, the score we will use to calculate your class grade would be W × ((100+Y)/100) + Z.) In the next two paragraphs, all the scores are grader-dependent part of your scores.
For example, if the average for a particular grader is 85 and standard deviation is 10 and you got a score of 87.5 (i.e., average plus half a standard deviation), your "normalized" score will be the overall class average plus half of the overall class standard deviation. This means that if you were graded by an "easy grader", your normalized score may be lower than your original score. If you were graded by a "harsh grader", your normalized score may be higher than your original score. This is not a perfect system. But I think it's a big improvement over not normalizing your scores and it's done this way so that you can have flexibility when you choose which section to enroll.
Since the purpose of grade normalization is to normalize the difference in grading among the graders. For a programming assignment, the highest possible normalized grade anyone can get is still the original maximum score assigned to that assignment, independent of the grader. Similarly, the lowest score one can get is 1 point given that an assignment was submitted for grading.
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.
The following was by Pradeep Nayak, who took CS 402 in Fall 2012.---------- Forwarded message ----------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
BitBucket is probably better than using DropBox because it combines version control and backup:
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). 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.gzPlease 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.
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 e-mail to the instructor for clarification.
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:
You are allowed to submit modifications via e-mail 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:
Afterwards, additional modifications cost 10 points per line until 7 days past the submission deadline. After 7 days past the submission deadline, an additional modification costs 25 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.
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 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") 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 more details, please see the warmup1 FAQ item about 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. Please understand that, for warmup assignments, there is absolutely no requirement that you don't have memory leaks.
Recently, I have heard about two more memory debuggers (although I have not tried them).