Homework for Chapter 15 of 《Operating Systems: Three Easy Pieces》: Relocation

1. root@C202511211157657:~# python3 relocation.py -s 1
   ARG seed 1
   ARG address space size 1k
   ARG phys mem size 16k
   Base-and-Bounds register information:
   Base   : 0x0000363c (decimal 13884)
   Limit  : 290
   Virtual Address Trace
   VA  0: 0x0000030e (decimal:  782) --> PA or segmentation violation?
   VA  1: 0x00000105 (decimal:  261) --> PA or segmentation violation?
   VA  2: 0x000001fb (decimal:  507) --> PA or segmentation violation?
   VA  3: 0x000001cc (decimal:  460) --> PA or segmentation violation?
   VA  4: 0x0000029b (decimal:  667) --> 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 virtual address space of a given size.

   As the readme says, it’s darn simple.

VA 0: 0x0000030e (decimal: 782) –> segmentation violation
VA 1: 0x00000105 (decimal: 261) –> PA: 0x00003741
VA 2: 0x000001fb (decimal: 507) –> segmentation violation
VA 3: 0x000001cc (decimal: 460) –> segmentation violation
VA 4: 0x0000029b (decimal: 667) –> segmentation violation

Actually: correct.

root@C202511211157657:~# python3 relocation.py -s 2 -c
ARG seed 2
ARG address space size 1k
ARG phys mem size 16k
Base-and-Bounds register information:
  Base   : 0x00003ca9 (decimal 15529)
  Limit  : 500
Virtual Address Trace
  VA  0: 0x00000039 (decimal:   57) --> PA or segmentation violation?
  VA  1: 0x00000056 (decimal:   86) --> PA or segmentation violation?
  VA  2: 0x00000357 (decimal:  855) --> PA or segmentation violation?
  VA  3: 0x000002f1 (decimal:  753) --> PA or segmentation violation?
  VA  4: 0x000002ad (decimal:  685) --> PA or segmentation violation?

VA 0: 0x00000039 (decimal: 57) –> PA: 0x00003ce2
VA 1: 0x00000056 (decimal: 86) –> PA: 0x00003cff
VA 2: 0x00000357 (decimal: 855) –> segmentation violation
VA 3: 0x000002f1 (decimal: 753) –> segmentation violation
VA 4: 0x000002ad (decimal: 685) –> segmentation violation

Actually: correct.

root@C202511211157657:~# python3 relocation.py -s 3 -c
ARG seed 3
ARG address space size 1k
ARG phys mem size 16k
Base-and-Bounds register information:
  Base   : 0x000022d4 (decimal 8916)
  Limit  : 316
Virtual Address Trace
  VA  0: 0x0000017a (decimal:  378) --> PA or segmentation violation?
  VA  1: 0x0000026a (decimal:  618) --> PA or segmentation violation?
  VA  2: 0x00000280 (decimal:  640) --> PA or segmentation violation?
  VA  3: 0x00000043 (decimal:   67) --> PA or segmentation violation?
  VA  4: 0x0000000d (decimal:   13) --> PA or segmentation violation?

VA 0: 0x0000017a (decimal: 378) –> segmentation violation
VA 1: 0x0000026a (decimal: 618) –> segmentation violation
VA 2: 0x00000280 (decimal: 640) –> segmentation violation
VA 3: 0x00000043 (decimal: 67) –> PA: 0x00002317
VA 4: 0x0000000d (decimal: 13) –> PA: 0x000022e1

Actually: correct.

root@C202511211157657:~# python3 relocation.py -s 0 -n 10
ARG seed 0
ARG address space size 1k
ARG phys mem size 16k
Base-and-Bounds register information:
  Base   : 0x00003082 (decimal 12418)
  Limit  : 472
