Virtual memory system and methods

• US 6,760,909 B1
• Filed: 07/14/1998
• Issued: 07/06/2004
• Est. Priority Date: 04/29/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Odinak, Gilad, Draves, Richard P.
• Primary Examiner(s): LAO, SUE X
• Application Number:
  US09/115,448
• Time in Patent Office: 2,184 Days
• Field of Search: 709/300, 709/229, 707/8, 395/726, 395/728, 710/200, 710/240, 710/243, 718/102, 718/107, 718/100, 718/104, 711/205, 711/203, 711/200
• US Class Current: 718/102
• CPC Class Codes: G06F 12/1036 for multiple virtual address spaces, e.g. segmentation G06F12/1045 takes precedence
• CPC Class Codes: G06F 2212/681 Multi-level TLB, e.g. microTLB and main TLB

Abstract

A virtual memory system includes a hardware-implemented translation lookaside buffer (HTLB) as well as a software-implemented translation lookaside buffer (VTLB). The VTLB is in the system'"'"'s unmapped memory. The system further includes a plurality of address maps, corresponding to an operating system kernel and to individual tasks executing within the system. The kernel has an address space which includes both mapped and unmapped memory. The address maps corresponding to the individual tasks are stored in the mapped memory of the kernel'"'"'s address space. The address map corresponding to the kernel itself, however, is stored in the kernel'"'"'s unmapped memory. HTLB misses are handled by referring to the VTLB. VTLB misses are handled by referring to an appropriate one of the address maps. The code for handling these misses resides in unmapped memory of the kernel'"'"'s address space. This arrangement prevents recursive TLB misses, without requiring permanent or “wired” VTLB entries. Because there are no permanent VTLB entries, the VTLB can have a simple and efficient structure, and its size can be bounded. As a further features, the address maps are associated with both spin locks and mutex locks. A routine which modifies an individual address map first acquires the mutex lock associated with the address map and performs initial examination of the address map. Once the routine is ready to make actual modification, it also acquires the spin lock. By having the two types of locks, the majority of the routine can be preemptible. Only the portion of the routine which actually modifies the address map needs to be non-preemptible.

Claims

1. An operating system kernel comprising:

a program having preemptible code portions and non-preemptible code portions;

a data structure which is accessible by both the preemptible and non-preemptible code portions;

first and second locks associated with the data structure;

the first lock being a spin lock, which causes a requesting thread to spin while waiting to acquire the first lock;

the second lock being of a type that causes the requesting thread to be suspended while waiting to acquire the second lock;

wherein the preemptible code portions are configured to acquire only the second lock before accessing the data structure; and

wherein the non-preemptible code portions of the program are configured to acquire both the first lock and the second lock before accessing the data structure.

2. An operating system kernel as recited in claim 1 wherein the non-preemptible code portions mutate the data structure and the preemptible code portions do not mutate the data structure.

3. An operating system kernel as recited in claim 1 wherein the program has a database modification procedure, the database modification procedure having a preliminary section which examines but does not mutate the data structure and a subsequent section which mutates the data structure based on the previous examination of the data structure;

wherein the subsequent section is non-preemptible and the preliminary section is preemptible; and

wherein the subsequent section is configured to acquire both the first lock and the second lock before mutating the data structure.

4. A method of accessing a data structure from preemptible and non-preemptible code portions, the method comprising the following steps:

associating both first and second locks with the data structure;

the first lock being a spin lock, which causes a requesting thread to spin while waiting to acquire the first lock;

the second lock being of a type that causes the requesting thread to be suspended while waiting to acquire the second lock;

in the preemptible code portions, acquiring only the second lock before accessing the data structure; and

in the non-preemptible code portions, acquiring both the first lock and the second lock before accessing the data structure.

5. A method as recited in claim 4 and further comprising the following steps:

identifying first code sections which mutate the data structure and second code sections which do not mutate the data structure;

designating the first code sections as non-preemptible; and

designating the second code sections of the program as preemptible.

6. A method as recited in claim 4 and further comprising the following steps:

examining the data structure without mutating the data structure in a preemptible code section;

after examining the data structure, mutating the data structure in a non-preemptible code section based on the examining step; and

acquiring both the first lock and the second lock before mutating the data structure in the non-preemptible code sections.

7. A virtual memory system to be used by a plurality of tasks, each task having an associated virtual address space, the virtual memory system comprising:

physical memory that is accessible as virtual memory through variable virtual-to-physical address mappings;

a plurality of task address maps, each task address map describing a set of virtual-to-physical address mappings for a particular task'"'"'s virtual address space;

a first lock and a second lock associated with each of the task address maps;

the first lock being a spin lock, which causes a requesting thread to spin while waiting to acquire the first lock;

the second lock being of a type that causes the requesting thread to be suspended while waiting to acquire the second lock;

wherein before examining a particular task address map the requesting thread obtains the second lock; and

wherein before mutating the particular task address map the requesting thread obtains both the first lock and the second lock.

8. A method of accessing a data structure comprising:

associating both first and second locks with the data structure;

the first lock being a spin lock, which causes a requesting thread to spin while waiting to acquire the first lock;

the second lock being of a type that causes the requesting thread to be suspended while waiting to acquire the second lock;

acquiring the second lock before accessing the data structure; and

acquiring both the first lock and the second lock before mutating the data structure,

wherein the data structure is an address map.

9. An operating system comprising:

a data structure;

first code portions that examine the data structure without mutating the data structure;

second code portions that mutate the data structure;

first and second locks associated with the data structure;

the first lock being a spin lock, which causes a requesting thread to spin while waiting to acquire the first lock;

the second lock being of a type that causes the requesting thread to be suspended while waiting to acquire the second lock;

wherein the first code portions are configured to acquire the second lock before examining the data structure; and

wherein the second code portions are configured to acquire both the first lock and the second lock before mutating the data structure.

10. An operating system as recited in claim 9, wherein the data structure is an address map.