CS 111 Scribe Notes (Lecture 1, Winter 2013)

 

By: Tiancheng Zhao, Huangshuoyu Weng and Cory Desautels

 

Course Information:

 

Instructor:

á      Paul Eggert

 

Course Website:

á      http://cs.uca.edu/classes/winter13/cs111

 

Textbook:

á      Jerome H. Saltzer and M. Frans Kaashoek, Principles of Computer System Design: An Introduction, Morgan Kaufmann (2009)

 

Course Prerequisite:

Required:

á      CS32

á      CS33

á      CS35L

Recommended:

á      CS118

á      CS151b

á      CS131

 

Course workload:

á      Lecture: 4 hours/week

á      Discussion/Lab: 2 hours/week

á      Outside study: 9 hours/week

 

Lectures, Exams and Assignments:

á      17 Lectures (MW)

á      1 Midterm on Feb 11th

o   100 minutes

o   Open book/notes

á      1 Final

o   180 minutes

o    Open book/notes

á      4 Labs:

1.     Write a shell

2.     Kernel hacking

3.     File system hacking

4.     Something distributed

á      2 Mini Labs:

1.     Scheduling

2.     Virtual memory

á      1 Design Problem

o   Written report and presentation

o   1 week after the lab

á      1 Scribe Note

o   Team up to 4.

o   1 week after lecture.

¤  Except for the midterm week, the deadline is 5 days after the lecture

á      1 2-3-page paper:

o    About current issue (due last week)

 

Note: The Friday of the last week 23:59:59 is the final deadline for all assignments.

 

Grading Policy:

 

Fraction of Grade

Midterm

1/9

Final

2/9

Labs

1/12 for each

Design Problem

1/12

Mini Labs

1/15 for each

Scribe Note

1/20

Paper

1/15

 

Late Penalty:

á      2 ^ (n-1) points will be deduced from the project, where n is the number of days off. Therefore, the score will be less than zero for more than a week off.

 

Next Lecture:

á      Reading assignment for the next lecture: chapter 1.1 – 2.3

 

Introduction to Operating System

 

"We don't offer a ready mode program, but an entire operating system" - M. Weisband Pirate Party (Germany)

 

What is a system?

 

á      According to Oxford English Dictionary (original - 1928)

 

1. An organized or connected group of objects

2. A set of principles, etc; a scheme or a method

 

á      Definitions from Latin: organized whole, governmental, constitution, flock of birds, musical intervals, verses in a poem 

Root = "set up with"

 

 

2. What is an operating system?

 

á      Encarta 2007: a master control program in a computer (The first OS called MCP)

 

á      Wikipedia 531774181: a collection of software that manages computer hardware resources and provides common services for computer programs.

 

o   Resources: for example, the available hard drive size

o   Common services: for example, providing a standard way to talk to the network system.

 

á      The MIT definition: A system is a set of interconnected components that has a specified behavior observed at the interface with its environment 

 

 


 

 

á      This model provides a generic picture of system, however, the reality is not usually so simple.

           

3. Problems with computer systems:

 

á      Tradeoff: waterbed effect (pushing down here, everything else pops up)

 

o   Example1: sorting 

We have a 1 GB array with 512 bytes for each record, so we have 2^20 records. The overhead of sorting is the time for copying data.

 

Assume we use merge sort, then we have to do O (NlogN) copies.

Supposed we want to make the algorithm 100 times faster, we can use an array of pointers pointing to each record so that when we do sorting, we only need to copy pointers rather than the whole record.

Since the size of pointer is 4 bytes, we speed up the algorithm by 512/4 = 128 times

¤  The tradeoff is: 

a. We have to dereference the pointers, which takes time (slow down the comparison) 

b. Increase the memory overhead about 1/128

 

o   Example2: RSA Service ID + password -> increased security

 

¤  Many new downsides: inconvenience, etc.

 

á      Incommensurate scaling: (quantitative measures)

 

Not everything scales at the same rate.

o   For example, why are we not 2m tall?

Answer: Bones will break. The strength of bone scales O(N^2) and weight scales O(N^3). Therefore, the bone strength will not grow as fast as the weight.

(Assumption for mobile land animal)

 

o   Smith: Economics of scales

¤  Example: By building a pin factory, one can make pin production far more efficient than homemade pin as the number of customers grows. 

However, building such a factory will cause waste.

 

o   Diseconomies of scale: Ethernet switches

¤  4/8 port Ethernet switch is cheap

512 port Ethernet switch is expensive 

(Cause things break as we scale up)

 

á      Emergent properties (unanticipated before scaling) (Qualitative measures)

 

o   Example:

Napster (emerging property of a wired campus)

Computer worms after the invention of Internet.

Tacoma narrows bridge (wind resonant frequency of a large size)

 

á      Propagation of effects: Reagan becomes president because of a suicide

 

o   Propagation of effects happens naturally all the time in chaotic systems, such as butterfly effect.

It can also happen in engineered systems:

o   Any change to one subsystem may cause another subsystem to break

o   Example:

In one OS, \usr\bin\foo file names &separator

Another system, SJIS (the first byte flag, the rest 15 bytes is payload)  Multi bytes characters

 

Then: cp a.out\usr\bin\???

no directory: \usr\bin\??? when the characters happened to have exactly the same as '\'

 

The current fix is to use UTFA rather ASCII to encode the characters