Technical Field

The present invention relates to develop and process multi thread software, in particular, relates to method and system for operating an instance of a data structure.

Background

In the past two decades, the performance and capacity of computer systems dramatically increased with the rapid developing of microelectronics technology. More computing resources mean that more operations could be performed in parallel. Therefore, parallel system structure and parallel software development are playing more and more important role in information processing.

A process is a program or part of a program running in a computing system, or are related sequence steps being executed by a program. Every process comprises one or more threads. A thread is a set of instructions, or a specific section of a program. A thread could be executed independently in a program. Therefore, a thread is basically a light process, which is responsible for executing a task in a single program. Usually, an operating system will be responsible for schedule and execution of threads.

A data structure is a kind of data organization solution, e.g. records or data array, which is helpful for data analyzing or perform operations on data. An instance of a data structure is a kind of implementation object of the data structure. Processing an instance of a data structure often employs multithread process in a process or a program. This could utilize system resources, short program response time and improve user experience. If only single thread is used in a program, then it will greatly hinder the program running speed and response time. Multithread software enables a plurality of threads run in parallel to finish tasks, thus to improve system efficiency. Threads are completed during same time for a plurality of tasks. However, the schedule of threads must be considered for threads to complete tasks during the same time. If the schedule is not suitable, then program will run into error or cause ridiculous result. It is known that multithread software is difficult to develop comparing with sequentially executed software.

Since there might be contradiction among multithread, thus program with parallel system structure often has defects. Especially, if there is no suitable synchronization mechanism, access to shared data structure in parallel will cause unpredicted error. Until now, two methods are used for develop multithread software, namely lock based method and lock free method.

The traditional approach to multi-threaded programming is to synchronize access to shared resources using locks. Synchronization primitives such as mutexes, semaphores, and critical sections are all mechanisms by which a programmer can ensure that certain sections of code do not execute concurrently otherwise it would corrupt shared memory structures. If one thread attempts to acquire a lock that is already held by another thread, the thread will be blocked until the lock is released. For example, in a program, many threads must be executed in specific sequence. If two threads must be executed in a sequence, a thread lock may be employed. The basic idea of the thread lock is: if thread A and thread B will operate two functions a and b respectively, and if A must be executed before B, then B may be scheduled to enter into a wait set until A finishes operate function a; then B is activated from the wait set. This will ensure that B will be executed after A no matter what their sequence is before the execution.

Mutual exclusion locks is a common mechanism for synchronization between processes or threads. Its implementation is simple. In a parallel computing environment for high performance applications, the simple could not be achieved. When lots of locks are employed and lots of threads are executed in parallel, the scalability of Mutual exclusion locks is not good. The access to shared data in parallel requires complex refined lock strategy to schedule operations without contradiction to be executed in parallel. The strategy is quite difficult to design to keep good performance. There might be implied problem, e.g. dead lock or reversed priority. Blocking a thread is undesirable for many reasons. An obvious reason is that while the thread is blocked, it cannot accomplish anything during this time. If the blocked thread is performing a high-priority or real-time task, it is highly undesirable to halt its progress.

Furthermore, certain interference between locks can lead to error conditions such as deadlock, live-lock, and priority inversion. Using locks also involves a trade-off between coarse-grained locking which can significantly reduce opportunities for parallelism, and fine-grained locking which requires more careful design and is more prone to bugs.

Lock free method is an alternative for multithread software develop and processing. Lock free and wait free algorithms are written using atomic primitives that the hardware must provide. These atomic primitives could be found in the instruction set of most popular hardware. The most notable of the atomic primitives is "compare and swap" (often notated "CAS") which takes three arguments: a memory address, an old value, and a new value. If the address contains the old value, it is replaced with the new value, otherwise it is unchanged. Critically, the hardware guarantees that this "comparison and swap" operation is executed atomically. The success of this operation is then reported back to the program with a value 1 or 0. This allows an algorithm to read a datum from memory, modify it, and write it back only if no other thread modified it in the meantime. The above two methods have their advantages and disadvantages as shown in the following table.

Fraser mentioned a hybrid scheme based on MCAS and W-Locks (See Practical lock- freedom, by Keir Fraser, 2004). Run-time performance feedback might then be used to dynamically select which technique to use according to the current level of contention. Runtime profiling and switching between synchronization primitives are used.

Summary

