System and method for evaluating paging behavior

Claim 3

In a data processing apparatus which is operated as a paging machine and wherein a program is considered as a page reference string, said data processing apparatus including primary storage for containing a portion, m, of the pages of said program and secondary storage for containing the remainder (n-m) of the pages of the program wherein n is the total number of pages in said program, means responsive to the occurrence of a page exception for effecting the exchange of a page in primary storage for the page in secondary storage causing said exception, means for maintaining a first list of the names of the pages of said program weighted in accordance with a least recently used (LRU) criterion, said first list being constituted by the names of said pages and (LRU) weighing integers respectively having one of the different discrete values of 1 to n, associated with each of said names according to said criterion, said first list comprising a first portion comprising means for containing the names of those pages in primary storage and having LRU weightings of 1 to m and the respective LRU integers associated therewith, and a second portion comprising the names of the remaining pages of said program and which have the LRU weightings of (m+1) to n and their respective integers in a location in said storage, said data processing apparatus further including means for effecting changes of information in said first and second portions of said first list, a system for determining the minimum memory capacities (MMC) for the pages of said page reference string comprising: means for maintaining a second list of said names, said second list being constituted by an ordered sequence of 1st to nth addresses, there being located at each of said addresses a different integer, C, from which the minimum memory capacity (MMC) of a page can be determined, each of said integers, C, of said second list having a different discrete value of 1 to n; means responsive to said means for maintaining said second list for determining said minimum memory capacity of a given referenced page comprising; means responsive to the referencing of said given page for dividing said second list into a first group of addresses having the values of 1 to (l-1), respectively, and a second group of addresses having the values of l to m, respectively, wherein l is equal to the LRU integer associated with said given referenced page, means responsive to said means for dividing said second list for determining the address, k, in said second group having the lowest value integer, C, in said second group, means responsive to said means for determining said address, k, for marking the series of addresses in said second group included in the subgroup containing the addresses l, (l+1), . . . , (k-1), which have the following values, viz. l, (l+a), (l+b), (l+c), . . . , up to address (k-1), if necessary, wherein (l+a) has the smallest address value greater than l such that C(l+a) < C(l), wherein (l+b) has the smallest address value greater than (l+a) such that C(l+b) < C(l+a), etc., wherein C(i) is the integer, C, address , means responsive to said means for dividing said second list for incrementing each of the addresses 2 to (l-1) in said first group by 1 to constitute the addresses 3 to l, means responsive to said means for determining said address, k, for assigning the address value of 2 to said smallest integer originally at address k, said smallest integer being said minimum memory capacity of said given referenced page, and means responsive to said means for assigning said address value of 2 for respectively assigning to each of the series of said marked addresses, of said second group, the value of the next address in said series, the highest value address in said series being assigned a value of k, said means in said data processing apparatus for effecting changes of information as in said first and said second portions of said first list, in response to the occurrence of said page exception, a. placing the page name of said page causing said exception into said first portion and assigning it the LRU integer of one; b. transferring the page name which had the LRU integer of m associated therewith immediately prior to the occurrence of said page exception into said second portion of said first list and assigning it the LRU integer of (m+1); c. respectively incrementing by one all of those LRU integers in said first portion which, immediately prior to the occurrence of said page exception, had the LRU values of 1 to (m-1); d. respectively incrementing by one those LRU PG,91 integers in said second portion which immediately prior to the occurrence of said page exception had values of (m+1) to one less than the value of the LRU integer associated with the page causing the exception.

Claim 4

