Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-06-16
2002-12-10
Banankhah, Majid (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C717S162000, C712S212000
Reexamination Certificate
active
06493740
ABSTRACT:
FIELD OF THE INVENTION
The field of this invention pertains to computer systems, and more particularly, is directed to multi-threaded processing in a computer system.
DESCRIPTION OF THE TECHNOLOGY
A typical computer system is comprised of a collection of software, accessible by a variety of executing threads; i.e. applications.
As shown in
FIG. 2
, software code may be organized into software libraries
101
. A software library
101
is a collection of software packages
103
. A software package
103
is a collection of related procedures
105
and/or functions
107
, collectively termed routines, stored together in the computer system for continued use as a unit. Software packages
103
provide a method of encapsulating and storing related procedures
105
and functions
107
together as a unit.
Procedures
105
and functions
107
each consist of a set of computer language statements functionally grouped together as an executable unit to perform a specific task. Procedures
105
and functions
107
are essentially equivalent constructs, except that functions
107
return a single value to the caller, while procedures
105
do not return any value. Procedures
105
and functions
107
may be called explicitly by applications or user stations of a computer system.
A typical multi-context/shared data architecture for a computer system, as depicted in
FIG. 3
, has a plurality of software packages in a software library
201
. Each software package has a related context associated with it. A context in this multi-context/shared data architecture is a collection of data required by the routines of a software package to execute properly. Thus, the software package
202
is associated with the context
203
, the software package
204
is associated with the context
205
and the software package
206
is associated with the context
207
.
The data in each context in the software library
201
is designated, i.e., designed to be, shared, or global, or exposed, data. Thus, threads executing the software library, either consecutively or concurrently, access the same data in a context when they call the same routines of a software package.
Threads are lightweight processes that exist within a larger process. In a multi-context/shared data architecture, threads share the same software code and related data, but have their own individual program counters, machine registers and stacks. A process is a mechanism that can execute a series of steps; some systems refer to processes as “jobs” or “tasks”.
For example, if there are two threads
304
and
306
, as depicted in
FIG. 4A
, executing consecutively, and both call the same procedure
305
in the software package
302
, then both threads
304
and
306
share data in the context
303
. However, because the two threads
304
and
306
execute consecutively, i.e., one after the other, there are no data access contention issues. As one thread executes before the other, the first thread to execute finishes accessing the shared data in the context
303
before the second thread begins to execute. Executing consecutively, threads
304
and
306
will not access the same data at the same time.
Yet, if the same two threads
304
and
306
execute concurrently, and both threads
304
and
306
call the same procedure
305
in the software package
302
, the situation raises data access contention concerns. This is because both threads
304
and
306
may potentially attempt to access the same data in the context
303
at essentially the same time.
In such a situation, one thread may change the value of a data item that a second thread is relying on to have an original, unchanged value. This can result in faulty processing by the second thread. Thus, when two or more threads may potentially access the same data at the same time, a mutual exclusivity mechanism, i.e., a mutex, is generally required to manage access to the shared data in the context
303
.
A mutex may be a semaphore
312
. When a first thread
304
calls
308
a procedure
305
in a software package
302
, thereby accessing data in the related context
303
, the semaphore
312
associated with context
303
is set. When a second thread
306
thereafter calls
310
the procedure
305
in the software package
302
, involving access to the data in the related context
303
, the second thread
306
first checks the context
303
associated semaphore
312
. As semaphore
312
has been set by the first thread
304
, the second thread
306
must wait to gain access to data in the context
303
.
When the first thread
304
exits from the procedure
305
in the software package
302
, it no longer requires access to the data in the related context
303
. Thus, the semaphore
312
is reset to indicate that the data in the context
303
is not being accessed. Sometime thereafter, when the second thread
306
checks the semaphore
312
and discovers that it indicates that the data in the context
303
is not being accessed, then the semaphore
312
is once again set, and the second thread
306
continues its processing, executing the procedure
305
.
As with the first thread
304
, when the second thread
306
exits the procedure
305
in the software package
302
, it no longer requires access to the data in the related context
303
. Thus, the semaphore
312
is once more reset to indicate that the data in the context
303
is not being accessed.
A package that uses shared data and relies on a mutex to protect the data from access contentions is referred to as a thread-safe package. An advantage of a thread-safe package is that threads may share the same data. Another advantage of a thread-safe package is that it conserves memory space. The same data is used by each thread calling a particular routine in a specific software package. Thus, in computer systems where memory space and/or allocation are at a premium, thread-safe packages are favored.
A disadvantage of thread-safe packages is that their use can affect the processing time of concurrently executing threads. For example, if there are ten threads executing concurrently and they all call a routine in the same software package at essentially the same time, then nine threads will thereafter have to wait for the first thread to gain access to the data in the related context to exit the associated routine. Thereafter, eight threads will have to wait for the second thread to gain access to the data in the related context to exit the associated routine, and so on. The tenth thread to gain access to the respective data, thereby continuing its processing, may be forced to wait a relatively long time to do so. In time critical processing threads, this wait may fail to meet established system performance requirements.
In an alternative multi-context/unshared data architecture, an example of which is depicted in
FIG. 4B
, the data in each context is designated unshared, or private, or local. With this architecture, threads executing either consecutively or concurrently create a copy of the context for each software package that they access via a routine call. The software packages in a multi-context/unshared data architecture do not rely on a mutex to protect data from concurrent access. Thus, these packages may be referred to as non thread-safe packages.
Non thread-safe packages, rather than using mutexes for data protection, rely on the accessing threads to first make a copy of the package's context, and thereafter execute the respective routines using the context copy.
For example, if two threads
404
and
406
execute consecutively, and both threads call the same procedure
405
in the software package
402
, then both threads will need to access the data in the related context
403
. As the software package
402
is non thread-safe, meaning its related data in the context
403
is not to be shared, when a first thread
404
calls
408
procedure
405
in the software package
402
, a copy
412
of the context
403
is created for this first thread's use. Likewise, when a second thread
406
calls
410
procedure
405
, a copy
41
Banankhah Majid
Lyon & Lyon LLP
Oracle Corporation
LandOfFree
Methods and apparatus for multi-thread processing utilizing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for multi-thread processing utilizing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for multi-thread processing utilizing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2987284