Memory reference estimation method and device based on improved cache

A computer system that includes a processor, a memory and a processor cache for the main memory with a check-in-cache instruction may be provided. The processor executes computer readable instructions stored in the memory that include receiving a check-in-cache instruction from a check-in-cache storage location. The instructions also include responsive to receiving the check-in-cache instruction, determining whether data bytes specified by the check-in-cache instruction are at least partially available in the processor cache. The instructions further include storing a condition code of the determination result in a storage location.

BACKGROUND

The present invention relates generally to a computer system and memory management, and more specifically, to a computer system that includes a processor with a cache for caching main memory that is managed by an enhanced memory management system.

Virtual machine (VM) concepts allow creating and running multiple operating environments on one physical server at the same time. Because each virtual environment requires its own operating system for running applications independently, a virtualization layer (hypervisor) provides a layer between the processing, storage and/or main memory, and networking hardware and the software that runs on it. This way, information technology cost may be lowered through increased efficiency and flexibility. Each virtual environment emulates a complete hardware system. However, virtual main memory areas need to be mapped to the real physical main memory of the underlying hardware system. Therefore, memory pages in the physical main memory may be shared between different processes, e.g., of different virtual machines or other processes. Memory pages in main memory which are currently not accessed are typically moved or pushed to disk and are not present in the physical main memory.

The underlying paging algorithm goal is therefore to move non-accessed pages to disk and to move required pages to the main memory. The basic problem may be described as efficiently identifying non-access pages to free up main memory. The underlying complexity exists due to shared memory pages and main memory. The same problem exists for a mapping of main memory pages to cache systems. There are currently some solutions for memory reference tracking available in order to make paging decisions.

U.S. Pat. No. 8,438,363 B1 describes a system, a method and a computer program product for virtualizing a processor including a virtualization system running on a computer system and controlling memory pages through hardware support for maintaining real paging structures.

U.S. Pat. No. 6,308,247 B1 discloses a page table entry management method and apparatus for providing a microkernel system with the ability to program a memory management unit on a PowerPC® family of processors. The PowerPC processors define a limited set of page table entries (PTEs) to maintain virtual to physical mappings. The page table entry management method and apparatus solve the problem of a limited number of PTEs by segment aliasing when two or more user processes share the segment of the memory.

However, almost all currently available architectures do not provide 2-way accurate reference information of the active page tracking. The available implementations provide fast memory access times, but slow checking/resetting of reference information. In the well-known Intel architecture, each page table entry has a reference bit embedded. In order to find the cumulative reference status of a page or all pages, table entries need to be found which requires quite some time. Pages of some dynamic shared library objects (DSOs), e.g., libc, are found in most all address spaces and thus, have many page table entries associated with them. Another architecture, the System Z® architecture uses a reference bit in a storage key, which is associated with each physical page frame. Special-purpose instructions are required; and quiesce operations need to automatically read/set the storage key, which in terms of performance can be relatively expensive, even after an optimization.

Hence, there is a need for better management of memory pages, particularly for identifying non-accessed pages to determine infrequent accessed pages as candidates for being moved from main memory to disk on a regular basis with low computing overhead.

SUMMARY

An embodiment includes a computer system that comprises a processor, a main memory and a processor cache for the main memory may be provided. The processor can execute computer instructions for receiving a check-in-cache instruction from a check-in-cache storage location. The processor can also execute computer instructions for, responsive to receiving the check-in-cache instruction, determining whether data bytes specified by the check-in-cache instruction are at least partially available in the processor cache. The processor can further execute computer instructions for storing a condition code of the determination result in a storage location.

According to another embodiment of the present invention, a method for memory management in a computer system that comprises a processor, a main memory and a processor cache for the main memory may be provided. The method may comprise receiving a check-in-cache instruction from a check-in-cache storage location, determining, responsive to receiving the check-in-cache instruction, whether data bytes specified by the check-in-cache instruction are at least partially available in the processor cache, and storing a condition code of the determination result in a storage location.

It may be noted that the check-in-cache instruction may not read-out the addressed data. Additionally, it may be noted that the check-in-cache storage location may be the main memory.

