Caching virtual memory locks - Patent Review 5983329

We claim:

1. A computer-implemented method of placing a lock upon a region of physical memory within a computer system in response to an input/output (I/O) request, the method comprising:

receiving a virtual memory I/O request that includes a virtual address range corresponding to a region in virtual memory of the computer system, the virtual memory being distinct from the physical memory and the computer system having a facility for creating a plurality of range locks, each range lock representing corresponding pages of virtual memory that are present in the physical memory and that are locked in the physical memory, the virtual memory I/O request normally resulting in a virtual memory lock occurring;

identifying a virtual page range that includes the requested virtual address range and identifies at least one page of virtual memory;

determining whether a range lock exists that represents the identified virtual page range; and

wherein when it is determined that a range lock exists that represents the identified virtual page range, the method further comprises incrementing a usage counter associated with the range lock in order to indicate that the I/O request is now outstanding for the identified virtual page range, the usage counter indicating the number of outstanding I/O requests for the virtual page range and the range lock existing when the usage counter is greater than or equal to zero, whereby a virtual memory lock is avoided for a subsequent virtual memory I/O request for the virtual address range.

2. A method as recited in claim 1 wherein when it is determined that a range lock does not exist that represents the virtual page range, the method further comprises the steps of:

applying a virtual memory lock function to the virtual page range in order to lock the pages of virtual memory that are identified by the virtual page range in the physical memory;

creating a first range lock that represents the virtual page range.

3. A method as recited in claim 2 wherein the first range lock includes a physical page list pointer that indicates the physical pages in physical memory corresponding to the virtual page range and the method further comprises the step of returning the physical page list pointer.

4. A method as recited in claim 1 wherein the plurality of range locks in the computer system are organized using a hash table having a plurality of buckets, each bucket being arranged to indicate a distinct subset of the plurality of range locks, and the step of determining whether a range lock exists includes the sub-steps of:

computing a hash function based at least partially upon a portion of the requested virtual address range, the hash function returning a hash function result indicating one of the plurality of buckets; and

searching a first subset of the plurality of range locks corresponding to the bucket indicated by the hash function result.

5. A computer-implemented method of placing a lock upon a region of physical memory within a computer system in response to an input/output (I/O) request, the method comprising:

receiving a virtual memory I/O request that includes a virtual address range corresponding to a region in virtual memory of the computer system, the virtual memory being distinct from the physical memory and the computer system having a virtual memory lock function operative to lock pages of virtual memory in the physical memory of the computer system, the computer system also having a facility for creating a plurality of range locks, each range lock representing corresponding pages of virtual memory that are present in the physical memory and that are locked in the physical memory, the virtual memory I/O request normally resulting in a virtual memory lock occurring;

identifying a virtual page range that includes the requested virtual address range and identifies at least one page of virtual memory;

determining whether a range lock exists that represents the identified virtual page range, wherein when it is determined that a range lock does not exist that represents the virtual page range, the method further comprises,

applying the virtual memory lock function to the virtual page range in order to lock the pages of virtual memory that are identified by the virtual page range in the physical memory, the virtual memory lock function being operative to force a continuous assignment of a first group of physical memory pages to the pages of virtual memory that are identified by the virtual page range on a one-to-one basis, and

creating a first range lock that represents the virtual page range, the first range lock having a usage counter indicating the number of outstanding I/O requests for the virtual page range and the first range lock existing when the usage counter is greater than or equal to zero, whereby a virtual memory lock is avoided for a subsequent virtual memory I/O request for the virtual address range.

6. A method as recited in claim 5 wherein the step of applying a virtual memory lock function further includes the sub-steps of:

determining whether a set of pages of virtual memory included within the virtual page range have already been locked into physical memory by the virtual memory lock function; and

wherein when it is determined that a set of pages of virtual memory included within the virtual page range have already been locked into physical memory, the step of applying a virtual memory lock function operates to avoid locking the set of pages that have already been locked.

7. A method as recited in claim 5 further including the step of determining whether the step of applying a virtual memory lock function has succeeded.

8. A method as recited in claim 5 wherein the first range lock includes a physical page list pointer that indicates the physical pages in physical memory corresponding to the virtual page range and the method further comprises the step of returning the physical page list pointer.

9. A method as recited in claim 5 wherein the plurality of range locks in the computer system are organized using a hash table having a plurality of buckets, each bucket arranged to indicate a distinct subset of the plurality of range locks, and the step of determining whether a range lock exists includes the sub-steps of:

