Method and apparatus for managing access contention to a linear list without the use of locks

A data processing system, comprising:

• a multiprocessor (MP) central processing unit (CPU);
• shared random access memory (RAM);
• read only memory (ROM);
• an I/O adapter;
• and
• a bus system coupling said CPU to said ROM, said RAM and said I/O adapter, wherein said CPU further comprises:
• a system for managing a list of data elements, said list residing in a block of said shared memory in RAM of said MP, comprising:
• a first circuit operable for selectively adding a data element to said list, said first circuit including an atomic circuit operable for manipulating addresses pointers of said list;
• and
• a second circuit operable for selectively removing a data element from said list, said second circuit including said atomic circuit operable for manipulating addresses pointers of said list,
• wherein said atomic operation comprises a compare and swap operation on parameters of said list and said compare and swap operation sets a flag bit said flag bit indicating decision paths taken within said compare and swap when executed,
• wherein said parameters comprise a plurality of pointer values of said list said plurality of pointer values comprising, data element pointers;
• a first_ptr, last_ptr, a next_ptr, a block_ptr, a cur_first pointer, and a cur_last pointer, and
• wherein contention for access to said list is managed without locks if a least two processors of a multiplicity of processors of said MP system concurrently add a first data element to and remove a second data element from said list of data elements.

A computer program product embodied in a machine readable medium, including programming for a symmetrical multiprocessor system with shared memory, comprising a program of instructions for performing the method steps of:

• modifying said list, said step of modifying said list further comprising the steps:
• selectively invoking a first function for adding a data element to said list, said first function including an atomic operation for manipulating pointers of said list;
• and
• selectively invoking a second function for removing a data element from said list, said second function including said atomic operation for manipulating pointers of said list,
• wherein said atomic operation comprises a compare and swap operation on parameters of said list and said compare and swap operation sets a flag bit said flag bit indicating decision paths taken within said compare and swap when executed,
• wherein said parameters comprise a plurality of pointer values of said list said plurality of pointer values comprising, data element pointers;
• a first_ptr, last_ptr, a next_ptr, a block_ptr, a cur_first pointer, and a cur_last pointer, and
• whereby contention for access to said list is managed without locks if each of a multiplicity of processors of said MP system invoke concurrently a corresponding one of said first function or said second function.

A system of managing a list of data elements, said list residing in a block of shared memory in a multiprocessor (MP) system comprising:

• a first circuit operable for selectively adding a data element to said list, said first circuit including an atomic circuit operable for manipulating addresses pointers of said list;
• and
• a second circuit operable for selectively removing a data element from said list, said second circuit including said atomic circuit operable for manipulating addresses pointers of said list,
• wherein said atomic operation comprises a compare and swap operation on parameters of said list and said compare and swap operation sets a flag bit said flag bit indicating decision paths taken within said compare and swap when executed,
• wherein said parameters comprise a plurality of pointer values of said list said plurality of pointer values comprising, data element pointers;
• a first_ptr, last_ptr, a next_ptr, a block_ptr, a cur_first pointer, and a cur_last pointer, and
• wherein contention for access to said list is managed without locks if a least two processors of a multiplicity of processors of said MP system concurrently add a first data element to and remove a second data element from said list of data elements.