Method for information retrieval in broadcast disk systems
First Claim
1. A method for information retrieval, wherein the information is broadcast in the form of pages, comprising the steps of:
- receiving a request for a first page;
labelling pages with first, second or third labels, wherein the first label designates pages more recently requested than the second label, and the second label designates pages more recently requested than the third label;
storing a broadcasted page in a fast memory when said broadcasted page is the requested first page, and labelling the broadcasted page with the first label, but only if the broadcasted page is not already stored in the fast memory; and
prefetching the broadcasted page when said broadcasted page is not the requested first page, said prefetching comprising storing said broadcasted page in the fast memory, but only if;
(i) the broadcasted page is not already stored in the fast memory; and
(ii) the broadcasted page is labelled with the second label.
5 Assignments
0 Petitions
Accused Products
Abstract
A paging method for information retrieval from broadcast disk systems is described. In response to a page request (e.g., a request for an item of data), the method selectively stores and evicts, in and from a fast memory, pages of data broadcasted by the broadcast disk system. The methods proceeds using a three-“color” labelling scheme, wherein the label assigned to a broadcasted page is based on how recently a given page was last requested. If a requested page is stored in fast memory, then the request is immediately served. If the requested page is not stored in fast memory, the request cannot be served until the requested page is broadcasted. While waiting for the requested page to be broadcasted, certain “somewhat-recently” requested pages are “prefetched,” wherein they are stored in fast memory even though there is no pending request for such pages. Since the size of the fast memory is very small compared to the amount of information being broadcasted, only a small amount of the available information can be stored and there will be significant turnover in the particular stored pages as a function of the page requests. Pages are selected for eviction based upon the “cost” (to the competitive performance of the method) to replace the evicted page, wherein the least costly page to replace is evicted. The present method achieves a bounded competitive ratio of O (n log k), where n is the number of pages being broadcasted and k is the size of the fast memory.
-
Citations
13 Claims
-
1. A method for information retrieval, wherein the information is broadcast in the form of pages, comprising the steps of:
-
receiving a request for a first page;
labelling pages with first, second or third labels, wherein the first label designates pages more recently requested than the second label, and the second label designates pages more recently requested than the third label;
storing a broadcasted page in a fast memory when said broadcasted page is the requested first page, and labelling the broadcasted page with the first label, but only if the broadcasted page is not already stored in the fast memory; and
prefetching the broadcasted page when said broadcasted page is not the requested first page, said prefetching comprising storing said broadcasted page in the fast memory, but only if;
(i) the broadcasted page is not already stored in the fast memory; and
(ii) the broadcasted page is labelled with the second label. - View Dependent Claims (2, 3, 4, 5, 6, 7)
selecting a page for eviction from the fast memory and evicting the selected page if the fast memory is full, wherein, only a page labelled with the second label is eligible for eviction.
-
-
4. The method of claim 3, wherein the selecting step comprises selecting that eligible page which would be least expensive to reload into the fast memory.
-
5. The method of claim 4, and further comprising the steps of:
-
relabelling all pages when the fast memory is full of pages labelled with the first label, wherein, (i) all pages having the second label are given, instead, the third label; and
(ii) all pages having the first label are given, instead, the second label.
-
-
6. The method of claim 2, wherein the step of serving the request further comprises the step of re-labelling the first page stored in fast memory with the first label if the stored first page has the second label.
-
7. The method of claim 1, wherein the step of receiving a request further comprises receiving a request for the first page from an applications software program.
-
8. A broadcast disk paging system, comprising:
-
a server operable to broadcast information organized into a plurality of equal-sized pages, and a client operable to receive the broadcasted pages of information, the client comprising;
means for receiving the broadcasted pages;
a fast memory;
selecting means for selecting pages to store in the fast memory in response to a request for a first page, said selecting means operable to;
(i) label pages with at least first or second labels, the first label designating pages more recently requested than the second label; and
(ii) prefetch a page labelled with the second label when said page is being broadcast, but only if said page is not the first requested page and said page is not stored in the fast memory. - View Dependent Claims (9, 10, 11, 12)
an appropriately-programmed general purpose processor;
a memory for storing the selecting means embodied as software; and
the fast memory, in which broadcasted pages are stored, wherein the processor is operable to run the selecting means and store pages in the fast memory.
-
-
12. The broadcast disk paging system of claim 11, wherein the client further comprises:
an applications software program stored in the memory.
-
13. A computer-readable storage medium comprising encoded computer-readable program instructions for use in conjunction with a programmable computer, which instructions cause the computer to selectively store information, in response to a request for a first page of information, wherein the information is stored in a fast memory that is in communication with the programmable computer, the instructions further operable to cause the computer to:
-
(i) label pages with at least first or second labels, the first label designating pages more recently requested than the second label; and
(ii) prefetch a page labelled with the second label when said page is being broadcast, but only if said page is not the first requested page and said page is not
-
Specification