The present invention accordingly provides, in a first aspect, a method for operating an instance of a data structure, comprising: requesting a weak lock of a first lock for at least one lock free capable operation to operate the instance of the data structure; in response to obtaining the weak lock for the at least one lock free capable operation, performing the at least one lock free capable operation to operate the instance of the data structure; requesting a strong lock of the first lock for a lock free incapable operation to operate the instance of the data structure; and in response to obtaining the strong lock for the lock free incapable operation, performing the lock free incapable operation to operate the instance of the data structure.

Preferably, a plurality of operations are allowed to respectively obtain weak locks of the first lock during the same time, only one operation is allowed to obtain the strong lock of the first lock, a weak lock and the strong lock of the first lock is not allowed to be obtained during the same time; wherein, a plurality of operations obtaining weak locks of the first lock are performed in parallel.

The method may further comprise, in response to performing the lock free incapable operation, blocking an operation requesting the strong lock of the first lock; and in response to performing the lock free incapable operation, blocking an operation requesting a weak lock of the first lock or other operation requesting the strong lock of the first lock.

The method may further comprise, in response to the lock free capable operation having operated the instance of the data structure, releasing the weak lock; and in response to the lock free incapable operation having operated the instance of the data structure, releasing the strong lock.

Preferably an operation performed by the lock free capable operation may comprise a writing operation.

The method may further comprise: classifying operations for the instance of the data structure into lock free capable operations and lock free incapable operations.

Preferably, if the number of atomic operations required by a lock free algorithm of one operation is a constant, classifying the one operation as a lock free capable operation; if the number of atomic operations required by a lock free algorithm of one operation is not a constant, classifying the one operation as a lock free incapable operation.

Preferably, if the number of atomic operations required by a lock free algorithm of one operation is a constant, and the constant is not related to element number of the instance of the data structure, classifying the one operation as a lock free capable operation; and if the number of atomic operations required by a lock free algorithm of one operation is not a constant, and the number is related to element number of the instance of the data structure, classifying the one operation as a lock free incapable operation.

Preferably, the lock free capable operation for the instance of the data structure may be divided into operations comprising predefined number of atomic operations.

Preferably, the lock free capable operation for the instance of the data structure may be divided into 1 to 5 atomic operations.

Preferably, if the number of memory cells to be modified by one operation is a constant, classifying the one operation as lock free capable operation; if the number of memory cells to be modified by one operation is not a constant, classifying the one operation as lock free incapable operation.

Preferably, the number of memory cells to be modified by the lock free capable operation is not related to element number of the instance of the data structure; the number of memory cells to be modified by the lock free capable operation is related to element number of the instance of the data structure.

Preferably, the lock free capable operation has access to memory cells less than one word or double word; the lock free incapable operation has access to memory cells greater than double word or two non subsequent words.

Preferably, in a single thread processing, for every operation for same instance of the data structure, if the difference between the performance efficiency in a lock free mode and that in a lock based mode is less than a predefined value, classifying the operation as lock free operation; otherwise, classifying the operation as lock free incapable operation.

Preferably, in a single thread processing, for every operation for same instance of the data structure, if the difference between the performance efficiency in a lock free mode and that in a lock based mode is less than 1.5 times, classifying the operation as lock free operation; otherwise, classifying the operation as lock free incapable operation.

In a second aspect, there is provided a system for operating an instance of a data structure, comprising: weak lock module, for requesting a weak lock of a first lock for at least one lock free capable operation to operate the instance of the data structure; lock free capable operation performing module, for performing the at least one lock free capable operation to operate the instance of the data structure, in response to obtaining the weak lock for the at least one lock free capable operation; strong lock module, for requesting a strong lock of the first lock for a lock free incapable operation to operate the instance of the data structure; and lock free incapable operation performing module, for performing the lock free incapable operation to operate the instance of the data structure, in response to obtaining the strong lock for the lock free incapable operation.

Preferably, the weak lock module and the strong lock module are further configured thus: a plurality of operations are allowed to respectively obtain weak locks of the first lock during the same time, only one operation is allowed to obtain the strong lock of the first lock, a weak lock and the strong lock of the first lock is not allowed to be obtained during the same time; wherein, a plurality of operations obtaining weak locks of the first lock are performed in parallel.

