Due 2020/04/30 end of day
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.
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 extension 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 implementations should be detailed in your
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
||Releases the memory held by a process
||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
||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
||Locates the starting address and size allocated by the process labeled
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.
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.
# 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
$ 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)
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 | email@example.com, Helped me understand calculations Dorothy Vaughan | firstname.lastname@example.org, Helped me with multiplexed time management Stackoverflow | https://example | helped me with a compilation but
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 repository GitHub called
liuyunl777 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 a second version before the 24 hour deadline, use the tag
If you would like to submit an updated version of your code before the first deadline, you can select
Your submission/release is due on Monday, April 30th at the end of the day. 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.
|Each command works correctly||85%|
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.
Back to projects