159.342 - Operating Systems and Networks
Assignment #3 (due on 6/Jun)
Memory Management Using the Buddy System Strategy
OBJECTIVE:
The main objective in this assignment is to implement the Buddy System memory management 
strategy by writing two functions that implement the same functionalities as the C Standard library’s 
malloc() and free(). You should apply your knowledge of memory management concepts, so the 
functions are as efficient as possible. The buddy system will be characterised and compared against 
the existing C Standard library functions based on ACTUAL RUNNING TIME and MEMORY USAGE. 
Given a large block of contiguous memory to manage, your functions should be able to fulfil a series 
of memory allocation and deallocation requests. In your implementation, you are not allowed to 
use the built-in malloc, free, new, delete or any other memory allocators that come from other 
third-party libraries. 
START-UP CODES:
The start-up codes provide a test routine that makes successive calls for memory allocations and 
deallocations, involving a replaceable implementation of MALLOC and FREE. Functions for 
measuring the actual running time and total memory usage of the memory management strategy
are also provided.
///////////////////////////////
// TEST ROUTINE
///////////////////////////////
#ifdef RUN_COMPLETE_TEST 
 cout << "\n\n executing " << NO_OF_ITERATIONS << " rounds of combinations of memory allocation and deallocation..." <<
endl;
 
 for(i=0;i<NO_OF_ITERATIONS;i++) {
 k=myrand() % NO_OF_POINTERS; // pick a pointer
 if(n[k]) { // if it was allocated then free it
 // check that the stuff we wrote has not changed
 if ( (n[k][0]) != (unsigned char) k)//(n[k]+s[k]+k) )
 printf("Error when checking first byte! in block %d \n",k);
 if(s[k]>1 && (n[k][s[k]-1])!=(unsigned char) k )//(n[k]-s[k]-k))
 printf("Error when checking last byte! in block %d \n",k);
 FREE(n[k]); 
 }
 size=randomsize(); // pick a random size
 #ifdef DEBUG_MODE
 cout << "\tPick random size to allocate: " << size << endl;
 #endif
 
 n[k]=(unsigned char *)MALLOC(size); // do the allocation
 if(n[k] != NULL){
 #ifdef DEBUG_MODE
 cout << "\tallocated memory of size: " << size << endl; 
 #endif 
 s[k]=size; // remember the size
 n[k][0]=(unsigned char) k; // put some data in the first and 
 if(s[k]>1) n[k][s[k]-1]=(unsigned char) k; // last byte
 } else {
 cout << "\tFailed to allocate memory of size: " << size << endl; 
 } 
 }
