COMP 3000 2012 Week 2 Notes - Revision history

Cdelahou: /* Boot Process Sidenote */

2012-09-24T17:20:24Z

Boot Process Sidenote

← Older revision		Revision as of 17:20, 24 September 2012
Line 177:		Line 177:
	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.		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 [http://en.wikipedia.org/wiki/Bootstrapping#Computing \| boostrapping (aka. booting)]		See [http://en.wikipedia.org/wiki/Bootstrapping#Computing boostrapping (aka. booting)]

	== Sidenote ==		== Sidenote ==

Cdelahou: Added a few tidbitties. Fixed a tiny bit of formatting here and there.

2012-09-24T17:20:05Z

Added a few tidbitties. Fixed a tiny bit of formatting here and there.

← Older revision		Revision as of 17:20, 24 September 2012
Line 72:		Line 72:
	1900		1900
	* separation of math/logic and computation		* separation of math/logic and computation
	* Hilbert proposes entscheidungsproblem		** A person was either a mathematician/logician (one who developed the field) or a "computer" (a technician within the field)
			* Hilbert proposes the [http://en.wikipedia.org/wiki/Entscheidungsproblem entscheidungsproblem]
	** decision problems		** decision problems
	** input: statement in first order logic		** input: statement in first order logic
Line 81:		Line 82:
	** Church creates Lambda Calculus		** Church creates Lambda Calculus
	** Kleene creates µ-recursive functions		** Kleene creates µ-recursive functions
	** Turing creates Turing Machines		** Turing creates Turing Machines
	* negative answer to entscheidungsproblem		*** His paper [http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf "On computable numbers, with an application to the Entscheidungsproblem"] gives negative answer to entscheidungsproblem


	== What is Computation? ==		== What is Computation? ==
Line 140:		Line 142:
	== Boot Process ==		== Boot Process ==

	# press switch: power -> motherboard		# press switch: power to motherboard
	# motherboard		# motherboard
	## says "power ok"		## says "power ok"
	## turns on CPU		## turns on CPU
	# x86		# x86
	## switches to real mode		## switches to real mode -> no muiltitasking
	## executes instruction at ~~ffffffffh~~		## executes instruction at 0xffffffffh
	# Power On Self Test (POST) run by Basic I/O System (BIOS)		# Power On Self Test (POST) run by Basic I/O System (BIOS)
	# BIOS loads MBR ~~(446~~ bytes)		::: (note: this is a legacy system --> UEFI is used by more modern systems -- Macs and smartphones)
			# BIOS loads [http://en.wikipedia.org/wiki/Master_boot_record MBR]
			## Contained in first sector of drive
			## >= 512 bytes
	# MBR contains		# MBR contains
	## bootloader (GRUB stage 1)		## bootloader (GRUB stage 1)
Line 157:		Line 162:
	## stage 1 in MBR		## stage 1 in MBR
	## stage 1.5 usually in the first 30kB of HDD		## stage 1.5 usually in the first 30kB of HDD
	## stage 2 loads /~~etct~~/grub.conf or /boot/menu.lst		### Loads file system driver
	### grub> kernel /zimage-2.6.14		## stage 2 loads /etc/grub.conf or /boot/menu.lst
			### grub> kernel /zimage-2.6.xx
	### grub> initrd (initial ram disk -- initrd2.6.xx.img)		### grub> initrd (initial ram disk -- initrd2.6.xx.img)
	### grub> boot		### grub> boot
	# start()		# start() called
	~~# start_kernel()~~		# startup_32() called which decompresses the linux-kernel
	~~# cpu_idle()~~
	# startup_32() fn called ~~--> decompress~~ linux-kernel
	# start_kernel() --> /init/main.c starts scheduler		# start_kernel() --> /init/main.c starts scheduler
	# cpu_idle() ---> tells CP to idle		# 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 [http://en.wikipedia.org/wiki/Bootstrapping#Computing \| boostrapping (aka. booting)]

	== Sidenote ==		== Sidenote ==

Sdp: added links to Adder, NAND, D flip-flops, and registers

2012-09-18T21:22:21Z

added links to Adder, NAND, D flip-flops, and registers

← Older revision		Revision as of 21:22, 18 September 2012
Line 104:		Line 104:
	=== Adder ===		=== Adder ===

			[https://en.wikipedia.org/wiki/Adder_(electronics) Adder]

	=== NAND gate using transistors ===		=== NAND gate using transistors ===

			[https://en.wikipedia.org/wiki/NAND_gate NAND gate]

	=== register with transistors ===		=== register with transistors ===

			[https://en.wikipedia.org/wiki/D_flip-flops#D_flip-flop D flip flop] built using NAND gates

			[https://en.wikipedia.org/wiki/Shift_register Shift register] built using flip-flops

	=== microprocessor architecture ===		=== microprocessor architecture ===

Sdp: added week 2 notes

2012-09-18T21:10:09Z

added week 2 notes

New page

== 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 ===

=== 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
# 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 ==

* [https://en.wikipedia.org/wiki/Logical_block_addressing|Logical 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