Information processing apparatus and method for carrying out multi-thread processing

• US 9,658,905 B2
• Filed: 09/12/2012
• Issued: 05/23/2017
• Est. Priority Date: 05/24/2010
• Status: Active Grant

• Current Assignee: Sony Interactive Entertainment Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Interactive Entertainment Inc. (Sony Group Corp.)
• Inventors: Nagata, Akihito
• Primary Examiner(s): Bullock, Jr., Lewis A
• Assistant Examiner(s): Aquino, Wynuel
• Application Number:
  US13/611,561
• Publication Number:
  US 20130014114A1
• Time in Patent Office: 1,714 Days
• Field of Search: None
• CPC Class Codes: G06F 2209/548 Queue
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

For a thread where data is to be popped off of queue storage, whether or not there is data that can be popped out of the queue storage accessed is first checked and then the data, if any, is popped. When there is no such data, the thread pushes thread information, including the identification information of its own thread, on the same queue and then releases a processor and shifts to a standby state. For a thread that is to push the data, when there is the thread information in the queue, it is determined that there is a thread waiting for the data, and then the data is sent after the thread information has been popped, which in turn resumes the processing.

Claims

1. An information processing apparatus comprising:

a memory configured to store a data queue comprised of individual data, wherein the data queue comprises a head position and a tail position; and

at least one processor configured to process a data generation thread and a plurality of data consumption threads, the data generation thread placing generated data into the data queue by performing the steps of;

determining what type of data is located at an element identified by the head position of the data queue;

if the head position data contains thread identification relating to one of the plurality of data consumption threads, remove the head position element from the data queue and directly assign the generated data to the data consumption thread associated with the thread identification information for processing the generated data;

if the head position data does not contain thread identification of any of the plurality of data consumption threads, pushing the generated data at the tail position of the data queue by the data generation thread;

a data consumption thread of the plurality of data consumption threads, processing data of the data queue, by performing the steps of;

checking the data located at the head position of the data queue to determine whether the data queue is empty, wherein the data queue is empty if the data at the element in the head position stores thread identification data;

based on the checking, if the data queue is not empty, remove and process the data from the data queue by the data consumption thread;

based on the checking, if the data queue is empty;

insert into the data queue an element containing the thread identification of the data consumption thread at the tail position of the data queue; and

suspend the data consumption thread to allow for further processing of the processor.

2. An information processing apparatus according to claim 1, wherein, when the identification information of the data consumption thread exists in the data queue during processing of the data generation thread, the processor changes a state of the data consumption thread which has been suspended to a state to be resumed.

3. An information processing apparatus according to claim 1, wherein an operation of placing the data into the data queue during processing of the data generation thread and an operation of retrieving the data from the data queue during processing of the data consumption thread are performed in stages in units of predetermined atomic operations, and during a period of time other than a period of atomic operation, an operation on the data queue for processing another thread is not inhibited even though the operation of placing data into the data queue or the operation of retrieving the data from the data queue is incomplete.

4. An information processing apparatus according to claim 3, wherein, when, during processing of another thread, the operation on the data queue for processing of the other thread is disabled even during the period of time other than the period of atomic operation, the processor determines that the operation of placing data into the data queue or the operation of retrieving the data from the data queue is incomplete, and wherein the processor performs a predetermined operation according to the incomplete state, so as to partially progress at least either of the operation of placing data into data queue or the operation of retrieving the data from the data queue.

5. An information processing apparatus according to claim 3, wherein the data queue is structured by a linked list such that each unit of data is connected by a pointer indicating subsequent data in the data queue, and the operation of placing the data into the data queue and the operation of retrieving the data from the data queue are performed in stages by updating each pointer atomically.

6. An information processing apparatus according to claim 1, wherein the data queue is structured by a linked list such that each unit of data is connected by a pointer indicating subsequent data in the data queue, wherein dummy data is placed in the data queue in a state where neither of the data to be retrieved and the identification information of the data consumption thread are placed therein, and wherein information by which the dummy data is identified is appended to a pointer indicating the dummy data in the linked list.

7. An information processing apparatus according to claim 1, wherein the data queue is structured by a linked list such that each data is connected by a pointer indicating subsequent data in the data queue, wherein, when placing the identification information of the data consumption thread into the data queue during processing of the data consumption thread, the processor appends information, indicating that the identification information thereof has been placed into the data queue, to a pointer indicating the identity information thereof in the linked list, and wherein, during processing of the data generation thread, the processor determines, by referencing the pointer in the linked list, whether or not the identification information of the data consumption thread is placed into the data queue.

