Any memory usage paradigm besides Stack and Heap?_问答_开发者

As I have learned data structure, I know there are plenty of other data stuctures besides Stack and Heap, why the processes nowadays only contain these 2 paradigm as the "standard equipment" in their address space? Could there be any brand new paradigm for memory usage?

Thanks for your replies. Yes, I realized that something is wrong with my statement. The heap data structur开发者_如何学编程e is not the same as the heap in a process' address space. But what I am wondering is besides Stack area and Heap area in the proecss address space, is there any new paradigm to use memory? It seems that other ways of memory usage is built upon these two basic paradigms. And these 2 paradigms are kind of some meta-paradigms?

Let's think for a moment. We have two fundamental storage disciplines. Contiguous and Fragmented.

Contiguous.

Stack is constrained by order. Last in First Out. The nesting contexts of function calls demand this.
We can easily invert this pattern to define a Queue. First in First Out.
We can add a bound to the queue to make a Circular Queue. Input-output processing demands this.
We can combine both constraints into a Dequeue.
We can add a key and ordering to a queue to create a Priority Queue. The OS Scheduler demands this.

So. That's a bunch of variations on contiguous structures constrained by entry order. And there are multiple implementations of these.
You can have contiguous storage unconstrained by entry order: Array and Hash. An array is indexed by "position", a hash is indexed by a hash function of a Key.

Fragmented:

The bare "heap" is fragmented storage with no relationships. This is the usual approach.
You can have heap storage using handles to allow relocation. The old Mac OS used to do this.

You can have fragmented storage with relationships -- lists and trees and the like.

Linked Lists. Single-linked and doubly-linked lists are implementation choices.
Binary Trees have 0, 1 or 2 children.
Higher-order trees. Tries and the like.

What are we up to? A dozen?

You can also look at this as "collections" which exist irrespective of the storage. In this case you mix storage discipline (heapish or array-ish)

Bags: unordered collections with duplicates allowed. You can have a bag built on a number of storage disciplines: LinkedBag, TreeBag, ArrayBag, HashBag. The link and tree use fragmented storage, the array and hash use contiguous storage.

Sets: unordered collections with no duplicates. No indexing. Again: LinkedSet, TreeSet, ArraySet, HashSet.

Lists: ordered collections. Indexed by position. Again: LinkedList, TreeList, ArrayList, HashList.

Mapping: key-value association collections. Indexed by key. LinkedMap, TreeMap, ArrayMap, HashMap.

Note that "the heap" (a region of memory where you can allocate and release memory in random order) has nothing to do with the data structure called "heap" (priority lists).

By the way, yes, there is a third memory usage paradigm besides Stack and Heap: static storage ;-)

FIFO comes to mind. Shared memory between processors. Would messaging passing be a memory paradigm?

Javolution (http://javolution.org/) has a few interesting allocation paradigms implemented via code and interpreter 'hinting' using contexts. Pooled memory, object recycling support, and so on. Although this is Java and not C++, it could still be of use to study the concepts.

memory mapped files?

The "Heap" is not a paradigm at all, it's the most basic thing you can get: the memory is all yours, use it how ever you want. ("You" here referring the OS/Kernel).

Even the stack is not all that special if you think about it; you're just starting from one end of the heap and growing/shrinking as needed.

I'm thinking that it has to do with the physical nature of memory. Heaps and stacks are just intuitive ways of representing it.

For example, a queue or list does not lend itself conceptually to random access. A tree does not represent the physical nature of memory (one cell after another, like an array). Any sort of tuple with an x,y address is unnecessarily complicated compared to a simple integer address.

What about DMA? http://en.wikipedia.org/wiki/Direct_memory_access