$35
Program 7 – Memory Manager
CECS 325-01 System Programming with C++
Program 7 – Memory Manager (revised 11-27-22)
Background:
Computer languages often require a way to dynamically allocate memory. This means that memory is acquired while the program is running. This is in contrast to static memory allocation such as declaring a variable, an instance of an object or an array of some data type.
For example, these statements in C++ require no dynamic memory allocation:
int x; // creates one integer storage space at compile time
char array[20]; // creates 20 char storage spaces at compile time
Compare the above to these statements which create memory locations dynamically – after the program starts running
Int *dptr = new int[3]; // creates 3 integers, returned an integer pointer back to dptr
Card *myCard = new Card(‘A’, ‘H’); // creates a Card – the Ace of Hearts, returns a Card pointer to myCard.
Notice that the operator “new” is smart enough to return an integer pointer if an integer or group of integers is requested and return a Card pointer if a Card object is requested.
Your assignment is to create a Memory Manager which will allow the user to allocate and release memory. Your program also needs to keep track of how much memory is available, how much has been used, where the next available memory area is, etc.
Solution Requirements
---------------------
• Your solution should be capable of managing any number of allocations and deallocations,
• All allocations will come from the “free” memory. You will start with 64K free memory. Each time an allocation is requested, the free memory will decrease. When there is no more free memory available, your solution will call the onOutOfMemory() function.
• You should keep track of the InUse memory – so you don’t accidentally re-allocate it. The InUse memory is defined as the memory that is in use – it has been allocated but not yet deallocated. When it is deallocated, it is no longer InUse.
• When your solution deallocates memory, it is removed from the InUse memory. You need to keep track of the deallocated memory.
• You are not required to re-allocate deallocated memory. Even though a real memory manager would be expected to do this, it adds complexity to the solution and is not required for this assignment.
• Hints:
o You have three kinds of things you need to track: Free, InUsed, Used (deallocated)
o You should create an abstract linked-list structure for each of the above
You should provide implementations of the functions within MemoryManager.cpp.
!! DO NOT MODIFY MemoryManager.h !!
You can define additional functions within MemoryManager.cpp as necessary, but do not change the MemoryManager interface.
Memory Restrictions
-------------------
- No memory dynamically allocated during program execution (new, malloc, etc.).
- ALL data must fit inside MM_pool[ ]
- No other static or global variables
Error Handling
--------------
If you are unable to satisfy a request due to lack of memory your code should call the provided failure function (which will not return):
namespace MemoryManager
{
void onOutOfMemory();
}
HexDump
-------------
Many operating systems provide a utility called “hexdump” (or some other name with the same functionality.) A hexdump program allows you to examine the memory contents. I am providing a similar program called memView which allows you to see the contents of memory. This is a good debugging tool. Here is an example of the MemView output:
Pool Unsignd Unsigned
Mem Add indx bits chr ASCII# short int
-------- ---- -------- --- ------ ------- ------------
000A6430:[0 ] 00101110 |.| (46 ) (46 ) (1900590 )
000A6431:[1 ] 00000000 | | (0 ) (7424 ) (1090526464)
000A6432:[2 ] 00011101 | | (29 ) (29 ) (4259869 )
000A6433:[3 ] 00000000 | | (0 ) (16640) (16640 )
000A6434:[4 ] 01000001 |A| (65 ) (65 ) (65 )
000A6435:[5 ] 00000000 | | (0 ) (0 ) (0 )
000A6436:[6 ] 00000000 | | (0 ) (0 ) (0 )
000A6437:[7 ] 00000000 | | (0 ) (0 ) (0 )
000A6438:[8 ] 00000000 | | (0 ) (0 ) (805306368 )
000A6439:[9 ] 00000000 | | (0 ) (0 ) (1966080000)
000A643A:[10] 00000000 | | (0 ) (12288) (7680000 )
000A643B:[11] 00110000 |0| (48 ) (30000) (30000 )
000A643C:[12] 01110101 |u| (117 ) (117 ) (67108981 )
000A643D:[13] 00000000 | | (0 ) (0 ) (262144 )
000A643E:[14] 00000000 | | (0 ) (1024 ) (1024 )
Memory is nothing more than ones and zeroes. The meaning of each depends on context. memView will show the following:
Column 1: the hexadecimal value of the actual memory address
Column 2: the MM_pool index (from 0 to 64K - 1 which is 65,535)
Column 3: the bit sequence for that index (8 bits for 1 byte)
Column 4: the character value of that index (using only one byte)
Column 5: the ASCII # for that character
Column 6: the unsigned short value (using 2 bytes)
Column 7: the unsigned int value (using 4 bytes)
Compilation and Sample Output
-----------------------------
Please compile your implementation of MemoryManger.cpp against the provided MemoryManager.h and main.cpp.
This is only a test file. The actual file will be more complex but will only use the following functions
initializeMemoryManager() // set up the MM_pool with fresh memory
allocate() // allocate some memory, return a pointer
deallocate() // deallocate some memory
freeMemory() // return the number of bytes (chars) that is still free (un-used)
usedMemory() // return the number of bytes (chars) that used to be InUse, but have since been deallocated
inUseMemory() // return the number of bytes (chars) that are currently inUse
size() // return the size of the variable at this memory location. Similar to sizeof( ) in C++;
What to submit:
At the end of this document you will find your demo program along with the expected output. You will run this shell file which will produce the mmTest.out file. You will submit the following files:
mmTest.cpp,
mmTest.out,
MemoryManager.h
MemoryManager.cpp
Here is the command to produce the mmTest.out file
set -x #echo on
c++ mmTest.cpp MemoryManager.cpp -o mmTest
mmTest > mmTest.out
Endianness
From Wikipedia, the free encyclopedia
Endianness is the order of the bytes that compose a digital word in computer memory. It also describes the order of byte transmission over a digital link. Words may be represented in big-endian or little-endian format. When storing a word in big-endian format the most significant byte, which is the byte containing the most significant bit, is stored first and the following bytes are stored in decreasing significance order with the least significant byte, which is the byte containing the least significant bit, thus being stored at last place. Little-endian format reverses the order of the sequence and stores the least significant byte at the first location with the most significant byte being stored last.[1] The order of bits within a byte can also have endianness (as discussed later); however, a byte is typically handled as a numerical value or character symbol and so bit sequence order is obviated.
Both big and little forms of endianness are widely used in digital electronics. The choice of endianness for a new design is often arbitrary, but later technology revisions and updates perpetuate the existing endianness and many other design attributes to maintain backward compatibility. As examples, the IBM z/Architecture mainframes use big-endian while the Intel x86 processors use little-endian. The designers chose endianness in the 1960s and 1970s respectively.
Big-endian is the most common format in data networking; fields in the protocols of the Internet protocol suite, such as IPv4, IPv6, TCP, and UDP, are transmitted in big-endian order. For this reason, big-endian byte order is also referred to as network byte order. Little-endian storage is popular for microprocessors, in part due to significant influence on microprocessor designs by Intel Corporation. Mixed forms also exist, for instance the ordering of bytes in a 16-bit word may differ from the ordering of 16-bit words within a 32-bit word. Such cases are sometimes referred to as mixed-endian or middle-endian. There are also some bi-endian processors that operate in either little-endian or big-endian mode.
Illustration
Big-endianness may be demonstrated by writing a decimal number, say one hundred twenty-three, on paper in the usual positional notation understood by a numerate reader: 123. The digits are written starting from the left and to the right, with the most significant digit, 1, written first. This is analogous to the lowest address of memory being used first. This is an example of a big-endian convention taken from daily life.
The little-endian way of writing the same number, one hundred twenty-three, would place the hundreds-digit 1 in the right-most position: 321. A person following conventional big-endian place-value order, who is not aware of this special ordering, would read a different number: three hundred and twenty one. Endianness in computing is similar, but it usually applies to the ordering of bytes, rather than of digits.
The illustrations to the right, where a is a memory address, show big-endian and little-endian storage in memory.
Etymology
Danny Cohen introduced the terms Little-Endian and Big-Endian for byte ordering in an article from 1980.[2][3] In this technical and political examination of byte ordering issues, the "endian" names were drawn from Jonathan Swift's 1726 satire, Gulliver’s Travels, in which civil war erupts over whether the big or the small end of a soft-boiled egg is the proper end to crack open.[4][5]
Hardware
Computer memory consists of a sequence of storage cells. Each cell is identified in hardware and software by its memory address. If the total number of storage cells in memory is n, then addresses are enumerated from 0 to n-1. Computer programs often use data structures of fields that may consist of more data than is stored in one memory cell. For the purpose of this article where its use as an operand of an instruction is relevant, a field consists of a consecutive sequence of bytes and represents a simple data value. In addition to that, it has to be of numeric type in some positional number system (mostly base-10 or base-2 — or base-256 in case of 8-bit bytes).[6] In such a number system the "value" of a digit is determined not only by its value as a single digit, but also by the position it holds in the complete number, its "significance". These positions can be mapped to memory mainly in two ways:[7]
• increasing numeric significance with increasing memory addresses (or increasing time), known as little-endian, and
• decreasing numeric significance with increasing memory addresses (or increasing time), known as big-endian[8]
/* This is the driver for your memory manager. Do not make any changes to this file
Compile it with your MemoryManager.h and MemoryManager.cpp files.
The output that I got is at the bottom. Your output should be similar.
Notice that Total Memory = Free Memory + InUse Memory + Used Memory
Include this file when you submit your program
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include "MemoryManager.h"
using namespace std;
using namespace MemoryManager; // allow Memory Manager functions to be used without prefix
void memStats(); //helper function
int main(void)
{
initializeMemoryManager();
cout << "\nmemView immediately after initializeMemoryManager:\n";
memView(0,10);
cout<<"Program Starting...";
memStats();
cout<<"\n....allocate some memory:";
short* shortPtr = (short*) allocate(sizeof(short));
char* charPtr = (char*)allocate(sizeof(char));
int* intPtr = (int*)allocate(sizeof(int)*3);
char* lname = (char*)allocate(6);
char *fname = (char*)allocate(6);
int * maxIntPtr = (int*) allocate(sizeof(int));
memStats();
cout << "\n....assign some values:";
*maxIntPtr = INT_MAX; // largest positive 4 byte integer
strcpy(fname, "Steve");
strcpy(lname, "Gold");
*shortPtr = SHRT_MAX; // largest positive 2 byte integer
*charPtr = 'Z';
*intPtr = 1000000;
cout << "\n\nProper traversalInUse() worth 10 points:";
traverseInUse();
deallocate(fname);
deallocate(lname);
deallocate (shortPtr);
cout << "\n....deallocated 3 variables";
cout << "\n\nProper traversalInUse() and traversalUsed() worth 10 points:";
traverseInUse();
traverseUsed();
memView(0,75);
memStats();
cout << "\nFree Memory Avaialable before *DEATH:"<<(unsigned short)freeMemory()<<endl;
char *death = (char*)allocate(freeMemory()-10);
cout << "\nFree Memory Avaialable after *DEATH:"<<(unsigned short)freeMemory()<<endl;
cout << "Size of lname: "<<size(lname)<<endl;
cout << "Size of Death Star: "<<(unsigned short)size(death)<<endl;
memStats();
cout << "\n....forcing out-of-memory condition:";
int *zPtr = (int *) allocate(4 * 5); // try to allocate array of 5 integers
cout << "\nYou will never see this line";
return 0;
}
// this function gives you a summary of what memory looks like now.
void memStats()
{
int total = freeMemory()+inUseMemory()+usedMemory();
cout << "\n#####.....memStats.....################";
cout << "\n#Total:"<<total<<" Free:"<<freeMemory()<<" InUse:"<<inUseMemory()<<" Used:"<<usedMemory();
cout << "\n#Press return to continue...";
cout << "\n#######################################";
cin.get();
}
// output from this program:
/*
memView immediately after initializeMemoryManager:
Pool Unsignd Unsigned
Mem Add indx bits chr ASCII# short int
-------------- ---- -------- --- ------ ------- ------------
0x561cf3d14280:[ 0] 00000110 | | ( 6) ( 6) ( 6)
0x561cf3d14281:[ 1] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d14282:[ 2] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d14283:[ 3] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d14284:[ 4] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d14285:[ 5] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d14286:[ 6] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d14287:[ 7] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d14288:[ 8] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d14289:[ 9] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d1428a:[10] 00000000 | | ( 0) ( 0) ( 0)
Program Starting...
#####.....memStats.....################
#Total:65530 Free:65530 InUse:0 Used:0
#Press return to continue...
#######################################
....allocate some memory:
#####.....memStats.....################
#Total:65530 Free:65463 InUse:67 Used:0
#Press return to continue...
#######################################
....assign some values:
Proper traversalInUse() worth 10 points:
Traversing InUse Memory....
InUse Head:63
Index:63 Size:4 Next:51 Prev:0
Index:51 Size:6 Next:39 Prev:63
Index:39 Size:6 Next:21 Prev:51
Index:21 Size:12 Next:14 Prev:39
Index:14 Size:1 Next:6 Prev:21
Index:6 Size:2 Next:0 Prev:14
....deallocated 3 variables
Proper traversalInUse() and traversalUsed() worth 10 points:
Traversing InUse Memory....
InUse Head:63
Index:63 Size:4 Next:21 Prev:0
Index:21 Size:12 Next:14 Prev:63
Index:14 Size:1 Next:0 Prev:21
Traversing Used Memory....
Used Head:6
Index:6 Size:2 Next:39 Prev:0
Index:39 Size:6 Next:51 Prev:6
Index:51 Size:6 Next:0 Prev:39
Pool Unsignd Unsigned
Mem Add indx bits chr ASCII# short int
-------------- ---- -------- --- ------ ------- ------------
0x561cf3d14280:[ 0] 01001001 |I| ( 73) ( 73) ( 4128841)
0x561cf3d14281:[ 1] 00000000 | | ( 0) (16128) ( 100679424)
0x561cf3d14282:[ 2] 00111111 |?| ( 63) ( 63) ( 393279)
0x561cf3d14283:[ 3] 00000000 | | ( 0) ( 1536) ( 33555968)
0x561cf3d14284:[ 4] 00000110 | | ( 6) ( 6) ( 131078)
0x561cf3d14285:[ 5] 00000000 | | ( 0) ( 512) ( 654311936)
0x561cf3d14286:[ 6] 00000010 | | ( 2) ( 2) ( 2555906)
0x561cf3d14287:[ 7] 00000000 | | ( 0) ( 9984) ( 9984)
0x561cf3d14288:[ 8] 00100111 |'| ( 39) ( 39) ( 39)
0x561cf3d14289:[ 9] 00000000 | | ( 0) ( 0) (4278190080)
0x561cf3d1428a:[10] 00000000 | | ( 0) ( 0) (2147418112)
0x561cf3d1428b:[11] 00000000 | | ( 0) (65280) ( 25165568)
0x561cf3d1428c:[12] 11111111 | | ( 255) (32767) ( 98303)
0x561cf3d1428d:[13] 01111111 || ( 127) ( 383) ( 383)
0x561cf3d1428e:[14] 00000001 | | ( 1) ( 1) ( 1)
0x561cf3d1428f:[15] 00000000 | | ( 0) ( 0) ( 352321536)
0x561cf3d14290:[16] 00000000 | | ( 0) ( 0) ( 1376256)
0x561cf3d14291:[17] 00000000 | | ( 0) ( 5376) (1509954816)
0x561cf3d14292:[18] 00010101 | | ( 21) ( 21) ( 207224853)
0x561cf3d14293:[19] 00000000 | | ( 0) (23040) ( 809472)
0x561cf3d14294:[20] 01011010 |Z| ( 90) ( 3162) ( 234884186)
0x561cf3d14295:[21] 00001100 | | ( 12) ( 12) ( 917516)
0x561cf3d14296:[22] 00000000 | | ( 0) ( 3584) (1056968192)
0x561cf3d14297:[23] 00001110 | | ( 14) ( 14) ( 4128782)
0x561cf3d14298:[24] 00000000 | | ( 0) (16128) (1073757952)
0x561cf3d14299:[25] 00111111 |?| ( 63) ( 63) (1111490623)
0x561cf3d1429a:[26] 00000000 | | ( 0) (16384) ( 256000000)
0x561cf3d1429b:[27] 01000000 |@| ( 64) (16960) ( 1000000)
0x561cf3d1429c:[28] 01000010 |B| ( 66) ( 3906) ( 3906)
0x561cf3d1429d:[29] 00001111 | | ( 15) ( 15) ( 15)
0x561cf3d1429e:[30] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d1429f:[31] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d142a0:[32] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d142a1:[33] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d142a2:[34] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d142a3:[35] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d142a4:[36] 00000000 | | ( 0) ( 0) ( 100663296)
0x561cf3d142a5:[37] 00000000 | | ( 0) ( 0) ( 393216)
0x561cf3d142a6:[38] 00000000 | | ( 0) ( 1536) ( 855639552)
0x561cf3d142a7:[39] 00000110 | | ( 6) ( 6) ( 3342342)
0x561cf3d142a8:[40] 00000000 | | ( 0) (13056) ( 100676352)
0x561cf3d142a9:[41] 00110011 |3| ( 51) ( 51) ( 393267)
0x561cf3d142aa:[42] 00000000 | | ( 0) ( 1536) (1191183872)
0x561cf3d142ab:[43] 00000110 | | ( 6) ( 6) (1866924038)
0x561cf3d142ac:[44] 00000000 | | ( 0) (18176) (1819232000)
0x561cf3d142ad:[45] 01000111 |G| ( 71) (28487) (1684827975)
0x561cf3d142ae:[46] 01101111 |o| ( 111) (27759) ( 6581359)
0x561cf3d142af:[47] 01101100 |l| ( 108) (25708) ( 25708)
0x561cf3d142b0:[48] 01100100 |d| ( 100) ( 100) ( 100663396)
0x561cf3d142b1:[49] 00000000 | | ( 0) ( 0) ( 393216)
0x561cf3d142b2:[50] 00000000 | | ( 0) ( 1536) ( 1536)
0x561cf3d142b3:[51] 00000110 | | ( 6) ( 6) ( 6)
0x561cf3d142b4:[52] 00000000 | | ( 0) ( 0) ( 654311424)
0x561cf3d142b5:[53] 00000000 | | ( 0) ( 0) ( 2555904)
0x561cf3d142b6:[54] 00000000 | | ( 0) ( 9984) (1392518912)
0x561cf3d142b7:[55] 00100111 |'| ( 39) ( 39) (1951596583)
0x561cf3d142b8:[56] 00000000 | | ( 0) (21248) (1702122240)
0x561cf3d142b9:[57] 01010011 |S| ( 83) (29779) (1986360403)
0x561cf3d142ba:[58] 01110100 |t| ( 116) (25972) (1702258036)
0x561cf3d142bb:[59] 01100101 |e| ( 101) (30309) ( 6649445)
0x561cf3d142bc:[60] 01110110 |v| ( 118) (25974) ( 67134838)
0x561cf3d142bd:[61] 01100101 |e| ( 101) ( 101) ( 262245)
0x561cf3d142be:[62] 00000000 | | ( 0) ( 1024) ( 352322560)
0x561cf3d142bf:[63] 00000100 | | ( 4) ( 4) ( 1376260)
0x561cf3d142c0:[64] 00000000 | | ( 0) ( 5376) ( 5376)
0x561cf3d142c1:[65] 00010101 | | ( 21) ( 21) ( 21)
0x561cf3d142c2:[66] 00000000 | | ( 0) ( 0) (4278190080)
0x561cf3d142c3:[67] 00000000 | | ( 0) ( 0) (4294901760)
0x561cf3d142c4:[68] 00000000 | | ( 0) (65280) (4294967040)
0x561cf3d142c5:[69] 11111111 | | ( 255) (65535) (2147483647)
0x561cf3d142c6:[70] 11111111 | | ( 255) (65535) ( 8388607)
0x561cf3d142c7:[71] 11111111 | | ( 255) (32767) ( 32767)
0x561cf3d142c8:[72] 01111111 || ( 127) ( 127) ( 127)
0x561cf3d142c9:[73] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d142ca:[74] 00000000 | | ( 0) ( 0) ( 0)
0x561cf3d142cb:[75] 00000000 | | ( 0) ( 0) ( 0)
#####.....memStats.....################
#Total:65530 Free:65463 InUse:35 Used:32
#Press return to continue...
#######################################
Free Memory Avaialable before *DEATH:65463
Free Memory Avaialable after *DEATH:4
Size of lname: 6
Size of Death Star: 65453
#####.....memStats.....################
#Total:65530 Free:4 InUse:65494 Used:32
#Press return to continue...
#######################################
....forcing out-of-memory condition:
Memory pool out of memory
---Press "Enter" key to end program---:
*/
