Method of starting execution of threads simultaneously at a...

Details Method of starting execution of threads simultaneously at a... Method of starting execution of threads simultaneously at a...

2000-05-18

2004-01-06

Banankhah, Majid (Department: 2127)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C709S241000, C709S241000, C710S260000, C712S220000

Reexamination Certificate

active

06675191

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technique of starting execution of threads simultaneously at a plurality of processors at the time of thread context switching in a multi-processor system and, more particularly, to a technique of handling a plurality of thread execution states at a plurality of processors, that is, a plurality of thread contexts, as a single unit.
2. Description of the Related Art
As an example of a conventional kernel scheduler at a plurality of processors, handling of threads in Solaris is recited in “Uresh Vahalia: UNIX Internals The New Frontiers, Prentice Hall, pp. 130-139, 1996” and “Bill Luis and Daniel Berk: Guidance to Multi-thread Programming, ASCII Publishing, pp. 73-77, September 1996”. Unit for exclusive control among a plurality of processors is described in “A. S. Tanenbaum: Basics and Application of OS, Prentice Hall Toppan Company, 2nd chapter, 2nd paragraph. An example of a multi-processor system which executes a plurality of generated tasks in parallel to each other is recited in Japanese Patent Laying-Open (Kokai) No. Heisei 9-319653.
As shown in
FIG. 9
, structure of the conventional kernel scheduler having the minimum number of processors includes an input device
1
, a first processor
27
, a second processor
28
, an inter-processor interruption notification device
29
, a main storage
3
and an output device
4
.
Further included are in the first processor
27
, an exception management device
271
, and an interruption processing unit
272
and a kernel scheduler unit
273
executed by the first processor
27
, in the second processor
28
, an exception management device
281
, and an interruption processing unit
282
and a kernel scheduler unit
283
executed by the second processor
28
, and on the main storage
3
, an exclusive control variable
31
, a context save area
32
, a dispatch queue
33
and a priority list
38
.
FIG. 10
is a flow chart showing operation of the interruption processing units
272
and
282
and the kernel scheduler units
273
and
283
of FIG.
9
.
Operation of thus structured conventional kernel scheduler will be described in the following with reference to
FIGS. 9 and 10
.
Assume that a processor which receives an exception applied through the input device
1
is the first processor
27
, a first exception factor
11
is received by the exception management device
271
of the first processor
27
to activate the interruption processing unit
272
(Step S
1
).
In the interruption processing unit
272
, a context save unit
2723
is called and an execution state of the first processor
27
, that is, a context, is saved, assuming that a currently executed thread is the first thread, as a context
321
of the first thread in the context save area
32
(Step S
2
).
The interruption processing unit
272
subsequently activates the kernel scheduler unit
273
, where an exclusive arbitration unit
2731
is first executed. If the second processor
28
has changed the exclusive control variable
31
, the unit
2731
waits (Step S
3
) and otherwise, rewrites the exclusive control variable
31
to prevent other processors from accessing an area of the dispatch queue
33
or the like necessary for the subsequent operation (Steps S
4
and S
5
).
Subsequently, a dispatch queue operation unit
2732
in the kernel scheduler unit
273
determines whether there exists a thread newly attaining an executable state by the first exception factor
11
and the processing by the interruption processing unit
272
(Step S
6
) and when the thread exists, the unit
2732
registers a structure or an ID number indicative of the thread at the dispatch queue
33
(Step S
7
). The example of
FIG. 9
shows a state where the first processor
27
registers a structure
333
indicative of a third thread as a priority “115”. It is assumed here that the larger the value is, the higher the priority is.
Furthermore, an object to be activated selection unit
2733
searches the threads waiting at the dispatch queue
33
for a thread having the highest priority (Step S
8
) and searches the priority list
38
for a processor whose executing thread has the lowest priority (Step S
9
). In the example of
FIG. 9
, this search obtains the third thread having the priority “115” from the dispatch queue
33
and the second processor being executing the priority “100” from the priority list
38
.
Next, the object to be activated selection unit
2733
determines whether the priority “115” of the structure
333
indicative of the third thread which is the highest priority among the threads waiting at the dispatch queue
33
exceeds the priority “100” of the thread being executed by the second processor which is the lowest priority in the priority list
38
(Step S
10
). In this case, the former priority exceeds the latter, the unit
2733
further determines whether its own processor is executing the lowest priority thread or not (Step S
11
). In this case, the processor is not executing the thread in question. In such a case as this where a priority of a thread waiting at the dispatch queue
33
is higher than a priority of a thread being executed at other processor, an inter-processor interruption unit
2734
gives a notification to a processor which is executing the lowest priority thread by using an inter-processor interruption (Step S
12
). In the example of
FIG. 9
, the second processor
28
is to be notified.
The first processor
27
, after giving a notification using an inter-processor interruption, releases exclusive conditions by restoring the exclusive control variable
31
to an original state (Step S
15
) and returns the context to move onto a state prior to generation of the first exception factor
11
. In the example of
FIG. 9
, the processor will return to the original first thread.
On the other hand, at the processor
28
to be notified of an inter-processor interruption, the exception management device
281
of the second processor
28
is given a notification of an inter-processor interruption by the inter-processor interruption notification device
29
to activate the interruption processing unit
282
.
In the interruption processing unit
282
, similarly to the interruption processing unit
272
which has processed the first exception factor
11
, a context save unit
2823
is called to save an execution state of the second processor, that is, a context of the second thread, as a context
322
of the second thread in the context save area
32
(Step S
2
).
The interruption processing unit
282
activates the kernel scheduler unit
283
, where an exclusive arbitration unit
2831
is first executed. When other processor has changed the exclusive control variable
31
in such a case where processing of the kernel scheduler unit
273
at the first processor
27
is yet to be completed or the like, the unit
2831
waits (Step S
3
) and otherwise, the unit changes the exclusive control variable
31
to prevent other processors from accessing an area of the dispatch queue
33
or the like necessary for subsequent operation (Steps
4
and
5
).
Subsequently, a dispatch queue operation unit
2832
in the kernel scheduler unit
283
determines whether there exists a thread newly attaining an executable state by the processing by the inter-processor interruption notification device
29
and the interruption processing unit
282
(Step S
6
) and when the thread exits, the unit
2832
additionally registers the context from the context save area
32
at the dispatch queue
33
(Step S
7
).
In the example of
FIG. 9
, it is assumed that there exists no thread which newly attains an executable state after the structure
333
indicative of the third thread is registered by the first processor
27
.
Furthermore, an object to be activated selection unit
2833
searches the threads waiting at the dispatch queue
33
for a thread having the highest priority (Step S
8
) and also searches the priority list
38
for a processor whose executing thread has the lowest priority (Step S
9
). In the exa

Affiliated with

Also associated with

Rating

Method of starting execution of threads simultaneously at a... 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 of starting execution of threads simultaneously at a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of starting execution of threads simultaneously at a... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3241437