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

Question

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

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

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

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

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

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

我还没有完成价格

score 0 · Accepted Answer

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

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

当应该有 244 个页面错误时，只有 36 个

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

换句话说，在随后的迭代中，您正在重用先前迭代中的陈旧frame值。

您需要添加：

frame = 0;

在getline循环的顶部。

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

为什么我的点击停止在 17

在查找要填充/重用的 TLB 条目时，您不会进行任何 LRU 选择。而且，如果所有条目都已满，则您正在“滑动”数组以腾出空间。这是非常缓慢的并且是高度怀疑的（例如，真正的 TLB H/W 没有时间来做这件事）。

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

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

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

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

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

您没有看到这一点的原因是您的测试数据的性质和条目数量。对于不同的数据和/或更多条目，这将是一个真正的问题。

此外，您使用frame0 值表示“无效”。这对于第 0 页可能不太适用。所以，我会使用 -1 来指定无效。

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

我已经重构了您的代码以包含这些更改。

#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 算法使用简单/常量索引 [作为哈希]。每个哈希桶只有一个插槽。它似乎解决了您提出的问题。

我不确定这里的术语。

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

一些/大多数 H/W 使用“N-way set associative”模型。

我重构了代码以实现真正的哈希表查找，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

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

1 回答 1

Related

Reference