Background

Description

The ADTs that you will implement are described fully in the ADT section below. Use the description there to design your classes. Please remember that you must provide good documentation as described in the Project Organization handout.

Here are your tasks:

1. Obtain the files LinkedList.h, LinkedList.cpp, and dsexceptions.h from the following location:

   /afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj2/

   These files do not adhere to CS341 coding standards. You can use them "as is". That is, you do not need to edit them to bring them up to CS341 standards. HINT: You might find it useful to change the retrieve method to return a reference rather than a constant reference.

2. Implement the MemBlock class.
3. Implement the FreeBin class.
4. Implement the MemoryManager class.
5. Copy the file Proj2.cpp from:

/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj2/Proj2.cpp

to your own directory. This Proj2.cpp is a driver that you can use to test your program. You do not need to submit it, nor do you need to write your own Proj2.cpp, though you will probably do so anyway to test your code. We provide this Proj2.cpp because if your Makefile works with it, your Makefile will work with the driver programs we will use to grade your project. However, you can submit a Proj2.cpp if you wish to ensure that submitmake and submit run work for this project. If you submit a Proj2.cpp, it will be overwritten by the grading scripts.

6. Answer the questions posed in 341-Fall04-proj2_questions.txt. Copy the file

/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj2/341-Fall04-p2_questions.txt

to your own directory and edit it to provide your answers to the questions. Don't forget to submit the edited file; it's 10% of this project's grade.

Definition of the ADT

Overview

Information about the state of a block of memory is maintained in a MemoryManager object as shown in the lower part of the figure. The MemoryManager maintains a linked list of FreeBins, with the sizes of blocks of memory stored in the FreeBins increasing by a factor of 2 as you move down the list, starting with a block size of 8 bytes. In the figure there are FreeBins for blocks of size 8, 16, 32, 64, and 128.

Each FreeBin maintains a linked list of MemBlocks that are free and of the appropriate size. For example, the first FreeBin has a list of two 8-byte blocks that are free - bytes 32 through 39, and 48 through 55. Within a FreeBin, blocks are kept in sorted order by increasing start address.

In addition, the MemoryManager maintains a linked list of MemBlocks that have been alloocated. This list does not need to be kept in any sorted order. In the figure, there are four blocks of memory that have been allocated - two 8-byte blocks and two 16-byte blocks.

To allocate a block of memory of size N, the MemoryManager does the following:

• Always allocate memory in multiples of 8 bytes. For example, if N=2 bytes, allocate A = 8; if N=35 bytes, allocate A = 40.

• Find the smallest free block whose size is greater than or equal to N and remove it from the appropriate FreeBin. The start address, P, of that block is returned.

• If no block of the appropriate type is found, throw an exception.

• If the free block is of size M and M > A, then the M - A unused bytes in the free block must be added back to the FreeBins. If M - A is a power of 2, it can be inserted directly into one of the FreeBins. If not, it will have to be broken up into smaller blocks that are powers of 2 and inserted into multiple FreeBins.

• Add a MemBlock to the list of allocated blocks that starts at address P and ends at address P + N - 1.

• Search the list of allocated blocks for the address to be freed.

• If that search is unsucessful, throw an exception.

• Otherwise, remove the block from the list of allocated blocks and add it to the FreeBins. Again, unless the size of the block is a power of 2, it will need to be broken up into smaller blocks that are powers of 2.

For each class described below, all data members must be private. Other than this requirement and any others explicitly stated in the description of a class, you have the freedom to design the class as you see fit. However, remember that you will be graded on the quality of that design. Be sure to note that it is generally a good idea to write an explicit destructor, copy constructor, and assignment operator, even if they are never called explicitly in your code, because they are often called implicitly.

MemBlock

• typedef unsigned long int mem_addr_t;

• The FreeBin class will have a list of MemBlocks as a private data member. Weiss' linked list code requires that list elements have operator!= defined. If you don't define this operator for the MemBlock class you'll get a cryptic error, so be sure to implement it.

• You must implement operator<< as shown in the example code on page 35 of the Weiss text.

