存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
模拟页式虚拟存储管理中硬件的地址转换和缺页中断，并用先进先出调度算法（FIFO）处理缺页中断。
（1）为了装入一个页面而必须调出一页时，如果被选中调出的页面在执行中没有修改过，则不必把该页重新写到磁盘上（因磁盘上已有副本）。因此，在页表中可以增加是否修改过的标志，当执行“存”指令、“写”指令时把对应页的修改标志置成“1”表示该页修改过，否则为“0”表示该页未修改过。页表格式如表3-1所示。
（2）设计一个地址转换程序来模拟硬件的地址转换和缺页中断。当访问的页在主存时则形成绝对地址，但不去模拟指令的执行，可用输出转换后的绝对地址来表示一条指令已完成。当访问的页不在主存时则输出“*该页页号”来表示硬件产生了一次缺页中断。模拟地址转换的程序流程如图3-1所示。
（3）编制一个FIFO页面调度程序。FIFO页面调度算法总是先调出作业中最先进入主存的那一页，因此，可以用一个数组来构成页号队列。数组中每个元素是该作业已在主存的页面号，假定分配给作业的主存块数为m，且该作业开始的m页已装入主存，则数组可由m个元素组成：
P[0]，P[1]，…，P[m-1]
它们的初值为
P[0]∶=0，P[1]∶=1，…，P[m-1]∶= m-1
用一指针k指示当要装入新页时应调出的页在数组的位置，k的初值为“0”。
当产生缺页中断后，操作系统总是选择P[k]所指出的页面调出，然后执行
P[k]∶=要装入的新页页号
k∶=（k+1）mod m
在实验中不必实际地启动磁盘执行调出一页和装入一页的工作，而用输出“OUT调出的页号”和“IN要装入的新页页号”来模拟一次调出和装入的过程。模拟程序的流程见图3-1。
（4）假定主存的每块长度为1024个字节，现有一个共7页的作业，其副本已在磁盘上。系统为该作业分配了4块主存块，且该作业的第0页至第3页已经装入主存，其余3页尚未装入主存，该作业的页表见表3-2。
如果该作业依次执行的指令序列如表3-3所示。
依次执行上述的指令序列来调试你所设计的程序（仅模拟指令的执行，不必考虑指令序列中具体操作的执行）
（5）为了检查程序的正确性，可自行确定若干组指令序列，运行设计的程序，核对执行结果。
主类
package report;
import java.util.ArrayList;
import java.util.List;
public class N3 {
private static int L;
private static int j;
private static int m = 4;
private static int k = 0;
private static int P[] = { 0, 1, 2, 3 };
private static List<Page> pageList = new ArrayList<Page>();
private static List<Cmd> cmdList = new ArrayList<Cmd>();
public static void main(String[] args) {
Page page0 = new Page(0, 1, 5, 0, "011");
Page page1 = new Page(1, 1, 8, 0, "012");
Page page2 = new Page(2, 1, 9, 0, "013");
Page page3 = new Page(3, 1, 1, 0, "021");
Page page4 = new Page(4, 0, -1, 0, "022");
Page page5 = new Page(5, 0, -1, 0, "023");
Page page6 = new Page(6, 0, -1, 0, "121");
pageList.add(page0);
pageList.add(page1);
pageList.add(page2);
pageList.add(page3);
pageList.add(page4);
pageList.add(page5);
pageList.add(page6);
Cmd cmd0 = new Cmd("+", 0, "070");
Cmd cmd1 = new Cmd("+", 1, "050");
Cmd cmd2 = new Cmd("x", 2, "015");
Cmd cmd3 = new Cmd("存", 3, "021");
Cmd cmd4 = new Cmd("取", 0, "056");
Cmd cmd5 = new Cmd("-", 6, "040");
Cmd cmd6 = new Cmd("移位", 4, "053");
Cmd cmd7 = new Cmd("+", 5, "023");
Cmd cmd8 = new Cmd("存", 1, "037");
Cmd cmd9 = new Cmd("取", 2, "078");
Cmd cmd10 = new Cmd("+", 4, "001");
Cmd cmd11 = new Cmd("存", 6, "084");
cmdList.add(cmd0);
cmdList.add(cmd1);
cmdList.add(cmd2);
cmdList.add(cmd3);
cmdList.add(cmd4);
cmdList.add(cmd5);
cmdList.add(cmd6);
cmdList.add(cmd7);
cmdList.add(cmd8);
cmdList.add(cmd9);
cmdList.add(cmd10);
cmdList.add(cmd11);
printPageList();
while (!cmdList.isEmpty()) {
// 取指令中访问的页号＝＞L
L = cmdList.get(0).getPage();
while (true) {
// 查页表
// 页标志=1
if (pageList.get(L).getFlag() == 1) {
// 形成绝对地址
int absoluteAddress = pageList.get(L).getPiece() * 1024
+ Integer.parseInt(cmdList.get(0).getAddressInPage());
// 是”存”指令
if (cmdList.get(0).getOperation().equalsIgnoreCase("存")) {
// 置L页修改标志”1”
pageList.get(L).setModify(1);
} else {
}
// 输出绝对地址
System.out.println("运行指令:" + cmdList.get(0).getOperation() + "\t页号:" + pageList.get(L).getPage()
+ " 页内地址:" + cmdList.get(0).getAddressInPage() + " 绝对地址:" + absoluteAddress
+ " 页标志:" + pageList.get(L).getFlag() + " 主存块号:" + pageList.get(L).getPiece()
+ " 页修改标志:" + pageList.get(L).getModify() + " 页在磁盘上的位置:"
+ pageList.get(L).getPositionInDisk());
}
// 页标志!=1
else {
System.out.println();
System.out.println("内存中找不到页" + L);
j = P[k];
int tempPiece = pageList.get(j).getPiece();
if (pageList.get(j).getModify() == 1) {
System.out.println("页" + 3 + "写到外存");
} else {
}
System.out.println("内存调出页" + j);
pageList.get(j).setFlag(0);
pageList.get(j).setModify(0);
pageList.get(j).setPiece(-1);
System.out.println("内存调入页" + L);
pageList.get(L).setFlag(1);
pageList.get(L).setPiece(tempPiece);
P[k] = L;
k = (k + 1) % m;
printPageList();
continue;
}
// 当前指令结束
cmdList.remove(0);
break;
}
}
}
private static void printPageList() {
System.out.println("==========================================================================");
System.out.print("页号\t标志\t主存块号\t修改标志\t在磁盘上的位置\n");
// finish链
for (Page page : pageList)
System.out.println(page.getPage() + "\t" + page.getFlag() + "\t" + page.getPiece() + "\t" + page.getModify()
+ "\t" + page.getPositionInDisk());
System.out.println("==========================================================================");
}
}page类
package report;
public class Page {
private int page;
private int flag;
private int piece;
private int modify;
private String positionInDisk;
public Page(int page, int flag, int piece, int modify, String positionInDisk) {
this.page = page;
this.flag = flag;
this.piece = piece;
this.modify = modify;
this.positionInDisk = positionInDisk;
}
public int getPage() {
return page;
}
public void setPage(int page) {
this.page = page;
}
public int getFlag() {
return flag;
}
public void setFlag(int flag) {
this.flag = flag;
}
public int getPiece() {
return piece;
}
public void setPiece(int piece) {
this.piece = piece;
}
public int getModify() {
return modify;
}
public void setModify(int modify) {
this.modify = modify;
}
public String getPositionInDisk() {
return positionInDisk;
}
public void setPositionInDisk(String positionInDisk) {
this.positionInDisk = positionInDisk;
}
}
运行过程部分截图