The system may further comprise a block module, the block module is further configured to: in response to perform the lock free incapable operation, block an operation requesting the strong lock of the first lock; and in response to performing the lock free incapable operation, block an operation requesting a weak lock of the first lock or other operation requesting the strong lock of the first lock.

Preferably, the weak lock module is further configured to: in response to the lock free capable operation having operated the instance of the data structure, release the weak lock; and the strong lock module is further configured: in response to the lock free incapable operation having operated the instance of the data structure, release the strong lock. Preferably, operation performed by the lock free capable operation may comprise writing operation.

The system may further comprise an operation classifying module for classifying operations for the instance of the data structure into lock free capable operations and lock free incapable operations.

Preferably, the operation classifying module is further configured to classify operations for the instance of the data structure into lock free capable operations and lock free incapable operations with the method of any one or a combination of the method features of the first aspect.

In view of the shortcoming of prior arts, the present invention provides a new method and system for operating an instance of a data structure.

The method for operating an instance of a data structure comprises: requesting a weak lock of a first lock for at least one lock free capable operation to operate the instance of the data structure; in response to obtaining the weak lock for the at least one lock free capable operation, performing the at least one lock free capable operation to operate the instance of the data structure; requesting a strong lock of the first lock for one lock free incapable operation to operate the instance of the data structure; and in response to obtaining the strong lock for the one lock free incapable operation, performing the one lock free incapable operation to operate the instance of the data structure.

The present invention also provides a system for operating an instance of a data structure.

The system comprises: weak lock module, for requesting a weak lock of a first lock for at least one lock free capable operation to operate the instance of the data structure; lock free capable operation performing module, for performing the at least one lock free capable operation to operate the instance of the data structure, in response to obtaining the weak lock for the at least one lock free capable operation; strong lock module, for requesting a strong lock of the first lock for one lock free incapable operation to operate the instance of the data structure; and lock free incapable operation performing module, for performing the one lock free incapable operation to operate the instance of the data structure, in response to obtaining the strong lock for the one lock free incapable operation.

Comparing with prior arts, the above method and system of the invention may improve the efficiency for operating an instance of a data structure.

Brief Description of the Drawings

A preferred embodiment of the present invention will now be described, by way of example only, with reference to the accompanying drawings, in which:

Figure Ia illustrates the mechanism of a lock based method in the prior art.

Figure Ib illustrates the mechanism of a method without lock in the prior art.

Figure 2a illustrates an exception abort in a lock base method in the prior art. Figure 2b illustrates an exception abort in a method without lock in the prior art.

Figure 3 illustrates a method for operating an instance of a data structure according to one embodiment of the present invention.

Figure 4a and 4b illustrates an operation performance according to one embodiment of the present invention. Figure 5 a and 5b illustrates an operation performance of the prior art with comparison to one embodiment of the present invention.

Detailed Description

A data structure is a kind of data organization solution, e.g. records or data array, which is helpful for data analyzing or perform operations on data. An instance of a data structure is a kind of implementation object of the data structure. For a data structure or an instance of a data structure related with multithread processing, in order to ensure the coherence of the data structure among multithread or to ensure correctness of operations on the instance of the data structure, a common method is to employ a lock for the data structure. The lock theory itself or lock mechanism to protect a data structure with a lock employed by this invention, is similar to that used in prior arts. For example, for an instance of a data structure requires obtaining a lock before processing, an operation could process only after it obtains the lock. One embodiment of the invention is different from prior arts in two aspects, i.e. what kind of operations requires lock and requires what kind of lock. Further more, according to a further embodiment of the invention, after obtaining different locks, an operation may be allowed to perform different operations. This is different from prior arts. The following will be described with reference to figures.

Different prior arts applied different strategy that under what circumstance locks are required. For example, all process or operations are required to be protected with locks for lock based method. Thus, the safety of related data structure is ensured. However, the scalability is not good. For example, please see figure Ia and 2a.

Figure Ia illustrates the mechanism of a lock based method of a prior art. Wherein, there are four threads, al > a2> a3and a4 to be executed. If al obtained a lock and start execution, then other three threads are blocked. After al finished execution, it releases the held lock.

Then, other three threads attempt to obtain the lock. Similarly to al, the thread obtained lock will be executed, and other threads will be blocked. Thus, during the time of entering into and depart from a key portion, a plurality of threads need to wait. Algorithm or mechanism of a thread is similar to sequentially executed threads. The thread obtained lock may block other threads without a lock. However, as shown in figure 2a, the lock based method is not good at robust.

