Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
1995-08-08
2004-04-27
Banankhah, Majid A. (Department: 2127)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S100000, C718S107000
Reexamination Certificate
active
06728959
ABSTRACT:
COPYRIGHT NOTICE
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The copyright owner does not hereby waive any of its rights to have this patent document maintained in secrecy, including without limitation its rights pursuant to 37 C.F.R. § 1.14.
FIELD OF THE INVENTION
The present invention relates to the allocation and scheduling of processors in a multiprocessing computer system, and more particularly to a thread-scheduling invention which creates a strong affinity between each thread and the processor which is initially allocated to the thread.
TECHNICAL BACKGROUND OF THE INVENTION
Hardware
Many computing systems contain a single central processing unit (“CPU” or “processor”), a primary storage unit directly accessible to the processor, and a secondary storage unit for long-term bulk storage of information. The primary storage typically includes random access memory (“RAM”) and the secondary storage typically includes a magnetid disk, optical disk, or similar-device.
To create more powerful computing systems, these individual architectural components—processors, memories, and disks—have been and are being combined and connected in various ways. A major goal of these alternative architectures is to support parallel processing, that is, processing performed by several processors which are working on different pieces of a given problem at the same time. A parallel processing system is said to be “scalable” if adding additional processors clearly improves the system's performance.
Some parallel processing architectures are generally termed “multiprocessors” or “multiprocessing systems.” Multiprocessors contain at least two processors which communicate with one another through a “shared memory.” Shared memory makes a single virtual address space available to multiple processors, allowing each processor to read and write values at address locations that are accessible to all processors and addressed identically by each processor. Each processor in a multiprocessing system may also have a local private memory, known as its “cache,” which is not shared with the other processors.
Multiprocessors may be connected to each other and/or to single processor systems in a local area network, wide area network, on the Internet, or by other means. Processors which communicate with each other but do not have a common shared memory form a “multicomputing system.” Thus, a local area network is one of many possible types of multicomputing systems. Multiprocessing systems and multicomputing systems are known collectively as “distributed systems.”
Multiprocessors may be “bus-based” or “switched.” One bus-based multiprocessor is illustrated in FIG.
1
. The multiprocessor, which is indicated generally at
10
, includes four processors
12
, each of which has its own cache
14
. The caches communicate through signal lines
15
using MESI or another familiar protocol. The processors
12
communicate with one another through a shared memory unit
16
which is on a common bus.
17
with the processors
12
. The shared memory unit
16
typically includes a memory bus controller and RAM.
The bus
17
also provides communication between the processors
12
and/or shared memory
16
, on the one hand, and a drive
18
capable of reading a medium
19
, on the other hand. Typical drives
18
include floppy drives, tape drives, and optical drives. Typical media
19
include magnetic and optical computer-readable media.
To read the value of a word from the memory
16
, a particular processor such as CPU
1
puts the memory address of the desired word onto the bus
17
and signals that a read is desired. In response, the memory
16
places the value of the addressed word onto the bus
17
, thereby allowing the processor CPU
1
to read the value. Writes to the shared memory
16
are performed in a similar way.
Unfortunately, if shared memory
16
reads and writes are performed only by using this simple approach, then performance of the multiprocessor
10
drops dramatically as additional processors
12
are added. When too many processors
12
are present, the bus
17
cannot transfer information between the processors
12
and the shared memory
16
as rapidly as requested by the processors
12
. System performance then drops because some of the system's processors
12
are idle while they wait for access to the shared memory
16
.
To reduce the load on the bus
17
, copies of the values read or written by a given processor such as CPU
1
may be kept in that processor's cache
14
. Each value is stored in the cache
14
with some indication of the address at which that value is kept in the shared memory
16
. Addresses corresponding to values stored in the cache
14
are called “cached addresses,” while the values stored in the cache
14
are called “cached values.” If the address specified in a read request is a cached address, the corresponding cached value is read from the cache
14
and no request is placed on the bus
17
.
Although caching may dramatically reduce the load on the bus
17
, it also introduces potential inconsistencies. Imagine that processors CPU
1
and CPU
2
each read the word at address A0 from the shared memory
16
and that the value read is zero. Then the cache of CPU
1
and the cache of CPU
2
will each indicate that the value stored at address A0 is zero. Suppose CPU
1
then writes the value one to address A0 of the shared memory
16
. Then the cache of CPU
1
and the shared memory
16
will each indicate that the value stored at address A0 is one, while the cache of CPU
2
will still indicate that the value stored at A0 is zero.
Using one or both of two approaches, known as “write-through caches” and “snooping caches,” will prevent such inconsistencies on bus-based multiprocessing systems unless the number of processors is too large. If the number of processors grows too large, alternative architectures may be used. One alternative multiprocessing architecture, known as a “crossbar switch,” is indicated generally at
20
in
FIG. 2. A
shared memory is divided into modules
22
which are connectable to processors
24
by signal lines
26
. The signal lines
26
may be connected as needed by actuating appropriate crosspoint switches
28
.
Another alternative multiprocessing architecture, known as an “omega switching network,” is indicated generally at
30
in FIG.
3
. Shared memory is again divided into modules
32
which are connectable to processors
34
by signal lines
36
. The signal lines
36
may be connected as needed by actuating appropriate 2×2 switches
38
. In either the crossbar switch multiprocessor
20
(
FIG. 2
) or the omega multiprocessor
30
(FIG.
3
), some or all of the processors
24
,
34
may have a cache similar to the caches
14
in the bus-based multiprocessor
10
(FIG.
1
). The multiprocessors
20
,
30
may also include a drive such as the drive
18
(
FIG. 1
) for reading computer-readable media such as the medium
19
.
Software Generally
Although its underlying hardware limits the theoretical performance of a multiprocessor, in practice limitations imposed by an “operating system” are more frequently encountered. The operating system is software which (among other duties) controls access to the processors. The presence of multiple processors that are capable in theory of working in parallel on a given computational problem does not, in and of itself, make parallel processing a practical reality. The problem must be broken into appropriate parts, the parts must then be efficiently distributed among the processors, and the results of the separate computations must finally be combined to provide a solution to the problem.
Computational problems may be divided into “tasks,” each of which in turn contains one or
Banankhah Majid A.
Dinsmore & Shohl LLP
Novell Inc.
LandOfFree
Method and apparatus for strong affinity multiprocessor... 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 apparatus for strong affinity multiprocessor..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for strong affinity multiprocessor... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3270903