Memory Segmentation Simulation

Question

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

• Phrancis: Welcome to Code Review! This looks like a pretty complex project I'm sure our Java experts will appreciate, I hope you get some good reviews!
• Evan Bechtol: @Phrancis Thank you for the welcome! I certainly hope that I can get some valuable feedback, I want to get this project to 100% and am definitely in need of some fresh eyes to look at it.
• Evan Bechtol: @phrancis would you mind bumping this to a friend/someone who would know about Java in general?
• Phrancis: I pinged a few people to have a look. Just be patient, code reviews take a lot longer to write than your average Stack Overflow answer :)
• barq: What version of Java are you using?

Answer 1

What I Liked

I liked that you had good comments, especially at the beginning of each function. I was able to read through your code very easily. There were a few comments that were distracting (e.g. // End while), but I would always prefer to err on the side of more comments rather than less.

In your question, I liked how you explained the difference between a segment and a hole, and how you explained the constraints. I think you should copy this information into your code as comments.

Bugs

I ran your program and spotted the following bug. If you use this input file:

C 1000
A 100 10
A 50 10
A 50 10
P
E

You get this output:

0 800 0
0 100 11
50 50 13
50 50 12

As you can see, all 3 segments created overlap, and they also overlap with the hole.

The culprit is this code here:

 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;
 }

Here, you allocate the memory segment from the start of the hole, current.location. But you don't adjust the hole correctly. For example, with if you have a hole at 0..999 and you place a size 100 block, you should end up with a segment at 0..99 and a hole at 100..999. But instead, you end up with a hole at 0..899. What you are missing is this line:

 current.location += size;

Of course, once you do this, you need to adjust your code because the segment you create needs to now come before the old segment in the list. Or you could do it the other way and allocate from the end of the hole.

Duplicated Code

Regarding that piece of code from above, I noticed two other things:

1) You have two nearly identical copies of the same code for placing the segment. You should write a common function and call that function from the two places.

2) Those pieces of code are nearly identical, but they aren't. The difference is:

Node n = new Node (current.location, size, timeOfDay + lifeTime, current.next); //timeOfDay + lifeTime = timeToDepart
// Versus:
Node n = new Node (current.location + size, size, timeOfDay + lifeTime, current.next); //timeOfDay + lifeTime = timeToDepart

I suspect that you added the + size to the second one because it made some test case with 2 segments work correctly. But in actuality, that second version is wrong once you fix the earlier bug I mentioned.

Confusing Code

In the comments for your Node structure, it says this:

int timeToDepart; // Only valid when this Node represents a segment

But in the placement code, it does this:

if (!current.segment && current.timeToDepart <= timeOfDay) {

According to the comment, timeToDepart doesn't have a meaning for a hole. So the if statement shouldn't be checking timeToDepart since it is looking for a hole.

Another thing that confused me was this comment:

 //While there are still nodes to reverse, keep looking

I don't understand what you meant by "reverse".

Cleaning Up

I noticed that if you completely fill a hole with a segment, you end up with a zero length hole. That doesn't seem too useful, and if you print out the memory table, it looks a little confusing to have a zero length hole in the list. I suggest checking for that case and not leaving zero length holes lying around.

Also, it seems to me that the node list is always maintained in a sorted order. Therefore, I don't see the need to have a sort() function.

Fixed Version

Here is how I changed your code to fix everything mentioned above. You may choose to do things differently, since the way I added the new node may not be as intuitive as you would like. I actually create a new hole node and convert the existing hole into a segment.

Also notice that in a few places I use an early return from the function to reduce the indentation level of the rest of the code. That makes things slightly easier to read.

boolean tryplace(Node current, int size, int timeOfDay, int lifeTime,
 boolean verbose) {
 // If we are not looking at a hole, or the hole is too small, abort.
 if (current.segment || current.size < size)
 return false;
 int remainingSpace = current.size - size;
 // Convert the current hole into a segment.
 current.size = size;
 current.segment = true;
 current.timeToDepart = timeOfDay + lifeTime;
 // If there is any remaining space, create a new node representing
 // the leftover hole.
 if (remainingSpace > 0) {
 // Create a new hole with the remaining space.
 Node remainingHole = new Node (current.location+size,
 remainingSpace, current.next);
 current.next = remainingHole;
 lastPlacement = remainingHole;
 } else {
 lastPlacement = current;
 }
 // If verbose == true, print the confirmation
 if (verbose) {
 System.out.println ("Segment at location: " + current.location +
 "\twith size: " + current.size +
 "\tdeparts at: " + current.timeToDepart);
 }
 return true;
}
// ...
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;
 }
 // We start searching for a hole at our lastPlacement
 Node current = lastPlacement;
 while (current != null) {
 if (tryplace(current, size, timeOfDay, lifeTime, verbose))
 return true;
 current = current.next;
 }
 current = this.head; // Wraparound to start of list
 while (current != lastPlacement) {
 if (tryplace(current, size, timeOfDay, lifeTime, verbose))
 return true;
 current = current.next;
 }
 // If we reach this point, segment could not be placed
 return false;
}

• Evan Bechtol: Thank you very much for the detailed answer! I truly appreciate your time and effort in my problem, especially after it has been sitting for so long unanswered! I'll take a look at your implementation shortly.