The proposed computer system and the related method for memory management may offer a couple of advantages and technical effects:

In contrast to existing technologies embodiments of the here proposed system and method allow faster checking, eliminating the need to reset reference information for memory pages without traditional drawbacks of performance penalties due to data read-out. By adding a determination at the end of an active queue of page table entries about whether the memory page has been accessed and positioning the entry in the active list again at the top of the active queue instead of moving it to the inactive queue, memory pages are not treated as inactive pages which are managed in the inactive list.

Additionally, by adding a second determination at the end of the inactive queue of page table entries about whether the memory page has been accessed and positioning the entry in the active list again at the top of the active queue instead of moving it to disk, the management of memory content becomes much more effective. The check-in-cache instruction is key to both determinations just mentioned. The check-in-cache instruction may be issued to determine whether the page has been accessed, however, without a computation-wise expensive read-out of the data. Additionally, embodiments of the proposed technology also allow the use of traditional methods, e.g., contemporary “page dirty checks”, as a second indication for the memory page management algorithm.

A further improvement may be seen that by improving the performance of a reference determination a paging rate to input/output (I/O) may be improved, which has been limited by some prior art technologies, in particular those with a large amount of memory and fast I/O-channels.

In the following, further embodiments are described:

According to one embodiment of the computer system, the storage location may be a processor register, a processor flag or a main memory location. Thus, the storage location for the condition code of the determination may be stored in any suitable place dependent on individual design criteria. There are no real design limitations for the storage location.

According to one optional embodiment of the computer system, the processor cache may comprise at least two hierarchy levels. The hierarchy level directly caching the main memory may be an inclusive cache, and the determination may be based on a determination whether the data bytes are contained in the hierarchy level directly caching the main memory. This implementation option may be one option out of at least two, as can be seen from the next embodiment.

According to this alternative embodiment of the computer system, the processor cache may comprise at least two hierarchy levels, a first and a second level, and the hierarchy level directly caching the main memory may be a non-inclusive cache. In this case, the determination may be based on a determination whether the data bytes are contained in the first hierarchy level or in the second hierarchy level directly caching the main memory. Hence, the implementation of embodiments of the inventive technology may be independent of the cache organization.

According to an embodiment of the computer system, the processor may comprise a plurality of computing nodes, each node comprising a plurality of processor chip units, each processor chip unit comprising a plurality of processing cores, wherein each computing node may comprise a local cache controller. This may define a maximum hierarchy level of processing unit design. However, the inventive concept may also work with less, or even more, hierarchy levels.

According to an optional embodiment of the computer system, the local cache controller may have priority for a determination of whether a memory page is cached. This may imply that local cache controller belonging to a computing node may check the local cache first before checking the cache controllers of other nodes.

According to an embodiment of the computer system, a determination of whether to perform a check-in-cache instruction or to perform a reference bit check for a paging decision, in particular for memory management, may be performed by an operating system module. Thus, the memory management may be controlled by software, optionally as part of an operating system.

According to an embodiment of the computer system, the determination performed by the operating system module may be dependent on a memory page turn-over rate. A threshold may be defined. If the page turn-over rate may exceed the threshold, embodiments of the memory management method may be used for relaying in the check-in-cache instruction; in case the threshold may not or may just be reached, the traditional memory management methods may be used.

According to an embodiment of the computer system, the main memory content may be managed according to a least recently used concept, thus, the memory content may be pushed to a storage device if a memory page may be inactive. Specific caching and paging algorithms may control this process.

According to an additional embodiment of the computer system, page memory table entries may be organized according to a second chance least recently used algorithm. A person skilled in the art will know that a second chance least recently used algorithm is a modified form of a FIFO (1stin, 1stout) page replacement algorithm. It may fare relatively better than FIFO at little cost for the improvement. It works by looking at the front of the queue as FIFO does, but instead of immediately paging out that page, it checks to see if its referenced bit is set. If it is not set, the page may be swapped out. Otherwise, the referenced bit may be cleared, the page may be inserted at the back of the queue (as if it were a new page) and this process may be repeated. It may also be thought of as a circular queue.

