CS 111 Lecture 1 - Scribe Notes 4/2/2013

Michael Chan and William Kwok

Table of Contents

  1. Class organization
    1. Instructor and TAs
    2. Grading Policy
    3. Textbook
    4. Prerequisites
    5. Time Breakdown
  2. Lab 1 Summary
  3. Definition of a System and Operating Systems
  4. Problems in Computer Systems
    1. Tradeoffs
    2. Incommensurate Scaling
    3. Emergent Properties
    4. Propagation of Effects

Class Organization

Computer Science 111 - Operating Systems Principles

Course Description

Introduction to operating systems design and evaluation. Computer software systems performace, robustness, and functionality. Kernel structure, bootstrapping, input/output(I/O) devices and interrupts. Processes and threads; address spaces, memory management and virtual memory. Scheduling, synchronization. File systems: layout, performance, robustness. Distributed systems: networking, remote procedure call (RPC), asynchronous RPC, distributed file systems, transactions. Protection and security. Exercises involving applications using, and internals of, real-world operating systems. Leter grading.

Course Website

Instructor and TAs

Instructor

Teaching Assistants

Grading Policy

Grade Breakdown

Name Fraction of Grade Comments
1 Midterm 1/9
  • 1.8 hours, in-class
  • Open book, open note
1 Final 2/9
  • 2.8 hours
  • Location and time determined by Registrar
  • Open book, open note
4 Labs 1/12 (each)
  • Shell, file system, driver, distributed systems
  • Can work in teams of 2
2 Mini-labs 1/15 (each)
  • Scheduling, virtual memory
  • Done individually
1 Design Problem 1/12
  • Lab expansion
  • Can work in teams of 2
  • Includes written report
1 Research Survey 1/15
  • 2-3 pages
  • Articles assigned 8th week
  • Done individually
1 Scribe Notes 1/20
  • Done in HTML 4.01 or HTML 5
  • Encoded in UTF-8
  • Due a week after lecture

Late Policy

An assignment turned in N days after the due date, 2(N-1) points will be subtracted from the assignment grade. That means that an assignment 1 day late will lose 1 point, an assignment 2 days late will lose 2 points, an assignment 3 days late will lose 4 points, and so on. However, the one exception to this is that all assignments must be turned in by Friday of tenth week. Afterwards no more assignments will be accepted for a grade.

Textbook

Principles of Computer System Design by Jerome H. Saltzer and M. Frans Kaashoek

Prerequisites

Time Breakdown

Official Time Actual Time
Lecture - 4 Hours Lecture - 3.6 Hours
Lab - 2 Hours Lab - 1.7 Hours
Outside Study - 9 Hours Outside Study - 20 Hours

Lab 1 Summary

For Lab 1, we will be focused on reimplementing the shell. We attempt to parallelize the shell and have it execute two independent instructions at the same time. It is divided into 3 parts, 1a, 1b, and 1c. For part 1a (due Weds. 4/10) we will focus on writing the command reader. For part 1b we will focus on writing the standard execution model. For part 1c we will focus on writing the time-traveling mechanism.

Definition of a System and Operating System

What is a System?

Oxford English Dictionary(OED) (1928)

A System is a[n]...

  1. Organized or connected group of objects.
  2. Set of principles, etc. a scheme or method.
  3. Greek - συστημα, which means an organized whole government, constitution, a body of people or animals, musical intervals. Its roots mean "set up with".

What is an Operating System?

Textbook (2009)

A system is a set of interconnected components that has a specified behaviour observed at the interface with its environment.

Environment Interface System
The figure above illustrates how a system interacts with its environment via its interface.

American Heritage Dictionary (4th Edition 2000)

Software designed to control the behaviour of a specific data processing system in order to allow users and application programs to make use of this.

American Heritage Dfn
This figure demonstrates how the Operating System acts as the interface between the user and applications.

Encarta (2007)

The master control program in a computer...

Wikipedia (2013-04-02)

Collection of software that manages computer hardware resources and provides common services for computer programs.

The Evolution of the Operating System