computing a hash function based partially upon a portion of the requested virtual address range, the hash function returning a hash function result indicating one of the plurality of buckets; and

searching a first subset of the plurality of range locks corresponding to the bucket indicated by the hash function result.

10. A computer-implemented method of processing an input/output (I/O) completion notification received by a virtual memory sub-system within a computer system, the I/O completion notification corresponding to an original I/O request, the method comprising:

receiving a virtual memory I/O request that includes a virtual address range corresponding to a region in virtual memory of the computer system, the virtual memory being distinct from the physical memory and the computer system having a facility for creating a plurality of range locks, each range lock representing corresponding pages of virtual memory that are present in the physical memory and that are locked in the physical memory, the virtual memory I/O request normally resulting in a virtual memory unlock occurring;

identifying a virtual page range that includes the requested virtual address range and identifies at least one page of virtual memory;

determining whether a range lock exists that represents the identified virtual page range; and

wherein when it is determined that a range lock exists that represents the identified virtual page range, the method further comprises decrementing a usage counter associated with the range lock in order to indicate that the I/O request is no longer outstanding for the identified virtual page range, the usage counter indicating the number of outstanding I/O requests for the virtual page range and the range lock existing when the usage counter is greater than or equal to zero, whereby a virtual memory unlock is avoided for the virtual memory I/O request for the virtual address range.

11. A method as recited in claim 10 wherein the plurality of range locks in the computer system are organized using a hash table having a plurality of buckets, each bucket arranged to indicate a distinct subset of the plurality of range locks, and the step of determining whether a range lock exists includes the sub-steps of:

computing a hash function based partially upon a portion of the requested virtual address range, the hash function returning a hash function result indicating one of the plurality of buckets; and

searching a first subset of the plurality of range locks corresponding to the bucket indicated by the hash function result.

12. A computer-implemented method of removing a lock upon a region of physical memory within a computer system in response to a cache purge request, the method comprising:

receiving a cache purge request in a computer system having virtual memory distinct from the physical memory, the computer system having a facility for creating a plurality of range locks, each range lock representing corresponding pages of virtual memory that are present in the physical memory and that are locked in the physical memory;

identifying a first range lock having a virtual page range corresponding to a set of virtual memory pages, the first range lock having a usage counter indicating the number of outstanding I/O requests for the virtual page range and the first range lock existing when the usage counter is greater than or equal to zero;

determining whether the set of virtual memory pages that are locked in physical memory should be unlocked by determining that the usage counter of the range lock is zero; and

wherein when it is determined that the set of virtual memory pages that are locked in physical memory should be unlocked the method further comprises:

applying a virtual memory unlock function to the virtual page range in order to unlock the pages of virtual memory that are identified by the virtual page range in the physical memory, and

releasing the portion of physical memory that is occupied by the first range lock.

13. A method as recited in claim 12 wherein the cache purge request is in response to a low memory condition of the computer system and the step of determining whether a set of virtual memory pages that are locked in physical memory should be unlocked includes the step of determining whether a range lock exists having an associated usage counter that indicates that relatively few I/O operations are outstanding for the set of virtual memory pages that correspond to the existing range lock.

14. A method as recited in claim 13 wherein the step of determining whether a set of virtual memory pages that are locked in physical memory should be unlocked further includes the step of determining whether a range lock exists having an associated timer reference counter that indicates that relatively few I/O operations have been performed over a period of time using the set of virtual memory pages that correspond to the existing range lock.

15. A method as recited in claim 12 wherein the cache purge request is in response to a request to unlock a first virtual address range, and the step of determining whether a set of virtual memory pages that are locked in physical memory should be unlocked includes the step of determining whether said set of virtual memory pages overlap with said first virtual address range.

16. A method as recited in claim 12 wherein the plurality of range locks in the computer system are organized using a hash table having a plurality of buckets, each bucket arranged to indicate a distinct subset of the plurality of range locks, and the step of determining whether a set of virtual memory pages that are locked in physical memory should be unlocked includes the sub-steps of:

updating a bucket counter to indicate a current one of the plurality of buckets, and

searching a first subset of the plurality of range locks corresponding to the current bucket indicated by the bucket counter.

