aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-04-05 12:51:41 -0600
committerJack Sangdahl <[email protected]>2024-04-05 12:51:41 -0600
commitc84d6705c618dc4700c4aae1975d332ee2898920 (patch)
tree0963a7f6206d64b26cfba9aa380fd77ef5edc405
parent95558865f08e3a612b624624ae9d4a604b3db7f5 (diff)
downloadcsci3753-c84d6705c618dc4700c4aae1975d332ee2898920.tar.gz
csci3753-c84d6705c618dc4700c4aae1975d332ee2898920.zip
pa7
-rw-r--r--pa7_lru/Makefile40
-rw-r--r--pa7_lru/image1.jpgbin0 -> 43494 bytes
-rw-r--r--pa7_lru/image2.jpgbin0 -> 36764 bytes
-rw-r--r--pa7_lru/pager-basic.c29
-rw-r--r--pa7_lru/pager-lru.c33
-rw-r--r--pa7_lru/programs.c60
-rw-r--r--pa7_lru/readme.md215
-rw-r--r--pa7_lru/see.R505
-rw-r--r--pa7_lru/simulator.c835
-rw-r--r--pa7_lru/simulator.h111
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
new file mode 100644
index 0000000..1844471
--- /dev/null
+++ b/pa7_lru/image1.jpg
Binary files differ
diff --git a/pa7_lru/image2.jpg b/pa7_lru/image2.jpg
new file mode 100644
index 0000000..0ae7fc9
--- /dev/null
+++ b/pa7_lru/image2.jpg
Binary files differ
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;