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

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