17. A range lock data structure embodied in a computer-readable medium, the range lock data structure being arranged for use in implementing a virtual memory sub-system of a computer system, the computer system having physical memory and virtual memory distinct from the physical memory, the range lock representing a virtual page range that identifies one or more pages of virtual memory that are present in the physical memory and that are locked in the physical memory, the range lock comprising:

a process identifier indicative of the computer process to which the virtual pages correspond;

a virtual pages identifier indicative of the virtual pages of virtual memory that are locked in the physical memory;

a physical page list identifier indicative of those physical pages in physical memory that correspond to the virtual pages of virtual memory; and

a usage counter indicative of the number of outstanding input/output operations associated with the physical pages, the range lock data structure existing when the usage counter is greater than or equal to zero.

18. A computer apparatus for use in implementing a virtual memory sub-system of a computer system, the computer apparatus comprising:

a central processing unit;

random access memory in communication with the central processing unit;

a mass storage device in communication with the central processing unit

wherein the random access memory includes a data structure as recited in claim 17.

19. A computer program product comprising a computer-usable medium having computer-readable code embodied thereon for placing a lock upon a region of physical memory within a computer system in response to an input/output (I/O) request, the computer program product comprising computer-readable program code for effecting the following within the computer system:

receiving a virtual memory I/O request that includes a virtual address range corresponding to a region in virtual memory of the computer system, the virtual memory being distinct from the physical memory and the computer system having a facility for creating a plurality of range locks, each range lock representing corresponding pages of virtual memory that are present in the physical memory and that are locked in the physical memory, the virtual memory I/O request normally resulting in a virtual memory lock occurring;

identifying a virtual page range that includes the requested virtual address range and identifies at least one page of virtual memory;

determining whether a range lock exists that represents the identified virtual page range; and

wherein when it is determined that a range lock exists that represents the identified virtual page range, the method further comprises incrementing a usage counter associated with the range lock in order to indicate that the I/O request is now outstanding for the identified virtual page range, the usage counter indicating the number of outstanding I/O requests for the virtual page range and the range lock existing when the usage counter is greater than or equal to zero, whereby a virtual memory lock is avoided for a subsequent virtual memory I/O request for the virtual address range.

20. A computer program product as recited in claim 19 wherein when it is determined that a range lock does not exist that represents the virtual page range, the computer program product further comprises code for:

applying a virtual memory lock function to the virtual page range in order to lock the pages of virtual memory identified by the virtual page range in the physical memory;

creating a first range lock that represents the virtual page range.

21. A computer program product as recited in claim 20 wherein the first range lock includes a physical page list pointer that indicates the physical pages in physical memory corresponding to the virtual page range and the computer program product further comprises code for returning the physical page list pointer.

22. A computer program product as recited in claim 19 wherein the plurality of range locks in the computer system are organized using a hash table having a plurality of buckets, each bucket arranged to indicate a distinct subset of the plurality of range locks, and the step of determining whether a range lock exists includes the sub-steps of:

computing a hash function based partially upon a portion of the requested virtual address range, the hash function returning a hash function result indicating one of the plurality of buckets; and

searching a first subset of the plurality of range locks corresponding to the bucket indicated by the hash function result.

23. A computer-implemented method of transmitting the computer-readable program code as recited in claim 19, the method comprising the steps of:

storing the program code onto a computer-usable medium;

receiving a request for the transmission of the program code; and

transmitting the program code over a network to a remote location.

24. A computer program product comprising a computer-usable medium having computer-readable code embodied thereon for placing a lock upon a region of physical memory within a computer system in response to an input/output (I/O) request, the computer program product comprising computer-readable program code for effecting the following within the computer system:

receiving a virtual memory I/O request that includes a virtual address range corresponding to a region in virtual memory of the computer system, the virtual memory being distinct from the physical memory and the computer system having a virtual memory lock function operative to lock pages of virtual memory in the physical memory of the computer system, the computer system also having a facility for creating a plurality of range locks, each range lock representing corresponding pages of virtual memory that are present in the physical memory and that are locked in the physical memory, the virtual memory I/O request normally resulting in a virtual memory lock occurring;

identifying a virtual page range that includes the requested virtual address range and identifies at least one page of virtual memory;

determining whether a range lock exists that represents the identified virtual page range, wherein when it is determined that a range lock does not exist that represents the virtual page range, the method further comprises,

