In every OS, there are some fundamental choices to make about what types of features to include. To begin, let’s discuss an example of an existing OS which has some very interesting features.
There is currently a North Korean operating system called Red Star 3.0, which is a fork from Fedora, a Linux-based OS. However, this operating system has some rather unique features. First, it enacts automatic watermarking, where every file has a hidden watermark with metadata about itself. This is accomplished through the use of steganography. In addition, it has tamper-resistant OS modification, meaning that it can only run programs that are on a certain cleared list.
While these features may not be ideal for some cases, we can see that they offer a tremendous amount of control, which is what operating systems are all about.
We will have 17 lectures this quarter.
Website
The class website is http://web.cs.ucla.edu/classes/winter16/cs111/. Here you can find the syllabus, schedule of readings, lab specifications, and further resources.
Textbook
The textbook for this course is Principles of Computer System Design by Saltzer and Kaashoek, ISBN: 9780123749574
Tests
Exams are open notes and open book.
Labs and minilabs
The labs and minilabs will cover shells, kernel hacking, file systems, networking, scheduling, and virtual memory. The due dates and specifications are posted on the class website.
Design Problem
These problems require designing a system from scratch, based on a problem from the book or one you have come up with on your own. It includes a written report and code as necessary. More information can be found here.
Paper
The paper will be a 2-4 page report on a contemporary OS topic. The topic should be so contemporary that it only comes out in the next few months!
Scribe notes
Groups can sign up to take notes for each lecture. These notes must be turned in as described on the class website, and will be posted online before the midterm and final as an additional study resource. More information can be found here.
Deadline and lateness penalty
From the class website: “All assignments are due at 23:55 (i.e., five minutes before midnight) on the date specified. Design problem due dates are one week after the normal lab due dates, with presentations and slides due one week after that; except for Lab 4 where everything is due on the last day of instruction (please ignore statements about due dates in the design-problem web page, as that's for a previous edition of the course). Scribe notes are due one week after the lecture, except for lectures during the last week (due Friday of the last week).”
The lateness penalty for an assignment that is N days late is 2^N-1 points marked off.
Partners and groups
Labs and design problems are to be completed in partners or individually. You do not have to have the same partner for every assignment, and just one copy is turned in for each pair. Scribe notes may be completed in groups of up to four. All other assignments must be completed individually, including minilabs.
Grading Average
The goal is to have a mean of 50% on all assignments, so as to have a good bell curve. However, TAs will often struggle to be this harsh, so the real average may be higher.
Notice that the above three resources all used the word “control” in their definitions. However, there are some major missing issues left out in the definitions: resource management, reliability and error handling, and security.
Say, we have a big file of size ~10^9 bytes and name it “big”. The file is stored in ZFS (Zeta File System). Files in ZFS Note that we can create files with the truncate command. For example, the below command creates file f that has 57 null bytes.
$ truncate 57 f
$ ls -l big
-rw-rwr-- 1 eggert faculty 9223372036854775000
If we want to search the letter “x” in the file, we can use grep:
$ grep x big
Since it outputs nothing, we know that there is no “x” in the file. To see how long it takes for grep search the whole file, we use time:
$ time grep x big
real 0m0.009s
This tells us that the speed to search the big file is ~10^21 Bytes/s or ~10^22 bits/s.
It was said that the fastest way to deliver massive information is through SneakerNet--physically deliver a hard drive. (For more information, see http://what-if.xkcd.com/31/). Why is grep able to run that fast? It turns out that grep somehow senses that the big file is full of null bytes and so it concludes that the file does not have the “x” pattern. Even when the file does contain the pattern, it still runs pretty fast. We will learn more about how this works later in this course.
When sizes of systems change, their components do not always change at the same rate. As a simple example, consider a sphere. As the radius increases, the surface area increases by a factor of r^2 and the volume increases by a factor of r^3, and as r grows, the original ratio between the two grows much larger. As a large system changes in size, incommensurate scaling of its components may lead to unwanted challenges or problems. Sometimes this works to our benefit, such as with economies of scale. As the number of units being produced goes up, the individual cost per unit goes down, leading to a greater profit. However, the opposite circumstance also exists, called a diseconomy of scale. In this case, the cost per unit goes up as the system grows. For this, consider a program that has O(N^2), say from a set of nested loops. A few iterations of this loop may seem harmless, but each additional iteration increases the time by an order of N^2. An example given in class was the star network, in which as the number of potential connections grow, the time it takes to form the connections grows exponentially. The common outcome of incommensurate scaling is that things break as you grow.
Another common outcome when the size of a system grows is the emergence of properties that either originally didn’t seem to show up, or originally were so small they were negligible. A small prototype of this system may work, but as it grows to become very large, these negligible properties become problems that can no longer be ignored and can be catastrophic. As an example, the Tacoma Narrows Bridge, when viewed as a prototype, didn’t appear to be affected by winds and oscillation. However, when the large bridge was built itself, the structure was destroyed by this emergent property.
In a system, the size, complexity, and relationships between different parts of the system can lead to the problem referred to as the propagation of effects. The propagation of effects refers to the idea that a small error in one remote sector of a system may cause sweeping errors very far away from the original source. For example, when Windows started to support Japanese characters using an encoding called Shift-Jis, this caused problems in their file system where the second byte of a 2-byte Shift-Jis character could look like an ASCII ‘/’. The lesson learned here is that you cannot predict how changes in one area of a system will affect other areas.
In a large system, there will always be trade-offs. The professor referred to the “water-bed effect.” If you push down on one side of the water bed, another size will rise up. In a system, fixing one problem or inefficiency may lead to another. An example was with the Unix implementation of representing japanese characters. Each character required 3 bytes, and while that didn’t lead to the same problems the 2-byte implementation had, it required 50% more space. Another example given in class was one of security of myucla. With just a password, it is too easy for students to break in and change their grades. However, with an added key fob, you have professors complaining, misplaced key fobs, malfunctioning fobs...etc. So the added security comes at the cost of unhappy professors and a more complicated system to input grades.