Protecting shared resources using mutex striping

• US 6,199,094 B1
• Filed: 06/05/1998
• Issued: 03/06/2001
• Est. Priority Date: 06/05/1998
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Presler-Marshall, Martin Joseph Clayton
• Primary Examiner(s): Oberley, Alvin E.
• Assistant Examiner(s): NGUYEN, VAN H
• Application Number:
  US09/093,627
• Time in Patent Office: 1,005 Days
• Field of Search: 709/104, 709/105, 709/107, 710/200
• US Class Current: 718/104
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A technique, system, and computer program for improving access to shared resources in a computing system. The shared resources are grouped into application-defined resource sets. Mutual exclusion semaphores are used. A semaphore is associated with each resource set to provide mutually-exclusive (serialized) access to the resources in the set. The number of semaphores will be smaller (typically, much smaller) than the number of resource sets, so that a given semaphore will be associated with multiple of such sets. Thus, the set of semaphores is striped across the collection of resource sets. This greatly increases allowable parallelism in accessing shared resources, while reducing the number of semaphores that are required.

Claims

1. In a computing system, computer-readable code embodied on one or more computer-readable media readable by said system for improving shared access to resources, comprising:

a subprocess for grouping a plurality of sharable resources into a plurality of resource sets, each of said sharable resources being a member of only one of said resource sets;

a subprocess for associating each of a plurality of semaphores with one or more of said resource sets, at least one of said semaphores being concurrently associated with more than one of said resource sets, wherein a number of said resource sets to be concurrently associated with each semaphore is determined by evaluating an expression (K modulo N) wherein “

K”

represents a count of said resource sets and “

N”

represents a count of said semaphores and wherein N is less than K; and

a subprocess for locking a selected sharable resource, said selected sharable resource being one of said members of a selected resource set, using a selected semaphore associated with said selected resource set, thereby also locking all of said sharable resources which are grouped into all of said one or more resource sets associated with said selected semaphore.

2. Computer readable code for improving shared access to resources according to claim 1, wherein said computing system resides in a computer network.

3. Computer-readable code for improving shared access to resources according to claim 1 or claim 2, wherein said subprocess for associating semaphores further comprises a subprocess for sequentially assigning each successive result of an expression (I modulo N), wherein I is a counter successively stepping through a range of values between 0 and (K−

1), to a successive value of K.

4. Computer-readable code for improving shared access to resources according to claim 1 or claim 2, wherein said subprocess for associating semaphores further comprises a subprocess for assigning each successive one of said plurality of semaphores to a sequential range of values of K, wherein a particular number of said values of K to be assigned to said successive one of said semaphores is determined using a result of said expression.

5. A system for improving shared access to resources in a computing system, comprising:

a plurality of sharable resources;

a plurality of semaphores;

means for grouping said sharable resources into a plurality of resource sets, each of said sharable resources being a member of only one of said resource sets;

means for associating each of said plurality of semaphores with one or more of said resource sets, at least one of said semaphores being concurrently associated with more than one of said resource sets, wherein a number of said resource sets to be concurrently associated with each semaphore is determined by evaluating an expression (K modulo N) wherein “

K”

represents a count of said resource sets and “

N”

represents a count of said semaphores and wherein N is less than K; and

means for locking a selected sharable resource, said selected sharable resource being one of said members of a selected resource set, using a selected semaphore associated with said selected resource set, thereby also locking all of said sharable resources which are grouped into all of said one or more resource sets associated with said selected semaphore.

6. The system for improving shared access to resources according to claim 5, wherein said computing system resides in a computer network.

7. The system for improving shared access to resources according to claim 5 or claim 6, wherein said means for associating semaphores further comprises means for sequentially assigning each successive result of an expression (I modulo N), wherein I is a counter successively stepping through a range of values between 0 and (K−

1), to a successive value of K.

8. The system for improving shared access to resources according to claim 5 or claim 6, wherein said means for associating semaphores further comprises means for assigning each successive one of said plurality of semaphores to a sequential range of values of K, wherein a particular number of said values of K to be assigned to said successive one of said semaphores is determined using a result of said expression.

9. A method for improving access to shared resources in a computing system, comprising the steps of:

grouping a plurality of sharable resources into a plurality of resource sets, each of said sharable resources being a member of only one of said resource sets;

associating a plurality of semaphores with one or more of said resource sets, at least one of said semaphores being concurrently associated with more than one of said resource sets, wherein a number of said resource sets to be concurrently associated with each semaphore is determined by evaluating an expression (K modulo N) wherein “

K”

represents a count of said resource sets and “

N”

represents a count of said semaphores and wherein N is less than K; and

locking a selected sharable resource, said selected sharable resource being one of said members of a selected resource set, using a selected semaphore associated with said selected resource set, thereby also locking all of said sharable resources which are grouped into all of said one or more resource sets associated with said selected semaphore.

10. The method for improving shared access to resources according to claim 9, wherein said computing system resides in a computer network.

11. The method for improving shared access to resources according to claim 9 or claim 10, wherein said associating semaphores step further comprises sequentially assigning each successive result of an expression (I modulo N), wherein I is a counter successively stepping through a range of values between 0 and (K−

1), to a successive value of K.

12. The method for improving shared access to resources according to claim 9 or claim 10, wherein said associating semaphores step further comprises assigning each successive one of said plurality of semaphores to a sequential range of values of K, wherein a particular number of said values of K to be assigned to said successive one of said semaphores is determined using a result of said expression.