Virtual Memory - Revision exercises

mkdir lru
cd lru
1521 fetch lru

Your task is to simulate least-recently-used (LRU) replacement of virtual memory pages.

Write a C program, lru.c, which takes two arguments, both integers.

This will be respectively the size in frames of simulated physical memory and and the size in pages of simulated virtual memory.

lru.c should then read integers from stdin until EOF.

Each integer will be the number of a virtual page being accessed.

lru.c should print one line of output for indicate what action occurs with a physical memory with a given number of frames.

dcc lru.c -o lru
./lru 4 6
Simulating 4 frames of physical memory, 6 pages of virtual memory
5
Time 0: virtual page 5 loaded to physical frame 0
3
Time 1: virtual page 3 loaded to physical frame 1
5
Time 2: virtual page 5 -> physical frame 0
3
Time 3: virtual page 3 -> physical frame 1
0
Time 4: virtual page 0 loaded to physical frame 2
1
Time 5: virtual page 1 loaded to physical frame 3
2
Time 6: virtual page 2  - virtual page 5 evicted - loaded to physical frame 0
2
Time 7: virtual page 2 -> physical frame 0
3
Time 8: virtual page 3 -> physical frame 1
5
Time 9: virtual page 5  - virtual page 0 evicted - loaded to physical frame 2

The provided code includes an array containing a data structure mapping each physical frame to a virtual page, as well as its last access time. This is known as an inverted page table.

For each access this function is called:

void access_page(int virtual_page, int access_time, int n_physical_frames, struct ipt_entry *ipt) {

    // PUT YOUR CODE HERE TO HANDLE THE 3 cases
    //
    // 1) The virtual page is already in a physical page
    //
    // 2) The virtual page is not in a physical page,
    //    and there is free physical page
    //
    // 3) The virtual page is not in a physical page,
    //    and there is no free physical page
    //
    // don't forgot to update the last_access_time of the virtual_page

    printf("Time %d: virtual page %d accessed\n", access_time, virtual_page);
}

Note that the fourth argument, struct ipt_entry *ipt, is a pointer to the inverted page table. It can be effectively indexed as an array, e.g. ipt[0] is the first entry.

You can complete the lab by adding code to this function (you are also free to write your own program from scratch if you prefer).

When you think your program is working, you can use autotest to run some simple automated tests:

1521 autotest lru 

mkdir addr_translation
cd addr_translation
1521 fetch addr_translation

You have been provided a stub C program, addr_translation.c, as follows.

Your task is to add code to this function in addr_translation.c:

uint32_t translate_address(HashMap page_table, uint32_t virtual_address) {
    // TODO: Implement me!
    return 42;
}

Add code to the function addr_translation so that, given a uint32_t virtual address, it returns the corresponding uint32_t physical address.

The code in addr_translation_main.c will read from a file containing page table entries, and will load these entries into a hash map data structure. You aren't required to understand how this works, but you will need to make use of the hashmap_get function defined in addr_translation.h in order to retrieve the page table entry for a given virtual page number.

The function will return a struct page_table_entry, also defined in addr_translation.h. This structure contains the physical frame number, and a boolean indicating whether the page is valid or not. If the page is not valid, the function should return INVALID_ADDRESS. If there is no entry in the page table for the given virtual page number, hashmap_get will return NULL, and you should also return INVALID_ADDRESS.

Virtual addresses are structured so that the top 20 bits are the virtual page number, and the bottom 12 bits are the offset within the page.

Physical addresses are structured identically, except the top 20 bits are the physical frame number instead of the virtual page number.

Your goal is to use bitwise operations to extract the virtual page number from the virtual address, and then use the page table to find the physical page number. You should then combine the physical frame number with the offset to form the physical address. For example:

unzip examples.zip
... extracting ...
dcc -o addr_translation addr_translation.c addr_translation_hashmap.c addr_translation_main.c
cat examples/page_table_small.vpt
0 0xcd5f8
1 0x7156f 0x43d5b
1 0x3506f 0x1d2a4
1 0xe33be 0xa8ba0
1 0x0cb02 0xda99b
0 0x698d4
./addr_translation examples/page_table_small.vpt
0x7156ffff
0x43d5bfff
0x7156efff
0x00000000
0xcd5f8340
0x00000000
0x0cb02e8a
0xda99be8a

When you think your program is working, you can use autotest to run some simple automated tests:

1521 autotest addr_translation