CS111 Operating Systems - Lecture 1

Maksim Rozentsveyg
Phu Huynh

Class Information

Professor: Paul Eggert
Office Hours: M 12:50-1:50, W 11:00 - 12:00 in BH4532J

TA: Keith Stevens
Office Hours: T 2:30-3:30, R 2:30-3:30 in BH4428

Class Website

http://cs.ucla.edu/classes/fall10/cs111

Book

Saltzer & Kaasheek, Principles of Computer Systems Design (2009)
This is a general computer systems book, not just operating systems (OS).

Assignments

4 labs, 2 minilabs, 1 design problem, 1 research paper, scribe notes, midterm, and final

Grading Breakdown

Current Information

Lab 1A is due Oct. 1, Read Ch. 1-2.3 for Tuesday's lecture (September 28)

Intro to Operating Systems

An Anecdote about RIM

RIM is coming out with a tablet: the PlayBook. They plan to run BlackBerry apps on it the same way the iPad runs iPhone apps, but instead of porting the BlackBerry's OS or writing their own, they bought the company behind an OS called QNX. QNX has existed for ~30 years and is known for its stability; it's even used to runs nuclear power plants, among other things. Unlike Linux-based OS's, QNX is a message-passing OS, where threads communicate directly with each other instead of going through the kernel to get things done. Also unlike Linux, each device and program is controlled by a specific thread instead of the kernel directly. This makes QNX more stable because if a device driver or other low-level program crashes, it doesn't bring down the whole OS (this can happen in Linux if, say, the video driver crashes). Further, message-passing allows for easier parallelization. QNX is also a real-time OS, which means that each operation will finish under a set amount of time. The reason all of this is interesting is because the norm for developers is to write apps fit for the OS. RIM is doing the opposite: they are picking a specific OS to be able to run BlackBerry apps with the best performance and stability as possible.

What is a system?

To understand what OS's and computer systems are, we must first understand what a system is.

Oxford English Dictionary (1928)

        I. Organized or connected group of objects
	II. A set of principles, etc.; a scheme, method
	From the Greek word meaning "set up with"
		organized whole, government, constitution
		body of men or animals, musical interval
		group of connected verses in a poem

Now that we have a good feel for systems in general, what is an operating system?

Let's look at some recent definitions:

American Heritage Dictionary (2000)

	Software designed to control the hardware of a specific data processing system in order
	to allow users and application program to make use of it.

The above definition is flawed. An operating system doesn't need to be specific to a computer. Further, users aren't necessarily the entities interacting with a computer. Nonetheless, the idea of control is spot on. Encarta has the right idea too:

