CS111 Scribe Notes for April 9, 2013

By Matthew Lung

How to cope with complexity in OS

A. Modularity: Breaking things into pieces

Without Modularity:

assume that the number of bugs is proportional to the program size s
assume that the cost to fix a bug is proportional to the programs size s
the cost to fix all the bugs is then s^2

With Modularity:

assume modules are each of size S/M where S is program size and M is number of Modules
assume that the number of bugs per module is proportional to S/M
the cost to fix a bug is then proportional to S/M
the cost to fix all bugs in any module is proportional to S^2/M^2
the cost to fix all bugs is proportional to S^2/M^2

B. Abstraction: Break program into nice pieces

Looking at the word count program from Lecture 2 there is a problem:

There are two copies of the read sector function.
- a copy in the bootloader in MBR
- a copy in word count itself

To fix this, we can do one of three things:

Put read sector in BIOS (will make read sector BIOS specific, slow, and generic)
Put read sector into MBR (limited to only 512 bytes)
Create a library with read sector in RAM

___________________________________________________________

Crypto Analysis-uses a lot of CPU

I/O (0)___(1)___(2)___(3)___

CPU __(0)___(1)___(2)___(3)

time------------------------>

After I/O is done with (0) CPU can have (0)...This is inefficient, because I/O and CPU must wait for each other.

Double Buffer-almost twice as fast

I/O (0)(1)(2)(3)(4)

CPU __(0)(1)(2)(3)

time------------------------>

After finishing with (0) the I/O buffers (1), while the CPU is running (0). This is ~twice as fast as not buffering.
Note: triple buffering, quadra buffering,...etc will not further performance increase)

There are trade-offs for this performance, in this case complexity is traded for performance increases. Internally the system buffers or reads ahead.
___________________________________________________________

Direct Memory Access (DMA)

In regular memory accessing, the CPU tells the disk controller what it wants to be done, the disk controller then gets the necessary information and sends it back to the CPU. The CPU then moves that information to the RAM. This method is not very optimal, because the bus can obly be used for one thing at a time. Knowing this, the CPU uses the bus to request from the disk controller, the disk controller must return over the bus, and then the bus must be used to transfer the data to the RAM. Rather operating in this manner Direct Memory Access reduces the redundancy.

In DMA the CPU sends commands to the disk controller, but these commands will direct the disk controller to send the data directly to the RAM. This process is shown in red and blue in the figure above.

Brief Summary of Simple OS Modularity Problems

It is too much of a pain to reuse the code used in modularity
It is difficult and tedious to change things
It is too hard to run multiple programs, especially simultaneously
It is difficult to recover from faults
In the case of read_sector, it is too low level; it only works with disk or disk-like devices. It assumes that sectors are 512 bytes
Not very portable

Looking at the read_sector function

void read_sector(int S, int ptr_t a) can be changed to void read_sector(int S, int ptr_t a, int SectorSize)

and

int read(int S, int ptr_t buf, int bufsize) to size_t read(off_t offset, void* buf, size_t bufsize)

Or More Generally:
ssize_t read(void* buf, size_t bufsize) + off_t seek(off_t offset)

But this is still assuming that there is only one file and only one device.

How to tell whether modularity is good or bad.

Look for:

Simplicity: it is easy to learn and use
Lack of Assumptions: being flexible, portable, neutral, and easy to substitute
Robustness: tolerate harsh conditions
Performance: modularity usually hurts performance a bit. But not too much!

Common Policy on Modularity:
When there is no modularity there are many global variables and many functions used to fulfill small roles in operating the program. The plus side to this is that it runs fast the negative side is that it is often hard to understand and debug.
___________________________________________________________

Library Functions (What are their addresses?) in BIOS or in the Library Area Library Visually

Caller Code + Callee Code

(lazy version): one function that calls itself

int fact(int n) {
         if(n)
             return n*fact(n-1);
         else
             return 1;
}

Example: Non-optimized Factorial

	pushl	%ebp
	movl	$1, %eax			<--Caller Beware! Callee can modify %eax
	movl	%esp, %ebp			<--We will preserve %ebp
	subl	$8, %esp
	movl	%ebx, -4(%ebp)
	movl	8(%ebp), %ebx
	tstl	%ebx, %ebx
	jne		.L5
	
.L1
	movl	-4(%ebp), %ebx
	movl	%ebp, %esp
	popl	%ebp
	ret							<--The answer will be in %eax

.L5
	leal 	-1(%ebx), %eax
	movl 	%eax, (%esp)
	call	fact
	imull	%ebx, %eax
	jmp		.L1

___________________________________________________________

What can go wrong with function call modularity:

Caller could mess up; it could forget to push n
Callee can mess up; it could set registers that it is not suppose to
Callee can return registers wherever it wants to
Callee can loop infinitely

Function calls give soft modularity, but we want hard modularity which works even with buggy modules. To do this there are two common ways:

1. Client-Server: client code cannot step on the server memory and vice-versa. This works, but is very expensive.

2. Virtualization: the code run in virtualization can only stomp on itself; the OS insulates itself from the application.