Method for increased concurrency in a computer system

• US 7,111,293 B1
• Filed: 06/03/1999
• Issued: 09/19/2006
• Est. Priority Date: 06/03/1998
• Status: Expired due to Term

• Current Assignee: Four J's Development Tools Incorporated
• Original Assignee: Ants Software, Inc.
• Inventors: Gaeta, legal representative, Dominic, Sullivan, deceased, Herbert W., Todd, legal representative, Joan, Hersh, Clifford L.
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Truong, Camquy
• Application Number:
  US09/701,797
• Time in Patent Office: 2,665 Days
• Field of Search: 718/100, 709/234, 711/147
• US Class Current: 718/100
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications

Abstract

A method for enhancing concurrency in a multiprocessor computer system is described. Various tasks in a computer system communicate using commonly accessible mailboxes to access valid data from a location in the mailbox. A task holding the valid data places that data in a mailbox, and other tasks read the valid data from the mailbox. The task that inputs the valid data into the mailbox is caused to notify other tasks addressing the mailbox that the valid data is contained therein. Thus, no central coordination of mailbox access is required. Further, busy waits for valid data are minimized and the ressources of tasks and processors are used more efficiently. By coordinating several lists associated with each mailbox, conflicts in accessing data and delays in obtaining data are also minimized.

Claims

1. A method for operating a computer system, said computer system including at least one processor, comprising:

establishing a plurality of memory units each having a corresponding memory location;

executing a plurality of tasks running on said at least one processor, said plurality of tasks being operable to share data;

defining a plurality of lists for each memory location;

determining the validity of said data in one memory unit of said plurality of memory units;

locking at least one of said plurality of lists if said data is invalid;

inserting an entry corresponding to one of said plurality of tasks onto said locked list;

unlocking said locked list; and

determining if data is inputted in said corresponding memory location of said one memory unit between said determining step and said unlocking step.

2. A method for operating a computer system, said computer system comprising at least one processor, comprising:

establishing a plurality of memory units each having a corresponding memory location;

running a plurality of tasks on said processor, said plurality of tasks being operable to share data;

defining a plurality of lists for each memory location;

inserting an entry corresponding to one of said plurality of tasks onto one of said plurality of lists if said one list is unlocked; and

determining if another of said lists is unlocked if said one list is locked.

3. A method for synchronizing processes in a computer system, said computer system including at least one processor, comprising:

establishing a plurality of memory units each having a corresponding memory location;

executing a plurality of tasks running on said processor, said plurality of tasks being operable to share data located in said memory units;

defining a plurality of lists for each memory location;

locking at least one of said plurality of lists if said data is not valid in one of said plurality of memory units;

inserting an entry corresponding to one of said plurality of tasks onto said locked list;

unlocking said locked list;

suspending said one of said plurality of tasks until valid data is found in said member of said memory units;

reading said valid data;

determining if other data is inputted in said one of said memory units after said locking step and before said unlocking step; and

reading said other data if said other data appears in said memory unit.

4. The method of claim 3, wherein the locking step further comprises activating selected other ones of said plurality of tasks that are entered on said locked list.

5. The method of claim 3, wherein said plurality of lists includes a linked list.

6. The method of claim 3, wherein said plurality of lists is between four and eight.

7. The method of claim 3, further comprising transferring the operation of said locked list when said locked list is locked by another one of said plurality of tasks.

8. A computer system having enhanced concurrency, comprising:

a plurality of processors;

a plurality of tasks running on said plurality of processors;

a plurality of memory units each having a corresponding memory location;

a plurality of lists corresponding to each of said memory location;

wherein one of said plurality of tasks is responsible for activating selected ones of said plurality of tasks contained on the same list as said one task.

9. The system of claim 8, wherein said plurality of lists form a linked list.

10. The system of claim 8, wherein said plurality of lists is between four and eight.

11. The system of claim 8, wherein said computer system is a multitasking or multiprocessing computer system.

12. A method of operating a computer system having at least one processor, comprising:

determining the validity of data in a memory unit;

locking a list corresponding to said memory unit if said data is invalid;

inserting an entry corresponding to one of a plurality of tasks onto said locked list;

unlocking said locked list; and

determining if data is inputted in a memory location within said memory unit between said determining step and said unlocking step.