Virtual Address Trace
  VA  0: 0x000001ae (decimal:  430) --> PA or segmentation violation?
  VA  1: 0x00000109 (decimal:  265) --> PA or segmentation violation?
  VA  2: 0x0000020b (decimal:  523) --> PA or segmentation violation?
  VA  3: 0x0000019e (decimal:  414) --> PA or segmentation violation?
  VA  4: 0x00000322 (decimal:  802) --> PA or segmentation violation?
  VA  5: 0x00000136 (decimal:  310) --> PA or segmentation violation?
  VA  6: 0x000001e8 (decimal:  488) --> PA or segmentation violation?
  VA  7: 0x00000255 (decimal:  597) --> PA or segmentation violation?
  VA  8: 0x000003a1 (decimal:  929) --> PA or segmentation violation?
  VA  9: 0x00000204 (decimal:  516) --> 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 virtual address space of a given size.

Maximum address in VAS: 929, so the answer is strictly bigger than 929. (>=930)

3. root@C202511211157657:~# python3 relocation.py -s 1 -n 10 -l 100
   ARG seed 1
   ARG address space size 1k
   ARG phys mem size 16k
   Base-and-Bounds register information:
   Base   : 0x00000899 (decimal 2201)
   Limit  : 100
   Virtual Address Trace
   VA  0: 0x00000363 (decimal:  867) --> PA or segmentation violation?
   VA  1: 0x0000030e (decimal:  782) --> PA or segmentation violation?
   VA  2: 0x00000105 (decimal:  261) --> PA or segmentation violation?
   VA  3: 0x000001fb (decimal:  507) --> PA or segmentation violation?
   VA  4: 0x000001cc (decimal:  460) --> PA or segmentation violation?
   VA  5: 0x0000029b (decimal:  667) --> PA or segmentation violation?
   VA  6: 0x00000327 (decimal:  807) --> PA or segmentation violation?
   VA  7: 0x00000060 (decimal:   96) --> PA or segmentation violation?
   VA  8: 0x0000001d (decimal:   29) --> PA or segmentation violation?
   VA  9: 0x00000357 (decimal:  855) --> 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 virtual address space of a given size.

When the last address is not beyond the limit of physical address space, I think you can just use the last address in physical address space and the base address of virtual address in physical space, and minus it with 1 again, so it would be 16000 – 2201 – 1 = 13798.

Actually：

Base + limit ≤ phys_mem_size

1k = 1024 → maximum limit = 14183. I screwed up with the k and -1.

4. root@C202511211157657:~# python3 relocation.py -s 1 -n 10 -a 32m -p 1g -l 100
   ARG seed 1
   ARG address space size 32m
   ARG phys mem size 1g
   Base-and-Bounds register information:
   Base   : 0x08996c7c (decimal 144272508)
   Limit  : 100
   Virtual Address Trace
   VA  0: 0x01b1e2d5 (decimal: 28435157) --> PA or segmentation violation?
   VA  1: 0x01870d77 (decimal: 25628023) --> PA or segmentation violation?
   VA  2: 0x00829868 (decimal: 8558696) --> PA or segmentation violation?
   VA  3: 0x00fda9aa (decimal: 16624042) --> PA or segmentation violation?
   VA  4: 0x00e623b1 (decimal: 15082417) --> PA or segmentation violation?
   VA  5: 0x014d9d98 (decimal: 21863832) --> PA or segmentation violation?
   VA  6: 0x0193d38c (decimal: 26465164) --> PA or segmentation violation?
   VA  7: 0x00300e5d (decimal: 3149405) --> PA or segmentation violation?
   VA  8: 0x000e838f (decimal: 951183) --> PA or segmentation violation?
   VA  9: 0x01abe967 (decimal: 28043623) --> 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 virtual address space of a given size.

   It would be the same process as the 3rd question. So it would be the result of 1000000000 – 144272508 – 1 = 855727491.

Actually：1g = 1,073,741,824 → maximum limit = 929,469,316. I screwed up with the g and -1 again.

5. When the virtual address is smaller than the limit, it’s valid.