aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-14 22:55:52 -0700
committerJack Sangdahl <[email protected]>2024-11-14 22:55:52 -0700
commitb6d0f307fb61884c60a7aa0bc46f0a88c6ca4fab (patch)
treea449caf78c54e71a5f5961cbac37a02a8e40d346
parentb84375f891085d385c2a19a1e8e1bd21171ef91b (diff)
downloadcsci3753-master.tar.gz
csci3753-master.zip
pa8: improvementsHEADmaster
-rw-r--r--pa7_lru/pager-lru.c30
-rw-r--r--pa8_predict/Makefile36
-rw-r--r--pa8_predict/pager-predict.c208
-rw-r--r--pa8_predict/pager-predict2.c56
4 files changed, 158 insertions, 172 deletions
diff --git a/pa7_lru/pager-lru.c b/pa7_lru/pager-lru.c
index 14608d0..aa20825 100644
--- a/pa7_lru/pager-lru.c
+++ b/pa7_lru/pager-lru.c
@@ -3,19 +3,28 @@
// PA7 LRU
#include "../common/simulator.h"
#include <stdbool.h>
+#include <stdio.h>
#include <string.h>
void pageit(Pentry q[MAXPROCESSES]) {
- static int timestamps[MAXPROCESSES][MAXPROCPAGES], tick = 1;
static bool initialised = false;
+ static int prev[MAXPROCESSES], tick = 1;
+ static int timestamps[MAXPROCESSES][MAXPROCPAGES];
+ static int predict_cnt[MAXPROCESSES][MAXPROCPAGES];
if (!initialised) {
+ for (int i = 0; i < MAXPROCPAGES; i++)
+ prev[i] = -1;
memset(timestamps, 0, sizeof(timestamps));
+ memset(predict_cnt, 0, sizeof(predict_cnt));
initialised = true;
}
- for (int proc = 0; proc < MAXPROCESSES; proc++)
+ for (int proc = 0; proc < MAXPROCESSES; proc++) {
if (q[proc].active) {
int curr = q[proc].pc / PAGESIZE;
timestamps[proc][curr] = tick;
+ if (prev[proc] != -1 && prev[proc] != curr)
+ predict_cnt[prev[proc]][curr]++;
+ prev[proc] = curr;
if (!q[proc].pages[curr])
if (!pagein(proc, curr)) {
int min = tick, choice;
@@ -27,5 +36,20 @@ void pageit(Pentry q[MAXPROCESSES]) {
pageout(proc, choice);
}
}
- tick++;
+ tick++;
+ }
+ if (tick > 3000000 && tick < 3000020) {
+ int row_sum[MAXPROCPAGES];
+ memset(row_sum, 0, sizeof(row_sum));
+ for (int i = 0; i < MAXPROCPAGES; i++)
+ for (int j = 0; j < MAXPROCPAGES; j++)
+ row_sum[i] += predict_cnt[i][j];
+ for (int i = 0; i < MAXPROCPAGES; i++) {
+ for (int j = 0; j < MAXPROCPAGES; j++) {
+ double chance = (double)predict_cnt[i][j] / row_sum[i];
+ printf("%.2f\t", row_sum[i] ? chance : 0);
+ }
+ printf("\n");
+ }
+ }
}
diff --git a/pa8_predict/Makefile b/pa8_predict/Makefile
index 8629c67..093b75d 100644
--- a/pa8_predict/Makefile
+++ b/pa8_predict/Makefile
@@ -1,33 +1,9 @@
-# CSCI3753 - FA23 PA8
+OBJS = simulator.o programs.o pager-predict.o
+VPATH = ../common
+CFLAGS = -Wall -Wextra -g
-CC = gcc
-CFLAGS = -c -g -Wall -Wextra
-LFLAGS = -g -Wall -Wextra
-
-VPATH += ../common
-
-SUBMITFILES = pager-predict.c
-
-.PHONY: all clean
-
-all: test-predict
-
-test-predict: simulator.o pager-predict.o programs.o
- $(CC) $(LFLAGS) $^ -o $@
-
-simulator.o: simulator.c programs.o simulator.h
- $(CC) $(CFLAGS) $<
-
-pager-predict.o: pager-predict.c simulator.h
- $(CC) $(CFLAGS) $<
+all: $(OBJS)
+ cc $(CFLAGS) -o test-predict $(OBJS)
clean:
- rm -f test-basic test-predict test-predict test-api
- rm -f simulator.o pager-predict.o
- rm -f *~
- rm -f *.csv
- rm -f *.pdf
-
-submit:
- @read -r -p "please enter your identikey username: " username; \
- tar -cvf PA8-$$username.txt $(SUBMITFILES)
+ rm pager-predict.o simulator.o test-predict
diff --git a/pa8_predict/pager-predict.c b/pa8_predict/pager-predict.c
index e2e380a..be8f713 100644
--- a/pa8_predict/pager-predict.c
+++ b/pa8_predict/pager-predict.c
@@ -2,151 +2,81 @@
// CSCI3753 SP24
// PA8 Predict
#include "../common/simulator.h"
-#include <limits.h>
#include <stdbool.h>
-#include <stdio.h>
-#include <stdlib.h>
+#include <string.h>
-struct page_stat {
- int page;
- int freq;
- int *timestamp;
-};
-
-int active_page(int pc) { return pc / PAGESIZE; }
-
-struct page_stat *
-predict_page(int proc, int curr_pc,
- struct page_stat data[MAXPROCESSES][MAXPROCPAGES][MAXPROCPAGES]) {
- return data[proc][active_page(curr_pc + 101)];
-}
-
-int page_count(struct page_stat *guesses) {
- int n = 0;
- while (guesses[n].page != -1 && n < MAXPROCPAGES)
- n++;
- return n;
-}
-
-void swap(struct page_stat *x, struct page_stat *y) {
- struct page_stat z = *x;
- *x = *y;
- *y = z;
-}
-
-void page_sort(struct page_stat *guesses) {
- int n = page_count(guesses);
- bool swapped;
- do {
- swapped = false;
- for (int i = 1; i < n; i++)
- if (guesses[i - 1].freq < guesses[i].freq) {
- swap(guesses + (i - 1), guesses + i);
- swapped = true;
- }
- } while (swapped);
-}
-
-bool find_lru_page(int time_stamps[MAXPROCESSES][MAXPROCPAGES],
- Pentry q[MAXPROCESSES], int proc, int *lru_page) {
- int smallest_tick = INT_MAX;
- bool res = true;
- for (int i = 0; i < MAXPROCPAGES; i++)
- if (q[proc].pages[i] == 1 && time_stamps[proc][i] < smallest_tick) {
- *lru_page = i;
- smallest_tick = time_stamps[proc][i];
- res = false;
- }
- return res;
-}
-
-void update_page(
- int curr_page, int proc, int prev_page,
- struct page_stat data[MAXPROCESSES][MAXPROCPAGES][MAXPROCPAGES],
- int time_stamps[MAXPROCESSES][MAXPROCPAGES]) {
- struct page_stat *new = data[proc][prev_page];
- for (int i = 0; i < MAXPROCPAGES; i++) {
- if (new[i].page == curr_page) {
- new[i].freq++;
- break;
- }
- if (new[i].page == -1) {
- new[i].page = curr_page;
- new[i].freq = 1;
- new[i].timestamp = &(time_stamps[proc][i]);
- break;
- }
- }
-}
+static const float transition[MAXPROCESSES][MAXPROCPAGES] = {
+ {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0, 0, 0, 0, 0.93, 0, 0, 0, 0, 0, 0.07, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0.15, 0, 0, 0, 0, 0, 0.85, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0.04, 0, 0, 0, 0, 0, 0, 0, 0.57, 0, 0, 0.39, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0.81, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.12, 0, 0, 0, 0, 0, 0.08, 0},
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
+ {0.14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.86, 0, 0},
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
+ {0.29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.71, 0, 0, 0}};
void pageit(Pentry q[MAXPROCESSES]) {
- static bool initialized = false, proc_active[MAXPROCESSES];
- static struct page_stat data[MAXPROCESSES][MAXPROCPAGES][MAXPROCPAGES];
- static int proc_tmp, page_tmp, lru_page, prev_page, curr_page,
- tick = 1, time_stamps[MAXPROCESSES][MAXPROCPAGES], pc_prev[MAXPROCESSES];
- if (!initialized) {
+ static bool initialised = false;
+ static int prev[MAXPROCESSES], tick = 1;
+ static int row_sum[MAXPROCESSES][MAXPROCPAGES];
+ static int prediction[MAXPROCESSES][MAXPROCPAGES][MAXPROCPAGES];
+ bool swap[MAXPROCPAGES] = {false};
+ if (!initialised) {
for (int i = 0; i < MAXPROCESSES; i++)
- for (int j = 0; j < MAXPROCESSES; j++)
- for (int k = 0; k < MAXPROCESSES; k++) {
- data[i][j][k].page = -1;
- data[i][j][k].freq = -1;
- data[i][j][k].timestamp = NULL;
- }
- for (proc_tmp = 0; proc_tmp < MAXPROCESSES; proc_tmp++) {
- for (page_tmp = 0; page_tmp < MAXPROCPAGES; page_tmp++)
- time_stamps[proc_tmp][page_tmp] = 0;
- proc_active[proc_tmp] = false;
- }
- initialized = true;
- }
- for (proc_tmp = 0; proc_tmp < MAXPROCESSES; proc_tmp++) {
- if (!q[proc_tmp].active)
- continue;
- prev_page = active_page(pc_prev[proc_tmp]);
- pc_prev[proc_tmp] = q[proc_tmp].pc;
- curr_page = active_page(q[proc_tmp].pc);
- if (prev_page == curr_page)
- continue;
- pageout(proc_tmp, prev_page);
- update_page(curr_page, proc_tmp, prev_page, data, time_stamps);
- }
- for (proc_tmp = 0; proc_tmp < MAXPROCESSES; proc_tmp++) {
- if (!q[proc_tmp].active)
- continue;
- page_tmp = (q[proc_tmp].pc - 1) / PAGESIZE;
- time_stamps[proc_tmp][page_tmp] = tick;
+ prev[i] = -1;
+ memset(row_sum, 0, sizeof(row_sum));
+ memset(prediction, 0, sizeof(prediction));
+ initialised = true;
}
- for (proc_tmp = 0; proc_tmp < MAXPROCESSES; proc_tmp++) {
- if (!q[proc_tmp].active) {
- for (page_tmp = 0; page_tmp < MAXPROCPAGES; page_tmp++)
- pageout(proc_tmp, page_tmp);
- continue;
- }
- page_tmp = q[proc_tmp].pc / PAGESIZE;
- if (q[proc_tmp].pages[page_tmp] == 1)
- continue;
- if (pagein(proc_tmp, page_tmp)) {
- proc_active[proc_tmp] = false;
- continue;
- }
- if (proc_active[proc_tmp])
- continue;
- if (find_lru_page(time_stamps, q, proc_tmp, &lru_page))
- continue;
- if (!pageout(proc_tmp, lru_page)) {
- fprintf(stderr, "error: failed to page out page %d\n", lru_page);
- exit(EXIT_FAILURE);
+ for (int proc = 0; proc < MAXPROCESSES; proc++)
+ if (q[proc].active) {
+ int curr = q[proc].pc / PAGESIZE;
+ if (prev[proc] != -1 && prev[proc] != curr) {
+ row_sum[proc][prev[proc]]++;
+ prediction[proc][prev[proc]][curr]++;
+ }
+ prev[proc] = curr;
+ swap[curr] = true;
+ if (tick > PAGEWAIT && row_sum[proc][curr]) {
+ for (int i = 0; i < MAXPROCPAGES; i++)
+ if ((double)prediction[proc][curr][i] / row_sum[proc][curr]) {
+ swap[i] = true;
+ if (row_sum[proc][i])
+ for (int j = 0; j < MAXPROCPAGES; j++)
+ if ((double)prediction[proc][i][j] / row_sum[proc][i])
+ swap[j] = true;
+ }
+ } else {
+ for (int i = 0; i < MAXPROCPAGES; i++)
+ if (transition[curr][i]) {
+ swap[i] = true;
+ if (transition[curr][i] > 0.9)
+ for (int j = 0; j < MAXPROCPAGES; j++)
+ if (transition[i][j] * transition[curr][i] > 0.025)
+ swap[j] = true;
+ }
+ }
+ for (int i = 0; i < q[proc].npages; i++)
+ if (!swap[i] && q[proc].pages[i])
+ pageout(proc, i);
+ if (!q[proc].pages[curr])
+ pagein(proc, curr);
+ for (int i = 0; i < q[proc].npages; i++)
+ if (swap[i] && !q[proc].pages[i])
+ pagein(proc, i);
+ memset(swap, false, sizeof(swap));
}
- proc_active[proc_tmp] = true;
- }
- for (proc_tmp = 0; proc_tmp < MAXPROCESSES; proc_tmp++) {
- struct page_stat *predictions;
- if (!q[proc_tmp].active)
- continue;
- predictions = predict_page(proc_tmp, q[proc_tmp].pc, data);
- page_sort(predictions);
- for (int i = 0; i < page_count(predictions); i++)
- pagein(proc_tmp, predictions[i].page);
- }
tick++;
}
diff --git a/pa8_predict/pager-predict2.c b/pa8_predict/pager-predict2.c
new file mode 100644
index 0000000..512e7c4
--- /dev/null
+++ b/pa8_predict/pager-predict2.c
@@ -0,0 +1,56 @@
+// Jack Sangdahl
+// CSCI3753 SP24
+// PA8 Predict
+#include "../common/simulator.h"
+#include <stdbool.h>
+#include <string.h>
+
+void pageit(Pentry q[MAXPROCESSES]) {
+ static bool initialised = false;
+ static int prev[MAXPROCESSES], tick = 1;
+ static int row_sum[MAXPROCESSES][MAXPROCPAGES];
+ static int prediction[MAXPROCESSES][MAXPROCPAGES][MAXPROCPAGES];
+ bool swap[MAXPROCPAGES] = {false};
+ if (!initialised) {
+ for (int i = 0; i < MAXPROCESSES; i++)
+ prev[i] = -1;
+ memset(row_sum, 0, sizeof(row_sum));
+ memset(prediction, 0, sizeof(prediction));
+ initialised = true;
+ }
+ for (int proc = 0; proc < MAXPROCESSES; proc++)
+ if (q[proc].active) {
+ int curr = q[proc].pc / PAGESIZE;
+ if (prev[proc] != -1 && prev[proc] != curr) {
+ row_sum[proc][prev[proc]]++;
+ prediction[proc][prev[proc]][curr]++;
+ }
+ prev[proc] = curr;
+ swap[curr] = true;
+ if (tick > PAGEWAIT && row_sum[proc][curr])
+ for (int i = 0; i < MAXPROCPAGES; i++) {
+ double probability =
+ (double)prediction[proc][curr][i] / row_sum[proc][curr];
+ if (probability) {
+ swap[i] = true;
+ if (probability > 0.9)
+ for (int j = 0; j < MAXPROCPAGES; j++) {
+ double secondary_prob =
+ (double)prediction[proc][i][j] / row_sum[proc][i];
+ if (secondary_prob > 0.025)
+ swap[j] = true;
+ }
+ }
+ }
+ for (int i = 0; i < q[proc].npages; i++)
+ if (!swap[i] && q[proc].pages[i])
+ pageout(proc, i);
+ if (!q[proc].pages[curr])
+ pagein(proc, curr);
+ for (int i = 0; i < q[proc].npages; i++)
+ if (swap[i] && !q[proc].pages[i])
+ pagein(proc, i);
+ memset(swap, false, sizeof(swap));
+ }
+ tick++;
+}