程序代写|CSE 473 Project 2: Memory Allocator

这是一篇来自美国的关于存储分配器的程序代写

 

Goals

– Learn how to manage the memory (heap)

– Understand different allocation schemes

Overview

You will implement a memory allocator which supports Buddy Allocation and Slab Allocation schemes. The functioning/algorithm of each of these schemes has been discussed in class. Your memory allocator will support my_malloc() and my_free(), which is analogous to the C library’s malloc() and free(). To test your memory allocator,the program will call my_malloc() and my_free(), based on the input file. The input file has a list of memory allocation requests and memory free requests. The generated output file has the result of your allocations. Your memory allocator will allocate memory only within the given starting address and size provided in my_setup().

Hardware Model

This machine is a single CPU system. Only one thread will make requests to your memory allocator.

Allocation Policies

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 header 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 HEADER_SIZE bytes (header) containing the size.

Buddy Allocator:

The minimum chunk of memory that the Buddy System can allocate is MIN_MEM_CHUNK_SIZE bytes defined at interface.h.

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 HEADER_SIZE byte header is used to maintain the size of the allocated chunk within the chunk itself.

Slab Allocator:

The number of objects per slab is fixed at N_OBJS_PER_SLAB defined at interface.h. 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 HEADER_SIZE byte header. Hence, when using this scheme for allocating an object,there will be a HEADER_SIZE byte header for the object, and additionally a HEADER_SIZE 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 c library malloc() for allocating it). Please use the data structure explained in class for the Slab Descriptor Table.

Note that whenever you need to create a new slab, you need to call your Buddy Allocator from above to get the required slab (as discussed in class).APIs to Implement

In interface.h, the header size, the minimum memory chunk size, and the number of objects per slab (for slab allocator) is defined. You should implement the following three interfaces in a file called interface.c, whose semantics are described below.

#define MEMORY_SIZE 8 * 1024 * 1024

#define HEADER_SIZE 8

#define MIN_MEM_CHUNK_SIZE 512

#define N_OBJS_PER_SLAB 64

// Allocation type

enum malloc_type {

MALLOC_BUDDY = 0, // Buddy allocator

MALLOC_SLAB = 1, // Slab allocator

};

void my_setup(enum malloc_type 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), the total amount of memory at your disposal, and specify the type of memory allocator.

The below functions may be called multiple times, depending on the input.

void* my_malloc(int size);

This function should allocate size bytes of memory from the mem_size chunk of memory that is available for you (from the start_of_memory pointer) using the specified allocation algorithm. On successful allocation, it returns a pointer to the start of allocated memory. (The pointer returned should: start_of_memory <= return ptr <= start_of_memory+mem_size.) If a request cannot be accommodated by the scheme, this function should return

-1.

Note that the user programs expect that all the size bytes, starting from the first byte pointed to by the returned pointer, is available to it.

void my_free(void* ptr);

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.

You can implement additional functions (helper functions) and have additional variables and structures in my_memory.c/h, but note that the main.c will call only the above three functions. Also, note that there is no name  argument in my_malloc() and my_free(). The memory chunk [name] of the input file is only for the program user to interact. Your internal memory allocator only works with the size and ptr, similar to the C library’s malloc() and free().Input File Format

An input to the program is a text file which has the following format:

[name] [NumOps|Index] [Type] [Size]

[name] [NumOps|Index] [Type] [Size]

[name] [NumOps|Index] [Type] [Size]

where,

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

NumOPS/Index:

In case of allocation request (type “M”), NumOPS indicates the number of allocation requests for specified Size.

In case of free request (type “F”), it indicates the Index of the corresponding Name to be freed.

Type: Indicates the type of operation which can be either “M” for memory allocation or “F” for memory free.

Size:

If the operation type is “M”, it indicates the size of request to be allocated.

If the operation type is “F”, this field is not used (ignored).

Sample Input and Output

① Basic Case

Z 5 M 1234

A 1 M 4321

C 3 M 19

Z 1 F 0

Z 3 F 0 can be interpreted as:

– Five memory allocation (M) requests, each requesting 1234 bytes of memory. The corresponding name and index of these 1234 byte chunks will be referred as Z1, Z2, …, Z5.

– One memory allocation (M) request of 4321 bytes of memory. The corresponding name and index of this chunk will be A1.

– Three memory allocation (M) requests, each requesting 19 bytes of memory. The corresponding name and index of these 19 byte chunks will be referred as C1, C2, and C3.

– Free (F) request of the chunk named Z1.

– Free (F) request of the chunk named Z3.

Following is the MALLOC_BUDDY output of the above sample input (assuming HEADER_SIZE=8,

MIN_MEM_CHUNK_SIZE=512):

MALLOC_BUDDY

Start of first Chunk Z is: 8

Start of first Chunk Z is: 2056

Start of first Chunk Z is: 4104Start of first Chunk Z is: 6152

Start of first Chunk Z is: 8200

Start of Chunk A is: 16392

Start of Chunk C is: 10248

Start of Chunk C is: 10760

Start of Chunk C is: 11272

freed object Z at 8

freed object Z at 4104

– Since we have five allocation requests for name Z, we see five lines of output for Z. Since 1024 < 1234 < 2048,each chunk is allocated on the 0 + 8 (HEADER_SIZE), 2048 + 8, 4096 + 8, 6144 + 8, … address.

– Since we have one allocation request for name A, we see one line of output for A. Since 4096 < 4321 < 8192, the chunk is allocated on the 16384 + 8 (HEADER_SIZE) = 16392 address. Addresses lower than that can’t fulfill 4321 bytes of memory, according to the buddy allocation algorithm.

– Since we have three allocation requests for name C, we see three lines of output for C. Since 19 < 512

(MIN_MEM_CHUNK_SIZE), each chunk is allocated on the 10240 + 8 (HEADER_SIZE), 10752 + 8, 11264 + 8 address.

– Since we have a free request for chunk Z1, your memory allocator should free the chunk at address 8.

– Since we have a free request for chunk Z3, your memory allocator should free the chunk at address 4104.

* NOTE: the above explanation/algorithm is NOT how to actually allocate/free memory. The above explanation is for illustrative purposes only. See Allocation Policies below for more details.

② Same input, different output

A 1 M 250000

B 1 M 511000

C 1 M 150000

D 1 M 2000 can be interpreted as:

– One memory allocation (M) request of 250000 bytes of memory. The corresponding name and index of this chunk will be A1.

– One memory allocation (M) request of 511000 bytes of memory. The corresponding name and index of this chunk will be B1.

– One memory allocation (M) request of 150000 bytes of memory. The corresponding name and index of this chunk will be C1.

– One memory allocation (M) request of 150000 bytes of memory. The corresponding name and index of this chunk will be D1.