|
|
|
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:
Kernel Assignments:
(Please be aware that these are extremely difficult,
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:
Warmup 1:
|
| 7%
|
| Warmup 2:
|
| 18%
|
| 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.
If you have a Windows 7 or Windows 8 machine, please follow the insturctions
here. If you don't
have a Windows 7 or Windows 8 machine,
please see my general installation notes for hints.
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.
|
|
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.
|
|
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 2/23/2014 (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).
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. Please keep the instructor 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 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.
|
|
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.
As an alternative to Dropbox, you can also use Ubuntu One, which
is part of Ubuntu 12.04.
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. You can as well use Ubuntu One and the process should be the same. 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:
- You need git first! A simple way to install this would be sudo apt-get install git
- 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:
- 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
- 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.
- 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
- 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
- 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!
- Unless people use different branches, or don't work on the files in the sames time. They are nullifying any collaboration going on.
Here is probably a better way:
- Create GitHub account and a BitBucket Account
- Add your @usc.edu email address to their account and verify the email
- Apply for:
- Use one or both services are remotes
for your repository and those will act as backup.
- You must make sure to make your git repository private.
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.
ps. the fork repo is private, so don't worry.
|
|
General Guidelines
for Programming Assignments
|
- 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.
- 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.
- 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.
- 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.)
- Late
submissions will receive severe penalties. Please see the
late policy.
- 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.
- 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.
- 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:
- 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 ...".
- 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, within 24 hours
of the submission deadline.
The first 3 lines of modifications are free
of charge. 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.
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.
|
|
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. 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 */
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.
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.
|
|
|