applying the virtual memory lock function to the virtual page range in order to lock the pages of virtual memory that are identified by the virtual page range in the physical memory, the virtual memory lock function operative to force a continuous assignment of a first group of physical memory pages to the pages of virtual memory that are identified by the virtual page range on a one-to-one basis, and

creating a first range lock that represents the virtual page range, the first range lock having a usage counter indicating the number of outstanding I/O requests for the virtual page range and the first range lock existing when the usage counter is greater than or equal to zero, whereby a virtual memory lock is avoided for a subsequent virtual memory I/O request for the virtual address range.

25. A computer program product as recited in claim 24 wherein the step of applying a virtual memory lock function further includes the sub-steps of:

determining whether a set of pages of virtual memory included within the virtual page range have already been locked into physical memory by the virtual memory lock function; and

wherein when it is determined that a set of pages of virtual memory included within the virtual page range have already been locked into physical memory, the step of applying a virtual memory lock function operates to avoid locking the set of pages that have already been locked.

26. A computer program product as recited in claim 24 further including code for determining whether the step of applying a virtual memory lock function has succeeded.

27. A computer program product as recited in claim 24 wherein the first range lock includes a physical page list pointer that indicates the physical pages in physical memory corresponding to the virtual page range and the computer program product further comprises code for returning the physical page list pointer.

Description Submit all comments and votes

FIELD OF THE INVENTION

The present invention relates generally to a virtual memory locking technique for use within a computer system. More specifically, a locking technique for use with virtual memory that uses caching of the locks is described.

BACKGROUND OF THE INVENTION

Many computer systems in use today use some form of virtual memory scheme in order to address larger sections of memory than are available as physical memory (sometimes termed "real" memory) within the computer itself. Such a virtual memory scheme may allow a central processing unit (CPU) to address more memory than what may be available as random access memory located within the computer. This scheme allows data and instructions to be relocated in an organized fashion. In addition to providing solutions for problems of relocating data and instructions in memory, a virtual memory scheme also allows the illusion of a large, fast memory to be provided at lower hardware cost. The purpose of a virtual memory scheme is to allow a much greater flexibility in the physical placement of a particular datum within a possibly multi-level memory hierarchy. A multi-level memory hierarchy is an ordered collection of physical memory systems, each one typically larger and slower (and hence cheaper per byte) than the proceeding one. A virtual memory scheme typically involves the use of pages, in which a page from virtual memory may be brought into physical memory and then rewritten to a hard disk or the like when finished. Such an activity is also called page swapping.

However, in order to perform input/output (I/O) operations most virtual memory subsystems require page by page locking of the region undergoing I/O. This locking and unlocking for a page may occur each time an I/O operation begins and ends. This process can be quite expensive. For an operating system that is highly parallel and performs lots of I/O, it can be extremely costly to lock and release a page each time an I/O operation either requests a page, or is finished with a page, respectively. For I/O operations, many prior art virtual memory schemes acquire and release a lock on virtual memory pages each time an I/O operation is initiated and then completed. This prior art technique results in increased CPU overhead because creating and removing these I/O locks is very expensive. For example, in certain virtual memory subsystems, roughly 75% of CPU overhead for certain I/O operations can be attributed to this page by page locking.

Thus, the swapping in and out of pages, and the corresponding creation and release of leeks on a page by page basis can result in tremendous overhead. To reduce this overhead, it is desirable to keep a page in physical memory and prevent unmapping from occurring unless necessary. In other words, in order to reduce CPU overhead costs, it would be desirable to force a continuous assignment of a physical page to a logical page in virtual memory until the memory space is unneeded or otherwise required. It would also be desirable to have a locking technique for use with virtual memory subsystems that would retain the locks on a region of virtual memory between I/O operations, and would allow processes to locate and utilize cached representations of locks efficiently.

SUMMARY OF THE INVENTION

One aspect of the present invention relates to a method of placing a virtual memory lock upon a region of physical memory within a computer system in response to an input/output (I/O) request. For a computer system with a virtual memory distinct from physical memory, it is often necessary to lock pages of virtual memory in the physical memory during I/O operations. The present invention provides a facility for creating a plurality of range locks, each range lock representing corresponding pages of virtual memory that are present in the physical memory and that are locked in the physical memory. These range locks may be cached in memory and used subsequently to process a lock or unlock request. Regions of memory that are locked, but have no outstanding I/O operations may still have a range lock existing corresponding to that region. When an I/O request that includes a virtual address range corresponding to a region in virtual memory is received a virtual page range that includes the requested virtual address range is identified. Then, it is determined whether a range lock exists that represents the identified virtual page range, a usage counter associated with the range lock is incremented in order to indicate that the I/O request is now outstanding for the identified virtual page range.

