Task scheduling in an event driven environment

Details Task scheduling in an event driven environment Task scheduling in an event driven environment

1999-03-02

2002-12-10

Courtenay, III, St. John (Department: 2151)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C709S241000

Reexamination Certificate

active

06493739

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of systems for distributed computing, communication and control and, more specifically, communication of information between devices in a distributed computing environment.
2. Description of the Related Art
In distributed computer systems it is necessary to provide for communication of information between nodes in the system. A number of methods for providing such communication are known in the art.
These methods include message passing techniques in which messages are passed, over a medium, from one node to another in a network. In message passing techniques, messages are built by a sender node and sent to one or more receiver nodes. The message is then parsed by the receiver node in order to correctly interpret the data. Message passing allows the advantage of passing large amounts of data in an expected format. Of course, over time the format of the message may be required to change to support new applications or features. This typically leads to compatibility issues between nodes on the network.
A second technique involves remote procedure calls in which a first node, requiring data which exists on a second node, calls a procedure executing on the second node where the data exists and requests the procedure to manipulate the data and provide a result to the first node. Remote procedure calls are typically suited to passing small amounts of data; however, a separate procedure call is typically required for each interchange. Therefore, it is likely in any networking system that over time additional procedure calls will be required in the network as new functions are carried out by the network. The addition of new procedure calls to certain nodes of the network leads to incompatibility between nodes, because the existing nodes do not know of and cannot execute the new remote procedure calls.
A third technique for communication of data in a network involves data sharing. Bal, Henri E., Steiner, Jennifer G., and Tanenbaum, Andrew S.,
Programming Languages for Distributed Computing Systems,
ACM Computing Surveys, Vol. 21, No. 3, September, 1989, pp. 261-322 (hereinafter Bal et al.) describes certain data sharing techniques. A discussion of data sharing may be found in the Bal et al. article at pages 280, et seq. (It should also be noted that a discussion of messaging may be found in the Bal et al. article at pages 276, et seq. along with a general overview of interprocess communication and synchronization.)
Bal et al. describes how parts of a distributed program can communicate and synchronize through use of shared data Bal et al. states that, if two processes have access to the same variable, communication can take place by one processor setting the variable and the other processor reading the variable. This communication is described as being allowed to take place whether the two processors are both running on a host where the shared data is stored and thus can manipulate the shared data directly, or if the processes are running on different hosts and access to the shared data is accomplished by sending a message to the host on which the shared data resides.
Two types of shared data are described: (1) shared logical variables; and (2) distributed data structures. Briefly, shared logical variables are described as facilitating a communication channel between processes through a “single-assignment” property. Initially, a shared logical variable is unbound, but once a value is assigned to the variable the variable is considered to be bound. An example is provided in which the three goals of conjunction:
goal_
1
(X, Y), goal_
2
(X, Y), and goal_
3
(X)
are assumed and solved in parallel by processes P
1
, P
2
and P
3
. The variable X is initially unbound and represents a communication channel between the three processes. If any of the processes binds X to a value, the other processes can use this value. Likewise, Y is a channel between P
1
and P
2
. Processes synchronize by suspending on unbound variables. For example, if Y is to be used to communicate information from P
1
to P
2
, then P
2
may suspend until Y is bound by P
1
.
It should be emphasized that in the described concept of shared logical variables, the term binding is used to describe a process of assigning a value to a variable. As will be seen below, the term binding is also used to describe the present invention, however, the meaning of the term is significantly different and the reader is cautioned to avoid confusion between the concepts represented by these two uses of this term. Generally, in the present invention, the term binding is used to indicate a process of associating a variable of one node with a variable of at least one other node. It is not necessary that the variable of either node has yet been assigned a data value.
Distributed data structures are data structures which may be manipulated simultaneously by several processes. In concept, all processes share one global memory termed “tuple space” or TS. The elements of TS are ordered sequences of values, similar to records in a language such as Pascal. Three operations may take place on TS: (1) “OUT” adds a tuple to TS; (2) “READ” reads a tuple from TS; and (3) “IN” reads a tuple from TS and deletes it from TS. Thus, in order to change the value of a tuple in TS it is necessary to first perform an IN operation, then to manipulate the data, and then perform an OUT operation. The requirement that a tuple must first be removed by the IN operation makes it possible to build distributed systems without conflict between accesses by the various processes.
Bal et al. contrasts distributed data structures with interprocess communication techniques noting that communication accomplished by distributed data structures is anonymous. A process reading a tuple from TS does not know or care which other process inserted the tuple. Further, a process executing an OUT does not specify which process the tuple is intended to be read by.
Bal et al. states that in concept distributed data structures utilizing the tuple space implement conceptually a shared memory, although in implementation a physical shared memory is not required. However, as can be seen, in a system utilizing such distributed data structures a single copy of the data is stored in tuple space whether or not such tuple space is implemented as a single physical shared memory. Separate copies of the data are not maintained for the various processes or on the various hosts. In fact, maintaining separate copies would lead to data conflict possibilities as the various nodes attempted to coordinate updates of the variable between the various process and hosts. Thus, the reason or requiring use of the IN command to delete a tuple before allowing manipulation of the data represented by the tuple.
The present invention discloses a networked communication system which is perhaps closest in certain concepts to the described distributed data structures. However, it can, of course, be appreciated that certain advantages may be gained from development of a system which utilizes certain features of distributed data structures while retaining flexibility in allowing multiple copies of a data value to be stored on the various nodes.
The present invention discloses certain improved programming language and data structure support for communication, sensing and control as may be used by nodes of the present invention. It is known in the art to allow for scheduling of tasks through use of a programming statement such as a “when” clause or the like. However, in known systems such tasks may only be scheduled to be executed on the occurrence of a predefined event such as may be defined by the compiler writer. Examples of such events typically include expiration of a timer or input pin state changes. Such known systems do not allow for definitions of events, other than such predefined events. It has been discovered that it is useful to provide for definition of events as any valid programming language statement which may be evalu

Affiliated with

Also associated with

Rating

Task scheduling in an event driven environment does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Task scheduling in an event driven environment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Task scheduling in an event driven environment will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2972216