Read/write lock with reduced reader lock sampling overhead in absence of writer lock acquisition

• US 7,934,062 B2
• Filed: 06/22/2007
• Issued: 04/26/2011
• Est. Priority Date: 06/22/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Shenoy, Gautham R., Srivatsa, Vaddagiri, McKenney, Paul E.
• Primary Examiner(s): Kim; Matt
• Assistant Examiner(s): ROSSITER, SEAN D
• Application Number:
  US11/767,020
• Publication Number:
  US 20080320262A1
• Time in Patent Office: 1,404 Days
• Field of Search: None
• US Class Current: 711/147
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

An improved reader-writer locking for synchronizing access to shared data. When writing the shared data, a writer flag is set and a lock is acquired on the shared data. The shared data may be accessed following the expiration of a grace period and a determination that there are no data readers accessing the shared data. When reading the shared data, the writer flag is tested that indicates whether a data writer is attempting to access the shared data. If the writer flag is not set, the shared data is accessed using a relatively fast read mechanism. If the writer flag is set, the shared data is accessed using a relatively slow read mechanism.

Claims

1. A method for synchronizing access to shared data, comprising:

when reading said shared data is performed by a data reader;

said data reader testing a writer flag that indicates whether a separate data writer is attempting to access said shared data;

said data reader accessing said shared data using a fast read mechanism if said writer flag is not set, said fast read mechanism including said data reader performing an indicating action prior to reading said shared data that indicates to data writers desiring to access said shared data that said data reader has initiated accessing said shared data using said fast read mechanism; and

said data reader accessing said shared data using a slow read mechanism if said writer flag is set, said slow read mechanism including said data reader waiting for a data writer to complete its access to said shared data; and

when writing said shared data is performed by a data writer;

said data writer setting said writer flag;

following said writer flag setting, said data writer waiting for expiration of a grace period in which all executing instances of said data reader have an opportunity to either see said writer flag and initiate said slow read mechanism or complete said indicating action indicating that said data reader has initiated said fast read mechanism;

following said grace period expiration, said data writer waiting until there are no data readers accessing said shared data using said fast read mechanism;

following said waiting until there are no data readers, said data writer acquiring a lock on said shared data, said lock being different from said writer flag; and

said data writer accessing said shared data.

2. A method in accordance with claim 1 wherein said fast read mechanism comprises said data reader incrementing a reader reference counter prior to a data reader accessing said shared data and decrementing said reader reference counter after said data reader accesses said shared data, said incrementing a reader reference counter representing said indicating action.

3. A method in accordance with claim 1 wherein said slow read mechanism comprises said data reader waiting for read access prior to said data reader accessing said shared data and thereafter enabling a waiting data writer if there are no other waiting data readers.

4. A method in accordance with claim 1 wherein said grace period guarantees that said writer flag will be seen in a set condition if said writer flag is tested after said writer flag is set.

5. A method in accordance with claim 2 wherein said grace period guarantees that said incrementing of said reader reference counter will complete prior to said data writer determining that no data readers are accessing said shared data if said writer flag is tested before said writer flag is set.

6. A method in accordance with claim 1 wherein said writer flag is settable to a no_writers condition indicating that no data writers currently have or are waiting for exclusive write access to said shared data, a writer_waiting condition indicating that one or more data writers are waiting for exclusive write access to said shared data, and a writer_active condition indicating that a data writer has exclusive access to said shared data, and wherein acquiring said lock is effectuated by said data writer setting said writer flag to said writers_active condition.

7. A method in accordance with claim 6 wherein said lock comprises a writer wait queue for said data writers to wait for exclusive write access to said shared data when said writer flag is in said writer_waiting condition, said writer wait queue being used to identify said waiting data writers in order for an eligible one of said waiting data writers to be enabled for exclusive write access to said shared data by another writer completing its writing of said shared data or by a reader completing its reading of said shared data using said slow read mechanism, and wherein said lock further comprises a reader wait queue for data readers to wait for read access to said shared data, said reader wait queue being used to identify an eligible one of said waiting data readers to be enabled for read access to said shared data by a data writer completing its writing of said shared data and setting said writer flag to said no_writers condition.

8. A data processing system having one or more processors, a memory and a communication pathway between the one or more processors and the memory, said system being adapted to synchronize access to shared data, and comprising:

a writer flag settable by a data writer that indicates whether said data writer is attempting to access said shared data;

fast path read logic executed by a data reader and adapted to coordinate fast reader access to said shared data on behalf of said data reader when said writer flag is not set by said data writer, said fast reader access including said data reader performing an indicating action prior to reading said shared data that indicates to data writers desiring to access said shared data that said data reader has initiated accessing said shared data using said fast read access;

slow path read logic executed by said data reader and adapted to coordinate slow reader access to said shared data on behalf of said data reader when said writer flag is set, said slow reader access including said data reader waiting for a data writer to complete its access to said shared data;

first write logic executed by said data writer and adapted to set said writer flag;

grace period processing logic executed by said data writer and adapted to implement a grace period following said writer flag being set by said data writer;

