Reading 09: Segmentation, Paging

Everyone:

Next week, we will explore how an OS uses segmentation and paging to implement a more sophisticated version of virtual memory. Rather than rely on simple base and bounds registers, we will divide up memory into blocks and map these to different parts of physical memory. To perform this mapping, we will utilize a series of hardware tables or caches that need to be updated and managed by the operating system.

TL;DR¶

For this reading assignment, you are to read about segmentation, paging, page tables, and TLBs, and submit your responses to the Reading 09 Quiz.

Reading¶

The readings for this week are:

Operating Systems: Three Easy Pieces

Quiz¶

Once you have done the readings, answer the following Reading 09 Quiz questions:

Program¶

For this week, you are to implement a program that translates 16-bit virtual addresses into physical addresses, while also detecting segmentation faults:

# Download addresses binary file
$ curl -LO https://raw.githubusercontent.com/nd-cse-30341-fa21/cse-30341-fa21-assignments/master/reading09/addresses.bin

# Translate virtual addresses in binary file to physical addresses
$ ./program < addresses.bin
VA[840a] -> PA[940a]
VA[8fff] -> PA[9fff] Segmentation Fault
VA[4022] -> PA[8822]
VA[4aaa] -> PA[92aa] Segmentation Fault
VA[0366] -> PA[8366]
VA[0c33] -> PA[8c33] Segmentation Fault
VA[c19b] -> PA[719b]
VA[cbde] -> PA[7bde] Segmentation Fault

The program reads in a binary addresses.bin file from stdin where each virtual address is a 16-bit integer and then uses the following Segmentation Table to translate each virtual address into a physical address:

As noted in the reading, when using segmentation each virtual address can be broken down into a segment portion and an offset portion:

The segment portion is the first few bits in the virtual address. Since we have 4 segments, we will use the first 2 bits to denote the segment in each virtual address.

To programatically extract the segment, we can apply a bitmask to the virtual address and shift the bits to the right (the length of the offset).
The offset portion of the virtual address are the remaining bits not in the segment.

To programatically extract the offset, we can apply a bitmask to the virtual address.

Once we know the segment and the offset, we can use the base of the segment in the Segmentation Table to compute the physical address:

Physical Address = Segment.base + offset

To detect for segmentation faults, we can check that the offset is within the bounds or size of the segment in the Segmentation Table stored in the MMU.

Template¶

Your task is to implement this Segmentation address translation process by completing the following template.c:

/* Reading 09 */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

/* Constants */

#define KB            // TODO: Define Kilobyte
#define SEGMENT_MASK  // TODO: Define Bitmask for Segment portion of Virtual Address
#define SEGMENT_SHIFT // TODO: Define Bitshift amount for Segment portion of Virtual Address
#define OFFSET_MASK   // TODO: Define Bitmask for Offset portion of Virtual Address

/* Structures */

typedef struct {
    uint16_t base;
    uint16_t size;
} SegmentRecord;

/* Constants */

SegmentRecord MMU[] = { // Segmentation Table stored in MMU
    {.base = 32*KB, .size = 2*KB},   /* 00: Code  */
    {.base = 34*KB, .size = 2*KB},   /* 01: Data  */
    {.base = 36*KB, .size = 2*KB},   /* 10: Heap  */
    {.base = 28*KB, .size = 2*KB},   /* 11: Stack */
};

int main(int argc, char *argv[]) {
    uint16_t virtual_address;

    while (fread(&virtual_address, sizeof(uint16_t), 1, stdin)) {
        uint16_t segment = // TODO: Determine segment using SEGMENT_MASK and SEGMENT_SHIFT
        uint16_t offset  = // TODO: Determine offset using OFFSET_MASK

        char *fault = "";
        if () { // TODO: Perform bounds checking using MMU and offset
            fault = " Segmentation Fault";
        }

        uint16_t physical_address = // TODO: Compute physical address using MMU and offset
        printf("VA[%04hx] -> PA[%04hx]%s\n", virtual_address, physical_address, fault);
    }

    return EXIT_SUCCESS;
}

As can been seen, the MMU consists of the Segmentation Table described above with the base and bounds registers of each segment. You will need to implement each of the TODOs to implement the virtual address to physical address translator.

Hints¶

For KB, this is simply the number of bytes in a kilobyte (ie. base-2).
For SEGMENT_MASK, consider writing out the bitmask on paper and then translating into hexadecimal.
For SEGMENT_SHIFT, remember that this is the length of the offset component of the virtual address.
For OFFSET_MASK, this is the complement or inverse of the SEGMENT_MASK.
To compute the segment, we want to apply the SEGMENT_MASK to the virtual address and then shift the result to the right by the SEGMENT_SHIFT.

For instance, if the virtual address was 1100 0010 0000 1010, applying the SEGMENT_MASK should give us 1100 0000 0000 0000. We then want to shift to the right to get: 0000 0000 0000 0011.
To compute the offset, we want to apply the OFFSET_MASK to the virtual address.

For instance, if the virtual address was 1100 0010 0000 1010, applying the OFFSET_MASK should give us 0000 0010 0000 1010.
To perform bounds checking, you must check the offset with the size component of the segment record in the MMU.
To compute the physical address, you must use the base value in the Segmentation Table along with the offset.

Submission¶

To submit you work, follow the same process outlined in Reading 01:

$ git checkout master                 # Make sure we are in master branch
$ git pull --rebase                   # Make sure we are up-to-date with GitLab

$ git checkout -b reading09           # Create reading09 branch and check it out

$ cd reading09                        # Go into reading09 folder
$ $EDITOR answers.json                # Edit your answers.json file

$ ../.scripts/check.py                # Check reading09 quiz
Checking reading09 quiz ...
     Q01 0.20
     Q02 0.80
     Q03 0.20
     Q04 0.40
     Q05 0.20
     Q06 0.40
     Q07 0.60
     Q08 0.20
   Score 3.00 / 3.00
  Status Success

$ git add answers.json                # Add answers.json to staging area
$ git commit -m "Reading 09: Quiz"    # Commit work

$ $EDITOR program.c                   # Edit your program.c file

$ make test-program                   # Check reading03 program
Checking reading09 program...
   Score 3.00 / 3.00
  Status Success

$ git add Makefile                    # Add Makefile to staging area
$ git add program.c                   # Add program.c to staging area
$ git commit -m "Reading 09: Code"    # Commit work

$ git push -u origin reading09        # Push branch to GitHub

Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 09 TA List.