Allocation Architecture Idea 1: Linked Lists
Before each block, the status information about its size and usage (free/occupied) are stored.
As you can see, information about PCB for Process 0 is saved before Process 0’s block.
After a number of allocations and deallocations, our memory turns into a wasteful design consisting of free and occupied blocks like this:
And this type of result is called “fragmentation”.
- External Fragmentation: Free blocks, that are too small for any usage
- Internal Fragmentation: Blocks are divided in factors of constant numbers, for example 4 or 8 Bytes. Because of that, If you store a 9 byte data in 8 Byte system, you have to allocate 8 Bytes more for the remaining single 1 Byte. This is called internal fragmentation.