From the above definitions we can observe how the operating system has evolved from being a controller or master between the Users and Applications to being more of a servant or manager.

OS Evolution

What do we want from an Operating System?

  1. Protection
  2. Robustness
  3. Consistency/Simplicity
  4. Performance

Problems in Computer Systems

Tradeoffs

When improving one property will negatively affect another property. Also known as the "Waterbed Effect"

Waterbed
Sorting:The Time-Space Tradeoff

Say there was an array that contained 10^7 items and each item was 100 bytes. The fastest way to sort the array would be Merge Sort, but Merge Sort would also require the most memory to sort through the whole array. An alternative would be to use Quicksort, but Quicksort has the unfortunate side effect of having the time complexity of n^2 if a bad pivot element is chosen. Therefore we can observe how we can either improve execution time while increasing the memory needed or we can improve the amount of memory used at the sake of sacrificing execution time. This is a prime example of a tradeoff.

Incommensurate Scaling

Not everything in your system scales at the same rate

Two types of scaling

  1. Economies of Scale
    • Adam Smith's Pin Factory The inhabitants of a village need pins for everyday life. There are two apporaches that the villagers can take. They can either manually make the pins themselves everytime they need a new pin, or as Smith proposes, they can have a factory that specializes in making pins. The benefits of having a factory is that the factory would be able to pump out more pins at a cheaper cost per pin. Therefore since the cost per pin scales well with the number of customers, this demonstrates economies of scale.
    • Downside: Results in excess waste when the system increases in size.
  2. Diseconomies of Scale
    • Ethernet Hub Example
      • 4-port and 8-port Ethernet Hubs are relatively cheap to make
      • A 1024-port Ethernet Hub would be extremely expensive to manufacture.
      When there are very few ports in a Ethernet Hub, they are easy to purchase and manufacture. However as the number of ports per hub starts to increase, the price of each hub increases drastically. This behaviour is opposite of the pins in Adam Smith's Pin Factory. This demonstrates diseconomies of scale.
    • Downside: Results in breakage when the system gets too large.

Emergent Properties

Unanticipated properties that arise while scaling.

Napster and the Internet

When college dorms first received high speed internet around 1995, everybody thought that it marked a great milestone for the productivity of students who lived on campus. With the internet, many students had at their fingertips an almost unlimited amount of online resources such as research papers and case studies. However the students misused the internet and began to download pirated materials. The vast amount of shared pirated material was an unforseen circumstance to college dorms receiving high speed internet.

Napster Logo
Courtesy of webpages.scu.edu
Tacoma Narrows Bridge

Engineers have built bridges that could withstand hurricane-level winds, earthquakes, and other natural disasters. However when the Tacoma Narrows Bridge was built, no bridge of its size had ever been built before. Therefore the engineers did not forsee that the wind could match the resonant frequency of the bridge. Due to this unanticipated property, the bridge was destroyed by winds in 1940.

Tacoma Narrows
Image of the bridge during its collapse. Courtesy of Wikipedia.org

Propagation of Effects

Natural property of a chaotic system where a small effect in one part of the system results in large ramifications in another unrelated part of the system.

Microsoft Does Japanese Character Encoding

The English language is small enough that all of its characters can be encoded by using one byte of information. With a large, symbolic language like japanese, one byte is not big enough to store all of its characters. Therefore Microsoft decided to use two bytes of data to encode all of its japanese characters. If the first bit of any byte was switched on, this would mean that the computer would read the current byte as an extension of the data from the previous byte. Unfortunately, this functionality was completely independent from the Windows module that parsed filenames (e.g. C:\Desktop\).

Since the parser was not aware of the functionality of the new encoding, if someone attempted to copy a file to a directory, and the directory was written using the japanese multibyte encoding, a mysterious error could potentially appear. The screen would display "no directory named \usr\bin\[?]". If the bits in the second byte managed to form a '\', then the filesystem would get confused and think that the user was trying to copy a file to a directory that doesn't exist.

In order to solve this problem, Microsoft had to change its kernel to deal with the new-found issues of multibyte encoding.

Valid HTML 4.01 Strict