CS 3113 FA 21 Project 2 – Memory Allocation

In this project, you will simulate four memory allocation algorithms. You have flexibility in how you implement the actual memory allocation. You must use C. Before starting, design your solution into small testable parts. It is not necessary to perform any actual memory allocation but, your code should keep a record of the free and allocated spaces in a memory structure.

Algorithms

You should implement the four memory allocation algorithms from Chapter 9 of the Operating Systems Concept Textbook: (1) First Fit; (2) Best Fit; (3) Worst Fit; and (4) Next Fit. Use the Contiguous Memory Allocation section in Chapter 9.2.2, pages 358, of Operating Systems textbook and your lecture notes as a reference. The first three methods are discussed in the text, and the fourth is an additional method not discussed in this textbook.

To implement memory allocation, you have the freedom to choose a method you believe is best. The naive method of implementing methods (1) - (3) is to allocate large arrays for the code and label the contents of each array. The books describes a variable partitioning approach where the OS keeps a table indicating which parts of memory are available. The description of your implementation should be detailed in your README document.

Each algorithm will be given a starting memory allocation size. The allocation size will be \(2^k\) bytes, where \(k\) is an integer between 4 and 30.

Your code should be implemented in C. If you decide to use any external packages, you must clear it with the TA. You should also supply a README file that will serve as your manual. The command make all should create an executable called project2. The first parameter is a string of the algorithm that should be used. The options are BESTFIT, FIRSTFIT, NEXTFIT, and WORSTFIT. The second parameter is the total memory allocation N. All algorithms have a script file name as the last parameter.

Below are four example invocations of the project 2 executable where N is the total memory allocation and the strings “ex75.txt” and “ex76.txt” are script files derived from examples in the book. Note, only one allocation and algorithm can be chosen for each execution of code. Be sure to free all memory prior to exiting the program.

./project2 BESTFIT N ex75.txt
./project2 FIRSTFIT N ex75.txt
./project2 NEXTFIT N ex75.txt
./project2 WORSTFIT N ex76.txt

Commands

Command	Description
`REQUEST A n`	Allocates `n` bytes for a process named `A`. On successful allocation, print `ALLOCATED A x`, where `A` is the name of the allocated process and `x` is the relative location of the allocated memory. On error, print `FAIL REQUEST A n`.
`RELEASE A`	Releases the memory held by a process `A`. On success, print `FREE A n x` where `n` is the amount of reclaimed memory and `x` is the starting relative address of the released memory. On error, print `FAIL RELEASE A`.
`LIST AVAILABLE`	Prints location information for all available memory. Prints a list of space separated pairs of “\((n_1, x_1)\) \((n_2, x_2)\) \(…\)”, where \(n_i\) is the amount memory available and \(x_i\) is the starting location. If there are no available blocks you should print `FULL`.
`LIST ASSIGNED`	Returns a list of space separated triples including of the form “\((A_1, n_1, x_1)\) \((A_2, n_2, x_2)\) \(…\)”, where \(A_i\) represents process labels, \(n_i\) represents the number of allocated bytes for that process, and \(x_i\) is the relative starting address of the process. If there are no allocated blocks, this should print `NONE`.
`FIND A`	Locates the starting address and size allocated by the process labeled `A`. If successful, this command returns a tuple \((A, n, x)\), where \(n\) is the amount allocated by `A` and `x` is the relative starting address of the process labeled `A`. If unsuccessful, the program should print `FAULT`.

Process labels may be strings with a max length of 16 characters, containing only upper and/or lowercase characters and no spaces. All memory locations should be considered relative to the start of the free memory block. The addresses and memory sizes should be represented as long, unsigned integers. And memory sizes should always be represented as bytes.

All print commands should go to stdout. The program should reject fractional allocations. The minimum grantable request size is 1 byte. A request could be of any size. A page cannot be placed at the end and the beginning of the memory allocation. If an allocation was made at the end of the memory allocation, the next fit pointer should go to the beginning address in memory. If an allocation cannot be placed across the space before the end of the allocation, it cannot be placed in that location.

Corner cases

If memory is full, the Next fit pointer should reset to the lowest addressable memory space.
When running bestfit and worstfit algorithm, if multiple memory locations have the same “winning” size, choose the lowest open space as the winner.
When implementing the nextfit pointer, if a space becomes free immediately behind the current nextfit pointer location, the nextfit pointer will not recognize the full space until it loops around to the beginning of the open space.

