CS 111: Lecture 3

10/7/13

By Rebecca Pan and Mimi Chiang

Remember from the previous lecture how our stand alone word counter program works: Our word reader takes in a sector of words and counts the words and partial words in the sector.

Ways to Improve our Program Performance

1.       Increase block size: By increasing block size the processing overhead lessens. However, the block size cannot increase so much that the program runs out of memory.  In addition, if the file is tiny, trying to read a larger block size results in a lot of unnecessary extra work.

2.       Double Buffering : Double buffering fetches  the next  block while processing the current block. This overlap of I/O and computation improves speeds by 2x. However, double buffering requires 2x more memory consumption. Adding even more buffers would not help as the disk controller can only read in one sector at a time. 

3.       Change Input Method: Our program uses the insl instruction. The insl instruction is a programmed input/output (PIO) mode and is not efficient. The data is transferred from the controller to the CPU then to RAM. Therefore, the I/O bus is used twice. By using direct memory access (DMA), the controller transfers the data to the RAM directly, thus the I/O bus is used only once.

4.       Change Hardware:  A solid state drive is faster that a hard disk drive.

Real Problems with our Program

·         Too much of a pain to change to incorporate performance improvement ideas

·         Too much of a pain to change lots of programs systematically

·         Too much of a pain to run several programs simultaneously

·         Too much of a pain to recover from faults

OS PROVIDES A TECHINQUE TO FIX THESE PROBLEMS

Goal: Make useful improvements a module at a time

Aside: Modularity decreases the cost of fixing bugs. For example, a typical program has 1 bug/100 lines. Let’s assume a program had B bugs and L lines, and M modules if it has so. The cost to fix the bugs in a normal program is B*L. This takes N^2 time. A program with modularity costs (L/M)*B, which is N^2/k time. Therefore, it takes less time to fix bugs in a program with modularity as the cost of fixing each bug is divided between all the modules. However, there is a limit to how many modules that can be added to increase debuggability.

Metrics for quality modularization

·         Independence/Neutrality/Lack of Assumption/Flexibility: Easy to edit

·         Determinism/Predictability/Debuggability: Easy to fix

·         Simplicity: Easy to learn and use

·         Cohesiveness:  All the parts go well together

·         Performance: Modularity usually hurts performance a  little bit

·         Robustness: Tolerates harsh conditions

Function Call (Soft Modularity)

Library Functions in BIOS

Example: Non-optimized recursive factorial to observe the resulting functions calls. Typically a compiler would realize that a loop would be better for calculating factorial, however optimization has been turned off to observe the function calls.

C Code:

int fact(int n){

                if(n ==0)

                                return 1;

                return n*fact(n-1);

}

Assembly code:

Fact:           pushl         %ebp                            

                    movl          $1, %eax                       %caller beware, callee can modify %eax

                    movl          %esp, %ebp                %base pointer to stack pointer to store

                    subl            $8, %esp

                    movl          %ebx, -4(%ebp)        %saves %ebx

                    movl          8(%ebp), %ebx          %stores int n into %ebx

                    tstl              %ebx, %ebx

                    jne                                  .L5               % if not, recurse

.L1

                    movl          -4(%ebp), %ebx        %return value to %ebx

                    movl          %ebp, %esp               

                    popl           %ebp

                    ret                                                      

.L5              

                    leal             -1(%ebx), %eax         %answer in %eax

                    movl          %eax, (%esp)

                    call              fact

                    imull           %ebx, %eax                %n*fact(n-1)

                    jmp                                 .L1

What can go wrong with function call modularity?

1.       Hard to change conventions

2.       Callee can stomp on caller storage or caller’ caller and so on.

3.       Caller isn’t insulated from callee disasters

4.       Caller can mess up callee

5.       Callee can loop forever

Hard Modularity

We want hard modularity because it still words with buggy modules.

1. Client-server or peer to peer: This consists of two machines that communicate with SEND and RECEIVE. Thus the client and server cannot stomp on each other. It is slow though.

2. Virtualization: The caller runs the code on an emulator. Thus the code can only stomp on itself. The emulator provides trusted, c boundaries. It is slow.

Protected transfer of control

Protected transfer of control is a way to gain performance at the cost of modularity. The callee (OS) is protected from caller (untrusted app). It is however not as fast as function call

App code

CPU