Segmentation

Due:

11:00pm, Friday February 18, 2022

Description

For this assignment we will run process related simulators from the textbook supplementary material (source) and answer related questions. A zip file with the simulator programs linked on the assignments page. The README files for each program are listed below that contain information on how to run each simulator program. Read these before answering the questions that follow.

relocation.py README

This program allows you to see how address translations are performed in a system with base and bounds registers. As before, there are two steps to running the program to test out your understanding of base and bounds. First, run without the -c flag to generate a set of translations and see if you can correctly perform the address translations yourself. Then, when done, run with the -c flag to check your answers.

In this homework, we will assume a slightly different address space than our canonical one with a heap and stack at opposite ends of the space. Rather, we will assume that the address space has a code section, then a fixed-sized (small) stack, and a heap that grows downward right after, looking something like you see in the Figure below. In this configuration, there is only one direction of growth, towards higher regions of the address space.

  -------------- 0KB
  |    Code    |
  -------------- 2KB
  |   Stack    |
  -------------- 4KB
  |    Heap    |
  |     |      |
  |     v      |
  -------------- 7KB
  |   (free)   |
  |     ...    |

In the figure, the bounds register would be set to 7~KB, as that represents the end of the address space. References to any address within the bounds would be considered legal; references above this value are out of bounds and thus the hardware would raise an exception.

To run with the default flags, type relocation.py at the command line. The result should be something like this:

prompt> ./relocation.py 
...
Base-and-Bounds register information:

  Base   : 0x00003082 (decimal 12418)
  Limit  : 472

Virtual Address Trace
  VA  0: 0x01ae (decimal:430) -> PA or violation?
  VA  1: 0x0109 (decimal:265) -> PA or violation?
  VA  2: 0x020b (decimal:523) -> PA or violation?
  VA  3: 0x019e (decimal:414) -> PA or violation?
  VA  4: 0x0322 (decimal:802) -> PA or violation?

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). For this problem, you should assume a simple virtual address space of a given size.

As you can see, the homework simply generates randomized virtual addresses. For each, you should determine whether it is in bounds, and if so, determine to which physical address it translates. Running with -c (the “compute this for me” flag) gives us the results of these translations, i.e., whether they are valid or not, and if valid, the resulting physical addresses. For convenience, all numbers are given both in hex and decimal.

prompt> ./relocation.py -c
...
Virtual Address Trace
  VA  0: 0x01ae (decimal:430) -> VALID: 0x00003230 (dec:12848)
  VA  1: 0x0109 (decimal:265) -> VALID: 0x0000318b (dec:12683)
  VA  2: 0x020b (decimal:523) -> SEGMENTATION VIOLATION
  VA  3: 0x019e (decimal:414) -> VALID: 0x00003220 (dec:12832)
  VA  4: 0x0322 (decimal:802) -> SEGMENTATION VIOLATION

With a base address of 12418 (decimal), address 430 is within bounds (i.e., it is less than the limit register of 472) and thus translates to 430 added to 12418 or 12848. A few of the addresses shown above are out of bounds (523, 802), as they are in excess of the bounds. Pretty simple, no? Indeed, that is one of the beauties of base and bounds: it’s so darn simple!

There are a few flags you can use to control what’s going on better:

prompt> ./relocation.py -h
Usage: relocation.py [options]

Options:
  -h, --help            show this help message and exit
  -s SEED, --seed=SEED  the random seed
  -a ASIZE, --asize=ASIZE address space size (e.g., 16, 64k, 32m)
  -p PSIZE, --physmem=PSIZE physical memory size (e.g., 16, 64k)
  -n NUM, --addresses=NUM # of virtual addresses to generate
  -b BASE, --b=BASE     value of base register
  -l LIMIT, --l=LIMIT   value of limit register
  -c, --compute         compute answers for me

In particular, you can control the virtual address-space size (-a), the size of physical memory (-p), the number of virtual addresses to generate (-n), and the values of the base and bounds registers for this process (-b and -l, respectively).

segmentation.py README

This program allows you to see how address translations are performed in a system with segmentation. The segmentation that this system uses is pretty simple: an address space has just two segments; further, the top bit of the virtual address generated by the process determines which segment the address is in: 0 for segment 0 (where, say, code and the heap would reside) and 1 for segment 1 (where the stack lives). Segment 0 grows in a positive direction (towards higher addresses), whereas segment 1 grows in the negative direction.

Visually, the address space looks like this:

 --------------- virtual address 0
 |    seg0     |
 |             |
 |             |
 |-------------|
 |             |
 |             |
 |             |
 |             |
 |(unallocated)|
 |             |
 |             |
 |             |
 |-------------|
 |             |
 |    seg1     |
 |-------------| virtual address max (size of address space)

With segmentation, as you might recall, there is a base/limit pair of registers per segment. Thus, in this problem, there are two base/limit pairs. The segment-0 base tells which physical address the top of segment 0 has been placed in physical memory and the limit tells how big the segment is; the segment-1 base tells where the bottom of segment 1 has been placed in physical memory and the corresponding limit also tells us how big the segment is (or how far it grows in the negative direction).

As before, there are two steps to running the program to test out your understanding of segmentation. First, run without the “-c” flag to generate a set of translations and see if you can correctly perform the address translations yourself. Then, when done, run with the “-c” flag to check your answers.

For example, to run with the default flags, type:

prompt> ./segmentation.py 

or

prompt> python ./segmentation.py 

