Method and Apparatus for Managing Thread Private Data in a Parallel Processing Computer

1. Field of the Invention

The present invention relates to parallel processing in a computer using threads which share a task address space and in which each thread has a separately assigned stack, and more particularly to a method and an apparatus for managing globally declared data privately for each thread.

2. Description of the Background Art

As a model for representing parallel processing in a computer effectively, there is a model in which a usual abstraction of a process is split into two components: the task and the thread.

In this model, the task defines the static execution environment such as an address space, while the thread defines the dynamic execution environment such as a program counter.

In such a model, it is possible for any number of threads to be present simultaneously within a given single task. In other words, it is possible for multiple threads of control to be executed simultaneously by using the same data in the given task.

The use of this model employing the concepts of tasks and threads has the following advantages over the usual parallel execution of multiple processes.

(1) The communication between threads can be made at high speed because it is achieved through shared data.

(2) The thread is assigned a relatively small number of resources compared with a process, so that the overhead due to generation and termination is less for threads than for processes.

In such a model using tasks and threads, the address space is shared among the threads, so that the global data are shared by all the threads.

For example, the data used in a program written in the programming language C can be classified into two categories: global variables and auto variables. In these two categories, the global variables, which correspond to the global data to be shared among the threads in the above described model, are usually allocated in the data space as they are to be accessible from a plurality of functions, while the auto variables are usually allocated on the stacks as they are declared within a function and valid only within that function.

Now, in the multi-threaded environment in which multiple threads are present in a single task, it is necessary for each thread to support globally declared data privately. As an example of such a multi-threaded environment in which thread private data are required, a multi-threaded server will be described below.

In this example, the multi-threaded server implements an environment in which multiple threads that perform realizing the same service are present within a single task, and a plurality of service requests from a plurality of servers can be executed simultaneously. This multi-threaded server can be realized by the following program in the C programming language, for example.

In this case, in order for each thread to receive the service request, each thread calls the "get.sub.-- job" function first, and calls the "receive" function in the "get.sub.-- job" function, and then receives the message into the variable "m". This message variable "m" is usually going to be processed by a plurality of functions, so that it is necessary to allocate this variable globally. However, under the multi-threaded environment, globally declared data are shared among the threads so that there is a possibility that the message will be destroyed in this program. For example, when a plurality of service requests arrive, the request content of these service requests are stored as the message variable "m", but this message variable "m" is shared among the threads, so that the message that arrived later will overwrite the message that arrived earlier. Therefore, there is a possibility that the message that arrived earlier will be destroyed by the message that arrive later.

For this reason, it is necessary in such a multi-threaded environment to employ a specially devised data management method for supporting global data privately an a per thread basis.

Conventionally, the following two methods have been proposed as specially devised data management methods.

(I) Method for allocating private data on stack dynamically.

In this method, thread private data are allocated on the stack by declaring data used in several functions as auto variables in a certain function that is executed by each thread. Here, however, when the allocated data are to be used in other functions than the function that declared the auto variable, it is not possible for the other functions to directly access the allocated auto variables. There arises a need for handing the address of the allocated variable as a function argument from the calling function to that called function.

An exemplary program written in the C programming language of adopting this method is shown in FIG. 1. In this program of FIG. 1, after each thread is generated, each thread starts the execution from the function "start". Moreover, in order to support the private data "private.sub.-- data" for each thread, the private data are declared within the function "start" and allocated on the stack. When calling the functions "func1" and "func2" from the function "start", the private data "private.sub.-- data" cannot be accessed from either "func1" or "func2", so that there is a need to pass the address of this private data from the function "start" to the functions "func1" and "func2" as a function argument.

Thus, in this conventional data management method for supporting private data for each thread, there is a need to pass the address of the private data as a function argument when calling one function from another function. Therefore, the program entry for the called function which operates on the private data must contain the argument specifying the address of the private data, and consequently the program becomes quite complicated. In addition, in the called function, there is a need to store the address of the private data on the stack. Furthermore, the access to the private data can be made only indirectly through the address, so the execution efficiency is lowered.

(II) Method for expanding variables in correspondence to multiple threads, and accessing variables by using thread IDs.

In this method, each part of the thread private data is globally declared as a global sequence having as many elements as there are threads. An access from each thread is made by using a thread ID which is uniquely assigned to each thread in advance. In this method, if the thread IDs are not supported at the OS level, it becomes necessary to support the thread IDs themselves by using the specialized method (I) described above. Moreover, even when the thread IDs are supported at the OS level, this method is not applicable to a case in which a number of threads changes dynamically.

