Simulate virtual memory 

Virtual Memory System

1       PROJECT OVERVIEW

This project implements a virtual memory system (VM) using segmentation and paging. The system manages the necessary segment and page tables in a simulated main memory. It accepts virtual addresses and translates them into physical addresses according to the current contents of the segment and page tables. The system also utilizes a translation look-aside buffer (TLB) to make the translation process more efficient.

2       THE VIRTUAL MEMORY

We consider a virtual memory system and make the following assumptions:

• There is only a single process and hence only a single segment table (ST). Each entry of the ST points to a page table (PT), which in turn points to program/data pages
• A virtual address (VA) is assumed to be an integer and thus comprises 32 bits. These are divided into three components: the segment number, s, the page number, p, and the offset within the page, w. The sizes (in bits) of the three components are as follows:

|s| = 9, |p| = 10, |w| = 9

• Consequently, the size of the ST is 512 words (integers), the size of the each PT is 1024 words, and the size of each program/data page is 512 words.The leading 4 bits of the VA are unused.
• Each entry of the ST can have three types of entry:

o    ‒1 means the PT is currently not resident in physical memory. This would results in a page fault and the missing PT would be loaded from the disk. In this project we are not managing the disk and hence only a message will be generated.

• 0 means the corresponding PT does not exist. Consequently, a read access results in an error. A write access causes the creation of a new blank PT.
• a positive integer, f, means that the PT starts at physical address f .

• Similarly, each entry of a PT can have three types of entry:
  • ‒1 means the page is currently not resident in PM. Similar to a missing PT, a message is generated.
  • 0 means the corresponding page does not exist. A read access results in an error. A write access causes the allocation of a new blank page.
  • a positive integer, f, means that the page starts at physical address f .

3       THE Physical Memory

• The physical memory (PM) is represented as an array of integers, each corresponding to one addressable memory word. It is implemented as an array of 524,288 integers (= 2MB).
• These are divided into 1024 frames of size 512 words (integers). Consequently the size of a physical address (PA) is 19 bits.
• The ST occupies one frame, each PT occupies two (consecutive) frames, and each program/data page occupies one frame.
• The ST always resides in frame 0 of PM and is never paged out. A program/data page may be placed into any free frame. A PT may be placed into any pair of consecutive free frames.

The figure below shows the organization of the VM in PM:

ST occupies the first PM frame and thus each PM[s] is the staring address of a PT. If it is >0 then the PT resides in PM. Similarly, each PT entry PM[PM[s]+p] is the starting address of a page. If it is >0, then the corresponding page resides in PM.

• A bit map is used to keep track of which frames are occupied and which are free. The bit map consists of 1024 bits (one per frame) and thus can be implemented as an array of 32 integers. (Normally this would be maintained somewhere within the PM but for the purposes of this project it may be implemented as a separate data structure.)

1       The Address Translation Process

The main task of the VM system is to repeatedly accept VA’s and attempt to translate them to the corresponding PA’s. The first step is to break each VA into the three components s, p, w. The system then accesses the corresponding ST and PT entries to derive the final PA. Depending on the contents of each entry and the type of memory access (read or write), the system acts as follows:

• For a read operation to the VA:

o    If a ST entry (PM[s]) or a PT entry (PM[PM[s] + p]) equals ‒1 then output “pf” (page fault) and continuewith the next VA.

o    If a ST entry or a PT entry equals 0, then output “err” (error) and continue with the next VA.

o    Otherwise output the corresponding PA = PM[PM[s] + p] + w

• For a write operation to the VA:

o    If a ST entry or a PT entry equals ‒1 then output “pf” (page fault) and continuewith the next VA.

o    If a ST entry equals 0 then allocate a new blank PT (all zeroes), update the ST entry accordingly, and continue with the translation process; if a PT entry equals 0 then create a new blank page, and continue with the translation process.

o    Otherwise output the corresponding PA = PM[PM[s] + p] + w

Note that creating a new page involves modifying the corresponding PT. It also involves searching the bit map for a free frame and updating the bitmap to indicate that this frame is no longer available. Similarly, creating a new PT involves modifying the ST. It also involves searching the bit map for two consecutive free frames and updating the bitmap accordingly.

2       Initialization of the Physical Memory

You will be given the initial contents of PM in an input file. This file specifies the starting address of all PT’s and all program/data pages in PM. (ST always starts at address 0.) The file has the following format:

s₁f₁ s₂ f₂ … s_nf_n

p₁ s₁ f₁ p₂ s₂ f₂ …p_ms_mf_m

Each pair s_i f_i means that the PT of segment s_istartsat address f_i. If f_i = ‒1 then the corresponding PT is not resident in PM.

For example, 15 512 means that the PT of segment 15 starts at address 512. That is, ST[15] = 512. Similarly, 9 ‒1 means that the PT of segment 9 is not resident. That is, ST[9] = ‒1

