Department of Computer Science University of San FranciscoComputer Science 245Programming Assignment 2Spring 20051 IntroductionRecall that the heap is the memory used by the system to service requests for memory made bythe new operation in Java. Also recall that memory that has been allocated from the heap thatis no longer being used by the program is periodically returned to the heap by the Java garbagecollector. In languages such as C and C++ memory allocated from the heap that is no longer inuse should be explicitly returned to the heap by the program. In programming assignment 2 we’lllook at how one might write software for explicitly allo c ating and deallocating from the heap.One approach involves the use of a linked list that’s stored in the heap: each available block ofcontiguous memory stores two pieces of information: its size and the address of the next availableblock of memory. If the address of the first block is also stored, then the sequence of availableblocks forms a linked list.For example, suppose the heap consists of 16 memory locations, and addresses 2, 3, 6, 7, and10–15 are free. Then, together with the address 2 — the address of the first free block — our“linked list” might look something like this:Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents X X 6 2 X X 10 2 X X -1 6In this diagram, memory that has been allocated (addresses 0, 1, 4, 5, 8, and 9) is marked with an‘X’, and the first two addresses in each free block store the address of the next free location andthe size of the free block, respectively. So address 2 stores 6, since address 6 is the beginning ofthe next free block, and address 3 stores 2 since the first free block has 2 elements. Note that thefirst location in the last free block (location 10) stores a -1. In our examples we’re using this valueto indicate that there are no more blocks of free storage.When a program makes a request for memory, the system can traverse the linked list of freeblocks until it finds one that’s big enough to satisfy the new request. In our example, if a requestis made for 4 locations, the memory management software would start with the first free block(address 2), see that it only has 2 locations available, continue to the block starting at address 6,see that it also only has 2 locations available, and, finally, see that the block starting at address 10with 6 locations is big enough to satisfy the request.In order to satisfy the request, the system simply reduces the size of the block starting atlocation 10 by four and returns the address 12:Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents X X 6 2 X X 10 2 X X -1 2 X X X XNotice that in our example we’re allocating memory from the end of the block.Things get more complicated if a request is made for an entire block. For example, if a programrequests 2 locations, the e ntire block starting in location 2 can be used, and the address of the firstfree block will have to be changed to 6:1Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents X X X X X X 10 2 X X -1 2 X X X XIn general, if an entire block is requested, the address stored in the preceding free block willhave to be changed. For example, suppose the heap looks like this (e.g., addresses 4–5 and 0–1have been freed):Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents 4 2 X X 10 4 X X -1 2 X X X XIf a request is now made for a block of size 4, the entire block starting at address 4 will be allocated,and the address stored in 0 will have to be changed to 10:Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents 10 2 X X X X X X X X -1 2 X X X XWhen m emory is freed, a new block is “inserted” into the linked list. For example, if a block ofsize 2 starting at address 6 is freed, then the updated memory should look like this:Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents 6 2 X X X X 10 2 X X -1 2 X X X XNotice that the address stored in the free block at 0, the immediately preceding block, is updatedto reference the new block, and the address in the newly freed block is the old address stored inthe immediately preceding block at address 0.In general, when a block is freed, simply “inserting” it in the linked list won’t be enough. Forexample, if a block of size 2 starting at address 4 is now freed, and s imply inserted into the list,we’ll have the following layout:Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents 4 2 X X 6 2 10 2 X X -1 2 X X X XThe problem here is that all the blocks have size 2, and a request for a block of size 4 will be(incorrectly) refused. So after a freed block is inserted into the list, the system should see if it canbe merged with the following or preceding blocks (or both). In our example, a correct freeing ofthe block at address 4 will continue by merging the block at 4 and the block at 6:Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents 4 2 X X 10 4 X X -1 2 X X X XIf we free a block of siz e 2 at address 12, we should first create a new block:Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents 4 2 X X 10 4 X X 10 2 -1 2 X Xand then m erge the block at 10 and the block at 12:Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents 4 2 X X 10 4 X X -1 4 X XFinally, if we free the block of size 2 at address 2, we should first insert the new block:Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents 2 2 4 2 10 4 X X -1 4 X X2then merge it with the block at address 4:Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents 2 2 10 6 X X -1 4 X Xand finally merge it with the block at address 0:Address 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Contents 10 8 X X -1 4 X X2 The AssignmentFor programming assignment 2, you should write a program that implements the “me mory manage-ment” …