Process synchronization utilizing semaphores
First Claim
1. Apparatus for enabling synchronization among events such as a completion of an asynchronous operation, an arrival of a message, an availability of a resource, an arrival of a process at a particular stage of execution, any kind of which will affect to be affected by a process presently or ultimately operating in a data processing system, said events occurring at different times in said data processing system, comprising in combination:
- a memory member adapted to have stored therein first, second and third queues of representations, respectively of the occurrences of first, second and third kind events, said first, second and third kind events being, respectively, message free events, message bearing events and resource requesting processes;
said memory member having stored therein first and second data elements, each of said data elements comprising;
a first field representing a maximum number of events which may be associated with said data element;
a second field representing a number of events currently associated with said data element; and
a third field representing a location of the first kind event representation in one of said three queues associates with said data element;
first testing means responsive to the occurrence of one of said first kind events and to the first and second storage fields of said first data element for generating a first signal when the algebraic value of the number represented by said second field is less than a predetermined value and said number is less in magnitude than the number represented by said first field;
first control means responsive to the occurrence of said first signal for inserting a representation of said one first kind event into said first queue, for decrementing the number represented by the second field of said first data element, and for modifying the third field of said first data element to point to the location in said first queue of said representation inserted thereinto;
second testing means responsive to the occurrence of one of said second kind events and to the first and second fields of said first data element for generating a second signal when the algebraic value of the number represented by said second field is not less than said predetermined value and said number is less in magnitude than the number represented by said first field;
second control means responsive to the occurrence of said second signal for inserting a representation of said one second kind event into said second queue, for incrementing the number represented by the second field of said first data element, and for modifying the third field of said first data element to point to the location in said second queue of said repesentation inserted thereinto; and
means for applying message free and message bearing events having occurrence representations stored respectively in said first and second queues to requesting processes.
0 Assignments
0 Petitions
Accused Products
Abstract
An information structure called a semaphore serves as a signalling mechanism in process synchronization. The semaphore is used to relate a process and an event which do not appear simultaneously. In accomplishing this, the semaphore is capable of storing the presence of events or resources waiting for processes or, alternatively, the presence of processes waiting for events or resources via a queue.
233 Citations
8 Claims
-
1. Apparatus for enabling synchronization among events such as a completion of an asynchronous operation, an arrival of a message, an availability of a resource, an arrival of a process at a particular stage of execution, any kind of which will affect to be affected by a process presently or ultimately operating in a data processing system, said events occurring at different times in said data processing system, comprising in combination:
-
a memory member adapted to have stored therein first, second and third queues of representations, respectively of the occurrences of first, second and third kind events, said first, second and third kind events being, respectively, message free events, message bearing events and resource requesting processes; said memory member having stored therein first and second data elements, each of said data elements comprising; a first field representing a maximum number of events which may be associated with said data element; a second field representing a number of events currently associated with said data element; and a third field representing a location of the first kind event representation in one of said three queues associates with said data element; first testing means responsive to the occurrence of one of said first kind events and to the first and second storage fields of said first data element for generating a first signal when the algebraic value of the number represented by said second field is less than a predetermined value and said number is less in magnitude than the number represented by said first field; first control means responsive to the occurrence of said first signal for inserting a representation of said one first kind event into said first queue, for decrementing the number represented by the second field of said first data element, and for modifying the third field of said first data element to point to the location in said first queue of said representation inserted thereinto; second testing means responsive to the occurrence of one of said second kind events and to the first and second fields of said first data element for generating a second signal when the algebraic value of the number represented by said second field is not less than said predetermined value and said number is less in magnitude than the number represented by said first field; second control means responsive to the occurrence of said second signal for inserting a representation of said one second kind event into said second queue, for incrementing the number represented by the second field of said first data element, and for modifying the third field of said first data element to point to the location in said second queue of said repesentation inserted thereinto; and means for applying message free and message bearing events having occurrence representations stored respectively in said first and second queues to requesting processes. - View Dependent Claims (2, 3, 4, 5)
-
-
6. Apparatus for enabling synchronization among events such as a completion of an asynchronous operation, an arrival of a message, an availability of a resource, an arrival of a process at a particular stage of execution, any kind of which will affect or be affected by a process presently or ultimately operating in a data processing system, said events occurring at different times in said data processing system, comprising in combination;
-
a memory member adapted to have stored therein first and second queues of representations, respectively, of occurrences of first and second kind events, said first and second kind events being, respectively, message free events and message bearing events; said memory member having stored therein a data element, said data element comprising; a first field representing the maximum number of representation of both kinds of events which may be associated with said data element; a second field representing the number of events currently associated with said data element; and a third field representing the location of the first representation stored in a queue associated with said data element; first testing means responsive to the occurrence of one of said first kind events and to the first and second fields of said data element for generating a first signal when the algebraic value of the number represented by said second field is less than a predetermined value and said number is less in magnitude than the number represented by said first field; first control means responsive to the occurrence of said first signal for inserting a representation of said one first kind event into said first queue, for decrementing the number represented by the second field of said data element, and for modifying the third field of said element to point to the location in said first queue of said representation inserted thereinto; second testing means responsive to the occurrence of one of said second kind events and to the first and second fields of said data element for generating a second signal when the algebraic value of the number represented by said second field is not less than said predetermined value and said number is less in magnitude than the number represented by said first field; second control means responsive to the occurrence of said second signal for inserting a representation of said one second kind event into said second queue, for incrementing the number represented by the second field of said data element, and for modifying the third field of said data element to point to the location in said second queue of said representation inserted thereinto; and means for applying message free and message bearing events having occurrence representations stored respectively in said first and second queues to requesting processes.
-
-
7. Apparatus for enabling synchronization between events that affect or are affected by processes presently or ultimately operating in a data processing system, said events occurring at different times in said data processing system, comprising in combination:
-
a memory member adapted to have stored therein a queue of representations of occurrences of message free events and message bearing events; said memory member having stored therein a data element, said data element comprising; a first field representing the maximum number of events which may be associated with said data element; a second field representing the number of representations of events currently associated with said data element; and a third field representing the location of the first representation in a queue associated with said data element; first testing means responsive to the occurrence of one of said message free events and to the first and second fields of said data element for generating a first signal when the algebraic value of the number represented by said second field is less than a predetermined value and said number is less in magnitude than the number represented by said first field; first control means responsive to the occurrence of said first signal for inserting a representation of said one message free event into said queue, for decrementing the number represented by the second field of said data element, and for modifying the third field of said data element to point to the location in said queue of said representation inserted thereinto; second testing means responsive to an occurrence of a message bearing event and to the first and second fields of said data element for generating a second signal when the algebraic value of the number represented by said second field is not less than said predetermined value; second control means responsive to the occurrence of said second signal for incrementing the number represented by the second field of said data element; and means for applying message free and message bearing events having occurrence representations stored respectively in said first and second queues to requesting processes. - View Dependent Claims (8)
-
Specification