I recently have been working on a project to simulate segmentation in memory. I wanted to create everything from scratch; not use pre-built data structures.
I create a memory object that allows for "segment" nodes and "hole" nodes.
A segment is: Any location in the memory object that is occupied by data.
A hole is: Any location in memory that is currently vacant and can be occupied by data.
Constraints:
- There can never be 2 adjacent holes in memory
- The head node must always point to the lowest address in memory.
Problems encountered:
- Correctly setting location for each node; sometimes nodes share a location, incorrectly.
- printLayout() is supposed to print memory nodes in order of ascending location, but does not.
Seeking:
- Analysis of implementation
- Possible efficiency improvements
- Any bugs encountered (with corrections, if possible)
- Possible memory leaks
Test files:
For testing "R" command
N
R 1000 5 100 80 10000
P
E
For testing "A" command
N
C 100
A 20 10
A 50 5
A 70 20
P
E
Code:
/********************************************************************************
* @author Evan Bechtol (ecb120030)
* <h1>Project: Memory Segmentation Simulation</h1>
* <p>Simulation of arrivals/departures/placements of segments in a
* segmented virtual memory, through the use of a linked-list. Implements a
* next-fit policy. Constraints: There can never be neighboring holes.</p>
* @since 2015-2-13
* @see http://www.programmingsimplified.com/java/source-code/java-program-to-bubble-sort
* @see http://web.cerritos.edu/jwilson/SitePages/java_language_resources/Java_printf_method_quick_reference.pdf
* @see http://www.algolist.net/Data_structures/Singly-linked_list/Removal
* @see http://crunchify.com/a-simple-singly-linked-list-implementation-in-java/
*
********************************************************************************/
import java.util.*;
import java.io.*;
/**
* Creates nodes to be used as data containers in the Memory class
*/
class Node {
boolean segment; // Equals false if this Node represents a hole
int location; // Position in memory of first byte
int size; // Size that node occupies
int timeToDepart; // Only valid when this Node represents a segment
Node next;
/**
* Constructor for generating a segment in memory
*
* @param locn location of node to be created
* @param sz size of node to be created
* @param endOfLife the timeOfDay node is to depart
* @param nxt specifies the next node to reference in the list
*/
Node (int locn, int sz, int endOfLife, Node nxt) {
segment = true;
location = locn;
size = sz;
timeToDepart = endOfLife;
next = nxt;
}
/**
* Constructor for a hole
*
* @param locn location of hole to be created
* @param sz size of hole to be created
* @param nxt reference to next node in the list
*/
Node (int locn, int sz, Node nxt) {
segment = false;
location = locn;
size = sz;
next = nxt;
}
} // End Node class
/**
* Creates a linked-list of ndoes to simulate virtual memory segments and holes
*/
class Memory {
private static int memorySize; // Defines the total size for the memory
Node head; // Refers to first node in memory
Node lastPlacement; // Refers to the last node that was placed, or hole if the last placed segment is removed
/**
* Constructor for Memory, generates a single hole Node of the given size
*
* @param size initial size of memory object
*/
Memory (int size) {
memorySize = size;
Node n = new Node (0, memorySize, null);
lastPlacement = head = n;
}
/**
* Attempts to place a request using the Next Fit Policy. Returns false if there
* isn't a hole big enough. Prints a confirmation if placed; return true
*
* @param size size of placement to be made
* @param timeOfDay the time at which the placement is being made
* @param lifeTime how long the segment is to remain in memory
* @param verbose specifies if extra placement information is to be given
* @return boolean: returns true if the placement was successful
*/
boolean place (int size, int timeOfDay, int lifeTime, boolean verbose) {
// If the list is empty, we can place as head node
if (isEmpty()) {
Node current = new Node (0, size, 0, null);
lastPlacement = head = current;
return true;
}
// There are nodes in the list
else {
Node current = lastPlacement; //We start searching for a hole at our lastPlacement
//While there are still nodes to reverse, keep looking
while (current != null) {
// If we are looking at a hole
if (!current.segment && current.timeToDepart <= timeOfDay) {
// If the hole is larger or equal to the size we need
if (current.size >= size) {
Node n = new Node (current.location, size, timeOfDay + lifeTime, current.next); //timeOfDay + lifeTime = timeToDepart
current.next = n;
current.size = current.size - size; // Adjust size of hole after placing segment
lastPlacement = current = n;
// If verbose == true, print the confirmation
if (verbose) {
System.out.println ("Segment at location: " + lastPlacement.location + "\twith size: " + lastPlacement.size + "\tdeparts at: " + lastPlacement.timeToDepart);
}
return true;
}
}
current = current.next;
} // End while
current = this.head; // To traverse from start of list
//While there are still nodes to reverse, keep looking
while (current != lastPlacement) {
// If we are looking at a hole
if (!current.segment && current.timeToDepart <= timeOfDay) {
// If the hole is larger or equal to the size we need
if (current.size >= size) {
Node n = new Node (current.location + size, size, timeOfDay + lifeTime, current.next); //timeOfDay + lifeTime = timeToDepart
current.next = n;
current.size = current.size - size;
lastPlacement = current = n;
// If verbose == true, print the confirmation
if (verbose) {
System.out.println ("Segment at location: " + lastPlacement.location + "\twith size: " + lastPlacement.size + "\tdeparts at: " + lastPlacement.timeToDepart);
}
return true;
}
}
current = current.next;
} // End while
}
// If we reach this point, segment could not be placed
return false;
}
/**
* Remove segments from the list, which are ready to depart.
* <p>Checks the following conditions:<ul><li>
* 1) Head is segment and ready to depart
* 2) Current is segment and ready to depart
* 3) Previous is hole, current is hole
* 4) We are combining the node containing last placement, with another node</li></ul></p>
*
* @param timeOfDay time at which the removal is being done
*/
void removeSegmentsDueToDepart (int timeOfDay) {
// Case 1: Head is segment and ready to depart
if ((head.segment == true) && (head.timeToDepart <= timeOfDay)) {
head.segment = false; // Allow node to become a hole
//System.out.println ("Case 1.");
}
// Create reference to head node
Node previous = head;
// Begin iterating on list from 2nd node
while (previous.next != null) {
//Use this as our current position
Node current = previous.next;
// Case 2: Current is segment and ready to depart
if ((current.segment == true) && (current.timeToDepart <= timeOfDay)) {
//Combine
current.segment = false;
//System.out.println ("Case 2.");
}
// Case 3: previous is hole, current is hole
if ((previous.segment == false) && (current.segment == false)) {
// Case 4: We are combining the node containing last placement, with another node
if (current == lastPlacement) {
// Set last placement to the node to be combined to
lastPlacement = previous;
//System.out.println ("Case 4.");
}
// Combine
previous.size += current.size;
previous.next = current.next;
}
// Else we adjust our position.
else {
previous = current;
}
} // End while
}
/**
* Print a 3-column tab-separated list of all segments in Memory.
* Displayed in ascending order of location.
*/
void printLayout() {
Node current = head;
int numNodes = 0; // Number of nodes in the array
while (current != null) {
numNodes++;
current = current.next;
}
//System.out.println (counter);
Node [] nodeArray = new Node [numNodes];
int y = 0; // Used as increment in while-loop
current = head;
// Loop to print out all segments present
while (current != null) {
// Assign nodeArray a node for each index
nodeArray[y] = current;
y++;
current = current.next;
}// End while
// Sort the array
nodeArray = sort (nodeArray, numNodes);
// Print the sorted array of nodes
for (int i = 0; i < numNodes; i++) {
System.out.println (nodeArray[i].location + "\t" + nodeArray[i].size + "\t" + nodeArray[i].timeToDepart);
}
}
/**
* Use a bubble sort to sort the node array by location in ascending order
*
* @param node Node array that contains the nodes to be sorted in ascending order
* @param length How many nodes there are to be sorted
* @return Node[] Returns sorted Node array.
*/
Node [] sort (Node [] node, int length)
{
Node tempNode;
for (int i = 0; i < ( length - 1 ); i++) {
for (int j = 0; j < length - i - 1; j++) {
// Sort the array by location in ascending order
if (node[j].location > node[j + 1].location)
{
tempNode = node[j];
node[j] = node[j + 1];
node[j + 1] = tempNode;
}
}
}
return node;
}
/**
* Determines the empty or occupied state of the list
*
* @return Returns true if list is empty
* @return Returns false if nodes are in the list
*/
public boolean isEmpty () {
if (head == null) {
return true;
}
return false;
}
} // End Memory class
/**
* Class to test Memory and Node classes. Accepts file-redirection from commandline by using the
* scanner with System.in, can also accept file input by using scanner with new File
*/
public class EVBEP1 {
/**
* Used to test implementation of Memory and Node objects. Processes commands received through
* either the commandline or file-input.
*
* @param args Standard parameter for parsing commands received
* @throws FileNotFoundException If file is unable to be located, exception is thrown
*/
public static void main(String[] args) throws FileNotFoundException {
// Used for accepting command line arguments
//Scanner sc = new Scanner (System.in);
// Used for testing purposes
Scanner sc = new Scanner(new File("p115sd5.txt")); //Place file name here for different tests
String line = "";
boolean done = false;
Memory memory = new Memory(0); // Memory object
int timeOfDay = 0; // Simulated wall clock, begins with value zero
int placements = 0; // Number of placements completed, begins with value zero
long totalSpaceTime = 0; // Sum of placed segmentSize(i) x segmentLifetime(i)
float meanOccupancy = 0;
// Loop runs as long as done != true
while (!done) {
line = sc.nextLine(); // Store data gathered from file into String
String [] tokens = line.split(" "); // Split the string using space as delimiter
// Switch for processing commands received
switch (tokens[0]) {
// Print name followed by newline
case "N": {
System.out.println("Evan Clay Bechtol");
break;
}
// Create a memory object of size s
case "C": {
memory = new Memory(Integer.parseInt(tokens[1])); // Create a new Memory object
break;
}
// End of data file, print newline and exit
case "E": {
System.out.println();
done = true; // Break the loop, end the program
break;
}
// Add segment of size 'u' and lifetime 'v' and print confirmation record
case "A": {
int size = Integer.parseInt(tokens[1]);
int lifeTime = Integer.parseInt(tokens[2]);
timeOfDay++;
memory.removeSegmentsDueToDepart(timeOfDay);
// Boolean controls whether confirmation is printed.
while (!memory.place(size, timeOfDay, lifeTime, true)) {
timeOfDay++;
memory.removeSegmentsDueToDepart(timeOfDay);
} // End while
placements++;
// Print confirmation message
System.out.printf("Segment of size\t%4d", size);
System.out.printf(" placed at time\t%4d", timeOfDay);
System.out.printf(" at location\t%4d", memory.lastPlacement.location);
System.out.printf(" departs at\t%4d", memory.lastPlacement.timeToDepart);
break;
}
// Print the current segments in the list
case "P": {
System.out.println ();
memory.printLayout();
//System.out.println ("End at time: " + timeOfDay);
break;
}
case "R": {
int size = Integer.parseInt(tokens[1]); // Size
memory = new Memory(size);
int minSegSize = Integer.parseInt(tokens[2]); // Minimum seg. size
int maxSegSize = Integer.parseInt(tokens[3]); // Maximum seg. size
int maxLifeTime = Integer.parseInt(tokens[4]); // Maximum lifetime of segs.
int numSegs = Integer.parseInt(tokens[5]); // Number of segs. to simulate
timeOfDay = 0;
placements = 0;
Random ran = new Random (); // "Random" number generator
while (placements < numSegs) {
timeOfDay++;
memory.removeSegmentsDueToDepart(timeOfDay);
int newSegSize = minSegSize + ran.nextInt(maxSegSize - minSegSize + 1);
int newSegLifetime = 1 + ran.nextInt(maxLifeTime);
totalSpaceTime += newSegSize * newSegLifetime;
while (!memory.place(newSegSize, timeOfDay, newSegLifetime, false)) {
timeOfDay++;
memory.removeSegmentsDueToDepart(timeOfDay);
} // End while
placements++;
} // End while
// Print final summary of execution
meanOccupancy = totalSpaceTime / (timeOfDay);
System.out.printf ("Number of placements made = %6d\n", placements);
System.out.printf ("Mean occupancy of memory = %8.2f\n", meanOccupancy);
}
} // End switch
} // End while
sc.close();
} // End main
} // End EVBEP1 class
