Implementation of Virtual Functions ------------------------------------ Approach 1: Lookup type info at runtime, and then call the function defined by that type. Problem: very expensive, require type info to be maintained at runtime Approach 2: Treat function members like data members: Allocate storage for them within the object. Put a pointer to the function in this location, and translate calls to the function to make an indirection through this field. Benefit: No need to maintain type info at runtime. Implementation of virtual methods is fast, as it requires only a dereferencing of the field that stores the pointer to member funtion to be invoked. Problem: Potentially lot of space is wasted for each object, even though all objects of the same class have identical values for the table. Approach 3: Introduce additional indirection into approach 2: Store a pointer to a table in the object, and this table holds the actual pointers to virtual functions. Now we use only one word of storage in each object. class B { int i ; char c ; virtual void g(); virtual void h() ; } B b1, b2; b1: +-------------+ | i | |-------------| | c | |-------------| | VMT ptr ---|----------------+ +-------------+ | | | | Virtual Method Table (VMT) | for class B | +-------------+ +---------------->|ptr to B's g | | |-------------| | |ptr to B's h | b2: | |-------------| +-------------+ | | i | | |-------------| | | c | | |-------------| | | VMT ptr ---|----------------+ +-------------+ Impact of subtype principle on Implementation of OO-Languages ------------------------------------------------------------- The subtype principle requires that any piece of code that operates on an object of type B can work "as is" when given an object belonging to a subclass of B. This implies that runtime representation used for objects of a subtype A must be compatible with those for objects of the base type B. Note that the way the fields of an object are accessed at runtime is using an offset from the start address for the object. For instance, b1.i will be accessed using an expression of the form (we use C-like syntax here) *(&b1+0) where 0 is the offset corresponding to the field i. Similarly, the field b1.c will be accessed using the expression *(&b1+1) (This assumes that addresses are given in terms of words, and a single word of memory can store an integer variable. If we use byte addressing instead, and if all integers require 4 bytes, then the access would use an expression of the form *(&b1+4).) Similarly, an invocation of the virtual member function b1.h() will be implemented at runtime using an instruction of the form: call *(*(&b1+2)+1) where: &b1+2 gives the location where the VMT ptr is located *(&b1+2) gives the value of the VMT ptr, which corresponds to the location of the VMT table *(&b1+2) + 1 yields the location within the VMT table where the pointer to virtual function h is stored. (Note that the pointer to h is stored at offset 1 from the base of VMT.) Viewed in light of the way member fields and operations are accessed, the subtype principle imposes the following constraint: any field of an object of type B must be stored at the same offset from the base of any object that belongs to a subtype of B the VMT ptr must be present at the same offset from the base of any object of type B or one of its subclasses the location of virtual function pointers within the VMT should remain the same for all virtual functions of B across all subclasses of B. As a result, we must use the following layout for an object of type A defined as follows: class A: public B { float f; void h(); // Redefines h, but reuses implementation of G from B; virtual void k(); } A a; a's layout: Virtual Method Table (VMT) +-------------+ for class A | i | +-------------+ |-------------| /----->|ptr to B's g | | c | / |-------------| |-------------| / |ptr to A's h | | VMT ptr ---|-----------------/ |-------------| |-------------| | ptr to A's k| | float f | +-------------+ +-------------+ Note that in order to satisfy the constraint that VMT ptr appear at the same position in objects of type A and B, it is necessary for the data field f in A to appear after the VMT field. A couple of other points: a) non-virtual functions are statically dispatched, so they do not appear in the VMT table b) when a virtual function f is NOT redefined in a subclass, the VMT table for that class is initialized with an entry to the function f defined its superclass. Parallel/Concurrent Programming Languages =========================================== Although the terms "parallel" and "concurrent" overlap in their meaning, a distinction is typically made between the two. In parallel programming, we start with a computation that can be done sequentially (typically, the computation is better understood in its sequential form than the parallel form), and parallelism is a tool that is employed to reduce runtime. This is necessary especially for long-running computations, such as those for weather prediction. In concurrent programming, parallelism is an inherent part of the computation. Example: you may be accessing your bank account to withdraw some cash at an ATM. At the same time, your employer may be depositing your paycheck electronically into your account. In general, there is no way to ensure that these two actions happen sequentially. Thus, in concurrent systems, we are dealing with "autonomous agents" that are initiating actions (largely) independent of each other. We will study only concurrent languages from here on. The central issues in concurrent languages are: (a) regulating access to shared resources in the presence of contention (b) synchronization among multiple agents Models of concurrent computation -------------------------------- Two main paradigms exist: a) message-passing paradigm b) shared-memory paradigm Usually, the choice of which paradigm to use is dictated by the problem. For instance, in the above example, the ATM needs to communicate with the bank through message passing, since the they are at different geographic locations. Similarly, your employers payroll system needs to use message passing paradigm to communicate with the bank. Within the bank, there must be agents that receive these requests (withdraw or deposit) and update your account. Typically, such an agent will take the form of a computation thread on your bank's computer system. The threads performing the deposit and withdraw operations need to access and modify your account info --- thus they "communicate" via shared memory. Message passing paradigm: In this paradigm, the agents communicate strict through messages --- they do not share common variables or storage. Message exchange typically takes place over "channels." Message passing paradigms simplify problems that arise in concurrent computation by reducing (or eliminating) contentions: the only resources that are shared are the channels; and even here, one can minimize contention by permitting only one reader on a channel, although multiple writers may write on the same channel. (This restriction regarding readers and writers holds for current message passing systems, such as those based on TCP/IP suite of protocols.) Message passing paradigm is characterized by the operations for sending and receiving messages. The send operation is typically (a) asynchronous, i.e., the completion of the send operation does not mean that the recipient has received the message (b) non-blocking, i.e., the send operation can complete even before a message is actually sent out to the receiver, or the receiver acknowledges the receipt of the message Of course, in some applications, it may be useful to have synchronous communication, where the send operation blocks until a receiver receives the message. In addition, the operation may need to block if there is no space to store the message. Receive operation is typically blocking, i.e., if no message is available, the agent (which can be a process or a thread) performing the receive operation is suspended. It will be restarted when a message arrives. In some instances, however, a non-blocking send operation may be more suitable. Shared-memory paradigm: In this paradigm, the agents share some or all of their memory. Thus, contentions may arise in the access to shared memory. Unless handled carefully, these contentions can lead to unexpected errors. For instance, consider two concurrent threads, one performing a withdraw operation on your account, while the other one performs a deposit operation. The first opearation may consist of a statement of the form: account.balance = account.balance - amountWithdrawn while the deposit operation may execute a statement of the form: account.balance = account.balance + amountDeposited. For the sake of concreteness, assume that the initial balance in the account is $100, and that there is a deposit of $20 and a withdrawal of $50. It is possible for the following sequence of operations to take place: Thread 1 reads account.balance Thread 2 reads account.balance Thread 1 computes balance - amountWithdrawn and updates account Thread 2 computes balance + amountDeposited and updates the account. Now note that the final balance will be initialBalance+amountDeposited instead of initialBalance-amountWithdrawn+amountDeposited.