Lock architecture for large scale system

• US 6,477,597 B1
• Filed: 10/04/1999
• Issued: 11/05/2002
• Est. Priority Date: 10/09/1998
• Status: Expired due to Term

• Current Assignee: Bull Sas (Atos SE)
• Original Assignee: Bull Sas (Atos SE)
• Inventors: Walehiane, Nasr-Eddine, Sorace, Jean-Dominique
• Primary Examiner(s): Wong, Peter
• Assistant Examiner(s): VO, TIM T
• Application Number:
  US09/411,231
• Time in Patent Office: 1,128 Days
• Field of Search: 710/200, 710/220, 710/240, 710/241, 710/242, 710/243, 710/244, 710/107, 710/108, 710/109, 710/110, 710/111, 710/112, 710/113, 710/114, 710/115, 710/116, 710/117, 710/119, 710/120, 710/124
• US Class Current: 710/200
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

The lock architecture for a computer system comprises several processors (10, 11, 12, 13) such that each processor (10) requesting a resource of the system takes control of said resource if a first lock state indicates that said resource is free. The requesting processor is placed on active standby if a second lock state indicates that said resource is busy. A lock includes a first and second lock state. The first lock state corresponds to a null value, and the second lock state corresponds to a non-null value. The lock is associated with a data structure that comprises:

a counter that indicates a number of processors (10, 11, 12, 13) that have requested said resource without having used it and then released it;

a first data item specific to said processor (10) switched from a first value to a second value by said processor (10) detecting the second lock state;

at least one second data item specific to another processor (11, 12, 13), switched from a first value to a second value by said other processor (11, 12, 13) detecting the second lock state;

so that the second value of the first data item places said processor (10) on active standby until the first data item is set to the first value by said other processor (11, 21, 13) releasing said resource,

so that said processor (10), having used said resource, sets the second data item to the first value if it detects that the second lock state exists after the release of said resource.

Claims

1. Lock architecture having a first lock state and a second lock state for the allocation of shared resources of a computer systems the first lock state corresponding to a null value, the second lock state corresponding to a non-null value, said computer system comprising several processors (10, 11, 12, 13) arranged such that each processor (10) requesting a resource of the system takes control of said resource if the first lock state indicates that said resource is free and is placed on active standby if a second lock state indicates that said resource is busy, characterized in that a lock is associated with a data structure that comprises:

a counter that indicates a number of processors (10, 11, 12, 13) that have requested said resource without having used it and then released it,

a first data item specific to a first processor (10), switched from a first value to a second value by said first processor (10) detecting the second lock state;

at least one second data item specific to a second processor (11, 12, 13) switched from a first value to a second value by said second processor (11, 12, 13) detecting the second lock state;

so that the second value of the first data item places said first processor (10) on active standby until the first data item is set to the first value by said second processor (11, 12, 13) releasing said resource,

so that said first processor (10) having used said resource, sets the second data item to the first value if said first processor detects that the second lock state exists after the release of said resource.

2. Architecture according to claim 1, characterized in that it comprises:

a first table (4) for containing said first data item in a row wherein a row number corresponds to said resource, and

at least one second table (5, 6, 7) for containing said second data item in a row wherein a row number is identical to that of the first table (4) corresponding to said resource,

a counter table (1) for containing said counter in a row wherein a row number is identical to the row number of the first table (4) and the at least one second table (5, 6, 7) corresponding to said resource.

3. Architecture according to claim 2, characterized in that each resource in question of a set of resources of the computer system corresponds to a lock with which is associated a row number for containing at said other row number:

in the counter table (1), a counter of the number of processors (10, 11, 12, 13) having requested the resource in question, wherein a predetermined value indicates a first lock state;

in each table (4, 5, 6, 7) specific to one of the respective processors (10, 11, 12, 13), a data item that can be set to said second value by the respective processor that does not detect the predetermined value when it requests the resource in question, and can be set to said second value by any processor that decides to do so by releasing the resource in question.

4. A process executed by each processor in question (10) among for the allocation of shared resources in a computer system having several processors (10, 11, 12, 13) for requesting a resource in the computer system, said process being executed by each processor, the computer system comprising an atomic operation (2) for reading and modifying a lock that controls the use of said resource, characterized in that:

