CS 162, Spring 2007

Section notes for 20 February 2007

Sections 102/103

• Nachos 2
• Virtual Memory

• TONIGHT - Phase 1 code due
• 2/22 - Phase 1 final design doc & evals
• 3/3 - Phase 2 initial design doc
• 3/12 - Phase 2 code
  

Nachos Proj1
------------
• What did you like, dislike
    • How hard?
    • How's grouping?
    • How's subversion?
    • How's eclipse?
    • Due dates too early?
• Group evals


Nachos 2
========


• Syscalls

   - System call is invoked when MIPS simulator does 'syscall'
     instruction and traps to the OS
     - Causes instruction processing loop to throw 'MipsException'
     - When caught, calls MipsException.handle
       - handle() writes 'cause' into machine register
       - Causes 'Machine.processor().exceptionHandler' to be invoked
       - This is set by UserKernel constructor to be
     UserKernel.exceptionHandler
       - This gets current process (casts current KThread to UThread
         and extracts process field)
       - Calls process.handleException(cause)

   - Illegal operations do NOT include anything "illegal" done while
     calling a system call -> just return -1 from system call instead
   - write/read should return -1 if cannot read/write complete memory 
     buffer provided by user, but number of bytes transferred if memory
     is OK but filesystem is not

    • Should NEVER crash the operating system!! 
    • On error either (choice not arbitrary):
        • Return -1 from syscall
        • Crash the PROGRAM (not the OS)

   - Use Lib.random() to get an int for LotteryScheduler: Will be
     deterministic
   - Don't introduce overflow bugs in your code, but OK to assume that
     an 'int' is good enough to do the lottery with


• File tables
    • C example:
        in_fd = open("input.txt");
        if (in_fd == -1) { printf("oops"); exit(1); }
        out_fd = creat("output.txt");
        if (out_fd == -1) { printf("oops"); exit(1); }  
        char buf[100];
        read(in_fd, buf, 100);
        for (int j = 0; j<100; j++) { buf[j] ++; }
        write(out_fd, buf, 100);

    • Implementation:
        • YOU have to implement what file descriptor to return, and how to
          recognize it on read/write calls
        • Table of OpenFile objects

    • Never crash OS
    • Sometimes return -1 - error
    • Sometimes crash program (abnormal exit)

• Virtual memory
    • Recap of paging: virtual address of variable 'foo' is always 0x5123.
      How do you generalize so that it doesn't matter how many / which other
      programs are running and using how much memory?
    • Create a mapping
    • Do a table-lookup each time => page table
        • YOU implement page table creation & maintenance!
        • We will do more next project

• Processes
    • Exec: copy arguments
    • Join: wait for other user process to finish, and return arguments

    • C example:

    • shell.c:
        main() {
           pid = exec ("ls", "/");
           ret = join(pid);
           if (ret != 0) { printf("error\n"); }
        }

    • ls.c:
        main(int argc, char **argv) {
            // ...
            if (!file_exists(argv[1]))
                return 1;
        }

    • When can you remove child processes' state?
        • After join!



• Lottery scheduler
    • Why "max" when you can "+" ?
    • Probabilistic
    • Explain lotteries

    • Minimal changes to priority scheduler



• Lottery scheduler
    • Do "+" instead of "max"

    • In priority scheduling, always run process with highest effective
      priority

    • Now, do it probabilistically:

        • Rename effective priority => lottery tickets
     
        • Draw a pie chart with lottery tickets
        • Throw a dart randomly
     
        • Whichever section you hit is the process that runs for this time
          slice


   - LotteryScheduler should require minimal changes to existing code


Memory
------

• It's just a huge sequence of bits!

• How to organize?

• Protect operating system from user programs

• Protect user programs from each other

• Don't want to hard-code where in memory program goes

• Base & bounds:

    • Check bounds
    • Add to base

    • Can't access what you don't have a name for!

    • Registers

• Segmentation:
    • Many base & bounds segments
        • -> table

    • How addressing works

• Paging:
    • Shrink the offset-into-segment part of address and increase the
      number-of-segments => paging

• Internal vs external fragmentation