arraysclogic-error

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


the goal of my program is to take a list of 1000 logical addresses

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

and convert them to there phyiscal addresses, first get page and offset and then using a TLB and page_table, first i need to search the tlb and if theres a match increment hit, if not, search the page_table and if theres a hit get frame if not in both, its a page fault, and increment page faults if a page fault results, you must then look through a file called BACKING_STORE.bin and using fseek, fread, get the 256 byte page that matches with the page of the logical address and read it in, get the frame number and translate to phyiscal, the TLB has a maximum of 16 entrys and using a shift i just shift everything to the right the page table has 256 max entrys

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

now onto my problem, which ive spent a good day and a half being stuck on

and when I just pass the frame value as you can see in code above, i dont think every frame value here is supposed to be 16, but I'm not sure where that is coming from and im unsure as to where the cause, of the error is, been doing a lot of experimenting to no such luck, I just really need a fresh set of eyes, for this

why is my hits stopping at 17 why when there should be 244 page faults there's only 36

I haven't done the rates yet


Solution

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

    There are a number of issues contributing to why this is not happening.


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

    In your outer getline loop, after the first iteration, the subloops will not be executed because the if (frame == 0) statements will be false and the TLB, page tables, and backing store will never be searched.

    In other words, on subsequent iterations, you're reusing a stale frame value from the prior iteration.

    You need to add:

    frame = 0;
    

    at the top of the getline loop.

    With that change, I get 244 page faults instead of 36 [before the change].


    why is my hits stopping at 17

    You don't do any LRU selection when looking for a TLB entry to fill/reuse. And, if all entries are full, you are "sliding" the array to make room. This is very slow and is highly suspect (e.g. real TLB H/W can't afford the time to do this).

    Also, you're searching the TLB array twice for the same page value. That's because you use pos for the TLB index but reuse that variable for indexing into the page table. Use different names (e.g.) tlbpos and pagepos. Then, tlbpos will remain valid and you can omit the 2nd TLB scan loop.

    Without LRU, a simple strategy is to index into the TLB by page number modulo the TLB size. That's what most "real" H/W does in some form. It's similar to having TLB_SIZE hash buckets but only one slot per bucket.

    By indexing in this way, it means you do not have to loop on the TLB array at all.

    Doing this increases the number of TLB hits to 53.


    page_table increments without limit, so you can overflow page_table_* arrays (i.e. UB?). You may need: page_table %= PAGE_SIZE; after the increment or some other way to reclaim entries and prevent overflow.

    The reason you're not seeing this is because of the nature and number of entries of your test data. With different data and/or more entries this will be a real problem.

    Also, you are using a frame value of 0 to indicate "invalid". That may not work too well for page 0. So, I'd use -1 to designate invalid.

    Side note: You don't specify data for the backing store file or how to create it. But, for your simulation, it may not be relevant because we don't actually care about the data at a given location. For test purposes, any existing file will do, even an empty one.


    I've refactored your code to incorporate these changes.

    #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);
    }
    

    Here is the partial output from the program:

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

    UPDATE:

    The above TLB algorithm I came up with uses a simple/constant index [as a hash]. It has only one slot per hash bucket. It seems to solve your stated issues.

    I'm not sure of the terminology here.

    But, I think that algorithm is "direct" mapped.

    Some/most H/W uses an "N-way set associative" model.

    I've refactored the code to implement a true hash table lookup, and the number of TLB hits has gone up to 228.

    This is using a 4-way cache, with LRU replacement.

    Anyway, here's the code:

    #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);
    }
    

    Here's the partial output:

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