System, method and computer program product for implementing scalable multi-reader/single-writer locks
First Claim
1. A method for implementing a scalable multi-reader/single-writer lock within a computer system, comprising the steps of:
- (1) allocating a registry data structure corresponding to a resource within the computer system;
(2) allocating a client data structure, linked to said registry data structure, corresponding to a client within the computer system which requires read access to said resource, wherein said client data structure comprises a read enable flag initialized to a first enable state, and a read use flag initialized to a first use state;
(3) determining, by said client, whether said read enable flag is set to said first enable state;
(4) setting, by said client, said read use flag to a second use state when the determination of step (3) is positive;
(5) performing, by said client, at least one read operation on said resource; and
(6) setting, by said client, said read use flag to said first use state when step (5) is completed;
whereby the scalable multi-reader/single-writer lock allows readers to proceed in parallel without contending for a common resource within the computer system.
13 Assignments
0 Petitions
Accused Products
Abstract
An scalable multi-reader/single-writer lock implementation that eliminates contention for lock data structures that can occur in large symmetric multi-processing (SMP) computer systems. The present invention includes a registry head data structure for each critical resource within the computer system. Linked to each of the registry head data structures are one or more client data structures that represent each client (i.e., process, thread, interrupt handler, and the like) that needs read and/or write access to the critical resource represented by the registry head data structure. Further, five operations—Initialization, Adding a Client, Deleting a Client, Obtaining Read Access, and Obtaining Write Access—are provided in order to achieve the goal of contention elimination.
46 Citations
14 Claims
-
1. A method for implementing a scalable multi-reader/single-writer lock within a computer system, comprising the steps of:
-
(1) allocating a registry data structure corresponding to a resource within the computer system;
(2) allocating a client data structure, linked to said registry data structure, corresponding to a client within the computer system which requires read access to said resource, wherein said client data structure comprises a read enable flag initialized to a first enable state, and a read use flag initialized to a first use state;
(3) determining, by said client, whether said read enable flag is set to said first enable state;
(4) setting, by said client, said read use flag to a second use state when the determination of step (3) is positive;
(5) performing, by said client, at least one read operation on said resource; and
(6) setting, by said client, said read use flag to said first use state when step (5) is completed;
whereby the scalable multi-reader/single-writer lock allows readers to proceed in parallel without contending for a common resource within the computer system. - View Dependent Claims (2, 3, 4)
said first enable state is equal to one;
said first use state is equal to zero; and
said second use state is equal to one.
-
-
4. The method of claim 1, wherein said client data structure is linked to said registry data structure using a double linked-list.
-
5. A method for implementing a scalable multi-reader/single-writer lock within a computer system, comprising the steps of:
-
(1) allocating a registry data structure corresponding to a resource within the computer system, wherein said registry data structure comprises a writer flag initialized to a first write state and a spin lock initialized to a unlocked state;
(2) allocating a plurality of client data structures, linked to said registry data structure, each corresponding to a plurality of clients within the computer system which require write access to said resource, wherein each of said plurality of client data structures comprises a read enable flag initialized to a first enable state, and a read use flag initialized to a first use state; and
(3) performing, by one of said plurality of clients, at least one write operation on said resource, said performing step comprising the steps of;
(a) obtaining said spin lock in order to change its state to a locked state;
(b) determining if said read use flag is set to said first use state within others of said plurality of client data structures;
(c) setting said read enable flag within said others of said plurality of client data structures to a second enable state when the determination of step (b) is positive;
(d) updating the value of said writer flag to a second write state; and
(e) releasing said spin lock by changing its state to said unlocked state;
whereby the scalable multi-reader/single-writer lock avoids race conditions by assuring only a single writer can access the contents of said resource. - View Dependent Claims (6, 7, 8)
(f) obtaining, after performing at least one write operation on said resource, said spin lock in order to change its state to said locked state;
(g) setting said read enable flag within said others of said plurality of client data structures to said first enable state;
(h) updating the value of said writer flag to said first write state; and
(i) releasing said spin lock by changing its state to said unlocked state.
-
-
8. The method of claim 7, wherein:
-
said first write state is equal to zero;
said second write state is equal to one;
said first enable state is equal to one;
said second enable state is equal to zero;
said first use state is equal to zero; and
said second use state is equal to one.
-
-
9. A system for implementing a scalable multi-reader/single-writer lock within a computer system, comprising:
-
(a) a registry data structure corresponding to a resource within the computer system, wherein said registry data structure comprises;
(i) a writer flag initialized a first write state;
(ii) and a spin lock initialized to a unlocked state;
(b) a plurality of client data structures, linked to said registry data structure, corresponding to a plurality of clients within the computer system which desire read and write access to said resource, each of said plurality of client data structures comprising;
(i) a read enable flag initialized to a first enable state; and
(ii) a read use flag initialized to a first us e state;
(c) means for each of said plurality of clients to;
(i) obtain said spin lock in order to change its state to a locked state, (ii) determine if said read use flag is set to said first use state within each of said plurality of client data structures, (iii) set said read enable flag within each of said plurality of clients data structures a second enable state, and (iv) update the value of said writer flag to a second write state, before performing at least one write operation on said resource; and
(d) means for each of said plurality of clients to set said read use flag within its corresponding said plurality of client data structures to a second use state before performing at least one read operation on said resource;
whereby the scalable multi-reader/single-writer lock allows readers to proceed in parallel without contending for a common resource within the computer system, and avoids race conditions by assuring only a single writer can access the contents of said resource.
-
-
10. A system for implementing a scalable multi-reader/single-writer lock, within the operating system of a computer system, comprising:
-
a registry data structure corresponding to a resource within the computer system;
a plurality of clients within the computer system which require read access to said resource;
a plurality of client data structures, linked to said registry data structure, each corresponding to one of said plurality of clients, wherein each of said client data structures comprises a read enable flag indicating that said client is preapproved to read said resource; and
means for one of said plurality of clients to disable said read enable flag corresponding to others of said plurality of clients before performing at least one write operation on said resource;
wherein the scalable multi-reader/single-writer lock allows said plurality of clients to obtain read access to said resource in parallel without contending for said registry data structure, and avoids race conditions within the computer system by assuring only a single one of said plurality of clients can obtain write access to the contents of said resource at one time.
-
-
11. A computer program product comprising a computer usable medium having control logic stored therein for causing a computer to implement a scalable multi-reader/single-writer lock within its operating system, said control logic comprising:
-
first computer readable program code means for causing the computer to allocate a registry data structure corresponding to a resource within the computer;
second computer readable program code means for causing the computer to allocate a client data structure, linked to said registry data structure, corresponding to a client within the computer which requires read access to said resource, wherein said client data structure comprises a read enable flag initialized to a first enable state, and a read use flag initialized to a first use state;
third computer readable program code means for causing the computer to determine whether said read enable flag is set to said first enable state;
fourth computer readable program code means for causing the computer to set said read use flag to a second use state when the determination of said third computer readable program code means is positive;
fifth computer readable program code means for causing the computer to allow said client to perform at least one read operation on said resource; and
sixth computer readable program code means for causing the computer to set said read use flag to said first use state when said client has completed said at least one read operation on said resource;
whereby the scalable multi-reader/single-writer lock allows readers to proceed in parallel without contending for a common resource within the computer. - View Dependent Claims (12)
-
-
13. A computer program product comprising a computer usable medium having control logic stored therein for causing a computer to implement a scalable multi-reader/single-writer lock within its operating system, said control logic comprising:
-
first computer readable program code means for causing the computer to allocate a registry data structure corresponding to a resource within the computer, wherein said registry data structure comprises a writer flag initialized to a first write state and a spin lock initialized to a unlocked state;
second computer readable program code means for causing the computer to allocate a plurality of client data structures, linked to said registry data structure, each corresponding to a plurality of clients within the computer which require write access to said resource, wherein each of said plurality of client data structures comprises a read enable flag initialized to a first enable state, and a read use flag initialized to a first use state; and
third computer readable program code means for causing the computer to allow one of said plurality of clients to perform at least one write operation on said resource, said third computer readable program code means comprising;
fourth computer readable program code means for causing the computer to obtain said spin lock in order to change its state to a locked state;
fifth computer readable program code means for causing the computer to determine if said read use flag is set to said first use state within others of said plurality of client data structures;
sixth computer readable program code means for causing the computer to set said read enable flag within said others of said plurality of client data structures to said first enable state when the determination of said fifth computer readable program code means is positive;
seventh computer readable program code means for causing the computer to update the value of said writer flag to a second write state; and
eighth computer readable program code means for causing the computer to release said spin lock by changing its state to said unlocked state;
whereby the scalable multi-reader/single-writer lock avoids race conditions by assuring only a single writer can access the contents of said resource. - View Dependent Claims (14)
ninth computer readable program code means for causing the computer to obtain, after said one of said plurality of clients performs at least one write operation on said resource, said spin lock in order to change its state to said locked state;
tenth computer readable program code means for causing the computer to set said read enable flag within said others of said plurality of client data structures to said first enable state;
eleventh computer readable program code means for causing the computer to update the value of said writer flag to said first write state; and
twelfth computer readable program code means for causing the computer to release said spin lock by changing its state to said unlocked state.
-
Specification