SCRIBE NOTES: LECTURE 2

CS111 Spring 2013

by Evan Stanford




Part 1: Computer Improvement/ Complexity

Moore's Law

The number of transistors on a chip of minimum cost...
                original: doubles every year
                modified: doubles every 18 months
                Eggert: doubles every 2 years
When does it end?
                (can't go on forever)
                People have always been predicting that Moore's Law will end
                                Eggert thinks Moore's Law end will happen "in your [the student's] profession careers"


Kryder's Law

Moore's Law for the number of bytes on a hard drive
Also exponential but at a faster rate than Moore's Law
Note: Neither of these laws says that chips are getting faster (but they are)


Ability to build is growing at a growing rate

The better your tools are, the faster you can improve them
d(technology)/dt = K*technology (rate of technology change is proportional to technology)
therefore technology is increasing at exponential rate
Example
                1st Univac had to be designed very conservatively since they could not model it before building
                2nd Univac used Univac I to help design it, making it less conservative, faster
                ....
                Modern computing tools help us make even better computers


Conclusion:

Alongside increasingly powerful hardware we have developed increasingly complicated software
Our biggest problem is that computers are too complicated
In the next part we will explore a semi-solution:
                >Building the simplest possible operating system



Part 2: A simple program running without a complex operating system

Making an extremely simple operating system:

Advantages:
                More likely to be correct (less bugs)
                Faster
                Less resource intensive
                More secure
Uses:
                Security agencies want very simple OSs (simplicity over speed)
Bad ideas:
                OS X
                Windows
                Linux
                Each of these have millions of lines of code
Instead we will build our own that has a single, simple function


Sample application needed- WORD COUNT (WC)

Problem Definition:
                Functionality:
                                "Count the number of words in my text file"
                UI:
                                Turn computer on, answer (eg 2073) appears on screen
                IO:
                                At address 5,000,000,00 is the start of a text file that is null terminated
                Other software allowed to use:
                                No pre-written drivers allowed due to high complexity
                Hardware:
                                Intel Core i3-2130 3.4GHz 3MiB cache 4 GiB dual channel DDR3 SDRAM 1600 MHz
                                1TB HDD SATA 7200 rpm
                                Intel HD integrated graphics

    Side Note: What does the "i" indicate in memory units?

    GiB Gibibytes -> power of 2 based
    GB Gigabytes -> power of 10 based

                Portability:
                                No portability. Only needs to run on this machine.

Computer Diagram:

    -------      -----------          
    | CPU |      | Display |      
    -------      -----------      
       |            |                
================================================================BUS    
             |           |                    |
          -------     -------         -------------------
          | ROM |     | RAM |         | Disk controller |
          -------     -------         -------------------
                         ^
                         |
               Starts at random values, then set to 0

Flawed Solution 1:

Have the program start in RAM such that when the computer boots up the IP will be at the start of the program and it just executes
Flaw:
                The RAM is volatile and will be empty/contain random values on boot up
Question:
                How do you get memory into RAM when computer starts without memory in RAM?
Bootstrapping issue. You can't lift yourself by your own bootstraps
Answer: ROM (Read Only Memory)
                This is nonvolatile


Flawed Solution 2:

Put the program in ROM
Flaw:
                Impractical: Since you can't write to ROM you would have to have Dell make a one-off which would cost too much
                Inflexible: you could never change the program