8. An information processing method comprising:

processing a data queue, by a processor, accessed by a data generation thread and a plurality of data consumption threads wherein the data queue comprises a head position and a tail position;

placing, by the data generation thread, generated data into the data queue by performing the steps of;

determining what type of data is located at an element identified by the head position of the data queue;

if the head position data contains thread identification relating to one of the plurality of data consumption threads, remove the head position element from the data queue and directly assign the generated data to the data consumption thread associated with the thread identification information for processing the generated data;

if the head position data does not contain thread identification of any of the plurality of data consumption threads, pushing the data at the tail position of the data queue by the data generation thread;

processing data of the data queue, by a data consumption thread of the plurality of data consumption threads, by performing the steps of;

checking the data located at the head position of the data queue to determine whether the data queue is empty, wherein the data queue is empty if the data at the element in the head position stores thread identification data;

based on the checking, if the data queue is not empty, remove and process the data from the data queue by the data consumption thread;

based on the checking if the data queue is empty;

insert into the data queue an element containing the thread identification of the data consumption thread at the tail position of the data queue; and

suspend the data consumption thread to allow for further processing of the processor.

9. A non-transitory computer-readable medium in which a program is embedded, the program is executed by a processor and comprises:

a data queue comprised of individual data, wherein the data queue comprises a head position and a tail position;

the data generation thread placing generated data into the data queue by performing the steps of;

determining what type of data is located at an element identified by the head position of the data queue;

if the head position data contains thread identification relating to one of the plurality of data consumption threads, remove the head position element from the data queue and directly assign the generated data to the data consumption thread associated with the thread identification information for processing the generated data;

if the head position data does not contain thread identification of any of the plurality of data consumption threads, pushing the data at the tail position of the data queue by the data generation thread;

a plurality of data consumption thread of the plurality of data consumption threads, processing data of the data queue, by performing the steps of;

checking the data located at the head position of the data queue to determine whether the data queue is empty, wherein the data queue is empty if the data at the element in the head position stores thread identification data;

based on the checking, if the data queue is not empty, remove and process the data from the data queue by the data consumption thread;

based on the checking if the data queue is empty;

insert into the data queue an element containing the thread identification of the data consumption thread at the tail position of the data queue; and

suspend the data consumption thread to allow for further processing of the processor.

10. An information processing apparatus comprising:

a queue of empty packets indicating information on an unused storage area that stores a predetermined unit of data to be placed into a linked list, the linked list comprising a head position and a tail position;

at least one processor processing a data generation thread and a plurality of data consumption threads;

the processor, during processing of the data generation thread for performing the steps of;

attempting to retrieve an empty packet from the queue of empty packets;

remove an empty packet from the queue of empty packets and place data into the empty packet thereby establishing generated data;

determining what type of data is located at an element identified by the head position of the linked list;

if the head position data contains thread identification relating to one of the plurality of data consumption threads, remove the head position element from the linked list and directly assign the generated data to the data consumption thread associated with the thread identification information for processing the generated data;

if the head position data does not contain thread identification of any of the plurality of data consumption threads, pushing the generated data at the tail position of the linked list by the data generation thread;

a data consumption thread, of the plurality of data consumption threads, processing data of the linked list by performing the steps of;

checking the data located at the head position of the linked list to determine whether the linked list is empty, wherein the linked list is empty if the data at the element in the head position stores thread identification data;

based on the checking, if the linked list is not empty, remove and process the data from the linked list by the data consumption thread;

based on the checking if the linked list is empty;

insert into the linked list an element containing the thread identification of the data consumption thread at the tail position of the linked list; and

suspend the data consumption thread to allow for further processing of the processor.

11. An information processing apparatus according to claim 10, wherein the memory includes a queue of packets comprised of empty packets indicating information on an unused storage area capable of storing a predetermined unit of data to be placed into the data queue, wherein, during processing of data generation thread, the processor attempts to retrieve an empty packet from the queue of packets before the predetermined unit of data generated is placed into the data queue, wherein, when there is no empty packet to be retrieved, the processor places the identification information of the data generation thread into the queue of packets, and wherein, when, during processing of the data consumption thread, an empty packet, which is no longer needed, is returned to the queue of packets after a predetermined unit of data is retrieved from the data queue and when the identification information of the data generation thread is placed in the queue of packets, the processor changes the storage location of the empty packet such that the data generation thread acquires the empty packet.

