OSDev.org

(I hope I can describe my question clear enough in English)

My question is: Does it matter for system performance wheter a series of pages is mapped to a contigious part of physical memory or to fragmented parts?

An example with 32 kb of memory, 4 kb/page:

situation A:
logical page: 1 -> physical page 56
logical page: 2 -> physical page 57
logical page: 3 -> physical page 58
logical page: 4 -> physical page 59
logical page: 5 -> physical page 60
logical page: 6 -> physical page 61
logical page: 7 -> physical page 62
logical page: 8 -> physical page 63

situation B: [fragmented physical memory]
logical page: 1 -> physical page 56
logical page: 2 -> physical page 142
logical page: 3 -> physical page 2
logical page: 4 -> physical page 13
logical page: 5 -> physical page 1034
logical page: 6 -> physical page 240
logical page: 7 -> physical page 241
logical page: 8 -> physical page 23

Do the situations A and B differ in performance?

Final question is: Is it worthwhile to avoid fragmentation of physical memory?

In theory it shouldn't matter at all, because the MMU automagically figures out where to access when you read/write to memory.

The second case is unlikely to be slower than the first case, unless some weird caching issue pops up or the TLB's have problems with non-contiguous blocks of memory - which I doubt, because part of the appeal of paging is being able to do this.

Continuity isn't required, but it has a tendency to help due to the way the caches work. Each entry in the (TLB) cache can not normally hold all possible TLB values, so it is in extreme cases possible to run out of TLB's while large parts of the cache are completely unused.

This phenomenon is caused by cache associativity - There's also Cache colouring, which is the corresponding principle to avoid these effects.

Note that it's not limited to the TLB cache. The CPU's data caches are built in the same way and hence suffer the same kind of effects.

There are performance differences between using different sets of physical pages but the problem is not normally due to whether they are sequential or not but rather to which part of the processor's cache they use. Generally, modern processors have a cache on the physical memory on a page-by-page basis. All physical memory pages map to one particular cache location, so that page 1 maps to cache position 1, 2 to 2 and so on up to n to n, where n is the number of processor cache locations your particular system has. At this point the mapping rolls over, so that physical page n+1 maps to cache location 1 again.

What this means is that if process 1 uses physical pages 1, n+1, 2n+1, 3n+1 and so on, then they all fight for the same cache position (i.e. number 1) which is a bad thing. You generally want to spread the physical pages you allocate for a process over the available cache positions. The technique used is called page colouring. You basically have one allocator per page colour (cache location) and try to assign pages that aren't the same colour to each process.

Regards,
John.

edit: as indeed Combuster pointed out 1 minute before this post...