Each triple p_js_jf_j means that the page p_j of segment s_jstartsat address f_jIf f_i = ‒1 then the corresponding page is not resident in PM.

For example, 7 13 4096 means that page 7 of segment 13 starts at address 4096. That is, PT[ST[13]+7] = 4096.

Based on the above specifications, the initialization of the PM must proceed as follows:

• Read the series of pairs (line 1) and make the corresponding entries in the ST
• Read the series of triples (line 2) and make the corresponding entries in the PT’s
• Create the bitmap to indicate which frames have remained free

3       Running the VA Translations

Once the PM has been initialized, the system is ready to accept VA’s and to attempt to translate them into PA’s. The VA’s will be given in another input file.

Since the translation depends on whether the memory access is a read or a write operation (Section 4), each VA will be preceded by a 0 (indicating a read) or a 1 (indicating a write). Hence this input file has the following format:

o₁ VA₁ o₂ VA₂ … o_nVA_n

where each o_i is either a 0 or 1 and each VA_iis a positive integer corresponding to a virtual address. All value are separated by blanks.

Your assignment is to read the file and for each pair o_iVA_iattempt to translate the VA according to the rules of Section 4. The result of each translation is to be written into another file.

4       THE Translation Look-aside Buffer

To speed up the address translation process, a Translation Look-aside Buffer (TLB) can be employed. For this project we implement a TLB as shown in Figure 8-10 and make the following assumptions:

• The size of the TLB is 4 lines.
• The first field contains the LRU information, which is an integer in the range from 0 to 3. Zero corresponds to the least recently accessed page and 3 corresponds to the most recently accessed one. If a new entry is to be made into the TLB then the least recently accessed entry is replaced.
• The second field contains an integer representing the combined parts s and p of the VA.
• The third field, f, is the starting PA of the frame corresponding to the sp value.

5       Running the VA Translations with the TLB

For each VM to be translated, the system performs the following operations:

• Break the VA into two components, sp, and w, each represented as an integer
• Search the TLB for a match on sp
• If a match is found (called a TLB hit) then:

o    use the corresponding f from the TLB to form the physical address, PA = f+w

o    update the LRU fields as follows:

• Assume that the match is in line k. Then:
• Decrement all LRU values that are greater than LRU[k] by 1
• Set LRU[k] to the maximum, i.e., 3.
• If no match is found (called a TLB miss) then:

o    Resolve the VA as described in Section 4. In case of an error or a page fault, there is no change to the TLB. But if a valid PA is derived then the TLB is updated as follows:

• Select the line with LRU = 0 and set the LRU value to the maximum, i.e., 3
• Replace the sp field of that line with the new sp value
• Replace the f field of that line with PM[PM[s] + p]
• Decrement all other LRU values by 1
• Output the PA or “pf” or “err” as before. For each translation, indicate also whether a miss or hit occurred in the TLB by outputting “m” or “h” in front of each item.

6       SUMMARY OF SPECIFIC TASKS

1. Design and implement a VM system using segmentation and paging as described above.
2. Design and implement a TLB to speed up the address translation process.
3. Design and implement a driver program that initializes the system from a given input file. It then reads another input file and, for each VA, attempts to translate it to the corresponding PA. It outputs the result of each address translation into a new file. 

Solution 

BitMap.java 

public class BitMap {

long[] bitmap;

long[] mask;

long[] mask2;

publicBitMap() {

bitmap = new long[32];

mask = new long[32];

mask2 = new long[32];

mask[31] = 1;

for (int i = 30; i >= 0; i–) {

mask[i] = mask[i + 1] << 1;

}

for (int i = 0; i < 32; i++) {

mask2[i] = ~mask[i];

}

}

public void setOne(int i) {

bitmap[i / 32] = bitmap[i / 32] | mask[i % 32];

}

public void setZero(int i) {

bitmap[i / 32] = bitmap[i / 32] | mask2[i % 32];

}

@Override

public String toString() {

String ret = “”;

for (int i = 0; i < 32; i++) {

ret += Integer.toBinaryString((int) bitmap[i]) + ” “;

}

return ret;

}

publicintfindOne() {

for (int i = 0; i < 32; i++) {

for (int j = 0; j < 32; j++) {

long test = bitmap[i] & mask[j];

if (test == 0) {

return (i * 32) + j;

}

}

}

return -1;

}

publicintfindTwo() {

for (int i = 0; i < 32; i++) {

for (int j = 0; j < 31; j++) {

long test1 = bitmap[i] & mask[j];

long test2 = bitmap[i] & mask[j + 1];

if (test1 == 0 && test2 == 0) {

return (i * 32) + j;

}

}

}

return -1;

}

} 

Driver.java 

