Browse Prior Art Database

Methodology of an Efficient Locking Mechanism for a Hash Algorithm in a Multi-Processor Environment

IP.com Disclosure Number: IPCOM000202061D
Publication Date: 2010-Dec-03
Document File: 1 page(s) / 84K

Publishing Venue

The IP.com Prior Art Database

Related People

Juergen Carstens: CONTACT

Abstract

A hash algorithm is mostly used to store global objects within a process. If multiple threads are accessing the hash table, the hash table itself has to be thread-safe. Typically, a hash table contains a lock or a critical section. If multiple threads are accessing the hash table only one thread can access it while the remaining threads have to wait. Due to this the hash table is using only one processor at a time. Since multiple processor machines are common now, a hash algorithm is needed which uses at least two processors at a time. The hash class in the .NET Framework provides a reader and a writer lock.
A novel solution is proposed to use multiple locks. A hash table consists of an array where the elements point to linked lists. If the hash table has to store many elements the size of the array is large. Each array element can have a lock. The use of one lock per element would lead to a large number of locks. Since the operating system limits the number of locks and a lock itself needs a certain amount of memory, the number of locks should correlate with the number of processors. It is proposed to use the following formula (1) to calculate the number of locks

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 01 of 1

(This page contains 01 pictures or other non-text object)

(This page contains 00 pictures or other non-text object)

Methodology of an Efficient Locking Mechanism for a Hash Algorithm in a nment

Multi-Processor Enviro

Idea: Frank Wigger, IN-Bangalore

A hash algorithm is mostly used to store global objects within a process. If multiple accessing the hash table, the hash table itself has to be thread-safe. Typically, a ha lock or a critical section. If multiple threads are accessing the hash table only one t wh
time. Since multiple processor machines are common now, a hash algorithm
least two processors at a time. The hash class in the .NET Framework provides lock.

A novel solution is proposed to use multiple locks. A hash table consists of an arra elements point to linked lists. If the hash table has to store m
e. Each array element can have a lock. T
number of locks. Since the operating system limits the number of locks and a lo certain amount of memory, the number of locks should correlate with the number of proposed to use the following formula (1) to calculate the number of locks

Num

   re 1 shows an example of a hash table with 1
ed on formula (1) the number of locks is five. ate
locks. Once a thread wants to access an element, the hash value of this element is algorithm gets the corresponding lock by calculating the index using formula (2) and the array

Array index = (HashValue) modulo (HashTableS

                                                   threads are
sh table contains a hread can access it ile the remaining threads have to wait. Due to this the hash table is using only one processor at a

is needed which uses at

a reader and a writer

                                                    y where the any elements the size of the array is larg he use of one lock per element would lead to a large ck itself needs a

processors. It is

ber of locks = Number of processors ยท 2 + 1 (1)

Figu 6 hash values within a two processor machine.

Bas So the hash algorithm cre s a second array for the

calculated. The

index

using formula (3)

Lock index = (HashValue) modulo (NumberOfLocks) (2)

ize) (3)

The proposed solution provides the advantage that multiple threads can access the hash table at the same time. Furthermore the use of multiple processors can speed up the access to the hash table.

Figure 1: Exemplary hash table with 16 hash values and 5 locks

(This page contains 02 pictures or other non-text object)

(This page contains 08 pictures or other non-te...