Professor: Paul Eggert
Office Hours: TBD in Boelter 4532J
Teaching Assistants:
Office Hours: TBD in Boelter 2432
Office Hours: TBD in Boelter 2432
Office Hours: TBD in Boelter 2432
http://cs.ucla.edu/classes/winter13/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 | 9 | 18 |
| Item | Fraction of Grade |
| Labs (x4) | 1/12 each |
| Final | 2/9 (Wednesday March 20th 8 AM) |
| Midterm | 1/9 (Monday February 11th 12 PM) |
| Minilabs (x2) | 1/15 each |
| Design Problem, Presentation, & Report | 1/12 |
| Research Topic Paper | 1/15 |
| Scribe Notes | 1/20 |
Read Ch. 1-2.3
Lab 1a due Tuesday, January 15th
Oxford English Dictionary (1928)
Encarta (2007)
Master control program in a computer.
The operating system is what controls the computer.
Wikipedia (v. 531774181) (2013-01-07)
A collection of software that manages computer harware resources and provides common services for computer programs.
Resource management lies in the heart of computer science.
Saltzer & Kaashoek (book's definition from section 1.A.2)
A system is a set of interconnected components that has a specified behavior observed at the interface with its environment.
Interface technologies aka specified behavior observed include:
It is not usually this simple. But we can split up systems in different ways. Different split
"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 1GB array of 512B sized numbers in RAM that need to be sorted. What is the most efficient way in which to sort the numbers?
Mergesort? Here the complexity is O(n log n). The major overhead is that of copying data.
How would I make this 100x faster?
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 512B 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 512B numbers in the memory spaces of the array. However, memory is compromised since extra memory has to be allocated for the array of pointers. The memory overhead is about 1/128.
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).
Building a Secure System
We have a RSA SecureID which is another form of authentication. When combined with the password we have on a certain account, we get the extra layer of security due to the RSA SecureID.
Problems with this form a security include having a plain password and/or losing and retrieving a new RSA SecureID is a hassle.
Used for quantitative measures. Not everything scales at the same rate. For example, why don't humans grow to be 20 meters tall? Why do they grow to be about 2 meters? This is because of scaling issues. For humans, strength scales at O(N2) whereas weight scales atO(n3). Thus at some point the human bones will break. If put in water, weight is not as much of an issue which is why whales grow to be so big. 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:
Used for qualitative measures. 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.
This occurs naturally in engineered/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. One example being how Ronald Reagan becomes president because of a suicide.
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.