Optimization of data locks for improved write lock performance and CPU cache usage in multi core architectures

Patent metadata

Field	Value
Publication number	US-9569265-B2
Application number	US-201414507930-A
Country	US
Kind code	B2
Filing date	Oct 7, 2014
Priority date	Oct 7, 2014
Publication date	Feb 14, 2017
Grant date	Feb 14, 2017

Abstract

Data access optimization features the innovative use of a writer-present flag when acquiring read-locks and write-locks. Setting a writer-present flag indicates that a writer desires to modify a particular data. This serves as an indicator to readers and writers waiting to acquire read-locks or write-locks not to acquire a lock, but rather to continue waiting (i.e., spinning) until the write-present flag is cleared. As opposed to conventional techniques in which readers and writers are not locked out until the writer acquires the write-lock, the writer-present flag locks out other readers and writers once a writer begins waiting for a write-lock (that is, sets a writer-present flag). This feature allows a write-lock method to acquire a write-lock without having to contend with waiting readers and writers trying to obtain read-locks and write-locks, such as when using conventional spinlock implementations.

First claim

What is claimed is:

1. A method for data access by a CPU, the method comprising the steps of:
(a) a reader performing a first writer-present flag status check, and if said first writer-present, flag status check determines that said writer-present flag is:
(i) set, repeating said step of checking; or
(ii) cleared, initially acquiring said read-lock,

(b) subsequent to said initially acquiring said read-lock, said reader performing, a second writer-present flag status check, and
(c) if said second writer-present flag status check determines that said writer present flag is:
(i) set, releasing said read-lock and repeating said first writer-present flag status check; or
(ii) cleared, maintaining said read-lock.

2. (ii) The method of claim 1 wherein said repeating said step of checking includes implementing a spinlock.

3. The method of claim 1 wherein said read-lock is:
(a) associated with a CPU group that includes a plurality of CPUs; and
(b) for data accessed via said CPU group.

4. The method of claim 1 further comprising the step of:
(c) releasing said read-lock.

5. The method of claim 4 wherein releasing said read-lock includes clearing said read-lock flag.

6. A method for data access by a CPU, the method comprising the steps of:
(a) checking, by a writer, if a write-present flag is set or cleared; and
(b) when said writer-present flag is cleared then acquiring by said writer a write-lock;
wherein said step of checking includes performing a first writer-present flag status check, and if said first writer-present flag status check determines that said writer-present flag is:
(i) set, repeating said step of checking; or
(ii) cleared, setting said writer-present flag, and

(c) subsequent to setting said writer-present flag, performing a second writer-present flag status check, and
(d) if said second writer-present flag status check determines that said setting said writer-present flag is:
(i) unsuccessful, repeating said first write-present flag status check; or
(ii) successful, performing a read-lock check, if said read-lock check determines that said read-lock is:
(A) set, repeating said performing a read-lock check; or
(B) cleared, acquiring said write-lock.

7. The method of claim 6 wherein said repeating said step of checking includes implementing a spinlock.

8. The method of claim 6 wherein said repeating said step of performing a second writer-present flag status check includes implementing a spinlock.

9. The method of claim 6 wherein said write-lock is
(a) associated with a CPU group that includes a plurality of CPUs; and
(b) for data accessed via said CPU group.

10. The method of claim 6 further comprising the step of:
(c) releasing said write-lock.

11. The method of claim 10 wherein releasing said write-lock includes clearing said writer-present flag.

12. A system comprising:
(a) a processing system containing one or more processors, said processing system being configured to:
(i) checking by a reader, via a first writer-present flag status check, and if said first writer-present flag status check determines that said writer-present flag is:
(A) set, repeating said checking; or
(B) cleared, initially acquiring said read-lock,

(ii) subsequent to said initially acquiring said read-lock, said reader performing a second writer-present flag status check, and
(iii) if said second writer-present flag status check determines that said writer-present flag is:
(A) set, releasing said read-lock and repeating said first writer present flag status check: or
(B) cleared, maintaining said read-lock.

13. A system comprising:
(a) a processing system containing one or more processors, said processing system being configured to:
(i) check, by a writer, if a writer-present flag is set or cleared; and
(ii) when said writer-present flag is cleared then acquire by said writer a write-lock;

wherein said processing system is further configured to perform said checking via a first writer-present flag status check, and if said first-writer present flag status check determines that said writer-present flag is:
(A) set, repeating said step of checking; or
(B) cleared, setting said writer-present flag, and

(iii) subsequent to setting said writer-present flag, performing a second writer-present flag status check, and
(iv) if said second writer-present flag status check determine that said setting said writer-present flag is:
(A) unsuccessful, repeating said first writer-present flag status check or
(B) successful, performing a read-lock check and if said read-lock check determines that said read-lock is:
(I) set, repeating said performing a read-lock check; or
(II) cleared, acquiring said write-lock.

14. A computer-readable storage medium having embedded thereon computer-readable code for data access by a CPU, the computer-readable code comprising program code for:
(a) a reader performing a first writer-present flag status check, and if said first writer-present flag status cheek determines that said writer-present flag is:
(i) set, repeating said step of checking; or

(ii) cleared, initially acquiring said read-lock. (b) subsequent to said initially acquiring said read-lock, said reader performing a second writer-present flag status check, and
(c) if said second writer-present flag status check determines that said writer present flag is:
(i) set, releasing said read-lock and repeating said first writer-present flag status check; or
(ii) cleared, maintaining said read-lock.

15. A computer-readable storage medium having embedded thereon computer-readable code for data access by a CPU, the computer-readable code comprising program code for:
(a) checking, by a writer, if a write-present flag is set or cleared; and
(b) when said writer-present flag is cleared then acquiring by said writer a write-lock;
wherein said program code further performs said checking via a first writer-present flag status check, and if said first writer-present flag status check determines that said writer-present flag is:
(i) set, repeating said step of checking; or
(ii) cleared, setting said writer-present flag, and

(c) subsequent to setting said writer-present flag, performing a second writer-present flag status check, and
(d) if said second writer-present flag status check determines that said setting said writer-present flag is:
(i) unsuccessful, repeating said first write-present flag status check; or
(ii) successful, performing a read-lock check, if said read-lock check determines that said read-lock is:
(A) set, repeating said performing a read-lock check; or
(B) cleared, acquiring said write-lock.

Assignees

• Check Point Software Tech Ltd

Inventors

• Chandel Ajay

Classifications

• G06F9/526 Primary

  Mutual exclusion algorithms · CPC title

• G06F2212/1032

  Reliability improvement, data loss prevention, degraded operation etc · CPC title

• G06F9/50 Primary

  Allocation of resources, e.g. of the central processing unit [CPU] · CPC title

• G06F2212/1008

  Correctness of operation, e.g. memory ordering · CPC title

• G06F2212/62

  Details of cache specific to multiprocessor cache arrangements · CPC title