History

Remzi Arpaci-Dusseau ab8cba148a fixed bug (found by Benjamin Wilhelm) that doesn't check if phys addr is big enough given various base addresses		2020-06-13 08:00:57 -05:00
..
README.md	initial commit of segmentation simulator	2020-05-19 11:15:26 -05:00
segmentation.py	fixed bug (found by Benjamin Wilhelm) that doesn't check if phys addr is big enough given various base addresses	2020-06-13 08:00:57 -05:00

README.md

Overview

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

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.

Enjoy!