Storage management can be handled with a circular doubly-linked list of available space. Each node in the list consists of four fields: a starting address, a size, and two links to the adjacent nodes. The memory being managed is not part of the nodes; it is separate. The list has a header node with starting address and size fields set to zero. Initially, the available list looks like this
Write a PL6 program that uses this data structure to manage memory. Requests for allocation and blocks being freed are contained in file STORE310.COMPSCI. They are in the following form:
Columns 1-6 Job id Columns 8-12 # of words (right justified)
If the number of words is greater than zero, the entry is a freed block. If it is less than zero, it is a request.
Your program should do the following things:
1. Maintain the nodes in the available list in ascending order by starting address.
2. Allocate one memory block for each request. Use a first fit algorithm.
3. If a request can't be satisfied, print a message.
4. Return freed blocks to their proper place and coalesce blocks when possible.
5. Don't allow any node on the available list to get smaller than 200 words.
6. Print a status report for each requested and freed block. For example:
Job Id Requested Returned Address NDJ043 2600 7400 NYB047 4100 3300 NYB064 1300 2000 NDJ043 2600 7400 NDJ116 3000 Cannot be satisfied NDJ123 900 1100 NDJ123 900 1100 NYB047 4100 3300 NYB064 1300 2000
Hints:
1. How many nodes are required at most? There are 10000 words of storage and each node represents at least 200 words.
2. You can use relative pointers for links instead of PL6 pointers, if you want.