Encarta (2001) (This isn't the full definition, only the beginning)

	"The master control program in a computer..."

In a nutshell, the operating system is indeed what controls the entire computer.

Wikipedia (v. 1198341131)

	A set of computer programs that manage the hardware and software resources of a computer.

Managing is a softer term than control, but this short definition sums up best what an operating system really does, and is also a throwback to the centuries old definition of a system. The operating system is the main bureaucrat and traffic cop of a computer.

Saltzer & Kaasheek (our textbook, chapter 1)

	A set of interconnected components that has a specified behavior observed at the
	interface with its environment.

So, one way to think of a system is a "black box" whose inner workings are abstracted, but its behavior can be easily observed from the outside.

Systems can be nested as well. The classroom is a system containing other systems which interact with each other (the electrical system, the furniture layout, and the fire safety system).

Problems in Computer Systems

1. Tradeoffs (Waterbed Effect)

   

   Computer systems are like a waterbed: push down on one end, and the other comes up. Try and optimize memory, and the program runs slower. To sort a 100 GiB array of 1KiB items, we could simply sort the array in place with quicksort, but that would require enormous amounts of data swapping and thus take a long time. But, we minimize the amount of memory used: we only need the amount of space the array takes up. If we try and optimize for time, we could very well end up using more memory. For example, we could create an array of pointers to each 1KiB item and sort the dereferenced pointers instead, which would save the swapping time since each pointer is only 4B (or 8 if you're on a 64-bit OS). But, this would eat up more memory: we'd have to allocate an extra array for the pointers, which would take up 400 MiB on a 32-bit OS or 800MiB on a 64-bit OS.

2. Incommensurate Scaling

   

   Systems sometimes can't be scaled for inherent reasons. This can be demonstrated with an analogy and a thought experiment: why aren't humans 100 stories tall? Why only (roughly) 2 meters? Well, if humans were too big, there would be scaling issues. For example, the amount of heat generated is proportional to volume, while the amount of heat dissipated is proportional to surface area. Volume grows much faster than area (think O(n³ ) vs O(n²)), so humans wouldn't be able to survive if they were 100 feet tall simply because they would overheat. Another example is human bone strength: the amount of weight a bone can bear is proportional to its surface area, while a bone's weight is proportional to volume. So, a very large human shaped bone would crumble under its own weight. But why does this happen in the first place? Because, just like in computer systems, when an entire human scales, different parts of the human scale at different rates, thus causing the system to collapse inherently. The two types of incommensurate scaling that can appear in computer systems are as follows:

   1. Economies of Scale - items become cheaper per unit as additional units are created

      Consider Adam Smith's pin factory analogy. Imagine one 19th century village composed of a society where each person makes their own sewing pins -- each person would take a spool of wire, cut off a piece, hammer out one end, and sharpen the other to make a single pin. Now imagine a neighboring village allocating all pin-related manners to a blacksmith who runs a pin factory, making pins 8 hours a day, in parallel. Naturally, the other village is better off, especially if pins are high in demand. This is because the marginal cost of a single pin is very small; that is, creating an extra pin, if you've already made some, is easier, since pins don't require much time or resources, and can easily be made in parallel. This is an example of economics of scale: each additional unit is cheap to make, especially if you have many units already. This can be analogous to computer production, and is actually a good thing to have, as long as complexity is under control.

   2. Diseconomies of Scale - items become more expensive per unit as additional units are created.

      An example of this is a star network, where each user is connected to a central Ethernet switch, and must go through the switch to communicate with another user. A 4-port switch costs $20, an 8-port switch costs $40, and a 50-port switch costs $3000. Why? Because to support more ports, more complicated hardware is required, issues with threading and parallelizing traffic come up, and even different semiconductor materials may be necessary, among other things. So, a switch undergoes "diseconomies of scale" - adding another unit gets more and more expensive based on the amount of units you have. This is a negative type of scaling.

3. Emergent Properties

   

   Properties that are not evident in an individual component but emerge when combining components together are called emergent properties. In the TacomaNarrows bridge incident, a bridge collapsed because the wind hit its resonant frequency, an unfortunate emergent property that went unforeseen by the bridge's designers, because the bridge's individual components did not hint clearly that this would happen.

4. Propagation of Effects

   

   A change to one part of a system can produce a change in a far distant part of the system. Suppose we decide to introduce Japanese characters to an existing operating system, which currently uses only 1B ASCII characters. The system works as follows: if the most significant bit is a 0, interpret the next byte as a regular ASCII character. But if the most significant bit is a 1, interpret the next 2 bytes as a Japanese character. The issue that arose is that sometimes the 2^nd byte of the Japanese character started with a 0, and had the same bit-pattern as the directory separator character: the slash. So, when a user tried to use certain Japanese characters in file names, they wouldn't be able to manipulate the file, because they would receive an error regarding an inexistent directory. Or, they would modify an unintended file in a different directory. This exact problem happened when Microsoft attempted to implement JIS in Windows. A possible fix would be to use a different encoding (Linux has Japanese characters use a 1 as the most significant bit in all bytes), or to tell the kernel to do something special when a Japanese character is being used.

Complexity

Q: Why are we creating such complex systems in our computers?

A: Because we can! Two "laws" govern our hardware:

1. Moore's Law

   

   Moore's Law states that the number of transistors on a reasonably priced chip doubles approximately every two years (note the log scale on the y-axis).

2. Kryder's Law

   

   Kryder's Law states that the storage density of magnetic disks (HDD's) doubles annually (again, note the log scale).

Wrap-Up

With the introduction of powerful hardware, we can create complex, multifaceted software systems to support our machines. But, more and more transistors isn't everything. Neither is more and more disk space. In the end, computer chips aren't getting much faster. Hard disks aren't improving in terms of speed a whole lot, either. And OS's are still hard to write well. After all, you don't see RIM writing a new one for the PlayBook.