Introduction: Heap used for dynamically allocated memory, its important operations includes allocation and de-allocation. In C , Pascal, and Java allocation is done via the “new” operator and C allocation is done via the “malloc” function call. De-allocation is done either automatically. The heap is the portion of the store that is used for data that lives indefinitely, or until the program explicitly deletes it.
While local variables typically become inaccessible when their procedures end, many languages enable us to create objects or other data whose existence is not tied to the procedure activation that creates them. For example, both C and Java give the programmer new to create objects that may be passed — or pointers to them may be passed — from procedure to procedure, so they continue to exist long after the procedure that created them is gone. Such objects are stored on a heap.
Heap Memory Manager: The memory manager keeps track of all the free space in heap storage at all times. It performs two basic functions:
- Allocation. When a program requests memory for a variable or object,3 the memory manager produces a chunk of contiguous heap memory of the requested size. If possible, it satisfies an allocation request using free space in the heap; if no chunk of the needed size is available, it seeks to increase the heap storage space by getting consecutive bytes of virtual memory from the operating system. If space is exhausted, the memory manager passes that information back to the application program.
- De-allocation. The memory manager returns de-allocated space to the pool of free space, so it can reuse the space to satisfy other allocation requests.
Memory managers typically do not return memory to the operating system, even if the program's heap usage drops. Memory management would be simpler if (a) all allocation requests were for chunks of the same size, and (b) storage were released predictably, say, first-allocated first-de-allocated. There are some languages, such as Lisp, for which condition (a) holds; pure Lisp uses only one data element — a two pointer cell — from which all data structures are built. Condition (b) also holds in some situations, the most common being data that can be allocated on the run-time stack. However, in most languages, neither (a) nor (b) holds in general. Rather, data elements of different sizes are allocated, and there is no good way to predict the lifetimes of all allocated objects.
Thus, the memory manager must be prepared to service, in any order, allocation and de-allocation requests of any size, ranging from one byte to as large as the program's entire address space.
Here are the properties we desire of memory managers:
- Space Efficiency. A memory manager should minimize the total heap space needed by a program. Doing so allows larger programs to run in a fixed virtual address space. Space efficiency is achieved by minimizing "fragmentation," discussed in Section 7.4.4.
- Program Efficiency. A memory manager should make good use of the memory subsystem to allow programs to run faster. As the time taken to execute an instruction can vary widely depending on where objects are placed in memory. Fortunately, programs tend to exhibit "locality," which refers to the nonrandom clustered way in which typical programs access memory. By attention to the placement of objects in memory, the memory manager can make better use of space and, hopefully, make the program run faster.
- Low Overhead. Because memory allocations and de-allocations are frequent operations in many programs, it is important that these operations be as efficient as possible. That is, we wish to minimize the overhead — the fraction of execution time spent performing allocation and de-allocation. Notice that the cost of allocations is dominated by small requests; the overhead of managing large objects is less important, because it usually can be amortized over a larger amount of computation.
The Memory Hierarchy of a Computer: Memory management and compiler optimization must be done with an awarenessof how memory behaves. Modern machines are designed so that programmerscan write correct programs without concerning themselves with the detailsof the memory subsystem. However, the efficiency of a program is determinednot just by the number of instructions executed, but also by how long it takesto execute each of these instructions. The time taken to execute an instructioncan vary significantly, since the time taken to access different parts of memorycan vary from nanoseconds to milliseconds. Data-intensive programs can thereforebenefit significantly from optimizations that make good use of the memorysubsystem. As we shall see in Section 7.4.3, they can take advantage of thephenomenon of "locality" — the nonrandom behavior of typical programs.
The large variance in memory access times is due to the fundamental limitation in hardware technology; we can build small and fast storage, or large and slow storage, but not storage that is both large and fast. It is simply impossible today to build gigabytes of storage with nanosecond access times, which is how fast high-performance processors run. Therefore, practically all modern computers arrange their storage as a memory hierarchy. A memory hierarchy, as shown in Fig. 7.16, consists of a series of storage elements, with the smaller faster ones "closer" to the processor, and the larger slower ones further away.
Typically, a processor has a small number of registers, whose contents are under software control. Next, it has one or more levels of cache, usually made out of static RAM, that are kilobytes to several megabytes in size. The next level of the hierarchy is the physical (main) memory, made out of hundreds of megabytes or gigabytes of dynamic RAM. The physical memory is then backed up by virtual memory, which is implemented by gigabytes of disks. Upon a memory access, the machine first looks for the data in the closest (lowest-level) storage and, if the data is not there, looks in the next higher level, and so on.
Registers are scarce, so register usage is tailored for the specific applications and managed by the code that a compiler generates. All the other levels of the hierarchy are managed automatically; in this way, not only is the programming task simplified, but the same program can work effectively across machines with different memory configurations. With each memory access, the machine searches each level of the memory in succession, starting with the lowest level, until it locates the data. Caches are managed exclusively in hardware, in order to keep up with the relatively fast RAM access times. Because disks are relatively slow, the virtual memory is managed by the operating system, with the assistance of a hardware structure known as the "translation look aside buffer." Data is transferred as blocks of contiguous storage. To amortize the cost of access, larger blocks are used with the slower levels of the hierarchy. Between main memory and cache, data is transferred in blocks known as cache lines, which are typically from 32 to 256 bytes long. Between virtual memory (disk) and main memory, data is transferred in blocks known as pages, typically between 4K and 64K bytes in size.