If a range lock that covers the requested range does not exist, then the virtual memory subsystem is called to apply a virtual memory lock to the requested range thereby creating a range lock that corresponds to the newly locked region. The range locks may be stored and accessed through any suitable mechanism. In one preferred embodiment, a hash table is used to store the range locks.

One significant advantage of the present invention is that upon notification of the completion of an I/O operation, it may not be necessary to call the virtual memory subsystem in order to unlock the region that was in use. Another aspect of the present invention provides a method that receives an I/O completion notification that includes a virtual address range corresponding to a region in virtual memory. When received, a virtual page range is identified that includes the requested virtual address range and identifies at least one page of virtual memory. Then, it is determined whether a range lock exists that represents the identified virtual page range. When it is determined that a range lock exists that represents the identified virtual page range, the method decrements a usage counter associated with the range lock in order to indicate that the I/O request is no longer outstanding for the identified virtual page-range.

Another aspect of the present invention allows physical memory to be freed up upon receiving a request due to low memory or upon receiving notification of released pages. For a low memory request, the method will search through the stored range locks and will determined which range locks represent regions of virtual memory that are not in use. For released pages, the method will determine which stored range locks correspond to and overlap the pages needing to be released. In either case, for these range locks that are determined, the pages in physical memory corresponding to these range locks will be unlocked and the range locks themselves will be removed from memory.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention, together with further advantages thereof, may best be understood by reference to the following description taken in conjunction with the accompanying drawings in which:

FIG. 1 shows conceptually how a set of cached range locks for various regions of virtual memory correspond to particular processes within the operating system of a computer.

FIG. 2 shows symbolically a range lock according to one embodiment of the present invention that is used to represent a lock upon a region of virtual memory.

FIG. 3 diagrammatically shows a region of virtual memory for a computer system and a variety of virtual memory locks placed upon this region that are represented by various range locks.

FIG. 4 is a diagrammatic illustration of a hash table for use in accessing a set of range locks according to one embodiment of the present invention.

FIG. 5 is a flow chart illustrating a method suitable for implementing a virtual memory lock upon a range of virtual memory in response to a read or write request in accordance with one embodiment of the present invention.

FIG. 6 is a flow chart illustrating a method suitable for creating a range lock that represents a virtual memory lock upon a range of virtual memory.

FIG. 7 is a flow chart for releasing a range lock due to a notification of I/O completion.

FIG. 8 is a flow chart for removing a virtual memory lock upon a range of virtual memory due to a low physical memory situation within the computer system.

FIG. 9 is a flow chart for removing a virtual memory lock upon a range of virtual memory due to the release of a region of virtual memory by a process.

FIG. 10 shows a typical computer-based system for use in accordance with the present invention.

DETAILED DESCRIPTION OF THE INVENTION

The present invention uses a memory caching technique in order to retain the locks on a region of virtual memory between (input/output) I/O operations. These cached locks may then be located and utilized efficiently by later operations wishing to lock a region. The locking technique uses the concept of a range lock to represent a lock that is in place upon a range of virtual memory. This range lock is created and will exist for a particular range in virtual memory during I/O operations to that range. It will not necessarily be created and destroyed each time an I/O operation is initiated or is completed. These range locks are cached and organized in memory in an efficient manner such that they may be accessed and utilized with a low CPU overhead cost. In other words, for multiple I/O operations, corresponding pages in virtual memory will be locked once and will remain locked unless it is necessary that the region be unlocked. These range locks represent an I/O lock upon a region. There are other different low-level locks that may also be present on a page-by-page basis. They include a shared-exclusive lock that allows one to gain exclusive access to a page in order to destroy it, a lock to implement the I/O lists for paging, and special locks that control the right to apply locks.