You should see this:

  ARG seed 0
  ARG address space size 1k
  ARG phys mem size 16k
  
  Segment register information:

    Segment 0 base  (grows positive) : 0x00001aea (decimal 6890)
    Segment 0 limit                  : 472

    Segment 1 base  (grows negative) : 0x00001254 (decimal 4692)
    Segment 1 limit                  : 450

  Virtual Address Trace
    VA  0: 0x0000020b (decimal:  523) --> PA or segmentation violation?
    VA  1: 0x0000019e (decimal:  414) --> PA or segmentation violation?
    VA  2: 0x00000322 (decimal:  802) --> PA or segmentation violation?
    VA  3: 0x00000136 (decimal:  310) --> PA or segmentation violation?
    VA  4: 0x000001e8 (decimal:  488) --> PA or segmentation violation?

  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). For this problem, you should assume a simple address space with
  two segments: the top bit of the virtual address can thus be used to check
  whether the virtual address is in segment 0 (topbit=0) or segment 1
  (topbit=1). Note that the base/limit pairs given to you grow in different
  directions, depending on the segment, i.e., segment 0 grows in the positive
  direction, whereas segment 1 in the negative.  

Then, after you have computed the translations in the virtual address trace, run the program again with the “-c” flag. You will see the following (not including the redundant information):

  Virtual Address Trace
    VA  0: 0x0000020b (decimal:  523) --> SEGMENTATION VIOLATION (SEG1)
    VA  1: 0x0000019e (decimal:  414) --> VALID in SEG0: 0x00001c88 (decimal: 7304)
    VA  2: 0x00000322 (decimal:  802) --> VALID in SEG1: 0x00001176 (decimal: 4470)
    VA  3: 0x00000136 (decimal:  310) --> VALID in SEG0: 0x00001c20 (decimal: 7200)
    VA  4: 0x000001e8 (decimal:  488) --> SEGMENTATION VIOLATION (SEG0)

As you can see, with -c, the program translates the addresses for you, and hence you can check if you understand how a system using segmentation translates addresses.

Of course, there are some parameters you can use to give yourself different problems. One particularly important parameter is the -s or -seed parameter, which lets you generate different problems by passing in a different random seed. Of course, make sure to use the same random seed when you are generating a problem and then solving it.

There are also some parameters you can use to play with different-sized address spaces and physical memories. For example, to experiment with segmentation in a tiny system, you might type:

prompt> ./segmentation.py -s 100 -a 16 -p 32
ARG seed 0
ARG address space size 16
ARG phys mem size 32
 
Segment register information:

  Segment 0 base  (grows positive) : 0x00000018 (decimal 24)
  Segment 0 limit                  : 4

  Segment 1 base  (grows negative) : 0x00000012 (decimal 18)
  Segment 1 limit                  : 5

Virtual Address Trace
  VA  0: 0x0000000c (decimal:   12) --> PA or segmentation violation?
  VA  1: 0x00000008 (decimal:    8) --> PA or segmentation violation?
  VA  2: 0x00000001 (decimal:    1) --> PA or segmentation violation?
  VA  3: 0x00000007 (decimal:    7) --> PA or segmentation violation?
  VA  4: 0x00000000 (decimal:    0) --> PA or segmentation violation?

which tells the program to generate virtual addresses for a 16-byte address space placed somewhere in a 32-byte physical memory. As you can see, the resulting virtual addresses are tiny (12, 8, 1, 7, and 0). As you can also see, the program picks tiny base register and limit values, as appropriate. Run with -c to see the answers.

This example should also show you exactly what each base pair means. For example, segment 0’s base is set to a physical address of 24 (decimal) and is of size 4 bytes. Thus, virtual addresses 0, 1, 2, and 3 are in segment 0 and valid, and map to physical addresses 24, 25, 26, and 27, respectively.

Slightly more tricky is the negative-direction-growing segment 1. In the tiny example above, segment 1’s base register is set to physical address 18, with a size of 5 bytes. That means that the last five bytes of the virtual address space, in this case 11, 12, 13, 14, and 15, are valid virtual addresses, and that they map to physical addresses 13, 14, 15, 16, and 17, respectively.

If that doesn’t make sense, read it again – you will have to make sense of how this works in order to do any of these problems.

Note you can specify bigger values by tacking a “k”, “m”, or even “g” onto the values you pass in with the -a or -p flags, as in “kilobytes”, “megabytes”, and “gigabytes”. Thus, if you wanted to do some translations with a 1-MB address space set in a 32-MB physical memory, you might type:

prompt> ./segmentation.py -a 1m -p 32m

If you want to get even more specific, you can set the base register and limit register values yourself, with the –b0, –l0, –b1, and –l1 registers. Try them and see.

Finally, you can always run

prompt> ./segmentation.py -h 

to get a complete list of flags and options.

Questions

1. Run the relocation.py simulator with the flags: -s 0 -n 10. What value do you need to set the bounds register to (with the -l flag) in order to ensure that all generated virtual addresses are within the bounds?

2. Run the relocation.py simulator with the flags: -s 0 -n 10 -l 100. What is the maximum value that the base can be set to so that the address space still fits into the entire physical memory?

3. Given an address space specified by the command

   segmentation.py -a 128 -p 512 -b 0 -l 20 -B 512 -L 20

   Answer the following questions:

   • What is the highest legal virtual address in segment 0?
   • What is the lowest legal virtual address in segment 1?
   • What are the lowest and highest illegal addresses in the address space?
   • How would you set the -A flag to determine if you are correct?

4. Fill in the question marks in the command

   segmentation.py -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 ?

   so that the translation results for the specified address stream: valid, valid, violation, …, violation, valid, valid?

5. Can you run the simulator so that no virtual addresses are valid? If so write the command you used.

Turning in the Assignment

Create a text file named assignment3.txt containing your answers to the questions. Submit your solution to the appropriate folder on D2L.

Note that your answers must be correctly numbered and only the answers must be in your submission; any answer solution that does not satisfy these requirements will be marked as a zero.