CS 111

Lecture #1 Scribe Notes for 1/7/08

by David Chien, Sylvano Doddick, Justin Chun Chuen Yu


Professor: Paul Eggert
                OH: M 12:00 - 1:00 p.m., W 2:00 - 3:00 p.m.
                Boelter Hall 4532J;
                Email: eggert@cs.ucla.edu
TA: Donald Lam
                OH: T 9:30-10:30 a.m., R 9:30 - 10:30 a.m.
                Boelter Hall 4428;
                Email: donaldl@cs.ucla.edu
TA: Ian Ku
                OH: T 1:30 - 2:30 p.m., R 3:30 - 4:30 p.m.
                Boelter Hall 4428;
                Email: ianku@cs.ucla.edu

Website for Submitting Assignments:
                            http://courseweb.seas.ucla.edu
Supplementary Course Websites:
                            http://www.cs.ucla.edu/classes/winter08/cs111/
                            http://www.read.cs.ucla.edu/111/

Pre-requisites: CS 32, CS 33
Helpful to know: Computer Architecture CS 151, Programming Languages CS 131, Networking CS 118

Hours/Week

Nominal

In Reality

Lecture  

4

3.5

Lab Discussion 

2

1.5

Outside Study

6

6-20


Read for Next Lecture: Chapters 1-2 of Saltzer & Kaashoek.

Class Format:
  • 17 Lectures
  • 1 Midterm  2/11, 100 Minutes, Open Book/Notes
  • 1 Final   3/17, 180 Minutes, Open Book/Notes
  • 4 Labs   (Work in groups of 2)
    • Lab 1a Write a Shell Due 1/15
    • Lab 1b Write a Shell Due 1/25
    • Lab 2 Kernel Hacking Due 2/11
    • Lab 3 File System Due 2/27
    • Lab 4 Prototype? Due 3/13
    • 2 Minilabs  (Work individually) - Smaller/Small OSes
  • 1 Design Problem Oral Presentation and Written Report Required
       Negotiate with TA, Group Assignment
  • Scribe Notes
  • 1 Page Research Summary Paper at end of class

We will be programming in C;
Textbook/Course Reader can be purchased at 1137 Westwood Blvd for $20;

Grading:  1/3 Labs (Evenly Distributed)
       1/3 Exams (20% Final, 13.333% Midterm)
       1/3 Everything Else (Minilabs, reports, scribe notes, other)

Lateness Penalty:  One letter grade per day late.
   3 free late days for whole quarter.
   No work accepted after last day of discussion.
   Assignments are due 23:59:59 on the due date.

The textbook is about Computer Systems.
The course is about Operating Systems.
The common word in both is Systems!!!






WHAT IS A SYSTEM (Our Class Brainstorm Definition)?
   - Different parts composed into a while to accomplish a goal?

Oxford English Dictionary (OED) of 1928's Definition of a System:
   - An organized or connected group of objects; A set of principles, etc.; a scheme, method;
   - Originated from Greek word which means organized whole, government, constitution, a body of men or animals, musical interval, group of connected verses in a poem; the root of the wokd means to "setup with;"

American Heritage Definition of an Operating System (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;

Encarta Definition of an Operating System (2007):
   - Master control program in computer;

Wikipedia Definition of an Operating System (119834131):
   - A set of computer programs that manages the hardware and
software resources of a computer;

CS 111 Textbook Definition of a System (Best Definition):
   - A system is a set of interconnected components that has a specified behavior observed at the interface with its environment;

                 















Real World Example: Classroom is a system
Components:
   - The different aspects or parts of a system;
   - e.g. Walls, Doors, Blackboard, Electric Circuit, Lights, TV, Professor, Students, Knowledge, and more...

Interfaces:
   - The method which the system components relate or interact with the outside environment;
   - e.g. Switch, Power Interfaces, Building Codes (Wall Strength, Door Size, etc.), and more...



PROBLEMS WITH COMPUTER SYSTEMS

   - Tradeoffs (Waterbed effect, no free lunch!)
   - When choosing between two implementation options, there are always advantages and disadvantages that come with each choice; This idea is called tradeoffs;

ex. 1) Sort a big array of big objects
   
   Option 1: Sort objects in an array
      Advantages:
        - Doesn't require more memory space
        - Doesn't have any added costs
      Disadvantages:
        - Takes a long time to reorder the objects

          





   
   Option 2: Sort array of pointers to objects in array (Indirection)
                    Array of pointers to objects in array (Needs to Be Sorted)
      Advantages:
         - Takes less time to reorder the objects
      Disadvantages:
        - Requires more memory space
        - Has an added dereference cost

