In this assignment, we are simulating memory management. When a process is loaded into memory or a process requests a block of memory dynamically, the system must allocate memory, and when a process terminates or frees memory previously requested, the system must deallocate memory.

For the sake of this assignment, we will assume we have a small computer with only 16 MB of memory. We will assume that the operating system uses the first 3 MB, leaving 13 MB for applications. Starting at that point, we will process several kinds of transactions:

--- Load a process into memory

--- Allocate a block of memory dynamically

--- Deallocate a block obtained earlier

--- Terminate a process, freeing all its memory

From time to time, we will print out the contents of the data

structures involved.

--- Define a class or struct to represent one block of memory. It should include the starting address (an integer), the size (an integer), the process ID of the owner (a string, might be blank) and the ID of the block (a string, might be blank), as well as one or two pointers to blocks.

--- Use #define to create a constant which I shall call HOWOFTEN. Give it the value 5.

--- Create two linked lists of blocks. One list contains blocks that are presently in use, and the other contains blocks that are not presently in use. I shall refer to these as InUse and Avail, respectively.

--- Initialize InUse to be empty. --- Initialize Avail to consist of one 1 MB block, two 2MB blocks and two 4 MB blocks, in that order. The starting address for the first block should be at 3*1024*1024. (Again, we are assuming the operating system uses the first 3 megabytes of memory.)

--- Before any transactions, print the contents of both lists.

--- Open and read the input file and carry out the transactions.

--- Every HOWOFTEN transactions, reprint the contents of both lists.

--- After all transactions, reprint the contents of both lists.

The program will take one command-line argument. The value should be either "B" or "F". If the value is "B", the program should use the Best-Fit algorithm for allocation, and if the value is "F", the program should use the First-Fit algorithm. If the argument is missing or the value is anything else, print an appropriate error message and exit with a negative exit value.

At the top of the output, print a heading saying this is a memory-management simulation and which allocation algorithm is in use. Notice that the Avail list will be different from time to time. It will not always have the same five blocks. We will arbitrarily assume memory requests are restricted to a range of 4 KB to 4 MB. Blocks of memory are limited to 4 MB. You may find it useful to have defined constants KB and MB for the numbers 1024 and 1024*1024. When you print a list, include a line giving the total size of each list. (The sum of the two should always be the same: 13*1024*1024. Never lose a byte.) Notice that the Avail list is maintained in order by Starting Address (increasing). Order is not important for the InUse list.

Each line in the file represents one transaction. Each line begins with 1 letter, followed by other items:

L: Load a process. This is followed by its ID, size and block ID (which in this case is the program name).

A: Allocate memory. This is followed by the process ID, size and an ID for this block of memory.

D: Deallocate memory. This is followed by the process ID and the ID of the block.

T: Terminate a process: This is followed by the process ID.

The last line in the file starts with '?' as a delimiter.

Load transaction

Search the Avail list for the best-fit or first-fit block.

if there is no sufficiently large block

print an error message

Else

Create a new block of the correct size, recording the process

ID and the block ID

Decrease the block found on Avail by that amount

If the block on Avail is now of size 0

Delete it

End-If

Insert the new block at the beginning of InUse

Print a success message

End-If.

Allocate transaction

Search the Avail list for the best-fit or first-fit block.

If there is no sufficiently large block

print an error message

Else

Create a new block of the correct size, recording the process

ID and the Block ID

Decrease the block found on Avail by that amount

If the block on Avail is now of size 0

Delete it

End-If

Insert the new block at the beginning of InUse

Print a success message

End-If.

Deallocate transaction

Search the InUse list for the block with the correct process ID

and block ID. (The combination of the two should be unique.)

If it is not found

Print an error message

Else

Detach the block from InUse

Insert it into Avail in order by starting address

Traverse the Avail list combining any two consecutive blocks

for which the ending address of the first block is the starting

address of the second block, provided the combined block is no

more than 4 MB

Print a success message

End-If.

Terminate transaction

Search the InUse list as often as necessary to find and deallocate all blocks belonging to the indicated process.

If there are none

Print an error message

Else

Print a success message (there is no need to announce each and

every block that is deallocated in a Terminate transaction)

End-If.