对于大数据结构的表目锁定

摘要

本发明根据这样一种思想，即对于具有N个表目的大数据结构，通过在一个代表一个表目的值上执行散列函数，使其成为1到M之间的一个被散列值，用于相应于所述表目的锁的存储空间可以被节省。这个被散列的值被用于索引M个锁的表。M值典型地比N值小很多，从而减少存储空间需求。如果M被选择足够大并且一种好的散列函数被选择，则碰撞问题将很小。另外，当第二个表目的被散列值等于第一个表目的被散列值时，与死锁有关的问题出现，通过当第二个表目的被散列值小于第一个表目的被散列值时，通过交换所述第一和第二个表目的所述散列值，所述问题可以得到解决。

主权项

1.一种用于特别在从多个进程可访问的大数据结构中锁定表目的方法，其中递归锁被使用，该方法包括步骤：将第一个表目(e1)散列成为在1和M之间的第一个值(i)，将第二个表目(e2)散列成为在1和M之间的第二个值(j)；如果所述第二个值(j)小于所述第一个值(i)，则交换所述第一个和第二个被散列值(i；j)；通过第一个进程获取相应于被散列的第一个值(i)的第一个锁(lock(i))；通过第二个进程获取相应于被散列的第二个值(j)的第二个锁(lock(j))；其中根据被散列的第一个值(i)来授权所述第一个进程独占访问所述第一个表目(e1)；并且其中根据被散列的第二个值(j)来授权所述第二个进程独占访问所述第二个表目(e2)；其中在已经在所述第一个表目(e1)上执行处理之后，使得所述第一个进程能够释放所述第一个锁(lock(i))，并且其中在已经在所述第二个表目(e2)上执行处理之后，使得所述第二个进程能够释放所述第二个锁(lock(j))。