An exemplary program written in the C programming language adopting this method is shown in FIG. 2. In this program of FIG. 2, the private data "private.sub.-- data" is declared as a global sequence. A number of elements allocated to this global sequence is defined by a predetermined constant "THREAD.sub.-- NUM". The access to the private data is made by using the thread ID "THREAD.sub.-- SELF".

In this example, the number of elements involved in the global sequence is unchangeably fixed to "THREAD.sub.-- NUM", so that there is a limit to a number of threads that can be accommodated. In addition, in order for each thread to be able to make an access to the private data, it is necessary for the thread ID "THREAD.sub.-- SELF" of each thread to be supported at the OS level.

Thus, in this conventional data management method for supporting the global data privately by each thread, there is a need to provide the thread IDs. In addition, this method cannot deal with a situation involving the generation and termination of threads in which a number of threads changes dynamically. Here, there is a proposition to modify this method to be able to deal with the generation and termination of threads by utilizing a structure employing the hashing of the thread IDs, but this in turn lowers the execution efficiency considerably. Furthermore, the maximum number of threads that can be supported is limited by the number of elements defined in the global sequence in this method.

It is therefore an object of the present invention to provide a method and an apparatus for managing thread private data in which the thread private data can be declared globally without using thread IDs.

It is another object of the present invention to provide a method and an apparatus for managing thread private data which can deal with the dynamic change of the number of threads due to the generation and termination of threads.

According to one aspect of the present invention there is provided a method of managing thread private data in a computer program to be executed by using multiple threads in the address space of a single task, where each one of the multiple threads is associated with a different stack for storing the local data of said each one of the multiple threads, the method comprising the steps of: detecting the thread private data to be globally accessible from the multiple threads and to be used separately by each one of the multiple threads of the program; allocating on the stack a thread private data region for each of the threads for storing the thread private data detected in the detecting step; registering pointers to specify the respective base addresses of each of the thread private data regions with respect to the respective stacks for each one of the multiple threads; and while executing one of the multiple threads, accessing the thread private data region in the stack for said one of the multiple threads according to the base address specified by the pointer registered at the registering step for said one of the multiple threads.

According to another aspect of the present invention there is provided an apparatus for managing thread private data in a computer program to be executed by using multiple threads in the address space of a single task, where each one of the multiple threads is associated with a different stack for storing the local data of said each one of the multiple threads, the apparatus comprising: means for detecting the thread private data to be globally accessible from the multiple threads and to be used separately by each one of the multiple threads of the program; means for allocating on the stack a thread private data region for each of the threads for storing the thread private data detected by the detecting means; means for registering pointers to specify the respective base addresses of each of the thread private data regions with respect to the respective stacks for each one of the multiple threads and means for accessing the thread private data for one of the multiple threads while executing said one of the multiple threads, according to the base address specified by the pointer registered by the registering means for said one of the multiple threads.

Other features and advantages of the present invention will become apparent from the following description taken in conjunction with the accompanying drawings.

FIG. 1 is an illustration of an exemplary program in the C programming language incorporating one conventional method for managing thread private data.

FIG. 2 is an illustration of an exemplary program in the C programming language incorporating another conventional method for managing thread private data.

FIG. 3 is a block diagram of one embodiment of an apparatus for managing thread private data according to the present invention.

FIG. 4 is a diagram representing a major operation sequence in the apparatus of FIG. 3 schematically.

FIG. 5 is an illustration of an exemplary program in the C programming language containing the private data to be managed by the apparatus of FIG. 3.

FIG. 6 is an illustration of an internal data structure to be used in a private data recognition unit in the apparatus of FIG. 3.

FIG. 7 is an illustration of an exemplary executable file to be used in the apparatus of FIG. 3, containing the access instructions for the private data to be managed by the apparatus of FIG. 3.

FIG. 8 is a flow chart for the operation of the private data recognition unit in the apparatus of FIG. 3.

FIG. 9 is a flow chart for the operation of a thread set up unit in the apparatus of FIG. 3.

FIG. 10 is an illustration of stacks with the private data region allocated by the operation of the thread set up unit according to the flow chart of FIG. 8.

FIG. 11 is a flow chart for the operation of a thread switching unit in the apparatus of FIG. 3.

Referring now to FIG. 3, one embodiment of an apparatus for managing thread private data according to the present invention, which carries out a method for managing thread private data according to the present invention, will be described in detail.

