1

I am currently working on an assignment for my embedded systems course, and my professor has asked us to determine the memory allocation technique employed in Arduino. Specifically, I need to identify whether it utilizes best fit, quick fit, worst fit, next fit, or first fit memory allocation methods.

Despite conducting online research and seeking input from my colleagues, We have been unable to find an answer to this question.

I would greatly appreciate any insights or information on the memory allocation technique used in Arduino.

Thank you.

1

2 Answers 2

2

Use the source, Luke!

The AVR-based Arduinos rely on the avr-libc library, which provides malloc() and friends. You can read the source code online. It is generously commented, and you can understand pretty well the allocation strategy by reading the comments alone.

1

Long answer short, it used both first-fit and best-fit.

The malloc function in the avr-libc makes use of a so-called free list to track the free spaces in the memory.

When there is a memory request, it starts by looping over this list searching for the first exact match [First Fit].

While looping over the list, it keeps track of the piece of memory that will leave the least amount of space(best-fit). If it didn't find the exact match, it uses this piece of memory [Best Fit].

Furthermore, it doesn't use this piece of memory directly, it checks for its size first, if it is big enough, it takes the amount of memory needed and adds the leftover to the free list, else, it allocates the whole piece of memory.

N.B. it allocates new memory space to the heap if it doesn't find the first-fit or best-fit.


Example Scenarios:

  1. First Fit:
  • Free list: [64, 128, 128, 256, 512, 128]
  • Request: 128
  • Action: Take the first 128.
  1. Best Fit:
  • Free list: [64, 256, 512]
  • Request: 128
  • Action: Take the 256, use 128, and add the other 128 to the free list.
  1. Best Fit:
  • Free list: [64, 256, 512, 130]
  • Request: 128
  • Action: Take the 130 and use it all.

Hope things are clear now!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.