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

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

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

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

现在谈谈我的问题，我花了一天半的时间在上

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

为什么我的命中率在17分停止为什么当应该有244个页面错误时，只有36个

我还没有做利率

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

有许多问题导致了这不是发生的原因。

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

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

换句话说，在后续迭代中，您正在重用上一次循环中过时的frame值。

您需要添加：

frame = 0;

在CCD_ 4循环的顶部。

有了这个改变，我得到了244页错误，而不是[改变前]36页。

为什么我的命中率停在17

在查找要填充/重用的TLB条目时，不进行任何LRU选择。并且，如果所有条目都已满，则您是"；滑动"；阵列以腾出空间。这是非常缓慢且高度可疑的(例如，真正的TLB H/W没有时间这样做)。

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

在没有LRU的情况下，一个简单的策略是通过页面编号模化TLB大小来索引到TLB。这是最"；真实的"；H/W在某种形式上是这样做的。它类似于拥有TLB_SIZE散列桶，但每个桶只有一个槽。

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

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

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

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

此外，您正在使用frame值0来指示"；无效"；。这可能不适用于页面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' -- %sn",argv[1],strerror(errno));
exit(1);
}
FILE *BACKING_STORE = fopen(argv[2], "rb");
if (BACKING_STORE == NULL) {
printf("Unable to open '%s' -- %sn",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 findingn");
}
// 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 datan");
}
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 %dn", address, frame);
}
printf("translated pages %dn", translated_pages);
printf("page faults %dn", pagefaults);
printf("page fault rate: %dn", rate);
printf("TLB hits %dn", hits);
printf("TLB fault rate: %dn", 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路集合相联"；模型

我重构了代码以实现真正的哈希表查找，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' -- %sn",argv[1],strerror(errno));
exit(1);
}
FILE *BACKING_STORE = fopen(argv[2], "rb");
if (BACKING_STORE == NULL) {
printf("Unable to open '%s' -- %sn",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 findingn");
}
// 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 datan");
}
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 %dn", address, frame);
}
printf("translated pages %dn", translated_pages);
printf("page faults %dn", pagefaults);
printf("page fault rate: %dn", rate);
printf("TLB hits %dn", hits);
printf("TLB fault rate: %dn", TLB_rate);
fclose(addresses);
fclose(BACKING_STORE);
}

这是部分输出：

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

相关内容

最新更新

热门标签：