Distributed monitor concurrency control

• US 6,622,155 B1
• Filed: 11/24/1998
• Issued: 09/16/2003
• Est. Priority Date: 11/24/1998
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Haddon, Bruce Kenneth, Connor, William Hayden
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US09/198,477
• Time in Patent Office: 1,757 Days
• Field of Search: 709/106, 709/104, 709/100, 709/101, 709/102, 709/103, 709/105, 709/108, 709/201
• US Class Current: 718/100
• CPC Class Codes: G06F 9/449 Object-oriented method invocation or resolution
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A system and method is disclosed for synchronizing threads of execution within a distributed computing environment. Threads of execution within a computer spawn additional threads of execution on separate computers within the distributed computing environment. Each thread may compete for shared resources within the computing environment, thereby creating a need to avoid deadlocks among the local threads. Whereas locals thread exists within a single computing platform, logical threads are created to relate local threads to each other and thereby span the platforms on which the local threads reside. Distributed monitors are created to control access to shared resources by local threads based on logical thread affiliations. Locks within the distributed monitors are assigned to logical threads instead of local threads. Local threads that are each part of the same logical thread will all have access to the shared resource when the lock is assigned to the logical thread.

Claims

1. A method for synchronizing concurrent threads within a distributed computing network, said method comprising the steps of:

(a) establishing a unique thread context for a first local thread on a first computer;

(b) performing a thread jump from the first computer to a second computer to thereby spawn a second local thread on the second computer, wherein the first computer and the second computer are part of the distributed computing network;

(c) transferring the unique thread context to the second local thread to thereby establish that the first local thread and the second local thread belong to the same logical thread.

2. The method according to claim 1, further comprising the steps of:

(a) acquiring a lock on a distributed monitor using the first local thread;

(b) associating the lock with the logical thread; and

(c) gaining access to the distributed monitor with the second local thread.

3. The method according to claim 1, further comprising the steps of:

(a) mapping, within the first computer, the first local thread to the logical thread; and

(b) mapping, within the second computer, the second local thread to the logical thread.

4. The method according to claim 3, further comprising the step of updating each mapping within each computer whenever a new logical thread is created.

5. The method according to claim 3, further comprising the step of updating each mapping within each computer whenever a new logical thread is terminated.

6. The method according to claim 3, wherein the mapping is a table within each of the first and second computers, said table containing associations of local threads to logical threads.

7. The method according to claim 1, further comprising the step of creating a distributed monitor on shared resources.

8. A computing system for thread synchronization in a distributed computing environment, said system comprising:

a first local thread resident on a first computer;

a second local thread resident on a second computer, wherein said first computer and said second computer form at least part of said distributed computing environment;

a logical thread comprised of said first local thread and said second local thread;

a first mapping, stored within said first computer, associating said first local thread with said logical thread; and

a second mapping, stored within said second computer, associating said second local thread with said logical thread.

9. The system according to claim 8, further comprising a distributed monitor configured to operate on the logical thread.

10. The system according to claim 9, wherein said distributed monitor is further configured to grant said second local thread access to a shared resource.

11. The system according to claim 8, wherein said first mapping is a table stored within said first computer, and wherein said second mapping is a table stored within said second computer.

12. A system for thread synchronization in a distributed computing environment, said system comprising:

a first local thread resident on a first computer;

a second local thread resident on a second computer, wherein said first computer and said second computer form at least part of said distributed computing environment;

a logical thread comprised of at least said first local thread and said second local thread;

a mapping within said first computer, said mapping associating said first local thread with said logical thread;

a mapping within said second computer, said mapping associating said second local thread with said logical thread; and

a distributed monitor within the distributed computing environment, comprised of (a) a queue, (b) a lock and (c) a shared resource, wherein said distributed monitor is configured to allow at least said first local thread and said second local thread to gain access to said shared resource whenever said logical thread has gained access to said lock.

13. A digital storage medium within a distributed computing environment, said digital storage medium configured to enable computer operations comprising:

(a) executing a first local thread on a first computer

(b) executing a second local thread on a second computer, said first computer and said second computer forming at least a portion of said distributed computing environment;