FIG. 1 at 10 shows conceptually how a set of these range locks may be associated with a particular process within a computer system. Shown in particular are a group of processes identified as Process Id 1, Process Id 2 and Process Id 3. Each of these processes represent a process or program running on the CPU within the computer system. Each process may also have associated with it any number of threads. Each of these processes also represents a unique virtual address space that may have certain regions of virtual memory locked at a given time. These regions of virtual memory may be temporarily locked in physical memory because the process needs access to the information (data, program instructions) contained in the virtual memory. The regions of virtual memory that are locked by the process may each be represented conceptually by a data structure called a range lock. Each process may have a corresponding set of range locks 20 as shown.

Because each virtual address space within virtual memory will be unique, each virtual address space has associated with it a set of range locks that lock a unique but possibly overlapping range within virtual memory. Shown for Process Id's 1, 2 and 3 are a subset of their respective range locks. Process Id 1 may have two locks on virtual memory and these are represented by the two range locks shown. Likewise, Process Id 2 may have one outstanding lock on virtual memory that is represented by its single associated range lock 20. Process Id 3 currently has no outstanding locks on virtual memory and as such is not associated with any range lock. It should be appreciated that FIG. 1 shows one possible conceptual illustration of how range locks may be grouped in sets and then associated with a particular process. A wide variety of techniques may be used to group and organize these range locks. By way of example, one particular method for organizing, storing, and accessing these range locks will be discussed below with reference to FIG. 4. Alternatively, these range locks may be organized as sub-locks in a sub-lock list. Such a technique is described in U.S. Patent Application "Flexible Range Locking for Shared Resource", by Jonathan L. Bertoni, filed on Feb. 29, 1996, Ser. No. 08/607,965, now U.S. Pat. No. 5,761,659 and is hereby incorporated by reference in its entirety.

FIG. 2 at 20 shows symbolically one embodiment of a range lock suitable for use in the locking arrangement shown in FIG. 1. Once a process has placed an I/O lock upon a page range within virtual memory a range lock 20 may be used to represent this I/O lock conceptually. A range lock 20 has various fields associated with it that contain information related to the lock on virtual memory and the organization and accessing of the range locks.

The illustrated embodiment of the range lock 20 includes a number of fields that may be implemented using any suitable data structure. The fields includes a Process Identifier, a Virtual Page Start and a Virtual Page Count. The Process Identifier field 22 contains the identification for the process with which this range lock is associated. Alternatively, this may also be the virtual address space identifier. The Virtual Page Start field 24 represents the page within virtual memory at which the locked region begins. The Virtual Page Count field 26 represents the number of pages in virtual memory that are currently locked that begin at the Virtual Page Start. p For example, if the field Virtual Page Start has a value of 10, and the field Virtual Page Count has the value of four, this indicates that the pages in virtual memory that are locked range from page 10 to page 13. The field Usage Counter 28 represents how many outstanding I/O operations are present for this range. However, if the Usage Counter has a value of zero, indicating that no I/O operations are outstanding, this range lock will still exist and that region of virtual memory corresponding to this range lock will still be locked. In this fashion, the constant creating and deletion of locks based upon the initiation and completion of I/O operations may be avoided. The field Hash List Pointer 30 contains a pointer to the next range lock in a given set of range locks, thus forming a linked list. For example, referring back to FIG. 1, it can be seen that the first range lock 20 for Process Id 1 has a hash list pointer 30 that points to the second range lock for that Process Id 1. Likewise, the Hash List Pointer 30 for the final range lock is associated with a nil pointer because it does not point to a next range lock. The field Physical Page List Pointer 32 is a pointer that points to a list of all of the physical pages in main memory that are mapped to by the pages in virtual memory corresponding to this range. The field Timer Reference Counter 34 is a counter that represents over time the number of instances in which an I/O operation seeks to lock this range. It is incremented each time an I/O operation tries to lock this range and may be decremented or set equal to zero if a request is made to free physical memory. The Timer Reference Counter is used to keep track over time of the usage of a particular range lock and helps to indicate whether a particular range lock has had a low frequency of use and may then be removed.

FIG. 6 at 60 shows conceptually a region of virtual memory for a computer system that has various virtual memory locks applied to it. As will be appreciated by those skilled in the art, the size of a locked page may vary significantly from system to system. Shown in particular is a virtual memory region 61 that ranges from 0k up to X k in pages having length of 8k each. A lock 62 has been applied to pages 0 to 1 of this virtual memory and is represented by a range lock A. A second lock 64 has been applied to this virtual memory and is represented by a range lock B. As shown, range lock B corresponds to pages 1-4 and range locks A and B overlap with each representing a lock upon page 1 of the virtual memory. Also shown is a lock 66 represented by a range lock C. It should be appreciated that the size of a page within virtual memory may vary greatly, and that any number of locks may be placed upon the virtual memory at arbitrary locations. And although a range lock corresponds to a range of pages within virtual memory that are currently locked, these ranges may overlap. In this fashion, it may be appreciated that a range lock such as illustrated in FIG. 2 at 20 may be used to represent an I/O lock that has been placed upon a range of pages within the virtual memory.

