0% found this document useful (0 votes)

20 views62 pages

Java Two Pass Assembler Implementation

Q: Evaluate the effectiveness of the Least Recently Used (LRU) page replacement algorithm in comparison to FIFO in terms of hit ratio.

The Least Recently Used (LRU) page replacement algorithm is generally more effective than FIFO in terms of hit ratio because it considers the recency of page accesses, replacing the least recently used page rather than strictly following the order of page arrival as in FIFO. By maintaining a stack or a similar data structure to track the order of usage, LRU minimizes the chances of frequently accessed pages being replaced prematurely, often resulting in a higher hit ratio compared to FIFO, which may replace useful pages merely due to their arrival time .

Q: How is the Argument List Array (ALA) updated during Pass 2 of macro processing, and what is its significance in the expansion process?

During Pass 2 of macro processing, the Argument List Array (ALA) is updated by assigning actual parameter values from macro calls to corresponding formal parameters stored in the ALA. This involves parsing the macro call to extract arguments, replacing placeholder indices with actual argument values. The updated ALA is crucial as it allows for accurate substitution of arguments during macro expansion, ensuring that each parameter in the Macro Definition Table (MDT) is replaced correctly using the actual values from the macro invocation .

Q: What information is stored in the Macro Definition Table (MDT) during macro processing, and how is it utilized in Pass 2?

The Macro Definition Table (MDT) stores the sequence of instructions that define the body of each macro, including placeholders for arguments. It is indexed using the Macro Name Table (MNT) to facilitate access. During Pass 2, the MDT is utilized to retrieve and expand the macro definitions at every macro call in the input code. The corresponding actual arguments are substituted into the MDT entries using indices and placeholders defined in the Argument List Array (ALA), allowing for accurate macro expansion with the correct argument values .

Q: Explain how the two-pass macro assembler differentiates between macro definitions and regular instructions in Pass 1.

In Pass 1 of the two-pass macro assembler, macro definitions are identified by the presence of the keyword 'MACRO'. When this is encountered, the 'processMacroDefinition' method is invoked, which reads and processes the macro definition until a 'MEND' is encountered. This involves creating entries in the Macro Name Table (MNT) for the macro's name and its index in the Macro Definition Table (MDT). Regular instructions are simply written to the output file without special processing .

Q: What are the roles of the Macro Name Table (MNT) and Argument List Array (ALA) during the first pass of macro processing?

During the first pass of macro processing, the Macro Name Table (MNT) stores information about each macro name and its location in the Macro Definition Table (MDT), facilitating the identification and retrieval of macro bodies during Pass 2. The Argument List Array (ALA) stores parameter names and indices used in macro definitions, allowing for proper substitution during macro expansion. This ensures that each macro call in the source code can accurately substitute parameters and expand using the MDT's stored macro body .

Q: Analyze how the page replacement algorithm's implementation in the LRU program manages the 'full' state of the buffer and ensures correct page replacement.

In the LRU program, the 'full' state of the buffer is managed using a boolean flag 'isFull'. This is initially set to false while the buffer is being filled. Once the buffer is filled to capacity, 'isFull' is set to true. In this state, the program searches for the page in the buffer that is least recently used, determined by the page's position in a stack that tracks page usage order. The identified page is then replaced with the new page from the reference string. This ensures efficient page replacement based on recency of use rather than order of arrival .

Q: Describe the mechanism by which page faults are handled in the FIFO page replacement algorithm.

In the FIFO page replacement algorithm, page faults occur when a page being referenced is not in the current set of frames, triggering the replacement of the oldest page in memory. This mechanism uses a pointer to keep track of the frame to be replaced next. When a page fault occurs, the page at the current pointer's location is replaced with the new page, and the pointer is then advanced. If the pointer reaches the end, it wraps around to the beginning, maintaining a circular buffer approach .

Q: Explain how operand tokenization is performed and why it is important in the context of the assembler process.

Operand tokenization in the assembler process is performed using the string tokenization method where each operand is split based on delimiters such as spaces and commas. The 'tokenizeOperands' method as described breaks the final operand string into separate tokens, which are then added to a list. This process is crucial as it prepares the operands for further processing by the assembler, ensuring that each operation can be accurately parsed, and corresponding machine code instructions can be generated correctly .

Q: How does the symbol table initialization process occur, and what data structures are involved in it?

The symbol table initialization process occurs in the 'initializeTables' method where the 'symtable' is initialized using a LinkedList. Other data structures involved include 'basetable' which is a HashMap, and 'mot' and 'pot' which are also LinkedLists. The method reads data from 'mot.txt' for the operation table, sorting 'pot' for the pseudo-operation table. Each entry from the files is tokenized and added to the respective data structures .

Q: What is the significance of the 'AL' attribute in the assembler, and how does it affect the compilation process?

The 'AL' (Allow/Retract) attribute in the assembler is significant as it determines whether a certain symbol or directive can be altered during the assembly process. Symbols with a retractable attribute ('R') can be modified or moved, while those marked with a 'A' (Allow) remain fixed in their allocation and cannot be subject to certain optimizations. This impacts the compilation process by dictating whether particular data elements can be shuffled for optimization purposes, thus affecting both the compilation time and the execution efficiency of the generated machine code .

The document contains two Java programs that implement a two-pass assembler. The first program focuses on creating a symbol table and a machine operation table (MOT) from assembly code, while the second program enhances the assembler by including literal handling and more complex operations. Both programs demonstrate the parsing of assembly instructions and the generation of corresponding output tables.

Uploaded by

Vaibhav Kale

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as DOCX, PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

20 views62 pages

Java Two Pass Assembler Implementation

Uploaded by

Vaibhav Kale

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as DOCX, PDF, TXT or read online on Scribd

**PROGRAM 1:-

/* PASS-1 OF TWO PASS ASSEMBLER */

import [Link].*;

class P1

public static void main(String ar[])throws IOException

BufferedReader br=new BufferedReader(new InputStreamReader([Link]));

int i;