ROM must contain standard software, the BIOS

  BIOS:

  Basic Input/Output System
  Basically hardwired into ROM
                (possible to Flash it but this is rare to do)
  IP (instruction pointer) initially points into BIOS
  BIOS basic procedure:
                1. Checks computer for correctness
                2. Look for devices
                3. Look for devices that are bootable (bootable is shorthand for bootstrapable)
                                How to tell if bootable:
                                                Read first sector of device and bits may look like a Master Boot Record (MBR)
                                                MBR:
                                                                Has to work with Hardware manufactures and OS writers
                                                                What it looks like:

  Memory Diagrams

  Full Drive
  --------------------------------------------------------------------------
  ][   A    ][   sector 1      ][   sector 2 ][   sector 3  ][  sector 4  ][
  --------------------------------------------------------------------------


  A:
  Bytes:                                             64               2
  --------------------------------------------------------------------------
  ][   machine code (x86) + data            ][ 16 | 16 | 16  | 16 ][0xAA55][
  --------------------------------------------------------------------------
                                              ^                     ^
                                              |                     |
                                              |    Standard ending 16 bits
                                              |    to denote Bootable device
                                              |
                                              |
                                     16 bytes near end:
                                         (4byte)sector number of partition start
                                         (4byte)number of sectors in partition
                                         ()status (eg bootable)
                                         (1byte)type

Flawed Solution 3:

Put the program in the MBR
Flaw:
                MBR has limited size
                our program is too big


Correct Solution:

Put a tiny program in the MBR that will
                1. copy the WC program from disk to RAM
                2. jump into WC

Full boot procedure (as used on Ubuntu and others):

                1. BIOS loads MBR boot loader (OS agnostic)
                2. MBR loads VBR
                                -volume boot record
                                -at start of partition
                3. VBR loads GRUB
                                -grand unified boot loader
                4. GRUB loads linux kernel
                5. Linux Kernel loads 'init'
                                -init is process 1
                                -main job is to start other programs
                6. init loads other programs including shell
                7. shell loads more programs...


Example boot loader source code for Word Count (WC):

                (would usually be in machine code, but we will use C for simplicity) 
void read_sector(int s, intptr_t a);
void wait_for_disk (void);

int main(void) {
	for(int i=1; i<= 20; i++)
		//move memory
		read_sector(i, 0x100000 + (i-1)*512);
		//go to that place in memory so that you will execute the program
		goto *0x100000;	
}


void read_sector(int s, intptr_t a) {
	//check if busy
	wait_for_disk();
	
	//outb(dest, source)
		//take source value,
		//move it into dest register
	outb(0x1f2, 1); // <- number of sectors = 1
	
	//tell the disk controller "s" (source)
	//must break into 4 out byte instructions because int is 4 bytes, outb can only take 1 byte
	outb(0x1f3, s       & 0xff);
	outb(0x1f4, (s>>8 ) & 0xff);
	outb(0x1f5, (s>>16) & 0xff);
	outb(0x1f6, (s>>24) & 0xff);
	
	//now change status register (same reg as read in while loop)
	outb(0x1f7, (s>>24) & 0x20);
	//insl -> l means 4 btye chunks (l for long)
	insl (0x1f0, a, 128) // a is address we are reading into
	//128 in number of longs, 128*4bytes total
	

}

void wait_for_disk (void) {
	//mask out all but first 2 bits by bit & with  0xc0
	//check if first 2 bits are 01
	//0x1f7 is a special bus address that is the disk controller
	while ((inb (0x1f7) & 0xc0) != 0x40)
		continue; //Eggert likes to write continue because it is more clear than just a semicolon
}

Memory Diagram of this copy:

DISK
--------------------------------------------------------
][ MBR ][ rest of disk    | WC |                      ][
--------------------------------------------------------
                            |
                            |----What example boot loader is doing
RAM                         v
--------------------------------------------------------
][                     ][   WC    ][                  ][
--------------------------------------------------------

WC program code:

void write_out(int nwords);

int main(void) {
	int nwords  = 0;
	bool inwords = 0;
	int s = 5000000000/512;
	
	for (;;s++) {
		char buf [512];
		read_sector(s, (int ptr_t) buf);
		for (int j=0; j<512; j++) {
			//if null byte/end of file
			if (!buf[j]) {
				write_out(nwords)
				return;
			}
			//we want to make upper to lower case by flipping bit
			char uc = buf[j] & ('a'-'A');
			bool thisalpha = 'a' <= buf[j]&& uc <='z');
			//if we are not in a word and we see an alpha-numeric char we now it is a new word
			nwords += ~nwords & thisalpha;
			inword = thisalpha; //updates where or not we are in a word
		}
	}
}

//how this will work:
//there is an array in memory in memory that has every pixel, which we will modify

----------------------------------------------
       |  |  |  |  0xB8000                    
----------------------------------------------
//2 bytes per character location

void write_out( int nwords )	 {
	char *p = (char *) 0xb8004 + 24*80
	do {
		*--p = nwords %10 + '0';
		*--p = 7 //gray on black;
	} while ((nwords /= 10) != 0;)
}



Due to overwhelmed email servers I request that users stop sending me compliments on my text diagrams.