虚拟内存管理器使用 TLB 和页面 table 将逻辑地址转换为物理地址

Question

我的程序的目标是获取一个包含 1000 个逻辑地址的列表

并将它们转换为物理地址，首先获取页面和偏移量，然后使用 TLB 和 page_table，首先我需要搜索 tlb，如果有匹配增量命中，如果没有，则搜索page_table 如果两者都没有命中获取帧，则为页面错误，并增加页面错误如果出现页面错误，则必须查看名为 BACKING_STORE.bin 的文件并使用 fseek、fread 获取与逻辑地址页面匹配的 256 字节页面并将其读入，获取帧号并进行翻译对于物理，TLB 最多有 16 个条目，使用移位我只是将所有内容向右移动页面 table 有 256 个最大条目

根据列表，应该有 244 个页面错误和 54 个 TLB 命中，

现在开始我的问题，我花了一天半的时间解决这个问题

当我只是传递帧值时，正如您在上面的代码中看到的那样，我不认为这里的每个帧值都应该是 16，但我不确定这是从哪里来的我不确定错误的原因在哪里，做了很多实验都没有这样的运气，我真的需要一双新的眼睛，为此

为什么我的点击停止在 17 为什么当应该有 244 个页面错误时却只有 36

我还没有完成费率

Answer 1

based on the list there should be 244 page faults and 54 TLB hits,

有很多问题导致没有发生这种情况。

when there should be 244 page faults there's only 36

在你的外部 getline 循环中，在第一次迭代之后，子循环将不被执行，因为 if (frame == 0) 语句将为假，并且永远不会搜索 TLB、页面 tables 和后备存储。

换句话说，在后续迭代中，您将重复使用先前迭代中的陈旧 frame 值。

您需要添加：

frame = 0;

在 getline 循环的顶部。

通过该更改，我得到 244 个页面错误而不是 [更改前的 36 个]。

why is my hits stopping at 17

在查找 fill/reuse 的 TLB 条目时，您没有进行任何 LRU 选择。而且，如果所有条目都已满，则您正在“滑动”数组以腾出空间。这非常缓慢并且非常值得怀疑（例如，真正的 TLB H/W 没有时间这样做）。

此外，您在 TLB 数组中搜索了两次相同的页值。那是因为您使用 pos 作为 TLB 索引，但重用该变量来索引页面 table。使用不同的名称（例如）tlbpos 和 pagepos。然后，tlbpos 将保持有效，您可以省略第 2 次 TLB 扫描循环。

如果没有 LRU，一个简单的策略是通过页码对 TLB 大小取模来索引 TLB。这就是大多数“真实的”H/W 以某种形式所做的事情。它类似于具有 TLB_SIZE 个哈希桶，但每个桶只有一个个槽。

通过这种方式进行索引，这意味着您 而不是 必须在 TLB 数组上循环。

这样做会将 TLB 命中数增加到 53。

page_table 递增没有限制，所以你可以溢出 page_table_* 数组（即 UB？）。您可能需要：page_table %= PAGE_SIZE; 在递增之后或以其他方式回收条目并防止溢出。

您看不到这一点的原因是测试数据的性质和条目数。使用不同的数据 and/or 更多条目，这将是一个真正的问题。

此外，您使用的 frame 值 0 表示“无效”。这对于第 0 页可能不太有效。因此，我将使用 -1 来指定无效。

旁注：您没有指定后备存储文件的数据或如何创建它。但是，对于您的模拟，它可能不相关，因为我们实际上并不关心给定位置的 data。出于测试目的，任何现有文件都可以，即使是空文件。

我重构了您的代码以合并这些更改。

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>
#include <stdbool.h>
#include <unistd.h>
#include <errno.h>

#define PAGES 256
#define PAGE_SIZE 256
#define MEMORY_SIZE pages * page_size
#define TLB_SIZE 16
#define BACKING_STORE_PAGE 256

#define INVALID     -1

// Array intializations (to be edited?)
// TLB arrays
int TLB[TLB_SIZE];
int TLB_frame[TLB_SIZE];

// useless arrays
int memory[PAGES][PAGES];
char holder[PAGES];

// Page table arrays
int page_table_page[PAGE_SIZE];
int page_table_frame[PAGE_SIZE];

// variable intializations (most possibly useless?)
int hits = 0;
int pagefaults = 0;
int page_table_entrys = 0;
int page_table = 0;
int frame_table = 0;
int translated_pages = 0;
int TLB_entrys = 0;
int rate = 0;
int TLB_rate = 0;
int TLBFrame = 0;
int frame = 0;                          // frame value holder var
int pagepos;
int tlbpos;
char *address;
int page = 0;
int offset = 0;
size_t size = 0;                        // filler variable;
int eof = 0;                            // end of file;

void insertTLB(int pages, int frames);

