Method for synchronizing the dispatching of tasks among multitasking operating systems

• US 5,319,782 A
• Filed: 02/16/1993
• Issued: 06/07/1994
• Est. Priority Date: 01/31/1989
• Status: Expired due to Term

• Current Assignee: International Business Machines SA (International Business Machines Corporation)
• Original Assignee: International Business Machines SA (International Business Machines Corporation)
• Inventors: Mouton, Jerome A. Jr., Goldberg, Steven H., Holten, Gerald W.
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): CHAVIS, JOHN Q
• Application Number:
  US08/018,341
• Time in Patent Office: 476 Days
• Field of Search: 395/650, 395/700
• US Class Current: 718/104
• CPC Class Codes: G06F 8/458 Synchronisation, e.g. post-wait, barriers, locks synchronisation among tasks G06F9/52

Abstract

A method for synchronizing the dispatching of tasks from a CPU-based first multitasking operating system (OS) with threads of function calls opportunistically dispatched from a CPU-based second multitasking operating system. The second OS includes a set of callable resources. In the method, a task becomes bound to a thread for the duration of that thread'"'"'s ownership of a callable resource from the second OS. Also, a thread becomes available on a work queue of threads for binding to a task only if the thread owns exactly one resource. After execution, the function is eliminated from the thread and ownership of that resource is relinquished and passed to the next thread queued on that resource. A task can remain bound to the same thread if there are no other threads asserting ownership to the next resource being called by the original thread. With contention, however, the task relinquishes the thread and becomes bound to another thread on the work queue.

Claims

1. In system having a CPU including a first and a second multitasking operating system (OS), means responsive to data originating from one or more applications either executing with said first OS or externally on another CPU for invoking threads of function calls (FIG. 4D, StartThread) by the second OS, a method for synchronizing the dispatching of tasks from the first OS with counterpart threads dispatched from the second OS, said second OS including a plurality of of callable layered resources, comprising the steps by the second OS in nested iterative order of:

(a) enqueuing (FIG. 4B, EnqTie) each thread against each second OS resource, each second OS resource being named by a function call in said thread;

(b) securing resource ownership (FIG. 4B, DeqTie) to each thread among those threads enqueued against any one of the second OS resources in step (a) by binding at least a first and a second thread to respective first and second resources upon the condition that;

(1) the first or second threads occupy predetermined positions within the respective first and second resource queues (i.e. the initial thread in a FIFO queue), and

(2) said first or second threads donot own any other resource;

(c) enqueuing (FIG. 4C, EnqWork) the first and second threads against ones of a set of available tasks in a predetermined order as each thread satisfies step (b), binding (FIG. 4C, GetWork) a first one of the available tasks to an initial thread (i.e. first or second thread) among the threads enqueued against the tasks, and, executing (FIG. 4B, InvokeLayer) a predetermined one of the function calls of the initial thread by the bound first task; and

(d) after execution in step (c), causing (FIG. 4B, DeqTie) the initial thread in step (c) to relinquish ownership of its resource, causing any next thread queued against said same resource and satisfying step (b) conditions (1) and (2) to become the owner of that resource and to be enqueued against tasks.

2. A method for synchronizing the dispatching of tasks from a CPU based multitasking operating system (OS) responsive to at least one demand placed by at least one application upon a CPU resident open system interface (OSI) type layered communications subsystem, said subsystem including callable resources associated with the layers and forming a thread of service requests (FIG. 4D, StartThread) to a set of resources counterpart to each demand, comprising the steps executed by said OSI subsystem of:

(a) enqueuing (FIG. 4B, EnqTie) each thread against each OSI subsystem resource named by a service request in said thread;

(b) securing resource ownership (FIG. 4B, DeqTie) to each thread among those threads enqueued against any one of the OSI subsystem resources by binding at least a first and a second thread to respective first and second OSI subsystem resources upon the condition that;

(2) the first or second threads occupy a predetermined position within the respective first and second resource queues (i.e. initial thread in a FIFO queue), and

(2) the first or second threads donot own any other OSI subsystem resource;

(c) enqueuing (FIG. 4C, EnqWork) the first and second threads against tasks as each thread satisfies step (b), binding (FIG. 4C, GetWork) a first one of the available tasks to an initial thread among the threads enqueued against the tasks, and, executing (FIG. 4B, InvokeLayer) a predetermined one of the service requests of the initial thread by the bound first task; and

