Entry locking for large data structures
View Patent ↗The invention is based on the idea that for a large data structure with N entries, memory space for the locks corresponding to the entries can be saved by performing a hashing function on a value that represents an entry into a hashed value 1 to M. This hashed value is used to index the table of M locks. The value of M is typically much smaller than the value of N thereby reducing memory space requirements. If M is chosen large enough and a good hashing function is selected, problems with collisions will be very small. Additionally, problems relating to deadlock occurring, when the hashed value of a second entry equals the hashed value of a first entry, are being addressed by swapping the hashed values of the first and second entries, when the hashed value of the second entry is smaller than the hashed value of the first entry.
1. Method for locking entries, in particular in a large data structure, accessible from multiple processes, wherein recursive locks are being used, comprising the steps of:
hashing a first entry to a first value between 1 and M,
hashing a second entry to a second value between 1 and M;
swapping said first and second hashed values if said second value is smaller than said first value;
acquiring a first lock corresponding hashed first value by a first process; and
acquiring a second lock corresponding hashed second value by a second process;
wherein said first process is granted an exclusive access of said first entry on the basis of the hashed first values;
wherein said second process is granted an exclusive accesses of said second entry on the basis of the hashed second values;
wherein said first process is enabled to release said first lock after having executed the processing on said first entry and
wherein said second process is enabled to release said second lock after having executed the processing on said second entry.
2. Method according to claim 1 , wherein:
the value M is proportional to the multiplication of the number of processes which are simultaneously accessing the data structure with the number of entries that said processes need on average to lock in order to carry out their processing.
3. Computer program product comprising computer program code means for causing a computer to perform the steps of the method as claimed in claim 1 .
4. Method for locking entries, in particular in a large data structure, accessible from multiple processes, wherein non-recursive locks are being used, comprising the steps of:
hashing a first entry to a first value between 1 and M,
hashing a second entry to a second value between 1 and M;
swapping said first and second hashed values if said second value is smaller than said first value;
acquiring a first lock corresponding the hashed first value by a first process; and
acquiring a second lock corresponding the hashed second value by a second process, if said first hashed value does not equal said second hashed value;
wherein said first process is granted an exclusive access of said first entry on the basis of the hashed first value;
wherein said second process is granted an exclusive access of said second entry on the basis of the hashed second value;
wherein said first process is enabled to release said first lock after having executed the processing on said first entry, and
wherein said second process is enabled to release said second lock after having executed the processing on said second entry, if said first hashed value does not equal said second value.
5. Device for locking entries, in particular in a large data structure, accessible from multiple processes, wherein recursive locks are being used, comprising:
hashing means for hashing a first entry to a first value between 1 and M, and a second entry to a second value between 1 and M;
comparing means for comparing said first and second hashed values;
swapping means for swapping said first and second hashed values if said comparing means has determined that said second value is smaller than said first value;
first lock acquiring means for enabling a first process to acquire a first lock corresponding to the hashed first value by;
second lock acquiring means for enabling a second process to acquire a second lock corresponding to the hashed second value;
accessing permission means for granting exclusive access of said first process to said first entry on the basis of the hashed first value and for granting exclusive access of said second process to said second entry on the basis of the hashed second value; and
lock releasing means for enabling said first process to release said first lock after having executed the processing on said first entry, and for enabling said second process to release said second lock after having executed the processing on said second entry.
6. Computer system for concurrent processing with a data structure comprising N entries, comprising:
a device for locking entries, in particular in a large data structure, accessible from multiple processes, using recursive locks according to claim 5 .
7. Device for locking entries, in particular in a large data structure, accessible from multiple processes, wherein non-recursive locks are being, used, comprising:
hashing means for hashing a first entry to a first value between 1 and M, and a second entry to a second value between 1 and M;
comparing means for comparing said first and second hashed values;
swapping means for swapping said first and second hashed values if said comparing means has determined that said second value is smaller than said first value;
first lock acquiring means for enabling a first process to acquire a first lock corresponding to the hashed first value by;
second lock acquiring means for enabling a second process to acquire a second lock corresponding to the hashed second value, if said comparing means has determined, that said first hashed value does not equal said second hashed value;
accessing permission means for granting exclusive access of said first process to said first entry on the basis of the hashed first values and for granting exclusive access of said second process to said second entry on the basis of the hashed second values;
lock releasing means for enabling said first process to release said first lock after having executed the processing on said first entry, and for enabling said second process to release said second lock after having executed the processing on said second entry, if said comparing means has determined, that said first hashed value does not equal said second value.