int
main(int argc, char **argv)
{

    if (argc != 3) {
        printf("Usage: <address_list> <backing_store_file>\n");
        exit(1);
    }

    FILE *addresses = fopen(argv[1], "r");
    if (addresses == NULL) {
        printf("Unable to open '%s' -- %s\n",argv[1],strerror(errno));
        exit(1);
    }

    FILE *BACKING_STORE = fopen(argv[2], "rb");
    if (BACKING_STORE == NULL) {
        printf("Unable to open '%s' -- %s\n",argv[2],strerror(errno));
        exit(1);
    }

    for (tlbpos = 0;  tlbpos < TLB_SIZE;  ++tlbpos) {
        TLB[tlbpos] = INVALID;
        TLB_frame[tlbpos] = INVALID;
    }

    for (pagepos = 0;  pagepos < PAGE_SIZE;  ++pagepos) {
        page_table_page[pagepos] = INVALID;
        page_table_frame[pagepos] = INVALID;
    }

    while (eof = getline(&address, &size, addresses) != EOF) {
        page = atoi(address) / 256;
        offset = atoi(address) % 256;

#if 1
        frame = INVALID;
#endif

        // get index into TLB
        tlbpos = page % TLB_SIZE;

        // checks TLB for match if match, increase hit
        if (TLB[tlbpos] == page) {
            frame = TLB_frame[tlbpos];
            hits++;
        }

        // check here to see if frame had a match, shoud be 0 if there was not
        if (frame == INVALID) {
            // this is checking the page table for a match
            for (pagepos = 0; pagepos < page_table; pagepos++) {
                // if there is a page match in to the page retrieved, get frame at pos
                if (page_table_page[pagepos] == page) {
                    frame = page_table_frame[pagepos];
                }
            }
        }

        // still no change? BACKING_STORE
        if (frame == INVALID) {
            // move to pos of page
            if (fseek(BACKING_STORE, page * BACKING_STORE_PAGE, SEEK_SET) != 0) {
                printf("error in finding\n");
            }
            // get page in char size, im thinking 1 byte = 1 char
            if (fread(holder, sizeof(signed char), BACKING_STORE_PAGE, BACKING_STORE) == 0) {
                printf("error in reading the data\n");
            }

            for (pagepos = 0; pagepos < BACKING_STORE_PAGE; pagepos++) {
                memory[frame_table][pagepos] = holder[pagepos];
            }

            page_table_page[page_table] = page;
            page_table_frame[page_table] = frame_table;
            frame_table++;

            page_table++;
            page_table %= PAGE_SIZE;

            pagefaults++;
        }

        // (re)insert into TLB
        TLB[tlbpos] = page;
        TLB_frame[tlbpos] = frame;

        translated_pages++;
        printf("virtual address %s physical address %d\n", address, frame);

    }
    printf("translated pages %d\n", translated_pages);
    printf("page faults %d\n", pagefaults);
    printf("page fault rate: %d\n", rate);
    printf("TLB hits %d\n", hits);
    printf("TLB fault rate: %d\n", TLB_rate);
    fclose(addresses);
    fclose(BACKING_STORE);
}

这是程序的部分输出：

translated pages 982
page faults 244
page fault rate: 0
TLB hits 53
TLB fault rate: 0

更新：

我提出的上述 TLB 算法使用 simple/constant 索引 [作为哈希]。每个哈希桶只有一个槽。它似乎解决了您提出的问题。

我不确定这里的术语。

但是，我认为算法是“直接”映射的。

Some/most H/W 使用“N 路集合关联”模型。

我重构了代码以实现真正的哈希 table 查找，并且 TLB 命中数已上升到 228。

这是使用 4 路缓存，LRU 替换。

无论如何，这是代码：

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>
#include <stdbool.h>
#include <unistd.h>
#include <errno.h>

#define PAGES 256
#define PAGE_SIZE 256
#define MEMORY_SIZE pages * page_size
#define BACKING_STORE_PAGE 256

#if 1
#define TLB_WAYS    4
#define TLB_SIZE    16
#else
#define TLB_WAYS    4
#define TLB_SIZE    (16 / TLB_WAYS)
#endif

#define INVALID     -1

typedef struct {
    int tlb_page;
    int tlb_frame;
    unsigned int tlb_tlat;
} tlbent_t;

typedef struct {
    tlbent_t tlb_ways[TLB_WAYS];
} tlbset_t;

// Array intializations (to be edited?)
// TLB arrays
tlbset_t TLB[TLB_SIZE];

// useless arrays
int memory[PAGES][PAGES];
char holder[PAGES];

// Page table arrays
int page_table_page[PAGE_SIZE];
int page_table_frame[PAGE_SIZE];