We see the theme of tradeoffs as each option provides its own advantages and disadvantages;


ex 2) Authentication (User access security)
   
   Option 1: Traditional Password/Username
      Advantages:
        - Doesn't require increased hardware costs
      Disadvantages:
        - Less reliable (a simple keyboard bug can jeopardize the system)
        - Users will be unaware of hacked usernames and passwords
   
   Option 2: Hardware Token Based Authentication
      Advantages:
        - More reliable (token must be stolen to jeopardize the system)
        - Users will know when their account is exposed when they lose
           their hardware token
      Disadvantages:
        Increased hardware costs.

Again, we see the recurring theme of trade offs as each option provides its own advantages and disadvantages;



Incommensurate Scaling (Things don't scale at same rate)

ex 1) 
   Q: Why aren't people taller?
   A: Human mass increases by a factor of n3 whereas
       "strength" increases by n2.

ex 2) Economies of scale - Pin Factory by Adam Smith
      Advantages:
        - Reduced individual cost for consumers
        - Faster production in larger quantities
      Disadvantages:
        - Increased capital and shipping costs
        - Wastage as more units are made than sold

Again, we see the recurring theme of tradeoffs as each option provides its own advantages and disadvantages; ex 3) Diseconomies of scale - Star Network
        - Less Robust/Reliable (if master server crashes, system breaks)
        - As clients increase, master server may not be able to handle it


Emerging Properties (Unanticipated before scaling)

ex 1)  Tacoma Narrows Bridge
   - Engineers didn't take into account that if the wind caused the
     bridge to oscillate at its resonant frequency, the bridge would break

ex 2) Computer Worms
   - Good in the beginning and in small network environment; went
      badly with the expansion of Internet and malicious software developers 

ex 3) Campus High-Band Networks
   - Networks opened the door for illegal file sharing programs such
     as Napster


Propagation  of Effects (Changes in one place can cause undesirable results)

This is normally seen in chaotic systems such as the weather where one event in the arctic can cause a storm in other continents;

ex) 8-bit Character Sets with Multi-byte Encodings for Text
     - There are a limited number of characters, thus we can't
        normally type Chinese or Japanese characters.

              







Unfortunately, multi-byte encoding is not recognized at lower levels, thus the command line will not recognize the command since '/' is a reserved character in UNIX for directory;

Solutions:
  1. Use a different character instead of '/' for the multi-byte encoding
  2. Change OS so it recognizes multi-byte encoding

Both approaches work, but remember trade-offs!

Complexity (Very popular with computers)
   - Why?
  - Moore's Law - number of transistors on an integrated circuit
                          (at minimum cost) doubles approximately
                          every two years (exponential)
  - Kryder's Law - disk drive capacity grows exponentially



How to cope with complexity:
   - Modularity - break things into pieces/components

ex) Suppose the cost for finding a bug ?N (where N is the size of the system)

K modules
N lines of code
Bugs ? N
If there are no modules; debug time = Bugs*n ~ n2< /SUP >
If there are K modules, debug time = K*(Bugs/K*n/K) ~ n2/K

< BR >
Abstraction - use "nice" pieces or the simplest interfaces