CS 111 Operating Systems

Scribe Notes for Lecture 1, Winter 2015
By Crystal Hsieh and Tim Tang | January 5, 2015

Opening Example

Let's try creating a large file that has ~10^9 bytes, named "big."

$ ls -l big -rw-rw-r-- 1 eggert faculty 9223372036854775000 Oct 6 11:31 big
(meaning: read writable, 1 hard link, owned by eggert, number of bytes, dated)

After creating such a large file, about how long would it take for us to search for the character 'x'?
We can use the command "grep" to search through the file.

$ grep x big
(meaning: look through the entire file for character 'x', show that line)

The grep function outputs nothing, which means that it couldn't find 'x' in our file.
We can use the command "time" to figure out how long it takes for the computer to search!

$ time grep x big 

  real 0m0.009s

The speed that it took the computer to look through the huge file was: 10^19 bytes/.01s = 8x10^21 bits/s

We can use another situation regarding speed to put this number in perspective... The estimated total bandwidth of the internet: 167 Tb/s

The fastest way to deliver information over the internet is actually by "Sneakernet," where people physically deliver a hard drive by foot (or delivery services like FedEx).
The idea is further explored here.

Even if people filled gallon jugs with 25,000 MicroSD cards to transport data, the fastest that they could transfer information would be 0.5 Zb/s !
How is it possible that "grep" could search a gigantic file by 8 Zb/s?

Even when adding 'x' to the big file, grep can quickly identify that the file contains 'x'.


$ echo x>>big 

$ grep x big 

  Binary file 'big' matches

There's tricks in the computer that allow these unusual situations to occur, and this quarter we'll be exploring how the computer is able to perform these actions.

Course Information

Prerequisites: CS31, CS32, CS33, CS35L
Other helpful courses: CS131, CSM151B, CS118
Official Hours/week: 4 lecture, 2 lab, 9 outside study
Real Hours/week: 3.5 lecture, 1.7 lab, 20 outside study
Course Website: http://cs.ucla.edu/classes/winter15/cs111

Course Organization (17 Lectures):

Type	Weight of Grade	Notes
1 Final Exam	(2/9)	180 minutes
1 Midterm	(1/9)	100 minutes, Open Book/Notes
4 Labs	(1/3)	groups of at most 2 - write a shell (with performance features, 3 parts) - kernel hacking - file system - distributed
2 Mini-Labs	(2/15)	Solo, CPU scheduling, virtual memory
1 Design Problem	(1/12)	Groups of 2
1 Scribe Notes	(1/20)	Groups less than or equal to 4, HTML5 or 4.01, Validated Due one week after specified lecture
1 2-3 page research review paper	(1/15)	N/A

Lateness penalty: 23:55 on due date -- There will be 2^(n-1) percent docked per day late.
Drop dead date: March 13th, 2015 (No assignments can be turned in past this date)

Academic Honesty: Many assignments are repeated, so please do not cheat online

Textbook: Saltzer & Kaashaek, Principles of computer system design 2009
Systems in this book is very strong; collides many ideas together
For next time, read Sections 1-2.3

Definitions

Contextual References to Operating Systems

Red Star 4.0
North Korea launches its own OS
2014-12-21 | Sky News (UK)

Crouton for Chromebooks
(run Ubuntu in a browswer tab)
lilputing | 2014-12-28
- Doesn't work with Fedora.. why?

Samsung
Company says new (2015) TVS will run Tizen (LiMo)
c|net | 2015-1-05

Marina Weisbanol (Germany Pirate Party) in The Economist 2013-1-05, p19: "We don't offer a ready-made programme, but an entire operating system."
There's even connections between operating systems and politics!

What is a System?
Oxford English Dictionary (1928)

An organized or connected group of objects
A set of principles, etc., a scheme, method
from ancient Greek systema- organized whole, government, constitution, roots= "set up with"

Our textbook's definition in 1.A.2: a set of interconnected components that has a specified behavior observed at the interface with its environment

What is an Operating System?

Encarta 2007: master control program in a computer
American Heritage 4th edition, 2000: 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 (operating systems were machine specific, back in the 60's)
Wikipedia definition: software that manages computer hardware and software resources and provides common services for computer programs

GOAL OF BUILDING SYSTEMS: CLARITY | How do we make our systems obvious and clean?

Common Systems Problems

Incommensurate scaling
- Diseconomies of Scale (as something gets larger, more expensive per unit)
Example: star network (cost of an 8 port vs. 48 port scales with order n^2)
- Economies of Scale (pin factory from Wealth of Nations)
Example: pin factory - not hard to make a pin, but more efficient of one person in village decides to make many pins at once and thus use specialized equipment; can cause breakage, waste
Emergent properties (qualitative)
- Example: student internet use turned to music piracy, Tacoma Narrows bridge
Propagation of effects
- Example: a well designed system with clean interfaces, can still cross boundaries and create problems
- Further Example: file system using japanese characters
- SJIS - Japanese character setting (30,000ish characters)
- cp a; b c d:(japanese name)
- cannot create director (second half of japanese name looks like backslash)
Tradeoffs
- Waterbed effect (solving a problem in one area creates a problem in another area)
- Example: Sorting Algorithms - there's always a trade-off for which sorting method you choose
Complexity
- Hardware constantly improving
- Example: Moore's Law (complexity doubles every 18-24 months at cheapest design points)

Image From: Passy's World of Mathematics
- Example 2: Kryder's Law - Disk Drive Complexity

Image From: Lev Lafayette