On-line system for measuring the efficiency of replacement algorithms

Claim 2

In a data processing system of the virtual-memory type wherein blocks of information are stored at numbered block addresses in a backup store and in some instances are stored also at working addresses temporarily associated with such block numbers in a high-speed working memory having a limited storage capacity, said system including a central processoR operable to request blocks of information according to their block numbers in said backup store and to reference such blocks when they are residing in said working memory and being effective whenever the block which it requests is currently stored only in the backup store to fetch the requested block from said store and enter the same into said memory at a working address therein selected according to a predetermined replacement algorithm, thereby replacing the block formerly stored at such working address; the method of measuring the efficiency of said predetermined replacement algorithm by progressively comparing the number of block replacements that actually are performed with an optimal number of block replacements which would have been performed had the processor been operated under the control of an optimal replacement algorithm that takes cognizance of all blocks which have resided and are about to reside in said memory, including the block currently requested by said processor, and the relative order in which such blocks have entered the memory, said method comprising the steps of: counting the actual number of replacement intervals that are initiated by said processor while it is operating under the control of said predetermined replacement algorithm, each such interval being initiated when said processor requests a block not currently stored in the working memory and being terminated when said processor next requests a block that is not then residing in said memory; marking with suitable indicia those working addresses at which blocks are referenced by said processor during each interval between successive block replacements; storing a table of index values which associates the identifying number of each block that has been requested by said processor with the number of the replacement interval in which such block most recently would have been referenced in the working memory according to said optimal replacement algorithm; causing said processor, as an incident to the initiation of each new replacement interval and prior to entry of the currently requested block into said memory, to make an updated determination of the optimal number of block replacement intervals that thus far would have been initiated if said processor had operated under the control of the optimal replacement algorithm, said determination being based upon said block referencing indicia and said stored index values, and manifesting a count of the unnecessary block transfers that have occurred between the backup store and the working memory according to the difference, if any, between the actual number of block replacement intervals and the optimal number of block replacement intervals.

Claim 3

An efficiency measuring method as set forth in claim 1 further comprising the steps of: detecting the occurrence of a condition in which the processor references a requested block already present in said memory without initiating a new replacement interval at a time when, according to the optimal replacement algorithm, a new replacement interval would have had to be initiated by said processor in order to make the requested block available for referencing in said memory; and in response to the detection of such a condition, adjusting the optimal interval number and the unnecessary block transfer count consistently therewith.

Claim 4

A replacement efficiency measuring method as set forth in claim 1 further comprising the steps of: detecting the occurrence of a condition in which the processor references a requested block already present in said memory without initiating a new replacement interval at a time when, according to the optimal replacement algorithm and depending also upon whether the actual order of referencing corresponds to the relative order in which the marked working addresses are arranged, a new replacement interval would have had to be initiated by said processor in order to make the requested block available for referencing in said memory; and, in Response to the detection of such a condition, manifesting an indication that the count of unnecessary block transfers may required adjustment in view of the fact that there has been an increase in the optimal number of replacement intervals without a corresponding increase in the actual number of replacement intervals.

Claim 5

In a data processing system of the virtual-memory type wherein blocks of information are stored at numbered block addresses in a backup store and in some instances are stored also at working addresses temporarily associated with such block numbers in a high-speed working memory having a limited storage capacity of N blocks, said system including a central processor operable to request blocks of information according to their block numbers in said backup store and to reference such blocks when they are residing in said working memory and being effective whenever the block which it requests is currently stored only in the backup store to fetch the requested block from said store and enter the same into said memory at a working address therein selected according to a predetermined replacement algorithm, thereby replacing the block formerly stored at such working address; apparatus for measuring the efficiency of said predetermined replacement algorithm by progressively comparing the number of block replacements that actually are performed with an optimal number of block replacements which would have been performed had the processor been operated under the control of an optimal replacement algorithm that takes cognizance of all blocks which have resided and are about to reside in said memory, including the block currently requested by said processor, and the relative order in which such blocks have entered the memory, said apparatus comprising: means for counting the actual number of replacement intervals through which said system has operated under the control of said predetermined replacement algorithm in the course of attaining the current point in its program of operations; block reference storing means effective within each interval of the actual block replacement sequence for storing indicia designating which of the N blocks stored in the working memory are referenced by the processor during that interval only; intermittently operable computing means effective when operated to institute a computational procedure whereby said processor utilizes the indicia stored in said block reference storing means together with the identifying number of the currently requested block to determine the optimal number of replacement intervals in which the system could have attained the current point in its program of operations if it where functioning under the control of an optimal replacement algorithm evolved according to specific logical rules from the sequence in which the blocks have been requested by said processor; and enabling means for said computing means effective at the initiation of each interval in the actual sequence of operations to render said computing means operative for making an updated determination of the optimal interval number, whereby the processor executes said computational procedure at those times when the system is waiting for a currently requested block to be fetched from the backup store.

