CS 111 Lecture 3 Scribe Note

Prof. Paul Eggert, April 11th 2012

Harvey Abaya, Tai Pham, Varun Kumaraswamy, and Daifu Ye

READING DATA FROM SECTOR:

data-sector 
// typical low level code for reading sector
void main(void){
  long long words = 0; // initialize number of words to 0
  bool in_word = false;
  size_t sizeOfBuff;
  char * buf[sizeOfBuff];
  int s = 100000; // location of sector
  for(;;s++){
    read_ide_sector(s, buf);
    for(int j = 0; j < sizeOfBuff; j++)
      if(!buf[j]){
      write_out(words);
      }
    bool this_alpha = isAlpha(buf[j]); // check to see if the character is alpha
    words+=this_alpha&(~in_word); // add 1 to words if this_alpha=TRUE and 
              // in_word = FALSE
    in_word = is_alpha;
  }

DISPLAYING TO THE SCREEN

display-to-screen
display-to-screen-2 
void write_out (long long n){
  char *p = (char *) (0x6800 + 80*25*2/2 - 20); // assume 80 by 25 screen with 2 bites
            // 20 is a value we felt is close to the center
  do{
    int lsd = n%10; // get the least significant digit of N
    *--p =7; //this adds color 7 which is setting by first byte since a pixel is2bytes
    *--p = lsd + ‘0’; // this will get the ascii value of the lsd by adding it to char ‘0’
    n/= 10;
    }while(n);
}

IMPROVING PERFORMANCE:

how do we improve performance when we boot fast but I/O or CPU is idle:

typical scenario:

io-idle
  1. We can read more sectors at a time because time of grabbing sectors and computation on a single sector constitutes majority of time improvement:
    sector-improvment
  2. Pipelining- we can overlap IO and computation but we have to hold two buffers. improvement:
    io-computation-buffer
  3. DMA (Direct Memory Access)
    instead of CPU being in between disk controller and RAM we can have DMA to lessen the time of passing through CPU
  4. MULTICORE:
    we can have multi processors to handle reading sectors in parallel.

Advantages of standalone programs:

  • Good for paranoid people

Disadvantages of standalone programs:

  • Certain simple changes may cause you to change code throughout your application. Can become very tedious in large programs when thousands of lines are involved
  • Code is often application specific and can’t be reused in other applications
  • Two programs can’t be run simultaneously
  • If a program fails, we can’t recover from them

Approach to Improve Standalone Program

Now if we want to move away from standalone programs to enable multiple programs to be able to use read_ide_sector() function, we need to change a couple things. One way to allow other programs the ability to use the function is to put the function in the PROM(Programmable Read Only Memory) part of RAM. Although this works, there are some drawbacks.

Drawbacks of this approach:

  • If we need to modify our read_ide_sector() function, we have no way to upgrade other than to flash the BIOS
  • Too inflexible

To improve on this, we need:

  1. Modularity
    • Separate the computation and the I/O parts of our word count program so that we can modify either one of them when needed without affecting the operation of the other.
    • If we need to change the read_ide_sector function, we can modify the I/O portion of the program without affecting the computation part.
  2. Abstraction
    • Modularity that is simplied. Allows the computation and I/O parts to only have a small window to see each other.

To generalize the read_ide_sector function:

// 's' is the sector number we want to read, 'p' is where we read to
void read_ide_sector (int s, char* p); 
          ↓
// modified to void* p so that we can read any type of data
void read_ide_sector (int s, void* p);
          ↓
// there is a limit to the largest number we can represent as an integer, so
// we define a new type 'off_t' which allow us to access larger number of sectors
void read_ide_sector (off_t s, void* p);
          ↓
// we add a new parameter ‘buffSize’ to our function which will be the block
// size. This allows us flexibility to use our code on different systems even if
// their block sizes are different. We use the ssize_t return type to add room for
// knowing about errors when reading the sector. It will be negative if we get an
// error.
ssize_t read_ide_sector (off_t s, void* p, size_t buffSize);

We have modified our read_ide_sector() to look very similar to the pread() Linux command. The ‘pread’ command looks like:


// 'int fd' is a file descriptor and 'off_t s' is a byte location. All other
// parameters are the same as we have already discussed.
ssize_t pread (int fd, off_t s, void* p, size_t buffSize);

The ‘pread’ command was further modified to the ‘read’ command as follows:


// we don’t keep track of how much we have read in the file. The OS helps keep
// track of that for us.
ssize_t read (int fd, void* p, size_t buffSize);

We also have the ‘lseek’ command which returns the location a new location of the read pointer to a file. The command looks like:

// We can move the file pointer from either the beginning of the file, the end
// of the file or the current position any way we want by providing the ‘flag’ and
// 's' parameters. The ‘s’ parameter signifies how much we move the read pointer.
off_t lseek (int fd, off_t s, int flag);

The flag parameter takes the following values:

  • SEEK_START 0 - move relative to the start of the file.
  • SEEK_CUR 1 - move relative to where the read pointer is currently
  • SEEK_END 2 - move relative to EOF

Modularity

  • Where to draw the line between applications and operating system
  • How to draw the line between applications and operating system

When a function is called, we need to store its local variable, return address, etc... We do it by using a stack. A stack grows from bottom to top. An example of the stack of a nested function calls is below:

stack

Recursive factorial example:

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

Assembly code (unoptimized version, note that the number at the end is not part of the code):

 fact:
	pushl	%ebp            (1)
	movl	$1, %eax        (2)
	movl	%esp, %ebp      (3)
	subl	$8, %esp        (4)
	movl	%ebx, -4(&ebp)  (5)
	movl	8(%ebp), %ebx   (6)
	testl	%ebx, %ebx      (7)
	jne	.L5             (8)

The stack after each step is described below (%ebx contains n):

explain1 explain2

(7): Test if value %ebx = 0

(8): If the above condition is wrong (jne = jump not equal), then jump to L5 (recursive case)

.L5:
  leal	-1(%ebx), %eax(compute effective address, just means eax = eax -1)
  movl	%eax, (%esp)
  call	fact
  imull	%ebx, %eax
  jmp	.L1

L1 is call if n = 0 (base case):

.L1:
  movl	-4(%ebp), %ebx  (restore ebx)
  movl	(%ebp), %esb    (restore stack pointer)
  popl	%ebp
  ret

Refer to lecture27 for few more examples about C and assembly code

Things that can go wrong with the recursive approach for factorial:

  1. Exhaust the stack. How to fix ? Don’t use recursion !!
  2. Unreliable caller → system crash
    For example:
    push $5
    jump fact
    → Return to undefined address $5
  3. Unreliable callee → system crash
    Ex: .L6 jmp .L6 → caller never gains control again → system hung

This is an example of soft modularity (each module stays on their side, relies on communication for correct action)

We want hard modularity (which works even with unreliable caller /callee)