COM SCI 111

Lecture 2: Abstractions and Bootstrapping


by Jiuru Shao, Shuang Wang and Haoxiang Zhang

A Bit More OS Philosophy


Last time, we talked about 4 common system problems:

  • Incommensurate scaling
  • Emergent properties
  • Propagation of effects
  • Tradeoffs

These issues occur in traditional engineering systems and they have been with us for a long time. One issue is relatively new and is special to computer systems:

  • COMPLEXITY

Our computer system is getting more and more complicated. And it's getting worse with time. Take a look at Moore's Law, which states that the number of transistors on a mass-produce chip doubles every 18-24 months.

Consider also Kryder's Law, which applies to secondary storage capacity. The capacity of a hard disk also has an exponential growth.

We are really good at making things more complex. But we are not so good at making things faster. The log scale growth does not apply to the processor clock speed or average seek time, but only applies to the complexity of hardware devices. Here again, we have the issue of imcommansurate scaling.

Why exponential growth?

  • UNIVAC I
    •     - error correction circuitry everywhere
        - slow the machine down
  • UNIVAC II
    •     - use UNIVAC I to design
d(technology)/dt = K*technology

The solution is exponential with respect to time!

Thus, operating system designers face a big challenge of engineering OS that work for more and more complex hardware as time goes on.

How Not to Do an OS?


Why not to use an operating system?

  • Simplicity
  • Performance
  • Reliability
  • Security(paranoia)

Suppose that you are hired to write a word count program by a paranoid English professor. He's writing a top-secret paper and he does not trust the Linux kernel or any of the operating systems out there.

Goal:

  • Write an application(not an OS): count of words in an ASCII text file (bytes '\011'-'\177')

Hardware Specification:

  • Intel core i3-4160 (3 MiB cache, 3.6 GHz)
  • 4 GiB dual channel DDR3
  • 1600 MHz SDRAM
  • 1TB hard drive, SATA, 7200 rpm
  • Intel HD integrated graphics

User Interface:

  • Turn on power switch
  • Word count shows up on the screen

Bootstrapping

We need to address the classic problem of bootstrapping first. When we power cycling a computer, we clear out CPU registers, cache and RAM. To execute our word count program, we need to load it into memory. But how do we load the program that loads our word count program in the first place?

The answer is, we get help from the hardware.

Physical Memory

  • The initial instruction pointer is 0xffff0 (2^20-16), which is built in the hardware.
  • ROM (Read Only Memory) region is hardwired by design.

So how to get from power switch through physical RAM to the program we want?

There are three ways:

  1. Tell the manufacturer that that we want the special function wc. So the code of wc (word count program) will be stored in the ROM region when the manufacturer builds the physical ROM.
    But this way costs lots of money because everytime we want to implement another program, we needs to buy a new physical RAM.

  2. Better approach: EEPROM (Electrically Erasable Programmable Read-Only Memory)
    • EEPROM is nonvolative memory and is programmalbe ROM. So we can put the wc code in EEPROM and changes EEPROM when we want to implement another program.
    • It always takes too long to change EEPROM because changing EEPROM is more like changing hardware.

  3. Put wc program on disk. Then in EEPROM, we have location of disk on wc, size of wc and the instruction to load the program. The location on disk of wc and the size of wc are actually R.O.(Read Only), and they are constants built in by manufacturers. This is usually the way we use.

Master Boot Record

  • By convention, the first sector of on disk is usually the Master Boot Record (MBR).
  • MBR records the location and size of the program you are going to run.
  • MBR has a total size of 512 bytes. In a classical generic MBR, 512 bytes consists of 446 bytes + 2 bytes + 64 bytes. The 64 bytes tells you information about the parition of disks.

Inside the 64-byte parition table, we store information such as disk count(4 bytes), partition type(1 bytes), flags, etc.

The normal masterboot record looks at the partition table and finds a bootable partition in the disk and then boot off the first record in that partition.

Chainloading:

firmware -> MBR(OS agnostic, i.e. don't care about which OS is running) -> VBR(OS specific) -> kernel(many sectors) -> load different programs

So when computer boots up, it will run BIOS. The BIOS will then

  1. Hardware sanity check
  2. Check for devices
  3. Obtain firs device that has an MBR (identified by the signature 0xAA555 (last 2 bytes))
  4. Copy MBR into RAM at the location 0x7c00

When loading program, just use 'jmp: 0x7c00'. As a result, we can do what we want to do by changing MBR.

A Key Subrouting to Read Data from Disk

with error check omitted, X86


void read_ide_sector(int s /* sector number(where you read), 4 bytes */
		     char* a /* memory address to read into, 4 btyes */)
{
	while((inb(0x1f7) & 0xc0) != 0x40) 
		continue;	/* go to the disk controller whose address is 0x1f7(bus address) and 
					retrieve the byte on the bus; First two bits indicate if disk 
					drive is ready(01). Note the order of evaluation. */
	outb(0x1f2, 1); // we just want to read 1 sector
	outb(0x1f3, s & 0xff); // take lower 8 bits of the sector number and pass to outb()
						   // or just outb(0x1f3, s) because of int-char convertion
	outb(0x1f4, s >> 8);
	outb(0x1f5, s >> 16);
	outb(0x1f6, s >> 24);
	outb(0x1f7, 0x20); // 0x20: read sector command
	while((inb(0x1f7) & 0xc0) != 0x40) // wait for ready
		continue;
	insl(0x1f0, a, 128); // insert long, a: buffer, 128: # of words to copy
}							
/* We can call inb(0x1f7), a single but slow machine instruction 
 to get the contents of a certain bus from disk controller into CPU. */

Uses of different registers.

# Name Uses
1 0x1f7 read status or write commands
2 0x1f0 & 0x1f1 read data
3 0x1f2 sector count
4 0x1f3 ~ 0x1f6 sector number to read from or write to

Firmware can have a copy @0xffff97, a copy In MBR @7c2 and a copy in word count program. This leads to a problem: we have 3 copies of the same code. We can autaully throw the last two copies away. The remaining copy at firmware is called BIOS. And BIOS may affect I/O perfermance and therefore used only in small machines.