Claim 6

In a data processing system of the virtual-memory type wherein blocks of information are stored at numbered block addresses in a backup store and in some instances are stored also at working addresses temporarily associated with such block numbers in a high-speed working memory having a limited storage capacity of N blocks, said system including a central processor operable to request blocks of information according to their block numbers in said backup store and to reference such blocks when they are residing in said working memory and being effective whenever the block which it requests is currently stored only in the backup store to fetch the requested block from said store and enter the same into said memory at a working address therein selected according to a predetermined replacement algorithm, thereby replacing the block formerly stored at such working address; apparatus for measuring the efficiency of said predetermined replacement algorithm by progressively comparing the number of block replacements that actually are performed with an optimal number of block replacements which would have been performed had the processor been operated under the control of an optimal replacement algorithm that takes cognizance of all blocks which have resided and are about to reside in said memory, including the block currently requested by said processor, and the relative order in which such blocks have entered the memory, said apparatus comprising: means for counting the actual number of replacement intervals through which said system has operated under the control of said predetermined replacement algorithm in the course of attaining the current point in its program of operations; block reference storing means effective within each interval of the actual block replacement sequence for storing indicia designating which of the N blocks stored in the working memory are referenced by the processor during that interval only; intermittently operable computing means effective when operated to institute a computational procedure whereby said processor utilizes the indicia stored in said block reference storing means together with the identifying number of the currently requested block to determine the optimal number of replacement intervals in which the system could have attained the current point in its program of operations if it where functioning under the control of an optimal replacement algorithm evolved according to specific logical rules from the sequence in which the blocks have been requested by said processor; and enabling means for said computing means effective at the initiation of each interval in the actual sequence of operations to render said computing means operative for making an updated determination of the optimal interval number, whereby the processor executes said computational procedure at those times when the system is waiting for a currently requested block to be fetched from the backup store.

Claim 7

Apparatus as set forth in claim 4 wherein said computing means includes the following: registering means effective each time said processor requests a block not then stored in the working memory to register the number of the block and the number of the optimal interval corresponding to the actual interval in which it is so requested; means for designating which of the intervals defined by the optimal replacement algorithm contain complete sets of block references, each complete-set interval consisting of a single interval in the optimal sequence of operations corresponding to one or more contemporary intervals in the actual sequence of operations during at least one of which the working memory contains N blocks all of which are referenced by said processor within a period that includes said single optimal interval and, if necessary, not more than N-1 succeeding optimal intervals; and means under the control of said registering means and said complete-set designating means for effectively excluding from the current determination of the optimal interval number all block requests that were made prior to the most recently designated complete-set interval.

Claim 8

Apparatus as set forth in claim 5, further comprising: detecting means responsive to the block number requests registered by said registering means and responsive also to the optimal interval numbers determined by said computing means and said complete-set interval designations for detecting the occurrence of a condition in which a particular block has been permitted by said predetermined replacement algorithm to remain continuously in the working memory in an unreferenced state during a plurality of successive intervals in the actual sequence of operations corresponding to at least N successive intervals in the optimal sequence, commencing with a complete-set interval; and means controlled by said detecting means when it has detected the occurrence of such a condition, and operable in the event that the processor again references said particular block before it leaves the working memory, to increment the current optimal interval number without changing the current actual interval number, thereby effectively decrementing the count of unnecessary transfers charged to said predetermined replacement algorithm.

Claim 9