• You can write any constructors you feel are necessary.

FreeBin

• You can write any constructors you feel are necessary.

• Because the MemoryManager class will create a list of FreeBins, you'll need to define operator!= for this class.

• You must implement operator<< as shown in the example code on page 35 of the Weiss text.

• You will need a method that removes and returns the first MemBlock (i.e., the one with the smallest start address) in the FreeBin's list.

• You will need a method that takes a MemBlock as an argument and inserts it into the FreeBin's list in ascending order of start address. This method must also check for pairs of blocks in the list that are adjacent in memory, remove them, and return some indication that a new blocks needs to be added to the next larger FreeBin.

MemoryManager

• void initialize(mem_addr_t start, mem_addr_t end) - Give the memory manager an initial block of memory that is initially free to be used for future allocation requests.

• mem_addr_t alloc(mem_size_t size) - Return the address of a block of memory of the given size. You must define mem_size_t as follows:
  • typedef unsigned long int mem_size_t;
  If there is not a free block big enough to satisfy the request, your code must throw an OutOfMemory exception. This exception class is defined in dsexceptions.h.

• void free(mem_addr_t p) - Free the block of memory that starts at address p. If no such block was previously allocated, throw a BadPointer exception. You must add this exception class to dsexceptions.h.

It will be useful to have a private method that takes as input the start and end addresses of a block of memory and inserts that block into the appropriate FeeBin (if its size is a power of 2) or FreeBins (if it needs to be decomposed into a number if smaller blocks whose sizes are powers of 2).

The main routine

Sample Output

#include <iostream.h>
#include "MemoryManager.h"

using namespace std;

int main(int argc, char **argv) {
  MemoryManager m;

  m.initialize(1, 32);

  cout << m;
  cout << endl << endl;

  mem_addr_t p1, p2, p3, p4;

  p1 = m.alloc(1);
  p2 = m.alloc(1);
  p3 = m.alloc(1);
  p4 = m.alloc(1);

  m.free(p1);
  m.free(p3);
  
  cout << m << endl << endl;

  m.free(p2);

  cout << m << endl << endl;

  m.free(p4);

  cout << m << endl << endl;
}

Memory Manager
--------------

FreeBins
--------
FreeBin: size = 8

FreeBin: size = 16

FreeBin: size = 32
MemBlock: 1 - 32


Allocated
---------


Memory Manager
--------------

FreeBins
--------
FreeBin: size = 8

FreeBin: size = 16
MemBlock: 1 - 16

FreeBin: size = 32


Allocated
---------
MemBlock: 17 - 24
MemBlock: 25 - 32


Memory Manager
--------------

FreeBins
--------
FreeBin: size = 8
MemBlock: 25 - 32

FreeBin: size = 16
MemBlock: 1 - 16

FreeBin: size = 32


Allocated
---------
MemBlock: 17 - 24


Memory Manager
--------------

FreeBins
--------
FreeBin: size = 8

FreeBin: size = 16

FreeBin: size = 32
MemBlock: 1 - 32


Allocated
---------

Files To Be Submitted

Submit the files using the procedure given to you for your section of the course.
If your makefile is set up correctly, you should be able to execute the command make submit.

Submit Tools

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your
submittals. Make sure they work. Do this before the due date.

Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/. One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.

Additionally, there are two programs for use only by CMSC-341 students (not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/ and are named submitmake and submitrun. You can use these programs to
make or run your submitted projects.

The syntax is similar to that for submit:

submitmake <class> <project>

Example:  submitmake cs341 Proj1

This makes the project, and shows you the report from the make utility. It cleans up the directory after making the project (removes .o and ii_files), but leaves the
executable in place.

submitrun <class> <project> [command-line args]

Example:  submitrun cs341Proj1 checkers checkfile.dat

This runs the project, assuming there is an executable (i.e. submitmake was run successfully).

Grading and Academic Integrity

Project grading is described in the Project Policy handout.

Your answers to 341-Fall04-proj1_questions.txt are worth 10% of your project grade.

Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.