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

• US 9,569,265 B2
• Filed: 10/07/2014
• Issued: 02/14/2017
• Est. Priority Date: 10/07/2014
• Status: Active Grant

• Current Assignee: Check Point Software Technologies Limited
• Original Assignee: Check Point Software Technologies Limited
• Inventors: Chandel, Ajay
• Primary Examiner(s): TSUI, DANIEL D
• Application Number:
  US14/507,930
• Publication Number:
  US 20160098361A1
• Time in Patent Office: 861 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 2212/1008 Correctness of operation, e.g. memory ordering
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

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.

Claims

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.