In a data processing system of the kind wherein blocks of information are stored at numbered block addresses in a backup store and in some instances are stored also at working addresses temporarily associated with such block numbers in a high-speed working memory having a limited storage capacity of N blocks, said system including a central processor operable to request blocks of information according to their block numbers in said backup store and to reference such blocks when they are residing in said working memory and having block transfer instrumentalities effective whenever said processor requests a block currently stored only in the backup store to fetch the requested block from said store and enter the same into the working memory at a working address therein selected according to a predetermined replacement algorithm, thereby replacing the block formerly stored at such working address and causing the operation of the system to be divided into a succession of block replacement intervals, each interval commencing when the processor requests a block not currently stored in the working memory and terminating when the processor next requests a block that is not then residing in the working memory, the improvement consisting of an apparatus for enabling the replacement efficiency of the system to be dynamically measured while the system is operating under the control of said predetermined replacement algorithm, said apparatus comprising: means for counting the actual number of replacement intervals through which said system has operated under the control of said predetermined replacement algorithm in the course of attaining the current point in its program of operations; computing means for performing an optimization procedure wherein said processor determines the optimal number of replacement intervals in which the system could have attained the current point in its program of operations if it were functioning under the control of an optimal replacement algorithm evolved empirically from the sequence in which the blocks have been requested by said processor; the difference, if any, between the actual and optimal interval numbers representing the number of unnecessary block transfers chargeable to said predetermined replacement algorithm; said computing means including: registering means effective each time said processor requests a block not then stored in the wOrking memory to register the number of the block and the number of the optimal interval in which it is so requested; means for designating which of the intervals defined by the optimal replacement algorithm contain complete sets of block references, each complete-set interval consisting of a single interval in the optimal sequence of operations corresponding to one or more contemporary intervals in the actual sequence of operations during at least one of which the working memory contains N blocks all of which are referenced by said processor within a period that includes said single optimal interval and, if necessary, not more than N-1 succeeding optimal intervals; and means under the control of said registering means and said complete-set designating means for effectively excluding from the current determination of the optimal interval number all block requests that were made prior to the most recently designated complete-set interval; detecting means responsive to the block number requests registered by said registering means and responsive also to the optimal interval numbers determined by said computing means and to said complete-set interval designations for detecting the occurrence of a condition in which a particular block has been permitted by said predetermined replacement algorithm to remain continuously in the working memory in an unreferenced state during a plurality of successive intervals in the actual sequence or operations corresponding to at least N successive intervals in the optimal sequence, commencing with a complete-set interval; and means controlled by said detecting means when it has detected the occurrence of such a condition, and operable in the event that the processor again references said particular block before it leaves the working memory, to increment the current optimal interval number without changing the current actual interval number, thereby effectively decrementing the count of unnecessary transfers charged to said predetermined replacement algorithm.

Claim 10

In a data processing system of the kind wherein blocks of information are stored at numbered block addresses in a backup store and in some instances are stored also at working addresses temporarily associated with such block numbers in a high-speed working memory having a limited storage capacity of N blocks, said system including a central processor operable to request blocks of information according to their block numbers in said backup store and to reference such blocks when they are residing in said working memory and having block transfer instrumentalities effective whenever said processor requests a block currently stored only in the backup store to fetch the requested block from said store and enter the same into the working memory at a working address therein selected according to a predetermined replacement algorithm, thereby replacing the block formerly stored at such working address and causing the operation of the system to be divided into a succession of block replacement intervals, each interval commencing when the processor requests a block not currently stored in the working memory and terminating when the processor next requests a block that is not then residing in the working memory, the improvement consisting of an apparatus for enabling the replacement efficiency of the system to be dynamically measured while the system is operating under the control of said predetermined replacement algorithm, said apparatus comprising: means for counting the actual number of replacement intervals through which said system has operated under the control of said predetermined replacement algorithm in the course of attaining the current point in its program of operations; computing means for performing an optimization procedure wherein said processor determines the optimal number of replacement intervals in which the system could have attained the current point in its program of operations if it were functioning under the control of an optimal replacement algorithm evolved empirically from the sequence in which the blocks have been requested by said processor; the difference, if any, between the actual and optimal interval numbers representing the number of unnecessary block transfers chargeable to said predetermined replacement algorithm; said computing means including: registering means effective each time said processor requests a block not then stored in the wOrking memory to register the number of the block and the number of the optimal interval in which it is so requested; means for designating which of the intervals defined by the optimal replacement algorithm contain complete sets of block references, each complete-set interval consisting of a single interval in the optimal sequence of operations corresponding to one or more contemporary intervals in the actual sequence of operations during at least one of which the working memory contains N blocks all of which are referenced by said processor within a period that includes said single optimal interval and, if necessary, not more than N-1 succeeding optimal intervals; and means under the control of said registering means and said complete-set designating means for effectively excluding from the current determination of the optimal interval number all block requests that were made prior to the most recently designated complete-set interval; detecting means responsive to the block number requests registered by said registering means and responsive also to the optimal interval numbers determined by said computing means and to said complete-set interval designations for detecting the occurrence of a condition in which a particular block has been permitted by said predetermined replacement algorithm to remain continuously in the working memory in an unreferenced state during a plurality of successive intervals in the actual sequence or operations corresponding to at least N successive intervals in the optimal sequence, commencing with a complete-set interval; and means controlled by said detecting means when it has detected the occurrence of such a condition, and operable in the event that the processor again references said particular block before it leaves the working memory, to increment the current optimal interval number without changing the current actual interval number, thereby effectively decrementing the count of unnecessary transfers charged to said predetermined replacement algorithm.

