Programming Project 1

Due date: Thu 2/7 11:00 pm

Introduction

In this project you will write a simple heap manager for integer arrays. The heap manager will first obtain a large block of memory and will then handle requests to allocate and deallocate contiguous blocks of memory for integer arrays. In order to manage the memory efficiently, the large block is divided into small chunks and memory is given out in multiples of chunks. The manager allocates enough chunks to cover the requested size.

The Heap Manager

The heap size and chunk size are given by constants in the code. The constants and interface of the class are defined as follows:

#ifndef HEAP_SIZE 
#define HEAP_SIZE  100
#endif

#ifndef CHUNK_SIZE
#define CHUNK_SIZE  10
#endif

class HeapManager {
public:
  HeapManager();
  ~HeapManager();

  int *newInt(int size = 1);
  bool deleteInt(int *delptr);
  void printHeap();
private:
  ...
}
The function newInt mimics new and allows the user to request memory for integer arrays of the size given by its argument. The heap manager should implement the first-fit algorithm. Thus when a request arrives which requires k chunks, the manager will search for the first (in address order) sequence of k chunks that can be allocated and allocate these. If this succeeds then a pointer is returned and a message is printed to the screen as illustrated below. If the heap does not have k contiguous free chunks then a null pointer is returned and an appropriate message is printed to the screen as illustrated below.

The function deleteInt mimics delete and should deallocate the memory that was allocated with its argument pointer. The function must check that the input pointer is indeed associated with a block of memory that has been allocated by the manager; otherwise no memory is deallocated and the function returns false. If the pointer is legal then the function returns true.

The function printHeap prints a list of 0/1's each representing the status of a chunk, 0 if free and 1 if allocated. So we get a visual representation of the heap state.

For example, the following code

  HeapManager HM;
  int *p1, *p2, *p3, *p4;

  p1 = HM.newInt(9);
  for (int i=0;i<9;i++) p1[i]=i;
  p2 = HM.newInt(32);
  HM.printHeap();
	
  p3 = HM.newInt(29);
  HM.printHeap();
  p4 = HM.newInt(38);
  HM.printHeap();

  HM.deleteInt(p1+3);
  HM.printHeap();

  HM.deleteInt(p2);
  HM.printHeap();

  p4 = HM.newInt(19);
  HM.printHeap();
  for (int i=0;i<9;i++) cout << p1[i] << " ";
  cout << endl;
produces the the following output
Allocating 1 chunks starting at chunk 0
Allocating 4 chunks starting at chunk 1
1111100000
Allocating 3 chunks starting at chunk 5
1111111100
No Space found for allocation of 4 chunks
1111111100
Bad Pointer: memory not deallocated
1111111100
DeAllocating block at chunk 1
1000011100
Allocating 2 chunks starting at chunk 1
1110011100
0 1 2 3 4 5 6 7 8
Notice that we number chunks starting with 0, and that printHeap prints 10 bits representing the status of the 10 available chunks. Since chunk size is 10, the first request for 9 integers requires one chunk, the second request for 32 integers requires 4 chunks, etc. Notice that after the first 3 allocations, we only have 2 chunks left and therefore the next allocation request is denied. The first deallocation request is denied since the pointer is not the start of an allocated block (in this case not even the beginning of a chunk). The next deallocation request is executed. Notice that for the last allocation, as for the previous ones, the manager picks the first location of free blocks for the request - as required by first-fit allocation. Finally, note that you really must provide the requested memory. The program above uses the memory given by pointer p1. The last line of the output is a printout of all the values in this array.

Implementation

You are free to use any implementation of the interface above as long as you implement your own data structures (no STL or other libraries) and provide correct functionality.

However, to simplify testing of your code please use the same text as in the diagnostic messages in the example above. The printing statements are provided in the file HeapManager.cpp

One simple implementation is as follows. The status of the heap is represented using an integer array with one entry per chunk. Each free chunk is represented by a 0, and each allocated block is represented by having a unique integer identifier in all chunks of the block. Therefore, for the example above we need an array of size 10, and the representation after the first two allocations has the values: 1 2 2 2 2 0 0 0 0 0. After allocating the third and deallocating the second we get 1 0 0 0 0 3 3 3 0 0. After the final allocation we get 1 4 4 0 0 3 3 3 0 0. As the example illustrates it is enough to use unique identifiers; you do not need to reuse index 2 after it has been deallocated. This makes for a simple implementation . In principle one would need to make sure that we do not run out of indices (go over max int). It is relatively simple to handle this and you may do so but for this project you can just ignore this issue.

Notice that this representation allows you to identify free blocks (sequences of zeros), identify a beginning of a block (non zero and different from previous entry), and length of a block (all entries with same value), so that you can perform all the operations using it.

Files

The interface code of the heap manager and some printout statements are given in HeapManager.cpp and HeapManager.h, and the sample main program is given in main1.cpp. All files are in /comp/80/files/pp1/.

Submitting your program

Style:

You should use good style throughout your code: your code should be well documented and easy to follow; use meaningful variable names; indent your code appropriately; use constants where appropriate; give each function and major block of code a preceding comment describing what they do. Please make sure that your code and text should be easy to read when printed. Make sure that there are no line wraps by using less than 80 columns in your files.

Assuming your code is in files as above in the current directory on our sun machines, you should submit by typing:
provide comp80 pp1 HeapManager.cpp HeapManager.h

Your code should compile (with g++) with main1.cpp and any other program that uses the interface correctly.

Extra Credit

This part is optional; you can get up to 20 extra points for this part.

Notice that the implementation above is pretty inefficient since it spends time linear in the number of chunks when searching for free space for allocation and when updating the representation (since we have to mark all chunks).

Implement fast allocation using the best fit algorithm. Your implementation should avoid this linear dependence for allocation and deallocation of memory.

To submit add ExtraHeapManager.cpp ExtraHeapManager.h when providing your files.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation -no_images -dir TEMPHTML pp1.tex

The translation was initiated by Roni Khardon on 2008-01-30


Roni Khardon 2008-01-30