CS 3113 Fall 21

Logo

This is the web page for Operation Systems at the University of Oklahoma.

View the Project on GitHub oudalab/cs3113fa22

CS 3113 FA 22 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

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 cs3113fa22-project2. Add collaborators cegme, jasdehart, and farabee738 by going to Settings > Manage Access. (Or Settings > Collaborators in older version of GitHub).

When you are ready to submit, open the assignment’s submission area on Gradescope. You may make a submission by either uploading directly from your computer or linking to a GitHub repository. Gradescope will allow you to make multiple submissions, and get rapid feedback on those submissions. You will be able to choose to activate a previous submission up until the deadline.

Please make sure that you upload all of the required files.

README.md

The README file should be all uppercase with either no extension or a .md extension. You should write your name in it, an example of how to run the program, any bugs that should be expected, and a list of any web or external libraries that are used. The README file should make it clear contain a list of any bugs or assumptions made while writing the program. Note that you should not be copying code from any website not provided by the instructor. Using any code from previous semesters or students will results in an academic dishonesty violation. You should include directions on how to compile and use your code. You should describe all functions. You should describe any known bugs and cite any sources or people you used for help. Be sure to include any assumptions you make for your solution.

The README must be submitted through Gradescope along with the other files.

Deadline

Please view canvas for the due date. 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.

Examples of Integrity violation

Situation Integrity Violation?  
  Students A and B meet and work on their assignment together. Neither student prepared anything in advance and the resulting work is identical. Yes
  Students A and B create drafts of their assignment independently and get together to compare answers and discuss their understanding of the material. Each person decides independently whether to make changes that are discussed. No
  Students A and B agree to prepare drafts of their assignments independently, but only Student A does. Student A shares her draft to Student B who reviews it and offers suggestions for improvement. Yes
  Students A and B agree that student A will work the even problems and Student B will work the odd problems. They share their work. Yes
  Students A and B agree that student A will work on a read function and Student B will work the sorting function. They share their solutions. Yes
  Student A has completed a project and is helping Student B complete the same project. Student A explains to Student B what student B’s code actually does, which is different than what Student B thinks the code does. Student B determines how to modify the code independently. No
  Student A has completed a project and is helping Student B complete the same project. Student B is having trouble getting one part of the program to work, so Student A texts Student B three lines of their solution. Yes
  Student A has completed a project and is helping Student B complete the same project. Student B is having difficulty getting the program to work, so student A tells student B exactly what to type for several lines. Yes
  Student A has completed a project and is helping student B complete the same project. Student B is having difficulty getting the program to work, so Student A suggests that Student B use a specific debugging strategy (e.g. “Print out the contents of the variable”). No
  Student A has completed a project and is helping Student B complete the same project. Student A shows Student B an example program in the online textbook that will be helpful in figuring out the solution to the problem. No
  Student A publishes solutions to an assignment on a public Internet page. Yes
  Students A and B work on a project together. After they have finished it, student A takes the code and modifies it so the programs do not appear to be identical. Yes
  Student A copy and pastes code from a public Internet page but changes the variable names. Yes

Addenda


Back to projects