You can write a C, C++, or Java program that demonstrates the processing of memory allocation and deallocation requests when the buddy algorithm is being used. The input to your program will give the amount of memory available, the size of the smallest possible allocation, and a sequence of allocation and deallocation requests. Details are provided later.

In the buddy system each block of memory used to satisfy an allocation request has a size that is exactly a power of 2 storage units (for example, 512, 1024, 16384)1. The memory management software (that is, your solution to this assignment!) will keep linked lists that identify the unused blocks of memory, which will have sizes that are a power of 2. The number of such lists depends on the amount of memory available to the system, and the size of the smallest allowable allocation. For example, suppose we have 1024 bytes in the system, and the smallest allowable allocation is for 128 bytes. We will need four lists of unused blocks: one for 128-byte blocks, one for 256-byte blocks, one for 512-byte blocks, and one for 1024-byte blocks. Obviously some of these may be empty lists. Each list entry will need to identify its size and its location (that is, its lowest or starting address). The size could be implied from the list on which the block appears (all blocks on the 256-byte block list should obviously be 256 bytes long), but you will likely find it better to explicitly record the size of the block in its list entry.

The simulated memory used in this problem will begin at location 0. Note that there is no real memory being allocated in this problem, except, of course, for linked list entries and any other data structures used in your solution. For the example in the previous paragraph, where we have

1024 bytes of memory with a smallest block size of 128 bytes, all block addresses will be less than 1024. In fact, we can easily see that the only block addresses permitted are 0, 128, 256, 384,

512, 640, 768, and 896.

Memory Management Requests

There are two memory management request permitted in this assignment: allocation of a specified amount of memory, and deallocation of a pevious allocation. How your program is to handle each of these operations is described, in detail, in the following paragraphs.

Allocation of R bytes2 is performed by first rounding R up to the next power of 2, if it wasnt already a power of 2; assume this value is called K. The appropriate free list (that is, the free list for blocks of size K) is then checked to determine if a free block is available. If it is, then

1 Although most modern machines are byte addressable, many earlier machines could only address larger units of storage, like 16, 24, 36, or 60 bits. We will assume bytes as the units of allocation to avoid further use of stilted terms like units of storage.

2 You may assume that R will never be larger than the size of the memory.

that free block with the smallest address3 is removed from the list and used to satisfy the request; the allocation is complete.

If the free list for blocks of size K is empty, then the free list for blocks with the next larger size (2K) is examined. And if it doesnt have any entries, the program keeps looking in the free lists for larger and larger blocks (4K, 8K, ), until either a free block is found or the free lists for all the larger block sizes have been examined.

If no free block of size K or a larger is found, the allocation request isnt discarded. Instead, it isdeferreduntil sometime later when a suitable free block does become available4. Deferring a request is done by saving the request at the end of a linked list of such deferred requests. An example of a deferred request will be given later.

Of course, if a larger free block is found, then it is removed from its list and split into two smaller blocks (each half the size of the original), and these are placed on the appropriate free list. One of these blocks (we always choose the one with the smaller address5) is then used to satisfy the request, either directly (if it is of size K), or indirectly, by splitting it again to yield two even smaller blocks which are handled in the same manner.

Deallocation is almost the inverse of allocation. When a block B is deallocated, its buddys address is first determined. If block B has address A and size K, we compute A / K, always yielding an integer result. If this value is even (that is, if the low-order bit in the binary representation of A / K is 0, or (A / K) mod 2 is 0), then the buddys address is A + K; otherwise the buddys address is A K. The free list for blocks with size K is examined for a free block with the buddys address. If that block is not found, then an entry for B is added to the free list for size K blocks. Otherwise, Bs buddy is removed from the free list for size K blocks and joined with block B to form a larger free block B' . This block has size 2K and an address that is the smaller of B and its buddy. We then continue as if we were trying to deallocate this larger block B'. The process is guaranteed to terminate.

Once the deallocation is complete, we then need to determine if any of the deferred allocation requests can now be satisfied. This is done by considering each of the deferred requests, one at a time, in the same order the requests were submitted (that is, the deferred request queue is a FIFO queue). Each allocation request that can now be performed is removed from the deferred list, and is allocated the needed storage).

An Example

An illustration with real numbers will aid your understanding of these actions. Specifically, lets again assume we have a region with 1024 bytes to use in satisfying allocation requests, and that the smallest region well use to satisfy a request is 128 bytes.

Assume we have the following allocation and deallocation requests to process, in the order given. Each allocation request is given a unique positive integer ID. Deallocation of the allocated memory will use the same ID.