(c) defining a logical thread comprised of said first local thread and said second local thread;

(d) maintaining a mapping within said first computer to associate said first local thread with said logical thread;

(e) maintaining a mapping within said second computer to associate said second local thread with said logical thread; and

(f) using a distributed monitor with said logical thread to provide thread synchronization within said distributed computing environment.

14. A method, comprising:

spawning a first local thread on a first computing platform in response to a remote call from a second local thread on a second computing platform;

mapping the first local thread on the first computing platform to a first logical thread, wherein the first logical thread comprises the first local thread and the second local thread; and

the first local thread attempting to access a shared resource, wherein access to the shared resource is granted to the first local thread if a lock for the shared resource is held by the first logical thread.

15. The method as recited in claim 14, further comprising:

the first local thread spawning a third local thread on the first computing platform; and

mapping the third local thread to the first logical thread.

16. The method as recited in claim 15, further comprising the third local thread attempting to access the shared resource, wherein access to the shared resource is granted to the third local thread if the lock for the shared resource is held by the first logical thread.

17. The method as recited in claim 14, further comprising:

starting a fourth local thread on the first computing platform;

mapping the fourth local thread to a second logical thread;

the fourth local thread attempting to access the shared resource, wherein access to the shared resource is denied if the lock for the shared resource is held by the first logical thread.

18. The method as recited in claim 17, wherein in addition to the fourth local thread on the first computing platform, the second logical thread comprises one or more local threads on other computing platforms in a distributed computing environment.

19. A method for sharing a resource in a distributed computing environment, comprising:

assigning a lock for a shared resource to a first logical thread, wherein the logical thread comprises local threads on a plurality of different computing platforms in the distributed computing environment;

while the shared resource is assigned to the first local thread;

granting access to the shared resource for local threads belonging to the first logical thread; and

denying access to the shared resource for local threads not belonging to the first logical thread.

20. The method as recited in claim 19, further comprising queuing access requests from local threads not belonging to the logical thread currently holding the lock for the shared resource.

21. A method, comprising:

for each of a plurality of computing platforms in a distributed computing environment, mapping one or more local threads to one or more logical threads, wherein each local thread is a thread executing on one of the computing platforms and each logical thread comprises related local threads from different ones of the computing platforms;

assigning a lock for a shared resource to one of the logical threads; and

granting access to the shared resource to local threads belonging to the logical thread currently holding the lock for the shared resource.

22. The method as recited in claim 21, wherein at least two of the local threads that are granted access to the shared resource while their logical thread holds the lock, are executing on different computing platforms in the distributed computing environment.

23. The method as recited in claim 21, further comprising queuing access requests for the shared resource from local threads belonging to logical threads not currently holding the lock.

24. The method as recited in claim 23, further comprising:

the logical thread currently holding the lock releasing the lock; and

granting the lock to the logical thread for the next queued request.

25. The method as recited in claim 21, further comprising:

a local thread on a first one of the computing platforms making a remote call to a second one of the computing platforms;

spawning a local thread on the second one of the computing platforms in response to the remote call; and

mapping the local thread spawned on the second one of the computing platforms to the same logical thread as the local thread on the first one of the computing platforms that made the remote call.

26. The method as recited in claim 21, wherein each logical thread is uniquely identified across the distributed computing platform.

27. A system, comprising:

means executing a first local thread on a first computing platform in response to a remote call from a second local thread on a second computing platform;

a map configured to associate the first local thread on the first computing platform with a first logical thread, wherein the first logical thread comprises the first local thread and the second local thread; and

a computing resource, wherein access to the computing resource is granted to the first local thread if a lock for the computing resource is held by the first logical thread.

28. The system as recited in claim 27, further comprising:

means for executing a third local thread on the first computing platform in response to a call from the first local thread; and

wherein said map is configured to associate the third local thread to the first logical thread.

29. The system as recited in claim 28, wherein access to the shared resource is granted to the third local thread if the lock for the shared resource is held by the first logical thread.

30. The system as recited in claim 27, further comprising:

means for starting a fourth local thread on the first computing platform;

wherein said map is configured to associate the fourth local thread to a second logical thread; and

