CS111 Scribe Notes for April 2, 2013

Logistics

CS111 - Operating Systems Principles
Instructor: Prof. Paul Eggert
Weiguang Si forswg@ucla.edu
Course webpage: http://cs.ucla.edu/classes/spring13/cs111/

Formal Prerequisites:

• CS32 (Intro to Computer Science II)
  
• CS33 (Intro to Computer Organization)
  

• Networking (CS118)
• Computer Architecture (CS152B)
• Programming Languages (CS131)

Course Organization

• 19 lectures
• 1 midterm (in lecture)
• 1 final exam

Course Load

Assignments

Allowed to work on labs solo or in groups of two.

• 4 Labs -
  
  1. First Lab: Super aggressive parallelized operating shell. Consists of 3 parts A, B, and C.
• 1 Design Problem (an extension of one lab)
• 2 Mini Labs (Smaller than labs. Lets you work on a particular important, but focused, aspect of operating systems. Done solo)
• 1 Written Report (1-2 pages on a future topic. Not yet determined.)
• 1 Scribe Note - Create an html website with your notes from one lecture and post it to courseweb. Must conform to HTML standards and be HTML 4.01 not HTML 5. Should be turned in as a tarball that can be unpacked. Groups of at most 4. Around 5 scribe notes per lecture allowed.

Grading/Due Dates

Exam Information

Exams are open book and open notes but closed computer. This will be questions where the answer is not in the book.

Late Policy

2^n-1 points off where n=number of days off, rounded up to the nearest day. This is assuming the assignment is worth 100 points. Last day that you can turn in assignments is the last day of instruction, Friday.

Warning

You are encouraged to help each other in studying. You are encouraged to discuss general ideas and directions. You can't turn in any work that is not your own.

What is a System?

The text is about computer systems, but the course is about operating systems

Oxford English Dictionary Definitions:

• An organized group of objects
• A set of principles, etc,; a scheme, method
• From Greek, συστημα meaning "set up with" - organized whole, government, constitution, a body of men or animals, music interval, a stanza

Modern Definitions

• Master control program in a computer
• In an operating system you need to know what instruction will be executed next and under whose authority
• 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 too control oriented
  • Only concerns "specific data processing system" instead of general data processing systems which are more relevant due to portability reasons.

Wikipedia

• a collection of software that manage computer hardware resources and provide common services for computer programs
  • "Resources" - not really appreciated, but is a very big deal. This definition introduces the idea of "managing" resources. In the real world, this would be called budgeting.
    e.g. How much CPU to devote to a process
  • "common services" - application software has a lot things in common creating sockets, creating domain names … operating systems can provide these to make it easier for application writers.

This image summarizes the fundamental lay out of an effective operating system. The operating system isolates the application space from hardware space, the only way to get from one to the other is through the OS level.

What you want from an Operating System

1. Protection (from total failures, security requests, etc.)
2. Robustness (ability to accept strange inputs without becoming unstable)
3. Consistency/simplicity (allows for ease of use and maintenance)
4. Performance (a necessity, but not a priority. An operating system that performs well but is unstable is unusable.)
5. Flexibility (Ability to perform under a variety of circumstances without significant effort on the part of an application.)

Major Aspects of an Operating System

1. Virtualization - virtual memory, virtual machines
2. Scheduling
   • There is a limited amount of resources
   • There is too much demand for hardware resources - scheduling is required for when resources are stretched thinly.
   • Scheduling also has performance benefits. If certain aspects of the system are waiting, for example a network or disk component, a scheduler can improve performance by performing another task while the application waits for the slower I/O to finish.
3. Consistency - Rules for keeping applications from interfering with each other.
   e.g. synchronization, on the part of threads or I/O accessing
