Introduction
代写一个内存管理的小程序，不能使用malloc, free这些系统库的内存分配函数。
Requirement
You are to write an efficient program that will simulate a memory manager. I have provided the driver program MemRunner.cpp, and the necessary class stubs in MemMan.h, and MemMan.cpp. You may add any classes and/or code you wish to MemMan.cpp, and MemMan.h. You may also use, and alter any Weiss files. MemCreate.out was compiled from MemCreate.cpp, and creates files used for testing. You should study MemCreate.cpp to better understand the probabilities and ranges of the operations requested. All files mentioned, as well as my executable, MemRunner.out.
Further specifications
- Dynamic Memory Allocation.
1.1. You may not use malloc(), free(), maxRAM, or currentRAM anywhere in your source code, including any Weiss files. No entity larger the 80 bytes may be created without using new. If you use any outside files, other than template files, you must add #include “mynew.h” at the top of the files.
1.2. The underlying code of the overloaded new provided by mynew.cpp relies on the fact that the real memory manager in the CSIF 64-bit machines stores that actual size allocated (plus 1) in the eight bytes before the address returned. Using memsize.out, I found that requesting 1 to 24 bytes costs 33 bytes, requesting 25 to 40 bytes costs 49 bytes, and requesting 41 to 56 bytes costs 65 bytes. Thus, the manager works in increments of 16 bytes, and charges 8 bytes for its overhead no matter what size is requested. It is these costs that are summed to determine your RealRAM figure. - MemRunner.out takes two parameters. The first is the name of the Mem file to be tested. The second is a single character that indicates whether the program should print out debugging information. If the character is ‘0’, then it will not print info, else it will. The actual testing will use ‘0’ as the second parameter.
- Operation Files
3.1. These are created by MemCreate.out. The names reflect the number of processes, number of operations, and the seed used to initialize the random number generator.
3.2. The first line contains the Ideal RAM, which is the maximum RAM ever allocated at one moment during the operations specified in the file.
3.3. Each of the rest of the lines have the format: Command [char] Process [int] {BlockNum [int] {Size [int]}}
3.3.1. Commands: ‘N’ = alloc, ‘A’ = access, ‘D’ = dealloc, ‘E’ = endProc, ‘F’ = fault. - MemMan Operations
4.1. alloc() takes a process number, and size to allocate. It returns the start address of memory block allocated. Occurs 17% of the time, and ranges from 4 - 262,144 bytes with a hyperbolic distribution leaning towards the smaller values.
4.1.1. MemCheck checks to make sure the memory allocated is currently unused, and will print an error it is used.
4.2. access() takes a process number, and address to access. The address need not be the start address of a block.
4.2.1. If the process owns the address then return true. 70% of all operations.
4.2.2. The ‘F’, fault, commands cause MemRunner to attempt to access an address that is not owned by the process. 1% of all operations. Your access() function must detect this “seg fault”, end the offending process by deallocating all of its memory, and returning false.
4.2.3. MemCheck checks to make sure that the returned values are correct, and will print an error when they are not correct.
4.3. dealloc() takes a process number, and the start address of the memory block to deallocate. Occurs 10% of the time. The requests are always valid, and are not checked.
4.4. endProc() takes a process number, and should free all memory assigned to that process. Occurs 2% of the time. These are not checked directly, since there is no detectable error possible until the re-run by checkOperations(). - Measurements
5.1. CPU time starts just before constructing your MemMan object in main(), and ends after your class deals with all of the operations. Thus, your destructors will not be called during CPU time.
5.1.1. You may not have any global variables since they would be constructed before CPU time starts.
5.2. “Your RAM” is the largest (start address + size) you ever return from alloc().
5.3. “Real RAM” is the maximum size of real dynamic RAM to which your program ever grew. - Grading
6.1. The program will be tested using three 100 process, 400000 operation files. The measurements will be the total of the three runs.
6.2. Programs must be compiled without any optimization options. You may not use any precompiled code, including the STL and assembly. Other than Weiss files, you must have written all of the code you submit.
6.3. If there are ANY error messages, then the program will receive zero.
6.4. CPU Time score = min(23, 20 Sean’s CPU / Your CPU)
6.5. Your RAM score = min(17, 15 Sean’s RAM / Your RAM)
6.6. Real RAM score = min(17, 15 * Sean’s Real RAM / Your Real RAM) - Makefile. The Makefile provided contains the minimum needed to create MemRunner.out. Note that it expects MemCheck.o to already exist.
7.1. To ensure that you handin all of the files necessary for your program, you should create a temp directory, and copy only .cpp, .h, MemCheck.o, and Makefile into it. Then try to make the program. Many students have forgotten to handin dsexceptions.h. - Suggestions.
8.1. Start early, and get something working without errors.
8.2. Don’t fuss about speed or size until you have something working. Too many students fail to have a correct program by the deadline because they spend too much time tweaking early on.
8.2.1. You will learn a lot just getting it running. Then you can use this knowledge to improve your code. I changed ADTs in 15 minutes at one point because the basics could be reused.
8.3. Create MemBlock class(es) that is/are stored in your ADTs.
8.4. To debug, add if-statements that are only true during the state in which you are interested. I left such a line in the loop in main(). I created a couple of functions in MemCheck that are useful for debugging : printOwner(address, endAddress) and printCurrentAllocations(proc). I’ve left commented out calls to these in strategic locations in MemMan.cpp.
8.5. Leave lots of time for testing and debugging. Test with all of the available files.
Example
$ MemCreate.out
N 0 0 7
Processes: 5
F 4
Operations: 25
A 0 0
Seed: 4
N 1 0 13
$ cat Mem-5-25-4.txt
N 3 1 5
50 5 25
A 1 0
N 3 0 6
E 1
N 4 0 9
A 0 0
A 3 0
E 0
D 3 0
N 3 2 20
A 4 0
N 4 0 21
A 4 0
N 1 0 4
A 4 0
D 3 1
A 4 0
A 3 2
N 4 1 4
A 1 0
N 4 2 4
$ MemRunner.out Mem-5-25-4.txt 1
Opnum: 0 alloc: proc: 3 address: 0 size: 6
Opnum: 1 alloc: proc: 4 address: 6 size: 9
Opnum: 2 access: proc: 3 address: 1
Opnum: 3 daAlloc: proc: 3 startAddress: 0
Opnum: 4 access: proc: 4 address: 13
Opnum: 5 access: proc: 4 address: 6
Opnum: 6 access: proc: 4 address: 13
Opnum: 7 access: proc: 4 address: 11
Opnum: 8 alloc: proc: 4 address: 15 size: 4
Opnum: 9 alloc: proc: 4 address: 0 size: 4
Opnum: 10 alloc: proc: 0 address: 19 size: 7
Opnum: 11 access: proc: 4 address: 21
Opnum: 11 endProc: proc: 4
Opnum: 12 access: proc: 0 address: 20
Opnum: 13 alloc: proc: 1 address: 26 size: 13
Opnum: 14 alloc: proc: 3 address: 0 size: 5
Opnum: 15 access: proc: 1 address: 33
Opnum: 16 endProc: proc: 1
Opnum: 17 access: proc: 0 address: 21
Opnum: 18 endProc: proc: 0
Opnum: 19 alloc: proc: 3 address: 5 size: 20
Opnum: 20 alloc: proc: 4 address: 25 size: 21
Opnum: 21 alloc: proc: 1 address: 46 size: 4
Opnum: 22 daAlloc: proc: 3 startAddress: 0
Opnum: 23 access: proc: 3 address: 12
Opnum: 24 access: proc: 1 address: 48
CPU Time: 0.001431 Ideal RAM: 50 Your RAM: 50 Real RAM: 688300
$ MemRunner.out Mem-100-400000-1.txt 0
CPU Time: 0.791837 Ideal RAM: 407454 Your RAM: 1251836 Real RAM: 702358
Sample Code
1 | int main(int argc, char* argv[]) |