12. An information processing apparatus according to claim 10, wherein the indication of whether the linked list comprises thread identification is indicated in a head pointer in the linked list, wherein, when the identification information of a thread requesting access is retrieved from the linked list, the thread updates the head pointer in such a manner that the head pointer indicates identification information of a subsequent thread, and wherein the thread updates the head pointer based on the information concerning access requested by the subsequent thread.

13. An information processing apparatus according to claim 10, wherein an operation of placing the identification information of the thread into the linked list and an operation of retrieving the identification information thereof from the linked list are performed in stages in units of predetermined atomic operations, and wherein, during a period of time other than a period of atomic operation, an operation of another thread is not inhibited even though the operation of placing the identity information thereof into the linked list or the operation of retrieving the identity information thereof from the linked list is incomplete.

14. An information processing apparatus according to claim 12, wherein, when the operation on the linked list of the thread is disabled even during the period of time other than the period of atomic operation, the another thread determines that the operation of placing the identification information thereof into the linked list or the operation of retrieving the identification information thereof from the linked list is incomplete, and wherein the another thread performs a predetermined operation according to the incomplete state, so as to partially progress at least either of the operation of placing the identification information thereof into the linked list or the operation of retrieving the identification information thereof from the linked list.

15. An information processing apparatus according to claim 10, wherein the operation of placing the identification information of the thread into the linked list and the operation of retrieving the identification information thereof from the linked list are performed in stages by updating each pointer atomically.

16. An information processing method comprising:

storing, in memory, a queue of empty packets indicating information on an unused storage area that stores a predetermined unit of data to be placed into a linked list, wherein the linked list comprises a head position and a tail position;

processing, by at least one processor, a data generation thread and a plurality of data consumption threads, the processing, during the processing of the data generation thread, performing the steps of;

attempting to retrieve an empty packet from the queue of empty packets;

removing an empty packet from the queue of empty packets and place data into the empty packet thereby generating data;

determining what type of data is located at an element identified by the head position of the linked list;

if the head position data contains thread identification relating to one of the plurality of data consumption threads, remove the head position element from the linked list and directly assign the generated data to the data consumption thread associated with the thread identification information for processing the generated data;

if the head position data does not contain thread identification of any of the plurality of data consumption threads, pushing the generated data at the tail position of the linked list by the data generation thread;

processing data of the linked list by a data consumption thread of the plurality of data consumption threads by performing the steps of;

checking the data located at the head position of the linked list to determine whether the linked list is empty, wherein the linked list is empty if the data at the element in the head position stores thread identification data;

based on the checking, if the linked list is not empty, remove and process the data from the linked list by the data consumption thread;

based on the checking if the linked list is empty;

insert into the linked list an element containing the thread identification of the data consumption thread at the tail position of the linked list; and

suspend the data consumption thread to allow for further processing of the processor.

17. A non-transitory computer-readable medium in which a program is embedded, the program is executed by a processor and comprises:

a queue of empty packets indicating information on an unused storage area that stores a predetermined unit of data to be placed into a linked list, the linked list comprising a head position and a tail position;

the processor, during processing of the data generation thread for performing the steps of;

attempting to retrieve an empty packet from the queue of empty packets;

remove an empty packet from the queue of empty packets and place data into the empty packet thereby generating data;

determining what type of data is located at an element identified by the head position of the linked list;

if the head position data contains thread identification relating to one of the plurality of data consumption threads, remove the head position element from the linked list and directly assign the generated data to the data consumption thread associated with the thread identification information for processing the generated data;

if the head position data does not contain thread identification of any of the plurality of data consumption threads, pushing the generated data at the tail position of the linked list by the data generation thread;

a data consumption thread, of the plurality of data consumption threads, processing data of the linked list by performing the steps of;

checking the data located at the head position of the linked list to determine whether the linked list is empty, wherein the linked list is empty if the data at the element in the head position stores thread identification data;

based on the checking, if the linked list is not empty, remove and process the data from the linked list by the data consumption thread;

based on the checking if the linked list is empty, insert into the linked list an element containing the thread identification of the data consumption thread at the tail position of the linked list; and

suspend the data consumption thread to allow for further processing of the processor.