3 This is done to guarantee that all correct solutions will yield the same output.

4 In a real system, the process making such a request might be blocked until sufficient storage becomes available to satisfy the request.

5 As before, this guarantees all correct solutions will yield the same output.

ID	Action
1	Allocate 200 bytes
2	Allocate 399 bytes
3	Allocate 500 bytes
4	Allocate 100 bytes
5	Allocate 63 bytes
6	Allocate 75 bytes
4	Deallocate
5	Deallocate

Initially all our free lists are empty except for the one for blocks of size 1024 bytes, which has a single entry for the region starting at address 0.

The first request (ID 1, allocate 200 bytes, which is rounded up to 256 bytes) causes us to look first in the free list for 256 bytes (which is empty), then in the free list for 512 bytes (which is also empty), and finally the free list for 1024 bytes. This list has one entry for the free block at address 0. That entry is removed from the 1024-byte free list. Since it is larger than needed, it is split into two entries of size 512 (one at address 0 and one at address 512). The entry for address

512 is placed on the free list for size 512, and the one at address 0 is split again to give two free blocks of size 256, one at address 0 and one at address 256. The block at address 256 is added to the free list for size 256, and the one with address 0 is used to satisfy the current request.

The second request (ID 2, allocate 399 bytes, rounded up to 512) is easily satisfied, since there is a single block of size 512 available. After that request is satisfied, a single free block, of size 256, at address 256, remains.

The third request (ID 3, allocate 500 bytes, rounded up to 512) cannot be satisfied because there are no blocks on the free lists for 512 bytes and 1024 bytes. The request is therefore placed on the deferred list, and will be considered again after a deallocation.

The fourth request (ID 4, allocate 100 bytes, rounded up to 128) can be satisfied after the free block of 256 bytes at address 256 is split into two 128 byte blocks. The 128 byte block at address

256 is used to satisfy the request, and the other 128 byte block at address 384, is placed on the free list for 128 byte blocks.

The fifth request (ID 5, allocate 63 bytes, rounded up to 128, the minimum) is satisfied using the last free block in the system, at address 384.

The sixth request (ID 6, allocate 75 bytes, rounded up to 128) cannot be satisfied immediately, so it is deferred, and placed after the first deferred request on the deferred list.

The seventh request (ID 4, deallocate) indicates that the 128 byte block at address 256 is to be freed. Since its buddy (at address 384) is not free, the free block is placed on the 128 byte free list. Since there are deferred requests, we consider each of them in order. The first such deferred request (for 512 bytes) still cannot be satisfied, so it remains on the list. The second deferred request (for 128 bytes) can be satisfied using the single free block at address 256. We now have no free blocks, and one deferred request remains.

The eighth and final request (ID 5, deallocate) frees the 128 byte block at address 384. Its buddy, at address 256, is not free, so were done after placing the free block on the free list for 128 byte entries.

The example given here and the additional example given later have all of the allocation requests first, followed by deallocation requests. This will not necessarily be the case in real data. You are certainly encouraged to use these to test your program, but you should also prepare additional test cases. Developing suitable test data is an essential part of any development activity.

Input Data

The input data will be read from the standard input.

The first line of the input will contain two unsigned integers. The first of these, MSIZE, will indicate the total amount of memory available for allocation. The second integer, ASIZE, will indicate the size of the smallest block that can be used to satisfy a request. Each of these will be a power of 2, and ASIZE MSIZE < 232 .

Each remaining line will contain an allocation or deallocation request. Each request will begin with a positive integer ID, some whitespace (that is, blanks and/or tabs), and a '+' or '-'. '+' is used for an allocation request, and '' is used for a deallocation request. An allocation request will have the positive integer size of the allocation request specified after the '+' (separated by additional whitespace).

The end of the input is indicated by the end of file.

You may assume that all input is syntactically and semantically correct.

Details and Limits

You will need one free list for each power of 2 between (and including) ASIZE and MSIZE, a list to keep track of deferred allocation requests, and some way of recording information (ID, address, and size) for allocations that have been made but have not yet been deallocated.

No two allocation requests will ever have the same ID, but each deallocation request must contain the IDof a previously successful allocation. The input data used to test your solution will never attempt to deallocate an allocation that is currently deferred, but your solution should detect this case (if it should exist), since that would indicate either an error in the input data or, more troubling, an error in your solution! Although the IDs used in the earlier example were sequential, this need not be the case in actual test data.