Claim 11

In a data processing system of the kind wherein blocks of information are stored at numbered block addresses in a backup store and in some instances are stored also at working addresses temporarily associated with such block numbers in a high-speed working memory having a limited storage capacity of N blocks, said system including a central processor operable to request blocks of information according to their block numbers in said backup store and to reference such blocks when they are residing in said working memory and having block transfer instrumentalities effective whenever said processor requests a block currently stored only in the backup store to fetch the requested block from said store and enter the same into the working memory at a working address therein selected according to a predetermined replacement algorithm, thereby replacing the block formerly stored at such working address and causing the operation of the system to be divided into a succession of block replacement intervals, each interval commencing when the processor requests a block not currently stored in the working memory and terminating when the processor next requests a block that is not then residing in the working memory, the improvement consisting of an on-lines efficiency measurement apparatus for progressively determining, with the aid of said processor, how many of the block replacements effected under the control of said predetermined replacement algorithm were performed unnecessarily as a result of previous inconsistent replacement decisions executed under the control of said algorithm, said apparatus comprising: interval indexing means for assigning a succession of actual interval numbers (P) respectively to the successive intervals in the actual sequence of block entry and replacement operations performed by said block transfer instrumentalities under the control of said predetermined replacement algorithm; optimization means for defining a succeSsion of optimal intervals according to an assumed optimal sequence of block entry and replacement operations evolved empirically from the actual sequence of block requests made by said processor and for assigning numbers (A) consecutively to such optimal intervals; the difference, if any, between the current values of said actual interval number (P) and said optimal interval number (A) at any given time representing the number of unnecessary block transfers (U) performed by said processor under the control of said predetermined replacement algorithm as of said given time, said optimization means including: block indexing means for storing variable block index values (E), one for each block number which has been requested by the processor, the current index value of each block representing the number of the optimal interval in which the respective block would have been most recently referenced in the optimal sequence of operations; counter table means having selectable storage positions addressable according to the numbers representing the respective intervals in the optimal sequence of operations, each such position being adapted to store a variable counter value (C) that is capable of being stepped through a range of values having zero and N-1 as its limits, the first such limiting value being assigned to the selected interval the first time that said processor makes reference to a block whose index value (E) corresponds to the number of that interval; counter table adjusting means effective each time the processor makes reference to a different block having the same block index value (E) to step the counter value (C) for the corresponding interval by 1 toward its second limiting value, whereby a selected one of the counter values (C) attains its second limit each time a set of N blocks having same index value (E) is referenced by said processor; complete-set interval numbering means initially settable to a starting value (e.g., 1) and effective each time a counter value in said counter table means attains its second limiting value to register the number of the corresponding optimal interval as the current complete-set interval number (B), said number, when greater than said starting value, being equal to the number of the most recent interval in the optimal sequence of operations when the N blocks stored in the working memory could have been referenced by said processor within a period including such interval and, if necessary, not more than N-1 succeeding intervals in said optimal sequence; block index adjusting means effective each time a block having an index value (E) lower than the current setting (B) of the complete-set interval numbering means is requested by said processor to increment the optimal interval number (A) and set the index value (E) of such block equal to the incremented value of the optimal interval number (A); said optimization means normally being in an unoperated state; block reference registering means including, for each block storage address in the working memory, a storage device settable to store a reference bit (R'') which indicates by its value (1 or 0) whether or not the block stored at the corresponding address in the working memory has been referenced at least once by said processor since the most recent block replacement was effected under the control of said predetermined replacement algorithm; and updating means controlled by the reference bits (R'') stored in said block reference registering means and effective each time said processor requests a block of information not then stored in said working memory to cause an updating operation of said optimization means in accordance with the identities of the respective blocks which have been referenced in the working memory during the interval that terminated with the current block request, thereby updating the optimal interval number (A), the block index values (E), the counter values (C) and the coMplete-set interval number (B), such action occurring at times when the system is waiting for block replacements.

