Class 7: Double Faults

Posted: Thu 06 February 2014

Problem Set 2 is due Sunday, 9 February. You should sign-up for a team demo using this form.

Remember to check the course calendar for office hours updates. Several additional times have been scheduled to provide help on PS2 including 2-3pm and 7-8:30pm Thursday; 10-11am, 1:30-2:30pm, and 5-6:30pm Friday; and 4-5pm and 6-7pm Sunday. (Check the calendar for the locations and any changes.)

Recommended Reading

Chapters 12 through 23 of the OSTEP book provide a lot more information on virtual memory. You are not expected to know details covered there that we didn't also cover in class, but should find these chapters interesting and useful to read.

Slides

Page Fault Challenge

Michael Recachinas solved the Page Fault Challenge!

His code and results are here: https://github.com/mrecachinas/Page-Faults.

Page Tables

How well does the 386 architecture work for larger memories?

Why not just make the page size bigger to support more memory?

What are the advantages of flexible page sizes over fixed page sizes?

ARMv8 White Paper ARMv8 Architecture

Qualcomm and Samsung Pass AMD in MPU Ranking, IC Insights, 20 May 2013.

Faults

What is the difference between a segmentation fault and page fault?

What does it mean if a C++ program execution generates a segmentation fault?

What does it mean if a Rust program execution generates a segmentation fault?

How often should page faults happen in a Rust program?

What does this program do? [Code]

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  char *s = (char *) malloc (1);
  int i = 0;
  while (1) {
    printf("%d: %lx / %d\n", i, s + i, i[s]);
    i += 1;
  }
}

Processes, Threads, and Tasks

What is difference between a process and thread?

Is a Rust task more like a process or a thread?

How can Rust tasks provide process-like memory isolation but without the expense of a traditional process?

Spawning Tasks

The spawn function takes in an owned function (which cannot capture any mutable, shared objects) and runs that function in a new thread:

    fn spawn(f: proc())

Channels provide a way for spawned tasked to communicate back to their parent:

   let (port, chan) : (Port<int>, Chan<int>) = Chan::new();
   let val = node.head;
   do spawn {
      chan.send(f(val));
   }
   let newval = port.recv();

The port.recv() call with block until a sent value (from chan.send(f.val)) arrives.

Faster Collatz Steps

Here's the code for my klunky multi-tasking Collatz program: [Code] (I believe, but not with a lot of confidence, that it is correct, but it sometimes leads Rust to segv)

fn collatz_steps(n: int) -> int {
    if n == 1 {
        0
    } else {
        1 + collatz_steps(if n % 2 == 0 { n / 2 } else { 3*n + 1 })
    }
}

fn find_collatz(k: int) -> int {
    // Returns the minimum value, n, with Collatz stopping time >= k.
    let mut n = 1;
    let max_tasks = 7; // keep all my cores busy

    let mut found_result = false;
    let mut result = -1; // need to initialize

    while !found_result {
        let mut ports = ~[];

        for i in range(0, max_tasks) {
            let val = n + i;
            let (port, chan) : (Port<int>, Chan<int>) = Chan::new();
            ports.push(port);

            spawn(proc() { 
               let steps = collatz_steps(val);
               println!("Result for {}: {}", val, steps);
               chan.send(steps);
        });
        }

        for i in range(0, max_tasks) {
            let port = ports.pop();
            let steps = port.recv();
            if steps > k {
                found_result = true;
                result = n + i;
            }
        }
        n += max_tasks;
    }

    assert!(result != -1);
    result
}

fn main() {
    println!("Result: {}", find_collatz(500));
}

Challenge: Write a substantially better find_collatz program that makes good use of all available cores, and always produces the correct result. (In class, I said it had to run 6 times faster than the single-threaded version on an 8-core machine, but if it is close to getting a good speedup and using an effective strategy to keep all the cores busy doing useful work nearly all the time that is good enough.)

comments powered by Disqus


Class 6: Making a Process (Virtualizing Memory)

Posted: Tue 04 February 2014

Problem Set 2 is due Sunday, 9 February. You should sign-up for a team demo using this form.

Slides


Videos

Gnashing about Gash

Weilin's most evil test:

   curl "http://rust-class.org/pages/ps2.html" | sed "s/[^a-zA-Z ]/ /g" | tr "A-Z " "a-z\n"| grep "[a-z]" | sort -u

What is the difference between a background process and foreground process?

What happens when the user types Ctrl-C?

Memory Isolation

How can a program be isolated in memory without hardware support?

Native Client - Native Client: A Sandbox for Portable, Untrusted x86 Native Code, IEEE Security and Privacy ("Oakland") 2009.

What are the advantages/disadvantages of hardware-based memory isolation over software-based memory isolation?

Implementing Virtual Memory

Robert C. Daley and Jack B. Dennis, Virtual Memory, Processes, and Sharing in MULTICS - Symposium on Operating System Principles (SOSP), 1967.

What must be done to switch processes on MULTICS?

Virtual Memory on the x86

Intel x86 Software Develop Manuals - Most of what I covered today is in Volume I, Chapter 3 (Basic Execution Environment) with Section 3.3 on Memory Organization. Chapter 5 is all about Protection.

Why is it useful to convert a logical address into a linear address, as is done by the segmentation unit?

Where is the Global Descriptor Table stored?

Why is a memory page in the 80386 (32-bit) processor 4K bytes?

What will this program do and why?

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  char *s = (char *) malloc (1);
  int i = 0;
  while (1) {
    printf("%d: %x\n", i, s[i]);
    i += 4;
  }
}

Challenge: Write a program that takes N as an input and produces (nearly) exactly N page faults. A good solution is worth a USS Hopper patch (even cooler than a Rust sticker!) or an exemption from Exam 1 or Exam 2.

If you were designing a modern processor today, and not limited by the need to run legacy operating systems and programs, how would your memory isolation design be different from x86's virtual memory?

Growing a Language

Guy L. Steele's Growing a Language [Transcript]:

How well does the design of Rust espouse the philosophy of growing a language by Guy Steele in the talk?

comments powered by Disqus


Class 3: Zero to a Billion in 4.86 Years (Thu 23 January 2014)


Pages

  • Amazon EC2
  • Challenges
  • Classes
  • Forum
  • Getting Started with Github
  • IRC
  • Open Discussion Forum
  • Pages
  • Problem Set 3 - Zhtta Server - Benchmarking
  • Projects
  • Problem Set 0 - Tutorial and Course Registration
  • Problem Set 1 - zhttpto Web Server
  • Problem Set 2 - The Good Auld Shell
  • Problem Set 2 - Exploration 1
  • Problem Set 2 - Exploration 2
  • Problem Set 3 - Zhtta Web Server
  • Problem Set 4 - IronKernel
  • PS4 - Setup Commands
  • Open Enrollment
  • Survey Comments
  • Syllabus
  • Forum
  • Using Materials
  • VirtualBox
  • Working on Github in cs4414
  • Setting up your Zhtta Server on EC2