FIG. 4 shows at 80 a hash table that is used to efficiently organize and access all of the range locks corresponding to a virtual memory. The hash table is made up of a series of cells 81 that contain an associated set of range locks for that cell. A cell is also termed a bucket. The hash table also has an address space 82 that is labeled from 0 to N. This address space 82 is also termed the bucket number and is used to reference a particular bucket. The implementation and use of a hash table will be familiar to one of skill in the art. It should also be appreciated that the organization and accessing of all of the range locks for a virtual memory may also be accomplished by a technique other than the use of a hash table.

Shown in particular in the hash table at Bucket Number 0 is a Bucket 83 that contains two range locks 20. The representation of these range locks within Bucket Number 0 is achieved through the use of a Bucket Pointer 86 that points to a linked list of the range locks that are contained within this bucket. Thus, it can be seen that each bucket has an associated Bucket Pointer 86 that points to a first range lock in a list of range locks. Each successive range lock in this list is accessed by the Hash List Pointer 30 of each range lock 20. One of skill in the art will appreciate that for a given bucket its associated linked list of range locks may be searched in order to find a particular range lock. Each bucket, for example Bucket 89, has a mutex lock variable 84 that may be in a locked or unlocked state. This mutex lock variable when locked prevents the range locks in that bucket from being inserted, deleted or from being searched. This lock may be used while a particular bucket is being processed, as will be described below. In order to increase parallelism, it is also possible to perform some of this work outside of the locked bucket; such a technique will be known to one of skill in the art.

The hash table uses a hash function "f()" which is a function of the Virtual Page Start and Process Identifier. Thus, for a given range lock with a Virtual Page Start and a Process Identifier, these values are used in the hash function to produce a unique value K such that this range lock may be inserted at the bucket corresponding to the value K. Thus, the hash function may be stated mathematically as: K=f (Virtual Page Start, Process Identifier). The value K will range from 0 to N. The length of the hash table may be of any length, although a preferable value for the quantity N may be a power of 2 such as 128 or 256. It will be appreciated by one of skill in the art that an optimum number for the value N may be derived empirically and depends upon the particular computing system for which the hash table is being implemented.

FIG. 5 is a flow chart according to one embodiment of the present invention illustrating how a read/write request may implement an I/O lock upon a region within virtual memory. This read/write request may originate from a thread that is either requesting that data be read from virtual memory or that data within the physical memory of the computer be written to virtual memory. The steps described below illustrate how it may not be necessary to apply a new virtual memory lock to a particular range in certain circumstances, thus reducing CPU overhead.

This I/O request may be to/from a hard disk, tape, optical disk or the like that is considered secondary storage of the computer system. For example, a disk read request will actually write pages from the disk to the physical memory of the computer, while a disk write request will read pages from the physical memory and write them to disk. Thus, when a disk read occurs the system must verify that write access is available to the physical memory, while for a disk write the test is less stringent because the physical memory is only being read.

In step 202 a read/write request is received. Parameters included with this request are a Virtual Start Address, a Length and a Read/Write Flag. The Virtual Start Address indicates a byte address within virtual memory that indicates the beginning of the region that is desired to be locked. The Length is a variable in bytes that indicates the length of the region in virtual memory to be locked. Thus, a virtual address range that begins at the Virtual Start Address and extends for Length number of bytes within the virtual memory is delineated. The Read/Write Flag is a variable that will indicate that either a read or a write request is taking place. Step 204 looks up the Process Identifier associated with the thread or other routine that has made the request.

In step 206 the Virtual Page Range that corresponds to the virtual address range is identified. Any pages within the virtual memory that fall within the range of the virtual address range are identified as part of the Virtual Page Range. For example, if the virtual address range begins midway through page 2 and ends midway through page 6 the Virtual Page Range would extend from page 2 through page 6 inclusive. This Virtual Page Range is identified by a variable Virtual Page Start that denotes t