Professor: Paul Eggert
Office Hours: Mondays 13:00–14:00 and Wednesdays 9:50–10:50 in Boelter 4532J
Teaching Assistants:
Office Hours: Tuesday 15:00-17:00 in Boelter 2432
Office Hours: TBD in Boelter 2432
http://cs.ucla.edu/classes/spring12/cs111/
Jerome H. Saltzer and M. Frans Kaashoek, Principles of Computer System Design: An Introduction, Morgan Kaufmann (2009)
Official
Unofficial (Recommended)
| Supposed Hours/Week | Actual Hours/Week | |
| Lecture | 4 | 3.7 |
| Discussion Section | 2 | 1.7 |
| Outside Study | 6 | 12+ |
| Item | Fraction of Grade |
| Labs (x4) | 1/12 each |
| Final | 2/9 (Wednesday March 21th 8 AM) |
| Midterm | 1/9 (Monday February 13th 12 PM) |
| Minilabs (x2) | 1/15 each |
| Design Problem, Presentation, & Report | 1/12 |
| Research Topic Paper | 1/30 |
| Scribe Notes | 1/12 |
Read Ch. 1-2.3
Lab 1a due Tuesday April 10th
Oxford English Dictionary (1928)
American Heritage 4th Edition (2000)
Software designed to control(?) the hardware of a specific data processing system(?) in order to allow users and application programs to make use of it.
This definition is inaccurate since an operating system does not have to be specific for a computer. In addition, it is very control oriented.
Encarta (2007)
Master control program in a computer.
The operating system is what controls the computer.
Wikipedia (v. 469680935)
A set of programs that manage computer hardware resources and provide common services for application software.
While this definition is true, an operating system does more than just manage; it pretty much controls.
Saltzer & Kaashoek (book's definition from chapter 1)
A system is a set of interconnected components that has a specified behavior, observed at the interface with its environment.
Interface technologies include:
"The Waterbed Effect"
When you push down on one end, another end comes up. Thus, making one thing better can result into probems in another thing.
For example, if you want to increase a processor's clock rate then not only will there be an increase in the overall performance by ignoring time lost to timing errors, but there will also be an increase in the power consumption and timing errors.
Time-space Tradeoff in Sorting
Lets say you have a 10GB array of 1KB sized numbers in RAM that need to be sorted. What is the most efficient way in which to sort the numbers?
Quicksort? The average case is O(n log n). In the case where the numbers are in reverse order, we have a worst case scenario which has O(n2) since the sorting algorithm needs to do lots of data swapping. In this case, we optimize memory since we allocate no more memory, but the tradeoff is a slower sort.
Heapsort? This would be similar to quick sort except that the time complexity of the algorithm is O(n log n).
In the case where you can compromise memory for optimized time, a good solution would be one where you make an array of pointers in which each pointer points to a distinct 1KB memory address in the array. Now you can sort the dereferenced pointers and get the sorted list. In this scenario, time is saved since swapping 4B pointers would occur much faster than swapping 1KB numbers in the memory spaces of the array. However, memory is compromised since extra memory has to be allocated for the array of pointers.
Now, if each memory space was only 1B as opposed to 1KB then the above-mentioned time-space tradeoff would not work since the array of pointers is already bigger than the array itself. A good solution would be making a histogram which would solve the problem in O(n).
This occurs in designed systems as well as chaotic ones. One change in a certain part of the system or process leads to a change in another part of the system or process.
An example would be multibyte encoding for Japanese characters which uses 1B ASCII characters. If the system sees '0' as the leading bit then it will treat the next byte as a regular ASCII character. In the case where the leading bit is '1', the system will treat the next two bytes as a Japanese character. The problem that arose was that sometimes the leading bit of the 2nd byte of the Japanese character started with a '0' and had the same bit-pattern as the file and directory separator (slash). Thus, when a user tried to use some of the Japanese characters in file names, they would receive error messages regarding an nonexisting directory or would end up modifying files they did not intend on modifying. This is the issue Microsoft had when it tried to implement JIS in Windows.
A good fix to this problem is using a differnt encoding. For example, Linux makes sure that its Japanese characters have a leading bit of '1' in every byte. Utf-8 is a newer and better character encoding which also avoids this problem of mistaking a Japanese character with a slash.
Another Problem:
Backing up a partition in a container-based virtual system
An attacker would make a file f with a symbolic link to another filesystem and thus would attain access to all the files during backup.
Solution: open + fstat
Emergent properties are properties that are not evident when dealing with an individual component, but as we scale to having multiple connected components then they are evident.
Not everything scales at the same rate. For example, why don't humans grow to be 100 feet tall? Why do they grow to be about 2 meters? This is because of scaling issues. For humans, the amount of heat generated is proportional to volume whereas the amount of heat dissipated is proportional to surface area. Now, since volume(O(n3)) grows faster than surface area(O(n2)), humans will not be able to survive a height of 100 feet simply because they would overheat. As this example shows, different parts of humans scale at different rates. Similarly, computer systems work the same way; the two types of incommensurate scaling that take place with computer systems are the following:
This is probably the biggest problem. Why?
Moore's Law - The number of transistors on a chip doubles every two years.
Kryder's Law - The storage density of disk drives doubles annually.