Script File

The script file is a text file with a series of commands as defined above. Your code should read each line of the text file and execute the command. Lines prefixed with # represent comments. The program should ignore comments. Below is an example script file. The output of the script file will change depending on the algorithm and initial allocation used. The example below is an script file and a picture of an example with extra commands added in between to view the progress of the script.

Script below:

# Add the permanent OS position 
REQUEST OS 8388608
LIST AVAILABLE
# Check to see if A was added
REQUEST P1 20971520
REQUEST P2 14680064
REQUEST P3 18874368
RELEASE P2
REQUEST P4 8388608
RELEASE P1
REQUEST P2 14680064

Next Fit Example

Example Execution

$ cat testfile.txt
# Add OS memory
REQUEST OS 8388608
LIST AVAILABLE
REQUEST P1 20971520
REQUEST P2 14680064
REQUEST P3 18874368
RELEASE P2
REQUEST P4 8388608
RELEASE P1
REQUEST P2 14680064
LIST ASSIGNED
LIST AVAILABLE
$ ./project2 BESTFIT 268435456 testfile.txt
ALLOCATED OS 0
(260046848, 8388608)
ALLOCATED P1 8388608
ALLOCATED P2 29360128
ALLOCATED P3 44040192
FREE P2 14680064 29360128
ALLOCATED P4 29360128
FREE P1 20971520 8388608
ALLOCATED P2 8388608
(OS, 8388608, 0) (P2, 14680064, 8388608) (P4, 8388608, 29360128) (P3, 18874368, 44040192)
(6291456, 23068672) (6291456, 37748736) (205520896, 62914560)
$ ./project2 NEXTFIT 268435456 testfile.txt
ALLOCATED OS 0
(260046848, 8388608)
ALLOCATED P1 8388608
ALLOCATED P2 29360128
ALLOCATED P3 44040192
FREE P2 14680064 29360128
ALLOCATED P4 62914560
FREE P1 20971520 8388608
ALLOCATED P2 71303168
(OS, 8388608, 0) (P3, 18874368, 44040192) (P4, 8388608, 62914560) (P2, 14680064, 71303168)
(35651584, 8388608) (182452224, 85983232)
$ ./project2 FIRSTFIT 268435456 testfile.txt
ALLOCATED OS 0
(260046848, 8388608)
ALLOCATED P1 8388608
ALLOCATED P2 29360128
ALLOCATED P3 44040192
FREE P2 14680064 29360128
ALLOCATED P4 29360128
FREE P1 20971520 8388608
ALLOCATED P2 8388608
(OS, 8388608, 0) (P2, 14680064, 8388608) (P4, 8388608, 29360128) (P3, 18874368, 44040192)
(6291456, 23068672) (6291456, 37748736) (205520896, 62914560)

COLLABORATORS file

This file should contain a pipe separated list describing who you worked with and a small text description describing the nature of the collaboration. This information should be listed in three fields as in the example is below:

Katherine Johnson | kj@nasa.gov | Helped me understand calculations
Dorothy Vaughan | doro@dod.gov | Helped me with multiplexed time management
Stackoverflow | https://example | helped me with a compilation but

Grading

To evaluate your code, we generate random test scripts that produce known results. We will verify that the results from your code match expected results.

Include a Makefile with the standard targets all and clean. The make all command should create an executable project2 The make clean target should remove executables and temporary files.

Create a private GitHub repository called cs3113fa21-project2. Add collaborators cegme and jmless98 by going to Settings > Manage Access. (Or Settings > Collaborators in older version of GitHub).

When ready to submit, create a tag on your repository using git tag on the latest commit:

git tag v1.0
git push origin v1.0

The version v1.0 lets us know when and what version of code you would like us to grade. If you would like to submit a second version use the tag v2.0.

Deadline

Your submission/release is due on Tuesday, November 23rd. Submission of all code should be done through Gradescope and the code should be hosted on a private GitHub repository. We will continue to follow the course late submission policy.

Task	Percent
Each command works correctly	85%
`README` file is thorough and descriptive	15%
Max Total	100%

Proper Academic Conduct

The code solution to this project must be done individually. Do not copy solutions to this problem from the network and do not look at or copy solutions from others. However, you may use the net for inspiration and you may discuss your general approach with others.

Addenda

Back to projects