public class Driver {

public static void main(String[] args) {

Initializer Initializer;

System.out.println(“Well come to Virtual Memory System Simulator”);

//Initializer = new Initializer(“input1.txt”, “input2.txt”);

Initializer = new Initializer(“/home/tannt/workspace/test/input1_more.txt”, “/home/tannt/workspace/test/input2_more.txt”);

Initializer.run();

}

} 

Initializer.java 

import java.io.*;

importjava.util.Scanner;

public class Initializer {

StringBuilder sb1;

StringBuilder sb2;

BufferedWriter bw1;

FileWriter fw1;

BufferedWriter bw2;

FileWriter fw2;

PM PM1;

PM PM2;

String path1;

String path2;

String outpath1;

String outpath2;

public Initializer() {

sb1 = new StringBuilder();

sb2 = new StringBuilder();

}

public Initializer(String path1, String path2) {

this.path1 = path1;

this.path2 = path2;

outpath1 = path1.substring(0, path1.lastIndexOf(‘/’)) + “/output_notbl.txt”;

outpath2 = path2.substring(0, path2.lastIndexOf(‘/’)) + “/output_tbl.txt”;

System.out.println(“Output to: ” + outpath1 + ” for no TLB flag”);

System.out.println(“Output to: ” + outpath2 + ” with TLB flag”);

sb1 = new StringBuilder();

sb2 = new StringBuilder();

}

public void run() {

Scanner sc1 = null;

Scanner sc2 = null;

try {

sc1 = new Scanner(new File(path1));

} catch (FileNotFoundException e) {

e.printStackTrace();

}

String line1 = sc1.nextLine();

PM1 = new PM(false);

PM2 = new PM(true);

String line2 = sc1.nextLine();

PM1.init(line1, line2);

PM2.init(line1, line2);

try {

sc2 = new Scanner(new File(path2));

} catch (FileNotFoundException e) {

e.printStackTrace();

}

String line3 = sc2.nextLine();

sb1.append(PM1.translate(line3));

sb2.append(PM2.translate(line3));

if (sc1 != null)

sc1.close();

if (sc2 != null)

sc2.close();

try {

fw1 = new FileWriter(outpath1);

bw1 = new BufferedWriter(fw1);

bw1.write(sb1.toString());

fw2 = new FileWriter(outpath2);

bw2 = new BufferedWriter(fw2);

bw2.write(sb2.toString());

System.out.println(“Write finished”);

} catch (Exception e) {

e.printStackTrace();

} finally {

try {

if (bw1 != null)

bw1.close();

if (bw2 != null)

bw2.close();

if (fw1 != null)

fw1.close();

if (fw2 != null)

fw2.close();

} catch (Exception e) {

}

}

}

} 

PM.java 

public class PM {

int[] frame;

int size = 1024 * 512;

boolean TLB;

BitMapbm;

TLB tlb;

public PM(boolean b) {

this.TLB = b;

this.tlb = new TLB();

bm = new BitMap();

frame = new int[size];

for (int i = 0; i < 512; i++) {

frame[i] = 0;

}

for (int i = 512; i < size; i++) {

frame[i] = -1;

}

bm.setOne(0);

}

public void init(String line1, String line2) {

String[] param1 = line1.split(” “);

for (int i = 0; i < param1.length; i += 2) {

int segment = Integer.parseInt(param1[i]);

intaddr = Integer.parseInt(param1[i + 1]);

frame[segment] = addr;

if (addr != -1) {

for (int j = addr; j <addr + 1024; j++) {

frame[j] = 0;

}

int k = addr / 512;

bm.setOne(k);

bm.setOne(k + 1);

}

}

String[] param2 = line2.split(” “);

for (int i = 0; i < param2.length; i += 3) {

int index = frame[Integer.parseInt(param2[i + 1])];

int page = Integer.parseInt(param2[i]);

intaddr = Integer.parseInt(param2[i + 2]);

if (index > 0) {

frame[index + page] = addr;

if (addr != -1) {

for (int j = addr; j <addr + 512; j++) {

frame[j] = 0;

}

bm.setOne(addr / 512);

}

}

}

}

@Override

public String toString() {

return “PM [bm=” + bm + “]”;

}

public String translate(String line) {

String ret = “”;

String[] words = line.split(” “);

VA va = null;

if (TLB == false) {

for (int i = 0; i <words.length; i += 2) {

va = new VA(Integer.parseInt(words[i + 1]));

if (Integer.parseInt(words[i]) == 0)

ret += read(va) + ” “;

else

ret += write(va) + ” “;

}

} else {

for (int i = 0; i <words.length; i += 2) {

va = new VA(Integer.parseInt(words[i + 1]));

if (Integer.parseInt(words[i]) == 0)

ret += readTLB(va) + ” “;

else

ret += writeTLB(va) + ” “;

}

}

return ret;

}

private String writeTLB(VA va) {

intsp = va.getSp();

if (tlb.search(sp)) {

return “h ” + (tlb.highest() + va.getW());

}

int s = frame[va.getS()];

int p = frame[s + va.getP()];

String F = write(va);

if (!F.equals(“pf”) && !F.equals(“err”)) {

int f = Integer.parseInt(F);

tlb.update(sp, f);

}

return “m ” + F;

}

private String readTLB(VA va) {

intsp = va.getSp();

if (tlb.search(sp)) {

return “h ” + (tlb.highest() + va.getW());

}

int s = frame[va.getS()];

int p = frame[s + va.getP()];

String F = read(va);

if (!F.equals(“pf”) && !F.equals(“err”)) {

if (s != -1 && p != -1)

tlb.update(sp, p);

}

return “m ” + read(va);

}

private String read(VA va) {

int s = frame[va.getS()];

if (s == -1) {

return “pf”;

}

if (s == 0) {

return “err”;

}

int p = frame[s + va.getP()];

if (p == -1) {

return “pf”;

}

if (p == 0) {

return “err”;

}

int w = p + va.getW();

return “” + w;

}

private String write(VA va) {

int s = frame[va.getS()];

if (s == -1) {

return “pf”;

}

int p = frame[s + va.getP()];

if (p == -1) {

return “pf”;

}

if (s == 0) {

int i = bm.findTwo();

bm.setOne(i);

bm.setOne(i + 1);

int F = i * 512;

frame[va.getS()] = F;

for (int j = F; j < F + 1024; j++) {

frame[j] = 0;

}

int j = bm.findOne();

bm.setOne(j);

int P = j * 512;

frame[F + va.getP()] = P;

for (int k = P; k < P + 512; k++) {

frame[k] = 0;

}

} else if (p == 0) {

int i = bm.findOne();

bm.setOne(i);

int F = i * 512;

frame[frame[va.getS()] + va.getP()] = F;

for (int k = F; k < F + 512; k++) {

frame[k] = 0;

}

}

int w = frame[frame[va.getS()] + va.getP()] + va.getW();

return “” + w;

}

} 