In this embodiment, the apparatus comprises: a program input unit 1 for inputting a program to be executed; a compiler unit 2 for compiling the program inputted from the program input unit 1; a private data recognition unit 3 for recognizing all private data appearing in the program while the program is compiled at the compiler unit 2; an executable file memory unit 4 for storing an executable file obtained from the program compiled at the compiler unit 2 and analyzed in the private data recognition unit 3; an execution unit 5 for executing the executable file stored by the executable file memory unit 4; a stack unit 6 containing a stack in correspondence to each thread used in the execution at the execution unit 5; a private stack pointer (PSP) register 7 for registering the private stack pointer to indicate the base address of the private data region to be formed in each stack in the stack unit 6; a stack pointer (SP) register 8 for registering a top address of the private data region in each stack in the stack unit 6; a thread set up unit 9 for managing the stack unit 6, the private stack pointer register 7, and the stack pointer register 8 for each thread executed in the execution unit 5; a thread switching unit 10 for switching the settings of the private stack pointer register 7 and the stack pointer register 8 according to a change of a currently executed thread being executed in the execution unit 5; and a thread context managing unit 11 for managing the values stored in the private stack pointer register 7 and the stack pointer register 8 for each thread used in the execution at the execution unit 5.

In this embodiment, the private data region for storing the private data declared in the program is set up separately in each stack for each thread in the stack unit 6, such that the private data can be managed separately for each thread in the stack for each thread.

In this regard, the major operation sequence in the apparatus of FIG. 3 can be represented schematically as shown in FIG. 4. In general, the program 102 inputted from the program input unit 1 and compiled at the compiler unit 2 is checked by the private data recognition unit 3 to produce the appropriate executable file 103 in the executable file memory unit 4. Then, according to the execution of this executable file 103 at the execution unit 5, the thread set up unit 9 is operated to set up the private data region 106 within each stack in the stack unit 6 separately for each thread used in the execution. The base address of the private data region 106 is pointed to by the private stack pointer (PSP) registered in the private stack pointer register 7. Whenever the currently executed thread is to be switched from one thread to another thread, the thread switching unit 10 is operated to adjust the value of the private stack pointer (PSP) in the private stack pointer register 7.

Further detail of the operation in this apparatus of FIG. 3 will now be described.

In this apparatus of FIG. 3, while the program 102 inputted from the program input unit 1 is compiled at the compiler unit 2, the private data recognition unit 3 recognizes all private data variables appearing in the program 102 and determines the appropriate size of the private data region 106 to store the private data variables and a position (offset) of each private data variables within the private data region 106. The determined size of the private data region 106 is then recorded into a header portion of the executable file 103 in the executable file memory unit 4. The private data recognition unit 3 also generates an appropriate access instruction for accessing each private data variables according to the determined position (offset) of each private data variables. The generated access instructions are then recorded into the text executable of the executable file 103 at the executable file memory unit 4.

For example, suppose that the program 102 written in the C programming language which is compiled at the compiler unit 2 has a section as shown in FIG. 5 which contains a declaration of "data1" and "data2" as private data variables at a line 201, and functions "func1" and "func2" including access instructions for "data1" and "data2" at lines 202 and 203, respectively.

In such a case, the private data recognition unit 3 creates an internal data structure as shown in FIG. 5, which includes a private data region size indication 301 and private data position indication 302. In this example, each of the private data variables "data1" and "data2" is an integer expressed by 4 bytes, so that the private data region size indication 301 indicates 8 bytes and the private data position indication 302 indicates a position "0" and a position "4" for "data1" and "data2", respectively, as shown in FIG. 6. The determined private data region size of 8 byte is subsequently recorded into the header portion of the executable file 103 in the executable file memory unit 4.

Then, the private data recognition unit 3 generates the appropriate access instructions for these private data variables "data1" and "data2", to be recorded into the text portion of the executable file 103 in the executable file memory unit 4, according to the positions (offsets) of the private data variables within the private data region 106 indicated in the private data position indication 302, as shown in FIG. 7. Namely, in FIG. 7, lines 401 and 402 containing the access instructions are inserted as part of "func1" and "func2", respectively. The access instruction at a line 401 for instance is an "st" (store) instruction for storing a variable "X" into the address specified by its argument "PSP-0", i.e., the data at an address obtained by subtracting an offset "0" from the base address of the private data region 106 in a stack 104 in the stack unit 6, which is "data1".

Thus, the operation of the private data recognition unit 3 in conjunction with the preparation of the executable file 103 prior to the execution at the execution unit 5 is carried out according to the flow chart of FIG. 8, as follows.

First, at the step S1, the private data variables declared in the program 102 are detected by using the expression "private" used in the program 102 as a keyword.