According to an embodiment of the computer system, the check-in-cache instruction may return a result of a determination of an availability of a memory page or parts thereof without loading the memory page to the processor cache if the memory content is not in the processor cache. The result of the determination may be stored as a bit for further reference anywhere in the architecture.

According to a further embodiment of the computer system, in case the check-in-cache instruction result is indicative of a non-availability of the memory page or parts thereof in the processor cache or the main memory, a reference bit check is performed in the page table entries or a storage key of a physical memory page. Thus, both implementation options may use this technology. There are no architectural imitations.

According to another embodiment of the computer system, the reference bit check may only be performed in an inactive list of the page table entries or in the storage key of a physical memory page. Thus, the active list may not be checked as part of this determination resulting in a performance gain.

According to an embodiment of the computer system, the check-in-cache instruction may specify a subsequent number of data bytes stored in the main memory. This may be called the explicit form of the specification of the check-in-cache instruction because a number of subsequent data bytes may have to be specified. This may be viewed in contrast to the next embodiment, the implicit form.

According to an embodiment of the computer system, a subsequent number of data bytes stored in the main memory may be specified by the check-in-cache instruction, i.e., specified implicitly. Hence, the number of bytes may not be changed with the check-in-cache instruction. An exemplary number of implicitly specified bytes—without being limited to this number of bytes in this example—may, e.g., be 4 kB. However, this implementation may not be as flexible as the one described before having the explicit form, because the number of bytes after an address specified by the check-in-cache may be fixed.

DETAILED DESCRIPTION

The term ‘processor’ may denote a central processing unit (CPU), like a general purpose CPU, of a computer system. This may also include specific processors like graphic processing units (GPUs), accelerators, or other signal processing units.

The term ‘main memory’ or ‘memory’ may denote, e.g., random access memory (RAM) as used in virtually every computer system for storing data and executing program code. In typical cases, the main memory may lose its stored information in case of a power off.

The term ‘processor cache’ may denote a specific memory area of memory cells, typically geometrically located close to the processor, to enable a fast access to data in the cache if compared to an access of data in the main memory. One task of the operating environment is to ensure that the cache may be consistent with the content of the main memory. A person skilled in the art will be knowledgeable about different kinds of caching algorithms. There may be different cache hierarchy levels in a processing system; e.g., L1 to L4 caches, whereat the letter “L” stands for the level of the cache.

The term ‘check-in-cache instruction’ may denote a new form of an instruction, instrumental for an improved memory management. The check-in-cache instruction may return a result indicative of specific data being in a specific cache without accessing the individual memory cells, i.e., without reading the data out.

The term ‘storage location’, in particular for storing a reference of a determination result of whether a page has been accessed, may denote here, a storage location allowing a fast access by the processor on the caching algorithms in general. Therefore, options for the storage location, e.g., for a specific determination, and thus, just one bit, may be a processor register or a part thereof, a processor flag or, a main memory location, e.g., as part of a longer processor status word.

The term ‘hierarchy level’, in particular hierarchy levels of caches, may denote how close cache cells of a certain level may be to a processing unit. The smaller the number of the cache level, the closer the memory cells of that cash level are to the processing unit. Thus, L1 cache may be accessed instantaneously by a processing unit, because the two elements are located as close as possible to each other for immediate data access.

The term ‘inclusive cache’ may denote a cache design in which all data in the cache level, having a lower number than another cache level, are also comprised in a cache having a higher level number; i.e., in an inclusive cache all data of an L1 cache are also be comprised somewhere in a corresponding L2 cache. This may also be called “strictly inclusive”. This strict order is not implemented in a ‘non-inclusive cache’. The advantage of exclusive caches may be that they store more data. This advantage may be bigger when the exclusive L1 cache is comparable to the L2 cache, and may be diminished if the L2 cache is many times larger than the L1 cache. When the L1 cache may miss and the L2 cache may hit on an access, the hitting cache line in the L2 cache is exchanged with a line in the L1. This exchange may be quite a bit more work than just copying a line from L2 cache to a L1 cache, which is what an inclusive cache does.