In a data processing apparatus which is operated as a paging machine and wherein a program is considered as a page reference string, said data processing apparatus including primary storage for containing a portion, m, of the pages of said program and secondary storage for containing the remainder (n-m) of the pages of the program wherein n is the total number of pages in said program, means responsive to the occurrence of a page exception for effecting the exchange of a page in primary storage for the page in secondary storage causing said exception, means for maintaining a first list of the names of the pages of said program weighted in accordance with a least recently used (LRU) criterion, said first list being constituted by the names of said pages and (LRU) weighing integers respectively having one of the different discrete values of 1 to n, associated with each of said names according to said criterion, said first list comprising a first portion comprising means for containing the names of those pages in primary storage and having LRU weightings of 1 to m and the respective LRU integers associated therewith, and a second portion comprising the names of the remaining pages of said program and which have the LRU weightings of (m+1) to n and their respective integers in a location in said storage, said data processing apparatus further including means for effecting changes of information in said first and second portions of said first list, a system for determining the minimum memory capacities (MMC) for the pages of said page reference string comprising: means for maintaining a second list of said names, said second list being constituted by an ordered sequence of 1st to nth addresses, there being located at each of said addresses a different integer, C, from which the minimum memory capacity (MMC) of a page can be determined, each of said integers, C, of said second list having a different discrete value of 1 to n; means responsive to said means for maintaining said second list for determining said minimum memory capacity of a given referenced page comprising; means responsive to the referencing of said given page for dividing said second list into a first group of addresses having the values of 1 to (l-1), respectively, and a second group of addresses having the values of l to m, respectively, wherein l is equal to the LRU integer associated with said given referenced page, means responsive to said means for dividing said second list for determining the address, k, in said second group having the lowest value integer, C, in said second group, means responsive to said means for determining said address, k, for marking the series of addresses in said second group included in the subgroup containing the addresses l, (l+1), . . . , (k-1), which have the following values, viz. l, (l+a), (l+b), (l+c), . . . , up to address (k-1), if necessary, wherein (l+a) has the smallest address value greater than l such that C(l+a) < C(l), wherein (l+b) has the smallest address value greater than (l+a) such that C(l+b) < C(l+a), etc., wherein C(i) is the integer, C, address , means responsive to said means for dividing said second list for incrementing each of the addresses 2 to (l-1) in said first group by 1 to constitute the addresses 3 to l, means responsive to said means for determining said address, k, for assigning the address value of 2 to said smallest integer originally at address k, said smallest integer being said minimum memory capacity of said given referenced page, and means responsive to said means for assigning said address value of 2 for respectively assigning to each of the series of said marked addresses, of said second group, the value of the next address in said series, the highest value address in said series being assigned a value of k, said means in said data processing apparatus for effecting changes of information as in said first and said second portions of said first list, in response to the occurrence of said page exception, a. placing the page name of said page causing said exception into said first portion and assigning it the LRU integer of one; b. transferring the page name which had the LRU integer of m associated therewith immediately prior to the occurrence of said page exception into said second portion of said first list and assigning it the LRU integer of (m+1); c. respectively incrementing by one all of those LRU integers in said first portion which, immediately prior to the occurrence of said page exception, had the LRU values of 1 to (m-1); d. respectively incrementing by one those LRU PG,91 integers in said second portion which immediately prior to the occurrence of said page exception had values of (m+1) to one less than the value of the LRU integer associated with the page causing the exception.

Claim 5

In a data processing apparatus as defined in claim 2 wherein: said first portion of said first list comprises a first stack of at least m registers, each of said registers being capable of having contents of at least m, and means for incrementing said contents of said registers; and wherein said second list comprises a second stack of, at least, n registers, each of said registers of said second stack being capable of having contents of the value of at least n, and means for shifting the contents of the registers in said second stack into any of the other registers of said stack.

Claim 6

In a data processing apparatus which is operated as a paging machine and wherein a program is considered as a page reference string, said data processing apparatus including primary storage for containing portion, m, of the pages of said program and secondary storage for containing the remainder, (n-m), of the pages of said program, and means responsive to the occurrence of a page exception for effecting the exchanging of a page in primary storage for the page in secondary storage causing said page exception, a system for determining the minimum memory capacities (MMC) for the pages of said page reference string comprising: means for maintaining a first list of the names of the pages of said program weighted in accordance with at least recently used (LRU) criterion, said first list being constituted by the names of said pages and least recently used (LRU) weighting integers respectively having one of the different discrete values of 1 to n, associated with each of said names according to said criterion, said first list comprising a first portion comprising means for containing the names of those pages in primary storage having associated LRU weightings of 1 to m and the respective LRU weighting integers associated therewith, and a second portion comprising the names of the remaining pages of said program and which have the LRU weightings of (m+1) to n and their respective associated LRU weighting integers in a location in said storage; means in circuit with said means for maintaining said first list for effecting changes of information in said first and second portions of said first list; means responsive to said means for maintaining said first list for maintaining a second list of said names, said second list being constituted by an ordered sequence of 1st to nth addresses, there being located at each of said addresses a different integer, C, from which the minimum memory capacity (MMC) of a page can be determined, each of said integers, C, of said list having a different discrete value of 1 to n; means for determining said minimum memory capacity of a given referenced page comprising; means responsive to the referencing of said given page for dividing said second list into a first group of addresses having the values of 1 to (l-1), respectively, and a second group of addresses having the values of l to m, respectively, wherein l is equal to the LRU integer associated with said given referenced page; means responsive to said means for dividing said second list for determining the address, k, in said second group having the lowest value integer, C; means responsive to the determining of said address, k, for marking the series of addresss in said second group included in the subgroup containing the addresses l, (l+1), . . . , (k-1) which have the following values, viz. l, (l+a), (l+b), (l+c), . . . , up to address (k-l), if necessary, wherein (l+a) has the smallest address value greater than l such that C(l+a) < C(l), wherein (l+b) has the smallest address value greater than (l+a), such that C(l+b) < C(l+a), etc. wherein C(i) is the integer, C, at address , means responsive to said means for marking said series of addresses for respectively shifting down by one of the contents at addresses 2 to (l-1) in said first group, means responsive to said means for marking said series of addresses for shifting the contents at said address, k, i.e. said smallest integer, to address 2, said smallest integer being said minimum memory capacity of said given referenced page, and means responsive to said means for marking said series of addresses for respectively shifting the contents of each of the series of said marked addresses of said second group into the next address in said series, the contents of the highest value address in said series being shifted to address k, said means for effecting changes of information in said first and second portions of said first list, in response to the occurrence of said page exception, including means for a. placing the page name of said page causing said exception into said first portion of said first list and assigning to it the LRU integer of one; b. transferring the page name which had the LRU integer of m associated therewith immediately prior to the occurrence of said page exception into said second portion of first list and assigning to it the LRU integer of (m+1); c. respectively incrementing by one all of those LRU integers in said first portion which immediately prior to the occurrence of said page exception had the LRU values of 1 to (m-1); and d. respectively incrementing by one those LRU integers in said second portion which immediately prior to the occurrence of said page exception had values of (m+1) to one less than the value of the LRU integer associated with the page causing the exception.

