Friday, March 22, 2013

Virtual Memory Manager

Language: Java

Purpose:

To build part of an operating system--specifically a Virtual Memory Manager.

Synopsis:
This was quite a project. Now looking back over it after I have finished, I see some of the answers to the questions I had that I thought weren't ever answered. However my instructor just assigned the project and didn't know much about the specifics.
Here is the exact book instructions for the project:
Designing a Virtual Memory Manager


package virtualMMan;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.ArrayList;
import java.util.HashMap;

public class VmmDriver {

    private final int TABLE_ENTRIES_OR_SIZE = 256;
    private final int PHYSICAL_MEMORY_SCALAR = 1;
    private int [] pageTable = new int [TABLE_ENTRIES_OR_SIZE];
    private int [] frameTable = new int [TABLE_ENTRIES_OR_SIZE]; 
    private HashMap victimFrameLocater = new HashMap<Integer,Integer>();  
    private ArrayList<Integer> framesFIFOQueue = new ArrayList<Integer>();
    private HashMap TLB = new HashMap<Integer,Integer>(17, 1);  
    private ArrayList<Integer> TLB_FIFOQueue = new ArrayList<Integer>();
    private byte [] physicalMemory = new byte [TABLE_ENTRIES_OR_SIZE*TABLE_ENTRIES_OR_SIZE];
    private int physicalMemoryPointer = 0;
    private int availableFrameCounter = 0;
    private int bitMask = 0x00FF;
    private double pageFaults, numOfAddresses, pageFaultRate, TLBHits = 0;