In the following, a detailed description of the figures will be given. All instructions in the figures are schematic. Firstly, a block diagram of a known memory management method may be described. Afterwards, different embodiments of the proposed computer system using the check-in-cache instruction as well as embodiments of the method for memory management in a computer system will be described.

FIG. 1shows a block diagram of contemporary technology for memory management using a reference bit102embedded in the page table entry104for a single page frame106. In order to find a cumulative reference status of a memory page, all page table entries need to be found and examined. This may be quite time consuming. Pages of some dynamically shared objects (DSO), like libc, may be found in pretty much all address spaces of all virtual machines running on a physical processor. Thus, they all may have page table entries associated with it. The required overhead of this traditional technology can be relatively large.

FIG. 2shows a memory management using a storage key, such as that used by System z central execution complexes (CECs). A storage key202which may also include an associated reference bit204. The storage key202with the reference bit204may be associated with each physical page frame, indicative of a change of the stored content of that page frame. Special purpose instructions may be required to read the reference bit. For example, quiesce operations can be used to atomically read/set the storage key.

FIG. 3shows a substantial part of a larger CPU. Four processor or computing nodes306,308,310,312are shown. The IBM System z architecture may be used as example. Each of the computing nodes306,308,310,312may comprise a plurality of processing units302. Each processing unit302may comprise a plurality of cores (not shown). In case of the IBM System z architecture each processing unit302may manage its own level 1 (L1), level 2 (L2) and level 3 (L3) cache. Other processor architectures may have a different number of levels of caches as well as a different number of hierarchy levels inside the processing units.

As shown, each computing node306,308,310,312may have a dedicated cache controller304a,304bresponsible for communication and data exchange between a last level cache, in the example of the System z L4 cache, and the main memory. The differentiation between cache controller104aand the cache controllers304bis made because embodiments may ensure that a local cache controller104bmay be checked first before a request is issued to cache controllers104aof other computing nodes306,308,310. Thus, if processing unit302aneeds a memory page (not shown) in its cache, the local cache controller304ais checked first before the other cache controllers304bare checked.

The other “remote” cache controllers304bare only checked if parts of the memory page is not cached locally, i.e., controlled by cache controller304a. A page with no data resident in cache is considered to be inactive.

FIG. 4shows a block diagram how an operating system can use a check-in cache instruction for memory management in accordance with embodiments. In the block402“CPU instruction execution” unit, a check-in-cache instruction404is issued406, and operating system408controlled. The instruction execution unit402may recognize the new check-in-cache instruction. The check-in-cache instruction may comprise the address to be verified. The check-in-cache instruction404interpretation forwards410the address and the page size to the control and detection logic412of the cache411. The control and detection logic412starts414, and a cache416directory lookup on the memory page granularity is performed. The control and detection logic412tracks418if the cache directory look-up did succeed. If “yes” it suppresses a read-out of the cache data420. The control and detection logic412then returns422hit/miss information to the check-in-cache instruction404as a return value. Finally, the check-in-cache instruction404continues and returns424the result as status back to the operating system408. The operating system408algorithm acts then accordingly.

FIG. 5shows an embodiment of a memory management using active queue502for page table entries in accordance with embodiments. At the head502aof the active queue502, a page address assigned506to a process without a file backing is added to active queue502. Over time, more and more references to memory pages are added to the active queue502. Thus, earlier added references are moved, step by step, through the queue in the direction of the tail502bof the active queue502. From here, a reference to a memory page may be moved to the head504aof the inactive queue504. However, in accordance with embodiments, it may be checked using the check-in-cache instruction whether the corresponding memory page has been referenced508. If that is the case, the memory page reference entry is again added to the head502aof the active queue502. Thus, the movement of the reference for the memory page to the inactive queue504may only be performed if the corresponding page has not been referenced,508a.

The movement of the references for memory page through the inactive queue504is done in a comparable way to the movement of references for memory page through the active queue502. If a new entry is added at the head504a, the rest of the inactive queue504is moved one position to the right (in the diagram shown inFIG. 5).