Figure 2a illustrates an exception abort in a lock based method of a prior art. Wherein, an exception abort of a thread with a lock, e.g. Ia, will block other threads. For example, if the thread Ia is dead locked, and the lock hold by it is not released, then other waiting threads will unnecessarily wait for a long time.

A detailed implementation of a lock according to prior arts is as following example 1. For example, a traditional stack has the following arrangement. In prior arts, such stack is not safe for multithreads or threads to be executed in parallel.

Example 1

In order to ensure the correctness for operation to the stack, prior arts employ the following lock based method ( lock:LockType) . For example, employ a lock to the instance of the stack. Thus, the lock is requested before perform operation to the stack. The operation or thread obtained the lock may process the stack, and release the lock after finishing the process. During this time, other threads which need to process the stack will be blocked. These blocked threads may try to obtain the lock until the lock is obtained.

Example 2

Every operation for the stack, e.g. push()> pop() or clone(), may invoke lock.lock() to request the lock, and invoke lock.unlock() to release the lock. Thus, only one thread is allowed to process the stack.

According to one embodiment of the invention, as shown in the following example 3, methods for setting read lock and write lock(similar to the prior arts), may be employed to set a lock comprising a weak lock rLock:WeakLock and a strong lock wLock:StrongLock. Wherein, a plurality of operations/threads are allowed to respectively obtain weak locks during the same time, only one operation/thread is allowed to obtain the strong lock, a weak lock and the strong lock is not allowed to be obtained during the same time. An operation obtaining the weak lock or the strong lock may be performed on the stack. Furthermore, a plurality of operations obtaining weak locks of the first lock is performed in parallel, as shown in figure Ib, 2b and 4a. During the time that an operation obtaining the strong lock processes the stack, other operations for processing the stack will be blocked. These blocked operations may try to obtaining the lock, e.g. periodically try to obtaining the lock.During the time that an operation obtaining the weak lock processes the stack, other operations requesting the strong lock will be blocked, and other operations requesting the weak lock will obtain the weak lock. Similarly, these blocked operations may try to obtaining the strong lock, e.g. periodically try to obtaining the strong lock.

Example 3

Figure Ib illustrates the mechanism of a method for lock free implementation of a prior art. The purpose of the method for lock free is to overcome the shortcoming of not good scalability of lock based method. As shown in figure Ib, in the lock free method, a plurality of thread bl, b2, b3 and b4 may be executed in parallel, to improve the efficiency of the threads or the program. Lock free method is not only has good scalability, bust is also robust, as shown in figure 2b.

Figure 2b illustrates an exception abort in a method of lock free implementation of a prior art. As shown in figure 2b, if a thread bl aborted, other threads bl, b3 and b4 will still be executed. However, it is difficult to develop lock free methods. The thread algorithms (or mechanism) of a lock free method are often completely different with sequential ones. It often needs to prove the correctness among threads complex logic. Furthermore, the executions of some operations are quite inefficient.

According to one embodiment of the invention, the parallel execution mechanism of lock free method and the sequential execution mechanism of lock based method are integrated for multithread processing. A person skilled in the art could understand, protection scope or function domain of a lock may be set in a hardware, an operating system or an application. In prior arts, via setting a protection scope or function domain of a weak lock (wLock:WriteLock) and a strong lock (wLock:WriteLock), a plurality of operations with weak locks may perform their operations in parallel, and an operation with the strong lock will exclusively perform its operation.

A person skilled in the art could understand, methods similar to the prior arts, protection scope or function domain of a weak lock and a strong lock may be set in hardware, an operating system or an application. Such that a plurality of operations with weak locks may perform their operations in parallel, and an operation with the strong lock will exclusively perform its operation. As shown in the above figure 3, via setting a protection scope or function domain of a weak lock (wLock:WriteLock) and a strong lock (wLock:WriteLock), a plurality of operations with weak locks may perform their operations in parallel, and an operation with the strong lock will exclusively perform its operation. Under such circumstance, the scalability, robustness or characteristic for development of the multithread or process, may be ensured by further mechanism.