TLB.java 

importjava.util.Arrays;

public class TLB {

TLBtuple[] LRU;

public TLB() {

LRU = new TLBtuple[4];

for (int i = 0; i < 4; i++) {

LRU[i] = new TLBtuple();

}

}

publicboolean search(intsp) {

int index = 0;

for (int i = 0; i < 4; i++) {

if (LRU[i].getSp() == sp) {

index = i;

for (int j = 0; j < 4; j++) {

if (LRU[j].getFreq() > LRU[index].getFreq()) {

LRU[j].dec();

}

}

LRU[index].setFreq(3);

return true;

}

}

return false;

}

publicint highest() {

for (int i = 0; i < 4; i++) {

if (LRU[i].getFreq() == 3) {

return LRU[i].getFrame();

}

}

return 0;

}

public void update(intsp, int frame) {

for (int i = 0; i < 4; i++) {

LRU[i].dec();

}

for (int i = 0; i < 4; i++) {

if (LRU[i].getFreq() == -1) {

LRU[i].setFreq(3);

LRU[i].setSp(sp);

LRU[i].setFrame(frame);

return;

}

}

}

@Override

public String toString() {

return “TLB [LRU=” + Arrays.toString(LRU) + “]”;

}

} 

TLBtuple.java

public class TLBtuple {

intfreq;

intsp = -1;

int frame = -1;

public void inc() {

freq++;

if (freq> 3)

freq = 3;

}

public void dec() {

freq–;

if (freq< -1)

freq = -1;

}

publicintgetFreq() {

returnfreq;

}

publicintgetSp() {

returnsp;

}

publicintgetFrame() {

return frame;

}

public void setFreq(intfreq) {

this.freq = freq;

}

public void setSp(intsp) {

this.sp = sp;

}

public void setFrame(int frame) {

this.frame = frame;

}

@Override

public String toString() {

return “TLBtuple [freq=” + freq + “, sp=” + sp + “, frame=” + frame + “]”;

}

} 

VA.java

public class VA {

intva;

int s;

int p;

int w;

intsp;

public VA(intaddr) {

va = addr;

String bi = Integer.toBinaryString(addr);

int length = bi.length();

for (int i = length; i < 32; i++) {

bi = “0” + bi;

}

s = Integer.parseInt(bi.substring(4, 13), 2);

p = Integer.parseInt(bi.substring(13, 23), 2);

w = Integer.parseInt(bi.substring(23), 2);

sp = Integer.parseInt(bi.substring(4, 23), 2);

}

publicintgetVa() {

returnva;

}

publicintgetS() {

return s;

}

publicintgetP() {

return p;

}

publicintgetW() {

return w;

}

publicintgetSp() {

returnsp;

}

}