4. File Systems - watered down, simple versions of databases. Used to store persistant data for use within applications.
5. Security
   • Very difficult to retrofit security (if you don't think about it until the very end, then it is too late)
     "You cannot build a bank THEN think about building a safe - build a safe and then build a bank around it"
   • Isolation is key: isolating the operating system from the influence of applications, as well as isolating applications from each other.

Problems in Computer Systems

I. Tradeoffs

1. The Waterbed Effect: Pushing on one side of a waterbed raises the other side. This is a visual metaphor: when you apply pressure in one area, other areas of the bed are pushed up by the water being displaced. The amount of water is constant: the only question is where the water is allocated. That is your design decision: you have a set amount of water, and your job is to allocate it to maximize the goals of an operating system outlined in Major Aspects of an Operating System.
   
2. Time vs. Space: This is a typical scenario within an operating system that requires balancing trade offs. Imagine we would like to sort 1GB of randomized structs of size 100 bytes. If we use quicksort, it would make 1e7*log(1e7) ~ 22e7 ~ 1e8 comparisons since quick sort, on average, makes O(nlogn) comparisons. This indicates that the algorithm moves ~1e10 bytes. We can make the algorithm to run faster by reducing the number of movements. This can be done by allocating an array of pointers (5 bytes each in a 32-bit system) that corresponds to each record. Now, instead of moving the records, the pointers are moved. The latter method performs faster by saving up ~6% of number of movements (1-4e8/1e10), while the former requires more memory.
   
   The question of which implementation to choose is left to you as a designer, depending on the requirements of your system. There is no "right answer".
   
3. Passwords vs. Token-based Encryption: This is an example of a convenience vs. effectiveness trade off. Encryption algorithms need keys to decrypt. For a particular algorithm, this key could be a password that is typed into the system. This is an inexpensive approach, but it could be vulnerable to people stealing the password. There is a single point of failure. Another approach is to use hardware tokens which must be physically presented to run the system. It is more secure compared to passwords (remember the token can be stolen), but hardware components are normally costly and difficult to replace. We can also use both systems together, but the problem is now we have two points of failure and it's much more likely that a person will randomly be unable to access the system. Thus, the waterbed effect is present in that we cannot have more security without trading convienence.

II. Incommensurate Scaling

1. Every person makes their own pin, which may take two or three hours. This is reliable: everyone always has the pins they need, no more or less. There are no wasted pins or effort.
2. Collect a few villagers to start a pin factory. Now, pins have a much lower per-unit cost, because people who specialize in making pins can do so for less effort. There is a downside, however: overproduction is possible, and effort can be wasted. However, it is clear that as the number of pin users grows, the effectiveness of a pin factory increases. There is less chance of waste if more people are using pins. This means that the pin factory is an economy of scale: its effectiveness grows as its scale increases.

• An example of this is an ethernet port system. Adding etherport ports to an ethernet switch scales quadratically with the number of ports, so the complexity increases as the number of ports increases. A lot of this complexity can be tied back into IEEE specifications for ethernet, which specificy 10GB/second transfer time between any two ports. To make this speed happen, there is a lot more complexity than have a few ports.
  Here, scaling the size of the ethernet port does not increase the amount of data that the system is able to process. In a diseconomy of scale, the scale of a system is inversely related to its ability to operate effectively.
• Another example of this is creating logic gates. As the number of inputs to a logic gate scale up, the number of gates required to implement it increases superlinearly. This is why most systems are implemented with gates that have a small number of inputs (2-3). Also, we can note that we can inplement a 3-input nor gate with 2-input nor gates, but we need at least 2 2-input nor gates to implement a 3-input nor gate, so if we increase the number of inputs by 1, we increase the size, power requirements, scale and other physical properties far more than 1/2 of the original 2-input gate.

III. Emergent Properties

• Tacoma Narrows Bridge:This bridge was built using a scaled up model of smaller bridges. On smaller bridges there were no observable problems. Once scaled to a much larger size, when wind gusts around the bridge approached the resonant frequency of the bridge, the entire bridge oscillated. This resulted in the bridge failing. Now systems are all designed such that their resonant frequency is unreachable by wind.
  
  The lesson here is that a designer can not look at a small scale design and assume it will operate well in large scale. Certain properties are only observable when the scale is large enough.
• Napster: In the 1990s there was an initiative in college campuses to offer high-speed internet in the dorms. This was seen as a positive thing: give students the ability to quickly get information they need for their studies. The unexpected and unforeseen effect of this sudden increase in scale of the ability to acuire information is the rise of music piracy via Napster and other P2P sharing systems. No one foresaw the consequences when the school administrators decided to add high-speed internet to the dorms.

IV. Propagation of Effects (The Butterfly Effect)

V. Complexity

• Hardware is scaling faster than our knowledge/intelligence.
• Moore's Law: The number of transistors per chip has increased logarithmically from 2e4 in 1970 to 2e9 in 2009.

  (Wgsimon)

• Kryder's Law :The capacity of disk drives has increased from 0.1 GB in 1990 to 1000 GB in 2007.

  (Rentar)

Bibliography:

• Wgsimon. "Microprocessor Transistor Counts 1971-2011 & Moore's Law." Image. Wikipedia, 13 May 2011. Web. April 8 2013.
• Rentar. "Hardware Capacity Over Time." Image. Wikipedia, 25 Feb. 2009. Web. April 8 2013.