diff options
author | Jack Sangdahl <[email protected]> | 2024-04-05 12:51:41 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-04-05 12:51:41 -0600 |
commit | c84d6705c618dc4700c4aae1975d332ee2898920 (patch) | |
tree | 0963a7f6206d64b26cfba9aa380fd77ef5edc405 | |
parent | 95558865f08e3a612b624624ae9d4a604b3db7f5 (diff) | |
download | csci3753-c84d6705c618dc4700c4aae1975d332ee2898920.tar.gz csci3753-c84d6705c618dc4700c4aae1975d332ee2898920.zip |
pa7
-rw-r--r-- | pa7_lru/Makefile | 40 | ||||
-rw-r--r-- | pa7_lru/image1.jpg | bin | 0 -> 43494 bytes | |||
-rw-r--r-- | pa7_lru/image2.jpg | bin | 0 -> 36764 bytes | |||
-rw-r--r-- | pa7_lru/pager-basic.c | 29 | ||||
-rw-r--r-- | pa7_lru/pager-lru.c | 33 | ||||
-rw-r--r-- | pa7_lru/programs.c | 60 | ||||
-rw-r--r-- | pa7_lru/readme.md | 215 | ||||
-rw-r--r-- | pa7_lru/see.R | 505 | ||||
-rw-r--r-- | pa7_lru/simulator.c | 835 | ||||
-rw-r--r-- | pa7_lru/simulator.h | 111 |
10 files changed, 1828 insertions, 0 deletions
diff --git a/pa7_lru/Makefile b/pa7_lru/Makefile new file mode 100644 index 0000000..fd76806 --- /dev/null +++ b/pa7_lru/Makefile @@ -0,0 +1,40 @@ +# CSCI3753 - FA23 PA7 + +CC = gcc +CFLAGS = -c -g -Wall -Wextra +LFLAGS = -g -Wall -Wextra + +SUBMITFILES = pager-lru.c + +.PHONY: all clean + +all: test-basic test-lru + +test-basic: simulator.o pager-basic.o programs.o + $(CC) $(LFLAGS) $^ -o $@ + +test-lru: simulator.o pager-lru.o programs.o + $(CC) $(LFLAGS) $^ -o $@ + +simulator.o: simulator.c programs.o simulator.h + $(CC) $(CFLAGS) $< + +programs.o: programs.c simulator.h + $(CC) $(CFLAGS) $< + +pager-basic.o: pager-basic.c simulator.h programs.c + $(CC) $(CFLAGS) $< + +pager-lru.o: pager-lru.c simulator.h programs.c + $(CC) $(CFLAGS) $< + +clean: + rm -f test-basic test-lru test-predict test-api + rm -f *.o + rm -f *~ + rm -f *.csv + rm -f *.pdf + +submit: + @read -r -p "please enter your identikey username: " username; \ + tar -cvf PA7-$$username.txt $(SUBMITFILES) diff --git a/pa7_lru/image1.jpg b/pa7_lru/image1.jpg Binary files differnew file mode 100644 index 0000000..1844471 --- /dev/null +++ b/pa7_lru/image1.jpg diff --git a/pa7_lru/image2.jpg b/pa7_lru/image2.jpg Binary files differnew file mode 100644 index 0000000..0ae7fc9 --- /dev/null +++ b/pa7_lru/image2.jpg diff --git a/pa7_lru/pager-basic.c b/pa7_lru/pager-basic.c new file mode 100644 index 0000000..8d1399d --- /dev/null +++ b/pa7_lru/pager-basic.c @@ -0,0 +1,29 @@ +// Very basic pageit algorithm, only allows one process at a time, and one page +// in memory + +#include "simulator.h" + +void pageit(Pentry q[MAXPROCESSES]) { + for (int proc = 0; proc < MAXPROCESSES; proc++) { + if (q[proc].active != 1) + continue; // select only active processes + + int pc = q[proc].pc; // program counter for process + int page = pc / PAGESIZE; // current page the PC is on + + if (q[proc].pages[page]) + break; // if the page is already in memory, then we're done + if (pagein(proc, page)) + break; // if not in memory, then page it in + + for (int vic = 0; + vic++ < MAXPROCPAGES;) { // if the pagein fails, find pages to pageout + if (q[proc].pages[page] != 1) + continue; // only interested in pages that are in memory + if (vic == page) + continue; // make sure the incoming page isn't considered + if (pageout(proc, vic) == 1) + break; // page it out and we're done if successful + } + } +} diff --git a/pa7_lru/pager-lru.c b/pa7_lru/pager-lru.c new file mode 100644 index 0000000..b60b704 --- /dev/null +++ b/pa7_lru/pager-lru.c @@ -0,0 +1,33 @@ +// Jack Sangdahl +// CSCI3753 SP24 +// PA7 LRU +#include "simulator.h" +#include <stdbool.h> + +void pageit(Pentry q[MAXPROCESSES]) { + static int timestamps[MAXPROCESSES][MAXPROCPAGES], tick = 1; + static bool initialised = false; + if (!initialised) { + for (int proc = 0; proc < MAXPROCESSES; proc++) + for (int page = 0; page < MAXPROCPAGES; page++) + timestamps[proc][page] = 0; + initialised = true; + } + for (int proc = 0; proc < MAXPROCESSES; proc++) { + if (q[proc].active) { + int curr = q[proc].pc / PAGESIZE; + timestamps[proc][curr] = tick; + if (!q[proc].pages[curr]) + if (!pagein(proc, curr)) { + int min = tick, choice; + for (int i = 0; i < q[proc].npages; i++) + if (timestamps[proc][i] < min && q[proc].pages[i]) { + choice = i; + min = timestamps[proc][i]; + } + pageout(proc, choice); + } + } + } + tick++; +} diff --git a/pa7_lru/programs.c b/pa7_lru/programs.c new file mode 100644 index 0000000..7a1cfb1 --- /dev/null +++ b/pa7_lru/programs.c @@ -0,0 +1,60 @@ +/* + * File: programs.c + * + * Original Author: Dr. Alva Couch + * http://www.cs.tufts.edu/~couch/ + */ + +#include "simulator.h" + +Program programs[PROGRAMS] = { + {1535, + 3, + { + {500, 1402, IF, 0, 0, 0.6, 0}, + {1401, 1533, GOTO, 0, 0, 1, 0}, + {1533, 0, FOR, 10, 30, 0, 0}, + }, + 1, + { + 1534, + }}, + {1131, + 1, + { + {1129, 0, FOR, 20, 50, 0, 0}, + }, + 1, + { + 1130, + }}, + {1685, + 2, + { + {1682, 1166, FOR, 10, 20, 0, 0}, + {1683, 0, FOR, 10, 20, 0, 0}, + }, + 1, + { + 1684, + }}, + {1912, + 0, + {}, + 1, + { + 1911, + }}, + {505, + 4, + { + {500, 503, IF, 0, 0, 0.5, 0}, + {501, 0, GOTO, 0, 0, 1, 0}, + {502, 503, GOTO, 0, 0, 1, 0}, + {503, 0, FOR, 10, 20, 0, 0}, + }, + 1, + { + 504, + }}, +}; diff --git a/pa7_lru/readme.md b/pa7_lru/readme.md new file mode 100644 index 0000000..e1d7300 --- /dev/null +++ b/pa7_lru/readme.md @@ -0,0 +1,215 @@ +## PA7 - LRU +### introduction +modern operating systems use virtual memory and paging in order to +effectively utilise the computer's memory hierarchy. paging provides +memory space protection to processes, enables the use of secondary +storage, and also removes the need to allocate memory sequentially for +each process. we have studied how virtual memory systems are structured +and how the mmu converts virtual memory addresses to physical memory +addresses by means of a page table and a tlb. when a page has a valid +mapping from a virtual memory address to a physical address, we say the +page is swapped in. when no valid mapping is available, the page is +either invalid (segmentation fault) or more likely, swapped out. when +the mmu determines that a memory request requires access to a page that +is currently swapped out, it calls the operating system's page fault +handler. this handler must swap in the necessary page, possibly +evicting another page to secondary memory in the process. it then +retries the offending memory access and hands control back to the mmu. +as you may imaging, how the os chooses which page to evict when it has +reached the limit of available physical pages (frames) can have a +major effect on the performance of memory access on a given system. in +this assignment, we will look at the various strategies for managing +the system page table and controlling when pages are paged and out. + +### assignment +the goal of this assignment is to implement a paging strategy that +maximises the performance of the memory access in a set of predefined +programs. you will accomplish this by using a paging simulator that +has been created for you. your job is to write the paging strategy that +the simulator utilises. your initial goal will be to create a least +recently used (lru) paging implementation. you will then implement a +predictive paging algorithm for pa8, with the intent of increasing the +performance of your paging policy. you will be graded on the throughput +of your solution (the ratio of time spent doing useful work vs. time +spent waiting on necessary paging to occur). + +### paging simulator environment +the paging simulator has been provided. you have access to the source +code if you wish to review it (`simulator.{c,h}`), but you should not +need to modify the code. you will be graded using the unmodified +simulator, so any enhancements to the simulator program made with the +intention of improving your performance will be for naught. the +simulator runs a random set of programs utilising a limited number of +shared physical pages. each process has a fixed number of virtual +pages (that compose the process's virtual memory space) that it might +try to access. for the purpose of this simulation, all memory access is +due to the need to load program code. the simulated program counter for +each process dictates which memory location that process currently +requires access to, and thus which virtual page must be swapped in for +the process to successfully continue. the values of contants mentioned +above are available in the `simulator.h` file. for the purpose of +grading, the default values will be used: + +* 20 virtual pages per process (`MAXPROCPAGES`) +* 20 simultaneous processes competing for pages (`MAXPROCESSES`) +* 128 memory unit page size (`PAGESIZE`) +* 100 tick delay to sway a page in or out (`PAGEWAIT`) +* 100 physical pages (frames) total (`PHYSICALPAGES`) +* 40 processes run in total (`QUEUESIZE`) + +as you can see, you are working in a very resource constrained +environment. you will have to deal with attempts to access up to 400 +virtual pages (20 processes times 20 virtual pages per process), but +may only have at most 100 physical pages swapped in at any given time. +in addition, swapping a page in or out is an expensive operation, +requiring 100 ticks to complete. a tick is the minimum time unit used +in the simulator. each instruction or step in the simulated programs +requires one tick to complete. thus, in the worst case where every +instruction is a page miss (requiring a swap in), you will spend 100 +ticks of paging overhead for every 1 tick of useful work. if all +physical pages are in use, this turns into 200 ticks per page miss +since you must also spend 100 ticks swapping a page out in order to +make room for the required page to be swapped in. this leads to an +overhead to useful work ratio 200:1, which is very poor performance. +your goal is to implement a system that does much better than this. + +### simulator interface +the simulator exports three functions which you will use to interact with it: `pageit()`, `pagein()`, and `pageout()`. the first function +`pageit()`, is the core paging function. it is roughly equivalent to +the page fault handler in your operating system. the simulator calls +`pageit()` anytime something interesting happens (memory access, page +fault, process completion, etc.) or basically every cpu cycle, which +we'll refer to as a tick. it passes the function a page map for each +process, as well as the current value of the program counter for each +process. see `simulator.h` for details. you will implement your paging +strategy in the body of this function. the `pageit()` function is +passed an array of pentry structs, one per process. this struct +contains a copy of all the necessary memory information that the +simulator maintains for each process. you will most likely need the +information contained in this struct to make intelligent paging +decisions. you can read these fields as necessary, but should not write +to them, as any changes you make will be lost when you return from +`pageit()` + +| variable | behaviour | +|---|---| +| `long active` | flag indicating whether or not the process has been completed. 1 running, 0 exited. | +| `long pc` | value of program counter for the process. the current page can be calculated as `page = pc / PAGESIZE` | +| `long npages` | number of pages in the processes memory space. if the process is active, this will be equal to `MAXPROCPAGES`, otherwise 0 | +| `long pages[MAXPROCPAGES]` | array representing the page map for a given process. if `pages[i]` is 0, page `i` is swapped out, swapping, or swapping in. if `pages[i]` is 1, page `i` is current swapped in | + +the simulator also exports the functions `pagein()` and `pageout()`, +which are used to request that a specific page for a specific process +be paged in or out. you will use these functions to control the +allocation of virtual and physical pages when writing your paging +strategy. note that a page will be marked as swapped out as soon as +the `pageout()` request is made, but is not recognised as swapped in +until after the `pagein()` request completes 100 ticks later. `pagein()` +and `pageout()` will return a 1 if they succeed in starting a paging +operation, if the requested paging operation is already in progress, +or if the requested state already exists 100 ticks after requesting +a paging operation, the operation will complete. these functions +return 0 if the paging request can not be processed (due to exceeding +the limit of physical pages or because another paging operation is +currently in process on the requested page) or if the request is +invalid (paging operation requests non-existent page, etc.). see +figure 1 below for more details on function behaviour +![possible page states and transitions](image1.png) +the above shows the possible states that a virtual page can occupy, as +well as the possible transitions between these states. note that the +page map values alone do not define all possible page states. we must +also account for the possible operations currently underway on a page +to fully define its state. while the page map for each process can be +obtained from the `pageit()` input array of structs, there is no +interface to directly reveal any operations underway on a given page. +if knowing whether or not a paging operation is underway on a given +page is necessary for your `pageit()` implementation, you must +maintain the data yourself. + +### simulated programs +the simulator populates its 20 concurrent processes by randomly +creating them from a collection of 5 types of simulated programs. +pseudo code for each of the possible 5 programs is given below. + +#### program 1 - loop with inner branch +``` +for 10 30 + run 500 + if .4 + run 900 + else + run 131 + endif +end +exit +``` + +#### program 2 - single loop +``` +for 20 50 + run 1129 +end +exit +``` + +#### program 3 - double nested loop +``` +for 10 20 + run 1166 + for 10 20 + run 516 + end +end +exit +``` + +#### program 4 - linear +``` +run 1911 +exit +``` + +#### program 5 - probabilistic backward branch +``` +for 10 20 + label: + run 500 + if .5 + goto label + endif +end +exit +``` +note that while you know the structure of these programs, any program +flow is still probabilistic in nature. which branch a specific process +takes, how many loop iterations occur, or how long sequential runs are +will be dependent upon the random seed generated by the simulator. +thus, you may never be able to perfectly predict the execution of a +process, only the probabilistic likelihood of a collection of possible +execution paths. + +### implementation ideas +in general, your `pageit()` implementation will need to follow the +basic flow presented in figure 2 below. you will probably spend most +of your time deciding how to implement the "select a page to evict" +element. +![basic reactive pageit](image2.jpg) +a basic "one process at a time" implementation is provided for you. +this implementation never actually ends up having to swap out any +pages. since only one process is allocated at a time, no more than 20 +pages are ever in use. when each process completes, it releases all of +its pages and the next process is allowed to allocate pages and run. +this is a very simple solution, and you might expect it does not +provide very good performance. still, it provides a demonstration of +the simulator api in use. see `pager-basic.c` for more information. + +to start, create some form of least recently used algorithm. an lru +algorithm selects a page that has not been accessed for some time when +it must swap a page out to make room for a new page to be swapped in. +an lru algorithm can either operate globally across all processes, or +locally to a given process and ony allow each process to compete for +pages from this subset. a stub for implementing an lru version of +`pageit()` has been created for you in the `pager-lru.c` file. note +that use of static variables in order to preserve local state between +calls to `pageit()`. your lru algorithm should perform much better +than the trivial solution provided by the `pager-basic.c` algorithm. diff --git a/pa7_lru/see.R b/pa7_lru/see.R new file mode 100644 index 0000000..17a2c02 --- /dev/null +++ b/pa7_lru/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/pa7_lru/simulator.c b/pa7_lru/simulator.c new file mode 100644 index 0000000..38d959b --- /dev/null +++ b/pa7_lru/simulator.c @@ -0,0 +1,835 @@ +/* + * 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,repeats; + for (i=0; i<QUEUESIZE; i++) queuetype[i]=lrand48()%PROGRAMS; + 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++) { + queuetype[i] = i % PROGRAMS; + 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/pa7_lru/simulator.h b/pa7_lru/simulator.h new file mode 100644 index 0000000..dccb4c2 --- /dev/null +++ b/pa7_lru/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 5 /* 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; |