the atomic operation (2) consists of incrementing a counter wherein a predetermined value defines a first state of the lock;

the atomic operation (2) is followed by a first test (3) for triggering a first step (8) if the counter does not have a predetermined value at the start of the atomic operation (2) and for triggering a second step (14) for taking control of the resource if the counter has a predetermined value at the start of the atomic operation (2);

the first step (8) setting a data item specific to a first processor (10) in question to a second value such that the first processor (10) in question loops to a reading of its specific data item until the detection of a first value of its specific data item, which triggers the step for taking control of the resource (14);

the second step (14) being followed by a second test (16) after the release of the resource, for triggering a third step (17) if a decrementation of the counter does not result in the predetermined value and for triggering a fourth step (18) in the opposite case;

the third step (17) determining a second processor (11, 12, 13) distinct from the first processor (10) in question, wherein a specific data item is set to the second value, setting the specific data item of the determined second processor (11, 12, 13) to the first value, and triggering the fourth step (18);

the fourth step (18) comprising a second atomic operation for decrementing the counter.

5. Process according to claim 4, characterized in that each lock that controls the use of a distinct resource is associated with a row number in a data structure distributed in an addressable storage in the form of a counter table (1) and processor tables (4, 5, 6, 7), each specific to a processor (10, 11, 12, 13) so that:

for the first atomic operation (2), the first processor (10) connects to a first address that is a function of a start address of the table (1) and of the row number associated with the lock in question;

for the first step (8), the first processor (10) connects to a second address that is a function of a start address of the table (4) that is specific to the address and of the row number associated with the lock in question;

for the second test (16), the first processor (10) connects to the first address;

to determine in the third step (17) whether the data item specific to a second processor (11, 12, 13) is set to its second value, the first processor (10) connects to a third address that is a function of a start address of the table (5, 6, 7) specific to said second processor (11, 12, 13) and of the row number associated with the lock in question.

6. Process according to claim 4, characterized in that in order to determine, in the third step (17), a second processor (11, 12, 13) distinct from the first processor (10), the first processor (10):

calculates an address that is the sum of the row number associated with the lock in question, and the start address of the table (5) specific to the next second processor (11);

if the data item read at the address calculated is set to the second value, the next second processor (11) is the determined processor;

if not, the first processor (10) calculates an address that is the sum of the row number associated with the lock in question and the start address of the table (6) specific to the next further processor (12), and so on with the start address of the table (7) specific to the next still further processor (13) until it reads at the address calculated a data item set to the second value, which determines the distinct processor to which this data item is specific.

7. Process according to claim 4, characterized in that in order to determine, in the third step (17), a second processor (11, 12, 13) distinct from the first processor (10), the first processor (10):

calculates an address that is the sum of the row number associated with the lock in question and the start address of the table (5, 7, 8) specific to each respective distinct second processor (11, 12, 13);

determines the distinct second processor to be the one whose specific data item read at the address calculated is set to the lowest non-null value among the values of the data items specific to the distinct second processors, read at each calculated address.

8. Process according to claim 5, characterized in that in order to determine, in the third step (17), a second processor (11, 12, 13) distinct from the first processor (10), the first processor (10):

calculates an address that is the sum of the row number associated with the lock in question, and the start address of the table (5) specific to the next second processor (11);

if the data item read at the address calculated is set to the second value, the next second processor (11) is the determined processor;

if not, the first processor (10) calculates an address that is the sum of the row number associated with the lock in question and the start address of the table (6) specific to the next further processor (12), and so on with the start address of the table (7) specific to the next still further processor (13) until it reads at the address calculated a data item set to the second value, which determines the distinct processor to which this data item is specific.

9. Process according to claim 5, characterized in that in order to determine, in the third step (17), a second processor (11, 12, 13) distinct from the first processor (10), the first processor (10):

calculates an address that is the sum of the row number associated with the lock in question and the start address of the table (5, 7, 8) specific to each respective distinct second processor (11, 12, 13);

determines the distinct second processor to be the one whose specific data item read at the address calculated is set to the lowest non-null value among the values of the data items specific to the distinct second processors, read at each calculated address.