Aktör yapısına dayalı paralel programlama ortamının tasarımı ve gerçeklenmesi
Aktör yapısına dayalı paralel programlama ortamının tasarımı ve gerçeklenmesi
Dosyalar
Tarih
1992
Yazarlar
Kandemir, Mahmut Taylan
Süreli Yayın başlığı
Süreli Yayın ISSN
Cilt Başlığı
Yayınevi
Fen Bilimleri Enstitüsü
Özet
Çok görevlilik çalışmakta olan bir işlevden bir diğerinin ortasına ikisinin de durumlarını bozmadan geçmektir. Burada amaç aynı anda birden fazla olayın denetlenmesidir. Görev bıraktırmalı sistemlerde, görev düzenleyici o anda yapılan iş ne olursa olsun onu keserek başka bir görevi çalıştırabilir. Düzenleyici, elindeki görevlerin ne zaman ve hangi sırayla çalıştırılacağına da karar verir. Bu çalışmada asenkron mesaj aktarımına dayalı, dinamik görev oluşturmaya uygun bir dil olan ACT++'a ilişkin ilkeller C++ nesneye yönelik programlama dili kullanılarak gerçekleştirilmiştir.
Concurrent programming makes it possible to use a computer where many things need attention at the same time which may be people at terminals or temperatures in an industrial plant. A concurrent program specifies two or more sequential programs that may be executed concurrently as parallel processes. A concurrent program can be executed either by allowing processes to share one or more processors or by running each process on its own processor. The first approach is referred to as multiprogramming. The second one is referred to as multiprocessing if the processors share a common memory or as distributed processing if the processors are connected by a communications network. Hybrid approaches also exist -for example, processors in a distributed system are often multiprogrammed. Object oriented programming (OOP) on the other hand is a method of programming that seeks to mimic the way we form models of the world. To cope with the complexities of life, we have evolved a wonderful capacity to generalize, classify, and generate abstractions. Almost every noun in our vocabulary represents a class of objects sharing some set of attributes or behavioral traits. From the world of individual dogs, we distill an* abstract class called 'dog'. This allows us to develop and process ideas about canines without being distracted by the details concerning any particular dog. The OOP extensions in C++ exploit this natural tendency we have to classify and abstract things. Three main properties characterize an OOP language : Encapsulation : Combining a data structure with the functions (actions or methods) dedicated to manipulating the data. Encapsulation is achieved by means of new structuring and data- typing mechanism called 'class'. -vi- Inheritance : Building new, derived classes that inherit the data and functions from one or more previously- def ined base classes, while possibly redefining or adding new data and actions. This produces a hierarchy of classes. Polymorphisms : Giving an action one name or symbol that is shared up and down a class hierarchy, with each class in the hierarchy implementing the action in a way appropriate to itself. In object-oriented concurrent programming (OOCP), a problem is modeled as a set of cooperating objects and solved by these objects communicating with each other. This programming provides us with a higher level and more unified abstraction of objects and processes. By modelling a problem as a set of cooperating objects, we can obtain higher descriptivity and understandability. In OOCP objects are defined in terms of two main properties : 1. An object is the unit not only of protection but also of execution. 2. An object has its own computing facility. According to the first property, an object is a new module which encapsulates processes and the data which is accessed only by those processes. Last item indicates that an object can proceed with the computation by itself. From this, someone can say that object-oriented concurrent computing is a model by which all problems are described in terms of communicating objects. Embedded systems programming presents some interesting challenges. A typical application might involve juggling a variety of sampling, processing, control, and communication functions simultaneously on a very small system. Such applications are inherently parallel and are best implemented by small tasks working together. In preemptive multitasking, an interrupt timer periodically executes an executive program. The executive determines if the current task has been running too long, and if so forces a context switch to the next scheduled task. If the task still has time, it updates a counter and returns from interrupt. Because an interrupt can occur and force a context switch at any point in the program, the system must save and restore the processor's entire state. Resource sharing between tasks requires routines to lock and unlock common data structures. Further, operating system calls must be re-entrant (which Ms-Dos is not). Cooperative multitasking, on the other hand, has no executive overhead and does not rely on interrupts. Instead, when a task is ready to give up control, calls a routine (pause) which switches context to the next task. -vii- Because the point of switch is always the same, only the stack pointer and a few registers are saved and stored. This makes the context switch simple and potentially very fast. This sort of tasking greatly simplifies resource sharing since other tasks cannot sneak in during updating of common structures. System calls can be performed in any operating system because a context switch cannot occur unexpectedly during the call. But that is not a real multitasking. In implementing ACT++, preemptive method has been adopted. Critical regions, monitors, and path expressions are one outgrowth of semaphores; they all provide structured ways to control access to shared variables. A different outgrowth is 'message passing' which can be viewed as extending semaphores to convey data as well as to implement synchronization. When message passing is used for communication and synchronization processes send and receive messages instead of reading and writing shared variables. Communication is accomplished because a process, upon receiving a message, obtains values from some sender process. Synchronization is accomplished because a message can be received only after it has been sent, which constrains the order in which these two events can occur. A message is sent by executing: SEND expression. list TO destination. designator; The message contains the values of the expressions in 'expression. list' at the time send is executed. The 'destination. designator' gives the programmer to control over where the message goes, and hence over which statements can receive it. A message is received by executing : RECEIVE variable.list FROM source. designator; where 'variable.list' is a list of variables. The 'source.designator gives the programmer control over where the message came from, and hence over which statements could have send it. Receipt of a message causes, first, assignment of the values in the message to the variables in the 'variable list' and, second, subsequent destruction of the message. Designing message-passing primitives involves making choices about the form and semantics of these general commands. Taken together, the destination and source designators define a communications channel. Various schemes have been proposed for naming channels. Then simplest channel- naming scheme -viii- is for process names to serve as source and destination designators. That sort of naming is called 'direct naming'. Direct naming is easy to implement and to use. It makes it possible for a process to control the times at which it receives messages from each other processes. But one of the very important paradigms for process interaction is the client/server relationship. Some server processes render a service to some client processes. A client can request that a service be performed by sending a message to one of these servers. A server repeatedly receives a request for service from a client, performs that service, and (if necessary) returns a completion message to that client. Unfortunately, direct naming is not always well-suited for client/server interaction. Ideally, the receive in a server should allow receipt of a message from any client. If there is only one client, then direct naming will work well; the difficulties arise if there is more than one client because, at the very least, a receive would be required for each. Similarly, if there is more than one server (and all servers are identical), then the send in a client should produce a message that can be received by any server. Again, this cannot be accomplished easily by direct naming. A more sophisticated scheme for defining communications channels is based on the use of 'global names', sometimes called 'mail-boxes'. A mailbox can appear as the destination designator in any process 'send statements and as the source designator in any process 'receive statements. Thus messages sent to a given mail-box can be received by any process that executes a receive naming that mail box. As easily seen, this scheme is particularly well-suited for programming client/server interactions. A special case of mail- boxes, in which a mail-box name can appear as the source designator in receive statements in one process only, does not suffer any implementation difficulty. Such mail-boxes are often called as 'ports'. ACT++ is a concurrent OOP language being developed as a part of a research project on concurrent real time systems. The Actor model is a concurrent computation model in which computation is achieved by actors communicating via message passing. The model consists of five basic elements : actors, mail queues, messages, behaviors, and acquaintances. An actor is a self-contained active object. Interaction among actors can occur only through message passing. Each actor is associated with a unique mail queue, whose address serves as the IX- identifier of the actor. The messages send to actor are buffered by its mail queue. Messages buffered in a mail queue are read one at a time in a strict FIFO order. The behavior of an actor determines how the actor reacts to a request specified in the message processed. A behavior is defined by a code body called the behavior script. The script contains method definitions, and acquaintances. Acquaintances are the names of other actors *to which an actor can send messages. A behavior script corresponds to a class definition in other OOP languages while acquaintances correspond to instance variables. In processing a message, an actor can do three things: make new actors, send messages to actors, and specify a replacement behavior. Actors are dynamically produced at run-time as needed during the course of computation. A new actor is produced by the 'New' operation. The send operation is the primitive used for asynchronous message passing. A message consists of the address of the target actor, the name of the method to be invoked, and parameters for the method invocation. The last primitive operation is the specification of a replacement behavior. The 'become' operation is used for that. This operation requires a behavior script name and a list of acquaintances. The operation produces a thread. The newly produced thread is the current behavior of the actor. The replacement behavior determines how to handle the next unprocessed message. Since a thread can specify a replacement only once in its life, there is at most one behavior waiting for a message at any time. Concurrency in ACT++ comes from two sources: making a new actor and specification of a replacement behavior. The former results in inter - object concurrency, while the latter yields intra-object concurrency. Two kinds of objects are distinguished in ACT++, namely active objects and passive objects. An active objects proceeds concurrently with other objects. An active object, processing its own thread of control, is an actor. All objects that are not actors are passive objects. The invocation of a method of a passive object is performed using the thread of the requesting -x- object. Each object is an instance of some class. A class defines the properties of its instance objects. A class can inherit from another existing class by declaring itself as a subclass of existing class. A subclass can redefine, restrict, or extends the definition of its superclass. Active objects are instances of classes which are direct or indirect subclasses of a special class called ACTOR. Passive objects are instances of classes which are not subclasses of ACTOR. The language supports the primitive operations of the Agha's actor kernel language : New, Send and Become. Invoking methods of a passive object has the semantics of a function call. Invoking a method of an actor on the other hand, is via asynchronous message passing. Two types of messages are distinguished in ACT++, namely, request messages and reply messages. A request message is used for invoking a method while a reply message is used for delivery of the result of a method invocation. Two types of mail boxes are available to support these two different kinds of messages : 'MBox' and 'CBox'. A request message is used for sending a request to another actor. Request messages are buffered in the mail queue (MBox) of the receiving actor. An actor can refer to its own MBox using the pseudo variable 'self. Each behavior of actor can process only one request message in the MBox. If the sender of a request wants to receive the result of the method invocation, it may provide a CBox name in the request message. The 'reply' operation is used to transmit a reply message containing the result. The name of a CBox specified in a request message is called the reply destination. Technically, ACT++ is a language design which supports both class inheritance and the actor model of concurrency. As an expedient implementation strategy, C++ is used as the base language, extending it with the concurrency abstraction of the actor model. In ACT++, actors represent active objects. All non-actor objects are passive. A passive object represents a C++ object, which is local to a single active object. A shared object must be actor. Like passive objects, an actor class can inherit properties from- an existing actor class by defining itself to be a subclass of it. ACT++ distributes concurrency control into each method. The New operation for making a new actor MBox is a function which takes the name of an actor class as an argument. The operation is implemented as a conventional function without being a member of any class. The become operation is a friend member of ACTOR. The operation is overloaded to allow an actor to specify self as the replacement behavior. The send operation is implemented as a method of the class (struct) MBox. The -xi- syntax for sending a message is written as a series of stream like output operations (<<). For example, the following statement sends to an MBox called myMBox a message consisting of aMethod, replyDestination, ant two method invocation parameters, namely, firstinteger and second integer: myMBox << aMethod << replyDestination << firsinteger << second integer; An actor can read a request message from its MBox using the operation >> on the pseudo. variable self. Since the method name argument of a request message is used by the mail queue for selecting the method to invoke, the method name is not read by the >> operation. The >> operation is only used to read the values for the parameters of the method. Each method of a behaviour script contains with a >> statement. For example, contiuning the example above, the definition of a method aMethod of an actor myMBox uses the following for reading the message from the MBox: self >> first integer Arg >> second in tegerArg; The class CBox supports the 'reply' method for transmitting a reply message. The following statement sends a reply message containing 53 to the replyDestination. reply (53); Two other methods are provided by a CBox : In and receive. The method In() is used to check whether or not the reply has arrived in a CBox. The receive operation denoted by '»' reads a reply from a CBox. The use of these methods are illustrated in the following: if (myCBoxl.InO) then myCBoxl >> result else myCBox2 >> result; If myCBoxl has not yet received a reply, then myCBox2 is read, in which case the actor executing the statement may be blocked depending on the presence of a reply message in rayCBox2..
Concurrent programming makes it possible to use a computer where many things need attention at the same time which may be people at terminals or temperatures in an industrial plant. A concurrent program specifies two or more sequential programs that may be executed concurrently as parallel processes. A concurrent program can be executed either by allowing processes to share one or more processors or by running each process on its own processor. The first approach is referred to as multiprogramming. The second one is referred to as multiprocessing if the processors share a common memory or as distributed processing if the processors are connected by a communications network. Hybrid approaches also exist -for example, processors in a distributed system are often multiprogrammed. Object oriented programming (OOP) on the other hand is a method of programming that seeks to mimic the way we form models of the world. To cope with the complexities of life, we have evolved a wonderful capacity to generalize, classify, and generate abstractions. Almost every noun in our vocabulary represents a class of objects sharing some set of attributes or behavioral traits. From the world of individual dogs, we distill an* abstract class called 'dog'. This allows us to develop and process ideas about canines without being distracted by the details concerning any particular dog. The OOP extensions in C++ exploit this natural tendency we have to classify and abstract things. Three main properties characterize an OOP language : Encapsulation : Combining a data structure with the functions (actions or methods) dedicated to manipulating the data. Encapsulation is achieved by means of new structuring and data- typing mechanism called 'class'. -vi- Inheritance : Building new, derived classes that inherit the data and functions from one or more previously- def ined base classes, while possibly redefining or adding new data and actions. This produces a hierarchy of classes. Polymorphisms : Giving an action one name or symbol that is shared up and down a class hierarchy, with each class in the hierarchy implementing the action in a way appropriate to itself. In object-oriented concurrent programming (OOCP), a problem is modeled as a set of cooperating objects and solved by these objects communicating with each other. This programming provides us with a higher level and more unified abstraction of objects and processes. By modelling a problem as a set of cooperating objects, we can obtain higher descriptivity and understandability. In OOCP objects are defined in terms of two main properties : 1. An object is the unit not only of protection but also of execution. 2. An object has its own computing facility. According to the first property, an object is a new module which encapsulates processes and the data which is accessed only by those processes. Last item indicates that an object can proceed with the computation by itself. From this, someone can say that object-oriented concurrent computing is a model by which all problems are described in terms of communicating objects. Embedded systems programming presents some interesting challenges. A typical application might involve juggling a variety of sampling, processing, control, and communication functions simultaneously on a very small system. Such applications are inherently parallel and are best implemented by small tasks working together. In preemptive multitasking, an interrupt timer periodically executes an executive program. The executive determines if the current task has been running too long, and if so forces a context switch to the next scheduled task. If the task still has time, it updates a counter and returns from interrupt. Because an interrupt can occur and force a context switch at any point in the program, the system must save and restore the processor's entire state. Resource sharing between tasks requires routines to lock and unlock common data structures. Further, operating system calls must be re-entrant (which Ms-Dos is not). Cooperative multitasking, on the other hand, has no executive overhead and does not rely on interrupts. Instead, when a task is ready to give up control, calls a routine (pause) which switches context to the next task. -vii- Because the point of switch is always the same, only the stack pointer and a few registers are saved and stored. This makes the context switch simple and potentially very fast. This sort of tasking greatly simplifies resource sharing since other tasks cannot sneak in during updating of common structures. System calls can be performed in any operating system because a context switch cannot occur unexpectedly during the call. But that is not a real multitasking. In implementing ACT++, preemptive method has been adopted. Critical regions, monitors, and path expressions are one outgrowth of semaphores; they all provide structured ways to control access to shared variables. A different outgrowth is 'message passing' which can be viewed as extending semaphores to convey data as well as to implement synchronization. When message passing is used for communication and synchronization processes send and receive messages instead of reading and writing shared variables. Communication is accomplished because a process, upon receiving a message, obtains values from some sender process. Synchronization is accomplished because a message can be received only after it has been sent, which constrains the order in which these two events can occur. A message is sent by executing: SEND expression. list TO destination. designator; The message contains the values of the expressions in 'expression. list' at the time send is executed. The 'destination. designator' gives the programmer to control over where the message goes, and hence over which statements can receive it. A message is received by executing : RECEIVE variable.list FROM source. designator; where 'variable.list' is a list of variables. The 'source.designator gives the programmer control over where the message came from, and hence over which statements could have send it. Receipt of a message causes, first, assignment of the values in the message to the variables in the 'variable list' and, second, subsequent destruction of the message. Designing message-passing primitives involves making choices about the form and semantics of these general commands. Taken together, the destination and source designators define a communications channel. Various schemes have been proposed for naming channels. Then simplest channel- naming scheme -viii- is for process names to serve as source and destination designators. That sort of naming is called 'direct naming'. Direct naming is easy to implement and to use. It makes it possible for a process to control the times at which it receives messages from each other processes. But one of the very important paradigms for process interaction is the client/server relationship. Some server processes render a service to some client processes. A client can request that a service be performed by sending a message to one of these servers. A server repeatedly receives a request for service from a client, performs that service, and (if necessary) returns a completion message to that client. Unfortunately, direct naming is not always well-suited for client/server interaction. Ideally, the receive in a server should allow receipt of a message from any client. If there is only one client, then direct naming will work well; the difficulties arise if there is more than one client because, at the very least, a receive would be required for each. Similarly, if there is more than one server (and all servers are identical), then the send in a client should produce a message that can be received by any server. Again, this cannot be accomplished easily by direct naming. A more sophisticated scheme for defining communications channels is based on the use of 'global names', sometimes called 'mail-boxes'. A mailbox can appear as the destination designator in any process 'send statements and as the source designator in any process 'receive statements. Thus messages sent to a given mail-box can be received by any process that executes a receive naming that mail box. As easily seen, this scheme is particularly well-suited for programming client/server interactions. A special case of mail- boxes, in which a mail-box name can appear as the source designator in receive statements in one process only, does not suffer any implementation difficulty. Such mail-boxes are often called as 'ports'. ACT++ is a concurrent OOP language being developed as a part of a research project on concurrent real time systems. The Actor model is a concurrent computation model in which computation is achieved by actors communicating via message passing. The model consists of five basic elements : actors, mail queues, messages, behaviors, and acquaintances. An actor is a self-contained active object. Interaction among actors can occur only through message passing. Each actor is associated with a unique mail queue, whose address serves as the IX- identifier of the actor. The messages send to actor are buffered by its mail queue. Messages buffered in a mail queue are read one at a time in a strict FIFO order. The behavior of an actor determines how the actor reacts to a request specified in the message processed. A behavior is defined by a code body called the behavior script. The script contains method definitions, and acquaintances. Acquaintances are the names of other actors *to which an actor can send messages. A behavior script corresponds to a class definition in other OOP languages while acquaintances correspond to instance variables. In processing a message, an actor can do three things: make new actors, send messages to actors, and specify a replacement behavior. Actors are dynamically produced at run-time as needed during the course of computation. A new actor is produced by the 'New' operation. The send operation is the primitive used for asynchronous message passing. A message consists of the address of the target actor, the name of the method to be invoked, and parameters for the method invocation. The last primitive operation is the specification of a replacement behavior. The 'become' operation is used for that. This operation requires a behavior script name and a list of acquaintances. The operation produces a thread. The newly produced thread is the current behavior of the actor. The replacement behavior determines how to handle the next unprocessed message. Since a thread can specify a replacement only once in its life, there is at most one behavior waiting for a message at any time. Concurrency in ACT++ comes from two sources: making a new actor and specification of a replacement behavior. The former results in inter - object concurrency, while the latter yields intra-object concurrency. Two kinds of objects are distinguished in ACT++, namely active objects and passive objects. An active objects proceeds concurrently with other objects. An active object, processing its own thread of control, is an actor. All objects that are not actors are passive objects. The invocation of a method of a passive object is performed using the thread of the requesting -x- object. Each object is an instance of some class. A class defines the properties of its instance objects. A class can inherit from another existing class by declaring itself as a subclass of existing class. A subclass can redefine, restrict, or extends the definition of its superclass. Active objects are instances of classes which are direct or indirect subclasses of a special class called ACTOR. Passive objects are instances of classes which are not subclasses of ACTOR. The language supports the primitive operations of the Agha's actor kernel language : New, Send and Become. Invoking methods of a passive object has the semantics of a function call. Invoking a method of an actor on the other hand, is via asynchronous message passing. Two types of messages are distinguished in ACT++, namely, request messages and reply messages. A request message is used for invoking a method while a reply message is used for delivery of the result of a method invocation. Two types of mail boxes are available to support these two different kinds of messages : 'MBox' and 'CBox'. A request message is used for sending a request to another actor. Request messages are buffered in the mail queue (MBox) of the receiving actor. An actor can refer to its own MBox using the pseudo variable 'self. Each behavior of actor can process only one request message in the MBox. If the sender of a request wants to receive the result of the method invocation, it may provide a CBox name in the request message. The 'reply' operation is used to transmit a reply message containing the result. The name of a CBox specified in a request message is called the reply destination. Technically, ACT++ is a language design which supports both class inheritance and the actor model of concurrency. As an expedient implementation strategy, C++ is used as the base language, extending it with the concurrency abstraction of the actor model. In ACT++, actors represent active objects. All non-actor objects are passive. A passive object represents a C++ object, which is local to a single active object. A shared object must be actor. Like passive objects, an actor class can inherit properties from- an existing actor class by defining itself to be a subclass of it. ACT++ distributes concurrency control into each method. The New operation for making a new actor MBox is a function which takes the name of an actor class as an argument. The operation is implemented as a conventional function without being a member of any class. The become operation is a friend member of ACTOR. The operation is overloaded to allow an actor to specify self as the replacement behavior. The send operation is implemented as a method of the class (struct) MBox. The -xi- syntax for sending a message is written as a series of stream like output operations (<<). For example, the following statement sends to an MBox called myMBox a message consisting of aMethod, replyDestination, ant two method invocation parameters, namely, firstinteger and second integer: myMBox << aMethod << replyDestination << firsinteger << second integer; An actor can read a request message from its MBox using the operation >> on the pseudo. variable self. Since the method name argument of a request message is used by the mail queue for selecting the method to invoke, the method name is not read by the >> operation. The >> operation is only used to read the values for the parameters of the method. Each method of a behaviour script contains with a >> statement. For example, contiuning the example above, the definition of a method aMethod of an actor myMBox uses the following for reading the message from the MBox: self >> first integer Arg >> second in tegerArg; The class CBox supports the 'reply' method for transmitting a reply message. The following statement sends a reply message containing 53 to the replyDestination. reply (53); Two other methods are provided by a CBox : In and receive. The method In() is used to check whether or not the reply has arrived in a CBox. The receive operation denoted by '»' reads a reply from a CBox. The use of these methods are illustrated in the following: if (myCBoxl.InO) then myCBoxl >> result else myCBox2 >> result; If myCBoxl has not yet received a reply, then myCBox2 is read, in which case the actor executing the statement may be blocked depending on the presence of a reply message in rayCBox2..
Açıklama
Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 1992
Anahtar kelimeler
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol,
Paralel programlama,
Tasarım,
Computer Engineering and Computer Science and Control,
Parallel programs,
Design