C语言代写 | 操作系统OS | Memory Allocation


CSE 473 Project 2: Memory Allocation

Please direct all your project‑related questions/clarifications to the TAs, either in person or by email.


In this project, you will learn about Memory management. This project requires you to implement two memory allocation/de­allocation schemes, specifically Buddy System and Slab Allocation. The functioning  of each of these schemes has been discussed in class. One of the jobs of the memory management subsystem is to service memory requests by matching the size of the request with a large enough hole, from which to satisfy the request. You will be given the starting address from where memory is to be allocated ( start_of_memory pointer) together with the size of this memory region ( mem_size = 1 MB).


To implement the allocation policies, you should implement the following three interfaces in a file called

my_memory.c , whose semantics are described below.

void setup(int malloc_type, int mem_size, void* start_of_memory);

The purpose of setup() is to perform any initialization of variables that you may need, specify and give you the pointer ( start_of_memory) to the total amount of memory at your disposal, and also specify the type of memory allocator.

The parameter will be either 0 or 1, denoting 0­Buddy System and 1­Slab Allocation.

This function should allocate size bytes of memory from that 1MB chunk of memory that is available for     you (using the start_of_memory pointer) using the specified allocation algorithm. On allocation, it returns a pointer to the start of allocated memory. If a request cannot be accommodated by the scheme, this function should return ­1. Note that the user programs expect that all the pointed to by the returned pointer, is available to it.

This function deallocates the memory segment being passed by the pointer. Note that when free­ing, the resulting free segment should be merged with relevant neighboring holes (as per the algorithm/scheme) whenever possible to create holes of larger size. No size argument is being explicitly passed in this call.

test[x].c will call these interface functions that you will write, and test their working. Even though a few such test files will be made available, you should more extensively stress­test your code with more such test   cases that you can write yourself. In the final evaluation, several other test inputs may be used to verify the correctness of your implementation.

Implementation directions

The size parameter is given only in my_malloc and not in my_free. However, it is necessary to know the size of what is being freed. This should be handled by using the first 4 bytes of the allocated segment to contain  the size. However, programs would assume that all the space, starting from the first byte of the returned pointer, is available to be used. Hence, you should ensure that the pointer that my_malloc() returns points to the byte immediately after these 4 bytes (header) containing the size.

Buddy Allocator

The minimum chunk of memory that the Buddy System can allocate is 1KB.

Maintain the free (holes) list sorted by increasing addresses individually for different sizes (of powers of

2) as discussed in class.

Whenever there is a choice of multiple holes that a scheme allows, always pick the hole with the lowest starting address.

The 4 byte header is used to maintain the size of the allocated chunk within the chunk itself..

Slab Allocator

The Slab size is fixed at N_OBJS_PER_SLAB which is defined in memory.c. Note that each slab will only contain the objects of the appropriate type/size. However the size of the allocated object itself should be accounted to include its 4 byte header. Hence, when using this scheme for allocating an

object, there will be a 4 byte header for the object, and additionally a 4 byte header in the slab itself (where this object resides) which is allocated using Buddy.

The Slab Descriptor Table itself is maintained as a separate data structure (you can use the system malloc for allocating it). Please use the data structure explained in class for the Slab Descriptor Table.

What to turn in:

  1. c (and if needed, its header file), containing the above three interface functions which implement all 2 allocation schemes.
  2. A report to clarify the assumptions, design choices, the reasons that you made such decisions, and breakdown of the contribution of each member to the project. Also remember to include any special instructions for testing your

The project source code and report are due before 11:59 through Github. You need to set up an appointment with the TA  to demonstrate your implementation and answer a range of questions related to the entire    project (even though an individual may have worked on only one part). Academic dishonesty of any kind will not be tolerated.

Additional Information, PLEASE READ CAREFULLY!!!

  1. The inputs and sample outputs are given just for illustrative purposes to test your code. You can create more extensive input files for further
  2. The TAs WILL surprise you with several other test inputs during the demo and your routines should still work.
  3. Please stay tuned constantly to the canvas page for the exact and latest interface functions you need to implement, their arguments, test programs, examples, documentation/manuals and
  4. You can work in teams (at most 2 per team ­ they could be across sections), or individually, for the project. You are free to choose your partner but if either of you choose to drop out of your team for any reason at any time, each of you will be individually responsible for implementing and demonstrating the entire project and writing the project report by the designated deadline. If you have difficulty finding a partner, give your name to the TAs who will maintain an online list of students without partners to pair you up. Please let the TAs know who you are working with right
  5. Even though you will work in pairs, each of you should be fully familiar with the entire code and be prepared to answer a range of questions related to the entire project. It will be a good idea to work together at least during the initial design of the code. You should also ensure that there is a fair division of labor between the
  6. All the code­bases will be tested on the W­204 Linux Lab machines located on the second floor of Westgate. Ensure you test and run them in that

Input File Format (you do not need this unless you are creating extra input files yourself)

The test program will take an input file and perform the required activities. We will provide code to parse the input file and invoke the appropriate functions that you have to implement.

Each line in the input file specifies the operation which is either (i) one or more allocation requests or (ii) a free request. Each line is structured as below:

Name NoOPS/Index Type Size

 Below is the meaning of each item:

Name: Name (specified as a single alphabetic character) of the chunk(s) of memory that is to be allocated

NoOPS/Index: In case of allocation request (which is determined by Type, see below) NoOPS indicates the number of allocation requests for specified Size. In case of free request (which is determined by  Type, see below) it indicates the index of the corresponding Name to be freed.

Type: Indicates the type of operation which can be either “M” for my_malloc (allocation) or “F” for free. Size: If the operation type is “M” it indicates the size of request to be allocated and if the operation type   is “F” this field is not used.

For example a line such as: A 10 M 1024

Indicates 10 allocation requests each requesting 1024 bytes of memory is to be made. The corresponding names of these 1024 byte chunks will be referred to as A1, A2, … A10 And a line such as: Indicates a request to Free the chunk whose name is A3.

With this syntax, you can create your own test sequences intermixing allocations/frees to debug your code. You can also post these test sequences, if you would like, on the google groups page to benefit others who can test their code with the same input files (please note that your are NOT allowed to share C code).



本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: [email protected]  微信:dmxyzl003