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
• Hilbert proposes 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
• 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 -> motherboard
2. motherboard
   1. says "power ok"
   2. turns on CPU
3. x86
   1. switches to real mode
   2. executes instruction at ffffffffh
4. Power On Self Test (POST) run by Basic I/O System (BIOS)
5. BIOS loads MBR (446 bytes)
6. MBR contains
   1. bootloader (GRUB stage 1)
      1. loads GRUB stage 1.5
   2. partition table
   3. magic numbers like 55aah
7. GRUB
   1. stage 1 in MBR
   2. stage 1.5 usually in the first 30kB of HDD
   3. stage 2 loads /etct/grub.conf or /boot/menu.lst
      1. grub> kernel /zimage-2.6.14
      2. grub> initrd (initial ram disk -- initrd2.6.xx.img)
      3. grub> boot
8. start()
9. start_kernel()
10. cpu_idle()
11. startup_32() fn called --> decompress linux-kernel
12. start_kernel() --> /init/main.c starts scheduler
13. cpu_idle() ---> tells CP to idle

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