String a[][]={{"","START","101",""},

{"","MOVER","BREG","ONE"},

{"AGAIN","MULT","BREG","TERM"},

{"","MOVER","CREG","TERM"},

{"","ADD","CREG","N"},

{"","MOVEM","CREG","TERM"},

{"N","DS","2",""},

{"RESULT","DS","2",""},

{"ONE","DC","1",""},

{"TERM","DS","1",""},

{"","END","",""}};

int lc=[Link](a[0][2]);

String st[][]=new String[5][2];

int cnt=0,l;

for (i=1;i<11;i++)

if (a[i][0]!="")

st [cnt][0]=a[i][0];

st[cnt][1]=[Link](lc);
cnt++;

if(a[i][1]=="DS")

int d=[Link](a[i][2]);

lc=lc+d;

else

lc++;

else

lc++;

[Link]("***SYMBOL TABLE****\n");

[Link]("_____________________");

for(i=0;i<5;i++)

for(cnt=0;cnt<2;cnt++)

[Link](st[i][cnt]+"\t");

} [Link]();

String
inst[]={"STOP","ADD","SUB","MULT","MOVER","MOVEM","COMP","BC","DIV","READ","PRINT"};

String reg[]={"NULL","AREG","BREG","CREG","DREG"};

int op[][]=new int[12][3];

int j,k,p=1,cnt1=0;

for(i=1;i<11;i++)
{

for(j=0;j<11;j++)

if(a[i][1].equalsIgnoreCase(inst[j]))

op[cnt1][0]=j;

else

if(a[i][1].equalsIgnoreCase("DS"))

p=[Link](a[i][2]);

else if(a[i][1].equalsIgnoreCase("DC"))

op[cnt1][2]=[Link](a[i][2]);

for(k=0;k<5;k++)

if(a[i][2].equalsIgnoreCase(reg[k]))

op[cnt1][1]=k;

for(l=0;l<5;l++)

if(a[i][3].equalsIgnoreCase(st[l][0]))

int mn=[Link](st[l][1]);

op[cnt1][2]=mn;

}
}

cnt1=cnt1+p;

[Link]("\n *****OUTPUT*****\n");

[Link]("**********MOT TABLE**********");

int dlc=[Link](a[0][2]);

for(i=0;i<12;i++)

[Link](dlc+++"\t");

for(j=0;j<3;j++)

[Link](" "+op[i][j]+" ");

[Link]();

[Link]("");

}
**OUTPUT:-

***SYMBOL TABLE****

_____________________

AGAIN 102

N 106

RESULT 108

ONE 110

TERM 111

*****OUTPUT*****

**********MOT TABLE**********

101 4 2 110

102 3 2 111

103 4 3 111

104 1 3 106

105 5 3 111

106 0 0 0

107 0 0 0

108 0 0 0

109 0 0 0

110 0 0 1

111 0 0 0

112 0 0 0
**PROGRAM 2:-

Program to implement 2 Pass Assembler in Java

import [Link].*;

