Paper: Events can make sense | Frans Kaashoek and Maxwell Krohn - Academia.edu

1 Introduction

How to manage concurrency in network applications? There is much controversy about this issue. Event based system is a kind of method, it’s flexible and robust to load. But it has the problem called “stack ripping” which will complicate the code. As a result, it’s not easy to solve concurrency problems in events because of the property of being unreadable. To free events from the stack-ripping problem and retain the benefit of event-based, Tame is proposed. Tame is an event-based system, but it can be unified with thread in the same program. And it’s friendly to develop, read and debug just like the thread-based project. What’s more, Tame has excellent use of memory and great practical performance.

2 Using Tame

The core thought in Tame is to make the event-based project readable as the thread-based project by using a powerful abstraction. Tame introduces four important abstractions to implement this idea: Events Wait points、Rendezvous、Safe local variables

Events is a class which represents the abstraction of future occurrence. To create an event, using the function as: . And when an expected thing really happens, such as finishing reading from a file, the programmer should trigger the corresponding event by calling the trigger method as: . The type in trigger is a sequence of types or zero, and they should correspond to the declaration of event. With this mechanism, the event can pass information to the controller by this sequence when it occurs.

Wait points are written as in Tame. It means blocking the calling thread until one or more events are triggered. In general, any function containing a wait point needs to be marked with the keyword (Except using thread in Tame). And the blocking will cause it to directly return to its caller (it will be executed again when an event is triggered). This is a big difference between tamed function and thread. A blocked thread function’s caller only resumes when that callee function returns, but a tamed function’s caller resumes when the called function either returns or blocks. In that case, the advantage of Tame is that the entire call stack does not be blocked whenever a function blocks. And this is actually the benefit comes from event-based style, so the flexibility of codes can be increased.

Just using is a basic usage, and it can only choose to be triggered by the first event or the last event in statements. It’s not sufficient in many cases. A more flexible form is rendezvous, it
specifies a set of expected events relevant to a wait point. Such as:

{
rendezvous <> r;
statesment; // such as: event<int> e = mkevent(r, 0);
twait(r);
}

The here will wait for an event which is registered on the in the statement. Moreover, there is an argument called event ID. It can be used to differentiate events. And its corresponding definition is . The argument in is the event ID. Note that the definition of event should be in this situation. But because of the C++’s template machinery, there is no need to fill in the event ID when triggering that event. Using the event IDs in the event, tame will be very flexible. When differente vents are triggered, different resolutions can be done with this event ID. Such as the implementation of timeout or cancellation for many functions.

The last one is safe local variables. The variables who need to keep safe should be enclosed in a block. Then tame will preserve their values in a heap-allocated closure. Closure is a concept that is related to the control of the tamed function. Its lifetime is from the start of the tamed function to the exit of the function.

Besides, Tame can be unified with Thread in a program. It allows a simple transition between thread based code and event-based code. The basic idea of this feature is using event call to implement a thread call, and in turn, using thread call to implement an event call. An example of the former implementation is one event-based call that has but does not have a tamed mark. By this way, this event-based call will be blocked until the trigger arrives and then will return to its caller. Then with the help of function, a thread-based call can act like a tamed call as well.

There is an example of using Tame to solve the problem about “stack ripping”:

3 Implementing Tame

Tame is implemented as a source-to-source translator. The whole procedure to translate a tamed function could be looked at as four parts. First, the Tame will generate a new opaque C++ structure for each tamed function, and this structure couldn’t be accessed by programmers. Second, Tame will rewrite the variables in closure as references. Such as:

$𝑡𝑣𝑎𝑟𝑠 \{\ 𝑖𝑛𝑡\ 𝑖;\ \}\ \boldsymbol{to}\ 𝑖𝑛𝑡\ \&𝑖\ =\ 𝑐𝑙𝑜𝑠𝑢𝑟𝑒→𝑖$

Third, Tame rewrites points as return with different labels. Tame will add to the function one new entry and exit point per statement. Last, Tame will totally reconstruct the whole function. The preprocessor uses an extra “closure pointer” to indicate whether the function is called normally (the first time the function is called) or is reentered at a later wait point (the function may be called again when corresponding event trigger). In this process, Tame tries to avoid as much C++ parsing as possible at the cost of compiler integration. In addition, Tame also builds with the libraries and so it can be backwards compatible with legacy event code.

Tame provides a safe and automated memory management scheme, so the programmer does not need to worry about garbage collection. For the basic usage of , right program syntax is sufficient to ensure leakless memory management. But for the usage of , it’s much more difficult. Tame introduces three key invariants to make sure there is no memory leakage. But sometimes it’s hard to find out the violation of these invariants. Then Tame uses a careful reference-counting scheme to ensure these invariants. In a word, this reference-counting scheme uses strong reference to link controller of a function and corresponding closure, each event and its closure; use weak reference to link and its associated events, controller of the function and the . With these references, Tame can check whether there is memory leakage and cancel illegal operation.

4 Limitation of Tame

Even though Tame provides many powerful features, more work still needs to be done. Needing some
changes for Tame so that it can support true simultaneous threading. And Tame cannot interact well with
C++ exceptions. Moreover, there may be some cost about signature changes of a tamed function all the
way up the call stack in some situations, and it will influence the interfaces of export libraries.

5 Summary

In terms of practical effects in development, Tame is not just a source-to-source translator that can simplify the codes of event-based programs, but a powerful tool to integrate event-based and thread-based. More precisely, Tame provides a simple way to interchange the event-based codes and thread-based codes. If the assignment fits the event-based method better, but it was implemented by thread because of worrying about stack ripple. It costs very little to change it to event-based with the help of Tame now. And Tame will help programmers to do the memory management and debug which reduces the workload further.

However, Tame just unifies event and thread in terms of expressivity. It does not really solve the problem of thread. When there are too many requests to a thread-based system, the overhead of thread switching may be so high that it is unacceptable. Fortunately, there are some methods that can improve the performance of thread. Capriccio is a scalable thread package, and it uses sophisticated stack management to make one stack appear as many to provide superior performance in high concurrency. SEDA uses threads and events in concert to achieve flexible scheduling and intra-process concurrency. And all these techniques can cooperate with Tame to extend Tame from uniformity in expressivity to performance. Besides, Tame needs to refine the interaction with C++ exceptions, because exceptions can not be completely avoided.

Overall, with the use of Tame, programmers can be somehow liberated from complicated code development, memory management and program maintenance, especially in high concurrency scenarios. Programmers can focus on providing efficient and robust codes without the indecision about thread-based method or event-based method.