Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1994-12-13
2002-03-26
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06363410
ABSTRACT:
TECHNICAL FIELD
The invention relates generally to a method and system for managing dynamic resources, and, more specifically, to a method and system for threaded resource allocation and reclamation.
BACKGROUND OF THE INVENTION
An operating system is a set of computer programs that interact with a computer system to provide services and resources requested by application programs. An example of a resource provided by operating systems is a memory segment selector (“selectors”). Selectors are resources used in computers based on the Intel 80×86 series of microprocessors to virtualize the primary storage address space, allowing primary storage contents to be rearranged in primary storage and improving robustness by preventing applications from accidentally overwriting memory that they do not own.
FIG. 1
is a diagram demonstrating the use of a selector. The diagram shows an address space
110
used to store and retrieve data. Programs use pointers to store data in and retrieve data from one or more storage devices to which linear addresses within the address space are mapped. Some programs use “segmented pointers” (also called “far pointers”) to store and retrieve data. Segmented pointers like pointer
120
are comprised of two parts: a selector identifier (e.g., segment identifier
121
) and an offset (e.g., offset
122
). The selectors available in a computer system are stored together in a local descriptor table (“LDT”) like LDT 130. The selector identifier of a segmented pointer identifies a selector stored in the LDT. For example, the selector identifier
121
(“0x0050”) identifies selector
131
. Usually the selector identifier is not actually stored in the LDT, but rather it constitutes an offset from the beginning of the LDT to the portion of the LDT corresponding to a particular selector, for example, selector
131
is the selector stored beginning at the 0x0050
th
byte of the LDT. Each selector identifies a “segment” of the address space by containing a representation of a base address within the address space at which that segment begins. For example, selector
131
contains a base representation
133
of “0x0100000”, which represents linear address 0x01000000. Selector
131
therefore identifies segment
111
, which begins at linear addresses 0x01000000 (the base) and continues to 0x0100FFFF (the base plus a maximum length value). The linear address referred to by a segmented pointer is consequently the sum of the base represented by the selector identified by the segment identifier of the segmented pointer and offset of the segmented pointer. As an example, the segmented pointer
120
refers to linear address
112
(“0x01008000”).
In many operating systems, selectors are frequently allocated and released. For instance, whenever the operating system allocates a block of memory within the address space for an application that uses segmented pointers, it allocates a new selector and sets its base to the linear address at the beginning of the block. The operating system then returns a segmented pointer to the application comprised of the identifier of the allocated selector and the offset zero. When the application frees the block, the operating system frees the selector. Selectors are especially frequently allocated and released in hybrid operating systems in which both application that use segmented pointers and applications that use flat pointers containing a linear address. When an application that uses flat pointers attempts to pass a flat pointer containing a linear address to an application that uses segmented pointers, the operating system allocates a new selector and sets its base to the linear address. The operating system then passes a segmented pointer to the application comprised of the identifier of the allocated selector and the offset zero. When the application that receives the segmented pointer no longer needs it, the operating system frees the selector.
Because virtually every type of resource provided to application programs is scarce within the computer system, an operating system must allocate and reclaim resources in a way that maximizes their availability to application programs. Further, because applications request some types of resources frequently in a typical computer system, the portion of the operating system that responds to requests to allocate and reclaim resources must operate efficiently.
Both of these goals for resource allocation are more difficult to achieve in a multithreaded operating system. Multithreaded operating systems appear to execute several application programs at once by maintaining multiple execution contexts (typically at least one for each active application), each comprised of separate program counters and register values. Each execution context is said to correspond to a different thread. Typically, in multithreaded operating system running on a single processor, one thread at a time may be active and execute instructions. Such a multithreaded operating system provides concurrent processing of the threads, that is, the illusion of simultaneous processing, by frequently changing the execution context so that each thread, in turn, is the active thread and executes instructions for a brief period.
FIGS. 2A-2C
are allocation diagrams that demonstrate a common conventional approach to resource allocation and reclamation in a multithreaded operating system.
FIG. 2A
shows that 16 selectors, numbered 0x0001-0x0010, are available within a computer system. Some of these selectors are in use by a thread, while the others are unused, or “free.” Each thread that exists in the computer system is represented by a box bounded with broken lines. Box
210
shows that selector 0x0001 is in use by thread
1
; box
220
shows that selector 0x0002 is in use by thread
2
; and box
230
shows that thread
3
is not currently using any selectors. The other 14 selectors, 0x0003-0x0010, are free, and are stored in a structure called the free list. The free list is a linked list
240
, which has a head
241
that points to the first item. The first item corresponds to selector 0x0003, and contains a pointer to the next item, which corresponds to selector 0x0004. The free list is terminated by a null pointer stored in the last item, which corresponds to selector 0x0010.
FIG. 2B
is an allocation diagram that demonstrates the allocation of a free selector. When thread
3
requests the allocation of a selector, the approach removes the first item of the list, 0x0003, and allocates the associated selector to thread
3
. Selector 0x0003 therefore appears in the box for thread three, box
230
. The first item is removed from the free list by copying the pointer in the head to the first item for the requesting thread, then copying the pointer in the first item into the head.
FIG. 2C
is an allocation diagram that demonstrates the reclamation of a freed selector. When thread
2
finishes using selector 0x0002, it frees selector 0x0002 by requesting its reclamation, and the approach adds an item to the free list representing the reclaimed selector. The item is added to the free list by creating an item representing the reclaimed selector, copying the pointer in the head into the created item, and replacing the pointer in the head with a pointer to the created item.
Removing an item from the free list, as required by the allocation demonstrated in
FIG. 2B
, and adding an item to the free list, as required by the reclamation demonstrated in
FIG. 2C
, are both delicate operations. If two different threads were to each cause the operating system to modify the free list at approximately the same time and the component operations of the modifications were temporally interleaved, the free list could be corrupted. For example, if both a first and a second thread were attempting to free different selectors, and the first thread was interrupted between the two constituent operations of the freeing process by all of the operations of the freeing process from the second thread, the selector “freed” would not end up on the list.
As a result, the fre
Kanamori Atsushi
Thomason Jon
Christensen O'Connor Johnson & Kindness PLLC
Courtenay III St. John
Lao S.
Microsoft Corporation
LandOfFree
Method and system for threaded resource allocation and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for threaded resource allocation and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for threaded resource allocation and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2876904