Synchronization primitives - CAS

CAS (compare and swap) is a synchronization primitive to deal with race conditions as presented in Race conditions . This primitive checks whether a variable has the value previously read and in case it does, CAS changes the contents of that variable - all of this is applied atomically, i.e. no other thread can interrupt this set of actions. This is usually useful when reading a value, and we want to write the value changed, to see that the value has not changed since we have read it.

For example given the code:

P(){
   do {
1.   tmp = read(x)
2.   tmp = tmp+1
3. } while (! CAS (x, tmp, tmp+1));
}

This is very similar to the code in the previous post, but now we capture the case when someone has written some different value and prevents some undesirable schedules.

For instance, let's consider the following schedule:
A.1
B.1
B.2
B.3
A.2
A.3

In the previous post A.3 wrote in x without noticing if someone else had changed x's value in the meanwhile. Now, with the CAS statement, once B has written a new value, the CAS statement fails forcing A to read the updated value before writing it incremented by one. (which is what we would expect!)

Aspect-oriented Programming (AOP) - Pointcuts - 2

We have mentioned the call and execution pointcuts in the post Pointcuts - 1 .

There are several other useful pointcuts expressions, we will first describe static ones and then dynamic ones. Static ones are those that they can be analyzed at compilation time, and therefore, part of the weaving (applying the aspect at the correct place) is done statically, thus avoiding usual aspect overhead. Dynamic pointcuts expressions depend on the runtime state of the system. A certain joinpoint may match the pointcut at some point of time but not at another.

Some interesting static pointcut expressions (besides call and execution) are:

get/set (fieldPattern) do detect whenever a value read or written to a field (wildcards are allowed here too); 

initialization -> to capture constructors; 

within / withinCode -> to statically check if the pointcut is within a certain class or method name

Some interesting dynamic pointcut expressions are:

cflow(pointcut): captures any joinpoint within the execution flow of the pointcut. 

For example, if there is a pointcut: cflow (call(* *.foo()) and within foo() there is a call to bar(); then that call is within the execution flow of call(foo) therefore the advice with that pointcut will be activated. However, when bar is called within a stack trace where foo has not occurred, the matching advice will not be activated.

this, target, args: All this allow not only capturing dynamic information but also exposing it to be used within the advice. For instance, let's consider the pointcut

call(* *.foo()) && this(C)

This pointcut expresses any call to C where the call is done by an object of class C.

Moreover if we define the pointcut as follows:

pointcut p(C objC):call(* *.foo()) && this(objC)

we are saying the same as before but also saving the reference to the object calling foo in objC.

Similarly, with target we can save the reference of the targeted object, and with args, the arguments with which the call is being made.

Besides static and dynamic pointcut descriptors, more complex pointcuts can be obtained by boolean composition:

&& -> and among pointcuts

|| -> or among pointcut

! -> not pointcut

Race conditions

A race condition in parallel programs occurs when different schedules / interleavings may cause different results.
The most typical example is the following: let two threads A and B execute (each) the program P given by

P(){
1. tmp = read(x)
2. tmp = tmp+1
3. write(x,tmp) //write in x the value of tmp
}

This code is consistent with several formal representations of parallel programs where at each statement a shared variable is accessed only once. In particular, here we consider x to be the shared variable and each thread creates a temporal local variable tmp to increment it and then write it at the original location.

Now, if  the initial value of x is 0, and the schedule is A, B (i.e. first A executes all the lines, and then B), by the end x will contain the value 2 (one increment by A, another one by B)

However, in parallel programs, one of the threads may be preempted (interrupted) the other continues running, then returns.. so there are other possible execution orders for this code.
One of them is:
A.1 (A executes the first line)
B.1
B.2
B.3
A.2
A.3

what happens here when the initial value of  x is 0?
with A.1, tmp_A (tmp local to A) gets the value 0
with B.1, tmp_B also gets the value 0 (it has not been changed yet)
B.2, B.3 increments and writes the new value setting x with 1 (but tmp_A has not changed)
A.2 increments tmp_A (it was 0, now is 1)
A.3 writes this value in x

This causes the value of x by the end of this schedule to be 1.

Thus, this code (as is) is an example of a race condition. Usually synchronization primitives are used to avoid such problems, but I'll write more about these primitives later..

Aspect-oriented Programming (AOP) - Pointcuts - 1

So far we have talked very little about pointcuts, but there are several syntax keywords that allow capturing different joinpoints.

Here is the whole list: Pointcuts, but I will point out some that are very useful (and used):

call(MethodPattern): whenever a method is called. MethodPattern is an expression (containing wildcards) that may capture different sets. For instance public int C.m(String) is a method pattern capturing the public method m of class C that receives one argument of type String. We can also define the following * *.*(..) which represents, any method of any class of any type with any set of arguments. Something in the middle could be * Cl*.me*(String, ..) which captures methods (of any type) that begin with me, of classes that start with Cl and receive at least one String argument (as the first  argument).

execution (MethodPattern), is similar but represents when we are in the class of the method pattern. To observe the difference between call and execution let's consider the following example:

1. class MainClass {
2.   public static void main(){
3.      C o1 = new C();
4.      o1.m();
5.   }
6. }

1. class C {
2.   public void m(){
3.   }
4. }

the call pointcut matches the location at MainClass, line 4; while the execution pointcut matches the execution within C that is, between lines 2 and 3 of class C.

Aspect-oriented Programming (AOP) - Introduction - 2

In the previous post AOP - 1, I have started describing Aspect-Oriented Programming, that is, a paradigm that allows defining crosscutting concerns modularly. In particular, we have mentioned that it contains a query-like expression defining where the aspect should be applied, and the code representing the actual concern. In order to represent a crosscutting concern there may be several of such pieces of code, each called advice. The query expressing the locations is called pointcut and the actual locations that may match a pointcut are called joinpoints.
Each advice has a type: before, after or around. A before (or after) advice indicates that the code within the advice should be executed before (or after) the joinpoint matching the pointcut. An around advice allows changing the parameters of the original joinpoint, and even making the original call zero or more than once.
Some first (simple) examples are:
1)
before(): call(void *.m(..)){
  System.out.println("before calling m");
}

