Lecture #2: How Not to Write an Operating System!

• We will violate modularity (i.e. assume that it is not important).
• Scenario: A paranoid user who doesn't trust any operating system wants a simple application that counts the number of words in an ASCII text file (with a NULL byte at the end).

Q & A (Requirement Illicitation)

• Q: What kind of hardware is available?
• A: A x86 computer with 1 GiB RAM (bare computer) and 1 SATA disk drive (500GB) is present.
• Q: What's a word?
• A: Anything that satisfies the regex [A-Za-z]+ (any number of letters A through Z and a through z).
• Q: What is the output format?
• A:
• Q: What is the input source?
• A: A text file on disk (we pick start location).
• Q: What is the deadline?
• A: In 2 hours (end of class :D ).
• Q: How do you start the program?
• A: When you turn on the power.
• Q: Will the program modify disk?
• A. No. Disk may be set as read-only at the hardware level.
• Q: How might things change?
• A: Some examples are a new disk drive, other programs, or a spell checker that might be added.

Issues

1. bootstrapping
2. disk input
3. screen output

Bootstrapping

1. It tests the system (e.g. tests the RAM and hardware).
2. It looks for devices
3. It looks for a readable device containing a Master Boot Record (MBR):
   
   
   
   The MBR standard form. It contains 3 sections, a machine instruction section, a partition table, and a signature. The machine instruction for x86 is 446 bytes long. The partition table is 64 bytes long and has 4 entries. Each entry has 16 bytes. A partition table can partition the MBR for linux, windows, apache. Each entry contains the status and type of the partion. (am I bootable? what type?). Also has the start of where on disk the partition starts and the size of the information. The MBR has a signature, 0x55 0xAA, at the end to denote that it is a MBR.
4. It reads MBR into disk RAM and jumps to it. (An interesting note: if the beginning of the machine instruction is the x86 HALT instruction, the computer will never do anything. Try it on your friends today!)

Disk Properties

• The most common disk rotation speed is 7200 RPM.
• The average seek time is 8 ms.
• The transfer rate of the data going through the head is about 500Mb/s.
• The cost per gigabyte is about $.20/GB compared to RAM's costs per gigabyte is about $30/GB).
• It is a nonvolatile storage medium.
• A sector is a subdivision of a disk.
  

1. Wait for the disk to be ready (CPU reads location 0x1F7).
2. Store # of sectors you want to read into location 0x1F2.
3. Store sector offset into locations 0x1F3 - 0x1F6. The sector offset is disk location, given by a 32-bit quantity. This allows for referencing up to 2^32 * 2^9 = 2^41 bytes.
5. Store READ command into location 0x1F7.
6. Wait for disk to be ready.
7. Get results as a sector into CPU.
8. Store results into RAM.

Our MBR Program

int main(void){
	for (int i = 0; i < 20; i++){
		read_ide_sector(20000 + i, 0x100000 + i * 512);
		goto 0x10000;	// NOTE: Not proper C language!
	}
}

void read_ide_sector(int s, int a){
	while((inb(0x1F7) & 0xc0) != 0x40) // inb = inbyte
		continue;

	outb(0x1F2,1); // Outbyte # of sectors
	outb(0x1F3, s & 0xff);
	outb(0x1F4, (s >> 8) & 0xff);
	outb(0x1F5, (s >> 16) & 0xff);
	outb(0x1F6, (s >> 24) & 0xff);
	outb(0x1F7, 0x20); // Read sector

	while((inb(0x1F7) & 0xc0) != 0x40)
		continue;

	insl(0x1F0,a,128); // Where, data, copy # of 4-bytes units
}

int main(void){
	char buffer[512];
	int nwords = 0;
	bool in_word = false;

	for (int s = 500000;; s++){
		read_ide_sector(s, (int)buf); // Typecasting buf

		for (int j=0; j < 512; j++){
			if(!buf[j]){
				write_out[nwords];
				return;
			}

		bool this_alpha = isalpha((unsigned char) buf[j]) != 0;
		nwords += this_alpha & ~in_word; // ~ means invert bits; has the same effect as !, but is generally faster, increment word count
		in_word = this_alpha; // Now in a word
		}
	}
}

Screen Output

write_out(int nwords){
	unsigned char *screen = 0xB8000 + 20; // 10 chars into screen
	do{
		screen[0] = (nwords%10)+'0';
		screen[1] = 7; // Gray on black
		screen -=2;
		nwords /= 10;
	}while(nwords);
}

Performance Improvements