Then, at the step S2, the appropriate size of the private data variables region 106 needed to store the private data detected at the step S1 is calculated.

Then, at the step S3, the appropriate size of the private data region 106 calculated at the step S2 is recorded into a header portion of the execution file 103 stored in the executable file memory unit 4.

Then, at the step S4, the offset for each private data variables, i.e., a position of each private data variable within the private data region 106 with respect to the base address of the private data region 106, is determined.

Finally, at the step S5, the appropriate access instruction for each private data variable is generated according to the offset determined at the step S4, and the generated access instructions for all the detected private data variables are recorded into the text exectable portion of the executable file 103 stored in the executable file memory unit 4.

Now, when the executable file 103 so prepared is actually executed at the execution unit 5, the threads are generated and the current thread is switched among the generated threads according to the executable file 103.

In a case of generating a new thread during the execution at the execution unit 5, the thread set up unit 9 operates according to the flow chart of FIG. 9, as follows.

First, at the step S11, the thread set up unit 9 reads the size of the private data region 106 recorded in the header portion of the executable file 103.

Then, at the step S12, the thread set up unit 9 obtains a new stack 104 for a newly generated thread in the stack unit 6, and allocates the private data region 106 of the specified size within this new stack 104 for the newly generated thread. Here, in this embodiment, the private data region 106 is to be allocated at a lowest portion of the stack 104, although it may very well be allocated anywhere else in the stack 104, if desired.

Then, at the step S13, the thread set up unit 9 sets the base address of the private data region 106 in the new stack 104 for the newly generated thread, which is equal to the base address of the new stack 104 in this case, to the private stack pointer (PSP) in the private stack pointer register 7.

Finally, at the step S14, the thread set up unit 9 sets the top address of the private data region 106 in the new stack 104 for the newly generated thread to the stack pointer (SP) in the stack pointer register 8. Here, the stack pointer (SP) may be set to any other address above the top address of the private data region 106 if desired. The remaining region in the stack 104 above the stack pointer (SP) is subsequently utilized as a usual stack for storing the local data used only in the associated thread.

As a result of this operation by the thread set up unit 9, as shown in FIG. 10, the private data region 106 of the specified size used to store the private data "data1" and "data2" is set up in each one of the stacks for the threads 1 to n separately, with the private stack pointer (PSP) pointing to the base address of the private data region 106 while the stack pointer (SP) points to the top address of the private data region region 106.

Now, when switching the current thread during execution at the execution unit 5, the thread switching unit 10 operates according to the flow chart of FIG. 11, as follows.

First, at the step S21, the thread switching unit 10 reads the values of the private stack pointer (PSP) and the stack pointer (SP) for the current thread, and then at the step S22, the thread switching unit 10 stores these values into the thread context managing unit 11. The thread context managing unit 11 stores the values of the private stack pointer register 7 and the stack pointer register 8 for each thread separately.

Then, at the step S23, the thread switching unit 10 reads the values of the private stack pointer (PSP) and the stack pointer (SP) for the next thread to be executed from the thread context managing unit 11.

Finally, at the step S24, the thread switching unit 10 sets these values for the next thread into the private stack pointer register 8 and the stack pointer register 9.

As a result of this operation by the thread switching unit 10, the private stack pointer register 8 and the stack pointer register 9 are always set with the settings of the private stack pointer (PSP) and the stack pointer (SP) for the currently executed thread.

Thus, when an access instruction, such as those shown in FIG. 7, is encountered in the execution at the execution unit 5, the access to the desired private data is made by making an access to the address obtained by subtracting the offset of the desired private data specified in the access instruction from the private stack pointer (PSP) of the current thread indicated by the private stack pointer register 8.

As described above, according to the present invention, it becomes possible to provide a method and an apparatus for managing thread private data in which the thread private data variables can be declared globally as normal global data, because the private data region is set up in each stack for each thread separately. Consequently, the program is less complicated and aids in preventing the introduction of bugs into the program.

Moreover, as each private data variables is given a fixed position with respect to the private data region, there is no need to make an indirect access by specifying the address of a variable every time the private data is to be accessed. This improves the efficiency of the program execution.

In addition, according to the present invention, it also becomes possible to provide a method and an apparatus for managing thread private data which can handle changes in number of threads of a computer program due to the dynamic generation and termination of threads, because the private data region is set up in the stack of each thread independently.

It is to be noted that, besides those already mentioned above, many modifications and variations of the above embodiments may be made without departing from the novel and advantageous features of the present invention. Accordingly, all such modifications and variations are intended to be included within the scope of the appended claims.