In
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
,
cache coloring (also known as
page coloring) is the process of attempting to allocate free pages that are contiguous from the
CPU cacheA CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster memory which stores copies of the data from the most frequently used main memory locations...
's point of view, in order to maximize the total number of pages cached by the processor. Cache coloring is typically employed by low-level
dynamic memory allocationIn computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program...
code in the
operating systemAn operating system is an interface between hardware and user which is responsible for the management and coordination of activities and the sharing of the resources of the computer that acts as a host for computing applications run on the machine. As a host, one of the purposes of an operating...
, when mapping
virtual memoryVirtual memory is a computer system technique which gives an application program the impression that it has contiguous working memory , while in fact it may be physically fragmented and may even overflow on to disk storage. Systems that use this technique make programming of large applications...
to physical memory. A virtual memory subsystem that lacks cache coloring is less deterministic with regards to cache performance, as differences in page allocation from one program run to the next can lead to large differences in program performance.
For example, if page 10 of physical memory is assigned to page 0 of a process'
virtual memoryVirtual memory is a computer system technique which gives an application program the impression that it has contiguous working memory , while in fact it may be physically fragmented and may even overflow on to disk storage. Systems that use this technique make programming of large applications...
and the cache can hold 5 pages, the page coloring code will not assign page 15 of physical memory to page 1 of a process's virtual memory.
Discussion
Ask a question about 'Cache coloring' Start a new discussion about 'Cache coloring' Answer questions from other users |
In
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
,
cache coloring (also known as
page coloring) is the process of attempting to allocate free pages that are contiguous from the
CPU cacheA CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster memory which stores copies of the data from the most frequently used main memory locations...
's point of view, in order to maximize the total number of pages cached by the processor. Cache coloring is typically employed by low-level
dynamic memory allocationIn computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program...
code in the
operating systemAn operating system is an interface between hardware and user which is responsible for the management and coordination of activities and the sharing of the resources of the computer that acts as a host for computing applications run on the machine. As a host, one of the purposes of an operating...
, when mapping
virtual memoryVirtual memory is a computer system technique which gives an application program the impression that it has contiguous working memory , while in fact it may be physically fragmented and may even overflow on to disk storage. Systems that use this technique make programming of large applications...
to physical memory. A virtual memory subsystem that lacks cache coloring is less deterministic with regards to cache performance, as differences in page allocation from one program run to the next can lead to large differences in program performance.
Example
For example, if page 10 of physical memory is assigned to page 0 of a process'
virtual memoryVirtual memory is a computer system technique which gives an application program the impression that it has contiguous working memory , while in fact it may be physically fragmented and may even overflow on to disk storage. Systems that use this technique make programming of large applications...
and the cache can hold 5 pages, the page coloring code will not assign page 15 of physical memory to page 1 of a process's virtual memory. It would, instead, assign page 16 of physical memory. The page coloring code attempts to avoid assigning page 15 because this maps over the same cache memory as page 10 and would result in non-optimal caching.
Implementations
This code adds a significant amount of complexity to the virtual memory allocation subsystem, but the result is well worth the effort. Page coloring makes virtual memory as deterministic as physical memory in regard to cache performance. Page coloring is employed in
operating systemAn operating system is an interface between hardware and user which is responsible for the management and coordination of activities and the sharing of the resources of the computer that acts as a host for computing applications run on the machine. As a host, one of the purposes of an operating...
s such as
SolarisSolaris is a UNIX-based operating system introduced by Sun Microsystems in 1992 as the successor to SunOS.Solaris is known for its scalability, especially on SPARC systems, and for originating many innovative features such as DTrace and ZFS...
,
FreeBSDFreeBSD is a free Unix-like operating system descended from AT&T UNIX via the Berkeley Software Distribution . It has been characterized as "the unknown giant among free operating systems". It is not a clone of UNIX, but works like UNIX, with UNIX-compliant internals and system APIs. FreeBSD is...
and
Windows NTWindows NT is a family of operating systems produced by Microsoft, the first version of which was released in July 1993. It was originally designed to be a powerful high-level-language-based, processor-independent, multiprocessing, multiuser operating system with features comparable to Unix. It was...
External links