Request of an MCS lock by guests

Patent metadata

Field	Value
Publication number	US-10846148-B2
Application number	US-201515756932-A
Country	US
Kind code	B2
Filing date	Sep 10, 2015
Priority date	Sep 10, 2015
Publication date	Nov 24, 2020
Grant date	Nov 24, 2020

Abstract

In example implementations, a method include receiving a request for a lock in a Mellor-Crummey Scott (MCS) lock protocol from a guest user that is context free (e.g., a process that does not bring a queue node). The lock determines that it contains a null value. The lock is granted to the guest user. A pi value is received from the guest user to store in the lock. The pi value notifies subsequent users that the guest user has the lock.

First claim

The invention claimed is:

1. A method, comprising:
receiving a request for a lock in a Mellor-Crummey Scott (MCS) lock protocol from a first leader regular user of a first group;
determining that the lock contains a sentinel value indicating that a guest user has acquired the lock;
receiving a pointer to a most recent regular user in the first group;
receiving the sentinel value back from the first leader regular user, wherein the first leader regular user spins on the lock until the sentinel value is changed to a null value;
assigning a first positive integer to the first leader regular user that is multiplied by a positive multiplier that defines a countdown timer for the first leader regular user to resend the request for the lock;
receiving a subsequent request for the lock from a subsequent leader regular user of a subsequent group;
determining that the lock contains the sentinel value;
receiving a pointer to a most recent regular user in the subsequent group;
receiving the sentinel value back from the subsequent leader regular user, wherein the subsequent leader regular user spins on the lock until the sentinel value is changed to the null value; and
assigning a subsequent positive integer to the subsequent leader regular user that is multiplied by the positive multiplier that defines a countdown timer for the subsequent leader regular user to resend the subsequent request for the lock, wherein the subsequent positive integer is an incremental value higher than the first integer.

2. The method of claim 1 , wherein the first group and the subsequent group comprise a plurality of regular users in parallel queues.

3. The method of claim 1 , wherein the first integer is set to zero when the guest user releases the lock.

4. The method of claim 1 , wherein the multiplier is a duration of a number of computer processing unit (CPU) cycles.

5. The method of claim 1 , wherein the determining, the receiving the pointer of the subsequent leader regular user, the receiving the sentinel value back from the subsequent leader regular user, and the assigning the subsequent integer are repeated for each additional subsequent request for the lock that is received from additional subsequent leader regular users.

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Kimura Hideaki
• Wang Tianzheng
• Chabbi Milind M

Classifications

• G06F9/526 Primary

  Mutual exclusion algorithms · CPC title

• G06F2209/521

  Atomic · CPC title