Memory Segmentation Simulation

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)
* Project: Memory Segmentation Simulation
* 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.
* @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/
*
***

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 0) {
// Create a new hole with the remaining space.
Node remainingHole = new Node (current.location+size,
remainingSpace, current.next);
current.next = remainingHole;
lastPlacement = remainingHol

StackExchange Code Review Q#80470, answer score: 2