Figure 3 illustrates a method for operating an instance of a data structure according to one embodiment of the present invention. At step SlOO, the method starts. At step SI lO, classifying operations for the instance of the data structure into lock free capable operations and lock free incapable operations. As described in the following paragraphs, a plurality of methods may be used for classifying operations for the instance of the data structure into lock free capable operations and lock free incapable operations. A person skilled in the art may understand that this step may be carried out by a software developing tool or runtime environment of a program, and may be independent of steps S 120 S 160.

Furthermore, the function of a lock may be configured in a program or a runtime environment (e.g. in hardware, operating system or applications as described above). A plurality of operations are allowed to respectively obtain weak locks of the first lock during the same time, only one operation is allowed to obtain the strong lock of the first lock, a weak lock and the strong lock of the first lock is not allowed to be obtained during the same time; wherein, a plurality of operations obtaining weak locks of the first lock are performed in parallel. Operation performed by the lock free capable operation may comprise writing operation. In other words, according to one embodiment of the present invention, some lock free capable operation may only comprise read operations, and some lock free capable operation may comprise write operations. Additionally, the phrase "a first lock" in the above description is substantially referring to a lock. Using "first" is just for the need of reference. For example, "the first lock" in a context refers to "a first lock" mentioned before, to avoid using "the lock" confusing the circumstance of referring "a lock" mentioned before, or "a weak lock" mentioned before.

At step S 120, requesting a weak lock of a first lock for at least one lock free capable operation to operate the instance of the data structure. If other operations have already obtained weak locks of the first lock, the at least one lock free capable operation is allowed to obtain other weak lock of the first lock. If other operations have already obtained the strong lock of the first lock, the at least one lock free capable operation will be blocked until the strong lock is released. A person skilled in the art may understand, the usage of lock according to the embodiment of the invention, may be combined with other mechanism of lock distribution, e.g. combined with the lock distribution mechanism according to priorities, etc..

At step S 130, in response to obtaining the weak lock for the at least one lock free capable operation, performing the at least one lock free capable operation to operate the instance of the data structure. According to one embodiment of the invention, some lock free capable operation may only perform read operation, and some lock free capable operation may perform write operation. According to a further embodiment of the invention, the method may further comprise: in response to the lock free capable operation having operated the instance of the data structure, releasing the weak lock.

At step S 140, requesting a strong lock of the first lock for one lock free incapable operation to operate the instance of the data structure. If other operations have already obtained weak locks or the strong lock of the first lock, the one lock free incapable operation will be blocked until the weak locks or the strong lock is released.

At step S 150, in response to obtaining the strong lock for the one lock free incapable operation, performing the one lock free incapable operation to operate the instance of the data structure. According to a further embodiment of the invention, the method may further comprise: in response to the lock free incapable operation having operated the instance of the data structure, releasing the strong lock. At step S 160, the method ends.

A person skilled in the art could understand, steps S 120 to S 160 themselves already form a complete technical solution, and will be directly implemented in the runtime environment or tools software with the above strong lock and weak locks.

An instance of a data structure refers to an embodiment object of a data structure. Linked list is a commonly used data structure. Other commonly used data structures comprises sequential list, tree, graph and leap table, etc. A "linked list" is a kind of linked list structure. Each node in the linked list has a pointer to a next node. Operations of data structure "linked list" usually comprise adding an element, delete an element, searching an element, traversing elements and sorting elements. In one embodiment of the invention, a linked list instance list is illustrated; the list comprises a plurality of elements.

According to one embodiment of the invention, a strong lock and weak locks may be used to protect List class. Via setting a protection scope or function domain of weak locks and the strong lock, a plurality of operations with weak locks may perform their operations in parallel, and an operation with the strong lock will exclusively perform its operation. For lock free capable operations add() and remove(),weak locks may used to perform their operations in parallel. A strong lock may be used for a lock free incapable operation to exclusively access the List, and block other operations accessing the List.

