Title: Class 7: Double Faults
Date: 2014-02-06
Category: Classes
Tags: operating systems, Rust, virtual memory, processes
Author: David Evans

   <div class="todo">
<center>
**[Problem Set 2](|filename|../../pages/ps/ps2/ps2.md)** is due Sunday, 9 February.  You should sign-up for a team demo using [this form](https://docs.google.com/spreadsheet/ccc?key=0AvXGI69lkg_edGE4dk0taUFlcmVueGg0UExIT1RZSXc&usp=sharing#gid=0).  
</center>
   </div>


   <div class="todo"> 
Remember to check the [course
calendar](https://www.google.com/calendar/embed?src=7ibtm6lnt88vl00h7a0e8n0bc4%40group.calendar.google.com&ctz=America/New_York)
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.)

</center>
   </div>

### Recommended Reading

Chapters [12](http://pages.cs.wisc.edu/~remzi/OSTEP/vm-intro.pdf)
through [23](http://pages.cs.wisc.edu/~remzi/OSTEP/vm-dialogue.pdf) of
the [OSTEP](http://pages.cs.wisc.edu/~remzi/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

<center>
<iframe src="http://www.slideshare.net/slideshow/embed_code/30917468" width="476" height="400" frameborder="2" marginwidth="0" marginheight="0" scrolling="no"></iframe>

<!-- <iframe src="http://www.slideshare.net/slideshow/embed_code/30634254" width="476" height="400" frameborder="2" marginwidth="0" marginheight="0" scrolling="no"></iframe><br>-->
<!--[Videos](http://www.youtube.com/watch?v=ycpSnZN-c_Q&feature=share&list=PLvpsxlEF9cP2hCgWeSjVLIG-2QrMzq6Ma)-->
</center>

# Page Tables

How well does the 386 architecture work for larger memories?
<div class="gap">

</div>

Why not just make the page size bigger to support more memory?
<div class="gap">

</div>

What are the advantages of flexible page sizes over fixed page sizes?
<div class="gap">

</div>

[ARMv8 White Paper](http://www.arm.com/files/downloads/ARMv8_white_paper_v5.pdf) 
[ARMv8 Architecture](http://www.arm.com/files/downloads/ARMv8_Architecture.pdf)

[_Qualcomm and Samsung Pass AMD in MPU Ranking_](http://www.icinsights.com/news/bulletins/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?
<div class="gap">

</div>

What does it mean if a C++ program execution generates a segmentation fault?
<div class="gap">

</div>

What does it mean if a Rust program execution generates a segmentation fault?
<div class="gap">

</div>

How often should page faults happen in a Rust program?
<div class="gap">

</div>

What does this program do? [[Code](|filename|./segfault.c)]
````C
#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?

<div class="gap">

</div>

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

<div class="gap">

</div>

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

<div class="gap">

</div>

## 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:

````rust
    fn spawn(f: proc())
````

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

````rust
   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](|filename|./find_collatz_m3.rs)] (I believe, but not with a lot
of confidence, that it is correct, but it sometimes leads Rust to segv)

````rust
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.)


<div id="disqus_thread"></div>

<script type="text/javascript">
        /* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
        var disqus_shortname = 'rust-class'; // required: replace example with your forum shortname
	var disqus_url = 'http://www.rust-class.org/class-7-faults.html';

        /* * * DON'T EDIT BELOW THIS LINE * * */
        (function() {
            var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
            dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
            (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
        })();
</script>
<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

