CS 111, Operating Systems Principles

Lecture 1 Scribe Notes, September 24, 2009

Assembled by: Chandni Dhanjal, Chris Oentojo, Dmitriy Vinogradov, Gurneet Chhokar.

Course Overview

Professor's and TAs’ email addresses and Office Hours:

Paul Eggert, eggert@cs.ucla.edu: BH 4532J, Mon. 12:50pm - 1:50pm, Wed. 11:00am - 12:00pm
Dan He, danhe@cs.ucla.edu: BH 4428, Fri. 2pm - 4pm
Ian Ku, ianku@cs.ucla.edu: BH 4428, Tue. 2pm - 4pm

Class Website: http://cs.ucla.edu/classes/fall09/cs111, and Courseweb.

Textbook: Jerry Saltzer and Frans Kaashoek, Principles of computer system design, MIT 6.033 class notes, draft release 3.1, August 2006. Available at Course Reader, 1072 Broxton Ave (across from Chipotle).

Hours/week (Official): Lecture, 6 hrs; lab, 2 hrs; outside study, 6 hrs.

Hours/week (Actual): Lecture, 3.4 hrs; lab, 1.8 hrs; outside study, 20 hrs.

Course topics:

• Overview
• Principles
• Concurrency
• Scheduling and Dispatch
• Memory Management
• Device Management
• Security
• File Systems

Prerequisites: CS 32, 33 (CS 35L would be helpful).

Grading: 33% labs, 33% exams, 33% other:

• Labs: 4 labs, 1/12th of the grade each.
• Exams:
  • Midterm: Tuesday, October 27th, 1/9th of the grade.
  • Final: Thursday, December 10th 3:00-6:00pm, 2/9th of the grade.
  • Exams are open book and open notes but no electronic devices allowed. It’s helpful to bring work done in labs and homework.
• Other:
  • Mini-labs: small assignments that focus on a fairly narrow topic, 1/15th of the grade each
  • Design problem that student can select from the “extra” part of the mini-lab, 1/12th of the grade
  • One-page report, 1/30th of the grade.

Scribe notes: A group of students gets together and come up with good lecture notes. Deadline is 1 week after the lecture.

First lab: First lab is split into two, 1a and 1b. Due date for lab 1a is October 2nd, Friday, 23:59:59 PM. There are 3 “late days” available to each students, which can be either used or saved. Nothing is accepted after the last day of class. People are expected to do the assignments by themselves. It’s okay to talk about the assignments and general principles from the class.

Resources: UCLA LUG (Linux Users Group. InstallFest is on October 3rd), SEASNET accounts, Operating System resources

Introduction to Operating Systems

Course is about operating systems. Textbook is about computer systems.

What is a system?

A combination (of components) that performs a specific task.

OED definition: an organized or connected group of objects; a set of principles, etc., a scheme or a method. The definition is from the 1928 OED on which J. R. Tolkien was an editor. The word system comes from Greek language and means organized whole, government, constitution, a body of men or animals, a musical interval, or a group of connected verses in a poem.

What is an operatingsystem?

American Heritage Dictionary (2000): software designed to control the hardware of a specific data processing system. “Useful.” However, modern operating systems are not made for any specific hardware but rather can run on a variety of popular hardware architectures.

Encarta (2007): a master control program in the computer.

Wikipedia (119834131): a set of computer programs that manage the hardware and software resources of a computer.

Textbook Definition: A system is a set of interconnected components that has a specified behavior observed at the interface with its environment. A lot of the skill involved in system building is invested in building an appropriate interface. This definition also applies to each of the system’s components since each component is a system within itself.

A system designer has to be able to look through multiple viewpoints and change viewpoints frequently. Here, defining the interface is crucial.

Problems with Systems

• There’s more than one way to look at a system (viewpoints) and typically no single way of looking at the system is right.
• Incommensurate scaling, a design that works well when it’s small screws up when it’s large because not everything scales at the same rate.
• Example: a star network (hub with many terminals connected to it) - number of wires scales well, but the hub doesn’t - “diseconomy of scale”.
• Adam Smith’s Wealth of Nations has an example of “economy of scale:” a factory produces pins for a town instead of each townsperson making his/her own pins.
• Emergent properties, the properties of the system that are unanticipated and are not seen until the system is scaled.
• Example: Tacoma Narrows bridges, where engineers forgot to take into account extremely high wind speeds.
• Example: computer worms.
• Example: campus networks.
• Propagation of effects, a change in one module causes other modules to break.
• Example: weather: a chaotic system.
• Example: Microsoft’s operating system.
• Feature A: file/folder names can be separated by forward or back slash.Eg: c:\ab\cd\ef.txt
• Feature B: multibyte encoding for large character sets (Japanese). The 2nd part of a Japanese character, if happened to be the code for forward or back slash, would interfere with the folder/file parsing.
• Example: Kaminsky DNS design flaw. DNS queries use UDP which can be forged.Therefore the DNS response can be easily forged which results in DNS spoofing attack. Defenses: clients ignore responses that don’t match the query. However, since DNS queries are hierarchical, it is more advantageous for an attacker to forge the top-level domain (TLD) DNS responses which in effect forges every subdomain under it.
• Waterbed effect: if you push in one place, the system will push back in another place.
• Example: time-space tradeoff. Pushing down on the time results in a push back on space, and vice versa. Sorting a 1GB array of 1KB entries is fastest when done read-only, i.e. creating a 2nd array of pointers that is sorted instead of modifying the original array. This is because the cost of a swap action is the main factor contributing to the time of sort.
• Complexity: the systems that we’re building are too complicated to be understood by any single person. Part of the blame is Moore’s Law - hardware guys keep building devices that have more and more transistors. Kryder’s Law: disk space keeps increasing at a fast pace.

There are more transistors per chip so the operating system has to manage this complexity.  Hardware is becoming much more adept at running large systems, so while designing operating systems, the main goal should be to minimize complexity.

Reading assignment: Sections 1 - 2C from the textbook.