class Tuple {

String mnemonic, bin_opcode, type;

int length;

Tuple() {}

Tuple(String s1, String s2, String s3, String s4) {

mnemonic = s1;

bin_opcode = s2;

length = [Link](s3);

type = s4;

class SymTuple {

String symbol, ra;

int value, length;

SymTuple(String s1, int i1, int i2, String s2) {

symbol = s1;

value = i1;

length = i2;
ra = s2;

class LitTuple {

String literal, ra;

int value, length;

LitTuple() {}

LitTuple(String s1, int i1, int i2, String s2) {

literal = s1;

value = i1;

length = i2;

ra = s2;

class TwoPassAssembler {

static int lc;

static List<Tuple> mot;

static List<String> pot;

static List<SymTuple> symtable;

static List<LitTuple> littable;

static List<Integer> lclist;

static Map<Integer, Integer> basetable;

static PrintWriter out_pass2;

static PrintWriter out_pass1;

static int line_no;

public static void main(String args[]) throws Exception {

initializeTables();

[Link]("====== PASS 1 ======\n");

pass1();

[Link]("\n====== PASS 2 ======\n");

pass2();

static void pass1() throws Exception {

BufferedReader input = new BufferedReader(new InputStreamReader(new

FileInputStream("[Link]")));

out_pass1 = new PrintWriter(new FileWriter("output_pass1.txt"), true);

PrintWriter out_symtable = new PrintWriter(new FileWriter("out_symtable.txt"),

true);

PrintWriter out_littable = new PrintWriter(new FileWriter("out_littable.txt"), true);

String s;

while((s = [Link]()) != null) {

StringTokenizer st = new StringTokenizer(s, " ", false);

String s_arr[] = new String[[Link]()];

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

s_arr[i] = [Link]();

if(searchPot1(s_arr) == false) {

searchMot1(s_arr);

out_pass1.println(s);

[Link](lc);

int j;

String output = new String();

[Link]("Symbol Table:");

[Link]("Symbol Value Length R/A");

for(SymTuple i : symtable) {
output = [Link];

for(j=[Link]() ; j < 10 ; j++) {

output += " ";

output += [Link];

for(j=new Integer([Link]).toString().length() ; j < 7 ; j++) {

output += " ";

output += [Link] + " " + [Link];

[Link](output);

out_symtable.println(output);

[Link]("\nLiteral Table:");

[Link]("Literal Value Length R/A");

for(LitTuple i : littable) {

output = [Link];

for(j=[Link]() ; j < 10 ; j++) {

output += " ";

output += [Link];

for(j=new Integer([Link]).toString().length() ; j < 7 ; j++) {

output += " ";

output += [Link] + " " + [Link];

[Link](output);

out_littable.println(output);

static void pass2() throws Exception {

line_no = 0;
out_pass2 = new PrintWriter(new FileWriter("output_pass2.txt"), true);

BufferedReader input = new BufferedReader(new InputStreamReader(new

FileInputStream("output_pass1.txt")));

String s;

[Link]("Pass 2 input:");

while((s = [Link]()) != null) {

[Link](s);

StringTokenizer st = new StringTokenizer(s, " ", false);

String s_arr[] = new String[[Link]()];

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

s_arr[i] = [Link]();

if(searchPot2(s_arr) == false) {

searchMot2(s_arr);

line_no++;

[Link]("\nPass 2 output:");

input = new BufferedReader(new InputStreamReader(new

FileInputStream("output_pass2.txt")));

while((s = [Link]()) != null) {

[Link](s);

static boolean searchPot1(String[] s) {

int i = 0;

int l = 0;

int potval = 0;

if([Link] == 3) {

i = 1;
}

s = tokenizeOperands(s);

if(s[i].equalsIgnoreCase("DS") || s[i].equalsIgnoreCase("DC")) {

potval = 1;

if(s[i].equalsIgnoreCase("EQU")) {

potval = 2;

if(s[i].equalsIgnoreCase("START")) {

potval = 3;

if(s[i].equalsIgnoreCase("LTORG")) {

potval = 4;

if(s[i].equalsIgnoreCase("END")) {

potval = 5;

switch(potval) {

case 1:

// DS or DC statement

String x = s[i+1];

int index = [Link]("F");

if(i == 1) {

[Link](new SymTuple(s[0], lc, 4, "R"));

if(index != 0) {

// Ends with F

l = [Link]([Link](0, [Link]()-1));

l *= 4;
} else {

// Starts with F

for(int j=i+1 ; j<[Link] ; j++) {

l += 4;

lc += l;

return true;

case 2:

// EQU statement

if(!s[2].equals("*")) {

[Link](new SymTuple(s[0], [Link](s[2]),

"A"));

} else {

[Link](new SymTuple(s[0], lc, 1, "R"));

return true;

case 3:

// START statement

[Link](new SymTuple(s[0], [Link](s[2]), 1, "R"));

return true;

case 4:

// LTORG statement

ltorg(false);

return true;

case 5:

// END statement
ltorg(true);

return true;

return false;

static void searchMot1(String[] s) {

Tuple t = new Tuple();

int i = 0;

if([Link] == 3) {

i = 1;

s = tokenizeOperands(s);

for(int j=i+1 ; j < [Link] ; j++) {

if(s[j].startsWith("=")) {

[Link](new LitTuple(s[j].substring(1, s[j].length()), -1, 4, "R"));

if((i == 1) && (!s[0].equalsIgnoreCase("END"))) {

[Link](new SymTuple(s[0], lc, 4, "R"));

for(Tuple x : mot) {

if(s[i].equals([Link])) {

t = x;

break;

lc += [Link];

static void ltorg(boolean isEnd) {

Iterator<LitTuple> itr = [Link]();

LitTuple lt = new LitTuple();

boolean isBroken = false;

while([Link]()) {

lt = [Link]();

if([Link] == -1) {

isBroken = true;

break;

if(!isBroken) {

return;

if(!isEnd) {

while(lc%8 != 0) {

lc++;

[Link] = lc;

lc += 4;

while([Link]()) {

lt = [Link]();

[Link] = lc;

lc += 4;

static boolean searchPot2(String[] s) {

int i = 0;

if([Link] == 3) {
i = 1;

if([Link](pot, s[i]) >= 0) {

if(s[i].equalsIgnoreCase("USING")) {

s = tokenizeOperands(s);

if(s[i+1].equals("*")) {

s[i+1] = [Link](line_no) + "";

} else {

for(int j=i+1 ; j<[Link] ; j++) {

int value = getSymbolValue(s[j]);

if(value != -1) {

s[j] = value + "";

[Link](new Integer(s[i+2].trim()), new Integer(s[i+1].trim()));

return true;

return false;

static void searchMot2(String[] s) {

Tuple t = new Tuple();

int i = 0;

int j;

if([Link] == 3) {

i = 1;

}
s = tokenizeOperands(s);

for(Tuple x : mot) {

if(s[i].equals([Link])) {

t = x;

break;

String output = new String();

String mask = new String();

if(s[i].equals("BNE")) {

mask = "7";

} else if(s[i].equals("BR")) {

mask = "15";

} else {

mask = "0";

if(s[i].startsWith("B")) {

if(s[i].endsWith("R")) {

s[i] = "BCR";

} else {

s[i] = "BC";

List<String> temp = new ArrayList<>();

for(String x : s) {

[Link](x);

[Link](i+1, mask);

s = [Link](new String[0]);

}
if([Link]("RR")) {

output = s[i];

for(j=s[i].length() ; j<6 ; j++) {

output += " ";

for(j=i+1 ; j<[Link] ; j++) {

int value = getSymbolValue(s[j]);

if(value != -1) {

s[j] = value + "";

output += s[i+1];

for(j=i+2 ; j<[Link] ; j++) {

output += ", " + s[j];

} else {

output = s[i];

for(j=s[i].length() ; j<6 ; j++) {

output += " ";

for(j=i+1 ; j<[Link]-1 ; j++) {

int value = getSymbolValue(s[j]);

if(value != -1) {

s[j] = value + "";

s[j] = createOffset(s[j]);

output += s[i+1];

for(j=i+2 ; j<[Link] ; j++) {

output += ", " + s[j];

}
}

out_pass2.println(output);

static String createOffset(String s) {

String original = s;

Integer[] key = [Link]().toArray(new Integer[0]);

int offset, new_offset;

int index = 0;

int value = -1;

int index_reg = 0;

if([Link]("=")) {

value = getLiteralValue(s);

} else {

int paranthesis = [Link]("(");

String index_string = new String();

if(paranthesis != -1) {

s = [Link](0, [Link]("("));

index_string = [Link]([Link]("(")+1,
[Link](")"));

index_reg = getSymbolValue(index_string);

value = getSymbolValue(s);

offset = [Link](value - [Link](key[index]));

for(int i=1 ; i<[Link] ; i++) {

new_offset = [Link](value - [Link](key[i]));

if(new_offset < offset) {

offset = new_offset;

index = i;

}
}

String result = offset + "(" + index_reg + ", " + key[index] + ")";

return result;

static int getSymbolValue(String s) {

for(SymTuple st : symtable) {

if([Link]([Link])) {

return [Link];

return -1;

static int getLiteralValue(String s) {

s = [Link](1, [Link]());

for(LitTuple lt : littable) {

if([Link]([Link])) {

return [Link];

return -1;

static String[] tokenizeOperands(String[] s) {

List<String> temp = new LinkedList<>();

for(int j=0 ; j<[Link]-1 ; j++) {

[Link](s[j]);

StringTokenizer st = new StringTokenizer(s[[Link]-1], " ,", false);

while([Link]()) {
[Link]([Link]());

s = [Link](new String[0]);

return s;

static void initializeTables() throws Exception {

symtable = new LinkedList<>();

littable = new LinkedList<>();

lclist = new ArrayList<>();

basetable = new HashMap<>();

mot = new LinkedList<>();

pot = new LinkedList<>();

String s;

BufferedReader br;

br = new BufferedReader(new InputStreamReader(new

FileInputStream("[Link]")));

while((s = [Link]()) != null) {

StringTokenizer st = new StringTokenizer(s, " ", false);

[Link](new Tuple([Link](), [Link](), [Link](),

[Link]()));

br = new BufferedReader(new InputStreamReader(new FileInputStream("[Link]")));

while((s = [Link]()) != null) {

[Link](s);

[Link](pot);

}
**OUTPUT:-

Symbol Table:

Symbol Value Length R/A

PRGAM2 0 1 R

AC 2 1 A

INDEX 3 1 A

TOTAL 4 1 A

DATABASE 13 1 A

SETUP 6 1 R

LOOP 12 4 R

SAVE 64 4 R

DATAAREA 76 1 R

DATA1 76 4 R

Literal Table:

Literal Value Length R/A

A(DATA1) 48 4 R

F'5' 52 4 R

F'4' 56 4 R

F'8000' 60 4 R

====== PASS 2 ======

Pass 2 input:

USING *,15

LA 15,SETUP

SR TOTAL,TOTAL

USING SETUP,15

L DATABASE,=A(DATA1)

USING DATAAREA,DATABASE
SR INDEX,INDEX

LOOP L AC,DATA1(INDEX)

AR TOTAL,AC

A AC,=F'5'

ST AC,SAVE(INDEX)

A INDEX,=F'4'

C INDEX,=F'8000'

BNE LOOP

LR 1,TOTAL

BR 14

Pass 2 output:

LA 15, 6(0, 15)

SR 4, 4

L 13, 42(0, 15)

SR 3, 3

L 2, 0(3, 13)

AR 4, 2

A 2, 24(0, 13)

ST 2, 12(3, 13)

A 3, 20(0, 13)

C 3, 16(0, 13)

BC 7, 6(0, 15)

LR 1, 4

BCR 15, 14

lab-a-26@laba26-Vostro-3669:~/Documents/sp os/Untitled Folder/a1$

**PROGRAM 3:-
MACRO:-

import [Link].*;

class MACRO

static String mnt[][]=new String[5][3]; //assuming 5 macros in 1 program

static String ala[][]=new String[10][2]; //assuming 2 arguments in each macro

static String mdt[][]=new String[20][1]; //assuming 4 LOC for each macro

static int mntc=0,mdtc=0,alac=0;

public static void main(String args[])

pass1();

[Link]("\n*********PASS-1 MACROPROCESSOR***********\n");

[Link]("MACRO NAME TABLE (MNT)\n");

[Link]("i macro loc\n");

display(mnt,mntc,3);

[Link]("\n");

[Link]("ARGUMENT LIST ARRAY(ALA) for Pass1\n");

display(ala,alac,2);

[Link]("\n");

[Link]("MACRO DEFINITION TABLE (MDT)\n");

display(mdt,mdtc,1);

[Link]("\n");

static void pass1()

int index=0,i;

String s,prev="",substring;

try

{
BufferedReader inp = new BufferedReader(new FileReader("[Link]"));

File op = new File("pass1_output.txt");

if (![Link]())

[Link]();

BufferedWriter output = new BufferedWriter(new FileWriter([Link]()));

while((s=[Link]())!=null)

if([Link]("MACRO"))

prev=s;

for(;!(s=[Link]()).equalsIgnoreCase("MEND");mdtc++,prev=s)

if([Link]("MACRO"))

StringTokenizer st=new StringTokenizer(s);

String str[]=new String[[Link]()];

for(i=0;i<[Link];i++)

str[i]=[Link]();

mnt[mntc][0]=(mntc+1)+""; //mnt formation

mnt[mntc][1]=str[0];

mnt[mntc++][2]=(++mdtc)+"";

st=new StringTokenizer(str[1],","); //tokenizing the arguments

String string[]=new String[[Link]()];

for(i=0;i<[Link];i++)

string[i]=[Link]();

ala[alac][0]=alac+""; //ala table formation

index=string[i].indexOf("=");

if(index!=-1)

ala[alac++][1]=string[i].substring(0,index);

else
ala[alac++][1]=string[i];

else //automatically eliminates tagging of arguments in definition

{ //mdt formation

index=[Link]("&");

substring=[Link](index);

for(i=0;i<alac;i++)

if(ala[i][1].equals(substring))

s=[Link](substring,"#"+ala[i][0]);

mdt[mdtc-1][0]=s;

else

[Link](s);

[Link]();

catch(FileNotFoundException ex)

[Link]("UNABLE TO END FILE ");

catch(IOException e)

[Link]();

}
}

static void display(String a[][],int n,int m)

int i,j;

for(i=0;i<n;i++)

for(j=0;j<m;j++)

[Link](a[i][j]+" ");

[Link]();

}
**OUTPUT:-

lab-a-26@laba26-Vostro-3669:~/Documents/sp os/spos/a3$ javac [Link]

lab-a-26@laba26-Vostro-3669:~/Documents/sp os/spos/a3$ java MACRO

*********PASS-1 MACROPROCESSOR***********

MACRO NAME TABLE (MNT)

i macro loc

1 INCR1 1

2 INCR2 5

ARGUMENT LIST ARRAY(ALA) for Pass1

0 &FIRST

1 &SECOND

2 &ARG1

3 &ARG2

MACRO DEFINITION TABLE (MDT)

INCR1 &FIRST,&SECOND=DATA9

A 1,#0

L 2,#1

MEND

INCR2 &ARG1,&ARG2=DATA5

L 3,#2

ST 4,#3

MEND
**PROGRAM 4:-

Program to implement 2 Pass Macro Assembler in Java

import [Link].*;

class MntTuple {

String name;

int index;

MntTuple(String s, int i) {

name = s;

index = i;

public String toString() {

return("[" + name + ", " + index + "]");

class MacroProcessor {

static List<MntTuple> mnt;

static List<String> mdt;

static int mntc;

static int mdtc;

static int mdtp;

static BufferedReader input;

static List<List <String>> ala;

static Map<String, Integer> ala_macro_binding;

public static void main(String args[]) throws Exception {

initializeTables();

[Link]("===== PASS 1 =====\n");

pass1();

[Link]("\n===== PASS 2 =====\n");

pass2();

static void pass1() throws Exception {

String s = new String();

input = new BufferedReader(new InputStreamReader(new

FileInputStream("[Link]")));

PrintWriter output = new PrintWriter(new FileOutputStream("output_pass1.txt"),

true);

while((s = [Link]()) != null) {

if([Link]("MACRO")) {

processMacroDefinition();

} else {

[Link](s);

[Link]("ALA:");

showAla(1);

[Link]("\nMNT:");

showMnt();

[Link]("\nMDT:");

showMdt();

static void processMacroDefinition() throws Exception {

String s = [Link]();

String macro_name = [Link](0, [Link](" "));

[Link](new MntTuple(macro_name, mdtc));

mntc++;

pass1Ala(s);

StringTokenizer st = new StringTokenizer(s, " ,", false);

String x = [Link]();

for(int i=[Link]() ; i<12 ; i++) {

x += " ";

String token = new String();

int index;

token = [Link]();

x += token;

while([Link]()) {

token = [Link]();

x += "," + token;

[Link](x);

mdtc++;

addIntoMdt([Link]()-1);

static void pass1Ala(String s) {

StringTokenizer st = new StringTokenizer(s, " ,", false);

String macro_name = [Link]();

List<String> l = new ArrayList<>();

int index;

while([Link]()) {

String x = [Link]();

if((index = [Link]("=")) != -1) {

x = [Link](0, index);

[Link](x);

[Link](l);

ala_macro_binding.put(macro_name, ala_macro_binding.size());

static void addIntoMdt(int ala_number) throws Exception {

String temp = new String();

String s = new String();

List l = [Link](ala_number);

boolean isFirst;

while(![Link]("MEND")) {

isFirst = true;

s = [Link]();

String line = new String();

StringTokenizer st = new StringTokenizer(s, " ,", false);

temp = [Link]();

for(int i=[Link]() ; i<12 ; i++) {

temp += " ";

line += temp;

while([Link]()) {

temp = [Link]();

if([Link]("&")) {

int x = [Link](temp);

temp = ",#" + x;

isFirst = false;

} else if(!isFirst) {

temp = "," + temp;

}

line += temp;

[Link](line);

mdtc++;

static void showAla(int pass) throws Exception {

PrintWriter out = new PrintWriter(new FileOutputStream("out_ala_pass" + pass +

".txt"), true);

for(List l : ala) {

[Link](l);

static void showMnt() throws Exception {

PrintWriter out = new PrintWriter(new FileOutputStream("out_mnt.txt"), true);

for(MntTuple l : mnt) {

[Link](l);

static void showMdt() throws Exception {

PrintWriter out = new PrintWriter(new FileOutputStream("out_mdt.txt"), true);

for(String l : mdt) {

[Link](l);

}
}

static void pass2() throws Exception {

input = new BufferedReader(new InputStreamReader(new

FileInputStream("output_pass1.txt")));

PrintWriter output = new PrintWriter(new FileOutputStream("output_pass2.txt"),

true);

String token = new String();

String s;

while((s = [Link]()) != null) {

StringTokenizer st = new StringTokenizer(s, " ", false);

while([Link]()) {

token = [Link]();

if([Link]() > 2) {

token = [Link]();

MntTuple x = null;

for(MntTuple m : mnt) {

if([Link](token)) {

x = m;

break;

if(x != null) {

mdtp = [Link];

List<String> l = pass2Ala(s);

mdtp++;

String temp = new String();

while(!(temp =
[Link](mdtp)).trim().equalsIgnoreCase("MEND")) {

String line = new String();

StringTokenizer st2 = new StringTokenizer(temp,
" ,",false);

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

line += " ";

String opcode = [Link]();

line += opcode;

for(int i=[Link]() ; i<24 ; i++) {

line += " ";

line += [Link]();

while([Link]()) {

String token2 = [Link]();

int index;

if((index = [Link]("#")) != -1) {

line += "," +
[Link]([Link]([Link](index+1,index+2)));

mdtp++;

[Link](line);

break;

} else {

[Link](s);

break;

[Link]("\nALA:");
showAla(2);

static List<String> pass2Ala(String s) {

StringTokenizer st = new StringTokenizer(s, " ", false);

int num_tokens = [Link]();

String macro_name = [Link]();

int ala_no = ala_macro_binding.get(macro_name);

List<String> l = [Link](ala_no);

int ctr = 0;

StringTokenizer st2 = null;

try {

st2 = new StringTokenizer([Link](), ",", false);

while([Link]()) {

[Link](ctr, [Link]());

ctr++;

} catch(Exception e) {

// do nothing

if(ctr < num_tokens) {

String s2 = [Link](mdtp);

StringTokenizer st3 = new StringTokenizer(s2, " ,", false);

String token = new String();

int index = 0;

while([Link]()) {

token = [Link]();

if((index = [Link]("=")) != -1) {

try {

[Link](ctr++, [Link](index+1,
[Link]()));
} catch(Exception e) {

// do nothing

[Link](ala_no, l);

return l;

static void initializeTables() {

mnt = new LinkedList<>();

mdt = new ArrayList<>();

ala = new LinkedList<>();

mntc = 0;

mdtc = 0;

ala_macro_binding = new HashMap<>();

**OUTPUT:-

lab-a-26@laba26-Vostro-3669:~/Documents/sp os/spos/a4$ javac [Link]

lab-a-26@laba26-Vostro-3669:~/Documents/sp os/spos/a4$ java MacroProcessor

===== PASS 1 =====

ALA:

[&FIRST, &SECOND]

[&ARG1, &ARG2]

MNT:
[INCR1, 0]

[INCR2, 4]

MDT:

INCR1 &FIRST,&SECOND=DATA9

A 1,#0

L 2,#1

MEND

INCR2 &ARG1,&ARG2=DATA5

L 3,#0

ST 4,#1

MEND

===== PASS 2 =====

PRG2 START

USING *,BASE

A 1,DATA1

L 2,DATA2

L 3,DATA3

ST 4,DATA4

FOUR DC F'4'

FIVE DC F'5'

BASE EQU 8

TEMP DS 1F

DROP 8

END

ALA:

[DATA1, DATA2]

[DATA3, DATA4]
**PROGRAM 5:-

FCFS:-

import [Link];

class Fcfs

public static void main(String args[]){

int bst[],process[],wt[],tat[],i,j,n,total=0,pos,temp;

float wait_avg, TAT_avg;

Scanner s = new Scanner([Link]);

[Link]("Enter number of process: ");

n = [Link]();

process = new int[n];

bst = new int[n];

wt = new int[n];

tat = new int[n];

[Link]("\nEnter CPU time:");

for(i=0;i<n;i++)

[Link]("\nProcess["+(i+1)+"]: ");

bst[i] = [Link]();;

process[i]=i+1; //Process Number

[Link]("\t\t\t**********FCFS Scheduling*********");

//First process has 0 waiting time

wt[0]=0;//calculate waiting time

for(i=1;i<n;i++)

wt[i]=0;

for(j=0;j<i;j++)
wt[i]+=bst[j];

total+=wt[i];

//Calculating Average waiting time

wait_avg=(float)total/n;

total=0;

[Link]("-----------------------------------------------------------------------");

[Link]("\nProcess\t\t| Burst Time \t\t|Waiting Time\t\t|Turn Time");

[Link]("-----------------------------------------------------------------------");

for(i=0;i<n;i++)

tat[i]=bst[i]+wt[i];

total+=tat[i];//Calculating TurnaroundTimetotal+=tat[i];

[Link]("\np"+process[i]+"\t\t|\t"+bst[i]+"\t\t|\t"+wt[i]+"\t\t|\t"+tat[i]);

[Link]("-----------------------------------------------------------------------");

}//Calculation of Average Turnaround Time

TAT_avg=(float)total/n;

[Link]("\n\nAverage Waiting Time: "+wait_avg);

[Link]("\nAverage Turnaround Time: "+TAT_avg);

**OUTPUT:-

lab-a-26@laba26-Vostro-3669:~/Documents/sp os/spos/c10/FCFS$ javac [Link]

lab-a-26@laba26-Vostro-3669:~/Documents/sp os/spos/c10/FCFS$ java Fcfs

Enter number of process: 4

Enter CPU time:

Process[1]: 12

Process[2]: 13

Process[3]: 2

Process[4]: 3

**********FCFS Scheduling*********

-----------------------------------------------------------------------

Process | Burst Time |Waiting Time |Turn Time

-----------------------------------------------------------------------

p1 | 12 | 0 | 12

-----------------------------------------------------------------------

p2 | 13 | 12 | 25

-----------------------------------------------------------------------

p3 | 2 | 25 | 27

-----------------------------------------------------------------------

p4 | 3 | 27 | 30

-----------------------------------------------------------------------

Average Waiting Time: 16.0

Average Turnaround Time: 23.5

**PROGRAM 6:-

PRIORITY:-

import [Link];

public class priority {

public static void main(String args[]) {

Scanner s = new Scanner([Link]);

int x,n,p[],pp[],bt[],w[],t[],i;

float awt,atat;

p = new int[10];

pp = new int[10];

bt = new int[10];

w = new int[10];

t = new int[10];

//n is number of process

//p is process

//pp is process priority

//bt is process burst time

//w is wait time

// t is turnaround time

//awt is average waiting time

//atat is average turnaround time

[Link]("Enter the number of process : ");

n = [Link]();

[Link]("\n\t Enter CPU time---priority \n");

for(i=0;i<n;i++)

[Link]("\nProcess["+(i+1)+"]:");

bt[i] = [Link]();
pp[i] = [Link]();p[i]=i+1;

//sorting on the basis of priority

for(i=0;i<n-1;i++)

for(int j=i+1;j<n;j++)

if(pp[i]<pp[j])

x=pp[i];

pp[i]=pp[j];

pp[j]=x;

x=bt[i];

bt[i]=bt[j];

bt[j]=x;

x=p[i];

p[i]=p[j];

p[j]=x;

w[0]=0;

awt=0;

t[0]=bt[0];

atat=t[0];

for(i=1;i<n;i++)

w[i]=t[i-1];

awt+=w[i];

t[i]=w[i]+bt[i];

atat+=t[i];
}

//Displaying the process

[Link]("-----------------------------------------------------------------------");

[Link]("\n\nProcess \t\t |Burst Time \t\t |Wait Time \t\t |Turn Time \n");

[Link]("-----------------------------------------------------------------------");

for(i=0;i<n;i++)

[Link]("\n"+p[i]+"\t\t| "+bt[i]+"\t\t| "+w[i]+"\t\t|"+t[i]+"\t\t| "+pp[i]+"\n");

[Link]("-----------------------------------------------------------------------");

awt/=n;

atat/=n;

[Link]("\n Average Wait Time : "+awt);

[Link]("\n Average Turn Around Time : "+atat);

**OUTPUT:-

lab-a-26@laba26-Vostro-3669:~/Documents/sp os/spos/c10/priority$ java priority

Enter the number of process : 5

Enter CPU time---priority

Process[1]:10 3

Process[2]:1 1

Process[3]:2 3

Process[4]:1 4
Process[5]:5 2

-----------------------------------------------------------------------

Process |Burst Time |Wait Time |Turn Time

-----------------------------------------------------------------------

4 |1 |0 |1 |4

3 |2 |1 |3 |3

1 | 10 |3 |13 |3

5 |5 | 13 |18 |2

2 |1 | 18 |19 |1

-----------------------------------------------------------------------

Average Wait Time : 7

Average Turn Around Time : 10lab-a-26@laba26-Vostro-3669:~/Documents/sp

os/spos/c10/priority$
**PROGRAM 7:-

ROUND ROBIN SCHEDULING:-

//Round Robin Scheduling:

import [Link];

public class RoundR

public static void main(String args[])

Scanner s = new Scanner([Link]);

int wt[],bt[],rt[],num,quantum,total;

wt = new int[10];

bt = new int[10];

rt = new int[10];

[Link]("Enter number of processes: ");

num = [Link]();

[Link]("Enter burst time");

for(int i=0;i<num;i++)

[Link]("\nP["+(i+1)+"]: |\n\t");

bt[i] = [Link]();

rt[i] = bt[i];

wt[i]=0;

[Link]("\n\nEnter quantum:| ");

quantum = [Link]();

int rp = num;

int i=0;

int time=0;

[Link]("----------Round scheduling---------");
[Link]("\n------------");

wt[0]=0;

while(rp!=0)

if(rt[i]>quantum)

rt[i]=rt[i]-quantum;

[Link]("\n| P["+(i+1)+"] | ");

time+=quantum;

[Link](time);[Link](" |");

[Link]("\n-----------");

else

if(rt[i]<=quantum && rt[i]>0)

{time+=rt[i];

rt[i]=rt[i]-rt[i];

[Link]("\n| P["+(i+1)+"] | ");

rp--;

[Link](time);

[Link](" |");

[Link]("\n-------------");

//[Link]("\n---------------------------------");

i++;

if(i==num)

i=0;

}
**PROGRAM 8:-

SJF:-

import [Link];

class SJF

public static void main(String args[])

int burst_time[],process[],waiting_time[],tat[],i,j,n,total=0,pp,temp;

float wait_avg,TAT_avg;

Scanner s = new Scanner([Link]);

[Link]("Enter number of process: ");

n = [Link]();

process = new int[n];

burst_time = new int[n];

waiting_time = new int[n];

tat = new int[n];

[Link]("\nEnter Burst time:");

for(i=0;i<n;i++)

[Link]("\nProcess["+(i+1)+"]: ");

burst_time[i] = [Link]();;

process[i]=i+1; //Process Number

}[Link]("\n \t \t******* Shortest Job First Scheduling*");

//Sorting

for(i=0;i<n;i++)

pp=i;

for(j=i+1;j<n;j++)
{

if(burst_time[j]<burst_time[pp])

pp=j;

temp=burst_time[i];

burst_time[i]=burst_time[pp];

burst_time[pp]=temp;

temp=process[i];

process[i]=process[pp];

process[pp]=temp;

//First process has 0 waiting time

waiting_time[0]=0;

//calculate waiting time

for(i=1;i<n;i++)

waiting_time[i]=0;

for(j=0;j<i;j++)

waiting_time[i]+=burst_time[j];

total+=waiting_time[i];

//Calculating Average waiting time

wait_avg=(float)total/n;

total=0;

[Link]("----------------------------------------------------------");

[Link]("\nProcess\t| Burst Time \t|Waiting Time\t|Turnaround Time |");

[Link]("----------------------------------------------------------");

for(i=0;i<n;i++)

tat[i]=burst_time[i]+waiting_time[i];//Calculating Turnaround Time

total+=tat[i];
[Link]("\n p"+process[i]+" \t | \t "+burst_time[i]+"\t | \t "+waiting_time[i]+"\t |
\t"+tat[i]+" t | t ");

[Link]("----------------------------------------------------------");

//Calculation of Average Turnaround Time

TAT_avg=(float)total/n;

[Link]("\n\nAverage Waiting Time: "+wait_avg);

[Link]("\nAverage Turnaround Time: "+TAT_avg);

}
**PROGRAM 9:-

FIFO:-

import [Link].*;

public class FIFO {

public static void main(String[] args) throws IOException

BufferedReader br = new BufferedReader(new InputStreamReader([Link]));

int fr,rl,pt = 0, hit = 0, fault = 0;

int buffer[];

int reference[];

int mem_layout[][];

[Link]("\nENTER THE NUMBER OF FRAMES: ");

fr = [Link]([Link]());

[Link]("\nENTER THE LENGTH OF REFERENCE STRING: ");

rl = [Link]([Link]());

reference = new int[rl];

mem_layout = new int[rl][fr];

buffer = new int[fr];

for(int j = 0; j < fr; j++)

buffer[j] = -1;

[Link]("\nENTER THE REFERENCE STRING: ");

for(int i = 0; i < rl; i++)

reference[i] = [Link]([Link]());

}[Link]();

for(int i = 0; i < rl; i++)

int search = -1;

for(int j = 0; j < fr; j++)

if(buffer[j] == reference[i])

search = j;

hit++;

break;

if(search == -1)

buffer[pt] = reference[i];

fault++;

pt++;

if(pt == fr)

pt = 0;

for(int j = 0; j < fr; j++)

mem_layout[i][j] = buffer[j];

for(int i = 0; i < fr; i++)

for(int j = 0; j < rl; j++)

[Link]("%5d ",mem_layout[j][i]);

[Link]();

[Link]("\nTOTAL NUMBER OF HITS: " + hit);

[Link]("\nHIT RATIO IS: " + (float)((float)hit/rl));

[Link]("\nTOTAL NUMBER OF PAGE FAULT: " + fault);

}
**OUTPUT:-

lab-a-26@laba26-Vostro-3669:~/Documents/sp os/spos/Untitled Folder$ java FIFO

ENTER THE NUMBER OF FRAMES:

ENTER THE LENGTH OF REFERENCE STRING:

ENTER THE REFERENCE STRING:

9 9 9 9 9 6 6 6 6 6 6 7 7 7

-1 1 1 1 1 1 4 4 4 4 4 4 1 1

-1 -1 3 3 3 3 3 3 8 8 8 8 8 2
TOTAL NUMBER OF HITS: 5

HIT RATIO IS: 0.35714287

TOTAL NUMBER OF PAGE FAULT: 9

**PROGRAM 10:-

LRU:-
import [Link].*;

import [Link].*;

public class LRU {

public static void main(String[] args) throws IOException

BufferedReader br = new BufferedReader(new InputStreamReader([Link]));

int rl, fr, pointer = 0, hit = 0, fault = 0;

Boolean isFull = false;int buffer[];

ArrayList<Integer> stack = new ArrayList<Integer>();

int reference[];

int mem_layout[][];

[Link]("\nENTER THE NUMBER OF FRAMES: ");

fr = [Link]([Link]());

[Link]("\nENTER THE LENGTH OF REFERENCE STRING: ");

rl = [Link]([Link]());

reference = new int[rl];

mem_layout = new int[rl][fr];

buffer = new int[fr];

for(int j = 0; j < fr; j++)

buffer[j] = -1;

[Link]("\nENTER THE REFERENCE STRING: ");

for(int i = 0; i < rl; i++)

reference[i] = [Link]([Link]());

[Link]();

for(int i = 0; i < rl; i++)

{

if([Link](reference[i]))

[Link]([Link](reference[i]));

[Link](reference[i]);

int search = -1;

for(int j = 0; j < fr; j++)

if(buffer[j] == reference[i])

search = j;

hit++;

break;

if(search == -1)

if(isFull)

{int min_loc = rl;

for(int j = 0; j < fr; j++)

if([Link](buffer[j]))

int temp = [Link](buffer[j]);

if(temp < min_loc)

min_loc = temp;

pointer = j;

}
}

buffer[pointer] = reference[i];

fault++;

pointer++;

if(pointer == fr)

pointer = 0;

isFull = true;

for(int j = 0; j < fr; j++)

mem_layout[i][j] = buffer[j];

for(int i = 0; i < fr; i++)

for(int j = 0; j < rl; j++)

[Link]("%5d ",mem_layout[j][i]);

[Link]();

[Link]("\nTOTAL NUMBER OF HIT: " + hit);

[Link]("\nHIT RATIO: " + (float)((float)hit/rl));

[Link]("\nTOTAL NUMBER OF FAULTS: " + fault);

**OUTPUT:-

ENTER THE NUMBER OF FRAMES:

ENTER THE LENGTH OF REFERENCE STRING:

ENTER THE REFERENCE STRING:

111444555222666111

-1 2 2 2 2 2 2 6 6 6 3 3 3 3 3 3 3 3

-1 -1 3 3 3 1 1 1 1 1 1 7 7 7 2 2 2 6

TOTAL NUMBER OF HIT: 4

HIT RATIO: 0.22222222

TOTAL NUMBER OF FAULTS: 14

**PROGRAM 11:-

OPT:-
import [Link];

import [Link];

public class Opt {

public static void main(String[] args) throws IOException

{BufferedReader br = new BufferedReader(new InputStreamReader([Link]));

int rl, fr, pt = 0, hit = 0, fault = 0;

boolean isFull = false;

int buffer[];

int reference[];

int mem_layout[][];

[Link]("\nENTER THE NUMBER OF FRAMES: ");

fr = [Link]([Link]());

[Link]("\nENTER THE LENGTH OF REFERENCE STRING: ");

rl = [Link]([Link]());

reference = new int[rl];

mem_layout = new int[rl][fr];

buffer = new int[fr];

for(int j = 0; j < fr; j++)

buffer[j] = -1;

[Link]("\nENTER THE REFERENCE STRING: ");

for(int i = 0; i < rl; i++)

reference[i] = [Link]([Link]());

}
[Link]();

for(int i = 0; i < rl; i++)

int search = -1;

for(int j = 0; j < fr; j++)

if(buffer[j] == reference[i])

search = j;

hit++;

break;

if(search == -1)

if(isFull)

int index[] = new int[fr];

boolean index_flag[] = new boolean[fr];

for(int j = i + 1; j < rl; j++){

for(int k = 0; k < fr; k++)

if((reference[j] == buffer[k]) && (index_flag[k] == false))

index[k] = j;

index_flag[k] = true;

break;

int max = index[0];

pt = 0;

if(max == 0)

max = 200;

for(int j = 0; j < fr; j++)

if(index[j] == 0)

index[j] = 200;

if(index[j] > max)

max = index[j];

pt = j;

buffer[pt] = reference[i];

fault++;

if(!isFull)

pt++;

if(pt == fr)

pt = 0;

isFull = true;

for(int j = 0; j < fr; j++)

mem_layout[i][j] = buffer[j];

for(int i = 0; i < fr; i++)

{
for(int j = 0; j < rl; j++)[Link]("%3d ",mem_layout[j][i]);

[Link]();

[Link]("\nTOTAL NUMBER OF HIT: " + hit);

[Link]("\nHIT RATIO: " + (float)((float)hit/rl));

[Link]("\nTOTAL NUMBER OF PAGE FAULT: " + fault);

**OUTPUT:-

lab-a-26@laba26-Vostro-3669:~/Documents/sp os/spos/d14/opt$ java Opt

ENTER THE NUMBER OF FRAMES:

ENTER THE LENGTH OF REFERENCE STRING:

ENTER THE REFERENCE STRING:

3
4

1 1 1 1 1 1 1 1 1 1 3 3 3 3

-1 2 2 2 2 2 2 2 2 2 2 7 7 7

-1 -1 3 4 4 4 5 6 6 6 6 6 6 6

TOTAL NUMBER OF HIT: 6

HIT RATIO: 0.42857143

TOTAL NUMBER OF PAGE FAULT: 8

Common questions