Lecture 1: An Introduction

Written by Breanna Nery

Course Overview

I am the egg man.
Quick Facts:

Course Organization

Hour Breakdown
Work Suggested Hours
Lecture 3.7
Discussion 1.7
Outside Work 9-15
  • Labs: 4 labs which may be with a partner
  • Design Problem: An extension to a lab. May be with a partner
  • Minilabs: Solo labs.
  • Scribe Notes: Lecture notes.
  • OS Paper: A 2-3 paged paper on a recent topic in operating systems
  • Midterm: 100 minutes in class. Open note.
  • Final: 180 minutes. Open note.
Late Policy

Assignments are due 23:55. You will lose 2N-1 points for N days late. The policy ends on the last friday of class

Defining an Operating System

Before we define an operating system, we must define a system. In 1928, the Oxford-English Dictionary defined a system to be one of two things:

  1. An organized or connected group of objects
  2. A set of principles, ect., a scheme, method

But how is an operating system defined? Below we explore three different definitions.

  1. American Heritage Dictionary (2000): Software designed to control hardware of a specific data processing system in order to allow users and apps to make use of it.
  2. Bill Gates (2007): The Master control program in a computer.
  3. Wikipedia (2016-01-04): A collection of smaller programs and software that is used to control and operate the computer system.

What's missing in the definitions? A lot! Below are some key issues we will be discussing in CS 111:

  • Resource Management
  • Reliability and Error Handling
  • Security

Example: Grep

The grep command line utility gives us insight to some interesting operating system features. For example, let's say we have a file named 'big' with the following properties:


        $ ls -l big
        -rw-rw-r- -l eggert 9223372036854773000 Oct 6 11:31

The command below attempts to measure the time it takes for the grep utility to search for the character 'x' in the file 'big'. Due to the large size of the file, we expect the grep utility to take a long time to complete this task.


        $ time grep x big
        real 0m0.009s

Based on the file size, the measurement indicates that file was being searched at rate of 1022 bits per second or 8 zettabits per second. To put this speed in perspective, we can consider the following speeds:

  • The entire bandwith of the internet is 167 terabits per second. This is equivalent to only 10 11 bits per second.
  • xkcd What if? #31 asks a follow-up question: When will the bandwidth of the Internet surpass that of FedEx? The answer is not likely, as the entire freight industry has the ability to transfer 500 exabits per second. This is equivalent to only 0.5 zettabits per second. Grep is still faster!

So how is it that grep is faster? The 'big' file is stored in a Zeta File System, which represents the intensional 'big' file by a data structure containing properties of the file. One property, for example, would be if the file 'big' contained any x's or not. We can apply this example to a real life application like scanning for a virus in a file with hundreds of null characters. The naive approach of finding a virus would be to read the file bit by bit in order to find the malicious code. Instead, a smart virus scanner would skip the nulls until it hits the malicious code.

Common Problems in Operating System Design

All fields face multiple design challenges when designing a system. Here are four issues and examples that occur in OS design.

  1. Incommensurate Scaling:
    Not everything scales at the same rate. In economics, we can draw analogy between time complexity and the economies and diseconomies of scale.
    • Economies of Scale: As a system grows, the cost per unit decreases. This is analogous to O(log N).
    • Diseconomies of Scale: As a system grows, the cost per unit increases. This is analogous to O(N2).
  2. Propagation of Effects:
    The pathways for propagation are more effective. A small change in one subcomponent can create a huge issue in another component.

    Example: Internation Characters and the File System
    Microsoft used Shift JIS to encode japanese characters. The first byte is used to map japanese characters, whereas the second byte can potentionally be interpreted as an unintended character. An example of this the yen character represented by 0x5C. The second byte of 0x5C also represents the backslash character which cause issues in areas like a file path. The solution? Use UTF-8.

  3. Tradeoffs (The Waterbed Effect):
    Every design choice comes with a trade off in what you gain and what you lose.
    Example: Security Tradeoffs - Passwords versus RSA SecurID + Password
    • Passwords: Simple and Insecure
    • RSA SecurID + Password: Complicated and Secure