Claim 12

In a data processing system of the kind wherein blocks of information are stored at numbered block addresses in a backup store and in some instances are stored also at working addresses temporarily associated with such block numbers in a high-speed working memory having a limited storage capacity of N blocks, said system including a central processor operable to request blocks of information according to their block numbers in said backup store and to reference such blocks when they are residing in said working memory and having block transfer instrumentalities effective whenever said processor requests a block currently stored only in the backup store to fetch the requested block from said store and enter the same into the working memory at a working address therein selected according to a predetermined replacement algorithm, thereby replacing the block formerly stored at such working address and causing the operation of the system to be divided into a succession of block replacement intervals, each interval commencing when the processor requests a block not currently stored in the working memory and terminating when the processor next requests a block that is not then residing in the working memory, the improvement consisting of an on-lines efficiency measurement apparatus for progressively determining, with the aid of said processor, how many of the block replacements effected under the control of said predetermined replacement algorithm were performed unnecessarily as a result of previous inconsistent replacement decisions executed under the control of said algorithm, said apparatus comprising: interval indexing means for assigning a succession of actual interval numbers (P) respectively to the successive intervals in the actual sequence of block entry and replacement operations performed by said block transfer instrumentalities under the control of said predetermined replacement algorithm; optimization means for defining a succeSsion of optimal intervals according to an assumed optimal sequence of block entry and replacement operations evolved empirically from the actual sequence of block requests made by said processor and for assigning numbers (A) consecutively to such optimal intervals; the difference, if any, between the current values of said actual interval number (P) and said optimal interval number (A) at any given time representing the number of unnecessary block transfers (U) performed by said processor under the control of said predetermined replacement algorithm as of said given time, said optimization means including: block indexing means for storing variable block index values (E), one for each block number which has been requested by the processor, the current index value of each block representing the number of the optimal interval in which the respective block would have been most recently referenced in the optimal sequence of operations; counter table means having selectable storage positions addressable according to the numbers representing the respective intervals in the optimal sequence of operations, each such position being adapted to store a variable counter value (C) that is capable of being stepped through a range of values having zero and N-1 as its limits, the first such limiting value being assigned to the selected interval the first time that said processor makes reference to a block whose index value (E) corresponds to the number of that interval; counter table adjusting means effective each time the processor makes reference to a different block having the same block index value (E) to step the counter value (C) for the corresponding interval by 1 toward its second limiting value, whereby a selected one of the counter values (C) attains its second limit each time a set of N blocks having same index value (E) is referenced by said processor; complete-set interval numbering means initially settable to a starting value (e.g., 1) and effective each time a counter value in said counter table means attains its second limiting value to register the number of the corresponding optimal interval as the current complete-set interval number (B), said number, when greater than said starting value, being equal to the number of the most recent interval in the optimal sequence of operations when the N blocks stored in the working memory could have been referenced by said processor within a period including such interval and, if necessary, not more than N-1 succeeding intervals in said optimal sequence; block index adjusting means effective each time a block having an index value (E) lower than the current setting (B) of the complete-set interval numbering means is requested by said processor to increment the optimal interval number (A) and set the index value (E) of such block equal to the incremented value of the optimal interval number (A); said optimization means normally being in an unoperated state; block reference registering means including, for each block storage address in the working memory, a storage device settable to store a reference bit (R'') which indicates by its value (1 or 0) whether or not the block stored at the corresponding address in the working memory has been referenced at least once by said processor since the most recent block replacement was effected under the control of said predetermined replacement algorithm; and updating means controlled by the reference bits (R'') stored in said block reference registering means and effective each time said processor requests a block of information not then stored in said working memory to cause an updating operation of said optimization means in accordance with the identities of the respective blocks which have been referenced in the working memory during the interval that terminated with the current block request, thereby updating the optimal interval number (A), the block index values (E), the counter values (C) and the coMplete-set interval number (B), such action occurring at times when the system is waiting for block replacements.

