Lab 10: Freedom

Due by midnight tonight

The goal of this lab is to complete a special doubly-linked list class called FreeList that mimics the operation of a free list used by malloc() to manage heap memory in the C programming language.

Free list operation

A free list is a curious kind of linked list. It starts with a single node that contains all the free space. The figure below shows a brand new linked list with 1024 bytes of free memory. Note that the following figures are not to scale, though larger blocks are sometimes used to represent larger amounts of memory.

When the user tries to allocate a chunk of memory, the free list will search for the first unused block with enough space to hold the allocated chunk. If the unused block is exactly the size of the chunk requested, it will simply mark it used. Otherwise, the space inside the unused block will shrink to be the size of the requested chunk, mark itself used, and add a new unused block after it, containing the remainder of the unused memory. In the figure below, 100 bytes have been requested out of 1024 bytes of unused space.

The following figure shows the same free list after 50 and 200 bytes have been allocated, in that order.

The next figure shows the free list after the 50-byte chunk starting at address 100 has been freed.

The figure below shows the free list after the 100-byte chunk starting at address 0 has also been freed. Note that the two unused blocks of 50 and 100 bytes, respectively, are merged together to form an unused block of 150 bytes.

The following figure shows the free list after a 300-byte chunk is allocated. Because 300 bytes is too small to fit in the initial unused block of 150 bytes, the chunk must be allocated from the next unused block, which initially contained 674 free bytes. After allocation of 300 bytes, 374 bytes remain in that unused block.

The final figure shows the free list after a 150-byte chunk is allocated. Because 150 bytes fits perfectly in the initial unused block, that block is simply changed from unused to used without creating any new blocks.

Specification

Create a project called Lab10 and create a package in your project called allocation. Download the following two files and add them to the allocation package.

• FreeList.java
• MallocSimulator.java

Running the MallocSimulator class allows the user to simulate something similar to the free list that the malloc() function uses to manage memory. The MallocSimulator has been provided for you in its entirety. Your job is to implement three methods inside the FreeList class so that this simulation works correctly.

Constructor

Inside the constructor, you should create a new Node and point head and tail at it. You should set the space inside this Node to size and set its used member to false. Finally, set its address to 0.

The allocate() method

The allocate() method is the most challenging method in this lab. It's supposed to find the first available unused block large enough to hold bytes and divide it into used and unused Node objects (if the block is larger than bytes) or simply mark it as used (if the block is exactly the same size as bytes).

First, iterate through the list, starting at head, looking for a Node that's unused whose space is at least as big as bytes.

If you get to the end of the list without finding such a Node, return -1, indicating failure to find space. Otherwise, let temp be the Node with enough space in it.

If temp is larger than bytes, create a new Node. Set its space to however much is leftover after removing bytes from temp. Set its address to be bytes more than temp's address. Set temp's space to bytes. Make the new Node's next point at the Node after temp. Make the new Node's previous point at temp. If there's a Node after temp, make its previous point at the new Node. Make temp's next point at the new Node. If tail pointed at temp, point it at the new Node.

Whether or not temp was larger than it needed to be, mark it as used, and then return its address.

The print() method

The print() method prints out the contents of the list. You should loop through each Node in the list, starting at head.

Print out the address from each Node, a tab, and the space taken up by each Node, followed by the text "bytes". When printing out these numerical values, use System.out.format() to specify that each should take up 8 spaces of width. Then, if the Node is used, print "Used". Otherwise, print "Unused". Refer to the sample output below for formatting.

Sample Output

The sample output below shows exactly the sequence of allocations and frees illustrated in the figures above. At the very end of the program, the list is printed so that you can see the output formatting.

1. Allocate memory
2. Free memory
3. Print free list
4. Quit
Enter choice: 1

Bytes to allocate: 100
Allocation succeeded! Address: 0

1. Allocate memory
2. Free memory
3. Print free list
4. Quit
Enter choice: 1

Bytes to allocate: 50
Allocation succeeded! Address: 100

1. Allocate memory
2. Free memory
3. Print free list
4. Quit
Enter choice: 1

Bytes to allocate: 200
Allocation succeeded! Address: 150

1. Allocate memory
2. Free memory
3. Print free list
4. Quit
Enter choice: 2

Address to free: 100
Free succeeded!

1. Allocate memory
2. Free memory
3. Print free list
4. Quit
Enter choice: 2

Address to free: 0
Free succeeded!

1. Allocate memory
2. Free memory
3. Print free list
4. Quit
Enter choice: 1

Bytes to allocate: 300
Allocation succeeded! Address: 350

1. Allocate memory
2. Free memory
3. Print free list
4. Quit
Enter choice: 1

Bytes to allocate: 150
Allocation succeeded! Address: 0

1. Allocate memory
2. Free memory
3. Print free list
4. Quit
Enter choice: 3

Address:        0	     150 bytes Used
Address:      150	     200 bytes Used
Address:      350	     300 bytes Used
Address:      650	     374 bytes Unused

1. Allocate memory
2. Free memory
3. Print free list
4. Quit
Enter choice: 4

Turn In

Turn in your code by uploading FreeList.java from the Lab10\src\allocation folder inside your workspace folder to Blackboard. Do not upload the entire project. I only want the FreeList.java

All work must be done individually. Never look at someone else's code. Please refer to the course policies if you have any questions about academic integrity. If you have trouble with the assignment, I am always available for assistance.