Date: 14 Nov 94 23:06:00 GMT From: psrc@pegasus.att.com (Paul S R Chisholm) To: Patterns Subject: PATTERN: Guaranteed Termination (immediate/deferred/delegated) (We're making something that currently works inter-process, work inter- processor. This pattern leaped off the page at me!) Problem: Make sure some action gets terminated, whether or not it can be terminated immediately. Example 1: Consider a distributed server. The local object representing the server has some local resources, which may or may not be immediately available, and some non-local resources, which have significant response latency. Example 2: Consider a C or C++ function that's passed a pointer. The function is expected to "consume" the pointed-to object, deleting it when done. (This is not just a problem of memory leaks, but a larger issue of termination semantics. A C function might be passed a FILE pointer; the file may be used for a while for logging, but needs to be closed. On the other hand, this is a *constant* issue when avoiding memory leaks in C++ container classes that contain pointers.) Context: There is some action with a life cycle. It must be guaranteed to reach a valid end state. Often one talks about some object which must be "consumed" or "closed" or "finished." Termination must be guaranteed long before it happens. Solution: By the end of the method or function that accepts the action, EXACTLY ONE of three things must have happened: (1) The action must be "immediately" terminated. (2) The action must be "deferred" by the object, such that the accepting object accepts the responsibility to eventually terminate the action. (3) The action's termination must be "delegated" to some other object. Example 1: If a local resource is available, it satisfies the request. If no local resource is available, the request is queued. If a remote resource is appropriate, the request is passed on to a Proxy, which guarantees to satisfy the request. Example 2a: The sub-problem of C++ container classes is a classic. There are three or four design approaches: o The container can copy the pointed-to object (see clone() or deepCopy or Prototype); it deletes the copy when asked, or when the container is deleted. o The container can "consume" the pointer; the container now controls deletion. (Any pointers that exist outside the container may dangle at the container's descretion!) o The object can "remember" what containers it's in; if the object is destroyed, it tells the container, and vice versa. o Or the container can promise it won't last any longer than the objects it contains pointers to. That's two cases different cases of delegation, one that goes beyond the context of this pattern, and one bug waiting to happen. . . .-) Example 2b: Consider a C++ object that is passed a pointer to something, perhaps in its constructor, perhaps not. It may "consume" the pointed-to object. It may store the pointer. In that case: o the object may delete and zero the pointer during its own life cycle o the object may pass the pointer to some other object, and zero out its own copy o the object deletes the pointer in its own destructor (no problem if the pointer is zero). Resulting context: The deferred and delegated sub-solutions result in a context for Guaranteed Termination to be applied again! Date: Tue, 15 Nov 1994 14:30:43 -0600 To: psrc@pegasus.att.com (Paul S R Chisholm), Patterns From: johnson@cs.uiuc.edu (Ralph E. Johnson) Subject: Re: PATTERN: Guaranteed Termination (immediate/deferred/delegated) Although it is been some time since I have studied temporal logic, proving that something will eventually happen is a temporal logic problem. Maybe someone like Doug Lea will recast the pattern in the mold of temporal logic. I didn't realize that manual deallocation of memory required temporal logic. No wonder it is so tricky! -Ralph Johnson From: psrc@pegasus.att.com (Paul S R Chisholm) To: dl@g.oswego.edu (Doug Lea), johnson@cs.uiuc.edu (Ralph Johnson) Date: Wed, 16 Nov 1994 14:02 EST Subject: Re: PATTERN: Guaranteed Termination Ralph writes: > Maybe someone like Doug Lea will recast the pattern in > the mold of temporal logic. I didn't realize that manual deallocation > of memory required temporal logic. No wonder it is so tricky! A big part of good design is to make it un-tricky. As both Doug and I have pointed out, this is *not* restricted to "manual" memory management. (Certainly it's a problem that needs to be solved more often with manual rather than automatic deallocation.) Doug, I haven't read all your possible solutions carefully yet, but I *LIKE* the pattern! Meta-issue: Both versions of the pattern list multiple solutions. IMHO, this feels different than what "a single pattern" usually is, but it's clearly not a language. Something to think about the next time I have trouble falling asleep. --Paul Date: Fri, 18 Nov 94 01:01 GMT From: rdavies@cix.compulink.co.uk (Robin Davies) Subject: Re: PATTERN: Guaranteed Termination (immediate/deferred/delegated) To: patterns@cs.uiuc.edu, rdavies@cix.compulink.co.uk Reply-To: rdavies@cix.compulink.co.uk In-Reply-To: <9411142305.AA14590@ig1.att.att.com> I posted a guaranteed termination pattern to the mailing list somewhile back - about 6 months ago, which I refered to as the 'Poison' pattern. It was a very anthropomorphic adaptation of Dijkstra's Distributed Termination Detection algorithm. In brief the way it works is something like: A number of processing nodes (objects, machines etc)are connected together to form some kind of 'processing surface'. Each node in the surface connects and talks to each of its neighbours, and each node work asynchronously and independantly from its neighbours. The problem is to terminate all the nodes in some logical, non-catastrophic and orderly manner. If nodes are terminated too quickly they cause communication blockages in the system (at least in a CSP view of the system) and the whole system hangs, leaving nodes in a random state of quiescence. The solution is to send 'Poison' into the system, which taints each node as it passes through the system. The poison, however, does not act immediately and allows a node to propogate poison onto to all it's neighbours. The poisoned node then goes into a 'quite' state until it receives messages from all its neighbours confirming they've been poisoned too. At that stage a node will then know that it will no longer be apart of any communications path in the system and it can die gracefully.There are many other variations on the theme, frequently white and blck tokens being passed around rings are used to demonstrate the example, and I've heard of a banking scenario with credits and debits as well. I like the poison example because it has quite an intuative feel to it when you start to think about the problem. When I posted the pattern originally it was in response to some dialog regarding exception handling patterns(I think at least Grady Booch and Frank Buschmann were involved in the original exception handling patterns). The exception handling patterns mentioned exhibited other 'tighter' forms of coordinated behavour and control of knowledge in a system (like 'god objects') to control the 'group' behaviour of the objects.One of characteristic features of the Poison (and other termination) patterns is to do with the distriuted locus of control and state in the problem domain. I too feel that a pattern 'leaps' off the page at me, but primarily because the problem concerns objects in the system which require some strong cohesive and coordinated behaviour to achieve some primary goal, where that behaviour is intrinsically not related to the general behavour of the individual objects involved. This notion of decentralisation and non-deterministic behaviour surrounds us everywhere and we as humans are very used to dealing with it in our everyday life. To me patterns are an expression of the very intuative behaviours that we use to control this random world we live in. Patterns tend to put 'causality' back into a system where objects need to confined and constrained to achieve synergy with one another(or as a group). Unfortunely the right type of pattern to use is not always obvious and the wrong choices may have some undesirable side effects(just as in real life!!). Robin Davies Ford Motor Company 1/125 Eagle Way Brentwood, Essex UK Date: Wed, 16 Nov 1994 10:38:55 +0500 From: dl@g.oswego.edu (Doug Lea) To: patterns@cs.uiuc.edu Cc: psrc@pegasus.att.com, johnson@cs.uiuc.edu In-Reply-To: <199411152032.AA04906@hal.cs.uiuc.edu> (johnson@cs.uiuc.edu) Subject: Re: PATTERN: Guaranteed Termination (immediate/deferred/delegated) > Maybe someone like Doug Lea will recast the pattern in > the mold of temporal logic. I didn't realize that manual deallocation > of memory required temporal logic. No wonder it is so tricky! Thanks for the prodding. I do think this is amenable to the (mostly) temporal logic based distributed object protocol stuff I've been doing. (Anyone interested can ftp g.oswego.edu/pub/papers/psl.ps). But I'll avoid most of the formalisms, and instead recast this in an only slightly more abstract setting. Unfortunately, this abstraction makes the pattern too general and unfocussed, but here goes: > Context: There is some action with a life cycle. It must be > guaranteed to reach a valid end state. Often one talks about some > object which must be "consumed" or "closed" or "finished." Termination > must be guaranteed long before it happens. > > Problem: Make sure some action gets terminated, whether or not it can > be terminated immediately. Generalized: Context: There are two SETS of actions, call them B and E, where any action in B must be followed by one in E. Actions in B either return or accept a handle (reference, id, pointer, etc) argument, h, that is a required argument or message target of those actions in set E. Any number of a third set M of actions using handle h are allowed between those in B and E, but not otherwise. Examples: C++ objects: B = new, E = delete Transactions: B = beginTransaction, E = {commit, abort} Locking: B = lock, E = release Unix Files: B = {open, dup, ...}, E = close CORBA Objrefs: B = {create, duplicate}, E = release Problem: How do you ensure that this happens right? That is: * exactly one B-action occurs before all M-actions * exactly one E-action occurs after all M-actions Forces: * When multiple objects must invoke the actions in B, M, E, and the actions in set M are unknown in advance, ensuring that only legal B-M-E traces occur is a non-local, dynamic problem requiring some kind of multi-object protocols, policies, or conventions. In the worst case, tracking a given resource can become a global, system-wide problem. * An E-action for handle h may be required before some other B-action for some other handle h'. For example, in the case where actions in E release resources (memory, files, etc) they must be performed soon enough to allow new allocations. * You'd like to minimize the overhead associated with all this. * You'd like to minimize error-proneness, preferring simple conventions that do not depend on special actions being performed by a large number of objects. * You'd like to minimize the total number of associated policies and mechanisms adopted in a system. Solutions: There doesn't seem to be a general solution that is always optimal with respect to these forces. There are a number of alternatives that work in special contexts though. Thus the only solution I know is similar to Paul's: You should adopt a small, fixed set of policies and mechanisms that span across all objects involved in the associated actions. Possibilities include: Hard-coded Fixed Sequences: When the entire sequence of actions in B, M, E is known in advance (even when occurring across multiple objects), or when there is a designated `last' operation in M, then hard-wire the entire sequence. Sometimes, even when not immediately apparent in a design, these can be found (at great effort) via static analysis of the system, determining all usage dependencies, and associating the E-action with the final M-action. Examples: (1) A set of objects arrange to open a file, read exactly three inputs, then close it. (2) The object that hits an EOF on an open read-only file closes it. GC: Create a privileged infrastructure mechanism that can detect when no further M-actions are possible because handle h is not possessed by any other live object. This is the closest to an optimal solution, but applies only when (1) unreachability is the enabling condition for E-actions, and (2) dynamic reachability analysis is feasible. Single Object Responsibility: Establish the policy that the object, S, that performs a B-action on h is always the one that ultimately performs the E-action. All other objects receiving handle h from S in must also adopt the policy that they only perform M-actions on h before S performs the E-action. One way to help ensure this is for all objects receiving procedural message o->p(h) to never perform M-actions on h after returning control (i.e., to never store the handle for later use). Examples: (1) Block structuring: Locally stack-allocated objects in C++. (2) `By-value' contained subobjects in C++ Cascades: Special case of block structuring where an E-action in the designated object leads to E-Actions of others it is responsible for. Examples: (1) A delete of a repository-style container causes deletion of all its elements; (2) A transaction commit commits all of its nested transactions. (3) Killing a Unix process frees all of its resources. Pure Consumption: Any object receiving handle h is required to perform an E-action on it after using it for local M-actions. If needed, another duplicative B-action may be performed (resulting in a different handle, h') to propagate it. Examples: (1) `By-value' (by-copy) argument passing. (2) `Linear' protocols. (See papers by Henry Baker in SIGPLAN Notices in the past year or so.) Conditional Consumption: Establish a way to tag handle arguments controlling whether receivers should invoke an action in E after they have performed all local M actions. Examples: (1) In the Spring operating system, a handle argument can be qualified with ``consume'', meaning that the receiver should perform an E-action after using h. [No, I can't find a reference for this.] (2) In the CORBA IDL->C++ mapping, some data-objects carry bits indicating whether receivers must arrange deletion. Overridable Conventions: Establish one or more default policies, but adopt mechanisms to dynamically override them. Examples: (1) Use consumption-only, but also allow `keepalive' actions such as incrementing a reference count, and local termination actions such as decrementing a reference count and performing the action in E only if so indicated. (2) Use consumption-only, but do not actually consume if the handle is passed to another object. (This is `delegation' in Paul's version.) (3) Use GC, but also allow explicit invocations of actions in E to ensure timely resource release in the case of fixed sequences. (4) Use cascade, but record those instances of elements that should not be deleted (because of some other policy or conventions.) (5) Use single-responsibility, but add a protocol that can be initiated by any second object that allows responsibility to be transfered to it, thus disabling E-actions in the original object. (6) Use single-responsibility, but add pre-emptive protocols to perform E-Actions (along with associated recovery mechanisms) when an E-Action has not occurred and another B-Action depending on it is required. For example, pre-emptive lock-breaking. Hoping that others can improve this! -Doug