Read and write operations on shared data resources in parallel processing systems

Patent metadata

Field	Value
Publication number	US-9483323-B2
Application number	US-201414246158-A
Country	US
Kind code	B2
Filing date	Apr 7, 2014
Priority date	Apr 7, 2014
Publication date	Nov 1, 2016
Grant date	Nov 1, 2016

Abstract

Providing unblocked read operations concurrent with write operations with respect to shared data resources in parallel processing systems. In an embodiment, for each data resource, a pair of fields and an index field is maintained. The index field indicates which of the two fields (e.g., first field) stores a current value for the data resource. However, when a new value is to be stored for the data resource, the value is first stored in the second field using a execution entity, while ensuring exclusive access for the execution entity to the second field. The index field is then updated to indicate that the second field stores the current value, such that the new value in the second field is thereafter available as the current value for read operations. All read operations by any corresponding concurrent execution entities, during the write operation, are continued unblocked.

First claim

What is claimed is:

1. A method of performing read and write operations on shared data resources in parallel processing systems, said method comprising:
maintaining a first pair of fields and a first index field for a first data resource, wherein said first pair of fields includes a first field and a second field, wherein said first index field is designed to indicate which of said first field and said second field is a current field storing a current value for said first data resource,
said first field to store a first value for said first data resource at a first time instance, said first index field indicating that said first field is said current field at said first time instance such that said first value stored in said first field represents said current value for said first data resource at said first time instance;
forming a second value for said first data resource at a second time instance;
storing said second value in said second field using a first execution entity, while ensuring exclusive write access to said first execution entity for writing said second value to said second field, wherein said first index field is set by a third time instance to indicate that said second field is said current field such that said second value stored in said second field represents said current value for said first data resource after said third time instance;
permitting read operations unblocked in corresponding set of execution entities to access the value indicated by said first index field as the corresponding current value of said first data resource in a duration between said second time instance and said third time instance;
forming a third value for said first data resource at a fourth time instance;
storing said third value in said first field using a second execution entity, while ensuring exclusive write access to said second execution entity for writing said third value to said first field, wherein said first index field is set by a fifth time instance to indicate that said first field is said current field such that said third value stored in said first field represents said current value for said first data resource after said fifth time instance; and
permitting read operations unblocked in corresponding set of execution entities to access the value indicated by said first index field as the corresponding current value of said first data resource in a duration between said fourth time instance and said fifth time instance.

2. The method of claim 1 , wherein each of said first execution entity and said set of execution entities comprises a corresponding thread of a plurality of threads.

3. The method of claim 2 , wherein said plurality of threads are formed by a plurality of processors executing in parallel.

4. The method of claim 1 , wherein said first execution entity also performs said setting of said first index field to indicate that said second field is said current field, wherein said exclusive write access is ensured to said first execution entity for setting of said first index field also.

5. The method of claim 1 , wherein said first data resource is one of a sequence of data resources maintained as a linked list, said linked list being formed based on a sequence of nodes, said first pair of fields and said first index field being contained in a first node of said sequence of nodes,
said first data resource being a resource value of an object,
said maintaining also maintains a second pair of fields and a second index field in said first node,
said second pair of fields containing a fourth field and a fifth field to store a pointer, said pointer to point to a second node, wherein said second node is a next node following said first node in said sequence of nodes,
said second index field for indicating which of said second pair of fields is currently storing a pointer value to point to said next node,
said second index field indicating that said fourth field contains said pointer value at a fourth time instance.

6. The method of claim 5 , to remove said second node from said linked list, said method further comprising:
identifying a second pointer value in said second node, said second pointer value pointing to an immediate node after said second node in said sequence of nodes of said linked list;
storing said second pointer value in said fifth field of said first node using a third execution entity, while providing exclusive write access to said third execution entity for writing said second pointer value to said fifth field, wherein said second index field is thereafter set to indicate that said fifth field stores said pointer,
wherein said second pointer value is stored in said fifth field and said second index field is set to indicate that said fifth field stores said pointer by a fifth time instance; and
permitting traversal of said first node unblocked for purpose of read operations based on the pointer value in said fourth field or said fifth field as indicated by said second index field, such that said second node is traversed to be said next node to said first node until said fifth time instance, and said immediate node after said second node is traversed to be said next node to said first node after said fifth time instance.

7. The method of claim 5 , to insert a third node between said first node and said second node in said linked list, said method further comprising:
identifying a third pointer value in said pointer of said first node at said fourth time instance, said third pointer value pointing to said second node indicating that said second node is said next node to said first node in said sequence of nodes of said linked list at said fourth time instance;
creating said third node at a memory address, with said third node pointing to said second node;
storing said memory address in said fifth field using a third execution entity, while providing exclusive write access to said third execution entity for writing said memory address to said fifth field, wherein said second index field is thereafter set to indicate that said fifth field stores said pointer by a sixth time instance; and
permitting traversal of said first node unblocked for purpose of read operations based on the pointer value in said fourth field or said fifth field as indicated by said second index field, such that said second node is traversed to be said next node to said first node until said sixth time instance, and said third node is traversed to be said next node to said first node after said sixth time instance.

8. The method of claim 7 , wherein each of said sequence of nodes including said first node contains sixth field to store an IP address, said resource value comprising a MAC (medium access control) address corresponding to said IP address such that translating each IP address to corresponding MAC address is performed based on unblocked read operations.

9. A non-transitory machine readable medium storing one or more sequences of instructions for enabling a system to perform read and write operations on shared data resources, wherein execution of said one or more instructions by one or more processors contained in said system enables said system to perform the actions of:
maintaining a first pair of fields and a first index field for a first data resource, wherein said first pair of fields includes a first field and a second field, wherein said first index field is designed to indicate which of said first field and said second field is a current field storing a current value for said first data resource,
said first field to store a first value for said first data resource at a first time instance, said first index field indicating that said first field is said current field at said first time instance such that s

Assignees

• Oracle Int Corp

Inventors

• Narasimhamurthy Giridhar

Classifications

• G06F9/52 Primary

  Program synchronisation; Mutual exclusion, e.g. by means of semaphores · CPC title