1

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

16916
62493
30198
53683
40185
28781
24462
48399
64815
18295
12218
22760
57982
27966
54894
38929
32865
64243
2315
64454
55041
18633
14557
61006
62615
7591
64747
6727
32315
60645
6308
45688
969
40891
49294
41118
21395
6091
32541
17665
3784
28718
59240
40178
60086
42252
44770
22514
3067
15757
31649
10842
43765
33405
44954
56657
5003
50227
19358
36529
10392
58882
5129
58554
58584
27444
58982
51476
6796
21311
30705
28964
41003
20259
57857
63258
36374
692
43121
48128
34561
49213
36922
59162
50552
17866
18145
3884
54388
42932
46919
58892
8620
38336
64357
23387
42632
15913
15679
22501
37540
5527
63921
62716
32874
64390
63101
61802
19648
29031
44981
28092
9448
44744
61496
31453
60746
12199
62255
21793
26544
14964
41462
56089
52038
47982
59484
50924
6942
34998
27069
51926
60645
43181
10559
4664
28578
59516
38912
63562
64846
62938
27194
28804
61703
10998
6596
37721
43430
22692
62971
47125
52521
34646
32889
13055
65416
62869
57314
12659
14052
32956
49273
50352
49737
15555
47475
15328
34621
51365
32820
48855
12224
2035
60539
14595
13853
24143
15216
8113
22640
32978
39151
19520
58141
63959
53040
55842
585
51229
64181
54879
28210
10268
15395
12884
2149
53483
59606
14981
36672
23197
36518
13361
19810
25955
62678
26021
29409
38111
58573
56840
41306
54426
3617
50652
41452
20241
31723
53747
28550
23402
21205
56181
57470
39933
34964
24781
41747
62564
58461
20858
49301
40572
23840
35278
62905
56650
11149
38920
23430
57592
3080
6677
50704
51883
62799
20188
1245
12220
17602
28609
42694
29826
13827
27336
53343
11533
41713
33890
4894
57599
3870
58622
29780
62553
2303
51915
6251
38107
59325
61295
26699
51188
59519
7345
20325
39633
1562
7580
8170
62256
35823
27790
13191
9772
7477
44455
59546
49347
36539
12453
49640
28290
44817
8565
16399
41934
45457
33856
19498
17661
63829
42034
28928
30711
8800
52335
38775
52704
24380
19602
57998
2919
8362
17884
45737
47894
59667
10385
52782
64416
40946
16778
27159
24324
32450
9108
65305
19575
11117
65170
58013
61676
63510
17458
54675
1713
55105
65321
45278
26256
64198
29441
1928
39425
32000
28549
46295
22772
58228
63525
32602
46195
55849
46454
7487
33879
42004
8599
18641
49015
26830
34754
14668
38362
38791
4171
45975
14623
62393
64658
10963
9058
51031
32425
45483
44611
63664
54920
7663
56480
1489
28438
65449
12441
58530
63570
26251
15972
35826
5491
54253
49655
5868
20163
51079
21398
32756
64196
43218
21583
25086
45515
12893
22914
58969
20094
13730
44059
28931
13533
33134
28483
1220
38174
53502
43328
4970
8090
2661
53903
11025
26627
18117
14505
61528
20423
26962
36392
11365
50882
41668
30497
36216
5619
36983
59557
36663
36436
37057
23585
58791
46666
64475
21615
41090
1771
47513
39338
1390
38772
58149
7196
9123
7491
62616
15436
17491
53656
26449
34935
19864
51388
15155
64775
47969
16315
1342
51185
6043
21398
3273
9370
35463
28205
2351
28999
47699
46870
22311
22124
22427
49344
23224
5514
20504
376
2014
38700
13098
62435
48046
63464
12798
51178
8627
27083
47198
44021
32792
43996
41126
64244
37047
60281
52904
7768
55359
3230
44813
4116
65222
28083
60660
39
328
47868
13009
22378
39304
11171
8079
52879
5123
4356
45745
32952
4657
24142
23319
13607
46304
17677
59691
50967
7817
8545
55297
52954
39720
18455
30349
63270
27156
20614
19372
48689
49386
50584
51936
34705
13653
50077
54518
41482
4169
36118
9584
18490
55420
5708
23506
15391
36368
38976
50406
49236
65035
30120
62551
46809
21687
53839
2098
12364
45366
50437
36675
55382
11846
49127
19900
20554
19219
51483
58090
39074
16060
10447
54169
20634
57555
61210
269
33154
64487
61223
47292
21852
5281
45912
32532
63067
41683
20981
33881
41785
4580
41389
28572
782
30273
62267
17922
63238
3308
26545
44395
39120
21706
7144
30244
3725
54632
30574
8473
12386
41114
57930
15341
15598
59922
18226
48162
41250
1512
2546
41682
322
880
20891
56604
40166
26791
44560
38698
64127
15028
38669
45637
43151
9465
2498
13978
16326
51442
34845
63667
39370
55671
64496
7767
6283
55884
61103
10184
39543
9555
13963
58975
19537
6101
41421
45502
29328
8149
25450
58944
50666
23084
36468
33645
25002
53715
60173
46354
4708
28208
58844
22173
8535
42261
29687
37799
22566
62520
4098
47999
49660
37063
41856
5417
48856
10682
22370
63281
62452
50532
9022
59300
58660
56401
8518
63066
63250
48592
28771
37673
60776
56438
60424
39993
56004
59002
33982
25498
57047
1401
15130
42960
61827
32442
64304
30273
38082
22404
3808
16883
23111
62417
60364
4542
14829
44964
33924
2141
19245
47168
24048
1022
23075
24888
49247
4900
22656
34117
55555
48947
59533
21312
21415
813
19419
1999
20155
21521
13670
19289
58483
41318
16151
13611
21514
13499
45583
49013
64843
63485
38697
59188
24593
57641
36524
56980
36810
6096
11070
60124
37576
15096
45247
32783
58390
60873
23719
24385
22307
17375
15990
20526
25904
42224
9311
7862
3835
30535
65179
57387
63579
4946
9037
61033
55543
50361
6480
14042
21531
39195
37511
23696
27440
28201
23072
7814
6552
43637
35113
34890
61297
45633
61431
46032
18774
62991
28059
35229
51230
14405
52242
43153
2709
47963
36943
54066
10054
43051
11525
17684
41681
27883
56909
45772
27496
46842
38734
28972
59684
11384
21018
2192
18384
13464
31018
62958
30611
1913
18904
26773
55491
21899
64413
47134
23172
7262
12705
7522
58815
34916
3802
58008
1239
63947
381
60734
48769
41938
38025
55099
56691
39530
59003
6029
20920
8077
42633
17443
53570
22833
3782
47758
22136
22427
23867
59968
62166
6972
63684
46388
41942
36524
9323
31114
22345
46463
54671
9214
7257
33150
41565
26214
3595
17932
34660
51961
58634
57990
28848
49920
18351
53669
33996
6741
64098
606
27383
63140
32228
63437
29085
65080
38753
16041
9041
42090
46388
63650
36636
21947
19833
36464
8541
12712
48955
39206
15578
49205
7731
43046
60498
9237
47706
43973
42008
27460
24999
51933
34070
65155
59955
9277
20420
44860
50992
10583
57751
23195
27227
42816
58219
37606
18426
21238
11983
48394
11036
30557
23453
49847
30032
48065
6957
2301
7736
31260
17071
8940
9929
45563
12107

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

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

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

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

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

我还没有完成价格

4

1 回答 1

0

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

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


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

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

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

您需要添加:

frame = 0;

getline循环的顶部。

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


为什么我的点击停止在 17

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

此外,您在 TLB 数组中搜索了两次相同的页面值。那是因为您使用posTLB 索引,但重用该变量来索引页表。使用不同的名称(例如)tlbpospagepos. 然后,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
于 2021-05-02T00:56:57.417 回答