aboutsummaryrefslogtreecommitdiff
path: root/pa8_predict/pager-predict.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-04-26 12:14:41 -0600
committerJack Sangdahl <[email protected]>2024-04-26 12:14:41 -0600
commita4f877ffdc6bc802490f2998f7e7b226be2c7bfa (patch)
tree36353dbda99d8de36b831592997dfd15eb4a5b6d /pa8_predict/pager-predict.c
parent3c8bb65459ca0d8c5fac591977d92d074ab44d88 (diff)
downloadcsci3753-a4f877ffdc6bc802490f2998f7e7b226be2c7bfa.tar.gz
csci3753-a4f877ffdc6bc802490f2998f7e7b226be2c7bfa.zip
pa8
Diffstat (limited to 'pa8_predict/pager-predict.c')
-rw-r--r--pa8_predict/pager-predict.c180
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