diff options
author | Jack Sangdahl <[email protected]> | 2024-11-14 22:55:52 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-14 22:55:52 -0700 |
commit | b6d0f307fb61884c60a7aa0bc46f0a88c6ca4fab (patch) | |
tree | a449caf78c54e71a5f5961cbac37a02a8e40d346 | |
parent | b84375f891085d385c2a19a1e8e1bd21171ef91b (diff) | |
download | csci3753-master.tar.gz csci3753-master.zip |
-rw-r--r-- | pa7_lru/pager-lru.c | 30 | ||||
-rw-r--r-- | pa8_predict/Makefile | 36 | ||||
-rw-r--r-- | pa8_predict/pager-predict.c | 208 | ||||
-rw-r--r-- | pa8_predict/pager-predict2.c | 56 |
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++; +} |