INFORMATION PROCESSING APPARATUS AND METHOD FOR CARRYING OUT MULTI-THREAD PROCESSING

• US 20130014114A1
• Filed: 09/12/2012
• Published: 01/10/2013
• Est. Priority Date: 05/24/2010
• Status: Active Grant

• Current Assignee: Sony Interactive Entertainment Inc. (Sony Group Corp.)
• Original Assignee: Sony Computer Entertainment Incorporated (Sony Group Corp.)
• Inventors: NAGATA, Akihito
• Granted Patent: US 9,658,905 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• 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; and

at least one processor configured to process either of a data generation thread for placing data generated into the data queue or a data consumption thread for retrieving the data from the data queue,

wherein, when there is no data to be retrieved in the data queue during processing of the data consumption thread, the processor placed identification information of the data consumption thread into the data queue, and

wherein, when the data is to be placed into the data queue during processing of the data generation thread and when the identification information of the data consumption thread has been placed into the data queue, the processor changes a storage location of the data in such a manner that the data consumption thread is acquired.

2. An information processing apparatus according to claim 1, wherein after placing the identification information of the data consumption thread into the data queue during processing of the data consumption thread, the processor temporarily suspends the process of the data consumption thread.

3. An information processing apparatus according to claim 2, 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.

4. 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.

5. An information processing apparatus according to claim 4, 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.

6. An information processing apparatus according to claim 4, 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.

7. An information processing apparatus according to claim 1, 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.

8. 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.

9. 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.

10. An information processing method comprising:

placing the identification information of a first thread into a queue, when data is attempted to be retrieved from the queue stored in a memory during processing of a first thread performed by a processor but there is no data to be retrieved; and

sending data to the first thread, when the data is to be placed into the queue during processing of a second thread performed by the processor and identification information of the first thread has been placed into the queue.

11. A non-transitory computer-readable medium in which a program embedded, the program comprising:

a first thread module operative to place the identification information of a first thread into a queue, when data is attempted to be retrieved from the queue stored in a memory during processing of a first thread performed by a processor but there is no data to be retrieved; and

a second thread module operative to send data to the first thread, when the data is to be placed into the queue during processing of a second thread performed by the processor and identification information of the first thread has been placed into the queue.

12. An information processing apparatus comprising:

a processor configured to process a thread that accesses an object requiring synchronization management; and

a memory configured to store a queue that represents a pending queue of threads requesting access to the object, the queue being structured by a linked list such that the identification information of each thread is connected by a pointer indicating the identification information of a subsequent thread in the queue,

wherein information concerning a current state of the object is appended to a head pointer, which is a pointer indicating the identification information of a first thread in the linked list, and

wherein, when the thread requests access to the object, the thread determines whether or not access is granted by referencing the information concerning the current state of the object appended to the head pointer, and

wherein, if access is not granted, the identification information of the thread is placed into the queue.

13. An information processing apparatus according to claim 12, wherein when the thread completes access to the object, the thread determines whether or not a thread requesting access is in the queue, by referencing the information concerning the current state of the object appended to the head pointer in the linked list, and

wherein, if determined that there is the thread requesting access in the queue, the identification information of the thread is retrieved from the queue.

14. An information processing apparatus according to claim 13, wherein, if access is not granted, the thread places the identification information of the thread into the queue and then comes to a stop state, and

wherein, when another thread completes access to the object and when there is identification information of the thread requesting access in the queue, the another thread resumes a process of the thread, associated with the identification information that is in the stop state.

15. An information processing apparatus according to claim 12, wherein information concerning access requested by a thread indicated by the pointer is appended to the pointer in the linked list,

wherein, when the identification information of the thread requesting access is retrieved from the queue, the thread updates the head pointer in such a manner that the head pointer indicates identification information of the subsequent thread, and

wherein the thread updates the information concerning the current state of the object appended to the head pointer based on the information concerning access requested by the subsequent thread appended to the pointer associated with the retrieved identification information of the thread.

16. An information processing apparatus according to claim 12, wherein an operation of placing the identification information of the thread into the queue and an operation of retrieving the identification information thereof from the queue 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 on a queue of another thread is not inhibited even though the operation of placing the identity information thereof into the queue or the operation of retrieving the identity information thereof from the queue is incomplete.

17. An information processing apparatus according to claim 16, wherein, when the operation on the queue 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 queue or the operation of retrieving the identification information thereof from the queue 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 queue or the operation of retrieving the identification information thereof from the queue.

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

19. An information processing apparatus according to claim 15, wherein access to the object is usage of resources,

wherein the information concerning the current state of the object appended to the head pointer is the number of usable resources, and

wherein the information concerning access requested by the subsequent thread appended to each pointer is the number of resources requested.

20. An information processing apparatus according to claim 19, wherein the number of usable resources of a negative value represents the resource is insufficient for demand.

21. An information processing apparatus according to claim 15, wherein access to the object is read/write access from/to data stored in the shared memory,

wherein the information concerning the current state of the object appended to the head pointer is the number of threads that read the data and the number of threads that write the data, and

wherein the information concerning access requested by the subsequent thread appended to each pointer is distinguished between read and write.

22. An information processing method comprising:

referencing a queue when access needs to be made to an object requiring synchronization management during processing a thread, the queue being a pending queue requesting access to the object being structured by a linked list such that identification information of each thread is connected by a pointer indicating the identification information of a subsequent thread in the queue;

determining whether or not access is granted by acquiring information concerning a current state of the object appended to a head pointer, which is a pointer indicating the identification information of a first thread in the linked list; and

placing the identity information of the thread into the queue when access is not granted.

23. A non-transitory computer-readable medium in which a program embedded, the program comprising:

a referencing module operative to reference a queue when access needs to be made to an object requiring synchronization management during processing a thread, the queue being a pending queue requesting access to the object being structured by a linked list such that identification information of each thread is connected by a pointer indicating identification information of a subsequent thread in the queue;

a determining module operative to determine whether or not access is granted by acquiring information concerning a current state of the object appended to a head pointer, which is a pointer indicating the identification information of a first thread in the linked list; and

a push module operative to place the identity information of the thread into the queue when access is not granted.