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 | |
parent | 3c8bb65459ca0d8c5fac591977d92d074ab44d88 (diff) | |
download | csci3753-a4f877ffdc6bc802490f2998f7e7b226be2c7bfa.tar.gz csci3753-a4f877ffdc6bc802490f2998f7e7b226be2c7bfa.zip |
pa8
-rw-r--r-- | .gitignore | 1 | ||||
-rw-r--r-- | pa8_predict/Makefile | 31 | ||||
-rw-r--r-- | pa8_predict/pager-predict.c | 180 | ||||
-rw-r--r-- | pa8_predict/see.R | 505 | ||||
-rw-r--r-- | pa8_predict/simulator.c | 837 | ||||
-rw-r--r-- | pa8_predict/simulator.h | 111 |
6 files changed, 1665 insertions, 0 deletions
@@ -8,3 +8,4 @@ pa5_dns_resolver/lookup pa6_threaded_resolver/multi-lookup pa6_threaded_resolver/*.log pa7_lru/test* +pa8_predict/test-predict diff --git a/pa8_predict/Makefile b/pa8_predict/Makefile new file mode 100644 index 0000000..08024e8 --- /dev/null +++ b/pa8_predict/Makefile @@ -0,0 +1,31 @@ +# CSCI3753 - FA23 PA8 + +CC = gcc +CFLAGS = -c -g -Wall -Wextra +LFLAGS = -g -Wall -Wextra + +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) $< + +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) 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 diff --git a/pa8_predict/see.R b/pa8_predict/see.R new file mode 100644 index 0000000..17a2c02 --- /dev/null +++ b/pa8_predict/see.R @@ -0,0 +1,505 @@ +#======================================================== +# R statistics system grapher for PA4 +#======================================================== + +#======================================================== +# determine page from PC +#======================================================== +PAGESIZE <- 128 +page <- function (pc) { as.integer(pc/PAGESIZE) } + +#======================================================== +# read whole history from file 'output.csv' +#======================================================== +allHistory<- function(x, y, z) UseMethod('allHistory') + +allHistory.NULL <- function(x) { allHistory('output.csv') } + +# read results from file +allHistory.character <- function(file) { + out <- read.csv(file, header=FALSE) + out <- data.frame(time=out$V1, proc=out$V2, pid=out$V3, kind=out$V4, pc=out$V5, comment=out$V6) + class(out) <- c('allHistory', class(out)) + out +} + +# scope results in time +allHistory.allHistory <- function(all, low=0, high=1e25) { + sel <- (all$time >= low) & (all$time <= high) + out <- data.frame(time=all$time[sel], proc=all$proc[sel], + pid=all$pid[sel], kind=all$kind[sel], + pc=all$pc[sel], comment=all$comment[sel]) + class(out) <- c('allHistory', class(out)) + out +} + +#======================================================== +# read pages history from file 'pages.csv' +#======================================================== +allPages<- function(x, y, z) UseMethod('allPages') + +allPages.NULL <- function(x) { allPages('pages.csv') } + +# read results from file +allPages.character <- function(file) { + out <- read.csv(file, header=FALSE) + out <- data.frame(time=out$V1, proc=out$V2, page=out$V3, pid=out$V4, kind=out$V5, comment=out$V6) + class(out) <- c('allPages', class(out)) + out +} + +# scope results in time +allPages.allPages <- function(pl, low=0, high=1e25) { + +# # determine states before window +# times <- c(); procs <- c(); pages <- c() +# pids <- c(); kinds <- c(); comments <- c() +# for (p in c(1:20)) { # processes +# for (q in c(1:20)) { # pages +# # boolean bit field +# sel <- (pl$time<low) & (pl$proc==p) & (pl$page==q) +# temp <- pl$time[sel] +# if (length(temp)>0) { +# times[[length(times)+1]] <- temp[[length(temp)]] +# temp <- pl$proc[sel] +# procs[[length(procs)+1]] <- temp[[length(temp)]] +# temp <- pl$page[sel] +# pages[[length(pages)+1]] <- temp[[length(temp)]] +# temp <- pl$pid[sel] +# pids[[length(pids)+1]] <- temp[[length(temp)]] +# temp <- pl$kind[sel] +# kinds[[length(kinds)+1]] <- temp[[length(temp)]] +# temp <- pl$comment[sel] +# comments[[length(comments)+1]] <- as.character(temp[[length(temp)]]) +# } +# } +# } +# ord <- order(times,procs,pages) +# before <- data.frame(time=times[ord], proc=procs[ord], page=pages[ord], +# pid=pids[ord], kind=kinds[ord], comment=comments[ord]) +# +# # determine states after window +# times <- c(); procs <- c(); pages <- c() +# pids <- c(); kinds <- c(); comments <- c() +# for (p in c(1:20)) { # processes +# for (q in c(1:20)) { # pages +# # boolean bit field +# sel <- (pl$time>high) & (pl$proc==p) & (pl$page==q) +# temp <- pl$time[sel] +# if (length(temp)>0) { +# times[[length(times)+1]] <- temp[[1]] +# temp <- pl$proc[sel] +# procs[[length(procs)+1]] <- temp[[1]] +# temp <- pl$page[sel] +# pages[[length(pages)+1]] <- temp[[1]] +# temp <- pl$pid[sel] +# pids[[length(pids)+1]] <- temp[[1]] +# temp <- pl$kind[sel] +# kinds[[length(kinds)+1]] <- temp[[1]] +# temp <- pl$comment[sel] +# comments[[length(comments)+1]] <- as.character(temp[[1]]) +# } +# } +# } +# ord <- order(times,procs, pages) +# after <- data.frame(time=times[ord], proc=procs[ord], page=pages[ord], +# pid=pids[ord], kind=kinds[ord], comment=comments[ord]) + +# now construct the output + sel <- ((pl$time >= low) & (pl$time <= high)) + out <- data.frame( + time=pl$time[sel], + proc=pl$proc[sel], + page=pl$page[sel], + pid=pl$pid[sel], + kind=pl$kind[sel], + comment=pl$comment[sel] + ) +# out <- data.frame( +# time=c(before$time,pl$time[sel],after$time), +# proc=c(before$proc,pl$proc[sel],after$proc), +# page=c(before$page,pl$page[sel],after$page), +# pid=c(before$pid,pl$pid[sel],after$pid), +# kind=c(before$kind,pl$kind[sel],after$kind), +# comment=c(before$comment,pl$comment[sel],after$comment) +# ) + class(out) <- c('allPages', class(out)) + out +} + +#======================================================== +# paging history for one process +#======================================================== +procPages<- function(x, y, z, w) UseMethod('procPages') +procPages.allPages <- function(pl, proc, low=0, high=1e25) { + sel <- (pl$proc==proc) & (pl$time>=low) & (pl$time<=high) + out <- data.frame(time=pl$time[sel], proc=pl$proc[sel], page=pl$page[sel], + pid=pl$pid[sel], kind=pl$kind[sel], comment=pl$comment[sel]) + class(out) <- c('procPages', class(out)) + out +} + +procPages.procPages <- function(pl, low=0, high=1e25) { + sel <- (pl$time>=low) & (pl$time<=high) + out <- data.frame(time=pl$time[sel], proc=pl$proc[sel], page=pl$page[sel], + pid=pl$pid[sel], kind=pl$kind[sel], comment=pl$comment[sel]) + class(out) <- c('procPages', class(out)) + out +} + +#======================================================== +# paging history for one job +#======================================================== +jobPages<- function(x, y, z, w) UseMethod('jobPages') +jobPages.allPages <- function(pl, pid, low=0, high=1e25) { + sel <- (pl$pid==pid) & (pl$time>=low) & (pl$time<=high) + out <- data.frame(time=pl$time[sel], proc=pl$proc[sel], page=pl$page[sel], + pid=pl$pid[sel], kind=pl$kind[sel], comment=pl$comment[sel]) + class(out) <- c('jobPages', class(out)) + out +} + +jobPages.jobPages <- function(pl, low=0, high=1e25) { + sel <- (pl$time>=low) & (pl$time<=high) + out <- data.frame(time=pl$time[sel], proc=pl$proc[sel], page=pl$page[sel], + pid=pl$pid[sel], kind=pl$kind[sel], comment=pl$comment[sel]) + class(out) <- c('jobPages', class(out)) + out +} +#======================================================== +# a processor history is obtained from a full history +# by filtering by processor number +#======================================================== +procHistory <- function(x, y, z, w) UseMethod('procHistory') + +# extract a processor record from global history +procHistory.allHistory <- function(all, proc, low=0, high=1e25) { + sel <- (all$proc==proc) & (all$time >= low) & (all$time <= high) + out <- data.frame(time=all$time[sel], proc=all$proc[sel], + pid=all$pid[sel], kind=all$kind[sel], + pc=all$pc[sel],comment=all$comment[sel]) + class(out) <- c('procHistory', class(out)) + out +} + +# limit a processor history to a specific time +procHistory.procHistory <- function(ph, low=0, high=1e25) { + sel <- (ph$time >= low) & (ph$time <= high) + out <- data.frame(time=ph$time[sel], proc=ph$proc[sel], + pid=ph$pid[sel], kind=ph$kind[sel], + pc=ph$pc[sel],comment=ph$comment[sel]) + class(out) <- c('procHistory', class(out)) + out +} + +#======================================================== +# a job history is obtained from a full history by +# filtering by job number 0-39 +#======================================================== +jobHistory <- function(x, y, z, w) UseMethod('jobHistory') + +# extract a job from global history +jobHistory.allHistory <- function(all, pid, low=0, high=1e25) { + sel <- (all$pid==pid) & (all$time >= low) & (all$time <= high) + out <- data.frame(time=all$time[sel], proc=all$proc[sel], pid=all$pid[sel], + kind=all$kind[sel],pc=all$pc[sel],comment=all$comment[sel]) + class(out) <- c('jobHistory', class(out)) + out +} + +# limit a job to a specific time +jobHistory.jobHistory <- function(jh, low=0, high=1e25) { + sel <- (jh$time >= low) & (jh$time <= high) + out <- data.frame(time=jh$time[sel], proc=jh$proc[sel], pid=jh$pid[sel], + kind=jh$kind[sel],pc=jh$pc[sel],comment=jh$comment[sel]) + class(out) <- c('jobHistory', class(out)) + out +} + +#======================================================== +# smart plotting routines describe how to plot full +# histories, processor histories, job histories +# based upon object class. +#======================================================== + +# plot a single job +plot.jobHistory <- function(jh, low=0, high=1e25) { + toplot <- jobHistory(jh, low, high) + plot(c(), xlab='time', ylab='pc', ylim=c(0,max(toplot$pc)), xlim=c(toplot$time[[1]],toplot$time[[length(toplot$time)]])) + if (! is.na(pages)) lines(jobPages(pages,toplot$pid[[1]],low,high)) + # print(pages) + lines(toplot$time, toplot$pc, xlab='time', ylab='pc', col='black') + plotBlocked(toplot, low, high); +} + +# plot a single processor's results (all jobs) +plot.procHistory <- function(ph, low=0, high=1e25) { + toplot <- procHistory(ph, low, high) + plot(c(), , xlab='time', ylab='pc', ylim=c(0,max(toplot$pc)), xlim=c(toplot$time[[1]],toplot$time[[length(toplot$time)]])) + if (!is.na(pages)) lines(procPages(pages,toplot$proc[[1]],low, high)) + lines(toplot$time, (toplot$pc), xlab='time', ylab='pc', col='black') + plotBlocked(ph, low, high); +} + +# plot all job histories. +plot.allHistory <- function(all, low=0, high=1e25) { + toplot <- allHistory(all, low, high) + # create a selected region from this! + plot(c(), type='l', xlab='time', ylab='process', + xlim=c(1,toplot$time[[length(toplot$time)]]), ylim=c(0,41)) + x <- array() + y <- array() + for (job in c(0:39)) { + jh <- jobHistory(toplot, job, low, high) + if (length(jh$time)>0) { + x[[length(x)+1]] <- jh$time[[1]] + x[[length(x)+1]] <- jh$time[[length(jh$time)]] + x[[length(x)+1]] <- NA + y[[length(y)+1]] <- job + y[[length(y)+1]] <- job + y[[length(y)+1]] <- NA + } + } + lines(x,y,col='black') + x <- array() + y <- array() + for (job in c(0:39)) { + jh <- jobHistory(toplot, job, low, high) + if (length(jh$time)>0) { + for (index in c(1:(length(jh$time)-1))) { + if (jh$comment[[index]]=='blocked' + && jh$comment[[index+1]]=='unblocked') { + x[[length(x)+1]] <- jh$time[[index]] + x[[length(x)+1]] <- jh$time[[index+1]] + x[[length(x)+1]] <- NA + y[[length(y)+1]] <- job + y[[length(y)+1]] <- job + y[[length(y)+1]] <- NA + } + } + } + } + lines(x,y,col='red') +} + +#======================================================== +# subsystem plots page state on block graph +#======================================================== +plot.procPages <- function (pl, low=0, high=1e25) { + toplot <- procPages(pl, low, high) + plot(c(), xlab='time', ylab='memory', ylim=c(0,max(toplot$page)*128), xlim=c(toplot$time[[1]],toplot$time[[length(toplot$time)]])) + lines(toplot, low, high) +} + +lines.procPages <- function (pl, low=0, high=1e25) { + toplot <- procPages(pl, low, high) + + tot <- max(toplot$page) + refs <- array(dim=c(tot+1)) + coms <- array(dim=c(tot+1)) + for (i in c(1:(tot+1))) { + refs[[i]] = 0 + coms[[i]] = 'out' + } + xleft <- c() + xright <- c() + ybottom <- c() + ytop <- c() + cols <- c() + for (i in c(1:length(toplot$time))) { + time <- toplot$time[[i]] + page <- toplot$page[[i]] + if (!is.na(refs[[page+1]])) { + oldtime <- refs[[page+1]]; + oldcomm <- coms[[page+1]]; + xleft[[length(xleft)+1]] = oldtime + xright[[length(xright)+1]] = time + ybottom[[length(ybottom)+1]] = page*128 + ytop[[length(ytop)+1]] = (page+1)*128 + if (oldcomm=='in') { + cols[[length(cols)+1]] = rgb(.9,1,.9) + } else if (oldcomm=='out') { + cols[[length(cols)+1]] = rgb(1,.9,.9) + } else if (oldcomm=='coming') { + cols[[length(cols)+1]] = rgb(1,1,.9) + } else { # if (oldcomm=='going') + cols[[length(cols)+1]] = rgb(1,.9,1) + } + } + refs[[page+1]]=toplot$time[[i]] + coms[[page+1]]=as.character(toplot$comment[[i]]) + } + end <- toplot$time[[length(toplot$time)]] + # plot to end of line + for (page in c(0:19)) { + if (!is.na(refs[[page+1]])) { + oldtime <- refs[[page+1]]; + oldcomm <- coms[[page+1]]; + xleft[[length(xleft)+1]] = oldtime + xright[[length(xright)+1]] = end + ybottom[[length(ybottom)+1]] = page*128 + ytop[[length(ytop)+1]] = (page+1)*128 + if (oldcomm=='in') { + cols[[length(cols)+1]] = rgb(.9,1,.9) + } else if (oldcomm=='out') { + cols[[length(cols)+1]] = rgb(1,.9,.9) + } else if (oldcomm=='coming') { + cols[[length(cols)+1]] = rgb(1,1,.9) + } else { # if (oldcomm=='going') + cols[[length(cols)+1]] = rgb(1,.9,1) + } + } + } + rect(xleft=xleft, ybottom=ybottom, xright=xright, ytop=ytop, col=cols, border=NA) + # title(paste('pages for processor ',toplot$proc[[1]])) +} + +plot.jobPages <- function (pl, low=0, high=1e25) { + toplot <- jobPages(pl, low, high) + plot(c(), xlab='time', ylab='memory', ylim=c(0,max(toplot$page)*128), xlim=c(toplot$time[[1]],toplot$time[[length(toplot$time)]])) + lines(toplot, low, high) +} + +lines.jobPages <- function (pl, low=0, high=1e25) { + toplot <- jobPages(pl, low, high) + + tot <- max(toplot$page) + refs <- array(dim=c(tot+1)) + coms <- array(dim=c(tot+1)) + for (i in c(1:(tot+1))) { + refs[[i]] = 0 + coms[[i]] = 'out' + } + xleft <- c() + xright <- c() + ybottom <- c() + ytop <- c() + cols <- c() + for (i in c(1:length(toplot$time))) { + time <- toplot$time[[i]] + page <- toplot$page[[i]] + if (!is.na(refs[[page+1]])) { + oldtime <- refs[[page+1]]; + oldcomm <- coms[[page+1]]; + xleft[[length(xleft)+1]] = oldtime + xright[[length(xright)+1]] = time + ybottom[[length(ybottom)+1]] = page*128 + ytop[[length(ytop)+1]] = (page+1)*128 + if (oldcomm=='in') { + cols[[length(cols)+1]] = rgb(.9,1,.9) + } else if (oldcomm=='out') { + cols[[length(cols)+1]] = rgb(1,.9,.9) + } else if (oldcomm=='coming') { + cols[[length(cols)+1]] = rgb(1,1,.9) + } else { # if (oldcomm=='going') + cols[[length(cols)+1]] = rgb(1,.9,1) + } + } + refs[[page+1]]=toplot$time[[i]] + coms[[page+1]]=as.character(toplot$comment[[i]]) + } + end <- toplot$time[[length(toplot$time)]] + # plot to end of line + for (page in c(0:19)) { + if (!is.na(refs[[page+1]])) { + oldtime <- refs[[page+1]]; + oldcomm <- coms[[page+1]]; + xleft[[length(xleft)+1]] = oldtime + xright[[length(xright)+1]] = end + ybottom[[length(ybottom)+1]] = page*128 + ytop[[length(ytop)+1]] = (page+1)*128 + if (oldcomm=='in') { + cols[[length(cols)+1]] = rgb(.9,1,.9) + } else if (oldcomm=='out') { + cols[[length(cols)+1]] = rgb(1,.9,.9) + } else if (oldcomm=='coming') { + cols[[length(cols)+1]] = rgb(1,1,.9) + } else { # if (oldcomm=='going') + cols[[length(cols)+1]] = rgb(1,.9,1) + } + } + } + rect(xleft=xleft, ybottom=ybottom, xright=xright, ytop=ytop, col=cols, border=NA) + # title(paste('pages for processor ',toplot$proc[[1]])) +} + +#======================================================== +# subsystem plots blockages in red over grey background +#======================================================== +plotBlocked <- function(x, y, z) UseMethod('plotBlocked') +# print red blocked times over one job history +plotBlocked.jobHistory <- function(jh, low=0, high=1e25) { + toplot <- jobHistory(jh, low, high) + x <- array() + y <- array() + for (i in c(1:(length(toplot$time)-1))) { + if (toplot$comment[[i]]=='blocked' && toplot$comment[[i+1]]=='unblocked') { + x[[length(x)+1]] <- toplot$time[[i]] + x[[length(x)+1]] <- toplot$time[[i+1]] + x[[length(x)+1]] <- NA + y[[length(y)+1]] <- (toplot$pc[[i]]) + y[[length(y)+1]] <- (toplot$pc[[i]]) + y[[length(y)+1]] <- NA + } + } + lines(x,y,col='red'); +} + +# print red blocked times over one processor history +plotBlocked.procHistory <- function(ph, low=0, high=1e25) { + toplot <- procHistory(ph, low, high) + x <- array() + y <- array() + for (i in c(1:(length(toplot$time)-1))) { + if (toplot$comment[[i]]=='blocked' && toplot$comment[[i+1]]=='unblocked') { + x[[length(x)+1]] <- toplot$time[[i]] + x[[length(x)+1]] <- toplot$time[[i+1]] + x[[length(x)+1]] <- NA + y[[length(y)+1]] <- (toplot$pc[[i]]) + y[[length(y)+1]] <- (toplot$pc[[i]]) + y[[length(y)+1]] <- NA + } + } + lines(x,y,col='red'); +} + +#======================================================== +# interactive subsystem describes how to give more info +#======================================================== +interact <- function(x, y, z, w) UseMethod('interact') + +# zoom in on one job from full history +interact.allHistory <- function (all, low=0, high=1e25) { + while(TRUE) { + plot(all, low, high) + title("click on a timeline to graph the PC for the job") + which <- locator(1) + job <- as.integer(which$y[[1]]+0.5) + if ((job >= 0) && (job <= 39)) { + interact(jobHistory(all,job)) + } else { + break + } + } +} + +# plot one job interactively +interact.jobHistory <- function(jh, low=0, high=1e25) { + plot(jh,low,high) + title("click anywhere to return to overall view") + which <- locator(1) +} + +#======================================================== +# use the system to visualize results +#======================================================== + +# read file from disk into full history +all <- allHistory() +pages <- try(allPages(), silent=TRUE) +if (class(pages)[[1]] == 'try-error') { + pages <- NA +} + +# go interactive and show results +interact(all) diff --git a/pa8_predict/simulator.c b/pa8_predict/simulator.c new file mode 100644 index 0000000..58a5800 --- /dev/null +++ b/pa8_predict/simulator.c @@ -0,0 +1,837 @@ +/* + * File: simulator.c + * + * Original Author: Dr. Alva Couch + * http://www.cs.tufts.edu/~couch/ + */ + +#include <signal.h> +#include <stdarg.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <unistd.h> + +#include "simulator.h" + +extern Program programs[PROGRAMS]; + +FILE *output = NULL; /* PC history for statistical analysis */ +FILE *pages = NULL; /* block allocation history */ + +static long sysclock = 0; +static long seed = 0; +static long procs = MAXPROCESSES; + +#define LOG_ALWAYS (1 << 0) +#define LOG_LOAD (1 << 1) +#define LOG_BLOCK (1 << 2) +#define LOG_PAGE (1 << 3) +#define LOG_BRANCH (1 << 4) +#define LOG_DEAD (1 << 5) +#define LOG_QUEUE (1 << 9) + +#include <stdarg.h> +#include <stdio.h> +#include <sys/types.h> + +// shorthands for assertion handling +#define CHECK(bool) check((bool), #bool, __FILE__, __LINE__) +#define ASSERT(bool) assert((bool), #bool, __FILE__, __LINE__) +#define POSIT(bool) posit((bool), #bool, __FILE__, __LINE__) +#define DIE(reason) die((reason), __FILE__, __LINE__) +#define CARP(reason) carp((reason), __FILE__, __LINE__) + +// always print the result of a test +inline void check(int boolean, char *boolstr, char *file, int line) { + if (!boolean) { + fprintf(stderr, "ERROR: %s failed in line %d of file %s\n", boolstr, line, + file); + } else { + fprintf(stderr, "%s succeeded in line %d of file %s\n", boolstr, line, + file); + } +} + +// die if an assertion fails. +static inline void assert(int boolean, char *boolstr, char *file, int line) { + if (!boolean) { + fprintf(stderr, "Assertion %s failed in line %d of file %s\n", boolstr, + line, file); + exit(1); /* exit(0) means correct execution! */ + } +} + +// report failing assertions without bombing out... keeps running +inline int posit(int boolean, char *boolstr, char *file, int line) { + if (!boolean) + fprintf(stderr, "Assertion %s failed in line %d of file %s\n", boolstr, + line, file); + return boolean; +} + +// die on a fatal error +inline void die(char *condition, char *file, int line) { + fprintf(stderr, "Fatal error: %s at line %d of file %s\n", condition, line, + file); + exit(1); +} + +// print a non-fatal error +inline void carp(char *condition, char *file, int line) { + fprintf(stderr, "Non-fatal error: %s at line %d of file %s\n", condition, + line, file); +} + +static long log_port = LOG_ALWAYS; // logging ports for output +static void sim_log(long type, const char *format, ...) { + va_list ap; + if (log_port & type) { + va_start(ap, format); + fprintf(stderr, "%08ld: ", sysclock); + vfprintf(stderr, format, ap); + va_end(ap); + } +} + +/* keep track of physical page usage */ +static long pagesavail = PHYSICALPAGES; + +static Process *processes[MAXPROCESSES]; + +/* make a binary decision according to a + probability distribution */ +static long binary(double prob) { + if (drand48() < prob) + return 1; + else + return 0; +} + +/* clear a branching engine */ +static void bcontext_clear(Bcontext *c) { + long i; + c->bcount = 0; + c->boffset = 0; + c->bsize = 1; + c->bvalue = 1; + c->brings[0] = 1; + for (i = 1; i < MAXBRINGS; i++) + c->brings[i] = 0; +} + +/* initialize a branching engine */ +static void bcontext_init(Bcontext *c, Branch *b) { + long i; + c->bcount = 0; + c->btype = b->btype; + if (b->btype == GOTO) { + c->boffset = 0; + c->bsize = 1; + c->bvalue = 1; + // c->brings[0]=1; /* old version */ + c->brings[0] = 0x7fffffff; /* keep going forever */ + for (i = 1; i < MAXBRINGS; i++) + c->brings[i] = 0; + } else if (b->btype == IF) { + long cvalue; + c->boffset = 0; + c->bsize = 0; + cvalue = c->bvalue = binary(b->prob); + c->bcount = 0; + // compute future values for if statements + while (c->bsize < MAXBRINGS) { + if (binary(b->prob) == cvalue) { + c->brings[c->bsize]++; + } else { + c->bsize++; + c->brings[c->bsize] = 1; + cvalue = !cvalue; + } + } + } else if (b->btype == FOR) { + c->boffset = 0; + c->bvalue = 1; + c->bsize = 0; + while (c->bsize < MAXBRINGS) { + if (b->max > b->min) { + c->brings[c->bsize++] = lrand48() % (b->max - b->min) + b->min; + } else { + c->brings[c->bsize++] = b->min; + } + c->brings[c->bsize++] = 1; // one failure to escape loop + } + } else if (b->btype == NFOR) { + c->boffset = 0; + c->bvalue = 0; + c->bsize = 0; + while (c->bsize < MAXBRINGS) { + if (b->max > b->min) { + c->brings[c->bsize++] = lrand48() % (b->max - b->min) + b->min; + } else { + c->brings[c->bsize++] = b->min; + } + c->brings[c->bsize++] = 1; // one failure to escape loop + } + } else { + fprintf(stderr, "unknown btype %ld\n", (long)(b->btype)); + } +} + +/* decide whether to branch or not */ +static long bcontext_decide(Bcontext *c) { + long ret = c->bvalue; + c->bcount++; + ASSERT(c->boffset >= 0 && c->boffset < MAXBRINGS); + if (c->bcount >= c->brings[c->boffset]) { + c->boffset = (c->boffset + 1) % c->bsize; + // ASSERT(c->boffset>0); // no wrapping! + c->bcount = 0; + c->bvalue = !c->bvalue; + } + return ret; +} + +static void process_clear(Process *q) { + long i; + q->pc = 0; + q->compute = q->block = 0; + q->program = NULL; + q->pid = -1; + q->kind = -1; + q->nbcontexts = 0; + for (i = 0; i < MAXBRANCHES; i++) { + bcontext_clear(q->bcontexts + i); + } + q->npages = 0; + /* no physical pages assigned */ + for (i = 0; i < MAXPROCPAGES; i++) { + q->pages[i] = -PAGEWAIT - 1; + q->blocked[i] = FALSE; // ALC: so simulator will log first access + } + q->active = FALSE; +} + +/* load a program into a process */ +static void process_load(Process *q, Program *p, int pid, int kind) { + long i; + q->pc = 0; + q->compute = q->block = 0; + q->program = p; + q->pid = pid; + q->kind = kind; + q->nbcontexts = p->nbranches; + ASSERT(p->nbranches >= 0 && p->nbranches < MAXBRANCHES); + for (i = 0; i < p->nbranches; i++) { + bcontext_init(q->bcontexts + i, p->branches + i); + } + // fprintf(stderr,"actual page size for process is %d\n", + // (q->program->size+PAGESIZE-1)/PAGESIZE); + q->npages = MAXPROCPAGES; + for (i = 0; i < MAXPROCPAGES; i++) { + q->pages[i] = -PAGEWAIT - 1; + q->blocked[i] = FALSE; // ALC: so simulator will log first access + } + /* no physical pages assigned */ + q->active = TRUE; /* now running */ +} + +/* unload a process and release all resources */ +static void process_unload(int pnum, Process *q) { + long i; + for (i = 0; i < q->npages; i++) + if (q->pages[i] >= -PAGEWAIT) { + pagesavail++; + q->pages[i] = -PAGEWAIT - 1; + q->blocked[i] = 1; + } + q->active = FALSE; + sim_log(LOG_LOAD, "process %2d; pc %04d: unloaded\n", pnum, q->pc); +} + +/* do a branch if necessary */ +static void process_dobranch(int pnum, Process *q, Branch *b, Bcontext *c) { + if (bcontext_decide(c)) { + // must document where we branched from + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,branch_from\n", sysclock, pnum, + q->pid, q->kind, q->pc); + q->pc = b->whereto; + // and where we branched to + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,branch_to\n", sysclock, pnum, q->pid, + q->kind, q->pc); + sim_log(LOG_BRANCH, "process %2d; pc %04d: branch\n", pnum, q->pc); + } else { + q->pc++; + sim_log(LOG_BRANCH, "process %2d; pc %04d: no branch\n", pnum, q->pc); + } + if (q->pc < 0 || q->pc >= q->program->size) + q->pc = 0; /* start over */ +} + +/* compute one step of a process */ +static long process_step(int pnum, Process *q) { + long pc; + long page; + long max, min; + Branch *b; + Bcontext *c; + + if (!q) + return FALSE; + pc = q->pc; + page = q->pc / PAGESIZE; + if (!q->active) { + return FALSE; + } + + /* if page swapped out, don't allow to run */ + if (q->pages[page] != 0) { + if (!q->blocked[page]) { + sim_log(LOG_BLOCK, "process=%2d page=%3d blocked\n", pnum, page); + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,blocked\n", sysclock, pnum, q->pid, + q->kind, q->pc); + q->blocked[page] = TRUE; + } + q->block++; + return TRUE; + } else { + if (q->blocked[page]) { + sim_log(LOG_BLOCK, "process=%2d page=%3d unblocked\n", pnum, page); + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,unblocked\n", sysclock, pnum, + q->pid, q->kind, q->pc); + q->blocked[page] = FALSE; + } + q->compute++; + } + + /* should I exit */ + ASSERT(q->program->nexits >= 0 && q->program->nexits <= MAXEXITS); + min = 0; + max = q->program->nexits - 1; + while (min + 1 < max) { + long mid = (min + max) / 2; + if (pc == q->program->exits[mid]) { + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,exit\n", sysclock, pnum, q->pid, + q->kind, q->pc); + return FALSE; + } else if (pc < q->program->exits[mid]) + max = mid; + else + min = mid; + } + if (pc == q->program->exits[min] || pc == q->program->exits[max]) { + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,exit\n", sysclock, pnum, q->pid, + q->kind, q->pc); + return FALSE; + } + b = q->program->branches; + c = q->bcontexts; + ASSERT(q->program->nbranches >= 0 && q->program->nbranches <= MAXBRANCHES); + min = 0; + max = q->program->nbranches - 1; + while (min + 1 < max) { + long mid = (min + max) / 2; + if (pc == b[mid].wherefrom) { + process_dobranch(pnum, q, b + mid, c + mid); + return TRUE; + } else if (pc < b[mid].wherefrom) + max = mid; + else + min = mid; + } + if (pc == b[min].wherefrom) { + process_dobranch(pnum, q, b + min, c + min); + return TRUE; + } + if (pc == b[max].wherefrom) { + process_dobranch(pnum, q, b + max, c + max); + return TRUE; + } + q->pc++; /* default action */ + if (q->pc < 0 || q->pc > q->program->size) { + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,out_of_range\n", sysclock, pnum, + q->pid, q->kind, q->pc); + q->pc = 0; /* start over */ + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,restart\n", sysclock, pnum, q->pid, + q->kind, q->pc); + } + return TRUE; +} + +/* public routine: swap one page out */ +int pageout(int process, int page) { + if (process < 0 || process >= procs || !processes[process] || + !processes[process]->active || page < 0 || + page >= processes[process]->npages) + return FALSE; + if (processes[process]->pages[page] < 0) + return TRUE; /* on its way out */ + if (processes[process]->pages[page] > 0) + return FALSE; /* not available to swap out */ + sim_log(LOG_PAGE, "process=%2d page=%3d start pageout\n", process, page); + if (pages) + fprintf(pages, "%ld,%d,%d,%ld,%ld,going\n", sysclock, process, page, + processes[process]->pid, processes[process]->kind); + processes[process]->pages[page] = -1; + return TRUE; +} + +/* public routine: swap one page in */ +int pagein(int process, int page) { + if (process < 0 || process >= procs || !processes[process] || + !processes[process]->active || page < 0 || + page >= processes[process]->npages) + return FALSE; + if (processes[process]->pages[page] >= 0) + return TRUE; /* on its way */ + if (pagesavail == 0) + return FALSE; + if (processes[process]->pages[page] >= -PAGEWAIT) + return FALSE; /* not yet out */ + sim_log(LOG_PAGE, "process=%2d page=%3d start pagein\n", process, page); + if (pages) + fprintf(pages, "%ld,%d,%d,%ld,%ld,coming\n", sysclock, process, page, + processes[process]->pid, processes[process]->kind); + processes[process]->pages[page] = PAGEWAIT; + pagesavail--; + return TRUE; +} + +/*============ + job queue + ============*/ + +static long queuetype[QUEUESIZE]; +static Process queue[QUEUESIZE]; +static long queueend; +static void initqueue() { + long i; + for (i = 0; i < QUEUESIZE; i++) + queuetype[i] = lrand48() % PROGRAMS; + /* + long repeats; + for (repeats=0; repeats<10; repeats++) + for (i=0; i<QUEUESIZE; i++) { + int j=lrand48()%QUEUESIZE; + long temp=queuetype[i]; queuetype[i]=queuetype[j]; + queuetype[j]=temp; + } + */ + for (int i = 0; i < QUEUESIZE; i++) { + process_clear(queue + i); + process_load(queue + i, programs + queuetype[i], i, queuetype[i]); + } + + queueend = 0; +} +static Process *dequeue() { + if (queueend < QUEUESIZE) + return queue + queueend++; + else + return NULL; +} +static long empty() { return queueend >= QUEUESIZE; } + +/*=========================== + control of all processes + ===========================*/ + +static void allprint() { + int i, j; + fprintf(stderr, "\nprocess "); + for (i = 0; i < MAXPROCESSES / 2; i++) { + if (i) + fprintf(stderr, " | "); + if (processes[i] && processes[i]->active) { + fprintf(stderr, " %02d", i); + } else { + fprintf(stderr, " --"); + } + } + fprintf(stderr, "\n"); + fprintf(stderr, "pc "); + for (i = 0; i < MAXPROCESSES / 2; i++) { + if (i) + fprintf(stderr, " | "); + if (processes[i] && processes[i]->active) { + fprintf(stderr, "%04ld", processes[i]->pc); + } else { + fprintf(stderr, "----"); + } + } + fprintf(stderr, "\n"); + for (j = 0; j < MAXPROCPAGES; j++) { + fprintf(stderr, "page%02d ", j); + for (i = 0; i < MAXPROCESSES / 2; i++) { + if (i) + fprintf(stderr, " |"); + if (processes[i] && processes[i]->active) { + int pcblock = processes[i]->pc / PAGESIZE; + if (j == pcblock) { + if (processes[i]->pages[j] > 0) + fprintf(stderr, "*i%3ld", processes[i]->pages[j]); + else if (processes[i]->pages[j] == 0) + fprintf(stderr, "*=in "); + else if (processes[i]->pages[j] == -100) + fprintf(stderr, "*=out"); + else + fprintf(stderr, "*o%3ld", 100 + processes[i]->pages[j]); + // fprintf(stderr,"*%4d",processes[i]->pages[j]); + } else { + if (processes[i]->pages[j] > 0) + fprintf(stderr, " i%3ld", processes[i]->pages[j]); + else if (processes[i]->pages[j] == 0) + fprintf(stderr, " =in "); + else if (processes[i]->pages[j] == -100) + fprintf(stderr, " =out"); + else + fprintf(stderr, " o%3ld", 100 + processes[i]->pages[j]); + // fprintf(stderr," %4d",processes[i]->pages[j]); + } + } else { + fprintf(stderr, " ----"); + } + } + fprintf(stderr, "\n"); + } + fprintf(stderr, "------------------------------------------------------------" + "----------------\n"); + fprintf(stderr, "process "); + for (i = MAXPROCESSES / 2; i < MAXPROCESSES; i++) { + if (i - MAXPROCESSES / 2) + fprintf(stderr, " | "); + if (processes[i] && processes[i]->active) { + fprintf(stderr, " %02d", i); + } else { + fprintf(stderr, " --"); + } + } + fprintf(stderr, "\n"); + fprintf(stderr, "pc "); + for (i = MAXPROCESSES / 2; i < MAXPROCESSES; i++) { + if (i - MAXPROCESSES / 2) + fprintf(stderr, " | "); + if (processes[i] && processes[i]->active) { + fprintf(stderr, "%04ld", processes[i]->pc); + } else { + fprintf(stderr, "----"); + } + } + fprintf(stderr, "\n"); + for (j = 0; j < MAXPROCPAGES; j++) { + fprintf(stderr, "page%02d ", j); + for (i = MAXPROCESSES / 2; i < MAXPROCESSES; i++) { + if (i - MAXPROCESSES / 2) + fprintf(stderr, " |"); + if (processes[i] && processes[i]->active) { + int pcblock = processes[i]->pc / PAGESIZE; + if (j == pcblock) { + if (processes[i]->pages[j] > 0) + fprintf(stderr, "*i%3ld", processes[i]->pages[j]); + else if (processes[i]->pages[j] == 0) + fprintf(stderr, "*=in "); + else if (processes[i]->pages[j] == -100) + fprintf(stderr, "*=out"); + else + fprintf(stderr, "*o%3ld", 100 + processes[i]->pages[j]); + // fprintf(stderr,"*%4d",processes[i]->pages[j]); + } else { + if (processes[i]->pages[j] > 0) + fprintf(stderr, " i%3ld", processes[i]->pages[j]); + else if (processes[i]->pages[j] == 0) + fprintf(stderr, " =in "); + else if (processes[i]->pages[j] == -100) + fprintf(stderr, " =out"); + else + fprintf(stderr, " o%3ld", 100 + processes[i]->pages[j]); + // fprintf(stderr," %4d",processes[i]->pages[j]); + } + } else { + fprintf(stderr, " ----"); + } + } + fprintf(stderr, "\n"); + } + fprintf(stderr, "------------------------------------------------------------" + "----------------\n"); +} + +static void endit() { + allprint(); + exit(0); +} + +static void allinit() { + long i; + initqueue(); + for (i = 0; i < MAXPROCESSES; i++) + processes[i] = NULL; + for (i = 0; i < procs; i++) { + // zero out pages from processes + if (!empty()) { + processes[i] = dequeue(); + + sim_log(LOG_LOAD, "process %2d; pc %04d: loaded\n", i, processes[i]->pc); + if (output) + fprintf(output, "%ld,%ld,%ld,%ld,%ld,load\n", sysclock, i, + processes[i]->pid, processes[i]->kind, processes[i]->pc); + if (pages) { + long j; + for (j = 0; j < MAXPROCPAGES; j++) + fprintf(pages, "%ld,%ld,%ld,%ld,%ld,out\n", sysclock, i, j, + processes[i]->pid, processes[i]->kind); + } + } + } +} + +static void allscore() { + int i; + int block = 0; + int compute = 0; + for (i = 0; i < QUEUESIZE; i++) { + block += queue[i].block; + compute += queue[i].compute; + } + sim_log(LOG_ALWAYS, "simulation ends\n"); + sim_log(LOG_ALWAYS, "%d blocked cycles\n", block); + sim_log(LOG_ALWAYS, "%d compute cycles\n", compute); + sim_log(LOG_ALWAYS, "ratio blocked/compute=%g\n", + (double)block / (double)compute); +} + +static void allstep() { + long i; + for (i = 0; i < procs; i++) { + if (!process_step(i, processes[i])) { + if (processes[i] && processes[i]->active) { + // document final PC position + if (output) + fprintf(output, "%ld,%ld,%ld,%ld,%ld,unload\n", sysclock, i, + processes[i]->pid, processes[i]->kind, processes[i]->pc); + if (pages) { + long j; + for (j = 0; j < MAXPROCPAGES; j++) + fprintf(pages, "%ld,%ld,%ld,%ld,%ld,out\n", sysclock, i, j, + processes[i]->pid, processes[i]->kind); + } + process_unload(i, processes[i]); + } + processes[i] = NULL; + if (!empty()) { + processes[i] = dequeue(); + sim_log(LOG_LOAD, "process %2d; pc %04d: loaded\n", i, + processes[i]->pc); + if (output) + fprintf(output, "%ld,%ld,%ld,%ld,%ld,load\n", sysclock, i, + processes[i]->pid, processes[i]->kind, processes[i]->pc); + } + } + } +} + +static long alldone() { + long i; + for (i = 0; i < procs; i++) { + if (processes[i] && processes[i]->active) + return FALSE; + } + return TRUE; +} + +static int allblocked() { + int allfree = 0; + int runnable = 0; + int memwait = 0; + int freewait = 0; + int i, stat; + for (i = 0; i < procs; i++) + if (processes[i] && processes[i]->active) { + stat = processes[i]->pages[(int)(processes[i]->pc / PAGESIZE)]; + if (stat > 0) + memwait++; /* waiting for swap in */ + else if (stat == 0) + runnable++; /* ok */ + else if (stat < -PAGEWAIT) + allfree++; /* free */ + else + freewait++; /* waiting for swap out */ + } + + if (allfree && !memwait && !runnable && !freewait) { + sim_log(LOG_DEAD, "%d process pcs waiting for swap in\n", memwait); + sim_log(LOG_DEAD, "%d process pcs runnable\n", runnable); + sim_log(LOG_DEAD, "%d process pcs waiting for swap out\n", freewait); + sim_log(LOG_DEAD, "%d process pcs swapped out\n", allfree); + sim_log(LOG_DEAD, "All needed pages swapped out!\n"); + // allprint(); + return 1; + } else { + return 0; + } +} + +static void allage() { + long i; + for (i = 0; i < procs; i++) { + if (processes[i] && processes[i]->active) { + long j; + for (j = 0; j < processes[i]->npages; j++) { + if (processes[i]->pages[j] == 0) + ; + else if (processes[i]->pages[j] < -PAGEWAIT) + ; + else if (processes[i]->pages[j] > 0) { + processes[i]->pages[j]--; + if (processes[i]->pages[j] == 0) { + sim_log(LOG_PAGE, "process=%2d page=%3d end pagein\n", i, j); + if (pages) + fprintf(pages, "%ld,%ld,%ld,%ld,%ld,in\n", sysclock, i, j, + processes[i]->pid, processes[i]->kind); + } + } else if (processes[i]->pages[j] < 0 && + processes[i]->pages[j] >= -PAGEWAIT) { + processes[i]->pages[j]--; + if (processes[i]->pages[j] < -PAGEWAIT) { + sim_log(LOG_PAGE, "process=%2d page=%3d end pageout\n", i, j); + if (pages) + fprintf(pages, "%ld,%ld,%ld,%ld,%ld,out\n", sysclock, i, j, + processes[i]->pid, processes[i]->kind); + pagesavail++; + } + } + } + } + } +} + +static void callyou() { + long i, j; + Pentry pentry[MAXPROCESSES]; + for (i = 0; i < MAXPROCESSES; i++) { + if (processes[i]) { + pentry[i].active = processes[i]->active; + pentry[i].pc = processes[i]->pc; + pentry[i].npages = processes[i]->npages; + for (j = 0; j < processes[i]->npages; j++) { + pentry[i].pages[j] = (processes[i]->pages[j] == 0); + } + for (; j < MAXPROCPAGES; j++) + pentry[i].pages[j] = FALSE; + } else { + pentry[i].active = FALSE; + pentry[i].pc = 0; + pentry[i].npages = 0; + for (j = 0; j < MAXPROCPAGES; j++) + pentry[i].pages[j] = FALSE; + } + } + pageit(pentry); /* call your routine */ +} + +int main(int argc, char **argv) { + + long i, errors = 0, help = 0; + + signal(SIGINT, endit); + + log_port = LOG_ALWAYS; + for (i = 1; i < argc; i++) { + if (strcmp(argv[i], "-help") == 0) { + help++; + } else if (strcmp(argv[i], "-all") == 0) { + log_port |= LOG_LOAD | LOG_BLOCK | LOG_PAGE | LOG_BRANCH; + } else if (strcmp(argv[i], "-load") == 0) { + log_port |= LOG_LOAD; + } else if (strcmp(argv[i], "-block") == 0) { + log_port |= LOG_BLOCK; + } else if (strcmp(argv[i], "-page") == 0) { + log_port |= LOG_PAGE; + } else if (strcmp(argv[i], "-branch") == 0) { + log_port |= LOG_BRANCH; + } else if (strcmp(argv[i], "-dead") == 0) { + log_port |= LOG_DEAD; + } else if (strcmp(argv[i], "-seed") == 0) { + if (sscanf(argv[++i], "%ld", &seed) != 1) { + fprintf(stderr, "%s: could not read random seed from command line\n", + argv[0]); + errors++; + } else if (seed < 1 || seed > ((1 << 30) - 1)) { + fprintf(stderr, "%s: random seed must be between 1 and %d\n", argv[0], + (1 << 30) - 1); + errors++; + } + } else if (strcmp(argv[i], "-csv") == 0) { + output = fopen("output.csv", "w"); + if (!output) { + fprintf(stderr, "%s: could not open output.csv for writing\n", argv[0]); + errors++; + } + pages = fopen("pages.csv", "w"); + if (!pages) { + fprintf(stderr, "%s: could not open pages.csv for writing\n", argv[0]); + errors++; + } + } else if (strcmp(argv[i], "-procs") == 0) { + if (sscanf(argv[++i], "%ld", &procs) != 1) { + fprintf(stderr, + "%s: could not read number of processors from command line\n", + argv[0]); + errors++; + } else if (procs < 1 || procs > MAXPROCESSES) { + fprintf(stderr, "%s: number of processors must be between 1 and %d\n", + argv[0], MAXPROCESSES); + errors++; + } + } else { + fprintf(stderr, "t4: unrecognized argument %s\n", argv[i]); + errors++; + } + } + if (errors || help) { + fprintf(stderr, "%s usage: %s \n", argv[0], argv[0]); + fprintf(stderr, " -all log everything\n"); + fprintf(stderr, " -load log loading of processes\n"); + fprintf(stderr, " -unload log unloading of processes\n"); + fprintf(stderr, " -branch log program branches\n"); + fprintf(stderr, " -page log page in and out\n"); + fprintf(stderr, " -seed 512 set random seed to 512\n"); + fprintf(stderr, " -procs 4 run only four processors\n"); + fprintf(stderr, " -dead detect deadlocks\n"); + fprintf(stderr, + " -csv generate output.csv and pages.csv for graphing\n"); + if (errors) { + return EXIT_FAILURE; + } else { + return EXIT_SUCCESS; + } + } + if (seed == 0) { + seed = (time(NULL) * 38491 + 71831 + time(NULL) * time(NULL)) & + ((1 << 30) - 1); + } + srand48(seed); + sim_log(LOG_ALWAYS, "random seed %d\n", seed); + sim_log(LOG_ALWAYS, "using %d processors\n", procs); + + allinit(); + while (!alldone()) { // all processes inactive + allstep(); // advance time one tick; if process done, reload + allage(); // advance time for page wait variables. + callyou(); // call your program + sysclock++; // remember new time. + allblocked(); // deadlock detection + } + allscore(); + + return EXIT_SUCCESS; +} diff --git a/pa8_predict/simulator.h b/pa8_predict/simulator.h new file mode 100644 index 0000000..38160ad --- /dev/null +++ b/pa8_predict/simulator.h @@ -0,0 +1,111 @@ +/* + * File: simulator.h + * + * Original Author: Dr. Alva Couch + * http://www.cs.tufts.edu/~couch/ + */ + +#define TRUE 1 +#define FALSE 0 + +#define MAXPROCPAGES 20 /* max pages per individual process */ +#define MAXPROCESSES 20 /* max number of processes in runqueue */ +#define PAGESIZE 128 /* size of an individual page */ +#define PAGEWAIT 100 /* wait for paging in */ +#define PHYSICALPAGES 100 /* number of available physical pages */ +#define QUEUESIZE 40 /* total number of processes to run */ +#define PROGRAMS 10 /* total number of program types */ + +#define MAXBRANCHES 40 /* number of branches in a program */ +#define MAXEXITS 10 /* number of maximum exits per program */ +#define MAXBRINGS 100 /* must be EVEN! data points in branch table */ +#define MAXPC (MAXPROCPAGES * PAGESIZE) /* largest PC value */ + +struct pentry { + long active; + long pc; + long npages; + long pages[MAXPROCPAGES]; /* 0 if not allocated, 1 if allocated */ +}; + +typedef struct pentry Pentry; + +/* int pagein (int process, int page) + * This pages in the requested page + * Arguments: + * proc: process to work upon (0-19) + * page: page to put in (0-19) + * Returns: + * 1 if pagein started, already running, or paged in + * 0 if it can't start (e.g., swapping out) + */ +extern int pagein(int process, int page); + +/* int pageout(int process, int page) + * This pages out the requested page. + * Arguments: + * proc: process to work upon (0-19) + * page: page to swap out. + * Returns: + * 1 if pageout started, already running, or paged out + * 0 if can't start (e.g., swapping in) + */ +extern int pageout(int process, int page); + +/* void pageit(Pentry q[MAXPROCESSES]) + * This is called by the simulator + * every time something interesting occurs. + * It is where you implement the paging strategy. + * Arguments: + * q: state of every process + * Returns: + * void + */ +extern void pageit(Pentry q[MAXPROCESSES]); + +typedef enum { GOTO, FOR, NFOR, IF } BranchType; + +/* abstract description of a branch + describes qualitative behavior, not actual branching */ +typedef struct branch { + long wherefrom; + long whereto; + BranchType btype; + long min, max; + double prob; + long extent; +} Branch; + +typedef struct program { + long size; + long nbranches; + Branch branches[MAXBRANCHES]; + long nexits; + long exits[MAXEXITS]; /* which statements are "halt" */ +} Program; + +// branch context: determines which branch to +// take next in a probabilistic situation... +typedef struct bcontext { + BranchType btype; + long boffset; /* offset into brings array */ + long bsize; /* size of brings array */ + long bvalue; /* which branch direction to take */ + long bcount; /* value of current decrement */ + long brings[MAXBRINGS]; +} Bcontext; + +typedef struct process { + Program *program; + long nbcontexts; + Bcontext bcontexts[MAXBRANCHES]; + long pc; /* program counter */ + long npages; + long pages[MAXPROCPAGES]; /* whether page is available */ + long blocked[MAXPROCPAGES]; /* whether we've reported page state */ + long active; /* whether running now */ + long compute; /* number of compute ticks */ + long block; /* number of blocked ticks */ + long pid; /* unique process number */ + long kind; /* kind of process from table */ +} Process; |