    public static void main(String[] args) {
        new VmmDriver().run();
    }        
    public void run(){

        //Input File with Virtual Addresses
        String filename = ("U:\\Project3\\src\\resources\\InputFile.txt");

        // the file representing the simulated  disk
        File backStorePath;
        RandomAccessFile backingStore = null;

        /*Create pageTable and 
         * initialize each index with -1.
         * This indicates that the entry in
         * the pageTable is invalid.*/
        for(int i = 0; i <(TABLE_ENTRIES_OR_SIZE-1); i++){
            pageTable[i] = -1; }


        /*Create frameTable and 
         * initialize each index starting at 0
         * and increasing by TABLE_ENTRIES_OR_SIZE
         * at each iteration*/
        int frameNum = 0;
        for(int i = 0; i < (TABLE_ENTRIES_OR_SIZE)-1; i++){
            frameNum = i*(TABLE_ENTRIES_OR_SIZE);
            frameTable[i] = frameNum;}

        BufferedReader br = null;  
        try
        {   

            File file = new File(filename);   
            FileReader fr = new FileReader(file);
            br = new BufferedReader(fr);
            String data;

            while((data = br.readLine()) != null)    
            {   
                /*Right-Shift virtual Address by 8 bits virtual 
                 * address space256).
                 * Use bitMask to "mask" Least Significant 0xFF bits*/
                int pageNumber = (Integer.parseInt(data) >> 8);
                int offset = (Integer.parseInt(data) & bitMask);

                int val = 0;
                int frameNumber = 0;

                //Page Fault handling
                if((!(TLB.containsKey(pageNumber)) && pageTable[pageNumber] == -1)){

                    try {
                        backStorePath = new 
                                File("U:\\Project3\\BACKING_STORE_A");
                        backingStore = new RandomAccessFile(backStorePath, "r");


                        // seek to byte position pageNumber * TABLE_ENTRIES_OR_SIZE
                        backingStore.seek((pageNumber)*(TABLE_ENTRIES_OR_SIZE));
                        backingStore.read(physicalMemory, physicalMemoryPointer, TABLE_ENTRIES_OR_SIZE);

                        val = physicalMemory[physicalMemoryPointer+offset];

                        physicalMemoryPointer +=TABLE_ENTRIES_OR_SIZE;

                        //Update PageTable
                        pageTable[pageNumber] = frameTable[availableFrameCounter];
                        frameNumber = pageTable[pageNumber];

                        availableFrameCounter++;

                        //Update TLB
                        if(TLB.size() <= 16){
                            addtoTLB(pageNumber,frameNumber);
                        }
                        else{
                            TLB.remove(TLB_FIFOQueue.get(0));

                        }

                        pageFaults++;
                        //Place value in physicalMemory
                        //physicalMemory[frameNumber] = val;
                        //Take Frame number "or" it with offset to get physical address
                        int physicalAddress = frameNumber  | offset;
                        System.out.println("Virtual address: " + data +" Physical address: " 
                                + physicalAddress + " Value: " + val);
                        //System.out.println("PageNumber: " + pageNumber
                        //+ " FrameNumber: " + frameNumber + " Offset: " + offset);
                        numOfAddresses++;
                    }
                    catch (IOException e) {
                        System.err.println ("Unable to start the disk");
                        //System.exit(1);
                    }
                    finally {
                        backingStore.close();
                    }

                }//if
                else{
                    if(TLB.containsKey(pageNumber)){

                        frameNumber = checkTLB (pageNumber);
                        int physicalAddress = frameNumber | offset;
                        System.out.println("Virtual address: " + data +" Physical address: " 
                                + physicalAddress + " Value: " +  physicalMemory[frameNumber+offset]);
                        TLBHits++;
                        numOfAddresses++;
                    }
                    else{                //Take pageNumber as index and get Frame number from Page table
                        frameNumber = pageTable[pageNumber];
                        //Take Frame number  "or" it with offset to get physical address
                        int physicalAddress = frameNumber | offset;
                        System.out.println("Virtual address: " + data +" Physical address: " 
                                + physicalAddress + " Value: " +  physicalMemory[frameNumber+offset]);
                        //System.out.println("PageNumber: " + pageNumber + 
                        //" FrameNumber: " + frameNumber + " Offset: " + offset);
                        numOfAddresses++;
                    }            
                }//else
            }//while
        }//try
        catch(ArrayIndexOutOfBoundsException e){
            e.printStackTrace();
        }
        catch(IOException e){
            System.out.println(e + "File: " + "\"" + filename + "\"" + " not Found.");
        }
        finally{
            try{
                if(br != null){
                    br.close();
                }
            }
            catch(IOException e){
                e.printStackTrace();
            }
        }
        printStats();
    }//run()
    public void addtoTLB (int pageNumber, int frameNumber ){     
        // Put value into Hash Map
        TLB.put(pageNumber, frameNumber);
        TLB_FIFOQueue.add(pageNumber);

    }//addtoTLB
    public int checkTLB (int pageNumber){
        return (int) TLB.get(pageNumber);

    }//checkTLB

    public void printStats(){
        pageFaultRate = pageFaults/numOfAddresses;
        System.out.println("Number of Translated Addresses = " + (int)numOfAddresses);
        System.out.println("Page Faults = " + (int)pageFaults);
        System.out.println("Page Fault Rate = " + pageFaultRate);
        System.out.println("TLB Hits = " + (int)TLBHits);
        System.out.println("TLB Hit Rate = " + (TLBHits/numOfAddresses));
    }

}

InputFile.txt
correct output for InputFile.txt
Generate a Backing Store file
Random Access File example

Note:
Our instructor told us that we did not have to do the modifications as stated at the end of the instructions. So this implementation only accounts for physical memory size and virtual memory size being the same. My grade was 93%. The reason is I compared my output to the correct output using the website http://text-compare.com/ and all of my values were correct yet some of my translated addresses were not correct. Not sure where I went wrong. Also my statistics were all correct as well. I spend about 30 hours on this project.
 

Thursday, March 21, 2013

Prolog Projects

Language: Prolog

Purpose:

Various book exercises from Modern Programming Languages: A Practical Introduction, by Adam Brooks Webber to be exposed to the logical programming language Prolog.
 
"Project 1" :
 
