Queueing method supporting multiple client accesses simultaneously

• US 6,898,650 B1
• Filed: 08/10/2000
• Issued: 05/24/2005
• Est. Priority Date: 08/10/2000
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Song, Yi, Gao, Changju
• Primary Examiner(s): Vo, Tim
• Application Number:
  US09/636,293
• Time in Patent Office: 1,748 Days
• Field of Search: 710/200, 710/220, 710/240, 710/241, 710/243, 710/244, 710/260, 710/261, 709/1, 709100-106, 707 1- 3, 707 7- 9
• US Class Current: 710/200
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A queue includes a plurality of containers. Each container includes a lock. Clients, possibly in a multiprocessor system, can simultaneously access the queue, each client locking only a single container a needed. A manager can lock the entire queue to perform maintenance.

Claims

1. A queueing system supporting multiple simultaneous accesses, the queueing system comprising:

a computer;

a plurality of containers stored in the computer, each container storing data and including a container lock, so that the container locks are decentralized and a client acquires the container lock directly from the container upon the client locating the container; and

a queue head stored in the computer and pointing to a first container.

2. A queueing system according to claim 1, further comprising means for accessing the containers deterministically.

3. A queueing system according to claim 1, further comprising means for accessing the containers non-deterministically.

4. A queueing system according to claim 1, wherein the queue head includes a queue lock.

5. A queueing system according to claim 1, further comprising a manager to manage the queueing system.

6. A queueing system according to claim 1, further comprising a manager notification system to notify a manager when the queueing system requires maintenance.

7. A queueing system according to claim 1, wherein the computer is part of a multiprocessor computer system.

8. A queueing system according to claim 1, wherein the queue head includes a counter indicating the number of containers storing valid data.

9. A queueing system according to claim 1, wherein the container lock associated with each container includes an in-use flag specifying whether the associated container is being used.

10. A queueing system according to claim 5, wherein the manager is adapted to control the number of containers in the queueing system.

11. A queueing system according to claim 9, wherein the container lock associated with each container further includes a valid data flag specifying whether the associated container contains valid data.

16. A computer-readable medium containing a program to use a queue supporting multiple simultaneous accesses, the program being executable on the computer system to implement the method of claim 2.

12. A method for using a queue supporting multiple simultaneous accesses, the method comprising:

locating a container by a client;

acquiring a lock for the container directly from the container by the client;

using the container by the client; and

releasing the container lock by the client.

13. A method according to claim 12, wherein:

acquiring a lock includes acquiring a read/write lock for the queue; and

releasing the container lock includes releasing the read/write lock.

14. A method according to claim 12, wherein the method is implemented in a multiprocessor computer system.

15. A method according to claim 12, further comprising adjusting a queue counter.

17. A method according to claim 12, wherein acquiring a lock for the container includes testing to determine if the container is already being accessed.

18. A method according to claim 13, wherein:

the method further comprises acquiring the read/write lock for the queue by a manager; and

acquiring a read/write lock for the queue includes waiting for the manager to release the read/write lock.

19. A method according to claim 13, wherein acquiring a read/write lock for the queue includes simultaneously allowing multiple accesses to containers in the queue.

20. A method according to claim 13, wherein acquiring a lock for the container includes locating a second container if the container is already being accessed.