Claim 7

In a data processing apparatus which is operated as a paging machine and wherein a program is considered as a page reference string, said data processing apparatus including primary storage for containing portion, m, of the pages of said program and secondary storage for containing the remainder, (n-m), of the pages of said program, and means responsive to the occurrence of a page exception for effecting the exchanging of a page in primary storage for the page in secondary storage causing said page exception, a system for determining the minimum memory capacities (MMC) for the pages of said page reference string comprising: means for maintaining a first list of the names of the pages of said program weighted in accordance with at least recently used (LRU) criterion, said first list being constituted by the names of said pages and least recently used (LRU) weighting integers respectively having one of the different discrete values of 1 to n, associated with each of said names according to said criterion, said first list comprising a first portion comprising means for containing the names of those pages in primary storage having associated LRU weightings of 1 to m and the respective LRU weighting integers associated therewith, and a second portion comprising the names of the remaining pages of said program and which have the LRU weightings of (m+1) to n and their respective associated LRU weighting integers in a location in said storage; means in circuit with said means for maintaining said first list for effecting changes of information in said first and second portions of said first list; means responsive to said means for maintaining said first list for maintaining a second list of said names, said second list being constituted by an ordered sequence of 1st to nth addresses, there being located at each of said addresses a different integer, C, from which the minimum memory capacity (MMC) of a page can be determined, each of said integers, C, of said list having a different discrete value of 1 to n; means for determining said minimum memory capacity of a given referenced page comprising; means responsive to the referencing of said given page for dividing said second list into a first group of addresses having the values of 1 to (l-1), respectively, and a second group of addresses having the values of l to m, respectively, wherein l is equal to the LRU integer associated with said given referenced page; means responsive to said means for dividing said second list for determining the address, k, in said second group having the lowest value integer, C; means responsive to the determining of said address, k, for marking the series of addresss in said second group included in the subgroup containing the addresses l, (l+1), . . . , (k-1) which have the following values, viz. l, (l+a), (l+b), (l+c), . . . , up to address (k-l), if necessary, wherein (l+a) has the smallest address value greater than l such that C(l+a) < C(l), wherein (l+b) has the smallest address value greater than (l+a), such that C(l+b) < C(l+a), etc. wherein C(i) is the integer, C, at address , means responsive to said means for marking said series of addresses for respectively shifting down by one of the contents at addresses 2 to (l-1) in said first group, means responsive to said means for marking said series of addresses for shifting the contents at said address, k, i.e. said smallest integer, to address 2, said smallest integer being said minimum memory capacity of said given referenced page, and means responsive to said means for marking said series of addresses for respectively shifting the contents of each of the series of said marked addresses of said second group into the next address in said series, the contents of the highest value address in said series being shifted to address k, said means for effecting changes of information in said first and second portions of said first list, in response to the occurrence of said page exception, including means for a. placing the page name of said page causing said exception into said first portion of said first list and assigning to it the LRU integer of one; b. transferring the page name which had the LRU integer of m associated therewith immediately prior to the occurrence of said page exception into said second portion of first list and assigning to it the LRU integer of (m+1); c. respectively incrementing by one all of those LRU integers in said first portion which immediately prior to the occurrence of said page exception had the LRU values of 1 to (m-1); and d. respectively incrementing by one those LRU integers in said second portion which immediately prior to the occurrence of said page exception had values of (m+1) to one less than the value of the LRU integer associated with the page causing the exception.

Claim 8

In a data processing apparatus as defined in claim 4 wherein: said first portion of said first list comprises a first stack of at least m registers, each of said registers being capable of having contents of the value of at least m, and means for incrementing said contents of said registers; and wherein said second list comprises a second stack of, at least, n registers, each of said registers of said second stack being capable of having contents of the value of at least n, and means for shifting the contents of the registers in said second stack into any of the other registers of said stack.