Exercises 1 - 6 from chapter 19
- Define a mother predicate so that mother(X,Y) says that X is the mother of Y.
- Define a father predicate so that father(X,Y) says that X is the father of Y.
- Define a sister predicate so that sister(X,Y) says that X is the sister of Y. Be careful, a person cannot be her own sister.
- Define a grandson predicate so that grandson(X,Y) says that X is the grandson of Y.
- Define the firstCousin predicate so that firstCousin(X,Y) says that X is the first cousin of Y. Be careful, a person cannot be his or her own cousin, nor can a brother or sister also be cousin.
- Define the descendant predicate so that descendant(X,Y) says that X is the descendant of Y.



parent(X,Y) :- mother(X,Y), female(X).
parent(X,Y) :- father(X,Y), male(X).

sibling(X,Y) :- parent(Z,X), parent(Z,Y), X \= Y.

sister(X,Y) :- sibling(X,Y), female(Y).

grandparent(C,D) :- parent(C,E), parent(E,D).

grandson(X,Y) :- grandparent(X,Y), male(X).

firstCousin(X,Y) :- parent(Z,X), parent(W,Y), sibling(Z,W).

descendant(X,Y) :- parent(X,Y).
descendant(X,Y) :- parent(Z,X), descendant(Z,Y).

female(sabrina).
female(audrey).
female(maria).
female(christine).

male(jose).
male(juan).
male(diego).
male(carlos).

mother(sabrina,audrey).
mother(sabrina,maria).
mother(audrey,juan).
mother(christine,diego).

father(jose,audrey).
father(jose,maria).
father(carlos,sabrina).
father(carlos,christine).


"Project 2" : An Adventure Game

