Starting from:
$30
CSCE313-Assignment 1 Buddy System Memory Allocator Solved
You are to implement a buddy-system memory manager that allocates memory in blocks with sizes that are power-of-two multiples of a basic block size. The basic block size is given as an argument when the allocator is initialized.
• The memory allocator shall be implemented as a C++ module BuddyAllocator , which consists of a header file BuddyAllocator.h and BuddyAllocator.cpp . (A copy of the header file and a rudimentary .cpp file are provided to you). You have to:
– Provide implementation for the empty types (e.g., BlockHeader, LinkedList and functions in the BuddyAllocator class
– Add necessary functions and types as you see fit
• Evaluate the correctness (up to a certain point) and the performance of your allocator. For this, you will be given the source code of a function which implements the highly-recursive Ackerman function. In this implementation of the Ackerman function, random blocks of memory are allocated and de-allocated sometime later, generating a large combination of different allocation patterns. The Ackerman function is provided in the form of two files (i.e. Ackerman.h and Ackerman.cpp ).
• You will modify the given Main.cpp so that it reads the basic block size and the memory size (in bytes) from the command line, initializes the memory, and then calls the Ackerman function. It must measure the time it takes to perform the number of memory operations.
• Use the getopt() C library function to parse the command line for arguments. The usage of your executable should be of the form: memtest [-b <blocksize] [-s <memsize]
-b <blocksize defines the block size, in bytes. The default should be 128 bytes if the -b argument is not provided.
-s <memsize defines the size of the memory to be allocated, in bytes. The default should be 512 kB.
• Repeatedly invoke the Ackerman function with increasingly larger number of values for n and m (be careful to keep n ≤ 3 as the processing time increases steeply for large values of n). Identify at least one point that you may modify in the simple buddy system described above to improve the performance. Also be sure to provide an argument as to why/how your proposed change would improve performance. • Make sure that the allocator gets de-allocated (and has its memory freed) when the program either exits or aborts. Use the destructor function of the BuddyAllocator class to acheive that.
4 Implementating Buddy-System Allocation
In our buddy-system memory allocator, memory block sizes must be a power of two with a minimum size defined by the variable basic block size . For example, if 9kB of memory is requested, the allocator must return the nearest power of two, 16kB. Because of this 7kB is wasted in a process known as fragmentation. In spite of the potential for wastage, the restriction of block sizes to powers of two makes the management of free memory blocks easy. The allocator must simply keep an array of free lists, one for each allowable block size. Every request is rounded up to the next allowable size, and the corresponding free list is checked. If there is an entry in the free list, this entry is returned and then removed from the free list.
In the event that the free list for that particular block size is empty (i.e. there are no free memory blocks of that size), a larger block is selected using the free list of some larger block size and then recursively split until a block of the desired size is obtained. Whenever a free memory block is split in two, one block gets either used or further split, and the other unused block, its buddy, is added to the corresponding free list.
For example: Assume that the system needs a 16kB block, but the free list is empty.
Also assume that the free list for 32kB blocks is empty, but the 64kB list has a free element,
B. The allocator should therefore select the 64kB block and split it into two blocks, BL and BR, each 32kB and add then to the 32kB free list. BL should then be split again into BLL and BLR, each 16kB. Finally, BLL should be used and BLR should be added to the 16kB free list.
In the previous example, the blocks BL and BR are buddies, as are BLL and BLR. Whenever a memory block is freed, it may be coalesced with its buddy. Coalescing can only occur if the buddy is free as well. If it is, then the two buddies can be combined to form a single memory block that is twice the size of each buddy individually.
For example: Assume that BLL and BLR are free, and that we have just freed BLR. In this case, BLL and BLR can be coalesced into the single block BL. We therefore, delete BLL from its free list and proceed to insert the newly formed BL into into the next higher free list. Before we do that, we check to see if its buddy, BR is free. If so, then BL and BR can be recombined to form B, recreating the 64kB block that was split in the first example of this section.
4.1 Finding Buddies
The buddy system performs two operations on memory blocks: splitting and coalescing. Whenever we split a free memory block of size 2n with start address A, we generate two buddies: one with start address A, and the other with the start address of A that has the (n− 1)th bit flipped.
Finding the buddy of a block being freed is just as simple when the size of the block is known: The address of the buddy block is determined by flipping the appropriate bit of the block’s start address, just as is the case when we split a block. The problem is: How will we know what the block size is when the program needs to split or coalesce a block?
The easiest way is to explicitly store it at the beginning of the allocated block as a part of a header. This wastes memory as the space where the header is being stored cannot be used by the requesting program to store any data. Alternatively, the size can be implicitly inferred from other data, typically stored in the free list. However, for this assignment, you should just keep it part of the header.
4.2 Managing the Free List
You want to minimize the amount of space needed to manage the free list. For example, you do not want to implement the lists using traditional means (i.e. with dynamically created elements that are connected with pointers). An easy solution is to use the free memory blocks themselves to store the free-list data. For example, the first bytes of each free memory block would contain the pointer to the previous and to the next free memory block of the same size. The pointers in the first and last block in each free list can easily be stored in an array of pointers, two for each allowable block size.
4.3 Note on Block Size
If you decide to put management information into allocated blocks such as the size of the block, you have to be careful about how this may affect the size of the allocated block. For example, when you allocate a block of size 5, and add an 8-byte header to the block, you actually need room for the 8-byte header along with the 5-bytes for the data space requested. Consequently, you would need a 13-byte block instead of a 5-byte one (in case you couldn’t tell, this is extremely wasteful).
4.4 Where does the allocator get memory from?
Inside the constructor of BuddyAllocator class, your program must acquire the required amount of memory from the system. It must interface with the existing system library, malloc() in C or new operator in C++ , in order to do so. Remember, your allocator must
also return the memory to the system when it is done using the BuddyAllocator::free() function.
4.5 What does BuddyAllocator::alloc() return?
In the case above, putting the management information block in front of the allocated block is an effective way to access it easily. In this case, make sure that your BuddyAllocator::alloc() routine returns the address of the allocated block, not the address of the management information block. There is no guarantee that the program calling BuddyAllocator::alloc()
won’t completely overwrite the header information.
4.6 Initializing the Free List and the Free Blocks
You are given the size of the available memory as argument to the BuddyAllocatorconstructor function. The number entered by a potential user is likely not a power of two multiple of the basic block size. However, in order to function correctly, your program must partition the memory into a sequence of power-of-two sized blocks and initialize the blocks and the free list accordingly. This means that your program could use more memory than requested by the user.
• The memory allocator shall be implemented as a C++ module BuddyAllocator , which consists of a header file BuddyAllocator.h and BuddyAllocator.cpp . (A copy of the header file and a rudimentary .cpp file are provided to you). You have to:
– Provide implementation for the empty types (e.g., BlockHeader, LinkedList and functions in the BuddyAllocator class
– Add necessary functions and types as you see fit
• Evaluate the correctness (up to a certain point) and the performance of your allocator. For this, you will be given the source code of a function which implements the highly-recursive Ackerman function. In this implementation of the Ackerman function, random blocks of memory are allocated and de-allocated sometime later, generating a large combination of different allocation patterns. The Ackerman function is provided in the form of two files (i.e. Ackerman.h and Ackerman.cpp ).
• You will modify the given Main.cpp so that it reads the basic block size and the memory size (in bytes) from the command line, initializes the memory, and then calls the Ackerman function. It must measure the time it takes to perform the number of memory operations.
• Use the getopt() C library function to parse the command line for arguments. The usage of your executable should be of the form: memtest [-b <blocksize] [-s <memsize]
-b <blocksize defines the block size, in bytes. The default should be 128 bytes if the -b argument is not provided.
-s <memsize defines the size of the memory to be allocated, in bytes. The default should be 512 kB.
• Repeatedly invoke the Ackerman function with increasingly larger number of values for n and m (be careful to keep n ≤ 3 as the processing time increases steeply for large values of n). Identify at least one point that you may modify in the simple buddy system described above to improve the performance. Also be sure to provide an argument as to why/how your proposed change would improve performance. • Make sure that the allocator gets de-allocated (and has its memory freed) when the program either exits or aborts. Use the destructor function of the BuddyAllocator class to acheive that.
4 Implementating Buddy-System Allocation
In our buddy-system memory allocator, memory block sizes must be a power of two with a minimum size defined by the variable basic block size . For example, if 9kB of memory is requested, the allocator must return the nearest power of two, 16kB. Because of this 7kB is wasted in a process known as fragmentation. In spite of the potential for wastage, the restriction of block sizes to powers of two makes the management of free memory blocks easy. The allocator must simply keep an array of free lists, one for each allowable block size. Every request is rounded up to the next allowable size, and the corresponding free list is checked. If there is an entry in the free list, this entry is returned and then removed from the free list.
In the event that the free list for that particular block size is empty (i.e. there are no free memory blocks of that size), a larger block is selected using the free list of some larger block size and then recursively split until a block of the desired size is obtained. Whenever a free memory block is split in two, one block gets either used or further split, and the other unused block, its buddy, is added to the corresponding free list.
For example: Assume that the system needs a 16kB block, but the free list is empty.
Also assume that the free list for 32kB blocks is empty, but the 64kB list has a free element,
B. The allocator should therefore select the 64kB block and split it into two blocks, BL and BR, each 32kB and add then to the 32kB free list. BL should then be split again into BLL and BLR, each 16kB. Finally, BLL should be used and BLR should be added to the 16kB free list.
In the previous example, the blocks BL and BR are buddies, as are BLL and BLR. Whenever a memory block is freed, it may be coalesced with its buddy. Coalescing can only occur if the buddy is free as well. If it is, then the two buddies can be combined to form a single memory block that is twice the size of each buddy individually.
For example: Assume that BLL and BLR are free, and that we have just freed BLR. In this case, BLL and BLR can be coalesced into the single block BL. We therefore, delete BLL from its free list and proceed to insert the newly formed BL into into the next higher free list. Before we do that, we check to see if its buddy, BR is free. If so, then BL and BR can be recombined to form B, recreating the 64kB block that was split in the first example of this section.
4.1 Finding Buddies
The buddy system performs two operations on memory blocks: splitting and coalescing. Whenever we split a free memory block of size 2n with start address A, we generate two buddies: one with start address A, and the other with the start address of A that has the (n− 1)th bit flipped.
Finding the buddy of a block being freed is just as simple when the size of the block is known: The address of the buddy block is determined by flipping the appropriate bit of the block’s start address, just as is the case when we split a block. The problem is: How will we know what the block size is when the program needs to split or coalesce a block?
The easiest way is to explicitly store it at the beginning of the allocated block as a part of a header. This wastes memory as the space where the header is being stored cannot be used by the requesting program to store any data. Alternatively, the size can be implicitly inferred from other data, typically stored in the free list. However, for this assignment, you should just keep it part of the header.
4.2 Managing the Free List
You want to minimize the amount of space needed to manage the free list. For example, you do not want to implement the lists using traditional means (i.e. with dynamically created elements that are connected with pointers). An easy solution is to use the free memory blocks themselves to store the free-list data. For example, the first bytes of each free memory block would contain the pointer to the previous and to the next free memory block of the same size. The pointers in the first and last block in each free list can easily be stored in an array of pointers, two for each allowable block size.
4.3 Note on Block Size
If you decide to put management information into allocated blocks such as the size of the block, you have to be careful about how this may affect the size of the allocated block. For example, when you allocate a block of size 5, and add an 8-byte header to the block, you actually need room for the 8-byte header along with the 5-bytes for the data space requested. Consequently, you would need a 13-byte block instead of a 5-byte one (in case you couldn’t tell, this is extremely wasteful).
4.4 Where does the allocator get memory from?
Inside the constructor of BuddyAllocator class, your program must acquire the required amount of memory from the system. It must interface with the existing system library, malloc() in C or new operator in C++ , in order to do so. Remember, your allocator must
also return the memory to the system when it is done using the BuddyAllocator::free() function.
4.5 What does BuddyAllocator::alloc() return?
In the case above, putting the management information block in front of the allocated block is an effective way to access it easily. In this case, make sure that your BuddyAllocator::alloc() routine returns the address of the allocated block, not the address of the management information block. There is no guarantee that the program calling BuddyAllocator::alloc()
won’t completely overwrite the header information.
4.6 Initializing the Free List and the Free Blocks
You are given the size of the available memory as argument to the BuddyAllocatorconstructor function. The number entered by a potential user is likely not a power of two multiple of the basic block size. However, in order to function correctly, your program must partition the memory into a sequence of power-of-two sized blocks and initialize the blocks and the free list accordingly. This means that your program could use more memory than requested by the user.
1 file (97.6KB)
