CS 111 Spring 2010: Lecture 3 Scribe Notes

The read_sector() function has multiple copies: in the MBR, VBR, application, and BIOS. In order to avoid multiple copies of read_sector(), we keep only one in the BIOS and publish it so it is available in the other areas. In fact, BIOS stands for Basic Input Output System. One advantage to doing it this way is that it needs only one person to maintain it. Another advantage is that it is standardized. It also has disadvantages, two examples being that it is neither flexible nor portable.
+ 1 copy/maintainer, standardized
- very inflexible
Performance is an issue. By using DMA (Direct Memory Access), we can make I/O faster. The old method: The bus is used twice. Once for data to move from the disk controller to the CPU, and once for it to move between the CPU and the RAM.

We have: We want Direct Memory Access:

DMA: The controller talks to the RAM directly to send data, and notifies the CPU when it is done. This means that our previously defined read_sector() function has to be redefined to accomodate these operations.
Double Buffering (Overlapping reading and counting) Instead of the traditional method of running operations one at a time, we can run two operations concurrently in parallel, by the use of an extra buffer. The following picture may illustrate this better.

read    ---- ---- ---- ---- ----
count       --    --    --    --    --

        A    B    A    B    A             Need 2 buffers
read    ---------------------------       Read into a new buffer
             A    B    A    B    A        Count first buffer
count       -- -- -- -- --

Double buffering can thus speed up the performance of our O/S. The biggest performance increase is if counting and reading take the same amount of time, We can consider the use of triple buffering to run 3 different processes at one time to solve overhead problems, but there may be the problem of the HDD being able to read only one sector at a time. Again, to do this many of our previously defined functions have to be rewritten.
The application is too much of a pain to maintain. Difficulty to make changes to the application or reuse pieces of the application's code may be due to a large number of components or a large number of interconnections between components, or may be due to irregularity in the code or the code may be lacking a methodical description. These problems are symptoms of complexity.

To cope with complexity in our application, we can use common techniques like modularity and abstraction. The modularity of the application describes the extent to which the application is composed from separate parts, called modules. A module interacts with other modules through its interface. We want to reduce the number of interactions so that modules can be easily replaced or changed with little consequence to the rest of the application. In other words, we want "nice" boundaries between modules. To see what impact it can have, consider debugging the application. Let us assume that the cost of fixing a bug is proportional to module size, and examine the effect on findings bugs given an arbitrary system.

Modularity's effect on finding bugs:

N lines of code, M modules
Bugs = N, time to find/fix bug = N
Debug time (M = 0) = N^2
Debug time (M = M) = (N/M * N/M) * M = N^2/M
(this assumes bug is isolatable and easily found in which module)

As a general rule, the more modules we have, the less debug time is required. We can thus use this model as a good estimate of the required debug time for bugs that reside in only one module, as most bugs occur in single modules. However, we do take into account that some bugs can span across multiple modules, and more time will be needed to examine all the different modules relating to the bug, in turn increasing debug time.
Modularity can be bad or good (assess by metrics)
1. Performance - modularization usually costs performance
2. Robustness - tolerance of faults/failures - well designed modules should work well in harsh environments
3. Simplicity - easy to learn/use, small manual
4. Portability, neutrality, flexibility, lack of assumptions
  - let components be used in many ways
  - let "file" be anything - bytes on disk, packets in network

-> Because the ability to read a sector has been taken away, and all that remains to seek to a spot is the offset, there is also a function lseek to move the pointer to the desired spot

off_t lseek (int fd, off_t b, int flag)

Alternate variant of read
- read_eggert(int fd, off_t b, char* a, size_t nbytes)
  -> if you read sequential bytes, no lseek needed
Read has two properties
1. virtualization - there is a virtual machine which read controls
2. abstraction - simpler than underlying machine
How to enforce modularity (and virtualization):
- can either do nothing (trust) or function calls and C calls

In c format:

	1 int fact (int n) {
	2 	if (n == 0) 
	3 		return 1;
	4 	return n*fact(n-1);
	5 }

In x86 format:

	fact:
		pushl %ebp		//save fp
		movl $1, %eax		//ax=1
		movl %esp, %ebp		//fp=sp
		subl $8, %esp		//sp-=8
		movl %ebx, -4(%ebp)	//save bx
		movl 8(%ebp), %ebx	//bx=n
		testl %ebx, %ebx	//is n==0?
		jne .L5			//if nonzero go to L5
  	.L1	movl -4(%ebp), %ebx	//restore bx
		movl %ebp, %esp		//restore sp
		popl %ebp		//restore fp
		ret			//pop stack, go there
  	.L5	leal -1(%ebx), %eax	//ax=bx-1
		movl %eax, (%esp)	//*sp=ax
		call fact		//pushes return address on stack/jumps to fact
		imull %ebx, %eax	//result*=n
		jmp .L1

stack

Lecture Topic: Modularity and virtualization