(d) after execution, causing (FIG. 4B, DeqTie) the initial thread in step (c) to relinquish ownership of its OSI subsystem resource, causing any next thread queued against said same OSI subsystem resource and satisfying step (b) conditions (1) and (2) to become the resource owner and to be enqueued against tasks.

3. The method according to claim 2, wherein after a service request named in a thread has been executed, removing said service request from the thread.

4. In a system having a CPU including a multitasking operating system (OS) and a multitasking layered communications subsystem, a method for allocating tasks in the OS to threads of service requests generated by the layered communication sub-system as a function of service request (work) distribution,

each communication subsystem layer (FIG. 3) providing a unique set of functions for establishing an association between counterpart connection end-points, each layer being manifest by at least one control block, each control block being a state representation of the connection end-points in that layer, each control block further including indicia of a request to provide service,

each thread being denominated as a sequence of related service requests performed in a synchronous manner, each service request being associated with counterpart control block,

each control block further being split within a layer such that it depicts the adjacent layers to a connection within any given layer, each layer including at least one tie, each tie being the connection relation between split portions of the control block in the same layer, a tie group being an undirected graph of ties, only one thread executing per tie group at a time,

comprising the steps in nested iterative order of:

(a) starting at least a first and second thread (FIG. 4D, StartThread) responsive to counterpart communication subsystem oriented commands originated by at least a first application executing on said CPU or externally received by said subsystem;

(b) enqueuing (FIG. 4B, EnqTie) said first and second threads against counterpart tie groups named by each service request in each of said threads;

(c) securing tie group ownership (FIG. 4B, DeqTie) to said first and second threads as among any threads enqueued against any one of the tie groups upon the condition that;

(1) the first or second thread occupies a predetermined position within the counterpart tie group queue (i.e. the initial thread in a FIFO queue), and

(2) the first or second thread does not own any other tie group;

(d) enqueuing (FIG. 4C, EnqWork) the first and second threads against a set of available tasks upon each thread satisfying step (c), binding (FIG. 4C, GetWork) a first one of the available tasks to an initial thread among the threads enqueued against the tasks (FIG. 4A WorkQueue)

said binding occurring provided that there is no other thread in said queue of threads with a service request to a control block in the same tie group already bound to any task,

in the event that the first available thread violates the constraint of there being only one bound thread per tie group, binding of another available thread in the same tie group only after the first thread becomes free,

and, executing (FIG. 4B), InvokeLayer) a predetermined one of the service requests of the initial thread bound to said first task by the bound first task; and

(e) after execution, causing (FIG. 4B, DeqTie) the initial thread in step (d) to relinquish ownership of its tie group, causing a predetermined one threads queued against said same tie group satisfying step (a) conditions (1) and (2) to become the resource owner and to be enqueued against tasks.

5. In system having a CPU including a first and a second multitasking operating system (OS), means responsive to data originating from one or more applications either executing with said first OS or externally on another CPU for invoking threads of function calls (FIG. 4D, StartThread) by the second OS, an apparatus for synchronizing the dispatching of tasks from the first OS with counterpart threads dispatched from the second OS, said second OS including a plurality of callable layered resources, comprising:

(a) means including the second OS for enqueuing (FIG. 4B, EnqTie) each thread against each second OS resource, each second OS resource being named by a function call in said thread;

(b) means including the second OS for securing resource ownership (FIG. 4B, DeqTie) to each thread among those threads enqueued against any one of the second OS resources in step (a) by binding at least a first and a second thread to respective first and second resources upon the condition that;

(1) the first or second threads occupy predetermined positions within the respective first and second resource queues (i.e. the initial thread in a FIFO queue), and

(2) said first or second threads donot own any other resource;

(c) means including the second OS for enqueuing (FIG. 4C, EnqWork) the first and second threads against ones of a set of available tasks in a predetermined order as each thread satisfying step (b), for binding (FIG. 4C, GetWork) a first one of the available tasks to an initial thread (i.e. first or second thread) among the threads enqueued against the tasks, and, for executing (FIG. 4B, InvokeLayer) a predetermined one of the function calls of the initial thread by the bound first task; and

(d) means including the second OS responsive to the execution in step (c), for causing (FIG. 4B, DeqTie) the initial thread in step (c) to relinquish ownership of its resource, for causing any next thread queued against said same resource and satisfying step (b) conditions (1) and (2) to become the owner of that resource and to be enqueued against tasks.