From 4bf6f6c396c2961dd7c7b435686c84aa5ad25591 Mon Sep 17 00:00:00 2001 From: jack <0x6A73@pm.me> Date: Fri, 26 Apr 2024 21:41:25 -0600 Subject: move shared code to dir --- common/hostname_data/names1.txt | 23 ++ common/hostname_data/names11.txt | 23 ++ common/hostname_data/names12.txt | 20 + common/hostname_data/names13.txt | 20 + common/hostname_data/names14.txt | 20 + common/hostname_data/names15.txt | 20 + common/hostname_data/names2.txt | 20 + common/hostname_data/names21.txt | 23 ++ common/hostname_data/names22.txt | 20 + common/hostname_data/names23.txt | 20 + common/hostname_data/names24.txt | 20 + common/hostname_data/names25.txt | 20 + common/hostname_data/names3.txt | 20 + common/hostname_data/names31.txt | 23 ++ common/hostname_data/names32.txt | 20 + common/hostname_data/names33.txt | 20 + common/hostname_data/names34.txt | 20 + common/hostname_data/names35.txt | 20 + common/hostname_data/names4.txt | 20 + common/hostname_data/names41.txt | 23 ++ common/hostname_data/names42.txt | 20 + common/hostname_data/names43.txt | 20 + common/hostname_data/names44.txt | 20 + common/hostname_data/names45.txt | 20 + common/hostname_data/names5.txt | 20 + common/hostname_data/names51.txt | 23 ++ common/hostname_data/names52.txt | 20 + common/hostname_data/names53.txt | 20 + common/hostname_data/names54.txt | 20 + common/hostname_data/names55.txt | 20 + common/see.R | 505 +++++++++++++++++++++++ common/simulator.c | 837 +++++++++++++++++++++++++++++++++++++++ common/simulator.h | 111 ++++++ hostname_data/names1.txt | 23 -- hostname_data/names11.txt | 23 -- hostname_data/names12.txt | 20 - hostname_data/names13.txt | 20 - hostname_data/names14.txt | 20 - hostname_data/names15.txt | 20 - hostname_data/names2.txt | 20 - hostname_data/names21.txt | 23 -- hostname_data/names22.txt | 20 - hostname_data/names23.txt | 20 - hostname_data/names24.txt | 20 - hostname_data/names25.txt | 20 - hostname_data/names3.txt | 20 - hostname_data/names31.txt | 23 -- hostname_data/names32.txt | 20 - hostname_data/names33.txt | 20 - hostname_data/names34.txt | 20 - hostname_data/names35.txt | 20 - hostname_data/names4.txt | 20 - hostname_data/names41.txt | 23 -- hostname_data/names42.txt | 20 - hostname_data/names43.txt | 20 - hostname_data/names44.txt | 20 - hostname_data/names45.txt | 20 - hostname_data/names5.txt | 20 - hostname_data/names51.txt | 23 -- hostname_data/names52.txt | 20 - hostname_data/names53.txt | 20 - hostname_data/names54.txt | 20 - hostname_data/names55.txt | 20 - pa7_lru/Makefile | 2 + pa7_lru/pager-basic.c | 2 +- pa7_lru/pager-lru.c | 2 +- pa7_lru/programs.c | 2 +- pa7_lru/see.R | 505 ----------------------- pa7_lru/simulator.c | 835 -------------------------------------- pa7_lru/simulator.h | 111 ------ pa8_predict/Makefile | 2 + pa8_predict/pager-predict.c | 2 +- pa8_predict/see.R | 505 ----------------------- pa8_predict/simulator.c | 837 --------------------------------------- pa8_predict/simulator.h | 111 ------ 75 files changed, 2079 insertions(+), 3526 deletions(-) create mode 100644 common/hostname_data/names1.txt create mode 100644 common/hostname_data/names11.txt create mode 100644 common/hostname_data/names12.txt create mode 100644 common/hostname_data/names13.txt create mode 100644 common/hostname_data/names14.txt create mode 100644 common/hostname_data/names15.txt create mode 100644 common/hostname_data/names2.txt create mode 100644 common/hostname_data/names21.txt create mode 100644 common/hostname_data/names22.txt create mode 100644 common/hostname_data/names23.txt create mode 100644 common/hostname_data/names24.txt create mode 100644 common/hostname_data/names25.txt create mode 100644 common/hostname_data/names3.txt create mode 100644 common/hostname_data/names31.txt create mode 100644 common/hostname_data/names32.txt create mode 100644 common/hostname_data/names33.txt create mode 100644 common/hostname_data/names34.txt create mode 100644 common/hostname_data/names35.txt create mode 100644 common/hostname_data/names4.txt create mode 100644 common/hostname_data/names41.txt create mode 100644 common/hostname_data/names42.txt create mode 100644 common/hostname_data/names43.txt create mode 100644 common/hostname_data/names44.txt create mode 100644 common/hostname_data/names45.txt create mode 100644 common/hostname_data/names5.txt create mode 100644 common/hostname_data/names51.txt create mode 100644 common/hostname_data/names52.txt create mode 100644 common/hostname_data/names53.txt create mode 100644 common/hostname_data/names54.txt create mode 100644 common/hostname_data/names55.txt create mode 100644 common/see.R create mode 100644 common/simulator.c create mode 100644 common/simulator.h delete mode 100644 hostname_data/names1.txt delete mode 100644 hostname_data/names11.txt delete mode 100644 hostname_data/names12.txt delete mode 100644 hostname_data/names13.txt delete mode 100644 hostname_data/names14.txt delete mode 100644 hostname_data/names15.txt delete mode 100644 hostname_data/names2.txt delete mode 100644 hostname_data/names21.txt delete mode 100644 hostname_data/names22.txt delete mode 100644 hostname_data/names23.txt delete mode 100644 hostname_data/names24.txt delete mode 100644 hostname_data/names25.txt delete mode 100644 hostname_data/names3.txt delete mode 100644 hostname_data/names31.txt delete mode 100644 hostname_data/names32.txt delete mode 100644 hostname_data/names33.txt delete mode 100644 hostname_data/names34.txt delete mode 100644 hostname_data/names35.txt delete mode 100644 hostname_data/names4.txt delete mode 100644 hostname_data/names41.txt delete mode 100644 hostname_data/names42.txt delete mode 100644 hostname_data/names43.txt delete mode 100644 hostname_data/names44.txt delete mode 100644 hostname_data/names45.txt delete mode 100644 hostname_data/names5.txt delete mode 100644 hostname_data/names51.txt delete mode 100644 hostname_data/names52.txt delete mode 100644 hostname_data/names53.txt delete mode 100644 hostname_data/names54.txt delete mode 100644 hostname_data/names55.txt delete mode 100644 pa7_lru/see.R delete mode 100644 pa7_lru/simulator.c delete mode 100644 pa7_lru/simulator.h delete mode 100644 pa8_predict/see.R delete mode 100644 pa8_predict/simulator.c delete mode 100644 pa8_predict/simulator.h diff --git a/common/hostname_data/names1.txt b/common/hostname_data/names1.txt new file mode 100644 index 0000000..d43eb9d --- /dev/null +++ b/common/hostname_data/names1.txt @@ -0,0 +1,23 @@ +facebook.com +youtube.com +yahoo.com +live.com +wikipedia.org +msn.com +baidu.com +blogspot.com +microsoft.com +qq.com +taobao.com +bing.com +sina.com.cn +soso.com +163.com +ask.com +adobe.com +twitter.com +mozilla.com +youku.com +sdjjdsaf.com +andysayler.com +wmfo.org diff --git a/common/hostname_data/names11.txt b/common/hostname_data/names11.txt new file mode 100644 index 0000000..d43eb9d --- /dev/null +++ b/common/hostname_data/names11.txt @@ -0,0 +1,23 @@ +facebook.com +youtube.com +yahoo.com +live.com +wikipedia.org +msn.com +baidu.com +blogspot.com +microsoft.com +qq.com +taobao.com +bing.com +sina.com.cn +soso.com +163.com +ask.com +adobe.com +twitter.com +mozilla.com +youku.com +sdjjdsaf.com +andysayler.com +wmfo.org diff --git a/common/hostname_data/names12.txt b/common/hostname_data/names12.txt new file mode 100644 index 0000000..89943e7 --- /dev/null +++ b/common/hostname_data/names12.txt @@ -0,0 +1,20 @@ +amazon.com +wordpress.com +tudou.com +yahoo.co.jp +sohu.com +apple.com +hao123.com +windows.com +ebay.com +pps.tv +xunlei.com +56.com +fc2.com +paypal.com +sogou.com +tmall.com +ku6.com +rakuten.co.jp +about.com +orkut.com.br diff --git a/common/hostname_data/names13.txt b/common/hostname_data/names13.txt new file mode 100644 index 0000000..1ec9d3f --- /dev/null +++ b/common/hostname_data/names13.txt @@ -0,0 +1,20 @@ +ifeng.com +goo.ne.jp +bbc.co.uk +yandex.ru +myspace.com +mail.ru +cnet.com +go.com +4399.com +orkut.com +skype.com +ameblo.jp +naver.com +flickr.com +4shared.com +amazon.co.jp +linkedin.com +dailymotion.com +imdb.com +aol.com diff --git a/common/hostname_data/names14.txt b/common/hostname_data/names14.txt new file mode 100644 index 0000000..940a57c --- /dev/null +++ b/common/hostname_data/names14.txt @@ -0,0 +1,20 @@ +hotmail.com +360.cn +craigslist.org +weather.com +soku.com +alibaba.com +megaupload.com +renren.com +livedoor.jp +blogger.com +vkontakte.ru +answers.com +rapidshare.com +daum.net +7k7k.com +2345.com +photobucket.com +mediafire.com +ehow.com +seesaa.net diff --git a/common/hostname_data/names15.txt b/common/hostname_data/names15.txt new file mode 100644 index 0000000..e7f8366 --- /dev/null +++ b/common/hostname_data/names15.txt @@ -0,0 +1,20 @@ +paipai.com +alipay.com +softonic.com +nifty.com +imageshack.us +cnn.com +tianya.cn +mywebsearch.com +zynga.com +partypoker.com +hp.com +walmart.com +kugou.com +ebay.de +youdao.com +hotfile.com +qiyi.com +pconline.com.cn +odnoklassniki.ru +jp.msn.com diff --git a/common/hostname_data/names2.txt b/common/hostname_data/names2.txt new file mode 100644 index 0000000..89943e7 --- /dev/null +++ b/common/hostname_data/names2.txt @@ -0,0 +1,20 @@ +amazon.com +wordpress.com +tudou.com +yahoo.co.jp +sohu.com +apple.com +hao123.com +windows.com +ebay.com +pps.tv +xunlei.com +56.com +fc2.com +paypal.com +sogou.com +tmall.com +ku6.com +rakuten.co.jp +about.com +orkut.com.br diff --git a/common/hostname_data/names21.txt b/common/hostname_data/names21.txt new file mode 100644 index 0000000..d43eb9d --- /dev/null +++ b/common/hostname_data/names21.txt @@ -0,0 +1,23 @@ +facebook.com +youtube.com +yahoo.com +live.com +wikipedia.org +msn.com +baidu.com +blogspot.com +microsoft.com +qq.com +taobao.com +bing.com +sina.com.cn +soso.com +163.com +ask.com +adobe.com +twitter.com +mozilla.com +youku.com +sdjjdsaf.com +andysayler.com +wmfo.org diff --git a/common/hostname_data/names22.txt b/common/hostname_data/names22.txt new file mode 100644 index 0000000..89943e7 --- /dev/null +++ b/common/hostname_data/names22.txt @@ -0,0 +1,20 @@ +amazon.com +wordpress.com +tudou.com +yahoo.co.jp +sohu.com +apple.com +hao123.com +windows.com +ebay.com +pps.tv +xunlei.com +56.com +fc2.com +paypal.com +sogou.com +tmall.com +ku6.com +rakuten.co.jp +about.com +orkut.com.br diff --git a/common/hostname_data/names23.txt b/common/hostname_data/names23.txt new file mode 100644 index 0000000..1ec9d3f --- /dev/null +++ b/common/hostname_data/names23.txt @@ -0,0 +1,20 @@ +ifeng.com +goo.ne.jp +bbc.co.uk +yandex.ru +myspace.com +mail.ru +cnet.com +go.com +4399.com +orkut.com +skype.com +ameblo.jp +naver.com +flickr.com +4shared.com +amazon.co.jp +linkedin.com +dailymotion.com +imdb.com +aol.com diff --git a/common/hostname_data/names24.txt b/common/hostname_data/names24.txt new file mode 100644 index 0000000..940a57c --- /dev/null +++ b/common/hostname_data/names24.txt @@ -0,0 +1,20 @@ +hotmail.com +360.cn +craigslist.org +weather.com +soku.com +alibaba.com +megaupload.com +renren.com +livedoor.jp +blogger.com +vkontakte.ru +answers.com +rapidshare.com +daum.net +7k7k.com +2345.com +photobucket.com +mediafire.com +ehow.com +seesaa.net diff --git a/common/hostname_data/names25.txt b/common/hostname_data/names25.txt new file mode 100644 index 0000000..e7f8366 --- /dev/null +++ b/common/hostname_data/names25.txt @@ -0,0 +1,20 @@ +paipai.com +alipay.com +softonic.com +nifty.com +imageshack.us +cnn.com +tianya.cn +mywebsearch.com +zynga.com +partypoker.com +hp.com +walmart.com +kugou.com +ebay.de +youdao.com +hotfile.com +qiyi.com +pconline.com.cn +odnoklassniki.ru +jp.msn.com diff --git a/common/hostname_data/names3.txt b/common/hostname_data/names3.txt new file mode 100644 index 0000000..1ec9d3f --- /dev/null +++ b/common/hostname_data/names3.txt @@ -0,0 +1,20 @@ +ifeng.com +goo.ne.jp +bbc.co.uk +yandex.ru +myspace.com +mail.ru +cnet.com +go.com +4399.com +orkut.com +skype.com +ameblo.jp +naver.com +flickr.com +4shared.com +amazon.co.jp +linkedin.com +dailymotion.com +imdb.com +aol.com diff --git a/common/hostname_data/names31.txt b/common/hostname_data/names31.txt new file mode 100644 index 0000000..d43eb9d --- /dev/null +++ b/common/hostname_data/names31.txt @@ -0,0 +1,23 @@ +facebook.com +youtube.com +yahoo.com +live.com +wikipedia.org +msn.com +baidu.com +blogspot.com +microsoft.com +qq.com +taobao.com +bing.com +sina.com.cn +soso.com +163.com +ask.com +adobe.com +twitter.com +mozilla.com +youku.com +sdjjdsaf.com +andysayler.com +wmfo.org diff --git a/common/hostname_data/names32.txt b/common/hostname_data/names32.txt new file mode 100644 index 0000000..89943e7 --- /dev/null +++ b/common/hostname_data/names32.txt @@ -0,0 +1,20 @@ +amazon.com +wordpress.com +tudou.com +yahoo.co.jp +sohu.com +apple.com +hao123.com +windows.com +ebay.com +pps.tv +xunlei.com +56.com +fc2.com +paypal.com +sogou.com +tmall.com +ku6.com +rakuten.co.jp +about.com +orkut.com.br diff --git a/common/hostname_data/names33.txt b/common/hostname_data/names33.txt new file mode 100644 index 0000000..1ec9d3f --- /dev/null +++ b/common/hostname_data/names33.txt @@ -0,0 +1,20 @@ +ifeng.com +goo.ne.jp +bbc.co.uk +yandex.ru +myspace.com +mail.ru +cnet.com +go.com +4399.com +orkut.com +skype.com +ameblo.jp +naver.com +flickr.com +4shared.com +amazon.co.jp +linkedin.com +dailymotion.com +imdb.com +aol.com diff --git a/common/hostname_data/names34.txt b/common/hostname_data/names34.txt new file mode 100644 index 0000000..940a57c --- /dev/null +++ b/common/hostname_data/names34.txt @@ -0,0 +1,20 @@ +hotmail.com +360.cn +craigslist.org +weather.com +soku.com +alibaba.com +megaupload.com +renren.com +livedoor.jp +blogger.com +vkontakte.ru +answers.com +rapidshare.com +daum.net +7k7k.com +2345.com +photobucket.com +mediafire.com +ehow.com +seesaa.net diff --git a/common/hostname_data/names35.txt b/common/hostname_data/names35.txt new file mode 100644 index 0000000..e7f8366 --- /dev/null +++ b/common/hostname_data/names35.txt @@ -0,0 +1,20 @@ +paipai.com +alipay.com +softonic.com +nifty.com +imageshack.us +cnn.com +tianya.cn +mywebsearch.com +zynga.com +partypoker.com +hp.com +walmart.com +kugou.com +ebay.de +youdao.com +hotfile.com +qiyi.com +pconline.com.cn +odnoklassniki.ru +jp.msn.com diff --git a/common/hostname_data/names4.txt b/common/hostname_data/names4.txt new file mode 100644 index 0000000..940a57c --- /dev/null +++ b/common/hostname_data/names4.txt @@ -0,0 +1,20 @@ +hotmail.com +360.cn +craigslist.org +weather.com +soku.com +alibaba.com +megaupload.com +renren.com +livedoor.jp +blogger.com +vkontakte.ru +answers.com +rapidshare.com +daum.net +7k7k.com +2345.com +photobucket.com +mediafire.com +ehow.com +seesaa.net diff --git a/common/hostname_data/names41.txt b/common/hostname_data/names41.txt new file mode 100644 index 0000000..d43eb9d --- /dev/null +++ b/common/hostname_data/names41.txt @@ -0,0 +1,23 @@ +facebook.com +youtube.com +yahoo.com +live.com +wikipedia.org +msn.com +baidu.com +blogspot.com +microsoft.com +qq.com +taobao.com +bing.com +sina.com.cn +soso.com +163.com +ask.com +adobe.com +twitter.com +mozilla.com +youku.com +sdjjdsaf.com +andysayler.com +wmfo.org diff --git a/common/hostname_data/names42.txt b/common/hostname_data/names42.txt new file mode 100644 index 0000000..89943e7 --- /dev/null +++ b/common/hostname_data/names42.txt @@ -0,0 +1,20 @@ +amazon.com +wordpress.com +tudou.com +yahoo.co.jp +sohu.com +apple.com +hao123.com +windows.com +ebay.com +pps.tv +xunlei.com +56.com +fc2.com +paypal.com +sogou.com +tmall.com +ku6.com +rakuten.co.jp +about.com +orkut.com.br diff --git a/common/hostname_data/names43.txt b/common/hostname_data/names43.txt new file mode 100644 index 0000000..1ec9d3f --- /dev/null +++ b/common/hostname_data/names43.txt @@ -0,0 +1,20 @@ +ifeng.com +goo.ne.jp +bbc.co.uk +yandex.ru +myspace.com +mail.ru +cnet.com +go.com +4399.com +orkut.com +skype.com +ameblo.jp +naver.com +flickr.com +4shared.com +amazon.co.jp +linkedin.com +dailymotion.com +imdb.com +aol.com diff --git a/common/hostname_data/names44.txt b/common/hostname_data/names44.txt new file mode 100644 index 0000000..940a57c --- /dev/null +++ b/common/hostname_data/names44.txt @@ -0,0 +1,20 @@ +hotmail.com +360.cn +craigslist.org +weather.com +soku.com +alibaba.com +megaupload.com +renren.com +livedoor.jp +blogger.com +vkontakte.ru +answers.com +rapidshare.com +daum.net +7k7k.com +2345.com +photobucket.com +mediafire.com +ehow.com +seesaa.net diff --git a/common/hostname_data/names45.txt b/common/hostname_data/names45.txt new file mode 100644 index 0000000..e7f8366 --- /dev/null +++ b/common/hostname_data/names45.txt @@ -0,0 +1,20 @@ +paipai.com +alipay.com +softonic.com +nifty.com +imageshack.us +cnn.com +tianya.cn +mywebsearch.com +zynga.com +partypoker.com +hp.com +walmart.com +kugou.com +ebay.de +youdao.com +hotfile.com +qiyi.com +pconline.com.cn +odnoklassniki.ru +jp.msn.com diff --git a/common/hostname_data/names5.txt b/common/hostname_data/names5.txt new file mode 100644 index 0000000..e7f8366 --- /dev/null +++ b/common/hostname_data/names5.txt @@ -0,0 +1,20 @@ +paipai.com +alipay.com +softonic.com +nifty.com +imageshack.us +cnn.com +tianya.cn +mywebsearch.com +zynga.com +partypoker.com +hp.com +walmart.com +kugou.com +ebay.de +youdao.com +hotfile.com +qiyi.com +pconline.com.cn +odnoklassniki.ru +jp.msn.com diff --git a/common/hostname_data/names51.txt b/common/hostname_data/names51.txt new file mode 100644 index 0000000..d43eb9d --- /dev/null +++ b/common/hostname_data/names51.txt @@ -0,0 +1,23 @@ +facebook.com +youtube.com +yahoo.com +live.com +wikipedia.org +msn.com +baidu.com +blogspot.com +microsoft.com +qq.com +taobao.com +bing.com +sina.com.cn +soso.com +163.com +ask.com +adobe.com +twitter.com +mozilla.com +youku.com +sdjjdsaf.com +andysayler.com +wmfo.org diff --git a/common/hostname_data/names52.txt b/common/hostname_data/names52.txt new file mode 100644 index 0000000..89943e7 --- /dev/null +++ b/common/hostname_data/names52.txt @@ -0,0 +1,20 @@ +amazon.com +wordpress.com +tudou.com +yahoo.co.jp +sohu.com +apple.com +hao123.com +windows.com +ebay.com +pps.tv +xunlei.com +56.com +fc2.com +paypal.com +sogou.com +tmall.com +ku6.com +rakuten.co.jp +about.com +orkut.com.br diff --git a/common/hostname_data/names53.txt b/common/hostname_data/names53.txt new file mode 100644 index 0000000..1ec9d3f --- /dev/null +++ b/common/hostname_data/names53.txt @@ -0,0 +1,20 @@ +ifeng.com +goo.ne.jp +bbc.co.uk +yandex.ru +myspace.com +mail.ru +cnet.com +go.com +4399.com +orkut.com +skype.com +ameblo.jp +naver.com +flickr.com +4shared.com +amazon.co.jp +linkedin.com +dailymotion.com +imdb.com +aol.com diff --git a/common/hostname_data/names54.txt b/common/hostname_data/names54.txt new file mode 100644 index 0000000..940a57c --- /dev/null +++ b/common/hostname_data/names54.txt @@ -0,0 +1,20 @@ +hotmail.com +360.cn +craigslist.org +weather.com +soku.com +alibaba.com +megaupload.com +renren.com +livedoor.jp +blogger.com +vkontakte.ru +answers.com +rapidshare.com +daum.net +7k7k.com +2345.com +photobucket.com +mediafire.com +ehow.com +seesaa.net diff --git a/common/hostname_data/names55.txt b/common/hostname_data/names55.txt new file mode 100644 index 0000000..e7f8366 --- /dev/null +++ b/common/hostname_data/names55.txt @@ -0,0 +1,20 @@ +paipai.com +alipay.com +softonic.com +nifty.com +imageshack.us +cnn.com +tianya.cn +mywebsearch.com +zynga.com +partypoker.com +hp.com +walmart.com +kugou.com +ebay.de +youdao.com +hotfile.com +qiyi.com +pconline.com.cn +odnoklassniki.ru +jp.msn.com diff --git a/common/see.R b/common/see.R new file mode 100644 index 0000000..17a2c02 --- /dev/null +++ b/common/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$time0) { +# 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/common/simulator.c b/common/simulator.c new file mode 100644 index 0000000..58a5800 --- /dev/null +++ b/common/simulator.c @@ -0,0 +1,837 @@ +/* + * File: simulator.c + * + * Original Author: Dr. Alva Couch + * http://www.cs.tufts.edu/~couch/ + */ + +#include +#include +#include +#include +#include +#include +#include + +#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 +#include +#include + +// shorthands for assertion handling +#define CHECK(bool) check((bool), #bool, __FILE__, __LINE__) +#define ASSERT(bool) assert((bool), #bool, __FILE__, __LINE__) +#define POSIT(bool) posit((bool), #bool, __FILE__, __LINE__) +#define DIE(reason) die((reason), __FILE__, __LINE__) +#define CARP(reason) carp((reason), __FILE__, __LINE__) + +// always print the result of a test +inline void check(int boolean, char *boolstr, char *file, int line) { + if (!boolean) { + fprintf(stderr, "ERROR: %s failed in line %d of file %s\n", boolstr, line, + file); + } else { + fprintf(stderr, "%s succeeded in line %d of file %s\n", boolstr, line, + file); + } +} + +// die if an assertion fails. +static inline void assert(int boolean, char *boolstr, char *file, int line) { + if (!boolean) { + fprintf(stderr, "Assertion %s failed in line %d of file %s\n", boolstr, + line, file); + exit(1); /* exit(0) means correct execution! */ + } +} + +// report failing assertions without bombing out... keeps running +inline int posit(int boolean, char *boolstr, char *file, int line) { + if (!boolean) + fprintf(stderr, "Assertion %s failed in line %d of file %s\n", boolstr, + line, file); + return boolean; +} + +// die on a fatal error +inline void die(char *condition, char *file, int line) { + fprintf(stderr, "Fatal error: %s at line %d of file %s\n", condition, line, + file); + exit(1); +} + +// print a non-fatal error +inline void carp(char *condition, char *file, int line) { + fprintf(stderr, "Non-fatal error: %s at line %d of file %s\n", condition, + line, file); +} + +static long log_port = LOG_ALWAYS; // logging ports for output +static void sim_log(long type, const char *format, ...) { + va_list ap; + if (log_port & type) { + va_start(ap, format); + fprintf(stderr, "%08ld: ", sysclock); + vfprintf(stderr, format, ap); + va_end(ap); + } +} + +/* keep track of physical page usage */ +static long pagesavail = PHYSICALPAGES; + +static Process *processes[MAXPROCESSES]; + +/* make a binary decision according to a + probability distribution */ +static long binary(double prob) { + if (drand48() < prob) + return 1; + else + return 0; +} + +/* clear a branching engine */ +static void bcontext_clear(Bcontext *c) { + long i; + c->bcount = 0; + c->boffset = 0; + c->bsize = 1; + c->bvalue = 1; + c->brings[0] = 1; + for (i = 1; i < MAXBRINGS; i++) + c->brings[i] = 0; +} + +/* initialize a branching engine */ +static void bcontext_init(Bcontext *c, Branch *b) { + long i; + c->bcount = 0; + c->btype = b->btype; + if (b->btype == GOTO) { + c->boffset = 0; + c->bsize = 1; + c->bvalue = 1; + // c->brings[0]=1; /* old version */ + c->brings[0] = 0x7fffffff; /* keep going forever */ + for (i = 1; i < MAXBRINGS; i++) + c->brings[i] = 0; + } else if (b->btype == IF) { + long cvalue; + c->boffset = 0; + c->bsize = 0; + cvalue = c->bvalue = binary(b->prob); + c->bcount = 0; + // compute future values for if statements + while (c->bsize < MAXBRINGS) { + if (binary(b->prob) == cvalue) { + c->brings[c->bsize]++; + } else { + c->bsize++; + c->brings[c->bsize] = 1; + cvalue = !cvalue; + } + } + } else if (b->btype == FOR) { + c->boffset = 0; + c->bvalue = 1; + c->bsize = 0; + while (c->bsize < MAXBRINGS) { + if (b->max > b->min) { + c->brings[c->bsize++] = lrand48() % (b->max - b->min) + b->min; + } else { + c->brings[c->bsize++] = b->min; + } + c->brings[c->bsize++] = 1; // one failure to escape loop + } + } else if (b->btype == NFOR) { + c->boffset = 0; + c->bvalue = 0; + c->bsize = 0; + while (c->bsize < MAXBRINGS) { + if (b->max > b->min) { + c->brings[c->bsize++] = lrand48() % (b->max - b->min) + b->min; + } else { + c->brings[c->bsize++] = b->min; + } + c->brings[c->bsize++] = 1; // one failure to escape loop + } + } else { + fprintf(stderr, "unknown btype %ld\n", (long)(b->btype)); + } +} + +/* decide whether to branch or not */ +static long bcontext_decide(Bcontext *c) { + long ret = c->bvalue; + c->bcount++; + ASSERT(c->boffset >= 0 && c->boffset < MAXBRINGS); + if (c->bcount >= c->brings[c->boffset]) { + c->boffset = (c->boffset + 1) % c->bsize; + // ASSERT(c->boffset>0); // no wrapping! + c->bcount = 0; + c->bvalue = !c->bvalue; + } + return ret; +} + +static void process_clear(Process *q) { + long i; + q->pc = 0; + q->compute = q->block = 0; + q->program = NULL; + q->pid = -1; + q->kind = -1; + q->nbcontexts = 0; + for (i = 0; i < MAXBRANCHES; i++) { + bcontext_clear(q->bcontexts + i); + } + q->npages = 0; + /* no physical pages assigned */ + for (i = 0; i < MAXPROCPAGES; i++) { + q->pages[i] = -PAGEWAIT - 1; + q->blocked[i] = FALSE; // ALC: so simulator will log first access + } + q->active = FALSE; +} + +/* load a program into a process */ +static void process_load(Process *q, Program *p, int pid, int kind) { + long i; + q->pc = 0; + q->compute = q->block = 0; + q->program = p; + q->pid = pid; + q->kind = kind; + q->nbcontexts = p->nbranches; + ASSERT(p->nbranches >= 0 && p->nbranches < MAXBRANCHES); + for (i = 0; i < p->nbranches; i++) { + bcontext_init(q->bcontexts + i, p->branches + i); + } + // fprintf(stderr,"actual page size for process is %d\n", + // (q->program->size+PAGESIZE-1)/PAGESIZE); + q->npages = MAXPROCPAGES; + for (i = 0; i < MAXPROCPAGES; i++) { + q->pages[i] = -PAGEWAIT - 1; + q->blocked[i] = FALSE; // ALC: so simulator will log first access + } + /* no physical pages assigned */ + q->active = TRUE; /* now running */ +} + +/* unload a process and release all resources */ +static void process_unload(int pnum, Process *q) { + long i; + for (i = 0; i < q->npages; i++) + if (q->pages[i] >= -PAGEWAIT) { + pagesavail++; + q->pages[i] = -PAGEWAIT - 1; + q->blocked[i] = 1; + } + q->active = FALSE; + sim_log(LOG_LOAD, "process %2d; pc %04d: unloaded\n", pnum, q->pc); +} + +/* do a branch if necessary */ +static void process_dobranch(int pnum, Process *q, Branch *b, Bcontext *c) { + if (bcontext_decide(c)) { + // must document where we branched from + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,branch_from\n", sysclock, pnum, + q->pid, q->kind, q->pc); + q->pc = b->whereto; + // and where we branched to + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,branch_to\n", sysclock, pnum, q->pid, + q->kind, q->pc); + sim_log(LOG_BRANCH, "process %2d; pc %04d: branch\n", pnum, q->pc); + } else { + q->pc++; + sim_log(LOG_BRANCH, "process %2d; pc %04d: no branch\n", pnum, q->pc); + } + if (q->pc < 0 || q->pc >= q->program->size) + q->pc = 0; /* start over */ +} + +/* compute one step of a process */ +static long process_step(int pnum, Process *q) { + long pc; + long page; + long max, min; + Branch *b; + Bcontext *c; + + if (!q) + return FALSE; + pc = q->pc; + page = q->pc / PAGESIZE; + if (!q->active) { + return FALSE; + } + + /* if page swapped out, don't allow to run */ + if (q->pages[page] != 0) { + if (!q->blocked[page]) { + sim_log(LOG_BLOCK, "process=%2d page=%3d blocked\n", pnum, page); + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,blocked\n", sysclock, pnum, q->pid, + q->kind, q->pc); + q->blocked[page] = TRUE; + } + q->block++; + return TRUE; + } else { + if (q->blocked[page]) { + sim_log(LOG_BLOCK, "process=%2d page=%3d unblocked\n", pnum, page); + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,unblocked\n", sysclock, pnum, + q->pid, q->kind, q->pc); + q->blocked[page] = FALSE; + } + q->compute++; + } + + /* should I exit */ + ASSERT(q->program->nexits >= 0 && q->program->nexits <= MAXEXITS); + min = 0; + max = q->program->nexits - 1; + while (min + 1 < max) { + long mid = (min + max) / 2; + if (pc == q->program->exits[mid]) { + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,exit\n", sysclock, pnum, q->pid, + q->kind, q->pc); + return FALSE; + } else if (pc < q->program->exits[mid]) + max = mid; + else + min = mid; + } + if (pc == q->program->exits[min] || pc == q->program->exits[max]) { + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,exit\n", sysclock, pnum, q->pid, + q->kind, q->pc); + return FALSE; + } + b = q->program->branches; + c = q->bcontexts; + ASSERT(q->program->nbranches >= 0 && q->program->nbranches <= MAXBRANCHES); + min = 0; + max = q->program->nbranches - 1; + while (min + 1 < max) { + long mid = (min + max) / 2; + if (pc == b[mid].wherefrom) { + process_dobranch(pnum, q, b + mid, c + mid); + return TRUE; + } else if (pc < b[mid].wherefrom) + max = mid; + else + min = mid; + } + if (pc == b[min].wherefrom) { + process_dobranch(pnum, q, b + min, c + min); + return TRUE; + } + if (pc == b[max].wherefrom) { + process_dobranch(pnum, q, b + max, c + max); + return TRUE; + } + q->pc++; /* default action */ + if (q->pc < 0 || q->pc > q->program->size) { + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,out_of_range\n", sysclock, pnum, + q->pid, q->kind, q->pc); + q->pc = 0; /* start over */ + if (output) + fprintf(output, "%ld,%d,%ld,%ld,%ld,restart\n", sysclock, pnum, q->pid, + q->kind, q->pc); + } + return TRUE; +} + +/* public routine: swap one page out */ +int pageout(int process, int page) { + if (process < 0 || process >= procs || !processes[process] || + !processes[process]->active || page < 0 || + page >= processes[process]->npages) + return FALSE; + if (processes[process]->pages[page] < 0) + return TRUE; /* on its way out */ + if (processes[process]->pages[page] > 0) + return FALSE; /* not available to swap out */ + sim_log(LOG_PAGE, "process=%2d page=%3d start pageout\n", process, page); + if (pages) + fprintf(pages, "%ld,%d,%d,%ld,%ld,going\n", sysclock, process, page, + processes[process]->pid, processes[process]->kind); + processes[process]->pages[page] = -1; + return TRUE; +} + +/* public routine: swap one page in */ +int pagein(int process, int page) { + if (process < 0 || process >= procs || !processes[process] || + !processes[process]->active || page < 0 || + page >= processes[process]->npages) + return FALSE; + if (processes[process]->pages[page] >= 0) + return TRUE; /* on its way */ + if (pagesavail == 0) + return FALSE; + if (processes[process]->pages[page] >= -PAGEWAIT) + return FALSE; /* not yet out */ + sim_log(LOG_PAGE, "process=%2d page=%3d start pagein\n", process, page); + if (pages) + fprintf(pages, "%ld,%d,%d,%ld,%ld,coming\n", sysclock, process, page, + processes[process]->pid, processes[process]->kind); + processes[process]->pages[page] = PAGEWAIT; + pagesavail--; + return TRUE; +} + +/*============ + job queue + ============*/ + +static long queuetype[QUEUESIZE]; +static Process queue[QUEUESIZE]; +static long queueend; +static void initqueue() { + long i; + for (i = 0; i < QUEUESIZE; i++) + queuetype[i] = lrand48() % PROGRAMS; + /* + long repeats; + for (repeats=0; repeats<10; repeats++) + for (i=0; i= QUEUESIZE; } + +/*=========================== + 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/common/simulator.h b/common/simulator.h new file mode 100644 index 0000000..38160ad --- /dev/null +++ b/common/simulator.h @@ -0,0 +1,111 @@ +/* + * File: simulator.h + * + * Original Author: Dr. Alva Couch + * http://www.cs.tufts.edu/~couch/ + */ + +#define TRUE 1 +#define FALSE 0 + +#define MAXPROCPAGES 20 /* max pages per individual process */ +#define MAXPROCESSES 20 /* max number of processes in runqueue */ +#define PAGESIZE 128 /* size of an individual page */ +#define PAGEWAIT 100 /* wait for paging in */ +#define PHYSICALPAGES 100 /* number of available physical pages */ +#define QUEUESIZE 40 /* total number of processes to run */ +#define PROGRAMS 10 /* total number of program types */ + +#define MAXBRANCHES 40 /* number of branches in a program */ +#define MAXEXITS 10 /* number of maximum exits per program */ +#define MAXBRINGS 100 /* must be EVEN! data points in branch table */ +#define MAXPC (MAXPROCPAGES * PAGESIZE) /* largest PC value */ + +struct pentry { + long active; + long pc; + long npages; + long pages[MAXPROCPAGES]; /* 0 if not allocated, 1 if allocated */ +}; + +typedef struct pentry Pentry; + +/* int pagein (int process, int page) + * This pages in the requested page + * Arguments: + * proc: process to work upon (0-19) + * page: page to put in (0-19) + * Returns: + * 1 if pagein started, already running, or paged in + * 0 if it can't start (e.g., swapping out) + */ +extern int pagein(int process, int page); + +/* int pageout(int process, int page) + * This pages out the requested page. + * Arguments: + * proc: process to work upon (0-19) + * page: page to swap out. + * Returns: + * 1 if pageout started, already running, or paged out + * 0 if can't start (e.g., swapping in) + */ +extern int pageout(int process, int page); + +/* void pageit(Pentry q[MAXPROCESSES]) + * This is called by the simulator + * every time something interesting occurs. + * It is where you implement the paging strategy. + * Arguments: + * q: state of every process + * Returns: + * void + */ +extern void pageit(Pentry q[MAXPROCESSES]); + +typedef enum { GOTO, FOR, NFOR, IF } BranchType; + +/* abstract description of a branch + describes qualitative behavior, not actual branching */ +typedef struct branch { + long wherefrom; + long whereto; + BranchType btype; + long min, max; + double prob; + long extent; +} Branch; + +typedef struct program { + long size; + long nbranches; + Branch branches[MAXBRANCHES]; + long nexits; + long exits[MAXEXITS]; /* which statements are "halt" */ +} Program; + +// branch context: determines which branch to +// take next in a probabilistic situation... +typedef struct bcontext { + BranchType btype; + long boffset; /* offset into brings array */ + long bsize; /* size of brings array */ + long bvalue; /* which branch direction to take */ + long bcount; /* value of current decrement */ + long brings[MAXBRINGS]; +} Bcontext; + +typedef struct process { + Program *program; + long nbcontexts; + Bcontext bcontexts[MAXBRANCHES]; + long pc; /* program counter */ + long npages; + long pages[MAXPROCPAGES]; /* whether page is available */ + long blocked[MAXPROCPAGES]; /* whether we've reported page state */ + long active; /* whether running now */ + long compute; /* number of compute ticks */ + long block; /* number of blocked ticks */ + long pid; /* unique process number */ + long kind; /* kind of process from table */ +} Process; diff --git a/hostname_data/names1.txt b/hostname_data/names1.txt deleted file mode 100644 index d43eb9d..0000000 --- a/hostname_data/names1.txt +++ /dev/null @@ -1,23 +0,0 @@ -facebook.com -youtube.com -yahoo.com -live.com -wikipedia.org -msn.com -baidu.com -blogspot.com -microsoft.com -qq.com -taobao.com -bing.com -sina.com.cn -soso.com -163.com -ask.com -adobe.com -twitter.com -mozilla.com -youku.com -sdjjdsaf.com -andysayler.com -wmfo.org diff --git a/hostname_data/names11.txt b/hostname_data/names11.txt deleted file mode 100644 index d43eb9d..0000000 --- a/hostname_data/names11.txt +++ /dev/null @@ -1,23 +0,0 @@ -facebook.com -youtube.com -yahoo.com -live.com -wikipedia.org -msn.com -baidu.com -blogspot.com -microsoft.com -qq.com -taobao.com -bing.com -sina.com.cn -soso.com -163.com -ask.com -adobe.com -twitter.com -mozilla.com -youku.com -sdjjdsaf.com -andysayler.com -wmfo.org diff --git a/hostname_data/names12.txt b/hostname_data/names12.txt deleted file mode 100644 index 89943e7..0000000 --- a/hostname_data/names12.txt +++ /dev/null @@ -1,20 +0,0 @@ -amazon.com -wordpress.com -tudou.com -yahoo.co.jp -sohu.com -apple.com -hao123.com -windows.com -ebay.com -pps.tv -xunlei.com -56.com -fc2.com -paypal.com -sogou.com -tmall.com -ku6.com -rakuten.co.jp -about.com -orkut.com.br diff --git a/hostname_data/names13.txt b/hostname_data/names13.txt deleted file mode 100644 index 1ec9d3f..0000000 --- a/hostname_data/names13.txt +++ /dev/null @@ -1,20 +0,0 @@ -ifeng.com -goo.ne.jp -bbc.co.uk -yandex.ru -myspace.com -mail.ru -cnet.com -go.com -4399.com -orkut.com -skype.com -ameblo.jp -naver.com -flickr.com -4shared.com -amazon.co.jp -linkedin.com -dailymotion.com -imdb.com -aol.com diff --git a/hostname_data/names14.txt b/hostname_data/names14.txt deleted file mode 100644 index 940a57c..0000000 --- a/hostname_data/names14.txt +++ /dev/null @@ -1,20 +0,0 @@ -hotmail.com -360.cn -craigslist.org -weather.com -soku.com -alibaba.com -megaupload.com -renren.com -livedoor.jp -blogger.com -vkontakte.ru -answers.com -rapidshare.com -daum.net -7k7k.com -2345.com -photobucket.com -mediafire.com -ehow.com -seesaa.net diff --git a/hostname_data/names15.txt b/hostname_data/names15.txt deleted file mode 100644 index e7f8366..0000000 --- a/hostname_data/names15.txt +++ /dev/null @@ -1,20 +0,0 @@ -paipai.com -alipay.com -softonic.com -nifty.com -imageshack.us -cnn.com -tianya.cn -mywebsearch.com -zynga.com -partypoker.com -hp.com -walmart.com -kugou.com -ebay.de -youdao.com -hotfile.com -qiyi.com -pconline.com.cn -odnoklassniki.ru -jp.msn.com diff --git a/hostname_data/names2.txt b/hostname_data/names2.txt deleted file mode 100644 index 89943e7..0000000 --- a/hostname_data/names2.txt +++ /dev/null @@ -1,20 +0,0 @@ -amazon.com -wordpress.com -tudou.com -yahoo.co.jp -sohu.com -apple.com -hao123.com -windows.com -ebay.com -pps.tv -xunlei.com -56.com -fc2.com -paypal.com -sogou.com -tmall.com -ku6.com -rakuten.co.jp -about.com -orkut.com.br diff --git a/hostname_data/names21.txt b/hostname_data/names21.txt deleted file mode 100644 index d43eb9d..0000000 --- a/hostname_data/names21.txt +++ /dev/null @@ -1,23 +0,0 @@ -facebook.com -youtube.com -yahoo.com -live.com -wikipedia.org -msn.com -baidu.com -blogspot.com -microsoft.com -qq.com -taobao.com -bing.com -sina.com.cn -soso.com -163.com -ask.com -adobe.com -twitter.com -mozilla.com -youku.com -sdjjdsaf.com -andysayler.com -wmfo.org diff --git a/hostname_data/names22.txt b/hostname_data/names22.txt deleted file mode 100644 index 89943e7..0000000 --- a/hostname_data/names22.txt +++ /dev/null @@ -1,20 +0,0 @@ -amazon.com -wordpress.com -tudou.com -yahoo.co.jp -sohu.com -apple.com -hao123.com -windows.com -ebay.com -pps.tv -xunlei.com -56.com -fc2.com -paypal.com -sogou.com -tmall.com -ku6.com -rakuten.co.jp -about.com -orkut.com.br diff --git a/hostname_data/names23.txt b/hostname_data/names23.txt deleted file mode 100644 index 1ec9d3f..0000000 --- a/hostname_data/names23.txt +++ /dev/null @@ -1,20 +0,0 @@ -ifeng.com -goo.ne.jp -bbc.co.uk -yandex.ru -myspace.com -mail.ru -cnet.com -go.com -4399.com -orkut.com -skype.com -ameblo.jp -naver.com -flickr.com -4shared.com -amazon.co.jp -linkedin.com -dailymotion.com -imdb.com -aol.com diff --git a/hostname_data/names24.txt b/hostname_data/names24.txt deleted file mode 100644 index 940a57c..0000000 --- a/hostname_data/names24.txt +++ /dev/null @@ -1,20 +0,0 @@ -hotmail.com -360.cn -craigslist.org -weather.com -soku.com -alibaba.com -megaupload.com -renren.com -livedoor.jp -blogger.com -vkontakte.ru -answers.com -rapidshare.com -daum.net -7k7k.com -2345.com -photobucket.com -mediafire.com -ehow.com -seesaa.net diff --git a/hostname_data/names25.txt b/hostname_data/names25.txt deleted file mode 100644 index e7f8366..0000000 --- a/hostname_data/names25.txt +++ /dev/null @@ -1,20 +0,0 @@ -paipai.com -alipay.com -softonic.com -nifty.com -imageshack.us -cnn.com -tianya.cn -mywebsearch.com -zynga.com -partypoker.com -hp.com -walmart.com -kugou.com -ebay.de -youdao.com -hotfile.com -qiyi.com -pconline.com.cn -odnoklassniki.ru -jp.msn.com diff --git a/hostname_data/names3.txt b/hostname_data/names3.txt deleted file mode 100644 index 1ec9d3f..0000000 --- a/hostname_data/names3.txt +++ /dev/null @@ -1,20 +0,0 @@ -ifeng.com -goo.ne.jp -bbc.co.uk -yandex.ru -myspace.com -mail.ru -cnet.com -go.com -4399.com -orkut.com -skype.com -ameblo.jp -naver.com -flickr.com -4shared.com -amazon.co.jp -linkedin.com -dailymotion.com -imdb.com -aol.com diff --git a/hostname_data/names31.txt b/hostname_data/names31.txt deleted file mode 100644 index d43eb9d..0000000 --- a/hostname_data/names31.txt +++ /dev/null @@ -1,23 +0,0 @@ -facebook.com -youtube.com -yahoo.com -live.com -wikipedia.org -msn.com -baidu.com -blogspot.com -microsoft.com -qq.com -taobao.com -bing.com -sina.com.cn -soso.com -163.com -ask.com -adobe.com -twitter.com -mozilla.com -youku.com -sdjjdsaf.com -andysayler.com -wmfo.org diff --git a/hostname_data/names32.txt b/hostname_data/names32.txt deleted file mode 100644 index 89943e7..0000000 --- a/hostname_data/names32.txt +++ /dev/null @@ -1,20 +0,0 @@ -amazon.com -wordpress.com -tudou.com -yahoo.co.jp -sohu.com -apple.com -hao123.com -windows.com -ebay.com -pps.tv -xunlei.com -56.com -fc2.com -paypal.com -sogou.com -tmall.com -ku6.com -rakuten.co.jp -about.com -orkut.com.br diff --git a/hostname_data/names33.txt b/hostname_data/names33.txt deleted file mode 100644 index 1ec9d3f..0000000 --- a/hostname_data/names33.txt +++ /dev/null @@ -1,20 +0,0 @@ -ifeng.com -goo.ne.jp -bbc.co.uk -yandex.ru -myspace.com -mail.ru -cnet.com -go.com -4399.com -orkut.com -skype.com -ameblo.jp -naver.com -flickr.com -4shared.com -amazon.co.jp -linkedin.com -dailymotion.com -imdb.com -aol.com diff --git a/hostname_data/names34.txt b/hostname_data/names34.txt deleted file mode 100644 index 940a57c..0000000 --- a/hostname_data/names34.txt +++ /dev/null @@ -1,20 +0,0 @@ -hotmail.com -360.cn -craigslist.org -weather.com -soku.com -alibaba.com -megaupload.com -renren.com -livedoor.jp -blogger.com -vkontakte.ru -answers.com -rapidshare.com -daum.net -7k7k.com -2345.com -photobucket.com -mediafire.com -ehow.com -seesaa.net diff --git a/hostname_data/names35.txt b/hostname_data/names35.txt deleted file mode 100644 index e7f8366..0000000 --- a/hostname_data/names35.txt +++ /dev/null @@ -1,20 +0,0 @@ -paipai.com -alipay.com -softonic.com -nifty.com -imageshack.us -cnn.com -tianya.cn -mywebsearch.com -zynga.com -partypoker.com -hp.com -walmart.com -kugou.com -ebay.de -youdao.com -hotfile.com -qiyi.com -pconline.com.cn -odnoklassniki.ru -jp.msn.com diff --git a/hostname_data/names4.txt b/hostname_data/names4.txt deleted file mode 100644 index 940a57c..0000000 --- a/hostname_data/names4.txt +++ /dev/null @@ -1,20 +0,0 @@ -hotmail.com -360.cn -craigslist.org -weather.com -soku.com -alibaba.com -megaupload.com -renren.com -livedoor.jp -blogger.com -vkontakte.ru -answers.com -rapidshare.com -daum.net -7k7k.com -2345.com -photobucket.com -mediafire.com -ehow.com -seesaa.net diff --git a/hostname_data/names41.txt b/hostname_data/names41.txt deleted file mode 100644 index d43eb9d..0000000 --- a/hostname_data/names41.txt +++ /dev/null @@ -1,23 +0,0 @@ -facebook.com -youtube.com -yahoo.com -live.com -wikipedia.org -msn.com -baidu.com -blogspot.com -microsoft.com -qq.com -taobao.com -bing.com -sina.com.cn -soso.com -163.com -ask.com -adobe.com -twitter.com -mozilla.com -youku.com -sdjjdsaf.com -andysayler.com -wmfo.org diff --git a/hostname_data/names42.txt b/hostname_data/names42.txt deleted file mode 100644 index 89943e7..0000000 --- a/hostname_data/names42.txt +++ /dev/null @@ -1,20 +0,0 @@ -amazon.com -wordpress.com -tudou.com -yahoo.co.jp -sohu.com -apple.com -hao123.com -windows.com -ebay.com -pps.tv -xunlei.com -56.com -fc2.com -paypal.com -sogou.com -tmall.com -ku6.com -rakuten.co.jp -about.com -orkut.com.br diff --git a/hostname_data/names43.txt b/hostname_data/names43.txt deleted file mode 100644 index 1ec9d3f..0000000 --- a/hostname_data/names43.txt +++ /dev/null @@ -1,20 +0,0 @@ -ifeng.com -goo.ne.jp -bbc.co.uk -yandex.ru -myspace.com -mail.ru -cnet.com -go.com -4399.com -orkut.com -skype.com -ameblo.jp -naver.com -flickr.com -4shared.com -amazon.co.jp -linkedin.com -dailymotion.com -imdb.com -aol.com diff --git a/hostname_data/names44.txt b/hostname_data/names44.txt deleted file mode 100644 index 940a57c..0000000 --- a/hostname_data/names44.txt +++ /dev/null @@ -1,20 +0,0 @@ -hotmail.com -360.cn -craigslist.org -weather.com -soku.com -alibaba.com -megaupload.com -renren.com -livedoor.jp -blogger.com -vkontakte.ru -answers.com -rapidshare.com -daum.net -7k7k.com -2345.com -photobucket.com -mediafire.com -ehow.com -seesaa.net diff --git a/hostname_data/names45.txt b/hostname_data/names45.txt deleted file mode 100644 index e7f8366..0000000 --- a/hostname_data/names45.txt +++ /dev/null @@ -1,20 +0,0 @@ -paipai.com -alipay.com -softonic.com -nifty.com -imageshack.us -cnn.com -tianya.cn -mywebsearch.com -zynga.com -partypoker.com -hp.com -walmart.com -kugou.com -ebay.de -youdao.com -hotfile.com -qiyi.com -pconline.com.cn -odnoklassniki.ru -jp.msn.com diff --git a/hostname_data/names5.txt b/hostname_data/names5.txt deleted file mode 100644 index e7f8366..0000000 --- a/hostname_data/names5.txt +++ /dev/null @@ -1,20 +0,0 @@ -paipai.com -alipay.com -softonic.com -nifty.com -imageshack.us -cnn.com -tianya.cn -mywebsearch.com -zynga.com -partypoker.com -hp.com -walmart.com -kugou.com -ebay.de -youdao.com -hotfile.com -qiyi.com -pconline.com.cn -odnoklassniki.ru -jp.msn.com diff --git a/hostname_data/names51.txt b/hostname_data/names51.txt deleted file mode 100644 index d43eb9d..0000000 --- a/hostname_data/names51.txt +++ /dev/null @@ -1,23 +0,0 @@ -facebook.com -youtube.com -yahoo.com -live.com -wikipedia.org -msn.com -baidu.com -blogspot.com -microsoft.com -qq.com -taobao.com -bing.com -sina.com.cn -soso.com -163.com -ask.com -adobe.com -twitter.com -mozilla.com -youku.com -sdjjdsaf.com -andysayler.com -wmfo.org diff --git a/hostname_data/names52.txt b/hostname_data/names52.txt deleted file mode 100644 index 89943e7..0000000 --- a/hostname_data/names52.txt +++ /dev/null @@ -1,20 +0,0 @@ -amazon.com -wordpress.com -tudou.com -yahoo.co.jp -sohu.com -apple.com -hao123.com -windows.com -ebay.com -pps.tv -xunlei.com -56.com -fc2.com -paypal.com -sogou.com -tmall.com -ku6.com -rakuten.co.jp -about.com -orkut.com.br diff --git a/hostname_data/names53.txt b/hostname_data/names53.txt deleted file mode 100644 index 1ec9d3f..0000000 --- a/hostname_data/names53.txt +++ /dev/null @@ -1,20 +0,0 @@ -ifeng.com -goo.ne.jp -bbc.co.uk -yandex.ru -myspace.com -mail.ru -cnet.com -go.com -4399.com -orkut.com -skype.com -ameblo.jp -naver.com -flickr.com -4shared.com -amazon.co.jp -linkedin.com -dailymotion.com -imdb.com -aol.com diff --git a/hostname_data/names54.txt b/hostname_data/names54.txt deleted file mode 100644 index 940a57c..0000000 --- a/hostname_data/names54.txt +++ /dev/null @@ -1,20 +0,0 @@ -hotmail.com -360.cn -craigslist.org -weather.com -soku.com -alibaba.com -megaupload.com -renren.com -livedoor.jp -blogger.com -vkontakte.ru -answers.com -rapidshare.com -daum.net -7k7k.com -2345.com -photobucket.com -mediafire.com -ehow.com -seesaa.net diff --git a/hostname_data/names55.txt b/hostname_data/names55.txt deleted file mode 100644 index e7f8366..0000000 --- a/hostname_data/names55.txt +++ /dev/null @@ -1,20 +0,0 @@ -paipai.com -alipay.com -softonic.com -nifty.com -imageshack.us -cnn.com -tianya.cn -mywebsearch.com -zynga.com -partypoker.com -hp.com -walmart.com -kugou.com -ebay.de -youdao.com -hotfile.com -qiyi.com -pconline.com.cn -odnoklassniki.ru -jp.msn.com diff --git a/pa7_lru/Makefile b/pa7_lru/Makefile index fd76806..bf179e3 100644 --- a/pa7_lru/Makefile +++ b/pa7_lru/Makefile @@ -4,6 +4,8 @@ CC = gcc CFLAGS = -c -g -Wall -Wextra LFLAGS = -g -Wall -Wextra +VPATH += ../common + SUBMITFILES = pager-lru.c .PHONY: all clean diff --git a/pa7_lru/pager-basic.c b/pa7_lru/pager-basic.c index 8d1399d..ac2c179 100644 --- a/pa7_lru/pager-basic.c +++ b/pa7_lru/pager-basic.c @@ -1,7 +1,7 @@ // Very basic pageit algorithm, only allows one process at a time, and one page // in memory -#include "simulator.h" +#include "../common/simulator.h" void pageit(Pentry q[MAXPROCESSES]) { for (int proc = 0; proc < MAXPROCESSES; proc++) { diff --git a/pa7_lru/pager-lru.c b/pa7_lru/pager-lru.c index b60b704..21e592f 100644 --- a/pa7_lru/pager-lru.c +++ b/pa7_lru/pager-lru.c @@ -1,7 +1,7 @@ // Jack Sangdahl // CSCI3753 SP24 // PA7 LRU -#include "simulator.h" +#include "../common/simulator.h" #include void pageit(Pentry q[MAXPROCESSES]) { diff --git a/pa7_lru/programs.c b/pa7_lru/programs.c index 7a1cfb1..53873de 100644 --- a/pa7_lru/programs.c +++ b/pa7_lru/programs.c @@ -5,7 +5,7 @@ * http://www.cs.tufts.edu/~couch/ */ -#include "simulator.h" +#include "../common/simulator.h" Program programs[PROGRAMS] = { {1535, diff --git a/pa7_lru/see.R b/pa7_lru/see.R deleted file mode 100644 index 17a2c02..0000000 --- a/pa7_lru/see.R +++ /dev/null @@ -1,505 +0,0 @@ -#======================================================== -# 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$time0) { -# 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 deleted file mode 100644 index 38d959b..0000000 --- a/pa7_lru/simulator.c +++ /dev/null @@ -1,835 +0,0 @@ -/* - * File: simulator.c - * - * Original Author: Dr. Alva Couch - * http://www.cs.tufts.edu/~couch/ - */ - -#include -#include -#include -#include -#include -#include -#include - -#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 -#include -#include - -// 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; } - -/*=========================== - 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 deleted file mode 100644 index dccb4c2..0000000 --- a/pa7_lru/simulator.h +++ /dev/null @@ -1,111 +0,0 @@ -/* - * 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; diff --git a/pa8_predict/Makefile b/pa8_predict/Makefile index 08024e8..8629c67 100644 --- a/pa8_predict/Makefile +++ b/pa8_predict/Makefile @@ -4,6 +4,8 @@ CC = gcc CFLAGS = -c -g -Wall -Wextra LFLAGS = -g -Wall -Wextra +VPATH += ../common + SUBMITFILES = pager-predict.c .PHONY: all clean diff --git a/pa8_predict/pager-predict.c b/pa8_predict/pager-predict.c index e982c00..e2e380a 100644 --- a/pa8_predict/pager-predict.c +++ b/pa8_predict/pager-predict.c @@ -1,7 +1,7 @@ // Jack Sangdahl // CSCI3753 SP24 // PA8 Predict -#include "simulator.h" +#include "../common/simulator.h" #include #include #include diff --git a/pa8_predict/see.R b/pa8_predict/see.R deleted file mode 100644 index 17a2c02..0000000 --- a/pa8_predict/see.R +++ /dev/null @@ -1,505 +0,0 @@ -#======================================================== -# 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$time0) { -# times[[length(times)+1]] <- temp[[length(temp)]] -# temp <- pl$proc[sel] -# procs[[length(procs)+1]] <- temp[[length(temp)]] -# temp <- pl$page[sel] -# pages[[length(pages)+1]] <- temp[[length(temp)]] -# temp <- pl$pid[sel] -# pids[[length(pids)+1]] <- temp[[length(temp)]] -# temp <- pl$kind[sel] -# kinds[[length(kinds)+1]] <- temp[[length(temp)]] -# temp <- pl$comment[sel] -# comments[[length(comments)+1]] <- as.character(temp[[length(temp)]]) -# } -# } -# } -# ord <- order(times,procs,pages) -# before <- data.frame(time=times[ord], proc=procs[ord], page=pages[ord], -# pid=pids[ord], kind=kinds[ord], comment=comments[ord]) -# -# # determine states after window -# times <- c(); procs <- c(); pages <- c() -# pids <- c(); kinds <- c(); comments <- c() -# for (p in c(1:20)) { # processes -# for (q in c(1:20)) { # pages -# # boolean bit field -# sel <- (pl$time>high) & (pl$proc==p) & (pl$page==q) -# temp <- pl$time[sel] -# if (length(temp)>0) { -# times[[length(times)+1]] <- temp[[1]] -# temp <- pl$proc[sel] -# procs[[length(procs)+1]] <- temp[[1]] -# temp <- pl$page[sel] -# pages[[length(pages)+1]] <- temp[[1]] -# temp <- pl$pid[sel] -# pids[[length(pids)+1]] <- temp[[1]] -# temp <- pl$kind[sel] -# kinds[[length(kinds)+1]] <- temp[[1]] -# temp <- pl$comment[sel] -# comments[[length(comments)+1]] <- as.character(temp[[1]]) -# } -# } -# } -# ord <- order(times,procs, pages) -# after <- data.frame(time=times[ord], proc=procs[ord], page=pages[ord], -# pid=pids[ord], kind=kinds[ord], comment=comments[ord]) - -# now construct the output - sel <- ((pl$time >= low) & (pl$time <= high)) - out <- data.frame( - time=pl$time[sel], - proc=pl$proc[sel], - page=pl$page[sel], - pid=pl$pid[sel], - kind=pl$kind[sel], - comment=pl$comment[sel] - ) -# out <- data.frame( -# time=c(before$time,pl$time[sel],after$time), -# proc=c(before$proc,pl$proc[sel],after$proc), -# page=c(before$page,pl$page[sel],after$page), -# pid=c(before$pid,pl$pid[sel],after$pid), -# kind=c(before$kind,pl$kind[sel],after$kind), -# comment=c(before$comment,pl$comment[sel],after$comment) -# ) - class(out) <- c('allPages', class(out)) - out -} - -#======================================================== -# paging history for one process -#======================================================== -procPages<- function(x, y, z, w) UseMethod('procPages') -procPages.allPages <- function(pl, proc, low=0, high=1e25) { - sel <- (pl$proc==proc) & (pl$time>=low) & (pl$time<=high) - out <- data.frame(time=pl$time[sel], proc=pl$proc[sel], page=pl$page[sel], - pid=pl$pid[sel], kind=pl$kind[sel], comment=pl$comment[sel]) - class(out) <- c('procPages', class(out)) - out -} - -procPages.procPages <- function(pl, low=0, high=1e25) { - sel <- (pl$time>=low) & (pl$time<=high) - out <- data.frame(time=pl$time[sel], proc=pl$proc[sel], page=pl$page[sel], - pid=pl$pid[sel], kind=pl$kind[sel], comment=pl$comment[sel]) - class(out) <- c('procPages', class(out)) - out -} - -#======================================================== -# paging history for one job -#======================================================== -jobPages<- function(x, y, z, w) UseMethod('jobPages') -jobPages.allPages <- function(pl, pid, low=0, high=1e25) { - sel <- (pl$pid==pid) & (pl$time>=low) & (pl$time<=high) - out <- data.frame(time=pl$time[sel], proc=pl$proc[sel], page=pl$page[sel], - pid=pl$pid[sel], kind=pl$kind[sel], comment=pl$comment[sel]) - class(out) <- c('jobPages', class(out)) - out -} - -jobPages.jobPages <- function(pl, low=0, high=1e25) { - sel <- (pl$time>=low) & (pl$time<=high) - out <- data.frame(time=pl$time[sel], proc=pl$proc[sel], page=pl$page[sel], - pid=pl$pid[sel], kind=pl$kind[sel], comment=pl$comment[sel]) - class(out) <- c('jobPages', class(out)) - out -} -#======================================================== -# a processor history is obtained from a full history -# by filtering by processor number -#======================================================== -procHistory <- function(x, y, z, w) UseMethod('procHistory') - -# extract a processor record from global history -procHistory.allHistory <- function(all, proc, low=0, high=1e25) { - sel <- (all$proc==proc) & (all$time >= low) & (all$time <= high) - out <- data.frame(time=all$time[sel], proc=all$proc[sel], - pid=all$pid[sel], kind=all$kind[sel], - pc=all$pc[sel],comment=all$comment[sel]) - class(out) <- c('procHistory', class(out)) - out -} - -# limit a processor history to a specific time -procHistory.procHistory <- function(ph, low=0, high=1e25) { - sel <- (ph$time >= low) & (ph$time <= high) - out <- data.frame(time=ph$time[sel], proc=ph$proc[sel], - pid=ph$pid[sel], kind=ph$kind[sel], - pc=ph$pc[sel],comment=ph$comment[sel]) - class(out) <- c('procHistory', class(out)) - out -} - -#======================================================== -# a job history is obtained from a full history by -# filtering by job number 0-39 -#======================================================== -jobHistory <- function(x, y, z, w) UseMethod('jobHistory') - -# extract a job from global history -jobHistory.allHistory <- function(all, pid, low=0, high=1e25) { - sel <- (all$pid==pid) & (all$time >= low) & (all$time <= high) - out <- data.frame(time=all$time[sel], proc=all$proc[sel], pid=all$pid[sel], - kind=all$kind[sel],pc=all$pc[sel],comment=all$comment[sel]) - class(out) <- c('jobHistory', class(out)) - out -} - -# limit a job to a specific time -jobHistory.jobHistory <- function(jh, low=0, high=1e25) { - sel <- (jh$time >= low) & (jh$time <= high) - out <- data.frame(time=jh$time[sel], proc=jh$proc[sel], pid=jh$pid[sel], - kind=jh$kind[sel],pc=jh$pc[sel],comment=jh$comment[sel]) - class(out) <- c('jobHistory', class(out)) - out -} - -#======================================================== -# smart plotting routines describe how to plot full -# histories, processor histories, job histories -# based upon object class. -#======================================================== - -# plot a single job -plot.jobHistory <- function(jh, low=0, high=1e25) { - toplot <- jobHistory(jh, low, high) - plot(c(), xlab='time', ylab='pc', ylim=c(0,max(toplot$pc)), xlim=c(toplot$time[[1]],toplot$time[[length(toplot$time)]])) - if (! is.na(pages)) lines(jobPages(pages,toplot$pid[[1]],low,high)) - # print(pages) - lines(toplot$time, toplot$pc, xlab='time', ylab='pc', col='black') - plotBlocked(toplot, low, high); -} - -# plot a single processor's results (all jobs) -plot.procHistory <- function(ph, low=0, high=1e25) { - toplot <- procHistory(ph, low, high) - plot(c(), , xlab='time', ylab='pc', ylim=c(0,max(toplot$pc)), xlim=c(toplot$time[[1]],toplot$time[[length(toplot$time)]])) - if (!is.na(pages)) lines(procPages(pages,toplot$proc[[1]],low, high)) - lines(toplot$time, (toplot$pc), xlab='time', ylab='pc', col='black') - plotBlocked(ph, low, high); -} - -# plot all job histories. -plot.allHistory <- function(all, low=0, high=1e25) { - toplot <- allHistory(all, low, high) - # create a selected region from this! - plot(c(), type='l', xlab='time', ylab='process', - xlim=c(1,toplot$time[[length(toplot$time)]]), ylim=c(0,41)) - x <- array() - y <- array() - for (job in c(0:39)) { - jh <- jobHistory(toplot, job, low, high) - if (length(jh$time)>0) { - x[[length(x)+1]] <- jh$time[[1]] - x[[length(x)+1]] <- jh$time[[length(jh$time)]] - x[[length(x)+1]] <- NA - y[[length(y)+1]] <- job - y[[length(y)+1]] <- job - y[[length(y)+1]] <- NA - } - } - lines(x,y,col='black') - x <- array() - y <- array() - for (job in c(0:39)) { - jh <- jobHistory(toplot, job, low, high) - if (length(jh$time)>0) { - for (index in c(1:(length(jh$time)-1))) { - if (jh$comment[[index]]=='blocked' - && jh$comment[[index+1]]=='unblocked') { - x[[length(x)+1]] <- jh$time[[index]] - x[[length(x)+1]] <- jh$time[[index+1]] - x[[length(x)+1]] <- NA - y[[length(y)+1]] <- job - y[[length(y)+1]] <- job - y[[length(y)+1]] <- NA - } - } - } - } - lines(x,y,col='red') -} - -#======================================================== -# subsystem plots page state on block graph -#======================================================== -plot.procPages <- function (pl, low=0, high=1e25) { - toplot <- procPages(pl, low, high) - plot(c(), xlab='time', ylab='memory', ylim=c(0,max(toplot$page)*128), xlim=c(toplot$time[[1]],toplot$time[[length(toplot$time)]])) - lines(toplot, low, high) -} - -lines.procPages <- function (pl, low=0, high=1e25) { - toplot <- procPages(pl, low, high) - - tot <- max(toplot$page) - refs <- array(dim=c(tot+1)) - coms <- array(dim=c(tot+1)) - for (i in c(1:(tot+1))) { - refs[[i]] = 0 - coms[[i]] = 'out' - } - xleft <- c() - xright <- c() - ybottom <- c() - ytop <- c() - cols <- c() - for (i in c(1:length(toplot$time))) { - time <- toplot$time[[i]] - page <- toplot$page[[i]] - if (!is.na(refs[[page+1]])) { - oldtime <- refs[[page+1]]; - oldcomm <- coms[[page+1]]; - xleft[[length(xleft)+1]] = oldtime - xright[[length(xright)+1]] = time - ybottom[[length(ybottom)+1]] = page*128 - ytop[[length(ytop)+1]] = (page+1)*128 - if (oldcomm=='in') { - cols[[length(cols)+1]] = rgb(.9,1,.9) - } else if (oldcomm=='out') { - cols[[length(cols)+1]] = rgb(1,.9,.9) - } else if (oldcomm=='coming') { - cols[[length(cols)+1]] = rgb(1,1,.9) - } else { # if (oldcomm=='going') - cols[[length(cols)+1]] = rgb(1,.9,1) - } - } - refs[[page+1]]=toplot$time[[i]] - coms[[page+1]]=as.character(toplot$comment[[i]]) - } - end <- toplot$time[[length(toplot$time)]] - # plot to end of line - for (page in c(0:19)) { - if (!is.na(refs[[page+1]])) { - oldtime <- refs[[page+1]]; - oldcomm <- coms[[page+1]]; - xleft[[length(xleft)+1]] = oldtime - xright[[length(xright)+1]] = end - ybottom[[length(ybottom)+1]] = page*128 - ytop[[length(ytop)+1]] = (page+1)*128 - if (oldcomm=='in') { - cols[[length(cols)+1]] = rgb(.9,1,.9) - } else if (oldcomm=='out') { - cols[[length(cols)+1]] = rgb(1,.9,.9) - } else if (oldcomm=='coming') { - cols[[length(cols)+1]] = rgb(1,1,.9) - } else { # if (oldcomm=='going') - cols[[length(cols)+1]] = rgb(1,.9,1) - } - } - } - rect(xleft=xleft, ybottom=ybottom, xright=xright, ytop=ytop, col=cols, border=NA) - # title(paste('pages for processor ',toplot$proc[[1]])) -} - -plot.jobPages <- function (pl, low=0, high=1e25) { - toplot <- jobPages(pl, low, high) - plot(c(), xlab='time', ylab='memory', ylim=c(0,max(toplot$page)*128), xlim=c(toplot$time[[1]],toplot$time[[length(toplot$time)]])) - lines(toplot, low, high) -} - -lines.jobPages <- function (pl, low=0, high=1e25) { - toplot <- jobPages(pl, low, high) - - tot <- max(toplot$page) - refs <- array(dim=c(tot+1)) - coms <- array(dim=c(tot+1)) - for (i in c(1:(tot+1))) { - refs[[i]] = 0 - coms[[i]] = 'out' - } - xleft <- c() - xright <- c() - ybottom <- c() - ytop <- c() - cols <- c() - for (i in c(1:length(toplot$time))) { - time <- toplot$time[[i]] - page <- toplot$page[[i]] - if (!is.na(refs[[page+1]])) { - oldtime <- refs[[page+1]]; - oldcomm <- coms[[page+1]]; - xleft[[length(xleft)+1]] = oldtime - xright[[length(xright)+1]] = time - ybottom[[length(ybottom)+1]] = page*128 - ytop[[length(ytop)+1]] = (page+1)*128 - if (oldcomm=='in') { - cols[[length(cols)+1]] = rgb(.9,1,.9) - } else if (oldcomm=='out') { - cols[[length(cols)+1]] = rgb(1,.9,.9) - } else if (oldcomm=='coming') { - cols[[length(cols)+1]] = rgb(1,1,.9) - } else { # if (oldcomm=='going') - cols[[length(cols)+1]] = rgb(1,.9,1) - } - } - refs[[page+1]]=toplot$time[[i]] - coms[[page+1]]=as.character(toplot$comment[[i]]) - } - end <- toplot$time[[length(toplot$time)]] - # plot to end of line - for (page in c(0:19)) { - if (!is.na(refs[[page+1]])) { - oldtime <- refs[[page+1]]; - oldcomm <- coms[[page+1]]; - xleft[[length(xleft)+1]] = oldtime - xright[[length(xright)+1]] = end - ybottom[[length(ybottom)+1]] = page*128 - ytop[[length(ytop)+1]] = (page+1)*128 - if (oldcomm=='in') { - cols[[length(cols)+1]] = rgb(.9,1,.9) - } else if (oldcomm=='out') { - cols[[length(cols)+1]] = rgb(1,.9,.9) - } else if (oldcomm=='coming') { - cols[[length(cols)+1]] = rgb(1,1,.9) - } else { # if (oldcomm=='going') - cols[[length(cols)+1]] = rgb(1,.9,1) - } - } - } - rect(xleft=xleft, ybottom=ybottom, xright=xright, ytop=ytop, col=cols, border=NA) - # title(paste('pages for processor ',toplot$proc[[1]])) -} - -#======================================================== -# subsystem plots blockages in red over grey background -#======================================================== -plotBlocked <- function(x, y, z) UseMethod('plotBlocked') -# print red blocked times over one job history -plotBlocked.jobHistory <- function(jh, low=0, high=1e25) { - toplot <- jobHistory(jh, low, high) - x <- array() - y <- array() - for (i in c(1:(length(toplot$time)-1))) { - if (toplot$comment[[i]]=='blocked' && toplot$comment[[i+1]]=='unblocked') { - x[[length(x)+1]] <- toplot$time[[i]] - x[[length(x)+1]] <- toplot$time[[i+1]] - x[[length(x)+1]] <- NA - y[[length(y)+1]] <- (toplot$pc[[i]]) - y[[length(y)+1]] <- (toplot$pc[[i]]) - y[[length(y)+1]] <- NA - } - } - lines(x,y,col='red'); -} - -# print red blocked times over one processor history -plotBlocked.procHistory <- function(ph, low=0, high=1e25) { - toplot <- procHistory(ph, low, high) - x <- array() - y <- array() - for (i in c(1:(length(toplot$time)-1))) { - if (toplot$comment[[i]]=='blocked' && toplot$comment[[i+1]]=='unblocked') { - x[[length(x)+1]] <- toplot$time[[i]] - x[[length(x)+1]] <- toplot$time[[i+1]] - x[[length(x)+1]] <- NA - y[[length(y)+1]] <- (toplot$pc[[i]]) - y[[length(y)+1]] <- (toplot$pc[[i]]) - y[[length(y)+1]] <- NA - } - } - lines(x,y,col='red'); -} - -#======================================================== -# interactive subsystem describes how to give more info -#======================================================== -interact <- function(x, y, z, w) UseMethod('interact') - -# zoom in on one job from full history -interact.allHistory <- function (all, low=0, high=1e25) { - while(TRUE) { - plot(all, low, high) - title("click on a timeline to graph the PC for the job") - which <- locator(1) - job <- as.integer(which$y[[1]]+0.5) - if ((job >= 0) && (job <= 39)) { - interact(jobHistory(all,job)) - } else { - break - } - } -} - -# plot one job interactively -interact.jobHistory <- function(jh, low=0, high=1e25) { - plot(jh,low,high) - title("click anywhere to return to overall view") - which <- locator(1) -} - -#======================================================== -# use the system to visualize results -#======================================================== - -# read file from disk into full history -all <- allHistory() -pages <- try(allPages(), silent=TRUE) -if (class(pages)[[1]] == 'try-error') { - pages <- NA -} - -# go interactive and show results -interact(all) diff --git a/pa8_predict/simulator.c b/pa8_predict/simulator.c deleted file mode 100644 index 58a5800..0000000 --- a/pa8_predict/simulator.c +++ /dev/null @@ -1,837 +0,0 @@ -/* - * File: simulator.c - * - * Original Author: Dr. Alva Couch - * http://www.cs.tufts.edu/~couch/ - */ - -#include -#include -#include -#include -#include -#include -#include - -#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 -#include -#include - -// shorthands for assertion handling -#define CHECK(bool) check((bool), #bool, __FILE__, __LINE__) -#define ASSERT(bool) assert((bool), #bool, __FILE__, __LINE__) -#define POSIT(bool) posit((bool), #bool, __FILE__, __LINE__) -#define DIE(reason) die((reason), __FILE__, __LINE__) -#define CARP(reason) carp((reason), __FILE__, __LINE__) - -// always print the result of a test -inline void check(int boolean, char *boolstr, char *file, int line) { - if (!boolean) { - fprintf(stderr, "ERROR: %s failed in line %d of file %s\n", boolstr, line, - file); - } else { - fprintf(stderr, "%s succeeded in line %d of file %s\n", boolstr, line, - file); - } -} - -// die if an assertion fails. -static inline void assert(int boolean, char *boolstr, char *file, int line) { - if (!boolean) { - fprintf(stderr, "Assertion %s failed in line %d of file %s\n", boolstr, - line, file); - exit(1); /* exit(0) means correct execution! */ - } -} - -// report failing assertions without bombing out... keeps running -inline int posit(int boolean, char *boolstr, char *file, int line) { - if (!boolean) - fprintf(stderr, "Assertion %s failed in line %d of file %s\n", boolstr, - line, file); - return boolean; -} - -// die on a fatal error -inline void die(char *condition, char *file, int line) { - fprintf(stderr, "Fatal error: %s at line %d of file %s\n", condition, line, - file); - exit(1); -} - -// print a non-fatal error -inline void carp(char *condition, char *file, int line) { - fprintf(stderr, "Non-fatal error: %s at line %d of file %s\n", condition, - line, file); -} - -static long log_port = LOG_ALWAYS; // logging ports for output -static void sim_log(long type, const char *format, ...) { - va_list ap; - if (log_port & type) { - va_start(ap, format); - fprintf(stderr, "%08ld: ", sysclock); - vfprintf(stderr, format, ap); - va_end(ap); - } -} - -/* keep track of physical page usage */ -static long pagesavail = PHYSICALPAGES; - -static Process *processes[MAXPROCESSES]; - -/* make a binary decision according to a - probability distribution */ -static long binary(double prob) { - if (drand48() < prob) - return 1; - else - return 0; -} - -/* clear a branching engine */ -static void bcontext_clear(Bcontext *c) { - long i; - c->bcount = 0; - c->boffset = 0; - c->bsize = 1; - c->bvalue = 1; - c->brings[0] = 1; - for (i = 1; i < MAXBRINGS; i++) - c->brings[i] = 0; -} - -/* initialize a branching engine */ -static void bcontext_init(Bcontext *c, Branch *b) { - long i; - c->bcount = 0; - c->btype = b->btype; - if (b->btype == GOTO) { - c->boffset = 0; - c->bsize = 1; - c->bvalue = 1; - // c->brings[0]=1; /* old version */ - c->brings[0] = 0x7fffffff; /* keep going forever */ - for (i = 1; i < MAXBRINGS; i++) - c->brings[i] = 0; - } else if (b->btype == IF) { - long cvalue; - c->boffset = 0; - c->bsize = 0; - cvalue = c->bvalue = binary(b->prob); - c->bcount = 0; - // compute future values for if statements - while (c->bsize < MAXBRINGS) { - if (binary(b->prob) == cvalue) { - c->brings[c->bsize]++; - } else { - c->bsize++; - c->brings[c->bsize] = 1; - cvalue = !cvalue; - } - } - } else if (b->btype == FOR) { - c->boffset = 0; - c->bvalue = 1; - c->bsize = 0; - while (c->bsize < MAXBRINGS) { - if (b->max > b->min) { - c->brings[c->bsize++] = lrand48() % (b->max - b->min) + b->min; - } else { - c->brings[c->bsize++] = b->min; - } - c->brings[c->bsize++] = 1; // one failure to escape loop - } - } else if (b->btype == NFOR) { - c->boffset = 0; - c->bvalue = 0; - c->bsize = 0; - while (c->bsize < MAXBRINGS) { - if (b->max > b->min) { - c->brings[c->bsize++] = lrand48() % (b->max - b->min) + b->min; - } else { - c->brings[c->bsize++] = b->min; - } - c->brings[c->bsize++] = 1; // one failure to escape loop - } - } else { - fprintf(stderr, "unknown btype %ld\n", (long)(b->btype)); - } -} - -/* decide whether to branch or not */ -static long bcontext_decide(Bcontext *c) { - long ret = c->bvalue; - c->bcount++; - ASSERT(c->boffset >= 0 && c->boffset < MAXBRINGS); - if (c->bcount >= c->brings[c->boffset]) { - c->boffset = (c->boffset + 1) % c->bsize; - // ASSERT(c->boffset>0); // no wrapping! - c->bcount = 0; - c->bvalue = !c->bvalue; - } - return ret; -} - -static void process_clear(Process *q) { - long i; - q->pc = 0; - q->compute = q->block = 0; - q->program = NULL; - q->pid = -1; - q->kind = -1; - q->nbcontexts = 0; - for (i = 0; i < MAXBRANCHES; i++) { - bcontext_clear(q->bcontexts + i); - } - q->npages = 0; - /* no physical pages assigned */ - for (i = 0; i < MAXPROCPAGES; i++) { - q->pages[i] = -PAGEWAIT - 1; - q->blocked[i] = FALSE; // ALC: so simulator will log first access - } - q->active = FALSE; -} - -/* load a program into a process */ -static void process_load(Process *q, Program *p, int pid, int kind) { - long i; - q->pc = 0; - q->compute = q->block = 0; - q->program = p; - q->pid = pid; - q->kind = kind; - q->nbcontexts = p->nbranches; - ASSERT(p->nbranches >= 0 && p->nbranches < MAXBRANCHES); - for (i = 0; i < p->nbranches; i++) { - bcontext_init(q->bcontexts + i, p->branches + i); - } - // fprintf(stderr,"actual page size for process is %d\n", - // (q->program->size+PAGESIZE-1)/PAGESIZE); - q->npages = MAXPROCPAGES; - for (i = 0; i < MAXPROCPAGES; i++) { - q->pages[i] = -PAGEWAIT - 1; - q->blocked[i] = FALSE; // ALC: so simulator will log first access - } - /* no physical pages assigned */ - q->active = TRUE; /* now running */ -} - -/* unload a process and release all resources */ -static void process_unload(int pnum, Process *q) { - long i; - for (i = 0; i < q->npages; i++) - if (q->pages[i] >= -PAGEWAIT) { - pagesavail++; - q->pages[i] = -PAGEWAIT - 1; - q->blocked[i] = 1; - } - q->active = FALSE; - sim_log(LOG_LOAD, "process %2d; pc %04d: unloaded\n", pnum, q->pc); -} - -/* do a branch if necessary */ -static void process_dobranch(int pnum, Process *q, Branch *b, Bcontext *c) { - if (bcontext_decide(c)) { - // must document where we branched from - if (output) - fprintf(output, "%ld,%d,%ld,%ld,%ld,branch_from\n", sysclock, pnum, - q->pid, q->kind, q->pc); - q->pc = b->whereto; - // and where we branched to - if (output) - fprintf(output, "%ld,%d,%ld,%ld,%ld,branch_to\n", sysclock, pnum, q->pid, - q->kind, q->pc); - sim_log(LOG_BRANCH, "process %2d; pc %04d: branch\n", pnum, q->pc); - } else { - q->pc++; - sim_log(LOG_BRANCH, "process %2d; pc %04d: no branch\n", pnum, q->pc); - } - if (q->pc < 0 || q->pc >= q->program->size) - q->pc = 0; /* start over */ -} - -/* compute one step of a process */ -static long process_step(int pnum, Process *q) { - long pc; - long page; - long max, min; - Branch *b; - Bcontext *c; - - if (!q) - return FALSE; - pc = q->pc; - page = q->pc / PAGESIZE; - if (!q->active) { - return FALSE; - } - - /* if page swapped out, don't allow to run */ - if (q->pages[page] != 0) { - if (!q->blocked[page]) { - sim_log(LOG_BLOCK, "process=%2d page=%3d blocked\n", pnum, page); - if (output) - fprintf(output, "%ld,%d,%ld,%ld,%ld,blocked\n", sysclock, pnum, q->pid, - q->kind, q->pc); - q->blocked[page] = TRUE; - } - q->block++; - return TRUE; - } else { - if (q->blocked[page]) { - sim_log(LOG_BLOCK, "process=%2d page=%3d unblocked\n", pnum, page); - if (output) - fprintf(output, "%ld,%d,%ld,%ld,%ld,unblocked\n", sysclock, pnum, - q->pid, q->kind, q->pc); - q->blocked[page] = FALSE; - } - q->compute++; - } - - /* should I exit */ - ASSERT(q->program->nexits >= 0 && q->program->nexits <= MAXEXITS); - min = 0; - max = q->program->nexits - 1; - while (min + 1 < max) { - long mid = (min + max) / 2; - if (pc == q->program->exits[mid]) { - if (output) - fprintf(output, "%ld,%d,%ld,%ld,%ld,exit\n", sysclock, pnum, q->pid, - q->kind, q->pc); - return FALSE; - } else if (pc < q->program->exits[mid]) - max = mid; - else - min = mid; - } - if (pc == q->program->exits[min] || pc == q->program->exits[max]) { - if (output) - fprintf(output, "%ld,%d,%ld,%ld,%ld,exit\n", sysclock, pnum, q->pid, - q->kind, q->pc); - return FALSE; - } - b = q->program->branches; - c = q->bcontexts; - ASSERT(q->program->nbranches >= 0 && q->program->nbranches <= MAXBRANCHES); - min = 0; - max = q->program->nbranches - 1; - while (min + 1 < max) { - long mid = (min + max) / 2; - if (pc == b[mid].wherefrom) { - process_dobranch(pnum, q, b + mid, c + mid); - return TRUE; - } else if (pc < b[mid].wherefrom) - max = mid; - else - min = mid; - } - if (pc == b[min].wherefrom) { - process_dobranch(pnum, q, b + min, c + min); - return TRUE; - } - if (pc == b[max].wherefrom) { - process_dobranch(pnum, q, b + max, c + max); - return TRUE; - } - q->pc++; /* default action */ - if (q->pc < 0 || q->pc > q->program->size) { - if (output) - fprintf(output, "%ld,%d,%ld,%ld,%ld,out_of_range\n", sysclock, pnum, - q->pid, q->kind, q->pc); - q->pc = 0; /* start over */ - if (output) - fprintf(output, "%ld,%d,%ld,%ld,%ld,restart\n", sysclock, pnum, q->pid, - q->kind, q->pc); - } - return TRUE; -} - -/* public routine: swap one page out */ -int pageout(int process, int page) { - if (process < 0 || process >= procs || !processes[process] || - !processes[process]->active || page < 0 || - page >= processes[process]->npages) - return FALSE; - if (processes[process]->pages[page] < 0) - return TRUE; /* on its way out */ - if (processes[process]->pages[page] > 0) - return FALSE; /* not available to swap out */ - sim_log(LOG_PAGE, "process=%2d page=%3d start pageout\n", process, page); - if (pages) - fprintf(pages, "%ld,%d,%d,%ld,%ld,going\n", sysclock, process, page, - processes[process]->pid, processes[process]->kind); - processes[process]->pages[page] = -1; - return TRUE; -} - -/* public routine: swap one page in */ -int pagein(int process, int page) { - if (process < 0 || process >= procs || !processes[process] || - !processes[process]->active || page < 0 || - page >= processes[process]->npages) - return FALSE; - if (processes[process]->pages[page] >= 0) - return TRUE; /* on its way */ - if (pagesavail == 0) - return FALSE; - if (processes[process]->pages[page] >= -PAGEWAIT) - return FALSE; /* not yet out */ - sim_log(LOG_PAGE, "process=%2d page=%3d start pagein\n", process, page); - if (pages) - fprintf(pages, "%ld,%d,%d,%ld,%ld,coming\n", sysclock, process, page, - processes[process]->pid, processes[process]->kind); - processes[process]->pages[page] = PAGEWAIT; - pagesavail--; - return TRUE; -} - -/*============ - job queue - ============*/ - -static long queuetype[QUEUESIZE]; -static Process queue[QUEUESIZE]; -static long queueend; -static void initqueue() { - long i; - for (i = 0; i < QUEUESIZE; i++) - queuetype[i] = lrand48() % PROGRAMS; - /* - long repeats; - for (repeats=0; repeats<10; repeats++) - for (i=0; i= QUEUESIZE; } - -/*=========================== - control of all processes - ===========================*/ - -static void allprint() { - int i, j; - fprintf(stderr, "\nprocess "); - for (i = 0; i < MAXPROCESSES / 2; i++) { - if (i) - fprintf(stderr, " | "); - if (processes[i] && processes[i]->active) { - fprintf(stderr, " %02d", i); - } else { - fprintf(stderr, " --"); - } - } - fprintf(stderr, "\n"); - fprintf(stderr, "pc "); - for (i = 0; i < MAXPROCESSES / 2; i++) { - if (i) - fprintf(stderr, " | "); - if (processes[i] && processes[i]->active) { - fprintf(stderr, "%04ld", processes[i]->pc); - } else { - fprintf(stderr, "----"); - } - } - fprintf(stderr, "\n"); - for (j = 0; j < MAXPROCPAGES; j++) { - fprintf(stderr, "page%02d ", j); - for (i = 0; i < MAXPROCESSES / 2; i++) { - if (i) - fprintf(stderr, " |"); - if (processes[i] && processes[i]->active) { - int pcblock = processes[i]->pc / PAGESIZE; - if (j == pcblock) { - if (processes[i]->pages[j] > 0) - fprintf(stderr, "*i%3ld", processes[i]->pages[j]); - else if (processes[i]->pages[j] == 0) - fprintf(stderr, "*=in "); - else if (processes[i]->pages[j] == -100) - fprintf(stderr, "*=out"); - else - fprintf(stderr, "*o%3ld", 100 + processes[i]->pages[j]); - // fprintf(stderr,"*%4d",processes[i]->pages[j]); - } else { - if (processes[i]->pages[j] > 0) - fprintf(stderr, " i%3ld", processes[i]->pages[j]); - else if (processes[i]->pages[j] == 0) - fprintf(stderr, " =in "); - else if (processes[i]->pages[j] == -100) - fprintf(stderr, " =out"); - else - fprintf(stderr, " o%3ld", 100 + processes[i]->pages[j]); - // fprintf(stderr," %4d",processes[i]->pages[j]); - } - } else { - fprintf(stderr, " ----"); - } - } - fprintf(stderr, "\n"); - } - fprintf(stderr, "------------------------------------------------------------" - "----------------\n"); - fprintf(stderr, "process "); - for (i = MAXPROCESSES / 2; i < MAXPROCESSES; i++) { - if (i - MAXPROCESSES / 2) - fprintf(stderr, " | "); - if (processes[i] && processes[i]->active) { - fprintf(stderr, " %02d", i); - } else { - fprintf(stderr, " --"); - } - } - fprintf(stderr, "\n"); - fprintf(stderr, "pc "); - for (i = MAXPROCESSES / 2; i < MAXPROCESSES; i++) { - if (i - MAXPROCESSES / 2) - fprintf(stderr, " | "); - if (processes[i] && processes[i]->active) { - fprintf(stderr, "%04ld", processes[i]->pc); - } else { - fprintf(stderr, "----"); - } - } - fprintf(stderr, "\n"); - for (j = 0; j < MAXPROCPAGES; j++) { - fprintf(stderr, "page%02d ", j); - for (i = MAXPROCESSES / 2; i < MAXPROCESSES; i++) { - if (i - MAXPROCESSES / 2) - fprintf(stderr, " |"); - if (processes[i] && processes[i]->active) { - int pcblock = processes[i]->pc / PAGESIZE; - if (j == pcblock) { - if (processes[i]->pages[j] > 0) - fprintf(stderr, "*i%3ld", processes[i]->pages[j]); - else if (processes[i]->pages[j] == 0) - fprintf(stderr, "*=in "); - else if (processes[i]->pages[j] == -100) - fprintf(stderr, "*=out"); - else - fprintf(stderr, "*o%3ld", 100 + processes[i]->pages[j]); - // fprintf(stderr,"*%4d",processes[i]->pages[j]); - } else { - if (processes[i]->pages[j] > 0) - fprintf(stderr, " i%3ld", processes[i]->pages[j]); - else if (processes[i]->pages[j] == 0) - fprintf(stderr, " =in "); - else if (processes[i]->pages[j] == -100) - fprintf(stderr, " =out"); - else - fprintf(stderr, " o%3ld", 100 + processes[i]->pages[j]); - // fprintf(stderr," %4d",processes[i]->pages[j]); - } - } else { - fprintf(stderr, " ----"); - } - } - fprintf(stderr, "\n"); - } - fprintf(stderr, "------------------------------------------------------------" - "----------------\n"); -} - -static void endit() { - allprint(); - exit(0); -} - -static void allinit() { - long i; - initqueue(); - for (i = 0; i < MAXPROCESSES; i++) - processes[i] = NULL; - for (i = 0; i < procs; i++) { - // zero out pages from processes - if (!empty()) { - processes[i] = dequeue(); - - sim_log(LOG_LOAD, "process %2d; pc %04d: loaded\n", i, processes[i]->pc); - if (output) - fprintf(output, "%ld,%ld,%ld,%ld,%ld,load\n", sysclock, i, - processes[i]->pid, processes[i]->kind, processes[i]->pc); - if (pages) { - long j; - for (j = 0; j < MAXPROCPAGES; j++) - fprintf(pages, "%ld,%ld,%ld,%ld,%ld,out\n", sysclock, i, j, - processes[i]->pid, processes[i]->kind); - } - } - } -} - -static void allscore() { - int i; - int block = 0; - int compute = 0; - for (i = 0; i < QUEUESIZE; i++) { - block += queue[i].block; - compute += queue[i].compute; - } - sim_log(LOG_ALWAYS, "simulation ends\n"); - sim_log(LOG_ALWAYS, "%d blocked cycles\n", block); - sim_log(LOG_ALWAYS, "%d compute cycles\n", compute); - sim_log(LOG_ALWAYS, "ratio blocked/compute=%g\n", - (double)block / (double)compute); -} - -static void allstep() { - long i; - for (i = 0; i < procs; i++) { - if (!process_step(i, processes[i])) { - if (processes[i] && processes[i]->active) { - // document final PC position - if (output) - fprintf(output, "%ld,%ld,%ld,%ld,%ld,unload\n", sysclock, i, - processes[i]->pid, processes[i]->kind, processes[i]->pc); - if (pages) { - long j; - for (j = 0; j < MAXPROCPAGES; j++) - fprintf(pages, "%ld,%ld,%ld,%ld,%ld,out\n", sysclock, i, j, - processes[i]->pid, processes[i]->kind); - } - process_unload(i, processes[i]); - } - processes[i] = NULL; - if (!empty()) { - processes[i] = dequeue(); - sim_log(LOG_LOAD, "process %2d; pc %04d: loaded\n", i, - processes[i]->pc); - if (output) - fprintf(output, "%ld,%ld,%ld,%ld,%ld,load\n", sysclock, i, - processes[i]->pid, processes[i]->kind, processes[i]->pc); - } - } - } -} - -static long alldone() { - long i; - for (i = 0; i < procs; i++) { - if (processes[i] && processes[i]->active) - return FALSE; - } - return TRUE; -} - -static int allblocked() { - int allfree = 0; - int runnable = 0; - int memwait = 0; - int freewait = 0; - int i, stat; - for (i = 0; i < procs; i++) - if (processes[i] && processes[i]->active) { - stat = processes[i]->pages[(int)(processes[i]->pc / PAGESIZE)]; - if (stat > 0) - memwait++; /* waiting for swap in */ - else if (stat == 0) - runnable++; /* ok */ - else if (stat < -PAGEWAIT) - allfree++; /* free */ - else - freewait++; /* waiting for swap out */ - } - - if (allfree && !memwait && !runnable && !freewait) { - sim_log(LOG_DEAD, "%d process pcs waiting for swap in\n", memwait); - sim_log(LOG_DEAD, "%d process pcs runnable\n", runnable); - sim_log(LOG_DEAD, "%d process pcs waiting for swap out\n", freewait); - sim_log(LOG_DEAD, "%d process pcs swapped out\n", allfree); - sim_log(LOG_DEAD, "All needed pages swapped out!\n"); - // allprint(); - return 1; - } else { - return 0; - } -} - -static void allage() { - long i; - for (i = 0; i < procs; i++) { - if (processes[i] && processes[i]->active) { - long j; - for (j = 0; j < processes[i]->npages; j++) { - if (processes[i]->pages[j] == 0) - ; - else if (processes[i]->pages[j] < -PAGEWAIT) - ; - else if (processes[i]->pages[j] > 0) { - processes[i]->pages[j]--; - if (processes[i]->pages[j] == 0) { - sim_log(LOG_PAGE, "process=%2d page=%3d end pagein\n", i, j); - if (pages) - fprintf(pages, "%ld,%ld,%ld,%ld,%ld,in\n", sysclock, i, j, - processes[i]->pid, processes[i]->kind); - } - } else if (processes[i]->pages[j] < 0 && - processes[i]->pages[j] >= -PAGEWAIT) { - processes[i]->pages[j]--; - if (processes[i]->pages[j] < -PAGEWAIT) { - sim_log(LOG_PAGE, "process=%2d page=%3d end pageout\n", i, j); - if (pages) - fprintf(pages, "%ld,%ld,%ld,%ld,%ld,out\n", sysclock, i, j, - processes[i]->pid, processes[i]->kind); - pagesavail++; - } - } - } - } - } -} - -static void callyou() { - long i, j; - Pentry pentry[MAXPROCESSES]; - for (i = 0; i < MAXPROCESSES; i++) { - if (processes[i]) { - pentry[i].active = processes[i]->active; - pentry[i].pc = processes[i]->pc; - pentry[i].npages = processes[i]->npages; - for (j = 0; j < processes[i]->npages; j++) { - pentry[i].pages[j] = (processes[i]->pages[j] == 0); - } - for (; j < MAXPROCPAGES; j++) - pentry[i].pages[j] = FALSE; - } else { - pentry[i].active = FALSE; - pentry[i].pc = 0; - pentry[i].npages = 0; - for (j = 0; j < MAXPROCPAGES; j++) - pentry[i].pages[j] = FALSE; - } - } - pageit(pentry); /* call your routine */ -} - -int main(int argc, char **argv) { - - long i, errors = 0, help = 0; - - signal(SIGINT, endit); - - log_port = LOG_ALWAYS; - for (i = 1; i < argc; i++) { - if (strcmp(argv[i], "-help") == 0) { - help++; - } else if (strcmp(argv[i], "-all") == 0) { - log_port |= LOG_LOAD | LOG_BLOCK | LOG_PAGE | LOG_BRANCH; - } else if (strcmp(argv[i], "-load") == 0) { - log_port |= LOG_LOAD; - } else if (strcmp(argv[i], "-block") == 0) { - log_port |= LOG_BLOCK; - } else if (strcmp(argv[i], "-page") == 0) { - log_port |= LOG_PAGE; - } else if (strcmp(argv[i], "-branch") == 0) { - log_port |= LOG_BRANCH; - } else if (strcmp(argv[i], "-dead") == 0) { - log_port |= LOG_DEAD; - } else if (strcmp(argv[i], "-seed") == 0) { - if (sscanf(argv[++i], "%ld", &seed) != 1) { - fprintf(stderr, "%s: could not read random seed from command line\n", - argv[0]); - errors++; - } else if (seed < 1 || seed > ((1 << 30) - 1)) { - fprintf(stderr, "%s: random seed must be between 1 and %d\n", argv[0], - (1 << 30) - 1); - errors++; - } - } else if (strcmp(argv[i], "-csv") == 0) { - output = fopen("output.csv", "w"); - if (!output) { - fprintf(stderr, "%s: could not open output.csv for writing\n", argv[0]); - errors++; - } - pages = fopen("pages.csv", "w"); - if (!pages) { - fprintf(stderr, "%s: could not open pages.csv for writing\n", argv[0]); - errors++; - } - } else if (strcmp(argv[i], "-procs") == 0) { - if (sscanf(argv[++i], "%ld", &procs) != 1) { - fprintf(stderr, - "%s: could not read number of processors from command line\n", - argv[0]); - errors++; - } else if (procs < 1 || procs > MAXPROCESSES) { - fprintf(stderr, "%s: number of processors must be between 1 and %d\n", - argv[0], MAXPROCESSES); - errors++; - } - } else { - fprintf(stderr, "t4: unrecognized argument %s\n", argv[i]); - errors++; - } - } - if (errors || help) { - fprintf(stderr, "%s usage: %s \n", argv[0], argv[0]); - fprintf(stderr, " -all log everything\n"); - fprintf(stderr, " -load log loading of processes\n"); - fprintf(stderr, " -unload log unloading of processes\n"); - fprintf(stderr, " -branch log program branches\n"); - fprintf(stderr, " -page log page in and out\n"); - fprintf(stderr, " -seed 512 set random seed to 512\n"); - fprintf(stderr, " -procs 4 run only four processors\n"); - fprintf(stderr, " -dead detect deadlocks\n"); - fprintf(stderr, - " -csv generate output.csv and pages.csv for graphing\n"); - if (errors) { - return EXIT_FAILURE; - } else { - return EXIT_SUCCESS; - } - } - if (seed == 0) { - seed = (time(NULL) * 38491 + 71831 + time(NULL) * time(NULL)) & - ((1 << 30) - 1); - } - srand48(seed); - sim_log(LOG_ALWAYS, "random seed %d\n", seed); - sim_log(LOG_ALWAYS, "using %d processors\n", procs); - - allinit(); - while (!alldone()) { // all processes inactive - allstep(); // advance time one tick; if process done, reload - allage(); // advance time for page wait variables. - callyou(); // call your program - sysclock++; // remember new time. - allblocked(); // deadlock detection - } - allscore(); - - return EXIT_SUCCESS; -} diff --git a/pa8_predict/simulator.h b/pa8_predict/simulator.h deleted file mode 100644 index 38160ad..0000000 --- a/pa8_predict/simulator.h +++ /dev/null @@ -1,111 +0,0 @@ -/* - * File: simulator.h - * - * Original Author: Dr. Alva Couch - * http://www.cs.tufts.edu/~couch/ - */ - -#define TRUE 1 -#define FALSE 0 - -#define MAXPROCPAGES 20 /* max pages per individual process */ -#define MAXPROCESSES 20 /* max number of processes in runqueue */ -#define PAGESIZE 128 /* size of an individual page */ -#define PAGEWAIT 100 /* wait for paging in */ -#define PHYSICALPAGES 100 /* number of available physical pages */ -#define QUEUESIZE 40 /* total number of processes to run */ -#define PROGRAMS 10 /* total number of program types */ - -#define MAXBRANCHES 40 /* number of branches in a program */ -#define MAXEXITS 10 /* number of maximum exits per program */ -#define MAXBRINGS 100 /* must be EVEN! data points in branch table */ -#define MAXPC (MAXPROCPAGES * PAGESIZE) /* largest PC value */ - -struct pentry { - long active; - long pc; - long npages; - long pages[MAXPROCPAGES]; /* 0 if not allocated, 1 if allocated */ -}; - -typedef struct pentry Pentry; - -/* int pagein (int process, int page) - * This pages in the requested page - * Arguments: - * proc: process to work upon (0-19) - * page: page to put in (0-19) - * Returns: - * 1 if pagein started, already running, or paged in - * 0 if it can't start (e.g., swapping out) - */ -extern int pagein(int process, int page); - -/* int pageout(int process, int page) - * This pages out the requested page. - * Arguments: - * proc: process to work upon (0-19) - * page: page to swap out. - * Returns: - * 1 if pageout started, already running, or paged out - * 0 if can't start (e.g., swapping in) - */ -extern int pageout(int process, int page); - -/* void pageit(Pentry q[MAXPROCESSES]) - * This is called by the simulator - * every time something interesting occurs. - * It is where you implement the paging strategy. - * Arguments: - * q: state of every process - * Returns: - * void - */ -extern void pageit(Pentry q[MAXPROCESSES]); - -typedef enum { GOTO, FOR, NFOR, IF } BranchType; - -/* abstract description of a branch - describes qualitative behavior, not actual branching */ -typedef struct branch { - long wherefrom; - long whereto; - BranchType btype; - long min, max; - double prob; - long extent; -} Branch; - -typedef struct program { - long size; - long nbranches; - Branch branches[MAXBRANCHES]; - long nexits; - long exits[MAXEXITS]; /* which statements are "halt" */ -} Program; - -// branch context: determines which branch to -// take next in a probabilistic situation... -typedef struct bcontext { - BranchType btype; - long boffset; /* offset into brings array */ - long bsize; /* size of brings array */ - long bvalue; /* which branch direction to take */ - long bcount; /* value of current decrement */ - long brings[MAXBRINGS]; -} Bcontext; - -typedef struct process { - Program *program; - long nbcontexts; - Bcontext bcontexts[MAXBRANCHES]; - long pc; /* program counter */ - long npages; - long pages[MAXPROCPAGES]; /* whether page is available */ - long blocked[MAXPROCPAGES]; /* whether we've reported page state */ - long active; /* whether running now */ - long compute; /* number of compute ticks */ - long block; /* number of blocked ticks */ - long pid; /* unique process number */ - long kind; /* kind of process from table */ -} Process; -- cgit v1.2.3