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