Reading 09: Swapping

Everyone:

Next week, after finishing up paging, we will explore how an OS uses swapping to allow for virtual address spaces larger than physical memory along with various page replacement algorithms.

TL;DR¶

For this reading assignment, you are to read about swapping, page replacement policies, and submit your responses to the Reading 09 Quiz.

Reading¶

The readings for this week are:

Operating Systems: Three Easy Pieces

Optional AI Conversation¶

Using Learn About from Google, have a conversation about paging and swapping by asking the following questions:

When using paging, why do we need TLBs?

When using paging, why do we use multiple levels?

When does swapping occur?

How does swapping and paging work together?

What are some common page replacement algorithms?

As you explore, feel free to dive into the suggested related questions or to "simplify", "go deeper", and "get images".

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 8-bit virtual addresses into physical addresses, while also detecting segmentation and protection faults in a simple paging system with 16-byte pages:

# Download addresses binary file
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.30341.fa24/static/txt/reading09/addresses.bin

# Translate virtual addresses in binary file to physical addresses
$ ./program < addresses.bin
VA[24] -> PA[54]
VA[81] -> PA[01] Segmentation Fault
VA[05] -> PA[35]
VA[cf] -> PA[0f] Segmentation Fault
VA[3c] -> PA[2c] Protection Fault
VA[19] -> PA[79]

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

As discussed in class, when using paging each virtual address can be broken down into a vpn portion and an offset portion:

The vpn portion is the first few bits in the virtual address. Given that we have an 8-bit virtual address and each page is 16 bytes, we will use the first 4 bits to denote the vpn in each virtual address.

To programatically extract the vpn, 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 vpn.

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

Once we know the vpn and the offset, we can use the PFN of the corresponding Page Table Entry in the Page Table to compute the physical address:

Physical Address = (PageTableEntry.PFN << VPN_SHIFT) | offset

To detect segmentation faults, we can check that the Valid bit of the Page Table Entry. Likewise, to detect protection faults, we can check the Protected bit of the Page Table Entry.

Template¶

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

/* Reading 09 */

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

/* Constants */

#define ADDRESS_LENGTH  // TODO: Define number of bits in virtual address
#define PAGE_SIZE       // TODO: Define number of bytes per Page

#define MAX_PAGES       // TODO: Define number of Pages in virtual address space
#define VPN_MASK        // TODO: Define bitmask for VPN portion of virtual address
#define VPN_SHIFT       // TODO: Define bitshift amount for VPN portion of virtual address
#define OFFSET_MASK     // TODO: Define bitmask for offset portion of virtual address

/* Structures */

/**
* Each Page Table Entry is a byte with the followin bit fields:
*
*  NNNNNNVP
*
*  NNNNNN: Physical Frame Number
*  V:     Valid bit (page is valid/in-use)
*  P:     Protection bit (page is protected/accessible)
**/
typedef struct {
    uint8_t PFN       : 6;
    uint8_t Valid     : 1;
    uint8_t Protected : 1;
} PageTableEntry;

/* Constants */

PageTableEntry PageTable[MAX_PAGES] = { // Page Table (normally in physical memory)
    {.PFN = 3, .Valid = 1, .Protected = 0}, /* Page 0 */
    {.PFN = 7, .Valid = 1, .Protected = 0}, /* Page 1 */
    {.PFN = 5, .Valid = 1, .Protected = 0}, /* Page 2 */
    {.PFN = 2, .Valid = 1, .Protected = 1}, /* Page 3 */
};

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

    while (fread(&virtual_address, sizeof(uint8_t), 1, stdin)) {
        uint8_t vpn    = // TODO: Determine VPN using VPN_MASK and VPN_SHIFT
        uint8_t offset = // TODO: Determine offset using OFFSET_MASK

        // TODO: Perform bounds and protection checks
        char *fault = "";
        if () {
            fault = " Segmentation Fault";
        } else if () {
            fault = " Protection Fault";
        }

        uint8_t physical_address = // TODO: Compute physical address using PFN and offset
        printf("VA[%02x] -> PA[%02x]%s\n", virtual_address, physical_address, fault);
    }

    return EXIT_SUCCESS;
}

As can been seen, the PageTable consists of the Page Table Entries described above with the PFN, Valid, and Protection fields for each corresponding page.

You will need to implement each of the TODOs to implement the virtual address to physical address translator.

Hints¶

For ADDRESS_LENGTH, this is given to you in the instructions above.
For PAGE_SIZE, this is given to you in the instructions above.
For MAX_PAGES, this is the total number of pages possible given the address space size and the individual PAGE_SIZE.
For VPN_MASK, consider writing out the bitmask on paper and then translating into hexadecimal.
For VPN_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 VPN_MASK.
To compute the vpn, we want to apply the VPN_MASK to the virtual address and then shift the result to the right by the VPN_SHIFT.

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

For instance, if the virtual address was 0010 0100, applying the OFFSET_MASK should give us 0000 0100.
To check for segmentation and protection faults, you must check the Valid and Protected fields of the Page Table Entry.
To compute the physical address, you must use the PFN value in the Page Table along with the offset.

Submission¶

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

$ git switch 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.30
     Q02 0.40
     Q03 0.35
     Q04 0.40
     Q05 0.20
     Q06 0.15
     Q07 0.05
     Q08 0.10
     Q09 0.05
   Score 2.00 / 2.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
Testing reading09 program...
   Score 2.00 / 2.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.