At the tale504bof the inactive queue504, a reference for a memory page may be removed510in case a memory page is clean, meaning that the reference for the memory page is simply moved out of the queue. “Clean” may denote here that the cache entries and the main memory entries correspond to each other. The cache memory cells have not been modified if compared to the corresponding main memory cells. In case the corresponding memory page is changed (dirty), the reference for the memory page is again moved512to the head504aof the inactive queue504. However, the check-in-cache instruction comes into play and if the corresponding page has been referenced512(dirty page), the reference for the memory page is again moved514to the head502aof the active queue502. In that case, another action may be required, i.e., a reset,516, of the page referenced bit of the reference for the corresponding memory page in the active queue502.

It may be noted that before a reference for a memory page is moved from the tail502aor504bof the respective queue502,504, a check-in cache instruction is executed under the control of the operating system, controlling the memory management process. However, in case of the determination at the tail504bof the inactive queue504, a check-in-cache instruction may be executed first. If the check-in-cache result is negative, the “dirty check” is triggered. If the check-in-cache instruction returns a positive result, no reference check is performed. The result of the “dirty check” may also return a prior art reference check, which is used as a second indication for the caching algorithm.

FIG. 6shows the just described embodiment as flowchart. Reference numerals502,504symbolize the active queue502and the inactive queue ofFIG. 5. If a new PTE is added to the page table, the reference bit (here, “accessed”) is reset602. Then, the caching algorithm may wait604, until the memory gets under pressure, i.e., the cache does not provide enough memory cells to cache main memory page frames. At this stage606a PTE may be removed from the active queue502. At that point in time, it may be determined608whether the page may have been referenced, i.e., accessed since the PTE has been added to the active queue502. In case of “yes”, the process starts from the beginning602.

In case of “no” the referenced bit or access bit may be reset610and a write to disk of the memory page may be started. The back arrow from block610to block604, i.e., “wait for memory pressure”, may indicate that the process has to wait for the “write page to disk”610to complete (I/O completion). In practical terms, the PTE may again be added to the head504aof the inactive list504for a second round on the inactive list504assuming that the I/O has been completed when the PTE reaches the tail504bif the inactive list again.

As shown at block612, the process waits for the write to disk to be completed. Then, it may again be determined614whether the page has been accessed, i.e., referenced since the entry into the inactive queue504. In case of “no”, the page may be added 618 to the free pages list. In case of “yes”, the referenced bit may be reset616(reset “assessed”) and the PTE may be added again to the head502aof the active queue502.

A person skilled in the art may understand that the actions “reset accessed” in blocks602,610and616as well as the two determinations of whether the page has been accessed at608,614are different than contemporary methods.

Embodiments of the invention may be implemented together with virtually any type of modified computer, regardless of the platform being suitable for storing and/or executing program code.FIG. 7shows, as an example, a computing system700suitable for executing program code related to the proposed method.

As shown in theFIG. 7, computer system/server700is shown in the form of a general-purpose computing device. The components of computer system/server700may include, but are not limited to, one or more processors or processing units702, a system memory704, and a bus706that couples various system components including system memory704to the processor702. Bus706represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnects (PCI) bus. Computer system/server700typically includes a variety of computer system readable media. Such media may be any available media that is accessible by computer system/server700, and it includes both, volatile and non-volatile media, removable and non-removable media.

Program/utility714, having a set (at least one) of program modules716, may be stored in memory704by way of example, and not limitation, as well as an operating system, one or more application programs, other program modules, and program data. Each of the operating system, one or more application programs, other program modules, and program data or some combination thereof, may include an implementation of a networking environment. Program modules716generally carry out the functions and/or methodologies of embodiments of the invention as described herein.

The computer system/server700may also communicate with one or more external devices718such as a keyboard, a pointing device, a display720, etc.; one or more devices that enable a user to interact with computer system/server700; and/or any devices (e.g., network card, modem, etc.) that enable computer system/server700to communicate with one or more other computing devices. Such communication can occur via Input/Output (I/O) interfaces714. Still yet, computer system/server700may communicate with one or more networks such as a local area network (LAN), a general wide area network (WAN), and/or a public network (e.g., the Internet) via network adapter722. As depicted, network adapter722may communicate with the other components of computer system/server700via bus706. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with computer system/server700. Examples, include, but are not limited to: microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, and data archival storage systems, etc.