second write logic executed by said data writer after said first write logic and adapted to wait for expiration of said grace period in which all executing instances of said data reader have an opportunity to either see said writer flag and initiate said slow path read logic or complete said indicating action of said fast path read logic;

third write logic executed by said data writer after said second write logic and adapted to wait until there are no data readers accessing said shared data using said fast path read logic; and

fourth write logic executed by said data writer after said third write logic and adapted to acquire a lock on said shared data on behalf of said data writer, said lock being different from said writer flag.

9. A system in accordance with claim 8 wherein said fast read logic is adapted to increment a reader reference counter prior to said data reader accessing said shared data and to decrement said reader reference counter after said data reader accesses said shared data, said increment of said reader reference counter representing said indicating action.

10. A system in accordance with claim 8 wherein said slow read logic is adapted to wait for read access prior to accessing said shared data and thereafter enable a waiting data writer if there are no other waiting data readers.

11. A system in accordance with claim 8 wherein said grace period guarantees that said data reader will see said writer flag in a set condition if said data reader tests said writer flag after said writer flag is set.

12. A system in accordance with claim 9 wherein said grace period guarantees that said incrementation of said reader reference counter will complete prior to said second write logic determining that no data readers are accessing said shared data if said writer flag is tested before said writer flag is set.

13. A system in accordance with claim 8 wherein said writer flag is settable to a no_writers condition indicating that no data writers currently have or are waiting for exclusive write access to said shared data, a writer_waiting condition indicating that one or more data writers are waiting for exclusive write access to said shared data, and a writer_active condition indicating that a data writer has exclusive access to said shared data, and wherein acquiring said lock is effectuated by said data writer setting said writer flag to said writers_active condition.

14. A computer program product for synchronizing access to shared data, comprising:

one or more non-transitory machine-readable media;

program instructions provided by said one or more media for programming a data processing platform to operate as by;

when reading said shared data is performed by a data reader;

said data reader testing a writer flag that indicates whether a separate data writer is attempting to access said shared data;

said data reader accessing said shared data using a fast read mechanism if said writer flag is not set, said fast read mechanism including said data reader performing an indicating action prior to reading said shared data that indicates to data writers desiring to access said shared data that said data reader has initiated accessing said shared data using said fast read mechanism; and

said data reader accessing said shared data using a slow read mechanism if said writer flag is set, said slow read mechanism including said data reader waiting for a data writer to complete its access to said shared data; and

when writing said shared data is performed by a data writer;

said data writer setting said writer flag;

following said writer flag setting, said data writer waiting for expiration of a grace period in which all executing instances of said data reader have an opportunity to either see said writer flag and initiate said slow read mechanism or complete said indicating action of indicating that said data reader has initiated said fast read mechanism;

upon expiration of said grace period, said data writer waiting until there are no data readers accessing said shared data using said fast read mechanism;

following said waiting until there are no data readers, said data writer acquiring a lock on said shared data, said lock being different from said writer flag; and

said data writer accessing said shared data.

15. A computer program product in accordance with claim 14 wherein said fast read mechanism comprises incrementing a reader reference counter prior to a data reader accessing said shared data and decrementing said reader reference counter after said data reader accesses said shared data, said incrementing a reader reference counter representing said indicating action.

16. A computer program product in accordance with claim 14 wherein said slow read mechanism comprises said data reader waiting for read access prior to a data reader accessing said shared data and thereafter enabling a waiting data writer if there are no other waiting data readers.

17. A computer program product in accordance with claim 14 wherein said grace period guarantees that said writer flag will be seen in a set condition if said writer flag is tested after said writer flag is set.

18. A computer program product in accordance with claim 15 wherein said grace period guarantees that said incrementing of said reader reference counter will complete prior to said data writer determining that no data readers are accessing said shared data if said writer flag is tested before said writer flag is set.

19. A computer program product in accordance with claim 14 wherein said writer flag is settable to a no_writers condition indicating that no data writers currently have or are waiting for exclusive write access to said shared data, a writer_waiting condition indicating that one or more data writers are waiting for exclusive write access to said shared data, and a writer_active condition indicating that a data writer has exclusive access to said shared data, and wherein acquiring said lock is effectuated by said data writer setting said writer flag to said writers_active condition.

20. A computer program product for synchronizing access to shared data, comprising:

one or more non-transitory machine-readable media;

program instructions provided by said one or more media for programming a data processing platform to operate as by;

a data writer setting a writer flag;

following said writer flag setting, said data writer waiting for expiration of a grace period in which all executing instances of a data reader of said shared data have an opportunity to either see said writer flag and initiate a slow read mechanism or perform a fast read mechanism indicating action that indicates to a data writer desiring to access said shared data that said data reader has initiated accessing said shared data using said fast read mechanism;

following said grace period expiration, said data writer waiting until there are no data readers accessing said shared data;

following said waiting until there are no data readers, said data writer acquiring a lock on said shared data, said lock being different from said writer flag; and

said data writer accessing said shared data.