wherein access to the shared resource is denied for the fourth local thread while the lock for the shared resource is held by the first logical thread.

31. The system as recited in claim 30, wherein in addition to the fourth local thread on the first computing platform, the second logical thread comprises one or more local threads on other computing platforms in a distributed computing environment.

32. A system, comprising:

a shared resource;

a monitor for the shared resource, wherein the monitor is configured to assign a lock to a logical thread comprising one or more local threads on one or more computing platforms in a distributed computing environment;

wherein the monitor is configured to grant access to the shared resource for local threads belonging to the logical thread currently assigned the lock; and

wherein the monitor is configured to deny access to the shared resource for local threads not belonging to the logical thread currently assigned the lock.

33. The system as recited in claim 32, further comprising a queue configured to hold one or more access requests from local threads not belonging to the logical thread currently assigned the lock for the shared resource.

34. A system, comprising:

a plurality of computing platforms in a distributed computing environment, wherein each computing platform is configured to map one or more local threads to one or more logical threads, wherein each local thread is a thread executing on one of the computing platforms and each logical thread comprises related local threads from different ones of the computing platforms;

a shared resource;

a monitor for the shared resource, wherein the monitor is configured to assign a lock to one of the logical threads; and

wherein access to the shared resource is granted to local threads belonging to the logical thread currently holding the lock for the shared resource.

35. The system as recited in claim 34, wherein at least two of the local threads that are granted access to the shared resource while their logical thread holds the lock, are executing on different computing platforms in the distributed computing environment.

36. The system as recited in claim 34, wherein the monitor comprises a queue configured to queue access requests for the shared resource from local threads belonging to logical threads not currently holding the lock.

37. The system as recited in claim 36, wherein the monitor is configured to grant the lock to the logical thread for the next queued request when the logical thread currently holding the lock releases the lock.

38. The system as recited in claim 34, wherein:

one of the computing platforms is configured to spawn a local thread in response to a remote call from another local thread on another one of the computing platforms; and

the one of the computing platforms on which the local thread is spawned is configured to map the spawned local thread to the same logical thread as the local thread on the one of the computing platforms that made the remote call.

39. The system as recited in claim 34, wherein each logical thread is uniquely identified across the distributed computing platform.

40. A digital storage medium configured to enable computer operations comprising:

spawning a first local thread on a first computing platform in response to a remote call from a second local thread on a second computing platform;

mapping the first local thread on the first computing platform to a first logical thread, wherein the first logical thread comprises the first local thread and the second local thread; and

the first local thread attempting to access a shared resource, wherein access to the shared resource is granted to the first local thread if a lock for the shared resource is held by the first logical thread.

41. The digital storage medium as recited in claim 40, further configured to enable computer operations comprising:

the first local thread spawning a third local, thread on the first computing platform; and

mapping the third local thread to the first logical thread.

42. The digital storage medium as recited in claim 41, further configured to enable computer operations comprising the third local thread attempting to access the shared resource, wherein access to the shared resource is granted to the third local thread if the lock for the shared resource is held by the first logical thread.

43. The digital storage medium as recited in claim 40, further configured to enable computer operations comprising:

starting a fourth local thread on the first computing platform;

mapping the fourth local thread to a second logical thread;

the fourth local thread attempting to access the shared resource, wherein access to the shared resource is denied if the lock for the shared resource is held by the first logical thread.

44. The digital storage medium as recited in claim 43, wherein in addition to the fourth local thread on the first computing platform, the second logical thread comprises one or more local threads on other computing platforms in a distributed computing environment.

45. A digital storage medium configured to enable computer operations comprising:

assigning a lock for a shared resource to a first logical thread, wherein the logical thread comprises local threads on a plurality of different computing platforms in the distributed computing environment;

while the shared resource is assigned to the first logical thread;

granting access to the shared resource for local threads belonging to the first logical thread; and

denying access to the shared resource for local threads not belonging to the first logical thread.

46. The digital storage medium as recited in claim 45, further configured to enable computer operations comprising queuing access requests from local threads not belonging to the logical thread currently holding the lock for the shared resource.