HW6
released: 11/16, 21:00

> Answer the following questions.
> Submit your answers to Canvas assignments. There is an entry for this homework.
> 
> 1. Run mmap experiment.
> 
> Read handout week9.b (https://naizhengtan.github.io/21fall/notes/handout_9b.pdf).
> Copy the mmap code to a file "mmap.c".
> Do the exercise in the handout with 1G file and answer question:
> 
>   Which runs faster, option 1 or option 2 (in code)? by how much?

Mmap should be faster.
By how much depends, but should be somewhere between 5-1000x.

> 
> 2. Page replacement policy: CLOCK
> 
> Suppose you have a machine named CS5600-clover with 4 pages of memory (16KB) and a 1TB SSD.
> A process uses 10 pages; page P0-P3 are in the memory; P4-P9 are on SSD.
> OS runs CLOCK algorithm for page replacement, and a visualization is below.
> 
>       P0 (A=0)
>        ^
>        |
>  P3    +     P1
> (A=0)       (A=0)
> 
>       P2 (A=0)
> 
> For CLOCK algorithm:
> - The "hand"/"pointer" will go clock-wise.
> - When evicting page, check the page pointed by the "hand"
>   -- if access bit is set (A=1), clear the bit (A=0) and advance one position.
>   -- if A=0, evict the pointed page, load the new page, and advance one position.
>   (what's the access bit of the newly loaded page? answer: A=1)
> 
> If the memory accesses in the following are:
>   P0, P2, P3, P4, P5, P0, P9
> 
> How many page swaps will happen? and for each swap, which page has been swapped
> in and which page has been swapped out (namely, the victim)?
> 
> 
Anaswer:

  4 times

  (1) P4 replaces P1

         P0 (A=0)


    P3    +-->  P4
   (A=1)       (A=1)

         P2 (A=1)


  (2) P5 replaces P0

         P5 (A=1)
          ^
          |
    P3    +     P4
   (A=0)       (A=1)

         P2 (A=0)


  (3) P0 replaces P2

         P5 (A=1)


    P3    +     P4
   (A=0)  |    (A=0)
          v
         P5 (A=1)

  (4) P9 replaces P3

         P5 (A=1)


    P9 <--+     P4
   (A=1)       (A=0)

         P5 (A=1)


> 
> 3. Thrashing
> 
> Still, you're running program on the machine CS5600-clover with CLOCK algorithm.
> There are three processes A, B, and C. You run them separately.
> Each process starts with all pages on SSD.
> Below are their memory accesses:
> 
>   A: P0, P1, P2, P3, P0, P1, P2, P3, P0, P1
> 
>   B: P0, P1, P2, P3, P4, P0, P1, P2, P3, P4
> 
>   C: P0, P1, P2, P3, P4, P5, P6, P7, P8, P9
> 
> 3.a How many page loads from SSD (including page swaps) for each process?

Answer:
  A: 4
  B: 10
  C: 10

> 3.b Which process (or processes) do you think have trashing?

Answer:
  B and C
[update 11/23:
  OR B only (given the definition in my note.)]

  [By definition, thrashing means a state of constantly experiencing paging
  and page faults. For both B and C, 10 memory accesses trigger 10 page faults,
  which are of course thrashing.]