Protocol for coordinating the distribution of shared memory

Details Protocol for coordinating the distribution of shared memory Protocol for coordinating the distribution of shared memory

1999-02-04

2002-01-22

Thai, Tuan V. (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Shared memory area

C711S148000, C711S152000, C711S153000, C711S170000

Reexamination Certificate

active

06341338

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to multi-threaded applications, and more particularly to methods for coordinating the distribution of shared memory to threads of control executing in a data processing system.
BACKGROUND OF THE INVENTION
Multi-threading is the partitioning of a computer program that performs a particular process into logically independent “threads” of control that can execute in parallel. Each thread includes a sequence of instructions and data used by the instructions to carry out a particular program task, such as a computation or input/output function.
Although a single processor can execute instructions of only one thread at a time, the processor can execute multiple threads in parallel by, for example, executing instructions corresponding to one thread until reaching a selected instruction, suspending execution of that thread, and executing instructions corresponding to another thread, until all threads have completed. In this scheme, as long as the processor has begun executing instructions for more than one thread during a given time interval all executing threads are said to be “running” during that time interval, and multi-processing is achieved.
A process includes multiple threads operating out of a common address space. Processes may be configured such that portions of their address space are shared, that is, are mapped to a common physical location, or a memory. Multiple threads within a process share portions of that memory address space. It is possible for more than one thread to believe it has sole access to a portion of memory and for it to perform a series of reads and writes to an area of memory while another thread is performing reads and writes to the same area of memory. Such concurrent operation by competing threads may confuse operation of a process. Therefore, in a shared memory environment the shared memory must be allocated to each thread based on a coordination technique ensuring that only one thread has access to an area of shared memory at a time.
Current memory allocation techniques assign address space to threads in one of two ways: distribution or mutual exclusion. Distribution techniques partition shared memory into equal-sized blocks and assign the memory blocks to threads as requested. Each memory block must be large enough to meet the memory requirements of the thread requiring the most memory. Total memory requirements are dictated by the maximum demand for access to shared memory of a given thread multiplied by the total number of threads involved. This method is particularly wasteful when individual threads do not require similar amounts of shared memory. Even slight differences in the threads' memory requirements can have a significant impact on the total memory requirement.
Mutual exclusion techniques, which may be implemented in hardware or software, coordinate use of shared memory among threads by reading and writing shared variables and pointers referring to the shared addresses. Implementation of these techniques requires accessing the operating system, which is both slow and expensive.
In a mutual exclusion implementation the operating system only permits one thread at a time to access shared memory. Shared memory is assigned to a thread by exchanging signals between threads, such that a thread can be forced to stop at a specified point during execution until it has received a specific signal. More specifically, the operating system may allow a thread to access shared memory by locking the shared memory, allocating the memory for exclusive use of the thread, and unlocking the memory once the thread has completed the memory operation.
While the memory area is locked other threads are prevented from accessing it until the lock has been removed. This method is an acceptable way of allocating memory for one-time or infrequent operations, for example, the one-time startup required by a process. However, computing generally requires execution of operations that occur hundreds or even thousands of times per second, for example, when many threads are modifying a common memory area by performing a “write” operation. For such operations this method of locking and unlocking shared memory creates bottlenecks in system performance. As the number of threads making demands on system performance increases, the likelihood of a system bottleneck increases. This of course negatively impacts system performance.
SUMMARY OF THE INVENTION
Methods, systems, and articles of manufacture consistent with the present invention allocate blocks of a shared memory to threads during execution in a data processing system. Methods, systems, and articles of manufacture consistent with the present invention, as embodied and broadly described herein, involve operations that include receiving a memory allocation request, determining whether access to the shared memory is permitted for purposes of the allocation request, identifying a next available memory block in response to the memory allocation request, and designating the next available memory block in response to the request.


REFERENCES:
patent: 5499349 (1996-03-01), Nikhil et al.
patent: 5530816 (1996-06-01), Holt
patent: 5675790 (1997-10-01), Walls
patent: 5784698 (1998-07-01), Brady et al.
patent: 5963975 (1999-10-01), Boyle et al.
patent: 5978892 (1999-11-01), Neel et al.
patent: 5991893 (1999-11-01), Snider
patent: 6044438 (2000-03-01), Olnowich
patent: 6101525 (2000-08-01), Hecker
patent: 6125430 (2000-09-01), Noel et al.
Ian Foster,Designing and Building Parallel Programs, Addison-Wesley Publishing Company, 1995.
Barry Wilkinson and Michael Allen,Parallel Programming, Prentice Hall, 1999.
David E. Culler and Jaswinder Pal Singh,Parallel Computer Architecture, Morgan Kaufman Publishers, Inc., 1999.
Sun Microsystems Computer Company,Prism 5.0 Reference Manual, Revision A., Nov. 1997.

Affiliated with

Also associated with

Rating

Protocol for coordinating the distribution of shared memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Protocol for coordinating the distribution of shared memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Protocol for coordinating the distribution of shared memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2823019