#endif
n.h.reyes@massey.ac.nz
Selecting a memory management strategy to test
You can switch between different memory management strategies by changing the definition of 
MALLOC and FREE, as defined inside main.cpp (see below). The first two options are already 
provided, but the third option corresponds to the Buddy System and therefore, needs to be 
implemented in this assignment:
//---------------------------------------
// WHICH MEMORY MANAGEMENT STRATEGY?
//---------------------------------------
// enable the following compiler directives to test the real malloc and free
//(1) use built-in C functions
const string strategy = "malloc";
#define MALLOC malloc
#define FREE free
//---------------------------------------
//enable the following compiler directives to test a simple implementation of malloc and free
//(2) use user-defined functions
//const string strategy = "mymalloc";
// #define MALLOC mymalloc
// #define FREE myfree
//---------------------------------------
//enable the following compiler directives to test your implementation of the Buddy system strategy
//(3) use Buddy System
// const string strategy = "Buddy System";
// #define USE_BUDDY_SYSTEM
// #define MALLOC buddyMalloc
// #define FREE buddyFree
//---------------------------------------
CORE FUNCTIONS REQUIRED:
Skeleton functions for buddy system’s malloc and free are already provided inside buddysys.cpp. 
Write your implementation inside them. You are allowed to add any supporting functions, data 
structures and variables in the program. 
void *buddyMalloc(int request_memory){
 //write your buddy system’s memory allocation codes here
 //this function should provide the same functionality as the malloc() function
} 
int buddyFree(void *p){
 //write your buddy system’s memory deallocation codes here
 //this function should provide the same functionality as the free() function
}
AUXILIARY FUNCTIONS PROVIDED:
The Auxiliary functions, constants and data structures declared and implemented inside auxiliary.cpp 
and auxiliary.h should all be kept as is.
MINIMUM CONTIGUOUS MEMORY SIZE
As part of characterising the performance of your implementation, find the minimum contiguous 
memory size that allows the Buddy System strategy to accommodate the succession of memory 
allocation and deallocation requests in the test routine. To accomplish this, you need to experiment 
with different settings for the NUMBEROFPAGES until the test routine could be fully completed. 
Example: 
As an example, if you set NUMBEROFPAGES equal to 1024, then the MEMORYSIZE could be 
computed as follows:
// inside main.cpp
MEMORYSIZE = (long long int) ((long long int)NUMBEROFPAGES * (long long int)PAGESIZE);
Note that in the start-up codes, the PAGESIZE is set to 4096. Therefore, MEMORYSIZE will be equal 
to 4,194,304 bytes (1024 * 4096) or 4.19 MegaBytes. 
Next, with your MEMORYSIZE setting, run the test routines to see if all requests for memory 
allocations and deallocations can be satisfied. 
If the test routine cannot be completed, repeat the following steps until the test routine can be 
completed.
1. increase the MEMORYSIZE by a small amount, then recompile the code
2. run the test routine.
MEASURE OF PERFORMANCE
Download the Excel file, named assignment_documentation.xlsx from our stream website.
Characterise your Buddy System implementation and compare it against the C Standard library’s 
malloc and free to see if its speed of execution is comparable. Fill-up the Excel worksheet to 
document your experiment results. You only need to record the performance of your Buddy System 
implementation.
DEBUGGING:
For debugging purposes, I have created a simple test routine (inside the start-up codes) to assist the 
class. To activate this simple test temporarily, modify the auxillary.h file to enable 
RUN_SIMPLE_TEST as follows:
Before submitting your assignment, you should comment out #define RUN_SIMPLE_TEST and re activate #define RUN_COMPLETE_TEST again.
n.h.reyes@massey.ac.nz
n.h.reyes@massey.ac.nz
Further, inside main.cpp, I have made a provision for this Simple Test already, it will automatically 
switch to using 512 bytes as the MEMORYSIZE, to conduct the test.
For more details on how to debug your codes, please see the file, named 
A3_debugging_tips_2025_v1.docx. This is downloadable from our stream website.
SUBMISSION INSTRUCTIONS:
1. Submit your complete C/C++ program electronically via Stream. 
2. Use the following filename for your main program (as set in the start-up codes): main.cpp
3. Submit the makefile for building your codes. The makefile should suffice to build your 
codes.
4. As a backup, if you developed your program using an IDE, such as VSCODE or Clion, also 
submit the complete support files (e.g. CMakeLists.txt, project file, *.sln, *.JSON, etc.), for 
building your codes. 
5. Assignment documentation file: Download and fill out the Excel file, named 
assignment_documentation.xlsx to provide important information about your work. 
Rename the file using your ID_number (e.g. 87654321.xlsx). This will help facilitate 
accurate marking of your assignment. Deductions will be made if you do not submit the 
completed Excel file.
6. Snapshots file: Create a document containing snapshots of the simulation results. Show the 
results of executing RUN_COMPLETE_TEST. If this cannot be achieved, for partial marks, show 
the results of executing RUN_SIMPLE_TEST.
Label and briefly describe each image. You may create a Word document or a pdf file to 
accomplish this task.
7. Create a zip file containing the following files:
o Complete set of codes (including *.cpp, *.h, makefile, other supporting files)
o Snapshots file
8. Submit the zip file containing your complete program and snapshots electronically via 
Stream. You will find a button with the following label.
9. Submit the assignment documentation Excel file via Stream website. You will find a 
separate button with the following label.
10. Lastly, submit the Gen AI Usage documentation file via Stream website. You will find a 
separate button with the following label.
Distribution of marks:
The assignment will be marked based on functionality, design and correctness. 
The marks are distributed as follows:
• 5 marks: for correct implementation of buddyMalloc.
• 5 marks: for correct implementation of buddyFree.
• 3 marks: for memory efficiency (Note: this is based on the minimum contiguous memory 
size that allows the Buddy System strategy to accommodate the succession of memory 
allocation and deallocation requests in the RUN_COMPLETE_TEST routine)
• 2 marks: for documentation (i.e. accurate documentation of performance and other 
important assignment details - Excel assignment documentation, snapshots).
Other Notes
• This assignment is worth 15 marks. 
• Marks will be subtracted for obvious copying and/or for delays without justification.

請加QQ：99515681  郵箱：99515681@qq.com   WX：codinghelp