After reading each request, your program should display a line that indicates the request that is being processed; they should be similar to one of these:

Request ID 52: allocate 73 bytes. Request ID 35: deallocate.

Each line for an allocation request should be immediately followed by another line containing

Success; addr = 0x00001000.

or

Request deferred.

as appropriate. Note that the address in the Success message should be the address at which the region allocated for the request begins. Also make certain that you always satisfy each allocation request with the free region that has the smallest address. (It will likely be appropriate to maintain the free lists in ascending address order to make this requirement easier to satsify.)

After each deallocation request you should display a line that says

Success.

Additionally, for each deferred request that can be successfully accommodated as a result of a deallocation, display a line that says

Deferred request with ID 59 allocated; addr = 0x00001800.

Of course, the IDs and address values in each of these are just an examples. But do note that the addresses in the output should be displayed as 8-digit hexadecimal numbers preceded by 0x (that is, they should be C/C++/Java-style hexadecimal constants).

Keep in mind that the addresses used in the program for free blocks and allocations are not real memory addresses they are simulated memory addresses. Your program should not be doing dynamic memory allocation for blocks of the sizes used in the progam.

Sample Input and Output

You may also supply the option v on the command line to produce considerable additional

output. After each input request has been completed, the program will display the status of all requests, the contents of the free lists, and the list of deferred requests. For deallocation, the calculation of buddy addresses and the joining of blocks on various free lists will be displayed.

The first sample is the input used the earlier discussion

Heres what it looks like:

1024 128

1 + 200

2 + 399

3 + 500

4 + 100

5 + 63

6 + 75

4 -

5

The expected output for this input is as follows:

Request ID 1: allocate 200 bytes.

Success; addr = 0x00000000. Request ID 2: allocate 399 bytes. Success; addr = 0x00000200.

Request ID 3: allocate 500 bytes.

Request deferred.

Request ID 4: allocate 100 bytes.

Success; addr = 0x00000100. Request ID 5: allocate 63 bytes.

Success; addr = 0x00000180. Request ID 6: allocate 75 bytes.

Request deferred. Request ID 4: deallocate.

Success.

Deferred request 6 allocated; addr = 0x00000100

Request ID 5: deallocate.

Success.

The second sample is somewhat more ambitious, and is found in the file prog3.input2 on

Loki. Heres what it contains:

4096 256

1 + 500

2 + 250

3 + 100

4 + 1025

5 + 390

6 + 200

7 + 1

8 + 1200

9 + 200

10 + 2000

11 + 2000

4 -

3 -

2 -

1 -

9 -

7 -

5 -

6 -

8 -

10 -

11 -

And here is the expected output:

Request ID 1: allocate 500 bytes.

Success; addr = 0x00000000. Request ID 2: allocate 250 bytes. Success; addr = 0x00000200. Request ID 3: allocate 100 bytes. Success; addr = 0x00000300.

Request ID 4: allocate 1025 bytes.

Success; addr = 0x00000800. Request ID 5: allocate 390 bytes. Success; addr = 0x00000400. Request ID 6: allocate 200 bytes. Success; addr = 0x00000600.

Request ID 7: allocate 1 byte.

Success; addr = 0x00000700. Request ID 8: allocate 1200 bytes.

Request deferred.

Request ID 9: allocate 200 bytes.

Request deferred.

Request ID 10: allocate 2000 bytes.

Request deferred.

Request ID 11: allocate 2000 bytes.

Request deferred. Request ID 4: deallocate.

Success.

Deferred request 8 allocated; addr = 0x00000800

Request ID 3: deallocate.

Success.

Deferred request 9 allocated; addr = 0x00000300

Request ID 2: deallocate.

Success.

Request ID 1: deallocate.

Success.

Request ID 9: deallocate.

Success.

Request ID 7: deallocate.

Success.

Request ID 5: deallocate.

Success.

Request ID 6: deallocate.

Success.

Deferred request 10 allocated; addr = 0x00000000

Request ID 8: deallocate.

Success.

Deferred request 11 allocated; addr = 0x00000800

Request ID 10: deallocate.

Success.

Request ID 11: deallocate.

Success.

Three additional test cases, appropriately named, are also provided. The expected output for each test case can be obtained using the instructors solution. Additional test cases may be provided in the future. If so, theyll be announced on the class web page, and will be given names similar to the samples already provided.

Requirements

You must write (and test) a C, C++, or Java program that performs the tasks associated with the buddy system memory management system to perform the requests specifined in the input format described earlier. You should ideally have a single file of source code.