// variable intializations (most possibly useless?)
int hits = 0;
int pagefaults = 0;
int page_table_entrys = 0;
int page_table = 0;
int frame_table = 0;
int translated_pages = 0;
int TLB_entrys = 0;
int rate = 0;
int TLB_rate = 0;
int TLBFrame = 0;
int frame = 0;                          // frame value holder var
int pagepos;
int tlbpos;
char *address;
int page = 0;
int offset = 0;
size_t size = 0;                        // filler variable;
int eof = 0;                            // end of file;
int hitnow = 0;
int way;

tlbset_t *tlbset;
tlbent_t *tlbent;

unsigned int curtime = 1;

void insertTLB(int pages, int frames);

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

    if (argc != 3) {
        printf("Usage: <address_list> <backing_store_file>\n");
        exit(1);
    }

    FILE *addresses = fopen(argv[1], "r");
    if (addresses == NULL) {
        printf("Unable to open '%s' -- %s\n",argv[1],strerror(errno));
        exit(1);
    }

    FILE *BACKING_STORE = fopen(argv[2], "rb");
    if (BACKING_STORE == NULL) {
        printf("Unable to open '%s' -- %s\n",argv[2],strerror(errno));
        exit(1);
    }

    for (tlbpos = 0;  tlbpos < TLB_SIZE;  ++tlbpos) {
        tlbset = &TLB[tlbpos];
        for (way = 0;  way < TLB_WAYS;  ++way) {
            tlbent = &tlbset->tlb_ways[way];
            tlbent->tlb_page = INVALID;
            tlbent->tlb_frame = INVALID;
            tlbent->tlb_tlat = 0;
        }
    }

    for (pagepos = 0;  pagepos < PAGE_SIZE;  ++pagepos) {
        page_table_page[pagepos] = INVALID;
        page_table_frame[pagepos] = INVALID;
    }

    while (eof = getline(&address, &size, addresses) != EOF) {
        page = atoi(address) / 256;
        offset = atoi(address) % 256;

#if 1
        frame = INVALID;
#endif

        tlbpos = page % TLB_SIZE;
        tlbset = &TLB[tlbpos];

        // checks TLB for match if match, increase hit
        hitnow = 0;
        for (way = 0;  way < TLB_WAYS;  ++way) {
            tlbent = &tlbset->tlb_ways[way];
            if (tlbent->tlb_page == page) {
                frame = tlbent->tlb_frame;
                hits++;
                hitnow = 1;
                break;
            }
        }

        // check here to see if frame had a match, shoud be 0 if there was not
        if (frame == INVALID) {
            // this is checking the page table for a match
            for (pagepos = 0; pagepos < page_table; pagepos++) {
                // if there is a page match in to the page retrieved, get frame at pos
                if (page_table_page[pagepos] == page) {
                    frame = page_table_frame[pagepos];
                }
            }
        }

        // still no change? BACKING_STORE
        if (frame == INVALID) {
            // move to pos of page
            if (fseek(BACKING_STORE, page * BACKING_STORE_PAGE, SEEK_SET) != 0) {
                printf("error in finding\n");
            }
            // get page in char size, im thinking 1 byte = 1 char
            if (fread(holder, sizeof(signed char), BACKING_STORE_PAGE, BACKING_STORE) == 0) {
                printf("error in reading the data\n");
            }

            for (pagepos = 0; pagepos < BACKING_STORE_PAGE; pagepos++) {
                memory[frame_table][pagepos] = holder[pagepos];
            }

            page_table_page[page_table] = page;
            page_table_frame[page_table] = frame_table;
            frame_table++;

            page_table++;
            page_table %= PAGE_SIZE;

            pagefaults++;
        }

        // insert into tLB hopefully going to the beginning if full
        // check to see if its already in the TLB
        do {
            if (hitnow)
                break;

            unsigned int tlatbest = 0xFFFFFFFF;
            tlbent_t *tlbuse = NULL;

            for (way = 0;  way < TLB_WAYS;  ++way) {
                tlbent = &tlbset->tlb_ways[way];
                if ((tlbent->tlb_tlat < tlatbest) || (way == 0)) {
                    tlatbest = tlbent->tlb_tlat;
                    tlbuse = tlbent;
                }
            }

            tlbent = tlbuse;
        } while (0);

        tlbent->tlb_page = page;
        tlbent->tlb_frame = frame;
        tlbent->tlb_tlat = ++curtime;

        translated_pages++;
        printf("virtual address %s physical address %d\n", address, frame);

    }
    printf("translated pages %d\n", translated_pages);
    printf("page faults %d\n", pagefaults);
    printf("page fault rate: %d\n", rate);
    printf("TLB hits %d\n", hits);
    printf("TLB fault rate: %d\n", TLB_rate);
    fclose(addresses);
    fclose(BACKING_STORE);
}

这是部分输出：

translated pages 982
page faults 244
page fault rate: 0
TLB hits 228
TLB fault rate: 0

虚拟内存管理器使用 TLB 和页面 table 将逻辑地址转换为物理地址

virtual memory manager convert logical to phyiscal address useing TLB and page table

c

arrays

logic-error