CS 111 Operating Systems Principles, Spring 2008
Lecture 1 Notes (Monday, March 31)
prepared by L. O'Connor, R. Jeon, N. TilleyGeneral Announcements: | |
| Course requirements: click here | |
| Honesty standards: click here | |
| Assigned Prep Reading from Reader: here | |
Lecture Outline | |||
I. |
Overview | ||
II. |
Defining Systems | ||
III. |
How to Best Characterize a System | ||
IV. |
Development Issues | ||
A. |
Design Trade-offs | ||
B. |
Incommensurate Scaling | ||
C. |
Emergent Properties | ||
D. |
Propagation of Effects | ||
E. |
Complexity | ||
F. |
Technological Advancement Rate | ||
V. |
Resources | ||
Lecture Notes | |
I. Overview | |
| CS 111 Course Goals (§1.A, p.1-3) | |
| The goal of this course is to help the student understand aspects of low-level software design. Within this course you will understand the fundamentals of I/O operations, processor and memory interactions, and how your program will fit as a whole in the computer. Taking this course will give you a greater appreciation of details in software development. | |
II. Defining Systems | ||
| What is a system? Let's get a better handle on what we mean. (§1.A.2, p.1-8) | ||
| • "A set of interconnected objects with an overall purpose" – Nick, from class | ||
| • "An organized or connected group of objects; a set of principles, a scheme, method" – Oxford English Dictionary (1928) | ||
| more broadly in concept, from the Greek stem systema (συστημα) meaning, "to set up with" | ||
| • "An organized whole, a government, constitution, a body of people or animals, a musical interval, a group of verses in a poem" | ||
| Overall, then, it is the set-up (the skeleton?) necessary to be in place to get the work done. | ||
| What is an operating system? When computer scientists borrowed the word, they imbued it with more meaning. | ||
| The first operating system was MCP (Master Control Program) that ran on UNIVAC I in the late 1950s. | ||
| Consider 3 sources: | ||
| • Encarta – (dated, 1950s): an operating system is the "master control program in [a] computer." | ||
| • American Heritage Dictionary (4th ed.) – (dated, 1970s): an operating system is "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 assumes that an OS is tied to a particular type of hardware. According to this definition, and OS is not allowed to run on more than one type of hardware. | ||
| • Wikipedia (119834131 – as of 1 April 2008) – (most pertinent): an operating system is "software that manages the software and hardware resources of a computer". This is by far the best definition of the three because of its emphasis is on managing resources – both hardware and software, instead of on the control. The least interesting part of an OS is the control. The control part, for instance, keeping users out of a particular area, is brute force power, but the resource management part is much harder. As a side note, there is a reflective aspect of current OS's in that they help to manage themselves. One student made a point that an OS can manage resources on more than one computer. | ||
| system: from the textbook – | ||
| From the Reader Principles of Computer System Design, something a little more concrete: | ||
| "A system is a set of interconnected components that has a specified behavior observed at the interface with its environment." – §1.A.2, p 1-8 | ||
| A sketch to give a picture of this definition: | ||
|
|
||
| Things are not usually this simple. We can look at things from many different perspectives or axes. | ||
III. How to Best Characterize a System | ||
| What's in a System depends on your priority! This depends on your perspective. (§1.A.2, p.1-9) | ||
| Consider the example of giving an object-oriented description of the classroom. Different views might be mostly independent of one another: | ||
| • "furniture view" - desks, tables, boards, according to the interior designer | ||
| • "electric view" - switch locations, light locations, according to the electrician | ||
| A sketch conveying the idea that different views might be orthogonal to one another: | ||
|
|
||
| The views are mostly orthogonal, but not completely. There is a relationship between the lighting and the furniture, if you want to put lighting where people are sitting. One challenge is to decide how to modularize this, since you don't want to represent everything in one diagram. | ||
| Your goal: to know how many views & modules there are, and their trade-offs. | ||
IV. Development Issues | ||
| In working through the assigned labs and in solving design problems in the real world, there are several development issues to keep in mind. | ||
| These kinds of issues to work through include | ||
| A. Design Trade-offs | ||
| B. Incommensurate Scaling | ||
| C. Emergent Properties | ||
| D. Propagation of Effects | ||
| E. Complexity | ||
| F. Technological Advancement Rate | ||
A. Design Trade-offs | ||
| What are Trade-offs? They are exchanges, giving up of one thing in return for another. (§1.A.1.4, p.1-7) | ||
| Goals of a system can conflict with each other. Common examples are gaining speed in exchange for flexibility, simplicity, or ease of use; also time for space. | ||
| Examples: | ||
| • Sorts. Data records referenced by an array might save time sorting if sorting only the array references. However, the array takes up additional space, and other functions such as traversing the sorted records in order can take more time. | ||
| • Authentication. Use a password? Use a hardware token? Or both? It depends upon the application. For instance, a car generally uses a hardware token (a key), and a computer system will use a password. Some systems require both. Passwords preserve convenience, tokens provide more security and are harder to forge. | ||
| You must be conscious of a trade-off and know that it was made. Sometimes you need to re-evaluate the trade-off later on, either because the original trade-off was not good or because the situation has changed. | ||
B. Incommensurate Scaling | ||
| What is incommensurate scaling? As systems grow larger, there is a non-linear growth in the resources required; or not all parts scale in the same way. (§1.A.1.3, p.1-5) | ||
| • height/weight. | ||
| o Why are people two meters tall? Weight grows much faster than the cross-sectional strength of bones. Order O(n³) eventually overtakes Order O(n²). | ||
| There are ups and downs to growth. | ||
| • economies of scale. | ||
| o Pin factory (Adam Smith's Wealth of Nations). Can be more efficient if a few resources are dedicated to pin-making and supply all of the pins to the town. | ||
| Economies of scale are advantages to produce goods at reduced per-unit cost. | ||
| • diseconomies of scale. | ||
| o Pin factory. Re-tooling pin-making from a well-established method costs a lot of investment. (§1.B.1, p.1-14) | ||
| o Star network connecting PCs. Power goes out at the hub and power to all is lost. Or adding one more PC may require a much more expensive switch. | ||
| Diseconomies of scale are liabilities that force producing goods at higher per-unit cost. They cause inertia (unwillingness to change further), breakage, or bottlenecks (where not enough resources can be supplied). | ||
| While the topic of Scale is less handled in labs (labs are relatively small scale in size), this will be encountered in more detail in lecture and in the real world. | ||
C. Emergent Properties | ||
| What are Emergent Properties? Unforeseen effects that surface the next level of scaling. (§1.A.1.1, p.1-4) | ||
| These problems are often unpredictable. Emergent properties can be worse than incommensurate scaling, which is usually predictable. Suddenly the system has properties that it did not have before. | ||
| • Malicious use of networks. Computer worms emerged when the network system grew large enough, to include uncontrolled users who make malicious programs. | ||
| • Napster. This became feasible when a large number of technically savvy users had access to very high speed networks. | ||
| • Tacoma Narrows Bridge. The Washington bridge collapsed in 1940 from unanticipated results of building a bridge long enough to oscillate in resonance with persistent strong winds. | ||
D. Propagation of Effects | ||
| What are Propagated Effects? Changes that carry through in large systems to many sorts of unexpected places. (§1.A.1.2, p.1-5) | ||
| Making a small change in one area results in a change someplace else. This often happens in OS's. | ||
| • Multi-byte text encoding scheme. | ||
| "There are no small changes in a large system." – §App. 1–B, p.1-41 | ||
E. Complexity | ||
| What is complexity? The increased intricacy of storage density, circuitry. (§1.B, p.1-11) | ||
| • Moore's Law. The number of transistors that can be put on an IC economically doubles every 24 months. | ||
| • Kryder's Law. Disc drive capacity grows exponentially. (But the speed of a disc drive is not growing as fast as its size. An analogy is that we are using straws of the same size for bigger and bigger milkshakes. It is taking longer and longer to completely transfer or read the contents of a drive.) | ||
| Logarithmic graphs roughly charting the growth in transistors/disk drive capacity: | ||
|
|
||
F. Technological Advancement Rate | ||
| Did you know this? | ||
| Computer science is one of the fields in which current technology is used to create the next level of technology development (§1.D.2, p.1-25). For example, UNIVAC II was designed by having UNIVAC I run a simulator, giving UNIVAC II's technology a head-start. | ||
| Mathematically, we can write that the change in technology over time is a function of the existing technology, or | ||
| δ (technology) / δt = K × technology | ||
| which leads to the explicit equation that technology development is at an exponential rate | ||
| technology = C eKt | ||
| The question is whether that is sustainable? How will we keep up with this? | ||
V. References | ||
| • Multi-byte character encoding | ||
| • Wealth of Nations, and the pin-maker | ||
| • Tacoma Narrows Bridge Disaster | ||
| • Napster, and high-speed connectivity university networks | ||
| • Trade-offs in space and time | ||
| • Moore's Law | ||
| • Kryder's Law | ||
