Lab: Memory Translation, Segmentation, and Paging

CSC 213 - Operating Systems and Parallel Algorithms - Weinman



Summary:
You will experiment with address space virtualization via translation, segmentation and paging systems.
Assigned:
Tuesday 23 September
Due:
11:30 PM Monday 29 September
Objectives:
Practice memory address translation and identifying segmentation and page faults.
Collaboration:
You will do this lab in teams as assigned by the instructor.
Reading:
Read the details on the three simulators you will be using for the lab:

Exercises

Preliminaries

Do this laboratory on any MathLAN workstation. You don't need to copy any starter files, simply change your working directory as follows.
$ cd ~weinman/public_html/courses/CSC213/2014F/labs/code/memory

Part A: Address Translation

  1. [Exploration] Run the translation simulator with seed 1:
    ./relocation.pyc -s 1
    Manually check whether each virtual address generated is within bounds. If so, compute the translation. When you are done, verify your work with the -c flag.
  2. Consider the following translation scenario.
    ARG address space size 1k
    ARG phys mem size 16k
    Base-and-Bounds register information:
      Base   : 0x00003255 (decimal 12885)
      Limit  : 359
    Virtual Address Trace
      VA  0: 0x00000040 (decimal:   64)
      VA  1: 0x000000d1 (decimal:  209)
      VA  2: 0x00000001 (decimal:    1)
      VA  3: 0x00000105 (decimal:  261)
      VA  4: 0x0000035e (decimal:  862)
    For each virtual address, either write down the physical address it translates to or write down that it is an out-of-bounds address (a segmentation violation).
  3. Run the simulator as follows:
    ./relocation.pyc -s 0 -n 10
    What minimum value must the bounds register (set with the -l flag, (thats ell, for limit) be for all the generated virtual addresses to be valid? Verify your answer using the simulator.
  4. Run the simulator as follows:
    ./relocation.pyc -s 1 -n 10 -l 100
    What is the largest meaningful value the bounds register may take so that the address space fits entirely into physical memory? (Remember that 16k=16×210.)

Part B: Segmentation

If you haven't already, be sure you study and completely understand the small example in the segmentation reading.
  1. First let s use a tiny address space to translate some addresses. Run the segmentation simulator as follows:
    ./segmentation.pyc -a 128 -p 512 -b 0 -l 20 -B 512 -L 20 -s 0
    1. Translate the addresses (indicating the segment) or report a segmentation violation. When you are done, verify your work using the -c flag.
    2. What is the highest legal virtual address in segment 0?
    3. What about the lowest legal virtual address in segment 1?
    4. What are the lowest and highest illegal virtual addresses in this entire address space?
    5. Run segmentation.pyc with the -A flag to verify your answers. (This could require eight addresses.)
  2. Consider the following segmentation scenario.
    ARG address space size 128
    ARG phys mem size 512
    Segment register information:
      Segment 0 base  (grows positive) : 0x00000000 (decimal 0)
      Segment 0 limit                  : 20
      Segment 1 base  (grows negative) : 0x00000200 (decimal 512)
      Segment 1 limit                  : 20
    Virtual Address Trace
      VA  0: 0x0000007c (decimal:  124)
      VA  1: 0x00000009 (decimal:    9)
      VA  2: 0x0000002b (decimal:   43)
      VA  3: 0x00000043 (decimal:   67)
      VA  4: 0x0000001f (decimal:   31
      VA  5: 0x00000011 (decimal:   17)
      VA  6: 0x0000005c (decimal:   92)
      VA  7: 0x00000070 (decimal:  112)
      VA  8: 0x0000004c (decimal:   76)
      VA  9: 0x0000002b (decimal:   43)
    Translate the addresses or report a segmentation violation, indicating the segment in both cases.
  3. Let s say we have a tiny 16-byte address space in a 128-byte physical memory. Assuming an address stream from 0 to 15, what base and bounds would you set up so as to get the simulator to generate the following translation results: valid, valid, violation, ..., violation, valid, valid? That is, running the simulator as follows,
    ./segmentation.pyc -a 16 -p 128 -A 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 --b0 ? --l0 ? --b1 ? --l1 ?
    what should the arguments to b0, l0, b1, and l1 be? Where multiple values might be possible, indicate so and briefly explain why.
  4. Say we want to generate a problem where roughly 90% of the randomly-generated virtual addresses are valid (i.e., not segmentation violations). How should you configure the simulator to do so? Which parameters are important?

Part C: Linear Paging

  1. How do you expect the linear page table size to change as the address space grows?
  2. [Exploration] Test your hypothesis using the paging simulator with various address space sizes, keeping other elements constant. For example,
    ./paging-linear-translate.pyc -P 1k -a 1m -p 512m -v -n 0
    If your data explorations contradict your hypothesis, revise your hypothesis so that it is consistent with the data.
  3. How do you expect the linear page table size to change as the page size grows?
  4. [Exploration] Test your hypothesis using the paging simulator with various page sizes, keeping other elements constant. Once again, if necessary, revise your hypothesis so as to be consistent with the observations.
  5. [Exploration] Run the paging simulator as follows:
    ./paging-linear-translate.pyc -P 1k -a 16k -p 32k -v -u 50
    Translate the addresses (indicating the page number) or report an invalid page number. When you are done, verify your work using the -c flag.
  6. Consider the following paging scenario.
    ARG address space size 16k
    ARG phys mem size 32k
    ARG page size 1k
    ARG verbose True
    The format of the page table is simple:
    The high-order (left-most) bit is the VALID bit.
      If the bit is 1, the rest of the entry is the PFN.
      If the bit is 0, the page is not valid.
    Page Table (from entry 0 down to the max size)
      [       0]   0x80000000
      [       1]   0x80000007
      [       2]   0x80000015
      [       3]   0x80000002
      [       4]   0x80000000
      [       5]   0x00000000
      [       6]   0x80000000
      [       7]   0x00000000
      [       8]   0x80000011
      [       9]   0x00000000
      [      10]   0x80000019
      [      11]   0x00000000
      [      12]   0x80000016
      [      13]   0x80000004
      [      14]   0x8000000a
      [      15]   0x00000000
    Virtual Address Trace
      VA 0x00000630 (decimal:     1584)
      VA 0x0000363d (decimal:    13885)
      VA 0x000026a3 (decimal:     9891)
      VA 0x000033a7 (decimal:    13223)
      VA 0x00002eb3 (decimal:    11955)
    Translate the addresses (indicating the page number) or report an invalid page number.

What to turn in

A single pdf (no tar file) containing answers to all questions, except those marked [Exploration].
Acknowledgment:
These exercises are adapted from those accompanying the simulators in the Arpaci-Dusseaus' Three Easy Pieces.