When we looked at partitioned memory management, it was implicit that the OS somehow kept track of allocated memory and free memory. Similarly, when considering that each process should have a heap, we assumed that user-software would keep track of allocations and deallocations within the heap. Even with a paged memory system, we have not got rid of the need to track allocations and deallocations: the OS itself needs to allocate certain tables, lists and other structures.
All of these applications use similar techniques to track allocated memory. We will talk about allocating blocks of memory on a heap, but this applies equally to other memory management tasks. (In some systems, the OS is responsible for managing a heap which is shared between many applications. The Macintosh and Amiga work like this.)
The following are some means of tracking allocated memory: