联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Python编程Python编程

日期:2020-11-18 11:35

Assignment 2: Allocator

For this assignment you will implement your own heap allocator similar to ptmalloc2, jemalloc,

tcmalloc, and many others. These allocators are the underlying code of malloc. Heap allocators

request chunks of memory from the operating system and place several (small) object inside these. Using

the free call these memory objects can be freed up again, allowing for reuse by future malloc calls.

Important performance considerations of a heap allocator include being fast, but also to reduce memory

fragmentation.

Your allocator must implement its own malloc, free and realloc functions, and may not use the

standard library versions of these functions. Your allocator may only use the brk(2) and sbrk(2)

functions, which ask the kernel for more heap space. 1

Description of the functions to implement

You should implement mymalloc, mycalloc, myfree, and myrealloc as described in the Linux man

pages. 2

These functions should behave exactly as specified by their man-page description, although you

can ignore their Notes section as these are implementation-specific. Your allocations (i.e., the pointer

returned by mymalloc) should be aligned to sizeof(long) bytes.

Your allocator may not place any restrictions on the maximum amount of memory supported or the

maximum number of objects allocated. For example, your allocator should scale regardless of whether the

maximum brk size is 64KB or 1TB.

Grading

This assignment is individual; you are not allowed to work in teams. Submissions should be made to the

submission system before the deadline. Multiple submissions are encouraged to evaluate your

submission on our system. Our system may differ from your local system (e.g., compiler version); points

are only given for features that work on our system.

Your grade will be 1 if you did not submit your work on time, has an invalid format, or has errors during

compilation.

If your submission is valid (on time, in correct format and compiles), your grade starts from 0, and the

following tests determine your grade (in no particular order):

? +1.0pt if your make a valid submission that compiles.

? +1.0pt if your malloc returns a valid pointer to a new heap object. Required

? +0.5pt if your calloc returns a valid new heap pointer to zero-initialized memory.

? +2.0pt if a region of memory can be reused after freeing it with free. Required

? +1.0pt if realloc behaves as described on its man-page and only allocates a new object when

needed.

? +1.0pt if your allocator batches brk calls, i.e., it does not need to request memory from the kernel for

every allocation.

? +2.0pt if your amortized overhead per allocation is on average 8 bytes or less.

? +0.5pt if your allocator tries to optimize for locality (reuse recently freed memory).

? +1.0pt if your allocator gives back memory to the kernel (using brk) when a large portion of the

allocated memory has been freed up.

? +1.0pt if your design does not use in-band metadata.

? +2.0pt if your allocation functions work correctly without the my prefix too (see Notes below).

? -2.0pt if your allocator cannot scale with the maximum brk size.

? -1.0pt if gcc -Wall -Wextra reports warnings when compiling your code.

? -1.0pt if your source files are not neatly indented or formatted.

If you do not implement an item marked with Required you cannot obtain any further points. This means

you need to implement at least a simple allocator that can do malloc and free with reuse.

The grade will be maximized at 10, so you do not need to implement all features to get a top grade. Some

features might be mutually exclusive with each other, depending on your allocator design.

Note: Your allocator will be evaluated largely automatically. This means features only get a positive grade

if they work perfectly, and there will be no half grade for "effort".

Evaluation environment

For setting up a local development environment, refer to the setup document. In short, on Linux you should

install build-essential python3 python2, on Windows you should use WSL2, and on macOS you

should use Docker.

To test your implementation, the file test_framework/tests.c contains a number of (automated) test

cases that evaluate the different aspects of your allocator. It can be invoked manually via

./test <test name>. Running make check (or make docker-check) will run all test cases, and

additionally check your work for other errors that would lead to deducted points during grading.

Additionally you should test your work on our server. Remember to try this as often as your like, as your

local environment may be different than ours. Points are only awarded based on what works on our

server. The final submission before the deadline is used for grading.

Attempts to exploit, bypass or cheat the infrastructure and automated grading system will result in a 1 for

this assignment.

Notes

? While you can edit the test framework locally to debug issues, you should not modify alloc.h or any

file in test_framework/. During submission and grading any modifications made to these files will

be thrown away.

? If you add definitions for malloc etc. to your alloc.c, you should also keep the original set of my

functions for grading. Sample code that makes enables these functions is included in the skeleton

alloc.c.

? If you have added support for replacing the system allocator (i.e., by adding non my prefixed

functions) you can use your allocator for any existing program on your system. You can do this by

prefixing any command with LD_PRELOAD=/path/to/libmyalloc.so. For example,

LD_PRELOAD=./libmyalloc.so ls will run ls with your allocator.

? Calling your functions malloc instead of mymalloc not only redirects all calls inside your code to

your malloc, but will also cause all internal libc calls to go to your allocator instead of the built-in libc

malloc. Many libc functions, such as printf, internally make calls to malloc, and as such using

printf inside your allocation code would cause an infinite loop. Therefore we prefix our allocator

functions with my in this assignment.

1 Normal heap allocators may also use mmap to request memory from the kernel. For

this assignment you should only use brk (or sbrk).

2 https://linux.die.net/man/3/malloc


版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp