Programming (Write Code)
Budget: $10 – $30 USD
You MUST write your own code for the four primary functions (myalloc, myrealloc, myfree, mysbrk)
Your initial heap size will be 1000 words, and you may expand your heap to 100,000 words maximum
As an example, your heap would start at word 0. If your first call is myalloc(5), then you would start the header at word 1, your payload at word 2, and your footer at word 4 to meet alignment requirements. This is because the payload would have to start at an address divisible by 8, and take up two words, 5 bytes for the payload and 3 bytes of padding. So, your header would start at word 1 (address 4), the payload would start at word 2 (address 8), and your footer would start at word 4 (address 16). This would allow your next header to start at word 5 (address 20) and the next payload to start at word 6 (address 24).
|header | payload |footer |
|--------|--------|--------|--------|--------|--------|
0 1 2 3 4 5 6
Primary Functions
You will have four primary functions in your assignment, which MUST be named as follows:
myalloc(size):
takes an integer value indicating the number of bytes to allocate for the payload of the block
returns a "pointer" to the starting address of the payload of the allocated block
The "pointer" above can take any form you like, depending on the data structure you use to represent your heap
myrealloc(pointer, size):
takes a pointer to an allocated block and an integer value to resize the block to
returns a "pointer" to the new block
copies the payload from the old block to the new block
frees the old block
a call to myrealloc with a size of zero is equivalent to a call to myfree
myfree(pointer):
you must use a LIFO policy for explicit free lists
prev pointer should be first and next pointer should be second (opposite from slides)
frees the block pointed to by the input parameter "pointer"
returns nothing
only works if "pointer" represents a previously allocated or reallocated block that has not yet been freed
otherwise, does not change the heap
coalesce after freeing, coalesce lower before coalescing higher addresses, and update headers last
mysbrk(size):
grows or shrinks the size of the heap by a number of words specified by the input parameter "size"
you may call this whenever you need to in the course of a simulation, as you need to grow the heap only as much as needed for the allocation, do not extend a free block at end of previous space, use a totally new block
this call will return an error and halt the simulation if your heap would need to grow past the maximum size of 100,000 words
User Options:
The user must be able to specify the following (either in a GUI or on the command line) for each run of your simulator:
Input text file
Implicit or Explicit free list
First-fit or Best-fit allocation
Your initial heap size will be 1000 words, and you may expand your heap to 100,000 words maximum
As an example, your heap would start at word 0. If your first call is myalloc(5), then you would start the header at word 1, your payload at word 2, and your footer at word 4 to meet alignment requirements. This is because the payload would have to start at an address divisible by 8, and take up two words, 5 bytes for the payload and 3 bytes of padding. So, your header would start at word 1 (address 4), the payload would start at word 2 (address 8), and your footer would start at word 4 (address 16). This would allow your next header to start at word 5 (address 20) and the next payload to start at word 6 (address 24).
|header | payload |footer |
|--------|--------|--------|--------|--------|--------|
0 1 2 3 4 5 6
Primary Functions
You will have four primary functions in your assignment, which MUST be named as follows:
myalloc(size):
takes an integer value indicating the number of bytes to allocate for the payload of the block
returns a "pointer" to the starting address of the payload of the allocated block
The "pointer" above can take any form you like, depending on the data structure you use to represent your heap
myrealloc(pointer, size):
takes a pointer to an allocated block and an integer value to resize the block to
returns a "pointer" to the new block
copies the payload from the old block to the new block
frees the old block
a call to myrealloc with a size of zero is equivalent to a call to myfree
myfree(pointer):
you must use a LIFO policy for explicit free lists
prev pointer should be first and next pointer should be second (opposite from slides)
frees the block pointed to by the input parameter "pointer"
returns nothing
only works if "pointer" represents a previously allocated or reallocated block that has not yet been freed
otherwise, does not change the heap
coalesce after freeing, coalesce lower before coalescing higher addresses, and update headers last
mysbrk(size):
grows or shrinks the size of the heap by a number of words specified by the input parameter "size"
you may call this whenever you need to in the course of a simulation, as you need to grow the heap only as much as needed for the allocation, do not extend a free block at end of previous space, use a totally new block
this call will return an error and halt the simulation if your heap would need to grow past the maximum size of 100,000 words
User Options:
The user must be able to specify the following (either in a GUI or on the command line) for each run of your simulator:
Input text file
Implicit or Explicit free list
First-fit or Best-fit allocation