2)
after(): call(void *.m(..)){
  System.out.println("after calling m");
}

3)

void after(): call(void *.m(..)){
  System.out.println("before calling m");
  proceed();
  System.out.println("after calling m");
}

In the first example, before calling to any void method m (belonging to any class, with any set of arguments), the message "before calling m" is printed.
The second example is similar, but only prints the message after m has been called (and returned either successfully or because of an exception)
The third example surrounds the call with the two messages.

Aspect-oriented Programming (AOP) - Introduction - 1

In this post I will start writing a bit about Aspect-oriented programming, in a future post about aspect implementation in AspectJ, and I hope later explain about some ideas of combining formal methods with this paradigm.
I assume that you all know what object-oriented programming is, and in particular know some object-oriented language. Basically, we define classes from which we can instance objects, which are the fields and type of each instance of the class, and to which messages / methods the object responds and how.
However, when implementing an application there are crosscutting concerns that affect multiple objects, and get tangled in their implementation, and scattered along many objects [1]. Typical examples are logging, persistence, transaction management, gui updates. These are examples of aspects [2] applicable to multiple systems, but there could be aspects defined specifically for each application, when are the points updated in a game, which discounts to apply to a purchase, etc..
To represent this crosscutting concerns modularly aspects indicate where the particular code should be applied, and what should be do. For example, we could say "every time a public method is called, log it". This is expressed in a different module that looks like a class (but is an aspect), and the locations are expressed as a query. For example in AspectJ (an aspect-oriented extension for Java), that location is expressed as call(* public *(..)), i.e. call to a public method (first *: for any return type; second *: for any method name; ..: for any set of arguments).

References:
[1] Tarr, Peri, Harold Ossher, William Harrison, and Stanley M. Sutton Jr. "N degrees of separation: multi-dimensional separation of concerns." In Proceedings of the 21st international conference on Software engineering, pp. 107-119. ACM, 1999.
[2] Kiczales, Gregor, John Lamping, Anurag Mendhekar, Chris Maeda, Cristina Lopes, Jean-Marc Loingtier, and John Irwin. Aspect-oriented programming. Springer Berlin Heidelberg, 1997.