You can write a C, C++, or Java program that demonstrates the processing of memo
ID: 3858276 • Letter: Y
Question
You can write a C, C++, or Java program that demonstrates the processing of memory allocation and deallocation requests when the buddy algorithm is being used. The input to your program will give the amount of memory available, the size of the smallest possible allocation, and a sequence of allocation and deallocation requests. Details are provided later.
In the buddy system each block of memory used to satisfy an allocation request has a size that is exactly a power of 2 storage units (for example, 512, 1024, 16384)1. The memory management software (that is, your solution to this assignment!) will keep linked lists that identify the unused blocks of memory, which will have sizes that are a power of 2. The number of such lists depends on the amount of memory available to the system, and the size of the smallest allowable allocation. For example, suppose we have 1024 bytes in the system, and the smallest allowable allocation is for 128 bytes. We will need four lists of unused blocks: one for 128-byte blocks, one for 256-byte blocks, one for 512-byte blocks, and one for 1024-byte blocks. Obviously some of these may be empty lists. Each list entry will need to identify its size and its location (that is, its lowest or starting address). The size could be implied from the list on which the block appears (all blocks on the 256-byte block list should obviously be 256 bytes long), but you will likely find it better to explicitly record the size of the block in its list entry.
The simulated memory used in this problem will begin at location 0. Note that there is no real memory being allocated in this problem, except, of course, for linked list entries and any other data structures used in your solution. For the example in the previous paragraph, where we have
1024 bytes of memory with a smallest block size of 128 bytes, all block addresses will be less than 1024. In fact, we can easily see that the only block addresses permitted are 0, 128, 256, 384,
512, 640, 768, and 896.
Memory Management Requests
There are two memory management request permitted in this assignment: allocation of a specified amount of memory, and deallocation of a pevious allocation. How your program is to handle each of these operations is described, in detail, in the following paragraphs.
Allocation of R bytes2 is performed by first rounding R up to the next power of 2, if it wasn’t already a power of 2; assume this value is called K. The appropriate free list (that is, the free list for blocks of size K) is then checked to determine if a free block is available. If it is, then
1 Although most modern machines are byte addressable, many earlier machines could only address larger units of storage, like 16, 24, 36, or 60 bits. We will assume bytes as the units of allocation to avoid further use of stilted terms like “units of storage.”
2 You may assume that R will never be larger than the size of the memory.
that free block with the smallest address3 is removed from the list and used to satisfy the request; the allocation is complete.
If the free list for blocks of size K is empty, then the free list for blocks with the next larger size (2K) is examined. And if it doesn’t have any entries, the program keeps looking in the free lists for larger and larger blocks (4K, 8K, …), until either a free block is found or the free lists for all the larger block sizes have been examined.
If no free block of size K or a larger is found, the allocation request isn’t discarded. Instead, it isdeferreduntil sometime later when a suitable free block does become available4. Deferring a request is done by saving the request at the end of a linked list of such deferred requests. An example of a deferred request will be given later.
Of course, if a larger free block is found, then it is removed from its list and split into two smaller blocks (each half the size of the original), and these are placed on the appropriate free list. One of these blocks (we always choose the one with the smaller address5) is then used to satisfy the request, either directly (if it is of size K), or indirectly, by splitting it again to yield two even smaller blocks which are handled in the same manner.
Deallocation is almost the inverse of allocation. When a block B is deallocated, its buddy’s address is first determined. If block B has address A and size K, we compute A / K, always yielding an integer result. If this value is even (that is, if the low-order bit in the binary representation of A / K is 0, or (A / K) mod 2 is 0), then the buddy’s address is A + K; otherwise the buddy’s address is A – K. The free list for blocks with size K is examined for a free block with the buddy’s address. If that block is not found, then an entry for B is added to the free list for size K blocks. Otherwise, B’s buddy is removed from the free list for size K blocks and joined with block B to form a larger free block B' . This block has size 2K and an address that is the smaller of B and its buddy. We then continue as if we were trying to deallocate this larger block B'. The process is guaranteed to terminate.
Once the deallocation is complete, we then need to determine if any of the deferred allocation requests can now be satisfied. This is done by considering each of the deferred requests, one at a time, in the same order the requests were submitted (that is, the deferred request queue is a FIFO queue). Each allocation request that can now be performed is removed from the deferred list, and is allocated the needed storage).
An Example
An illustration with real numbers will aid your understanding of these actions. Specifically, let’s again assume we have a region with 1024 bytes to use in satisfying allocation requests, and that the smallest region we’ll use to satisfy a request is 128 bytes.
Assume we have the following allocation and deallocation requests to process, in the order given. Each allocation request is given a unique positive integer ID. Deallocation of the allocated memory will use the same ID.
3 This is done to guarantee that all correct solutions will yield the same output.
4 In a real system, the process making such a request might be blocked until sufficient storage becomes available to satisfy the request.
5 As before, this guarantees all correct solutions will yield the same output.
ID
Action
1
Allocate 200 bytes
2
Allocate 399 bytes
3
Allocate 500 bytes
4
Allocate 100 bytes
5
Allocate 63 bytes
6
Allocate 75 bytes
4
Deallocate
5
Deallocate
Initially all our free lists are empty except for the one for blocks of size 1024 bytes, which has a single entry for the region starting at address 0.
The first request (ID 1, allocate 200 bytes, which is rounded up to 256 bytes) causes us to look first in the free list for 256 bytes (which is empty), then in the free list for 512 bytes (which is also empty), and finally the free list for 1024 bytes. This list has one entry for the free block at address 0. That entry is removed from the 1024-byte free list. Since it is larger than needed, it is split into two entries of size 512 (one at address 0 and one at address 512). The entry for address
512 is placed on the free list for size 512, and the one at address 0 is split again to give two free blocks of size 256, one at address 0 and one at address 256. The block at address 256 is added to the free list for size 256, and the one with address 0 is used to satisfy the current request.
The second request (ID 2, allocate 399 bytes, rounded up to 512) is easily satisfied, since there is a single block of size 512 available. After that request is satisfied, a single free block, of size 256, at address 256, remains.
The third request (ID 3, allocate 500 bytes, rounded up to 512) cannot be satisfied because there are no blocks on the free lists for 512 bytes and 1024 bytes. The request is therefore placed on the deferred list, and will be considered again after a deallocation.
The fourth request (ID 4, allocate 100 bytes, rounded up to 128) can be satisfied after the free block of 256 bytes at address 256 is split into two 128 byte blocks. The 128 byte block at address
256 is used to satisfy the request, and the other 128 byte block at address 384, is placed on the free list for 128 byte blocks.
The fifth request (ID 5, allocate 63 bytes, rounded up to 128, the minimum) is satisfied using the last free block in the system, at address 384.
The sixth request (ID 6, allocate 75 bytes, rounded up to 128) cannot be satisfied immediately, so it is deferred, and placed after the first deferred request on the deferred list.
The seventh request (ID 4, deallocate) indicates that the 128 byte block at address 256 is to be freed. Since its buddy (at address 384) is not free, the free block is placed on the 128 byte free list. Since there are deferred requests, we consider each of them in order. The first such deferred request (for 512 bytes) still cannot be satisfied, so it remains on the list. The second deferred request (for 128 bytes) can be satisfied using the single free block at address 256. We now have no free blocks, and one deferred request remains.
The eighth and final request (ID 5, deallocate) frees the 128 byte block at address 384. Its buddy, at address 256, is not free, so we’re done after placing the free block on the free list for 128 byte entries.
The example given here and the additional example given later have all of the allocation requests first, followed by deallocation requests. This will not necessarily be the case in real data. You are certainly encouraged to use these to test your program, but you should also prepare additional test cases. Developing suitable test data is an essential part of any development activity.
Input Data
The input data will be read from the standard input.
The first line of the input will contain two unsigned integers. The first of these, MSIZE, will indicate the total amount of memory available for allocation. The second integer, ASIZE, will indicate the size of the smallest block that can be used to satisfy a request. Each of these will be a power of 2, and ASIZE MSIZE < 232 .
Each remaining line will contain an allocation or deallocation request. Each request will begin with a positive integer ID, some whitespace (that is, blanks and/or tabs), and a '+' or '-'. '+' is used for an allocation request, and '–' is used for a deallocation request. An allocation request will have the positive integer size of the allocation request specified after the '+' (separated by additional whitespace).
The end of the input is indicated by the end of file.
You may assume that all input is syntactically and semantically correct.
Details and Limits
You will need one free list for each power of 2 between (and including) ASIZE and MSIZE, a list to keep track of deferred allocation requests, and some way of recording information (ID, address, and size) for allocations that have been made but have not yet been deallocated.
No two allocation requests will ever have the same ID, but each deallocation request must contain the IDof a previously successful allocation. The input data used to test your solution will never attempt to deallocate an allocation that is currently deferred, but your solution should detect this case (if it should exist), since that would indicate either an error in the input data or, more troubling, an error in your solution! Although the IDs used in the earlier example were sequential, this need not be the case in actual test data.
After reading each request, your program should display a line that indicates the request that is being processed; they should be similar to one of these:
Request ID 52: allocate 73 bytes. Request ID 35: deallocate.
Each line for an allocation request should be immediately followed by another line containing
Success; addr = 0x00001000.
or
Request deferred.
as appropriate. Note that the address in the “Success” message should be the address at which the region allocated for the request begins. Also make certain that you always satisfy each allocation request with the free region that has the smallest address. (It will likely be appropriate to maintain the free lists in ascending address order to make this requirement easier to satsify.)
After each deallocation request you should display a line that says
Success.
Additionally, for each deferred request that can be successfully accommodated as a result of a deallocation, display a line that says
Deferred request with ID 59 allocated; addr = 0x00001800.
Of course, the IDs and address values in each of these are just an examples. But do note that the addresses in the output should be displayed as 8-digit hexadecimal numbers preceded by 0x (that is, they should be C/C++/Java-style hexadecimal constants).
Keep in mind that the addresses used in the program for free blocks and allocations are not real memory addresses – they are simulated memory addresses. Your program should not be doing dynamic memory allocation for blocks of the sizes used in the progam.
Sample Input and Output
You may also supply the option –v on the command line to produce considerable additional
output. After each input request has been completed, the program will display the status of all requests, the contents of the free lists, and the list of deferred requests. For deallocation, the calculation of buddy addresses and the joining of blocks on various free lists will be displayed.
The first sample is the input used the earlier discussion
Here’s what it looks like:
1024 128
1 + 200
2 + 399
3 + 500
4 + 100
5 + 63
6 + 75
4 -
5 –
The expected output for this input is as follows:
Request ID 1: allocate 200 bytes.
Success; addr = 0x00000000. Request ID 2: allocate 399 bytes. Success; addr = 0x00000200.
Request ID 3: allocate 500 bytes.
Request deferred.
Request ID 4: allocate 100 bytes.
Success; addr = 0x00000100. Request ID 5: allocate 63 bytes.
Success; addr = 0x00000180. Request ID 6: allocate 75 bytes.
Request deferred. Request ID 4: deallocate.
Success.
Deferred request 6 allocated; addr = 0x00000100
Request ID 5: deallocate.
Success.
The second sample is somewhat more ambitious, and is found in the file prog3.input2 on
Loki. Here’s what it contains:
4096 256
1 + 500
2 + 250
3 + 100
4 + 1025
5 + 390
6 + 200
7 + 1
8 + 1200
9 + 200
10 + 2000
11 + 2000
4 -
3 -
2 -
1 -
9 -
7 -
5 -
6 -
8 -
10 -
11 -
And here is the expected output:
Request ID 1: allocate 500 bytes.
Success; addr = 0x00000000. Request ID 2: allocate 250 bytes. Success; addr = 0x00000200. Request ID 3: allocate 100 bytes. Success; addr = 0x00000300.
Request ID 4: allocate 1025 bytes.
Success; addr = 0x00000800. Request ID 5: allocate 390 bytes. Success; addr = 0x00000400. Request ID 6: allocate 200 bytes. Success; addr = 0x00000600.
Request ID 7: allocate 1 byte.
Success; addr = 0x00000700. Request ID 8: allocate 1200 bytes.
Request deferred.
Request ID 9: allocate 200 bytes.
Request deferred.
Request ID 10: allocate 2000 bytes.
Request deferred.
Request ID 11: allocate 2000 bytes.
Request deferred. Request ID 4: deallocate.
Success.
Deferred request 8 allocated; addr = 0x00000800
Request ID 3: deallocate.
Success.
Deferred request 9 allocated; addr = 0x00000300
Request ID 2: deallocate.
Success.
Request ID 1: deallocate.
Success.
Request ID 9: deallocate.
Success.
Request ID 7: deallocate.
Success.
Request ID 5: deallocate.
Success.
Request ID 6: deallocate.
Success.
Deferred request 10 allocated; addr = 0x00000000
Request ID 8: deallocate.
Success.
Deferred request 11 allocated; addr = 0x00000800
Request ID 10: deallocate.
Success.
Request ID 11: deallocate.
Success.
Three additional test cases, appropriately named, are also provided. The expected output for each test case can be obtained using the instructor’s solution. Additional test cases may be provided in the future. If so, they’ll be announced on the class web page, and will be given names similar to the samples already provided.
Requirements
You must write (and test) a C, C++, or Java program that performs the tasks associated with the buddy system memory management system to perform the requests specifined in the input format described earlier. You should ideally have a single file of source code.
ID
Action
1
Allocate 200 bytes
2
Allocate 399 bytes
3
Allocate 500 bytes
4
Allocate 100 bytes
5
Allocate 63 bytes
6
Allocate 75 bytes
4
Deallocate
5
Deallocate
Explanation / Answer
In the program, mainly there are three packages
1.Main
-BuddyMemoryAlgorithm
2.Memory
-Memory
-MemoryManager
-MemoryRequest
And Test Cases
Test/Memory
-MemoryManagerTest
-MemoryRequestTest
-MemoryTest
-----------------------------------------------------------------------
BuddyMemoryAlgorithm.java
-------------------------------------
package main;
/*
* Main entry point for the program. Performs input operations
* for determining the next memory allocation/deallocation. Prints
* out success messages for both operations and deferred messages for
* allocations.
*
* Since the memory and minimum block sizes are guaranteed to be powers
* of two, efficient bitwise operations are used instead of dividing
* and multiplying.
*/
import memory.Memory;
import memory.MemoryManager;
import memory.MemoryRequest;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;
public class BuddyMemoryAlgorithm {
public static void main(String[] args) throws IOException {
Scanner in = null;
FileReader fin = null;
/* If there is one argument, it is the file to be read from. */
if (args.length == 0) {
in = new Scanner(System.in);
} else if (args.length == 1) {
fin = new FileReader(args[0]);
in = new Scanner(fin);
} else {
/* The program is being used incorrectly. Notify the user. */
System.err.println("Usage: java main.BuddyMemoryAlgorithm [filename");
System.exit(0);
}
/* Create a memory manager with the memory size and minimum block size. */
MemoryManager manager = new MemoryManager(in.nextInt(), in.nextInt());
/* Continue processing requests until the end of input. */
while (in.hasNext()) {
/* Get the allocation ID. */
int requestId = in.nextInt();
/* Get the operation type - allocation or deallocation. */
String requestType = in.next();
/* See if allocating or deallocating. */
if (requestType.equals("+")) {
/* See how much space is required. */
int size = in.nextInt();
System.out.printf("Request ID %d: allocate %d bytes. ", requestId, size);
/* Create a formal request to send to the memory manager. */
MemoryRequest request = new MemoryRequest(requestId, size);
/* Attempt to allocate the request. */
Memory allocated = manager.allocate(request);
if (allocated == null) {
/* The allocation returned null, could not be fulfilled. */
System.out.println(" Request deferred.");
} else {
/* The allocation was successful. Notify the user */
/* of the address of the newly allocated memory. */
System.out.printf(" Success; addr = 0x%08x. ", allocated.getAddress());
}
} else if (requestType.equals("-")) {
/* Deallocate the memory block identified by the request ID. */
/* This will always be successful, so print as such. */
System.out.printf("Request ID %d: deallocate. Success. ", requestId);
manager.deallocate(requestId);
} else {
/* There was a problem reading the request type, notify the user. */
System.err.printf("ERROR: got request ID (%d) but unknown request type (%s)",
requestId, requestType);
System.exit(1);
}
}
if (fin != null) {
fin.close();
}
}
}
-----------------------------------------------------------------------
Memory.java
-------------------------------------
package memory;
/*
* A memory chunk in the allocation scheme. The size is represented as a
* power of two for efficiency. The memory can be split, provided that it
* is not allocated and it's size is greater than the minimum block size.
* Merging must only be performed with it's buddy, which is identified by
* calling getBuddyAddress() and checking that the sizes are equal.
*/
public class Memory {
/* The minimum block size available, stored as log2 of the actual size. */
public static int minBlockSize;
/* Which request ID is holding this memory block. */
protected int allocatedBy;
/* Address of this memory block. */
private int address = 0;
/* Size, stored as log2 of the actual size. */
private int size;
/* Create the initial, unallocated memory block. */
public Memory(int size) {
this.size = size;
allocatedBy = 0;
}
/* Create a new memory block with the given size and address. */
public Memory(int address, int size) {
this(size);
this.address = address;
}
/* Take in an integer value, and convert it to a power of two. */
/* Will return the next highest power of two if not an exact match. */
public static int convertToPowerOfTwo(int num) {
int power = 0;
while((1 << power) < num) {
power++;
}
return power;
}
/* Creates and returns a new memory region split from this one. */
/* Returns null if the memory cannot be split because it is */
/* allocated or is already at the minimum size.The size of this */
/* memory and the new memory are half the original size of the */
/* current memory block. */
public Memory split() {
if (allocatedBy != 0 || size == minBlockSize) {
return null;
}
/* Size is stored as power of two, decrement to halve size. */
size--;
return new Memory(address + (1 << size), size);
}
/* Takes a memory block and merges it with itself, setting the */
/* appropriate address. Returns itself, the grown memory block. */
public Memory merge(Memory memory) {
/* Set the new address appropriately and double the size. */
address = (isEvenBuddy() ? address : memory.getAddress());
/* Size is stored as power of two, increment to double size. */
size++;
/* This memory block has been adjusted to be */
/* the new merged memory block. Return itself. */
return this;
}
/* Get the address of this memory block's buddy. */
public int getBuddyAddress() {
return (isEvenBuddy() ? address + (1 << size) : address - (1 << size));
}
/* See if this memory chuck is an even or odd chunk. */
private boolean isEvenBuddy() {
return (((address >> size) & 1) == 0);
}
public int getAddress() {
return address;
}
public int getSize() {
return size;
}
}
-----------------------------------------------------------------------
MemoryManager.java
-------------------------------------
package memory;
/*
* Main buddy memory management algorithm implementation that takes memory
* requests for allocation, and allocation IDs for deallocation.
* Has a list of allocated memory chunks, and a list of lists of unallocated
* memory chunks for fast allocation.
*/
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class MemoryManager {
/* List of lists of memory. Element zero is the list of memory blocks */
/* of the minimum size, element one is list of next bigger blocks. */
private List<List<Memory>> unallocated;
/* A list of the already allocated memory locations. */
private List<Memory> allocated;
/* A queue of waiting deferred requests. */
private Queue<MemoryRequest> deferredRequests;
/* Create the memory manager and initialize all of the */
/* lists and queues required. Add one full-sized chunk */
/* of memory to the unallocated memory list of lists. */
public MemoryManager(int memorySize, int minBlockSize) {
int memorySizeLog2 = Memory.convertToPowerOfTwo(memorySize);
int minBlockSizeLog2 = Memory.convertToPowerOfTwo(minBlockSize);
unallocated = new ArrayList<List<Memory>>();
for (int i = 0; i < memorySizeLog2 - minBlockSizeLog2 + 1; ++i) {
unallocated.add(i, new LinkedList<Memory>());
}
allocated = new LinkedList<Memory>();
deferredRequests = new LinkedList<MemoryRequest>();
/* Set the minimum size for a memory block. */
Memory.minBlockSize = minBlockSizeLog2;
/* Create the starting memory with the given */
/* size and the minimum block size. */
addToUnallocated(new Memory(memorySizeLog2));
}
/* Allocate memory given a request. Returns the memory */
/* block allocated if successful, null if unsuccessful. */
/* Unsuccessful allocations will cause the memory */
/* request to be stored in the deferred requests queue. */
public Memory allocate(MemoryRequest request) {
/* Attempt to find a large enough memory location. */
Memory allocatedMemory = findAvailableMemory(request.getSize());
/* Check if a free memory block of enough size was found. */
if (allocatedMemory != null) {
allocatedMemory = splitToSize(allocatedMemory, request.getSize());
allocatedMemory.allocatedBy = request.getId();
allocated.add(allocatedMemory);
return allocatedMemory;
} else {
/* Request could not be filled right now. Put it on hold. */
deferredRequests.add(request);
return null;
}
}
/* Find an available memory location at least the size passed */
/* (in log2). The memory chunk returned may be larger. */
/* The memory block is removed from the unused list. */
protected Memory findAvailableMemory(int desiredSize) {
Memory availableMemory = null;
/* See which list of memory elements to begin looking at. */
int smallestPossible = desiredSize - Memory.minBlockSize;
for (int i = smallestPossible; i < unallocated.size(); ++i) {
/* List of memory chunks of size i. */
List<Memory> iSizeMemories = unallocated.get(i);
if (iSizeMemories.size() > 0) {
availableMemory = iSizeMemories.remove(0);
break;
}
}
return availableMemory;
}
/* Halve the size of the memory block until it is the desired size. */
/* Adds the split off memory blocks back to the unallocated lists. */
protected Memory splitToSize(Memory foundMemory, int desiredSize) {
while (foundMemory.getSize() > desiredSize) {
Memory newMemory = foundMemory.split();
addToUnallocated(newMemory);
}
return foundMemory;
}
/* Takes in a request number, finds it in the allocated */
/* memory list and deallocates that memory block. Returns */
/* the resulting memory block after merging if successful. */
public Memory deallocate(int requestNumber) {
Memory merged = null;
/* Search through the allocated memory to find */
/* the memory block to be released. */
for (Memory allocatedMemory : allocated) {
if (allocatedMemory.allocatedBy == requestNumber) {
/* Remove memory block from allocated status. */
allocated.remove(allocatedMemory);
allocatedMemory.allocatedBy = 0;
/* Merge it with all of it's buddies. */
merged = merge(allocatedMemory);
/* Add the merged block to the unallocated list. */
addToUnallocated(merged);
/* See if any deferred requests can now be fulfilled. */
attemptAllocationOfDeferred();
break;
}
}
return merged;
}
/* Takes in a memory block and attempts to merge it with */
/* the other memory blocks in the unallocated lists. */
/* Returns the original memory if could not be merged, or */
/* returns a merged memory block. */
private Memory merge(Memory memory) {
/* Obtain the list of memory blocks of the same size. */
int sameSizeIndex = memory.getSize() - Memory.minBlockSize;
List<Memory> sameSizeMemories = unallocated.get(sameSizeIndex);
int buddyAddress = memory.getBuddyAddress();
/* Search through all other memory cells of the */
/* same size to see if they can be merged. */
for (Memory mergeCandidate : sameSizeMemories) {
if (mergeCandidate.getAddress() == buddyAddress) {
/* Remove the merge candidate from the unallocated list. */
sameSizeMemories.remove(mergeCandidate);
/* Recursively attempt to merge again. */
return merge(memory.merge(mergeCandidate));
}
}
/* Return the memory block that has been merged if possible. */
return memory;
}
/* Go through all deferred requests and attempt to allocate them. */
private void attemptAllocationOfDeferred() {
int numRequests = deferredRequests.size();
for (int i = 0; i < numRequests; ++i) {
/* Attempt to allocate given the request. */
/* If not possible, it is added back to */
/* the deferred requests list. */
Memory allocated = allocate(deferredRequests.poll());
if (allocated != null) {
System.out.printf(" Deferred request %d allocated; addr = 0x%08x. ",
allocated.allocatedBy, allocated.getAddress());
}
}
}
/* Takes a memory location and adds it to the proper */
/* list in the unallocated list of lists. */
/* Makes sure that the list is still sorted to make */
/* solution guaranteed to be the same as the example.*/
private void addToUnallocated(Memory memory) {
List<Memory> nSizeUnallocated = unallocated.get(memory.getSize() - Memory.minBlockSize);
/* Look through the array to find where it should be inserted */
/* in order to keep the unallocated array sorted by address. */
int i;
for (i = 0; i < nSizeUnallocated.size(); ++i) {
if (nSizeUnallocated.get(i).getAddress() > memory.getAddress()) {
break;
}
}
/* Add the memory at the found size, or at 0 if the */
/* list was empty to begin with. */
nSizeUnallocated.add(i, memory);
}
}
-----------------------------------------------------------------------
MemoryRequest.java
-------------------------------------
package memory;
/*
* Formal request for memory allocation. The memory request is created
* with an actual size needed, which is then rounded up to the nearest
* power of two. If this next power of two is even smaller than the
* minimum memory block size, the request is set for the minimum block
* size.
*/
public class MemoryRequest {
/* A unique ID for this request. */
private int id;
/* Size, stored as log2 of the actual size. */
private int size;
/* Create a new resource request given an id and a requested size. */
public MemoryRequest(int id, int size) {
this.id = id;
/* Convert the request to the next largest power */
/* of two that is >= the minimum memory block size. */
int actualPower = Memory.convertToPowerOfTwo(size);
this.size = (actualPower >= Memory.minBlockSize) ? actualPower : Memory.minBlockSize;
}
public int getId() {
return id;
}
public int getSize() {
return size;
}
}
----------------------------------------
TestCases
-----------------------------------------------------------------------
MemoryManagerTest.java
-------------------------------------
package memory;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
import static org.testng.Assert.*;
public class MemoryManagerTest {
private static final int MEMORY_SIZE = 16;
private static final int MIN_BLOCK_SIZE = 4;
private MemoryManager manager;
@BeforeMethod
public void setup() {
manager = new MemoryManager(MEMORY_SIZE, MIN_BLOCK_SIZE);
}
@Test
public void findAvailableMemory() {
assertEquals(manager.findAvailableMemory(2).getSize(), 4, "Should have found the block of size 16.");
}
@Test
public void splitToSize() {
Memory testMemory = new Memory(Memory.convertToPowerOfTwo(MEMORY_SIZE));
assertEquals(manager.splitToSize(testMemory, 2).getSize(), 2);
}
@Test
public void allocate() {
MemoryRequest request;
Memory allocatedMemory;
for (int i = 0; i < MEMORY_SIZE / MIN_BLOCK_SIZE; ++i) {
request = new MemoryRequest(i, MIN_BLOCK_SIZE);
allocatedMemory = manager.allocate(request);
assertNotNull(allocatedMemory);
assertEquals(allocatedMemory.getAddress(), i * MIN_BLOCK_SIZE);
assertEquals(allocatedMemory.allocatedBy, i);
}
request = new MemoryRequest(MEMORY_SIZE / MIN_BLOCK_SIZE, MIN_BLOCK_SIZE);
allocatedMemory = manager.allocate(request);
assertNull(allocatedMemory);
}
@Test
public void allocateDeallocate() {
MemoryRequest request = new MemoryRequest(1, MEMORY_SIZE);
Memory memory = manager.allocate(request);
assertEquals(memory.allocatedBy, 1);
assertEquals(memory.getSize(), Memory.convertToPowerOfTwo(MEMORY_SIZE));
memory = manager.deallocate(1);
assertEquals(memory.allocatedBy, 0);
assertEquals(memory.getSize(), Memory.convertToPowerOfTwo(MEMORY_SIZE));
}
@Test
public void deallocate() {
MemoryRequest request = new MemoryRequest(1, MIN_BLOCK_SIZE);
manager.allocate(request);
Memory releasedMemory = manager.deallocate(1);
assertEquals(releasedMemory.allocatedBy, 0);
assertEquals(releasedMemory.getAddress(), 0);
assertEquals(releasedMemory.getSize(), Memory.convertToPowerOfTwo(MEMORY_SIZE));
}
@Test
public void deallocateMany() {
MemoryRequest request = new MemoryRequest(1, MIN_BLOCK_SIZE);
manager.allocate(request);
request = new MemoryRequest(2, MIN_BLOCK_SIZE);
manager.allocate(request);
Memory releasedMemory = manager.deallocate(1);
assertEquals(releasedMemory.allocatedBy, 0);
assertEquals(releasedMemory.getAddress(), 0);
assertEquals(releasedMemory.getSize(), Memory.convertToPowerOfTwo(MIN_BLOCK_SIZE));
releasedMemory = manager.deallocate(2);
assertEquals(releasedMemory.allocatedBy, 0);
assertEquals(releasedMemory.getAddress(), 0);
assertEquals(releasedMemory.getSize(), Memory.convertToPowerOfTwo(MEMORY_SIZE));
}
@Test
public void allocateDeferred() {
MemoryRequest request = new MemoryRequest(1, MEMORY_SIZE);
assertNotNull(manager.allocate(request));
request = new MemoryRequest(2, MEMORY_SIZE / 2);
assertNull(manager.allocate(request));
request = new MemoryRequest(3, MEMORY_SIZE / 2);
assertNull(manager.allocate(request));
Memory releasedThanAllocated = manager.deallocate(1);
assertEquals(releasedThanAllocated.allocatedBy, 2);
assertEquals(releasedThanAllocated.getSize(), Memory.convertToPowerOfTwo(MEMORY_SIZE / 2));
request = new MemoryRequest(4, MEMORY_SIZE / 4);
assertNull(manager.allocate(request));
releasedThanAllocated = manager.deallocate(2);
assertEquals(releasedThanAllocated.allocatedBy, 4);
assertEquals(releasedThanAllocated.getSize(), Memory.convertToPowerOfTwo(MEMORY_SIZE / 4));
}
}
-----------------------------------------------------------------------
MemoryRequestTest.java
-------------------------------------
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
import static org.testng.Assert.assertEquals;
public class MemoryRequestTest {
@BeforeMethod
public void setup() {
Memory.minBlockSize = Memory.convertToPowerOfTwo(8);
}
@DataProvider(name = "testBlockSizes")
public Object[][] createTestCases() {
return new Object[][]{{1, 3}, {4, 3}, {8, 3}, {14, 4}, {25, 5}};
}
@Test(dataProvider = "createTestCases")
public void testGetSize(int requestSize, int outcomeSize) {
MemoryRequest request = new MemoryRequest(1, requestSize);
assertEquals(request.getSize(), outcomeSize);
}
}
-----------------------------------------------------------------------
MemoryTest.java
-------------------------------------
package memory;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
import static org.testng.Assert.*;
public class MemoryTest {
private static final int ORIGINAL_SIZE = Memory.convertToPowerOfTwo(8);
private Memory memory;
@BeforeMethod
public void setup() {
memory = new Memory(ORIGINAL_SIZE);
Memory.minBlockSize = Memory.convertToPowerOfTwo(2);
}
@Test
public void convertToPowerOfTwo() {
assertEquals(Memory.convertToPowerOfTwo(1), 0);
assertEquals(Memory.convertToPowerOfTwo(2), 1);
assertEquals(Memory.convertToPowerOfTwo(64), 6);
assertEquals(Memory.convertToPowerOfTwo(60), 6);
assertEquals(Memory.convertToPowerOfTwo(100), 7);
}
@Test
public void split() {
Memory newMemory = memory.split();
assertEquals(memory.getSize(), ORIGINAL_SIZE - 1);
assertEquals(newMemory.getSize(), ORIGINAL_SIZE - 1);
assertEquals(memory.getAddress(), 0);
assertEquals(newMemory.getAddress(), (1 << (ORIGINAL_SIZE - 1)));
}
@Test
public void split_minSize() {
assertNotNull(memory.split());
assertNotNull(memory.split());
assertNull(memory.split());
}
@Test
public void merge_memoryFirst() {
Memory newMemory = new Memory((1 << ORIGINAL_SIZE), ORIGINAL_SIZE);
Memory merged = memory.merge(newMemory);
assertMergeSuccess(merged);
}
@Test
public void merge_newMemoryFirst() {
Memory newMemory = new Memory((1 << ORIGINAL_SIZE), ORIGINAL_SIZE);
Memory merged = newMemory.merge(memory);
assertMergeSuccess(merged);
}
private void assertMergeSuccess(Memory merged) {
assertEquals(merged.getSize(), ORIGINAL_SIZE + 1);
assertEquals(merged.getAddress(), 0);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.