Description
In this homework, we are going to create a memory manager and its test program
on top of the software system of Homework #3. The generated executable is called
“memTest” and has the following usage:
memTest [-File
where the bold words indicate the command name or required entries, square
brackets “[ ]” indicate optional arguments, and angle brackets “< >” indicate
required arguments. Do not type the square or angle brackets.
This command-line memory manager test program should provide the following
functionalities:
1. Create a template class MemMgr to manage the memory as described
in the lecture notes. It should contain non-continuous memory blocks
(template class MemBlock) with recycling capability. The size of
each memory block can be determined in the constructor
MemBloc::MemBlock(size_t blockSize = 65536), or the function
“MemMgr::reset(size_t blockSize)”. The default size of the memory block is
65536 Bytes, and the parameter “blockSize” can re-define the “number of
Bytes” for the block.
2
2. The class of objects to be managed is class MemTestObj. It contains a
short, an int[10], a bool, a float[8], and a char, which are in total 76 Bytes.
However, in actual memory allocation, its size (by sizeof(MemTestObj))
will be promoted to 84 Bytes to get aligned with the size of int and float.
This class contains a static data member “static MemMgr* const _memMgr”
as its memory manager and its “new”, “new[]”, “delete”, and “delete[]”
operators are then overloaded to call the memory allocation/free functions
alloc(), allocArr(), free() and freeArr(), respectively, in class MemMgr.
3. The addresses of the allocated “MemTestObj” objects and arrays (by the
“MTNew” command) are recorded in the data members of the class
MemTest as “_objList” and “_arrList”, respectively (note: both are of the
same type (“vector
vector
“MTDelete”) of the objects/arrays are their positions in the vectors. They are
used to find the objects/arrays for the “delete/delete[]” related commands.
When an object/array is deleted, the corresponding position in the list is set
to ‘0’ (i.e. NULL). If another “delete/delete[]” command is trying to delete
the object/array with the same index, there will be no action and no error
message.
4. The class MemRecycleList is a private class only friend to class
MemMgr and is to recycle memory when the “delete” or “delete[]” operators
are called. There is a “MemRecycleList” array (“MemMgr::
_recycleList”) of size 256 to record the recycled “MemTestObj” for single
objects (i.e. delete), and arrays of size 1, 2, 3, …, to 255 (i.e. delete[]). If the
deleted “MemRecycleList” array has size ‘n’ which is greater than 255,
it will be recorded in a “MemRecycleList” that can be traced from the
“_recycleList[n % 256]” (See class slides and reference code for more
details).
5. A printing command to print out the contents in memory manager and class
MemTest.
2. Supported Commands
Other than the commands in Homework #3, we will support these new
commands:
MTReset: (memory test) reset memory manager
MTNew: (memory test) new objects
MTDelete: (memory test) delete objects
MTPrint: (memory test) print memory manager
info
USAGE: report the runtime and/or memory usage
3
Please refer to Homework #3 for the lexicographic notations. However, please
note that the “[ ]” optional parameters can appear anywhere in the command line,
while the “< >” mandatory parameters must follow the order as specified in the
command usage.
2.1 Command “MTReset”
Usage: MTReset [(size_t blockSize)]
Description: Reset the memory manager. The optional parameter “(size_t
blockSize)” specifies the number of Bytes for each memory block.
Please note that the parameter “blockSize” will be promoted to the
closest multiple of SIZE_T (by the MACRO “toSizeT()”) before
being passed to the MemMgr::reset() function. This command first
release all except for the first memory blocks back to system. Then it
checks whether the new blockSize is different from the size of the
first (active) memory block. If yes (different), reconstruct this only
block (i.e. the first block) to the new block size. Otherwise, or if the
parameter is not specified, the blockSize remains unchanged and the
memory of the first block will NOT be freed. The initial value of the
blockSize is 65536.
Example:
mtest> mtreset // reset memory manager using original value
mtest> mtr 123 // reset memory manager with blockSize = toSizeT(123) Bytes
Guarded command errors:
1. lexSingleOption() == false
2. If the specified “blockSize” is not a legal integer or is smaller than
toSizeT(sizeof(MemTestObj)).
2.2 Command “MTNew”
Usage: MTNew <(size_t numObjects)> [ -Array (size_t arraySize) ]
Description: Allocate memory test objects (class MemTestObj) and store in
“MemTest::_objectList” or “MemTest::_arrList”. The parameter
“(size_t numObjects)” specifies the number of memory test objects
or arrays to be allocated. If the optional parameter “-Array (size_t
arraySize)” is specified, allocate arrays of memory test objects with
“new MemTestObj[arraySize]”. Otherwise, allocate single objects by
“new MemTestObj”. Note that the allocated memory must be
promoted to multiple of sizeof(size_t). If the requested memory for
the object or array is greater than the block size of MemBlock, an
exception “bad_alloc()” should be thrown and this command should
catch it and return to the command prompt (i.e. Don’t crash the
program). If the requested memory is larger than the remaining space
of the current memory block, recycle the remaining memory space
and allocate a new memory block for the requested memory.
4
Examples:
mtest> mtnew 100 // new MemTestObj’s for 100 times
mtest> mtn 20 -a 5 // new MemTestObj[5] for 20 times
Guarded command errors:
1. lexOptions() == false
2. If the specified “numObjects” is not a legal integer or is not a positive
number.
3. If the parameter “numObjects” is not specified or is specified multiple
times.
4. If the specified “arraySize” is not a legal integer or is not a positive
number.
5. If the parameter “arraySize” is specified multiple times.
6. Any other syntax error with respect to the command usage.
7. Requested memory of the object or array is greater than the block size of
MemBlock (by catching “bad_alloc()”).
2.3 Command “MTDelete”
Usage: MTDelete < -Index (size_t objId) | -Random (size_t numRandId)>
[-Array]
Description: Delete memory test objects (class MemTestObj) and set the
corresponding entries in “MemTest::_objList” or
“MemTest::_arrList” to 0’s (NULLs). If the optional parameter “-
Array” is specified, delete the objects from “MemTest::_arrList”.
Otherwise, delete from “MemTest::_objList”. The parameter “-Index
(size_t objId)” explicitly specifies the object/array to be deleted in
the “_objList/_arrList” (objId as the array index). If the parameter “-
Random (size_t numRandId)” is specified, randomly generate
“numRandId” numbers of integers, without checking repeats, as
indices for objects/arrays in the “_objList/_arrList” array to be
deleted. The generated random indices must lie between 0 and
(_objList or _arrList array size – 1). If the object/array with respect
to the explicitly or randomly specified index has been deleted, just
ignore it and do not issue an error or re-generate the random
number.
Example:
mtest> mtdelete -i 3 // delete _objList[3]
mtest> mtd -r 5 // randomly generate 5 indices for deletion in _objList[]
mtest> mtd -i 8 -array // delete [] _arrList[8]
Guarded command errors:
1. lexOptions() == false
2. If both “-Index” and “-Random” are specified.
5
3. If none of “-Index” or “-Random” is specified.
4. If the parameter “-Index” is specified multiple times.
5. If the specified “objId” (for “-Index”) is not a legal integer, is smaller
than 0, or is greater than or equal to the size of “_objList” (if no “-Array”)
or “_arrList” (if with “-Array”). Print out error message like:
Size of object list (10) is <= 12!! or
Size of array list (10) is <= 12!!
// Assume size of object/array list is 10, and 12 is the specified parameter
6. If the parameter “-Random” is specified multiple times.
7. If the specified “numRandId” is not a legal integer, or is not a positive
number.
8. If the parameter “-Random (size_t numRandId)” is specified but the
“_objList” (if no “-Array”) or “_arrList” (if with “-Array”) is empty. In
such case, print out error message:
Size of object list is 0!! or
Size of array list is 0!!
9. Any other syntax error with respect to the command usage.
2.4 Command “MTPrint”
Usage: MTPrint
Description: Print out the contents of the memory manager and the class
MemTest. The output format is as shown in the following example --
=========================================
= Memory Manager =
=========================================
* Block size : 65536 Bytes
* Number of blocks : 13
* Free mem in last block: 7736
* Recycle list :
[ 0] = 1 [512] = 1 [1024] = 1 [555] = 1
[ 44] = 1 [556] = 5 [557] = 5
=========================================
= class MemTest =
=========================================
Object list ---
oooxooooo
Array list ---
ooooooooooooxx
Please note that the printout is aligned to left. The numbers “[ n]
= m” under “Recycle list” mean that the number of elements
in the recycle list of array size “n” is “m”. Do not show the entry if
the number in the recycle list is 0. The order of the printed recycle
6
lists follows the ascending order of the “array size % R_SIZE” (so, 0
à 512 à 1024 à 555 (% 256 = 43) à 44 à 556 (% 256 = 44) à
557 (% 256 = 45)). However, for the recycle lists of the same “array
size % R_SIZE”, print them out in the order as how they are linked
together (i.e. in the chronological order as they are constructed). The
strings under “Object list” and “Array list” indicate the
status of the objects and arrays, respectively. ‘o’ means the
object/array in the corresponding position is still valid, ‘x’ means it
has been deleted.
Examples:
mtest> mtprint
Guarded command errors:
1. If any parameter is specified.
2.5 Command “USAGE”
Usage: USAGE [-All | -Time | -Memory]
Description: report the runtime and/or memory usage.
Examples:
mtest> usage // print out both runtime and memory usage
mtest> usage -time // print out the runtime usage only
mtest> usage -m // print out the memory usage only
Guarded command errors:
1. If any of the parameters is repeatedly specified.
2. If two or more of the parameters “-All”, “-Time”, and “-Memory” are
specified.
Note: This command has been implemented in package “cmd” and pre-compiled
into “libcmd-{linux,mac}.a” in “lib”. You don’t need to work on it.
3. What you should do?
You are encouraged to follow the steps below for this homework assignment:
1. Read the specification carefully and make sure you understand the
requirements.
2. Think first how you are going to write the program, assuming you don’t have
the reference code.
7
3. Study the class slides and the provided source code (especially under
package “mem”).
4. The source codes for package “cmd” has been precompiled as “libcmdlinux18.a”, “libcmd-linux16.a”, and “libcmd-mac.a” for linux Ubuntu 18, 16,
and Mac platforms, respectively. Use “make linux18”, “make linux16” or
“make mac” in root directory to change the symbolic links in the directory
“lib” to suit your platform. Note that we will not test special keys in this
homework. However, if you have different keyboard mapping and would like
to use the special keys, please go ahead to copy your own “cmd” package and
modify the “REFPKGS” and “SRCPKGS” macros in Makefile accordingly.
We will restore it when testing your program. (i.e. Makefile is in
MustRemove.txt)
5. What you should do in this homework assignment are commented with
“TODO”’s. You should be able to complete this assignment by just finishing
these TODO’s. However, if you like to add new member functions, please go
ahead, but, do not add/remove any data member. Just make sure you
complete all the TODO’s and your program meets all the specifications.
6. Complete your coding and compile by “make”. Several test scripts are
provided under the directory “tests”. Please test your program thoroughly by
creating more test scripts.
7. You can turn on the debugging message by typing “make debug”. It will
define the compilation flag MEM_DEBUG and create an executable called
“memTest.debug”. Detailed memory allocation information will be printed
out. However, please note that the pointer addresses may be different in
different executions. Moreover, sometimes the codes may not be re-compiled
properly when switching between debug and normal modes. In that case,
type “make clean” before “make debug” or “make” to ensure the compilation
consistency.
8. Two reference programs are available under the “ref” directory. The
“memTest-linux18/linux16/mac” is the normal one without debugging
information, while “memTest-linux18/linux16/mac.debug” is with
debugging information. Use “make linux18”, “make linux16” or “make mac”
to switch platforms. Please note that the pointer addresses printed by
“memTest.debug” may be different from yours.
9. Please also watch out the announcement in the class website and FB.
Notes:
1. (IMPORTANT!!) Please use the global random number generator “rnGen”
(defined in “util.cpp” and “rnGen.h”) for the “-Random” option of the
“MTDelete” command. With the fixed random seed (0) (in util/util.cpp:15),
8
it should generate the same random number sequence every time and thus
make it easier for grading. Do not change the seed.
4. Grading
We will test your submitted program with various combinations/sequences of
commands to determine your grade. The results (i.e. outputs) will be compared with
our reference program. Minor difference due to printing alignment, spacing, error
message, etc may be tolerated. However, to assist TAs for easier grading work, please
try to match your output with ours.
Please also make sure your code is platform independent. Try to avoid platformdependent constants such as 4 or 8 for sizeof(void*). Use platform-independent macro
(e.g. #define SIZE_T sizeof(size_t)) instead.
Please also note that, to avoid ambiguity, for the command “MTDelete” with “-
random” option, we will use “-Index” to test the correctness, and “-Random” to test
the performance and robustness.
For the command parsing error message, since your command parsing logic may
be different from the reference program, it may not be easy for you to make the error
message the same as the reference program. Therefore, we will not compare the error
message when grading, but will check whether the error is properly detected.
To output the standard error (i.e. cerr) as well as standard output (i.e. cout) to a
file, please type: “yourExecutable >& yourLogFile”.
