http://www.ien.com/uploadedImages/ien/IENblog/MooresLaw.png
Computer systems can be chaotic for multiple reasons:
Because it may be hard to understand or predict the workings of a computer system, or the effect a certain change may have on the rest of the system, computer systems can be considered chaotic.
Computer technology advances at a logarithmic rate because the faster computers become, the faster our tools for designing them become. A good example of this is the UNIVAC I, created in 1951. Since there were no existing computers to run calculations on or to calculate the reliability of the computer components, the design was done by hand and a profusion of error checking was implemented, both of which resulted in the UNIVAC I being very slow. However, when the UNIVAC 2 was created, the UNIVAC 1 was used for the design process, speeding up both the process and the final product, as well as allowing a reduced amount of error checking.
Moore's law states that the number of transistors on computer chips doubles every two years, as shown by the graph. This reaffirms the current logarithmic rate of technological advancement, but it cannot continue forever since the number will eventually get unimaginably large and surpass unbreakable boundaries such as the number of particles in the universe.
http://www.ien.com/uploadedImages/ien/IENblog/MooresLaw.png
Similar to Moore's law, Kryder's law describes the rate of increase of magnetic storage capacity, which is even faster than the doubling of transistors occuring in accordance with Moore's law. This rate of increase can be seen in the graph below.
http://upload.wikimedia.org/wikipedia/commons/a/a1/Hard_drive_capacity_over_time.png
A professor needs to check the word count of his academic proposal, but he's extremely paranoid that other professors may have compromised all existing operating systems in order to steal his proposal or may have sabotaged its word-counting ability. We want to create a program he can use that satisfies the following four requirements:
Below is a diagram of the interconnnections of the hard drive with the RAM and CPU.
___
/ \
| HDD |
\___/
|
------------
| Disk | -------
|Controller| | RAM |
------------ -------
| |
================================= BUS
|
-------
| CPU |
-------
Because we need to access a file on the disk for our word count program (WC), and we don't have an OS to make system calls to, we need to know how to tell the disk controller a command:
1. Wait for it to become ready. This status is stored in the disk controller's register 0x1F7.
2. Store the number of sectors we want to read into the register 0x1F2.
3. Store which sector you want to read (a 4-byte number) into the registers 0x1F3 through 0x1F6. These are addressed in little endian.
4. Store a READ command into 0x1F7. Checking this register will now tell the CPU the disk is busy until the READ is completed.
5. Wait for it to become ready (signifying the READ is done).
6. Slurp the read data from the disk controller cache through the CPU into RAM (Note, if we want to speed things up a little, we can perform a direct memory access [DMA] which allows the data from the cache to bypass the CPU and go straight to RAM.
Bootstrapping (or booting) refers to the loading of basic software into the computer's memory, usually setting in motion a sequence in which the operating system is loaded. In the early days of computing, this was accomplished by a front panel on the computer, on which various switches were flipped in order to input the initial boot program.
This has been replaced by a BIOS (Basic Input/Output System) with the advent of read-only memory, or ROM. ROM is useful because data stored on it survives a power outage, but the trade-off is that it's hard to modify. The BIOS is started during the boot process and is stored in ROM, PROM, EEPROM, or another variant of read-only memory.
Standard BIOS Steps:
1. Run self-tests (longer for servers, shorter for consumer computers)
2. Look for devices (sends requests to each channel on the bus to see what devices respond)
3. Look for a special pattern in each device to see if it's bootable
4. Copy boot program into RAM and switch control to it
The very first 512-byte sector on a bootable disk stores the Master Boot Record, or MBR.
In these 512 bytes are stored the boot program, partition table, and signature, as shown in the figure:
------------------------------------------------------------------------------ | Boot program (446 bytes) | Partition table (64 bytes) | Signature (2 bytes)| ------------------------------------------------------------------------------
The boot program usually loads the volume boot record, or VBR, from the partition table, which then loads the OS, but in our case it will just load the actual WC program and run it since we don't have an OS. The MBR is OS agnostic, but the VBR can be OS specific.
The partition table consists of four 16-byte partition descriptors, which include the status (e.g. bootable or not), the start sector (4 bytes), the size in sectors (4 bytes), and the type (e.g. DOS or Linux). Because there are only four partition descriptors, there can only be a maximum of four partitions, but this is circumvented on modern computers by the OS simply pretending that more partitions exist while still storing the data on the fourth partition.
The signature consists of two bytes. The BIOS can tell that the device is bootable if the bytes are 0x55 and 0xAA, which appear as 0xAA55 since the memory is little endian.
We will write our word count program in C. Because the program will be too large to fit in the MBR, instead we will store it on the disk, and use a boot loader program to load it into memory. The code for this will be named mbr.c (stored at memory address 0x8000), since the MBR will exist solely to run our program, not load an operating system. The complilation process is shown below. The end of file character is set to a null byte in the linker.
mbr.c -> cc -> mbr.o -> ld (EOF ='\0') -> 512-byte mbr executable
The code is as follows:
int main(void){
for(int i = 0; i < 20; i++)
read_sector(1+i, 0x10000 + i * 512);
goto *0x10000;
}This code reads sectors 1-20 (which is where the word count program will be) sequentially into memory with the first sector placed at 0x10000. It then jumps to the beginning of the program to run it. However, we still need to implement read_sector.
read_sector reads each sector into memory using programmed I/O, which uses outb(), a function that copies 1 byte to a controller register:
void read_sector(int s, char* a, int ns){
//s: sector number, a: memory address, ns: number of sectors (max 255)
wait_for_ready(); //wait for the disk controller to be ready
outb(0x1f2, ns); //store the number of sectors into the sector count register (0x1f2)
for (int i = 0x1f6; i >= 0x1f3; i--){
outb(i, s);
s >>= 8;
}
outb(0x1f7, 0x20); //store the read command (0x20) into the status register (0x1f7)
wait_for_ready(); //wait for the storage of the sector(s) into the disk controller cache to complete
insl(0x1f0, (int*)a, 128); //read 128 4-byte words from the disk controller's cache (0x1f0), and write them to the memory address a
}
wait_for_ready waits for the disk controller to be ready by using inb() to check its status register.
void wait_for_ready(void){
while((inb(0x1f7) & 0xc0) != 0x40)
continue;
}
Now that we've created the infrastructure for a standalone program, we can write the program's code, which will run assuming it has already been read into 0x10000:
void main(void){
unsigned long nw = 0; //set number of words to 0
int s = 21;
bool inw = false; //true if in the middle of a word;
for(;;){
char buf[512];
read_sector(s, buf, 1); //read the current sector (starting at 21, right after our WC program) into buffer
for(int i = 0; i < 512; i++){
if(buf[i] == '\0'){ //if the EOF is reached
finish(nw); //call finish() with the number of words
for (;;); //go into infinite loop
}
bool mw1 = (buf[i] | 'a' - 'A') - 'a' < 26u; //lowercases all words then returns true if the current character is a valid letter;
nw += mw1 & inw; //if the current character is a valid letter, and isn't in the middle of a word, increment word count;
inw = mw1; //set inw to true if the current character is a letter;
}
}
}Now we implement the finish function to output the number of words:
void finish(int n){
short p = (short*)0xb804; //address of the computer display
do{
*p-- = '0' + n%10; //print digits from right to left
n /= 10;
}while(n);
}
Now, by plugging in the computer, the paranoid professor is able to count the number of words in his proposal without having to fear that someone might steal it. However, because the code was written as a standalone program, it's incredibly hard to change. We also didn't even take into account how the professor will actually write the proposal and get it onto the disk.
These limitations show us why operating systems are so useful.
Credit for the basic HTML structure of these notes goes to Karen Truong and Gary Ren http://cs.ucla.edu/classes/fall13/cs111/scribe/2c/index.html