COMP 3000 2012 Week 2 Notes

History of OS

Or: before we make a computer from scratch, we first have to create the universe!

With Saran Neti

0 seconds

• big bang

10^-46 seconds

• gravity separates

10^-36 seconds

• strong nuclear force
• inflation

10^-12 seconds

• electromagnetic force

300,000 years

• free electrons are captured

9 billion years (4.6 billion years ago)

• solar system forms

4 billion years ago

• first life

200 million years ago

• mammals

65 million years ago

• dinosaur extinction (critical to our existence)

200 thousand years ago

• homo sapiens

70 thousand years ago

• geometric patterns

30 thousand years ago

• quantify time (in France)

3400 B.C.

• decimal number system (in Mesopotamia)

3400 - 500 B.C.

• zero
• infinity
• recursion

500 B.C.

• Aristotle
• Euclid
• Eratosthenes

0 - 1700 A.D.

• nothing

1700 A.D.

• function
• Bernoulli
• Euler

1850

• Cantor's set theory
• axiomatic systems
• boolean logic (Boole)

1900

• separation of math/logic and computation
  • A person was either a mathematician/logician (one who developed the field) or a "computer" (a technician within the field)
• Hilbert proposes the entscheidungsproblem
  • decision problems
  • input: statement in first order logic
  • output: yes or no

1936

• Equivalent and universal models of computation
  • Church creates Lambda Calculus
  • Kleene creates µ-recursive functions
  • Turing creates Turing Machines
    • His paper "On computable numbers, with an application to the Entscheidungsproblem" gives negative answer to entscheidungsproblem

What is Computation?

• calculating functions

Electronics

Or: we have to go deeper!

• and gate
• or gate
• nand gate (universal)

output = sort( input ): input, output ∈ N

Combinational Logic

• truth tables

Adder

Adder

NAND gate using transistors

NAND gate

register with transistors

D flip flop built using NAND gates

Shift register built using flip-flops

microprocessor architecture

• ALU (flip flops)
• registers
• instruction register
  • where the instruction is stored
• instruction decoder
  • where the instruction is decoded
• memory I/O controller
  • connects to RAM
• clock
• interrupts

Sorting

• require OS services
  • load code into RAM
  • start execution
  • access memory
  • display answer
  • exit

Boot Process

1. press switch: power to motherboard
2. motherboard
   1. says "power ok"
   2. turns on CPU
3. x86
   1. switches to real mode -> no muiltitasking
   2. executes instruction at 0xffffffffh
4. Power On Self Test (POST) run by Basic I/O System (BIOS)

(note: this is a legacy system --> UEFI is used by more modern systems -- Macs and smartphones)

1. BIOS loads MBR
   1. Contained in first sector of drive
   2. >= 512 bytes
2. MBR contains
   1. bootloader (GRUB stage 1)
      1. loads GRUB stage 1.5
   2. partition table
   3. magic numbers like 55aah
3. GRUB
   1. stage 1 in MBR
   2. stage 1.5 usually in the first 30kB of HDD
      1. Loads file system driver
   3. stage 2 loads /etc/grub.conf or /boot/menu.lst
      1. grub> kernel /zimage-2.6.xx
      2. grub> initrd (initial ram disk -- initrd2.6.xx.img)
      3. grub> boot
4. start() called
5. startup_32() called which decompresses the linux-kernel
6. start_kernel() --> /init/main.c starts scheduler
7. cpu_idle() ---> tells CPU to idle

Boot Process Sidenote

If you're using a regular PC, one that uses a BIOS and all that good stuff, when you first turn it on, it believes it's in the 80's. It doesn't know how to read the filesystem or really do anything. That's why it's called a boot PROCESS. All resources need to be loaded sequentially. Dependencies (ie. FS drivers, etc...) need to be loaded before other processes can run.

See boostrapping (aka. booting)

Sidenote

Difference between core and CPU: cores are different CPUs on a single chip, concurrency controlled on chip.

Partitions and Boot Loading

• Block Addressing (LBA)
• boot process is staged, largely as legacy support
  • BIOS loads first 512 bytes in 8086 mode
  • each further stage loads more space and shifts to more modern mode
  • at some point the initial ram disk including kernel modules
  • at some other point the kernel can be loaded
  • finally, the kernel can take over
• EFI is an intel standard competing with BIOS
  • implemented on mac
• WUBI is some flavour of linux that acts like another version of windows
• initial ramdisk (initrd)
  • a filesystem in the ram for storage during the boot process
• once kernel is loaded
  • kernel contains almost nothing when first loaded
  • the kernel is told about the initrd, on which are installed initial kernel modules
  • kernel loads in modules that have drivers and extensions
    • modules are special C object files
    • modprobe lets you load modules and tell you what modules are loaded
• first program that is run: /sbin/init
  • always has to run
  • process id (pid) of 1
  • loads things like init.d