CS 241: System Programming

Machine Problem 4
Memory Management

Deadline: Monday, 17 April, 4:00pm
(electronic submission)

Solution: Makefile, MemoryManager.c, MemoryManager.h (our test.c)
Description In this project, you will learn about Memory management. First, you will implement some memory allocation/deallocation schemes. Then, you will improve these allocation schemes by implementing compaction/defragmentation within your memory management system. Last, you will time and evaluate the allocation schemes.
When done with this MP, you should end up with at least two files: MemoryManager.h and MemoryManager.c. We are providing a very basic test program to help understand the overall interface, but you should modify it to run more extensive tests on your code. Ultimately, you will provide a framework for allocating and deallocating memory. You will also print timing information. Example output is provided here. You do not need to match the output exactly. Additionally, the addresses and distances between your addresses may vary.

Part 1: Memory Management Infrastructure

For part 1, you should implement at least two files: MemoryManager.c and MemoryManager.h.
Your memory management subsystem will implement the following memory allocation schemes:
First-Fit, Best-Fit, Worst-Fit and Next-Fit, as described in Tannenbaum, chapter four (especially section 4.2.2 pages 382-383). You will provide the user with an interface for making memory allocation requests and also for freeing up memory that is no longer needed by the user. In order to accomplish this, you need to implement the following five functions:
  1. MyMalloc, which first takes an integer parameter representing the desired memory allocation size, and second a void** parameter, which will be modified by the function to store a pointer to the newly allocated memory. (i.e. after a call to this function, dereferencing this pointer would give a pointer to the actual memory allocated within the system). This function should return an integer value of 1 if successful, and 0 if the memory could not be allocated (i.e. there is no hole big enough to hold the requested size).
    Note: You will need to store the pointers that MyMalloc assigns for part 2.

  2. MyFree, which takes a void**, corresponding to memory that was previously allocated using MyMalloc, and returns 0 if unsuccessful and 1 if successful. The memory should be deallocated, and made available for future requests. Last, it should set the pointer to NULL (that way the caller will have the local var as NULL)

  3. PrintMemory, which takes no parameters and returns nothing. This function should print out the state of the allocated memory following the format in the sample output provided here.

  4. InitializeMemory, which takes two parameters: First, the allocation scheme to use (You should use the enumeration given below), and second, an integer corresponding to the memory size available to this system. This function returns 1 if successful and 0 if the system could not allocate enough memory. You should allocate memory for your memory system and initialize your data structure(s) here.
    Note: We will give 5 extra credit points for any solutions that restrict mallocs to only InitializeMemory (i.e. all memory you use after the initial allocation of the array will be contained within that array). To get these bonus points, you must not use any extra memory outside of small automatics (e.g. no arrays or structs). If you qualify for the bonus points, note this in your README file. Clarification: You are only allowed to use one call to malloc() in order to qualify for the extra credit.

  5. TerminateMemory, which takes no parameters and frees up all the memory used for the initialized memory manager (including the MyMalloc'ed memory and the allocated array). This function should allow us to test multiple allocation schemes in a single run of the executable


    typedef enum AllocationAlgorithm
    {
	    FIRST_FIT, 
	    BEST_FIT, 
	    WORST_FIT, 
	    NEXT_FIT,
    } Algorithm;
In order to simulate the memory management, you must allocate a contiguous chunk of memory corresponding to the size passed into the InitializeMemory function. Then, whenever the user calls MyMalloc or MyFree, all the memory they access should be within the contiguous memory chunk you allocated initially.
One of the jobs of the memory management subsystem is to service memory requests by matching the size of the request with a large enough hole, from which to satisfy the request. The hole should be chosen corresponding to the selected memory allocation scheme (First-fit, Best-fit, Worst-fit, or Next-fit).
Note that when freeing memory, you must coalesce with the neighboring memory if possible, as shown in Figure 4-6, on page 382 in Tannenbaum. (i.e. If two or more holes would be adjacent after a call to MyFree, they should be merged into one hole).
In addition to the required array for the simulated system memory, you can use any data structure(s) you want to implement the allocation algorithms. Figure 4-5 in Tanenbaum (page 381) shows two data structures, but you may decide to modify or change anything. You should try to implement structures to provide efficient searching for the appropriate holes in the chosen allocation scheme. However, you will not be graded on efficiency; although you have the option for extra credit if you do implement it under the no malloc's outside of InitializeMemory constraint, as stated.

Part 2: Compaction

Implement compaction in your memory manager. Compacting memory attempts to move the allocated memory so that the remaining holes can be combined into a larger hole. Your memory manager should automatically compact memory under the following two conditions:
  1. A call is made to MyMalloc where no holes are found which are large enough to fit the requested memory, and the sum of the remaining hole sizes would supply enough memory
  2. The fragmentation has gone above the specified fragmentation threshold. For simplicity, you can compute the fragmentation by simply using: numberOfHoles / totalNumSegments, where the total number of segments is the number of holes plus the number of allocated processes.

NOTE: in order to allow us to more precisely test part 1, compaction must be implemented as an optional choice. To do this, add an integer parameter to the InitializeMemory function. This should correspond to the fragmentation threshold (e.g. a value of 75 corresponds to 75%). A value of 100 or higher means no compaction should be performed.
In order to implement compaction, you must somehow store the addresses of all the pointers you return from MyMalloc (as noted in part 1). Then, you need to update these pointers so that the caller will point to the updated memory location.

For uniformity, implement the compaction as a separate function called, Compact (or something equivalent).

Part 3: Timing and Evaluation

Similar to past MPs, we want to measure various execution times of your implementation. Follow the sample output provided in terms of what you must print out. You should provide the following times:
  1. Individual and total times to find the appropriate hole for memory allocation
  2. Individual and total compaction times

Like MP2 & MP3, use clock_gettime as used in Example 9.8 in R&R to time the various requested behaviors.
These results should be included in your output, similar to the sample output. Note: You will need to provide a brief analysis in the README file as described below.
Given Code test.c: Sample test program. Note: We will use our own test.c for testing your implemntation.
Sample output, same link from above
Deliverable This assignment is expected to be completed via pair programming. You are encouraged to form a group of 2, although you may elect to work alone. Newsgroup communication about general issues is allowed. Please post any questions on the given code on the newsgroup. You should use the CSIL Linux machines to do the assignment.

You are strictly required to use C. For this MP, you must create MemoryManager.c and MemoryManager.h. You are welcome to create other files if desired. Additionally, create a makefile which compiles your files and links them with test.c to create an executable called, memory_test.

Create a README file as well, detailing any problems encountered during program design or execution. Include in the README the following information:
  1. MP number and title
  2. Your names and netids
  3. How you split the work for the entire MP
  4. Analysis of the memory allocation schemes. From your results, which allocation is best, and why? (Your answer may depend on the situation - in which case describe what makes one better in some situations than in others). Included in this section, you should briefly describe the data structure(s) you used and any assumptions you made.
  5. Whether you implemented under the extra credit constraints
  6. An approximate percentage range of the total memory that is available for allocation with your implementation and what causes the range (e.g. all small allocations vs. one large, etc.)
Handin Use Compass to electronically handin an archive containing the files listed above (makefile, MemoryManager.h, MemoryManager.c, and README - and any others you created) under the "MP4 Handin" assignment. This must be done before 4pm on Monday, 17 April. Every hour late is minus 2% credit. No submissions accepted after 4pm on Tuesday, 18 April.

Grading Criteria
  • Part 1: Memory Management framework - 50%
    • Overall Framework - 10%
    • Allocation Schemes - 40%
      • First-Fit - 10%
      • Best-Fit - 10%
      • Worst-Fit - 10%
      • Next-Fit - 10%
  • Part 2: Memory Compaction - 30%
  • Part 3: Evaluation and Timing - 15%
  • Makefile and README - 5%
  • Extra credit for malloc only in InitializeMemory() - 5%

Clarifications
  1. Compaction for #2 above is easily performed if we check as the first duty in MyMalloc.
  2. You are only allowed to use one call to malloc() in order to qualify for the extra credit.
  3. In your README, specify an approximate percentage range of how much of the total memory is available for allocation and what situations fit the different values (e.g. all small allocations vs. one large, etc.)
  4. The one malloc you perform in InitializeMemory should allocate the entire memory block you will use, and no more. You should not be allocating twice or three times that amount for any overhead. If you are trying for extra credit, that data must fit within that one malloc (of size requested by the user). If you are not trying for extra credit, use a separate malloc call for those additional bytes.