Claim 13

Apparatus as set forth in claim 8, further comprising: detecting means responsive to the block index values (E) and responsive also to the optimal interval number (A) and to the complete-set interval numbers (B) for detecting a condition in which a particular block has been permitted by said predetermined replacement algorithm to remain continuously in the working memory in an unreferenced state during a plurality of successive intervals in the actual sequence of operations corresponding to at least N successive intervals in the optimal sequence, commencing with a complete-set interval; and means controlled by said detecting means when it has detected the occurrence of such a condition, and operable in the event that the processor again references said particular block before it leaves the working memory, to increment the current optimal interval number (A) without changing the current actual interval number (P), thereby effectively decrementing the count of unnecessary transfers (U) charged to said predetermined replacement algorithm.

Claim 14

In a data processing system of the kind wherein blocks of information are stored at numbered block addresses in a backup store and in some instances are stored also at working addresses temporarily associated with such block numbers in a high-speed working memory having a limited storage capacity of N blocks, said system including a central processor operable to request blocks of information according to their block numbers in said backup store and to reference such blocks when they are residing in said working memory and having block transfer instrumentalities effective whenever said processor requests a block currently stored only in the backup store to fetch the requested block from said store and enter the same into the working memory at a working address therein selected according to a predetermined replacement algorithm, thereby replacing the block formerly stored at such working address and causing the operation of the system to be divided into a succession of block replacement intervals, each interval commencing when the processor requests a block not currently stored in the working memory and terminating when the processor next requests a block that is not then residing in the working memory, the improvement consisting of an on-line efficiency measurement apparatus for progressively determining, with the aid of said processor, how many of the block replacements effected under the control of said predetermined replacement algorithm were performed unnecessarily as a result of previous inconsistent replacement decisions executed under the control of said algorithm, said apparatus comprising: interval indexing means for assigning a succession of actual interval numbers (P) respectively to the successive intervals in the actual sequence of block entry and replacement operations performed by said block transfer instrumentalities under the control of said predetermined replacement algorithm; optimization means for defining a succession of optimal intervals according to an assumed optimal sequence of block entry and replacement operations evolved empirically from the actual sequence of block requests made by said processor and for assigning numbers (A) consecutively to such optimal intervals; the difference, if any, between the current values of said actual interval number (P) and said optimal interval number (A) at any given time representing the number of unnecessary block transfers (U) performed by said processor under the control of said predetermined replacement algorithm as of said given time, said optimization means including: block indexing means for storing variable block index values (E), one for each block number which has been requested by the processor, the current index value of each block representing the number of the optimal interval in whIch the respective block would have been most recently referenced in the optimal sequence of operations; counter table means having selectable storage positions addressable according to the numbers representing the respective intervals in the optimal sequence of operations, each such position being adapted to store a variable counter value (C) that is capable of being stepped through a range of values having zero and N-1 as its limits, the first such limiting value being assigned to the selected interval the first time that said processor makes reference to a block whose index value (E) corresponds to the number of that interval; counter table adjusting means effective each time the processor makes reference to a different block having the same block index value (E) to step the counter value (C) for the corresponding interval by 1 toward its second limiting value, whereby a selected one of the counter values (C) attains its second limit each time a set of N blocks having the same index value (E) is referenced by said processor; complete-set interval numbering means initially settable to a starting value (e.g., 1) and effective each time a counter value in said counter table means attains its second limiting value to register the number of the corresponding optimal interval as the current complete-set interval number (B), said number, when greater than said starting value, being equal to the number of the most recent interval in the optimal sequence of operations when the N blocks stored in the working memory could have been referenced by said processor within a period including such interval and, if necessary, not more than N-1 succeeding intervals in said optimal sequence; block index adjusting means effective each time a block having an index value (E) lower than the current setting (B) of the complete-set interval numbering means is requested by said processor to increment the optimal interval number (A) and set the index value (E) of such block equal to the incremented value of the optimal interval number (A); detecting means responsive to the block index values (E) and responsive also to the optimal interval number (A) and to the complete-set interval numbers (B) for detecting a condition in which a particular block has been permitted by said predetermined replacement algorithm to remain continuously in the working memory in an unreferenced state during a plurality of successive intervals in the actual sequence of operations corresponding to at least N successive intervals in the optimal sequence, commencing with a complete-set interval; and means controlled by said detecting means when it has detected the occurrence of such a condition, and operable in the event that the processor again references said particular block before it leaves the working memory, to increment the current optimal interval number (A) without changing the current actual interval number (P), thereby effectively decrementing the count of unnecessary transfers (U) charged to said predetermined replacement algorithm.

