diff options
author | Jack Sangdahl <[email protected]> | 2024-04-26 12:14:41 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-04-26 12:14:41 -0600 |
commit | a4f877ffdc6bc802490f2998f7e7b226be2c7bfa (patch) | |
tree | 36353dbda99d8de36b831592997dfd15eb4a5b6d /pa8_predict/pager-predict.c | |
parent | 3c8bb65459ca0d8c5fac591977d92d074ab44d88 (diff) | |
download | csci3753-a4f877ffdc6bc802490f2998f7e7b226be2c7bfa.tar.gz csci3753-a4f877ffdc6bc802490f2998f7e7b226be2c7bfa.zip |
pa8
Diffstat (limited to 'pa8_predict/pager-predict.c')
-rw-r--r-- | pa8_predict/pager-predict.c | 180 |
1 files changed, 180 insertions, 0 deletions
diff --git a/pa8_predict/pager-predict.c b/pa8_predict/pager-predict.c new file mode 100644 index 0000000..6b19eb3 --- /dev/null +++ b/pa8_predict/pager-predict.c @@ -0,0 +1,180 @@ +// Jack Sangdahl +// CSCI3753 SP24 +// PA8 Predict +#include "simulator.h" +#include <stdbool.h> + +#define LOWER_BOUND 0.00001 +#define UPPER_BOUND 0.5 + +int predict_prev(int proc, int page, + int prev[MAXPROCESSES][MAXPROCPAGES][MAXPROCPAGES]) { + int prediction = -1, most_frequent = 0; + for (int i = 0; i < MAXPROCPAGES; i++) + if (prev[proc][page][i] > most_frequent) { + most_frequent = prev[proc][page][i]; + prediction = i; + } + return prediction; +} + +#pragma GCC push_options +#pragma GCC optimize("-O3") + +void pageit(Pentry q[MAXPROCESSES]) { + static bool initialised = false; + static double fault_freq[MAXPROCESSES]; + static int tick = 1, timestamps[MAXPROCESSES][MAXPROCPAGES], + prev[MAXPROCESSES][MAXPROCPAGES][MAXPROCPAGES], + allocate[MAXPROCESSES], frame_cnt[MAXPROCESSES], + fault_cnt[MAXPROCESSES], hit_cnt[MAXPROCESSES], + prev_pc[MAXPROCESSES][MAXPROCPAGES], + curr_pc[MAXPROCESSES][MAXPROCPAGES], + prev_status[MAXPROCESSES][MAXPROCPAGES][MAXPROCPAGES] = {{{0}}}; + int proc, pc, page, proc_running = 0, running[MAXPROCESSES], flag = 1, + total_pages = 0, total_allocated = 0; + + if (!initialised) { + for (int i = 0; i < MAXPROCESSES; i++) { + fault_freq[i] = 0; + allocate[i] = 5; + frame_cnt[i] = 0; + fault_cnt[i] = 0; + hit_cnt[i] = 0; + for (int j = 0; j < MAXPROCPAGES; j++) { + timestamps[i][j] = 0; + prev_pc[i][j] = 0; + curr_pc[i][j] = 0; + for (int k = 0; k < MAXPROCPAGES; k++) + prev[i][j][k] = 0; + } + } + initialised = true; + } + + for (int i = 0; i < MAXPROCESSES; i++) + if (q[i].active) { + running[proc_running] = i; + proc_running++; + } else { + allocate[i] = 0; + for (int j = 0; j < MAXPROCPAGES; j++) + if (q[i].pages[j]) + pageout(i, j); + } + + if (!proc_running) + return; + if (proc_running <= 7) + flag = 0; + for (int i = 0; i < proc_running; i++) { + proc = running[i]; + pc = q[proc].pc; + page = pc / PAGESIZE; + if (!curr_pc[proc][page]) { + prev_pc[proc][page] = pc; + curr_pc[proc][page] = 1; + for (int j = 0; j < MAXPROCPAGES; j++) + prev_status[proc][page][j] = q[proc].pages[page] ? 1 : 0; + } + for (int i = 0; i < MAXPROCPAGES; i++) + if (curr_pc[proc][i] && pc >= prev_pc[proc][i] + 170) { + curr_pc[proc][i] = 0; + prev[proc][i][page]++; + if (pc == prev_pc[proc][i] + 170) + prev[proc][i][page]++; + for (int j = 0; j < MAXPROCPAGES; j++) { + if (prev_status[proc][i][j] && !q[proc].pages[j] && j != page) + prev[proc][i][j]--; + if (pc == prev_pc[proc][i] + 170) + prev[proc][i][j]--; + } + } + for (int i = 0; i < MAXPROCPAGES; i++) + timestamps[proc][i]++; + timestamps[proc][page] = 0; + if (flag) { + for (int i = 0; i < MAXPROCESSES; i++) { + frame_cnt[i] = 0; + for (int j = 0; j < MAXPROCPAGES; j++) + if (q[i].pages[j]) + frame_cnt[i]++; + total_pages += frame_cnt[i]; + total_allocated += allocate[i]; + } + for (int i = 0; i < MAXPROCESSES; i++) + if (fault_freq[i] < LOWER_BOUND) + if (frame_cnt[i] < allocate[i] && allocate[i] >= 5) { + allocate[i]--; + total_allocated--; + } + + if (total_allocated < PHYSICALPAGES) { + int i = 0; + while (total_allocated < PHYSICALPAGES && i < MAXPROCESSES) { + if (fault_freq[i] >= UPPER_BOUND && allocate[i] < 14) { + allocate[i]++; + total_allocated++; + } else if (fault_freq[i] > UPPER_BOUND / 2 && allocate[i] < 10) { + allocate[i]++; + total_allocated++; + } else if (allocate[i] < 8) { + allocate[i]++; + total_allocated++; + } + i++; + } + } + } + if (q[proc].pages[page]) { + hit_cnt[proc]++; + fault_freq[proc] = (double)fault_cnt[proc] / hit_cnt[proc]; + continue; + } else { + fault_cnt[proc]++; + fault_freq[proc] = + hit_cnt[proc] ? (double)fault_cnt[proc] / hit_cnt[proc] : UPPER_BOUND; + if (!flag && pagein(proc, page)) + continue; + else if (flag && frame_cnt[proc] < allocate[proc] && pagein(proc, page)) + continue; + else if (flag && total_pages < PHYSICALPAGES && + total_allocated < PHYSICALPAGES && pagein(proc, page)) { + allocate[proc]++; + continue; + } else { + int evict_page = -1, lru = -10; + for (int i = 0; i < MAXPROCPAGES; i++) + if (q[proc].pages[i] && prev[proc][page][i] < lru && i != page) { + evict_page = i; + pageout(proc, evict_page); + } + if (evict_page == -1) { + for (int i = 0; i < MAXPROCPAGES; i++) { + if (!q[proc].pages[i]) + continue; + if (timestamps[proc][i] > lru) { + lru = timestamps[proc][i]; + evict_page = i; + } + } + pageout(proc, evict_page); + } + } + } + } + for (int i = 0; i < proc_running; i++) { + proc = running[i]; + pc = q[proc].pc; + page = pc / PAGESIZE; + int page_predict = predict_prev(proc, page, prev); + if (page_predict == -1 || page_predict == page) + continue; + if (q[proc].pages[page_predict]) + continue; + pagein(proc, page_predict); + } + tick++; +} + +#pragma GCC pop_options |