Next the lock free capable operations and lock free incapable operations are described with examples. In the following embodiment, operation add is a lock free capable operation, operation remove is a lock free capable operation, and operation sort is a lock free incapable operation. After operation add obtained a weak lock of the List, operation remove may also obtain a weak lock for the List. Therefore, operation add and operation remove may be performed in parallel. Operation sort will not be allowed to be performed with operation add or operation remove in parallel. class List{ private Lock weaklock, stronglock ; public List() {

WeakStrongLock wslock = new WeakStrongLock(); weaklock = wslock.weaklock(); stronglock = wslock.stronglock(); }

In the above program, first define a List class, then define a lock for the List class with private Lock weaklock, stronglock. During the initiation of the program, a lock

WeakStrongLock wslock = new WeakStrongLock() will be generated, which comprises a weak lock, weaklock = wslock.weaklock(), and a strong lock, stronglock = wslock.stronglock() _o public void add(Object obj){ try{ weaklock. lock(); // do the lock free add } finally! weaklock.unlock(); }

} In the above program, the operation add for addition object obj to the List, may comprise one or more atomic operations. Therefore, the operation add is a lock free capable operation. When it is to be performed, first request a weak lock with weaklock.lock(). In response to obtaining a weak lock, perform the lock free capable operation add to add object obj to the

List; in response to finishing operation, weaklock.unlock() will release the weak lock.

If the strong lock of the lock is being obtained by other operation or thread, the operation add will be blocked. Then, only after the strong lock being released, the operation add may obtain the requested weak lock. public void remove(Object obj){ try{ weaklock.lock(); // do the lock free remove } finally! weaklock.unlock(); }

}

In the above program, operation remove for deleting the object obj form the List, comprises one or more atomic operations. Therefore, the operation remove is a lock free capable operation. When it is to be performed, first request a weak lock with weaklock.lock(). In response to obtaining a weak lock, perform the lock free capable operation remove to add object obj to the List; and in response to finishing operation, weaklock.unlock() will release the weak lock. If the strong lock of the lock is being obtained by other operation or thread, the operation remove will be blocked. Then, only after the strong lock being released, the operation remove may obtain the requested weak lock. However, if a weak lock of the lock is being obtained by other operation or thread, the operation remove may obtain another weak lock of the lock, public void sort() { try{ stronglock.lock();

// do sorting } finally! stronglock.unlock();

} }

}

In the above program, the operation sort for sorting the objects obj in the class List, could not be divided into predefined one or more atomic operations. The number of the required atomic operation will vary according to the elements number in the List. Therefore, the operation sort is a lock free incapable operation. When it is to be performed, first request a strong lock with stronglock.lock(). In response to obtaining the strong lock, perform the lock free incapable operation sort; and in response to finishing operation, stronglock.unlockQ will release the weak lock. If the strong lock or a weak lock of the lock is being obtained by other operation or thread, the operation sort will be blocked. Then, only after the strong lock or weak lock being released, the operation sort may obtain the requested strong lock.

In the above method of figure 3, step Sl 10 for classifying operations for the instance of the data structure into lock free capable operations and lock free incapable operations, may be carried out with a plurality of methods.

According to one embodiment of the invention, if the number of atomic operations required by a lock free algorithm of one operation is a constant, then the one operation is classified as a lock free capable operation; if the number of atomic operations required by a lock free algorithm of one operation is not a constant, then the one operation is classified as a lock free incapable operation. In a further embodiment of the invention, if the number of atomic operations required by a lock free algorithm of one operation is a constant, and the constant is not related to element number of the instance of the data structure, then the one operation is classified as a lock free capable operation; and if the number of atomic operations required by a lock free algorithm of one operation is not a constant, and the number is related to element number of the instance of the data structure, then the one operation is classified as a lock free incapable operation.

The lock free capable operation for the instance of the data structure may be divided into operations comprising predefined number of atomic operations. Preferably, the lock free capable operation for the instance of the data structure may be divided into 1 to 5 atomic operations. Wherein, the lock free incapable operation for the instance of the data structure may not be divided into operations comprising predefined number of atomic operations.

For example, in the example of above processing List, adding an element only needs one atomic operation, and deleting an element only needs one or two atomic operation. Therefore, these two kinds of operations may be classified as lock free capable operation. While, operation sort for the List relates with elements number of the data structure, thus belong to lock free incapable operation. Push or pop in stack may be classified as lock free capable operation; while adding a frame for a figure will be classified as lock free incapable operation.

In the prior arts of this invention, lock based method used lock for protection. Such data structure is safe, but with low extensibility. If some operations for the data structure is lock free capable and safe for multithread, e.g. add() and remove() for the List. While, other operations are not safe for multithread, e.g. sort() for the List. The usage of the data structure is limited. When using method not safe for threads, programmer must be very careful, wait for a safe time, and invoke the method being not safe for threads in this safe time. Such mode requires more attention from programmer, thus developing efficiency and performing efficiency will be affected.

According to a further embodiment of the invention, if the number of memory cells to be modified by one operation is a constant, then classify the one operation as lock free capable operation; if the number of memory cells to be modified by one operation is not a constant, then classify the one operation as lock free incapable operation. According to a further embodiment of the invention, the number of memory cells to be modified by the lock free capable operation is not related to element number of the instance of the data structure; the number of memory cells to be modified by the lock free capable operation is related to element number of the instance of the data structure. Preferably, the lock free capable operation has access to memory cells less than one word or double word; the lock free incapable operation has access to memory cells greater than double word or two non subsequent words.

For the above example for processing List, adding an element only needs amend one pointer in the original List; and deleting an element only needs amend one or two pointer in the original List. Therefore, these two kinds of operations may be classified as lock free capable operation. While for sorting elements in the List, the number of pointers to be amended has direct ratio with the number of elements in the List, thus belong to lock free incapable operation.

According to a further embodiment of the invention, wherein in a single thread processing, for every one operation for same instance of the data structure, if difference of performance efficiency in a lock free mode and in a lock based mode is less than a predefined value, then classify the every one operation as lock free operation; otherwise, classify the every one operation as lock free incapable operation. Preferably, wherein in a single thread processing, for every one operation for same instance of the data structure, if difference of performance efficiency in a lock free mode and in a lock based mode is less than 1.5 times, then classify the every one operation as lock free operation; otherwise, classify the every one operation as lock free incapable operation.

Every operation for a data structure may be implemented with two versions, one is lock free implementation, and the other is lock based implementation. In the above example for processing List, the efficiency of the operation of adding an element and the operation of deleting an element is similar to lock based implementation. Thus, the two operations could be classified as lock free capable operation. While, lock free implementation of the operation for sorting the List is quite inefficient, thus this operation will be classified as lock free incapable operation. Additionally, for adding a frame for a figure, the efficiency of lock free implementation is quite low.

According to a further embodiment of the invention, in the method shown in figure 3, a plurality of operations/threads may be allowed to possess weak locks of a first lock respectively, only one operation is allowed to obtain the strong lock of the first lock, a weak lock and the strong lock of the first lock is not allowed to be obtained during the same time; wherein, a plurality of operations obtaining weak locks of the first lock are performed in parallel. Wherein, the method of figure 3 may further comprises: in response to the lock free capable operation having operated the instance of the data structure, releasing the weak lock; and in response to the lock free incapable operation having operated the instance of the data structure, releasing the strong lock.

Figure 4a and figure 4b illustrates an operation performance according to one embodiment of the present invention. In figure 4a, two or more lock free capable operation may be performed in parallel. Under such circumstance one or more lock free incapable operations are blocked. For example, the operation add() and remove(),etc. shown in figure 4a are performed in parallel, while lock free incapable operation size(), etc. are blocked. In figure 4b, one or more lock free incapable operations are performed in parallel, while other lock free incapable operations and lock free capable operations are blocked. The operations size(), etc. in figure 4b are performed sequentially, while other lock free incapable operations and lock free capable operations add() and remove(), etc. are blocked.

In prior arts, there are many benefits in lock free methods. However, the methods are difficult to develop. Therefore, lock free mechanism usually used for simple operations. For example, the following operations to operate an instance of a data structure — linked list List class. class List{ public void add(Object obj); public void remove(Object obj); public void sort();

} It is not difficult to implement lock free mechanism for add() and remove() method. The add() is for adding an element, public void add(Object obj) represents adding an object element for List class, and the add for this List could be invoked by an operation of other threads. The remove()is for deleting an element, public void remove(Object obj) represents deleting an object element from List class, and the remove for this List could be invoked by an operation of other threads. The sort()is for sorting elements, public void sort()represents sorting object elements of the List, and the sort for this List could be invoked by an operation of other threads. However, It is difficult to implement lock free mechanism for sort() method. The reason is that the instance List of the data structure usually comprises a plurality of elements. Thus, during sorting List elements, if other thread adds to or removes an object element from the List, there will be contradiction.

Then, a natural method is to protect sort() with a lock. Thus, the codes are rewritten as following, class List{ public void add(Object obj); public void remove(Object obj); public synchronized void sortQ; }

The public synchronized void sort() represents lock unlock pair is required for performing sort. Under such circumstance, sort() is amended with synchronized method. When it is to perform the operation, first try to obtain a lock; perform sort operation after obtaining the lock; release the lock after performing the sort operation. Such that, only one thread is allowed to enter into the method to invoke the sort at any time. However, the above method is not correct. If at the time that one thread enters the sort method, another thread is trying to delete a node with the remove method, the sort method might fail.

This is because the execution of add() method might come across with sort() method sometime. Furthermore, although sort() method is locked; add is lock free. This allow add could be performed at any time. There might be contradiction. Therefore, a safe version will use the following method, wherein all operations are performed with synchronized (or locked) method, class List{ public synchronized void add(Object obj); public synchronized void remove(Object obj); public synchronized void sort(); }

The above public synchronized void add(Object obj) represents that lock unlock pair is required for performing add. The public synchronized void remove(Object obj) represents that lock unlock pair is required for performing remove. Now, the List is safe. However, three methods are all protected with lock. Then, as shown in figure 1 and figure 2, only one thread is allowed to enter into one of the above three method. In figure 1 , a simple operation obtains a mutual exclusion lock, and blocks other operations from obtaining the mutual exclusion lock. In figure 2, a complex operation obtains a mutual exclusion lock, and blocks other operations from obtaining the mutual exclusion lock. Such mode hindered performing software execution in parallel.

Figure 5 a and 5b illustrates an operation performance of a prior art with comparison to one embodiment of the present invention. The prior art applies locked based operation. In figure 5 a, since add() needs to perform a write operation, rather than just a read operation, other operations are blocked during the time when add() is being performed with a lock. In figure 5b, since size() needs to perform a write operation, rather than just a read operation, other operations are blocked during the time when size() is being performed with a lock.

Corresponding to the above method for operating an instance of a data structure, this invention also provides a system for operating an instance of a data structure. The system comprises: weak lock module, for requesting a weak lock of a first lock for at least one lock free capable operation to operate the instance of the data structure; lock free capable operation performing module, for performing the at least one lock free capable operation to operate the instance of the data structure, in response to obtaining the weak lock for the at least one lock free capable operation; strong lock module, for requesting a strong lock of the first lock for one lock free incapable operation to operate the instance of the data structure; and lock free incapable operation performing module, for performing the one lock free incapable operation to operate the instance of the data structure, in response to obtaining the strong lock for the one lock free incapable operation.

Wherein, weak lock module and strong lock module are further configured: a plurality of operations are allowed to respectively obtain weak locks of the first lock during the same time, only one operation is allowed to obtain the strong lock of the first lock, a weak lock and the strong lock of the first lock is not allowed to be obtained during the same time; wherein, a plurality of operations obtaining weak locks of the first lock are performed in parallel.

The above system may further comprises a block module, the block module is further configured to: in response to perform the lock free incapable operation, block an operation requesting the strong lock of the first lock; and in response to performing the lock free incapable operation, block an operation requesting a weak lock of the first lock or other operation requesting the strong lock of the first lock.

Furthermore, the weak lock module is further configured to: in response to the lock free capable operation having operated the instance of the data structure, release the weak lock; and the strong lock module is further configured to: in response to the lock free incapable operation having operated the instance of the data structure, release the strong lock.

Furthermore, operation performed by the lock free capable operation may comprise writing operation.

The above system may further comprises an operation classifying module for classifying operations for the instance of the data structure into lock free capable operations and lock free incapable operations. The operation classifying module is further configured to classify operations for the instance of the data structure into lock free capable operations and lock free incapable operations with the method of anyone or combination of the above methods.

Comparing with prior arts, this invention integrates lock based method and lock free method. As described above, lock free codes could be performed in parallel with good extensibility, but are difficult for programming. To the contrary, lock based method is not good at extensibility, but is easy to be understand and programmed. When a plurality lock free operations are performed in parallel in threads, lock free capable operations could ensure atomic characteristic and variables consistency. When a lock free incapable operation and other lock free incapable operation or other lock free capable operation need to be performed, using a strong lock to ensure atomic characteristic and variables consistency.

According to an embodiment of the present invention, when there are only simple methods without a complex operation, lock free capable operation could be performed in parallel. Operations could be performed to operate an instance of a data structure. When a complex method is to be performed, a strong lock could be employed to operate an instance of a data structure. A lock free incapable operation will not be blocked when it is not necessary.

The present invention also provides a storage media or signal carrier, which comprises instructions for carrying out the method according to the invention.