Claim 15

In a data processing system of the kind wherein blocks of information are stored at numbered block addresses in a backup store and in some instances are stored also at working addresses temporarily associated with such block numbers in a high-speed working memory having a limited storage capacity of N blocks, said system including a central processor operable to request blocks of information according to their block numbers in said backup store and to reference such blocks when they are residing in said working memory and having block transfer instrumentalities effective whenever said processor requests a block currently stored only in the backup store to fetch the requested block from said store and enter the same into the working memory at a working address therein selected according to a predetermined replacement algorithm, thereby replacing the block formerly stored at such working address and causing the operation of the system to be divided into a succession of block replacement intervals, each interval commencing when the processor requests a block not currently stored in the working memory and terminating when the processor next requests a block that is not then residing in the working memory, the improvement consisting of an on-line efficiency measurement apparatus for progressively determining, with the aid of said processor, how many of the block replacements effected under the control of said predetermined replacement algorithm were performed unnecessarily as a result of previous inconsistent replacement decisions executed under the control of said algorithm, said apparatus comprising: interval indexing means for assigning a succession of actual interval numbers (P) respectively to the successive intervals in the actual sequence of block entry and replacement operations performed by said block transfer instrumentalities under the control of said predetermined replacement algorithm; optimization means for defining a succession of optimal intervals according to an assumed optimal sequence of block entry and replacement operations evolved empirically from the actual sequence of block requests made by said processor and for assigning numbers (A) consecutively to such optimal intervals; the difference, if any, between the current values of said actual interval number (P) and said optimal interval number (A) at any given time representing the number of unnecessary block transfers (U) performed by said processor under the control of said predetermined replacement algorithm as of said given time, said optimization means including: block indexing means for storing variable block index values (E), one for each block number which has been requested by the processor, the current index value of each block representing the number of the optimal interval in whIch the respective block would have been most recently referenced in the optimal sequence of operations; counter table means having selectable storage positions addressable according to the numbers representing the respective intervals in the optimal sequence of operations, each such position being adapted to store a variable counter value (C) that is capable of being stepped through a range of values having zero and N-1 as its limits, the first such limiting value being assigned to the selected interval the first time that said processor makes reference to a block whose index value (E) corresponds to the number of that interval; counter table adjusting means effective each time the processor makes reference to a different block having the same block index value (E) to step the counter value (C) for the corresponding interval by 1 toward its second limiting value, whereby a selected one of the counter values (C) attains its second limit each time a set of N blocks having the same index value (E) is referenced by said processor; complete-set interval numbering means initially settable to a starting value (e.g., 1) and effective each time a counter value in said counter table means attains its second limiting value to register the number of the corresponding optimal interval as the current complete-set interval number (B), said number, when greater than said starting value, being equal to the number of the most recent interval in the optimal sequence of operations when the N blocks stored in the working memory could have been referenced by said processor within a period including such interval and, if necessary, not more than N-1 succeeding intervals in said optimal sequence; block index adjusting means effective each time a block having an index value (E) lower than the current setting (B) of the complete-set interval numbering means is requested by said processor to increment the optimal interval number (A) and set the index value (E) of such block equal to the incremented value of the optimal interval number (A); detecting means responsive to the block index values (E) and responsive also to the optimal interval number (A) and to the complete-set interval numbers (B) for detecting a condition in which a particular block has been permitted by said predetermined replacement algorithm to remain continuously in the working memory in an unreferenced state during a plurality of successive intervals in the actual sequence of operations corresponding to at least N successive intervals in the optimal sequence, commencing with a complete-set interval; and means controlled by said detecting means when it has detected the occurrence of such a condition, and operable in the event that the processor again references said particular block before it leaves the working memory, to increment the current optimal interval number (A) without changing the current actual interval number (P), thereby effectively decrementing the count of unnecessary transfers (U) charged to said predetermined replacement algorithm.