Exercise 6 from chapter 20
Add the following features to the adventure game from this chapter:
- There is a gate between the fork in the path and the mountaintop. the gate is a separate location; that is, the player must move from at(you,fork) to at(you,gate) and then to at(you,mountaintop).
- To move forward through the gate the player must first unlock it with a key.
- The key is somewhere in the maze. The player must find it and explicitly pick it up.
- If the player tries to pass through the gate while still holding the key, he or she is killed by lightning. (To get the treasure, the player must first open the gate, then put down the key, and then pass through.)
Start from the code in this chapter ( which is also available on this book's web site, http://www.webber-labs.com/mpl.html). Part of your implementation should be a general way for the player to pick things up, carry them, and put them down. Design your solution so that I would be easy to add additional objects for the player to pick up and put down.
 
 

/*
  This is a little adventure game.  There are three
  entities: you, a treasure, and an ogre.  There are 
  six places: a valley, a path, a cliff, a fork, a maze, 
  a gate, and a mountaintop.  Your goal is to get the
  treasure without being killed first, but there will
  be challenges along the way.
*/

/*
  First, text descriptions of all places within the
  game.
*/
description(valley,
  'You are in a pleasant valley, with a trail ahead.').
description(path,
  'You are on a path, with ravines on both sides.').
description(cliff,
  'You are teetering on the edge of a cliff.').
description(fork,
  'You are at a fork in the path.').
description(maze(_),
  'You are in a maze of twisty trails, all alike.').
description(mountaintop,
  'You are on the mountaintop.').
description(gate,
  'You are right at a pearly white gate TO HEAVEN.').

/*
  report prints the description of your current
  location.  It is usually called directly as an
  automated routine call.
*/
report :-
  at(you,Loc),
  description(Loc,Y),
  write(Y), nl.

/*
  These connect predicates establish the map.
  The meaning of connect(X,Dir,Y) is that if you
  are at X and you move in direction Dir, you
  get to Y.  Recognized directions are
  forward, right, and left.
*/
connect(valley,forward,path).
connect(path,right,cliff).
connect(path,left,cliff).
connect(path,forward,fork).
connect(fork,left,maze(0)).
connect(fork,right,gate).
connect(gate,forward,mountaintop).
connect(maze(0),left,maze(1)).
connect(maze(1),right,maze(2)).
connect(maze(2),left,fork).
connect(maze(0),right,maze(3)).
connect(maze(_),_,maze(0)).

/*
  move(Dir) moves you in a direction Dir, then
  prints the description of your updated location.
  If you are at the gate and the gate is locked,
  then it alerts you, gives you a hint to unlock it,
  and reports your location.  If the active controller
  is the builder than this is overridden.
*/
move(Dir)  :-
  at(you,gate),
  connect(gate,Dir,Dest),
  gate(locked) ->
  write('The gate is locked.  You must have a key to open the gate.\n'),
  report ; at(you,gate), connect(gate,Dir,_), gate(unlocked), at(key,you), write('ZAAAAAP!  Poseidon\'s bolt got you in the bottom.  You\'re toast.  Oh, and you\'re dead.'), retract(at(you,gate)), assert(at(you,done)).
/*
  But if you are at the gate and the gate is unlocked,
  or you are moving between any other locations via
  a valid direction Dir, then travel to the new
  location and report it.
*/
move(Dir)  :-
  at(you,Loc),
  connect(Loc,Dir,Next),
  at(key,you) ->
  retract(at(key,you)),
  retract(at(you,Loc)),
  assert(at(you,Next)),
  assert(at(key,you)),
  report ; connect(Place,Dir,Step),
  retract(at(you,Place)),
  assert(at(you,Step)),
  report.
/*
  But if the movement was not a legal direction,
  print an error message and don't move.
*/
move(_)  :-
  write('That is not a legal move.\n'),
  report.

/*
  Shorthand for moves.
*/
forward :- move(forward).
left :- move(left).
right :- move(right).

/*
  Actions.
*/
take(key)  :- at(you,Loc), at(key,Loc), not(Loc = you), 
retract(at(key,Loc)), assert(at(key,you)), write('You have swallowed the key...I mean taken it.\n'), report.
take(key)  :- write('I\'m sorry, but you already have the key.  You can\'t take it twice bozo!\n'), report.

drop(key)  :- at(you,Loc), at(key,you), not(Loc = you) -> retract(at(key,you)), assert(at(key,Loc)), write('You have dropped the key.\n'), report ; write('You don\'t have a key in your 
inventory. Check inventory with \'inventory\'.\n'), report.


unlock(gate)  :- gate(unlocked) -> write('Unfortunately, a colossal swarm of Africanized bees migrating with Egyptian scarabs in the shape of Imotep\'s uuuuuugly face...scared you away from the pearly gate momentarily.  That or you aren\'t even at the gate, don\'t have the key in your inventory, or you were so distracted that you didn\'t notice the gate was already unlocked.\n'), report ; at(you,gate), at(key,you), retract(gate(locked)), assert(gate(unlocked)), write('You have unlocked the pearly gate with your creepy key.\n'), report.

lock(gate)  :- gate(locked) -> write('Unfortunately, a colossal swarm of Africanized bees 
migrating with Egyptian scarabs in the shape of Imotep\'s uuuuuugly face...scared you away from the pearly gate 
momentarily.  That or you aren\'t even at the gate, don\'t have the key in your inventory, or you were so 
distracted that you didn\'t notice the gate was already locked.\n'), report ; at(you,gate), at(key,you),  retract(gate(unlocked)), assert(gate(locked)), write('You have locked the pearly gate with your creepy key.\n'), report.

/*
  Shorthand for actions.
*/
takeKey  :- take(key).
dropKey  :- drop(key).
unlockGate  :- unlock(gate).
lockGate  :- lock(gate).
inventory  :-
  write('Your Inventory:\n'),
  at(key,you) -> write('Key\n'), report ; write('Empty.\n'), report.

/*
  If you and the ogre are at the same place, it 
  kills you.
*/
ogre :-
  at(ogre,Loc),
  at(you,Loc),
  write('An ogre sucks your brain out through\n'),
  write('your eye sockets, and you die.\n'),
  retract(at(you,Loc)),
  assert(at(you,done)).
/*
  But if you and the ogre are not in the same place,
  nothing happens.
*/
ogre.

key :-
  at(you,Loc),
  at(key,Loc),
  write('There is a key on the ground with a skull and crossbones on it along with a warning label.\n').
key.

/*
  If you and the treasure are at the same place, you
  win.
*/
treasure :-
  at(treasure,Loc),
  at(you,Loc),
  write('There is a treasure here.\n'),
  write('Congratulations, you win!\n'),
  retract(at(you,Loc)),
  assert(at(you,done)).
/*
  But if you and the treasure are not in the same
  place, nothing happens.
*/
treasure.

/*
  If you are at the cliff, you fall off and die.
*/
cliff :-
  at(you,cliff),
  write('You fall off and die.\n'),
  retract(at(you,cliff)),
  assert(at(you,done)).
/*
  But if you are not at the cliff nothing happens.
*/
cliff.

/*
  Main loop.  Stop if player won or lost.
*/
main :- 
  at(you,done),
  write('Thanks for playing.\n').
/*
  Main loop.  Not done, so get a move from the user
  and make it.  Then run all our special behaviors.  
  Then repeat.
*/
main :-
  key,
  write('\nNext move -- '),
  read(Move),
  call(Move),
  ogre,
  treasure,
  cliff,
  main.

/*
  This is the starting point for the game.  We
  assert the initial conditions, print an initial
  report, then start the main loop.
*/
go :-
  retractall(at(_,_)), % clean up from previous runs
  assert(gate(locked)),
  assert(at(key,fork)),
  assert(at(you,valley)),
  assert(at(ogre,maze(3))),
  assert(at(treasure,mountaintop)),
  write('This is an adventure game. \n'),
  write('Legal moves are left, right, or forward.\n'),
  write('End each move with a period.\n\n'),
  report,
  main.

Perl

Language: Perl

Purpose:

Various book exercises from Modern Programming Languages: A Practical Introduction, by Adam Brooks Webber to be exposed to the high level, general purpose, interpreted (not compiled), dynamic programming language Perl.

Note: I never got grades back for this project but I assume I did well since I passed the class with an A. The program has legal syntax and should run just fine.

 


  # 1.    Write a program that computes 
   #the circumference and area of a circle 
   #(use 3.141592654 as the value of pi). 
   #Prompt for input and read the radius from standard input.
   
      

   print "Circumference of a Circle";
   $pi = 3.141592654;
   print "Please enter a radius\n";
   $radius = <STDIN>;
   print "Circumference of a circle with the radius of $radius is:\n 2*$pi*$radius";
   

 # 2.    Write a program that prompts 
 #for a string and a number on separate 
 #lines. Print the string the number 
 #of times indicated by the input number.
   

   print "Please type a String.\n";
   $theString = <STDIN>;
   print "Now enter the number of times \"$theString\" is to be written.\n";
   $numOfTimes = <STDIN>;
   

   if($theString eq "\n"){
    print "Empty string.";
   }
   else{
    foreach(1..$numOfTimes){
        print "$theString";
    }
   }
   

   #3. Write a program that reads a list 
   #of numbers from standard input 
   #until an end-of-file (ctrl-z). 
   #Print the corresponding name 
   #for each number in the input 
   #list.
   

   @flinstones = qw / Fred Wilma Barney Betty Dino Pebbles BamBam /;
   

   $index = 0;
   while($line ne eof){
    $line = <STDIN>;
    print "\n";
    $numList[index] = $line;
    index++;
   }
   index = 0;
   $numListLength = @numList;
   

   foreach (1..$numListLength){
   

    if($numList[index] > numListLength){
        print "No such index: $numbList[index]\n";
    }
    else{
        print "$flinstones[$numbList[index]]\n";
    }
   index++;
   

   }
   

   #Project 2
   

   #1.    Write a subroutine called &total 
   #that returns the total of a list of 
   #numbers. The list is to be the input, 
   #the answer is to be returned.
   
   

   
    my @numbers = qw( 1 3 5 7 9 );
    my $numberTotal = &total(@numbers);
    print “The total of \@numbers is $numberTotal\n”;
    print “Enter some numbers on separate lines: ”;
    my newTotal = &total(<STDIN>);
    print “The total of \@numbers is $numberTotal\n”;