`US 6,633,968 B2
`(10) Patent N0.:
`Zwiegincew et al. Oct. 14, 2003 (45) Date of Patent:
`
`
`
`U8006633968B2
`
`(54) PRE-FETCHING OF PAGES PRIOR TO A
`HARD PAGE FAULT SEQUENCE
`
`(75)
`
`Inventors: Arthur Zwiegincew, Kirkland, WA
`(US), James E. Walsh, Kirkland, WA
`(US)
`
`(73) Assignee: Microsoft Corporation, Redmond, WA
`(US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 416 days.
`
`(21) Appl. N0.: 09/794,851
`
`(22)
`
`Filed:
`
`Feb. 27, 2001
`
`(65)
`
`Prior Publication Data
`US 2002/0019723 A1 Feb. 14, 2002
`
`Related U.S. Application Data
`
`('63)
`
`Continuation—in—part of application No. 09/282,499, filed on
`Mar. 30, 1999, now Pat. No. 6,317,818.
`
`Int. Cl.7 ........... G06F 12/00
`('51)
`
`(52) U.S. Cl. ......................... 711/213
`(58) Field of Search ................................. 711/203, 204,
`711/209, 213, 217, 221; 712/207
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`................ 711/137
`9/1992 Blank et al.
`5,150,472 A *
`12/1997 Harrison, III et al.
`5,694,568 A
`7/1999 Drewry et al.
`5,925,100 A
`4/2000 Lewchuk
`6,047,363 A
`OTHER PUBLICATIONS
`
`An efirective onwhip preloading scheme to reduce data
`access penalty; Jean—Loup Baer and Tien—Fu Chen; Pro-
`ceedings of the 1991 conference on Supercomputing, 1991,
`pp. 176—186.
`
`Optimal prepaging and font caching; David R. Fuchs and
`Donald E. Knuth; ACM Trans. Program. Lang. Syst. 7, 1
`(Jan. 1985), pp. 62—79.
`An architecture for softwarewontrolled data prefetching;
`Alexander C. Klaiber and Henry M. Levy; Proceedings of
`the 18m annual
`international symposium on Computer
`architecture, 1991, pp. 43—53.
`An eflective programmable prefetch engine for on—chip
`caches; Tien—Fu Chen; Proceedings of the 28m annual
`international symposium on ,Microarchitecture, 1995, pp.
`237—242.
`
`(List continued on next page.)
`
`Primary Examiner—Kevin Verbrugge
`(74) Attorney, Agent, or Firm—Merchant & Gould
`
`(57)
`
`ABSTRACT
`
`Arnethod for pre-fetching of pages prior to a hard page fault
`sequence is described. A scenario file comprising a list of
`pages that need to be pre-fetched may be created. A scenario
`that requires pre-fetching may be automatically detected
`when process creation begins (such as at application startup
`or system boot). The scenario begins and it is determined
`whether or not a scenario file exists for the scenario. If not,
`the process continues (for example, the application is started
`up and run, the system is booted, etc.). If a scenario file does
`exist, the pages in the scenario file are pre-fetched to RAM.
`The process continues (application is started up and run, the
`system is booted, etc.). Pages that are used by the application
`are logged into a scenario log. The scenario log is also used
`to log page faults. An end scenario timer is started and it is
`determined whether a page fault (soft or hard) has been
`detected. Page faults are logged into memory (the scenario
`log) and the end scenario timer is reset each time a new page
`fault is encountered. If the end scenario timer has reached a
`predetermined threshold, the scenario ends and a work item
`is queued to post-process the scenario log and scenario file
`during idle time. The scenario file and scenario log are
`processed and an updated scenario file is written out to the
`disk space.
`
`19 Claims, 5 Drawing Sheets
`
`
`
`
`
`
`
`1
`
`Apple v. Realtime
`Proceeding No. |PR2016-01737
`APPLE 1038
`
`Apple v. Realtime
`Proceeding No. IPR2016-01737
`APPLE 1038
`
`1
`
`
`
`US 6,633,968 132
`Page 2
`
`OTHER PUBLICATIONS
`
`Modelling contention sensing memory management sys-
`tems—A VAX/VMS case study; C.P. Singer and P. Biswas;
`Mathematical and Computer Modelling, 1990, v.14, pp.
`184—189.
`
`Distributed, configurable memory management in an oper-
`ating system supporting quality of service; I. McDonald;
`Proceedings of the 7th IEEE Workshop on Future Trends of
`Distributed Computing Systems, 1999, pp. 191—196.
`
`On minimizing the number of page faults with complete
`information; T.F. Gonzales; 10th IMACS World Congress on
`System Simulation and Scientific Computation , 1982, pp.
`279—281, vol. 4.
`
`How to pack trees; J. Gil and A. Itai; Journal ofA lgorithms,
`1999, V.32, N2 (AUG) pp. 108—132.
`
`* cited by examiner
`
`2
`
`
`
`US. Patent
`
`m024a1LCO
`
`6m
`
`5f01
`
`US 6,633,968 B2
`
`S50362moi603
`{02:02wmr
`
`___________.____
`
`______._____u
`
`"O®E>mewmuEQ
`
`
`5334‘EDmmr899mmCEmEQO
`
`w:FNF
`
`mNr5.6.x
`
`
`
`©NrmO_m_
`
`mam.E296mm?
`
`
`
`EmemmcmS.\COEmE
`
`
`
`
`
`0:MN?9352Emhmoi
`
`
`
`
`
`NNrVNr‘\1EDM—
`
`
`
`>._oEws_Emuw>w
`
`
`
`fitmw$26026822
`
`meEmI
`
`momtmg
`
`$25
`
`cosmozqa<
`
`Emaoi
`
`3:622
`
`tBr
`
`mumtwt:
`
`
`
`
`
`ton.m>:n_xmfi025x20
`
`Ezano
`
`908mm
`
`EmogoxN:.-
`
`3:22I
`
`
`
`
`
`momtBEmothEmomth.
`
`
`
`EEmoicosmeaad.EmemmcmEEoEmE9:930w?umw
`
`
`
`
`
`$5822322EEmoEE936
`
`
`3
`
`
`
`
`
`
`
`
`
`
`
`US. Patent
`
`Oct. 14, 2003
`
`Sheet 2 0f 5
`
`US 6,633,968 B2
`
`I “\ 250
`
`7
`
`I
`
`Page Fault Scenario
`Detector
`
`“
`
`7
`
`,
`,/ K 240
`,,
`
`t
`
`7 7
`
`Page Fault Scenarlo
`Analyzer
`
`
`a 7’ 1
`
`l
`l
`
`Page FaultLog
`
`4
`fiFaultLogger
`
`270
`
`,
`
`l,
`
`“or 255
`
`l
`Y
`
`,
`
`7.7
`Pre-Fetcher
`
`l
`3
`
`Scenario
`FIIe
`
`245
`//
`777/ I
`
`‘
`
`
`
`:3
`
`
`
`
`
`”xx-7 205
`
`I
`
`W
`
`Ax 210
`
`!_l ,,
`Application Program
`Module
`
`
`
`T
`
`
`
`Memory Management Unit
`
`
`
`(7,!“
`
`I D
`
`isk Drive i
`H I,
`J
`
`
`
`L
`
`[VI/Rx 230
`V,
`
`Disk Storage
`
`Scenario File Defragger
`
`I 4
`
`Compressor/
`Decompressor J
`
`FIG. 2
`
`4
`
`
`
`US. Patent
`
`Oct. 14, 2003
`
`Sheet 3 0f5
`
`US 6,633,968 B2
`
`
`
`/'fl
`
`/I
`t
`
`Start
`\_\ 7“-
`
`\\
`\, 301
`l
`
`”//
`
`__.__Liw , 302
`Monitor Application
`Program Module for Page
`Fault Scenarios
`
`.7,,
`
`[V —_ 304
`Detect Page Fault
`l
`
`
`Scenario
`
`,7
`
`
`FCreate Scenario
`
`File
`
`300
`
`310
`
`308
`
`/ \,
`
`//,,
`
`
`
`\_ 306
`/
`.
`/
`.\
`,
`Analyze Page
`/" Scenario File \
`
`Fault Scenario
`\ Exists?
`\
`
`
`
`
`
`312
`
`Open Scenario File in Pre-
`Fetcher
`
`if,
`
`#47 ,
`
`314
`
`Allocate Memory Space in RAM
`for Copies of Memory Pages in
`Sequence File
`
`ff; ”l 316
`Transfer Copies of Memory
`Pages into RAM
`
`#ii 7 318
`
`Set Up Page Table Entries to .
`Reflect New Memory Page in
`RAM
`
`
`
`
`
`FIG. 3
`
`5
`
`
`
`US. Patent
`
`Oct. 14, 2003
`
`Sheet 4 0f5
`
`US 6,633,968 B2
`
`400
`
`440
`
`
`
`Detect Application Startup i
`
`i
`,/ \, 410
`_\
`
`/
`
`/'
`
`
`,x/Scenario File\\ N0
`_,_t\\
`Exists?
`,/
`
`]
`
`f 7,
`
`415
`
`Prefetch pages in scenario fiie‘
`,,
`
`,’Yf, ,
`
`420 i
`
`Run appiication
`
`,J
`
`,
`
`425
`
`1
`
`
`
`
`Start end scenario timer k #7 Reset end scenario
`
`timer
`
`/
`
`,,
`
`\
`
`430
`
`‘
`
`'< 435
`
`Log page fault into
`memory
`
`460
`
`FIG. 4
`
`
`/
`i
`/§eceived pag\e‘\ Yes
`‘
`*1,
`.
`2* Hr» }
`\~
`,/
`\
`\fauit Interrupt?/
`\\‘ /./
`gNo
`/,u’l \\\\
`'
`K]
`d \3‘45
`No/
`eceive _en \\\
`4(\
`scenario
`,2
`\ '
`'7 /
`\interrupt . /"
`\\_
`x//
`\/
`#55J 450
`End scenario; queue work item
`
`to post-process scenario file
`
`and scenario log
`455
`
`
`x
`
`/
`
`‘
`
`
`
`4"
`, Post-process the scenario file
`
`I
`and scenario log
`
`L;
`.
`,
`Write out new scenario
`file
`
`i
`
`6
`
`
`
`US. Patent
`
`Oct. 14, 2003
`
`Sheet 5 0f5
`
`US 6,633,968 B2
`
`/
`
`/
`
`/, (505
`
`v’
`
`,,
`,
`,
`3
`,,
`,,
`,‘
`,,
`,,
`,
`1
`,
`
`
`
`Nifn‘id’ lNilejid’}Needed/”:95?” Needed/ Needed! Nizdned/ ”mined,
`Needed/1
`Not
`lNileOdn'fd’
`Not
`Not
`Not
`”if?“
`
`
`
`‘
`l
`l
`-
`,
`l
`.
`-
`_
`_
`
`ReSldent Needed Resndent Needed ‘ Needed ‘ReSldent Resident Resudent‘Resident‘ReSIdent Resudent Resident Resldent needec ‘Resident
`
`
`7 be; a l
`i
`'7
`'
`' lg A; 'l‘
`,7
`l
`l
`‘
`
`
`
`l A l
`l
`l l l
`,,
`l
`
`l
`‘
`7"
`"7,,
`r“ I, ,r
`.L
`l
`l
`l
`l
`
`
`J
`,
`
`‘
`
`
`
`‘
`
`,
`
`‘
`
`\
`
`
`
`
`
`
`ll
`,«7
`7
`,._
`7
`77g“.
`“L7
`,
`,4“
`
`y
`,
`,
`, v
`,,
`,,
`,
`,
`v,
`,
`v
`v
`‘
`Allocated ‘ Allocated 1 Allocated
`Allocated
`Allocated
`Allocated
`Allocated 1
`‘
`Pree
`Pree
`,
`Pre-
`Pre-
`l
`by Pre-
`by Pre—
`by Pre»
`‘
`by Pre-
`by Pre-
`by Pre-
`l
`by Pre-
`‘ Dummy l
`t'
`E .
`t'
`E .
`t'
`E .
`t‘
`
`fetcher
`fetcher
`fetcher
`‘
`fetcher
`‘
`fetcher
`l
`fetcher
`‘
`fetcher
`Ex‘smg‘ X's mg
`“5mg
`X'smg
`A
`
`FIG. 5
`
`7
`
`
`
`US 6,633,968 B2
`
`1
`PRE-FETCHING OF PAGES PRIOR TO A
`HARD PAGE FAULT SEQUENCE
`
`REFERENCE TO RELATED APPLICATIONS
`
`This is a continuation-in-part of US. patent application
`Ser. No. 09/282,499, entitled “PRE-FETCHING OF PAGES
`PRIOR TO A HARD PAGE FAULT SEQUENCE”, filed
`Mar. 30, 1999, now US. Pat. No. 6,317,818, which is
`incorporated by reference herein.
`
`TECHNICAL FIELD
`
`This invention relates in general to the management of
`pages for improved performance of an application program
`module during hard page fault intensive scenarios. More
`particularly, the present invention relates to the reduction of
`hard page faults by pre-fetching pages into memory prior to
`the occurrence of a hard page fault sequence.
`
`BACKGROUND
`
`In a computer system, physical memory refers to a
`hardware device that is capable of storing information. In
`common usage, physical memory refers to semiconductor
`storage (RAM) that is connected to the processing unit of the
`computer system. Many modem processing units and oper-
`ating systems also support virtual memory. Virtual memory
`is a technique that allows smaller and/or partially simulated
`memory devices to be represented as a large uniform pri-
`mary memory source. In operation, application program
`modules access memory through virtual addresses, which
`are then mapped by the operating system in conjunction with
`a memory management unit (MMU) onto physical memory
`addresses.
`
`In the context of a paging memory system, a “page” is
`defined as a fixed-size block of bytes whose physical address
`can be changed via the MMU, working in conjunction with
`a Virtual Memory Manager. Apage is either mapped onto a
`physical address or is not present in RAM, in which case it
`is stored on a disk storage in a page file. A “hard page fault”
`is an exception that occurs when an application program
`module attempts to access a virtual memory page that is
`marked as being not present in RAM. When a hard page
`fault occurs, the Virtual Memory Manager must access disk
`storage to retrieve the data for the requested page.
`Application program modules are typically disk-bound. In
`other words, disk access and transfer times are limiting
`factors of the performance speed of an application program
`module. Disk access time refers to the time required by a
`disk drive to access disk storage and respond to a request for
`a data read or write operation. Therefore, the performance of
`an application program module is significantly limited dur-
`ing hard page fault intensive scenarios.
`There are various potential solutions to the performance
`bottleneck caused by disk access time during hard page fault
`scenarios. An obvious potential solution is to reduce disk
`access time. The reduction of disk access time is primarily
`a hardware consideration and is not easily accomplished.
`However, other potential solutions involve the manipulation
`of memory storage through software program modules.
`For example, one prior solution involves manipulating
`pages such that related blocks of memory are stored together
`on the same or an adjacent page. More specifically, appli-
`cation program module code is typically stored in pages in
`the order in which a compiler processed the source code, not
`in the order in which it will be executed. Therefore, when a
`page is accessed by an application program module, it is
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`likely that only a portion of the requested code is stored
`thereon and one or more hard page faults will occur to
`retrieve additional
`requested code from other pages.
`Manipulating the pages so that related code is stored on the
`same or adjacent pages reduces the number of pages
`required to execute the code and thus reduces hard page
`faults. Implementing this approach requires an extra per-
`application eifort. Also, it is not always possible to manipu-
`late code in pages in an efficient manner.
`Another prior solution involves strategically ordering
`pages in disk storage. According to this prior solution, the
`order in which pages will likely be accessed during typical
`usage of an application program is determined based on the
`assumption that disk access patterns are similar from run to
`run. Then, pages are stored in disk storage in the determined
`order. A strategic ordering of pages will result in a reduction
`of hard page fault times. However, this approach is some-
`what limited by the fact pages may be accessed more than
`once by an application program. Therefore, additional hard
`page faults may occur when a particular page must be
`re-retrieved from disk storage. Strategically ordering pages
`in disk storage tends to work best when it is employed to
`reduce hard page faults in a single hard page fault scenario,
`typically boot.
`Another prior technique to reduce the performance bottle-
`neck caused by disk access time during hard page fault
`scenarios involves decreasing the amount of pages associ—
`ated with an application program module. Reducing the
`number of pages containing code executed by an application
`program module necessarily reduces the number of hard
`page faults that may possibly occur during execution of the
`application program module. However,
`the reduction of
`memory associated with an application program module
`requires significant effort on the part of the programmer, or
`improvements in compiler technologies,
`to streamline the
`application program module. Also, end-users demand appli-
`cation program modules having extremely robust function-
`ality and complex graphics capabilities. Thus, it is becoming
`increasingly more difficult
`to streamline application pro-
`gram modules while meeting market demands.
`Thus, there remains a need for a method and system for
`improving the performance of an application program mod—
`ule by reducing disk access time without burdening the
`programmer.
`There further remains a need in the art for a method and
`
`system for reducing hard page faults during execution of an
`application program module without detracting from the
`robustness of the application program module.
`SUMMARY OF THE INVENTION
`
`The present invention meets the needs described above by
`providing a system and method for improving the perfor-
`mance of an application program module by reducing the
`occurrence of hard page faults during the operation of an
`application program module. The present invention may be
`embodied in an add-on software program module that oper-
`ates m conjunction with the application program module. In
`this manner, no effort is required on the part of the appli-
`cation programmer to manipulate or modify the application
`program module in order
`to improve performance.
`Furthermore, the add-on software program module does not
`detract from the intended operation of the application pro-
`gram module.
`invention is a method for
`the present
`In one aspect,
`avoiding hard page faults during the booting of an operating
`system of a computer system. Prior to booting the operating
`
`8
`
`
`
`US 6,633,968 B2
`
`3
`is determined which pages will need to be
`it
`system,
`retrieved from disk. When the operating system needs to be
`booted, the determined pages are loaded into a RAM of the
`computer system, whereby the determined pages will be
`available in the RAM and hard pages faults will not occur
`during the booting of the operating system. The step of
`determining which pages will be retrieved from disk may
`include creating a log of hard page faults that occur during
`the booting of the operating system, analyzing the log to find
`a common hard page fault scenario for booting the operating
`system, and determining from the log which pages were
`retrieved from disk during the common hard page fault
`scenario. A copy of each of the determined pages may be
`stored in a scenario file. Alternatively, a reference for each
`of the determined pages may be stored in a referenced
`scenario file.
`
`As described above, the scenario file may be a referenced
`scenario file including a number of page references wherein
`each page reference includes a reference to section infor-
`mation (file name and whether the file is mapped as data or
`as an image) and a file offset for the referenced page.
`Alternatively, each page reference may include a physical
`disk sector for the page. The section information table that
`the page references refer to, is also stored in the scenario file.
`In yet another aspect,
`the invention is a method for
`automatically detecting a hard page fault scenario. The
`start—up of an application program module is detected and
`the hard page fault scenario begins. It is determined if a
`scenario file exists. If not, then the application program
`module is run and a scenario file is created. If a scenario file
`
`already exists, then the pages in the scenario file are fetched
`into RAM and the application program module is run. When
`the application begins to run, an end scenario timer is started
`and soft page faults and hard page faults are logged. Each
`time a page fault is logged, the end scenario timer is reset.
`If the time period between two page faults is such that the
`end scenario timer reaches a predetermined threshold, then
`the hard page fault scenario is ended.
`A queue may generate a work item to post—process the
`scenario file and scenario log. During idle time, the scenario
`file and scenario log may be post-processed. A scenario file
`may then be written to the disk space.
`As part of post-processing the scenario file and scenario
`log,
`it may be determined which pages are part of the
`scenario log and not already in the scenario file. These pages
`are added to the scenario file. Scenario file entries corre-
`sponding to pages that were used during the scenario are
`updated to indicate that the page was used by the scenario.
`Scenario file entries for pages that have not been used for a
`predetermined number of times are deleted from the sce-
`nario file. The scenario file entries may then be sorted
`according to the section ID and file offset of each page
`represented by each scenario file entry.
`In another aspect, the invention is a method for detecting
`a hard page fault scenario. The start-up of an application
`program module is detected and it is determined whether a
`scenario file exists. If a scenario file exists, then the pages in
`the scenario file are pre-fetched into RAM and the applica-
`tion program module is run. Any soft page faults or hard
`page faults are logged into memory. The hard page fault
`scenario may end when a Win32 hourglass cursor is replaced
`with a regular cursor.
`the invention is a method for
`In still another aspect,
`building a plurality of memory descriptor lists (MDLs) for
`mapping to physical memory a plurality of pages referenced
`in a scenario file.
`It
`is determined whether each page
`
`10
`
`15
`
`'
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`referenced in the scenario file is already resident in physical
`memory and, if so,
`then these pages are discarded from
`consideration. For all pages not resident in physical memory,
`it
`is determined whether the file offsets for each pair of
`consecutive pages is below a predetermined level and if so,
`then the pages are put into the MDL. If the pages are not
`consecutive,
`the gap between the pages is plugged by
`inserting a required number of dummy pages into the MDL.
`These and other aspects, features and advantages of the
`present
`invention may be more clearly understood and
`appreciated from a review of the following detailed descrip-
`tion of the disclosed embodiments and by reference to the
`appended drawings and claims.
`BRIEF DESCRIPTION OF THE FIGURES
`
`FIG. 1 is a block diagram of a personal computer illus-
`trating an operating environment for an exemplary embodi-
`ment of the present invention.
`FIG. 2 is a functional block diagram illustrating operation
`of an exemplary embodiment of the present invention.
`FIG. 3 is a flow diagram illustrating operation of an
`exemplary embodiment of the present invention.
`FIG. 4 is a flow diagram illustrating a method for auto-
`matic scenario detection in accordance with an embodiment
`of the present invention.
`FIG. 5 is a diagram illustrating a plurality of memory
`pages being mapped to physical memory in accordance with
`an embodiment of the present invention.
`DETAILED DESCRIPTION OF EMBODIMENTS
`OF THE INVENTION
`
`The present invention is directed to a system and method
`for managing pages in order to improve the performance of
`an application program module or an operating system
`during hard page fault scenarios. The present invention is
`operable to detect and analyze a potential hard page fault
`scenario. In analyzing the potential hard page fault scenario,
`the present invention determines which pages will have to be
`retrieved from disk upon the occurrence of a hard page fault
`sequence. Then, prior to the occurrence of the potential hard
`page fault sequence, the present invention pre-fetches into
`RAM most, if not all, of the determined pages. Accordingly,
`no hard page fault will occur when the application program
`module or operating system attempts to access the deter-
`mined pages. Thus, the performance speed of the application
`program module or operating system is improved due to
`fewer disk seeks. Those skilled in the art should appreciate
`that the definition of a hard page fault scenario is arbitrary,
`i.e., a single lengthy scenario could be ‘split’ into multiple
`smaller scenarios. Thus, pages may be pre-fetched in
`segments, one segment per ‘smaller’ scenario, resulting in a
`spreading out of the demand for a single large amount of
`memory in which to read the prefetched pages.
`A hard page fault occurs when a page requested by the
`application program or operating system is not available in
`RAM. The order in which pages are likely to be requested
`in a particular hard page fault scenario is determined. A
`referenced scenario file is created to store a list of the
`determined pages. A pre-fetcher is used to load an appro-
`priate scenario file into RAM prior to the occurrence of a
`particular hard page fault sequence. Then, during the par-
`ticular hard page fault scenario, the requested pages will be
`found on the hard disk and passed into RAM before a hard
`page fault occurs.
`
`Exemplary Operating Environment
`The following description will hereinafter refer to the
`drawings,
`in which like numerals indicate like elements
`
`9
`
`
`
`US 6,633,968 B2
`
`5
`throughout the several figures. FIG. 1 and the following
`discussion are intended to provide a brief and general
`description of a suitable computing environment 100 for
`implementation of the present invention. The exemplary
`operating environment 100 includes a conventional personal
`computer system 120, including a processing unit 121, a
`system memory 122, and a system bus 123 that couples the
`system memory 122 to the processing unit 121. The system
`memory 122 includes read only memory (ROM) 124 and
`random access memory (RAM) 125. A basic input/output
`system 126 (BIOS), containing the basic routines that help
`to transfer information between elements within the personal
`computer system 120, such as during start-up, is stored in
`ROM 124.
`
`10
`
`15
`
`The personal computer system 120 further includes a hard
`disk drive 127, a floppy disk drive 128, e.g., to read from or
`write to a removable magnetic disk 129, and an optical disk
`drive 130, e.g., for reading a CD-ROM disk 131 or to read
`from or write to other optical media. The hard disk drive
`127, removable magnetic disk drive 128, and optical disk .
`drive 130 are connected to the system bus 123 by a hard disk
`drive interface 132, a removable magnetic disk drive inter-
`face 133, and an optical drive interface 134, respectively.
`The drives and their associated computer-readable media
`provide nonvolatile storage for the personal computer sys-
`tem 120. Although the description of computer-readable
`mcdia abovc refers to a hard disk, a removable magnetic
`disk and a CD-ROM disk, it should be appreciated by those
`skilled in the art that other types of media that are readable
`by a computer system, such as magnetic cassettes, flash
`memory cards, digital video disks, Bernoulli cartridges, and
`the like, may also be used in the exemplary operating
`environment.
`
`25
`
`30
`
`The computer system 120 may include additional input
`devices (not shown), such as a microphone, joystick, game
`pad, satellite dish, scanner, or the like. These and other input
`devices are often connected to the processing unit 121
`through a serial port interface 146 that is coupled to the
`system bus 123, but may be connected by other interfaces,
`such as an IEEE 1394 bus or a universal serial bus (USB).
`A monitor 147 or other type of display device is also
`connected to the system bus 123 via an interface, such as a
`video adapter 148. In addition to the monitor, personal
`computer systems typically include other peripheral output
`devices (not shown), such as speakers or printers.
`The personal computer system 120 may operate in a
`networked environment using logical connections to one or
`more remote computer systems, such as a remote computer
`system 149. The remote computer system 149 may be a
`server, a router, a peer device or other common network
`node, and typically includes many or all of the elements
`described relative to the personal computer system 120,
`although only a memory storage device 150 has been
`illustrated in FIG. 1. The logical connections depicted in
`FIG. 1 include a local area network (LAN) 151 and a wide
`area network (WAN) 152. Such networking environments
`are commonplace in oflices, enterprise-wide computer
`networks, intranets and the Internet.
`When used in a LAN networking environment, the per-
`sonal computer system 120 is connected to the LAN 151
`through a network interface 153. When used in a WAN
`networking environment, the personal computer system 120
`typically includes a modem 154 or other means for estab-
`lishing communications over a WAN 152, such as the
`Internet. The modem 154, which may be internal or external,
`is connected to the system bus 123 Via the serial port
`interface 146. In a networked environment, program mod-
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`10
`
`6
`ules depicted relative to the personal computer system 120,
`or portions thereof, may be stored in the remote memory
`storage device 150. It will be appreciated that the network
`connections shown are exemplary and other me ans of estab-
`lishing a communications link between the computer sys-
`tems may be used. It will be further appreciated that the
`invention could equivalently be implemented on host or
`server computer systems other than personal computer
`systems, and could equivalently be transmitted to the host
`computer system by means other than a CD-ROM,
`for
`example, by way of the network connection interface 153.
`Anumber of program modules may be stored in the drives
`and RAM 125 of the computer system 120. Program mod-
`ules control how the computer system 120 functions and
`interacts with the user, with I/O devices or with other
`computers. Program modules comprise routines, data struc-
`tures and other software or firmware components. Examples
`of program modules are operating systems 135 and appli-
`cation program modules 138. In an exemplary embodiment,
`the present invention may comprise one or more memory
`management program modules 137 stored on the drives or
`RAM 125 of the computer 100. Specifically, program mod-
`ules 137 of the present invention may comprise computer
`implemented instructions for determining which pages will
`have to be retrieved from disk during a potential hard page
`fault scenario and pre-fetching the determined pages into
`RAM prior to the occurrence of the potential hard page fault
`sequence.
`Those skilled in the art will appreciate that the invention
`may be practiced with other computer system
`configurations, including hand-held devices, multiprocessor
`systems, microprocessor-based or programmable consumer
`electronics, minicomputers, mainframe computers, and the
`like. The invention may also be practiced in distributed
`computing environments where tasks are performed by
`remote processing devices that are linked through a com-
`munications network.
`In a distributed computing
`environment, program modules may be located in both local
`and remote memory storage devices.
`FIG. 2 is a functional block diagram illustrating operation
`of an exemplary embodiment of the present invention. As
`shown, an application program module 205 interacts with a
`virtual memory device 210 to access data stored in pages. It
`should be understood that the application program module
`205 may instead be an operating system.
`The virtual memory device 210 communicates with a
`memory management unit (MMU) 215, which maps virtual
`memory addresses onto physical memory addresses in the
`RAM 220 of the computer system. The MMU, which is a
`well known device, maintains a record of pages present in
`the RAM 220. An MMU includes a lookaside cache;
`requests for pages not recorded by the MMU are redirected
`to a VMM (not shown). When the requested pages are not
`present in the RAM 220, they must be retrieved from disk
`storage 230. In such a situation, the VMM instructs a disk
`drive 225 to transfer the requested pages into the RAM 220.
`Typically, the requested pages are swapped with less used
`pages in the RAM 220. Accordingly, the least recently used
`pages are stored on the disk storage 230 and the VMM
`updates its records to reflect the new pages in the RAM 220.
`Swapping is a memory management technique that is well
`known in the art. Those skilled in the art will appreciate that
`the above description of memory management has been
`provided by way of example only and that other algorithms
`may be, and often are, employed.
`A hard page fault scenario analyzer 240 anticipates and
`analyzes hard page fault scenarios. As mentioned, a hard
`
`10
`
`
`
`US 6,633,968 B2
`
`7
`page fault scenario is a situation in which a hard page fault
`sequence is highly likely to occur. The hard page fault
`scenario analyzer logs various hard page fault scenarios that
`occur during operation of the application program module
`205. The logged hard page fault scenarios are then analyzed
`to determine if they re-occur frequently, and if they do, they
`are put in a scenario file. This analysis can occur program-
`matically on the end-user’s computer system, or in advance
`by the developer of a particular software product. As an
`example, suppose the application program module 205 is a
`word processor and that an anticipated hard page fault
`scenario is the situation in which the user selects a well
`known “file open” command. In response to the “file open”
`command, the application program will display a graphical
`representation of a file directory. However,
`in order to
`display the graphical representation of the file directory, a
`sequence of hard page faults will occur because the word
`processor must retrieve a particular set of pages from disk.
`In accordance with an exemplary embodiment of the present
`invention, the hard page fault scenario analyzer 240 antici-
`pates the “open file” hard page fault scenario of the example
`and determines the set of pages that will need to be retrieved
`from disk upon the occurrence of the hard page fault. The
`determination of pages that will need to be retrieved from
`disk will be described in greater detail below. The detection
`of particular classes of hard page fault scenarios may be built
`into the system. For example, application launch is virtually
`always a hard page fault scenario, so an exemplary embodi-
`ment of the present invention may be configured such that
`any launch operation of an application program will be
`considered to be a hard page fault scenario.
`Based on the determined pages,
`the hard page fault
`scenario analyzer 240 creates a scenario file 245, which is
`stored in the disk storage 230. The scenario file 245 may
`comprise ordered copies of the pages that will
`likely be
`retrieved from disk due to one or more hard page faults
`during the hard page fault scenario. The scenario file 245
`may comprise multiple copies of a single page. Similarly,
`multiple scenario files may include copies of the same pages.
`In this manner, the copies of the pages may be transferred
`into RAM 220 from the scenario file 245 in the appropriate
`order without
`the occurrence of a hard page fault. The
`transfer of the copies of pages into RAM is discussed below.
`In one embodiment of the present invention, the scenario
`file 245 may be a referenced scenario file comprising
`ordered references to the pages that are likely to be retrieved
`from disk storage 230 during a hard page fault scenario,
`rather than copies of the actual pages themselves.
`In
`response to the detection of a begin-of—scenario instruction
`or a hard page fault scenario, the pages referenced in the
`scenario file are fetched from disk storage in the optimal
`manner and are transferred into RAM. In this manner, the
`requested pages will be available in RAM when requested,
`and no hard page fault will occur. This exemplary embodi-
`ment of the invention will result in more seek operations on
`disk, but will still allow reading of the required pages in an
`optimal manner, rather than the ‘as needed” ordering if the
`pages are hard faulted into RAM. As compared to a scenario
`file 245 comprising ordered copies of the determined pages,