text:
|Publication number
|Publication type
|Application number
|Publication date
|Jan 11, 2011
|Filing date
|Sep 28, 2007
|Priority date
|Sep 24, 2002
|Fee status
|Also published as
|Publication number
|Nir N. Shavit, Mark S. Moir, Victor M. Luchangco
|Original Assignee
|Oracle America, Inc.
|Export Citation
|BiBTeX, EndNote, RefMan
|Patent Citations (37), Non-Patent Citations (47), Referenced by (2), Classifications (20), Legal Events (1)
|External Links: USPTO, USPTO Assignment, Espacenet
This application is a divisional of U.S. application Ser. No. 10/670,495, filed Sep. 24, 2003 now U.S. Pat. No. 7,293,143, which claims priority, under 35 U.S.C. �119(e), of U.S. Provisional Application No. 60/413,231, filed 24 Sep. 2002, naming Nir Shavit, Mark S. Moir, Victor Luchangco as inventors.
1. Field of the Invention
The present invention relates generally to coordination amongst execution sequences in a multiprocessor computer, and more particularly, to techniques for facilitating implementations of concurrent data structures and/or programs.
2. Description of the Related Art
Interest in atomic multi-location synchronization operations dates back at least to the Motorola MC68030 chip, which supported a double-compare-and-swap operation (DCAS). See generally, Motorola, MC68030 User's Manual, Prentice-Hall (1989). A DCAS operation generalizes a compare-and-swap (CAS) to allow atomic access to two locations. DCAS has also been the subject of recent research. See e.g., O. Agesen, D. Detlefs, C. Flood, A. Garthwaite, P. Martin, M. Moir, N. Shavit, and G. Steele, DCAS-based Concurrent Deques, Theory of Computing Systems, 35:349-386 (2002); D. Detlefs, P. Martin, M. Moir, and G. Steele, Lock-free Reference Counting, Distributed Computing, 15(4):255-271 (2002); and M. Greenwald, Non-Blocking Synchronization and System, Design, Ph.D. Thesis, Stanford University Technical Report STAN-CS-TR-00-1624 (1999).
In general, the implementation of concurrent data structures is much easier if one can apply atomic operations to multiple non-adjacent memory locations. However, despite the early MC68030 support for DCAS and despite some research interest multi-location synchronization, current processor architectures, by and large, support atomic operations only on small, contiguous regions of memory (such as a single or double word).
As a result, the current literature offers two extremes of nonblocking software synchronization support for concurrent data structure design: intricate designs of specific structures based on single-location operations such as compare-and-swap (CAS), and general-purpose multi-location transactional memory implementations. While the former are sometimes efficient, they are invariably hard to extend and generalize. The latter are flexible and general, but typically costly.
In an early paper, Herlihy and Moss described transactional memory, a more general transactional approach where synchronization operations are executed as optimistic atomic transactions in hardware. See M. Herlihy and J. E. B. Moss, Transactional Memory Architectural Support for Lock-free Data Structures, In Proc. 20th Annual International Symposium on Computer Architecture (1993).
Barnes proposed a software implementation of a K-location read-modify-write. See e.g., G. Barnes, A Method for Implementing Lock-free Shared Data Structures, In Proc. 5th ACM Symposium on Parallel Algorithms and Architectures, pp. 261-270 (1993). That implementation, as well as those of others (see e.g., J. Turek, D. Shasha, and S. Prakash, Locking without Blocking: Making Lock-based Concurrent Data Structure Algorithms Nonblocking, In Proc. 11th ACM Symposium on Principles of Database Systems, pp. 212-222 (1992); A. Israeli and L. Rappoport, Disjoint-Access-Parallel Implementations of Strong Shared Memory Primitives, In Proc. 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 151-160 (1994)) was based on a cooperative method where threads recursively help all other threads until an operation completes. Unfortunately, this method introduces significant overhead as redundant "helping" threads do the work of other threads on unrelated locations because a chain of dependencies among operations exists.
Shavit and Touitou coined the term software transactional memory (STM) and presented the first lock-free implementation of an atomic multi-location transaction that avoided redundant "helping" in the common case, and thus significantly outperformed other lock-free algorithms. See N. Shavit and D. Touitou, Software Transactional Memory, Distributed Computing, 10(2):99-116 (1997). However, the described formulation of STM was restricted to "static" transactions, in which the set of memory locations to be accessed was known in advance.
Moir, Luchangco and Herlihy have described an obstruction-free implementation of a general STM that supports "dynamic" multi-location transactions. See commonly-owned, co-pending U.S. patent application Ser. No. 10/621,072, entitled "SOFTWARE TRANSACTIONAL MEMORY FOR DYNAMICALLY SIZABLE SHARED DATA STRUCTURES" filed 16 Jul. 2003 naming Mark S. Moir, Victor Luchangco and Maurice Herlihy as inventors. Moir, Luchangco and Herlihy have also described an obstruction-free implementation of a multi-location compare-and-swap (KCAS) operation, i.e., a k-location compare-and-swap on non-adjacent locations. See commonly-owned, co-pending U.S. patent application Ser. No. 10/620,747, entitled "OBSTRUCTION-FREE MECHANISM FOR ATOMIC UPDATE OF MULTIPLE NON-CONTIGUOUS LOCATIONS IN SHARED MEMORY" filed 16 Jul. 2003 naming Mark S. Moir, Victor Luchangco and Maurice Herlihy as inventors.
While such obstruction-free implementations can avoid helping altogether, thereby reducing the algorithm complexity of the algorithm and eliminating associated overheads, further reductions are desired. Indeed, the strong semantics of the aforementioned techniques, e.g., full multi-location transaction support, generally come at a cost. Further, full multi-location transaction support may be overkill for some important software applications such as linked-list manipulations. What is needed is reasonably efficient, though potentially-weaker, multi-location operations that are general enough to reduce the design complexities of algorithms based on CAS alone.
We have developed an obstruction-free implementation of an atomic k-location-compare single-swap (KCSS) operation. Amongst other things, KCSS allows for simple nonblocking manipulation of linked data structures by overcoming a key algorithmic difficulty in their design: i.e., making sure that while a pointer is being manipulated, neighboring parts of the data structure remain unchanged. Our implementation is efficient in the typical uncontended case. For example, in some realizations, a successful k-location KCSS operation employs only two CAS operations, two stores, and 2 k noncached loads when there is no contention. Our techniques are supportable using a variety of single-location atomic read-modify-write operations, such as CAS, LL/SC, etc. Accordingly, we believe that our results lend themselves to efficient and flexible nonblocking manipulations of list-based data structures using synchronization mechanisms available on many current processor architectures. Finally, while KCSS operation semantics provide a useful descriptive context for our techniques, these techniques apply more generally to transactions that read multiple locations but modify only a single location.
In addition, as a building block for some implementations of our techniques, we have developed a mechanism for emulating load-linked (LL) and store-conditional (SC) operations for use in an LL/SC synchronization construct. One interesting exploitation is to provide LL/SC synchronization in a processor that does not directly support load-linked and store-conditional operations. For example, our techniques may be used to provide emulation for LL/SC synchronization (e.g., to support data structures and software designed for LL/SC synchronization) on a processor architecture that supports CAS operations. Alternatively, our techniques may be employed to provide LL/SC synchronization with stronger semantics than provided by the LL and SC operations directly supported by a particular processor.
The present invention may be better understood, and its numerous objects, features, and advantages made apparent to those skilled in the art by referencing the accompanying drawings.
The use of the same reference symbols in different drawings indicates similar or identical items.
A shared data structure is a collection of data that can be accessed using an associated set of operations. A traditional way to implement a shared data structure is to use mutual exclusion (locks) to ensure that multiple operations do not concurrently access (the same part of) the data structure concurrently. This approach has many disadvantages, as discussed in numerous papers in the literature. A significant amount of research over the last decade or so has focused on designing nonblocking shared data structures, which preclude the use of locks and thereby avoid their associated disadvantages.
Typically, two nonblocking conditions, lock-freedom and wait-freedom, have been considered in the literature. In this description, we focus on a new nonblocking condition, obstruction-freedom, that we now define, in part, through contrast with the more conventionally understood nonblocking conditions.
Lock-freedom: An implementation of an operation is lock-free if after a finite number of steps of any execution of that operation, some operation execution completes (irrespective of the timing behavior of any concurrent operation executions).
Wait-freedom: An implementation of an operation is wait-free if after a finite number of steps of any execution of that operation, that operation execution completes (irrespective of the timing behavior of any concurrent operation executions).
A shared data structure is lock-free or wait-free if all its operations are lock-free or wait-free respectively. Much of the difficulty associated with designing lock-free and wait-free shared data structures is that when concurrent operations interfere with each other, we must ensure that at least one of them makes progress (all of them, in the wait-free case). Obstruction-freedom relaxes this requirement. We explain in the next section why obstruction-freedom is a useful property despite its weaker progress guarantees.
Obstruction-freedom: An implementation of an operation is obstruction-free if every operation execution that executes in isolation after some point completes after a finite number of steps.
Observe that all three properties preclude the use of locks for synchronization because, if an operation acquires a lock and then fails, any other operation that requires that lock can never complete, regardless of how many steps it takes, even if it runs alone.
As applied to transactions, the definitions above need to be extended slightly to preclude the possibility that every attempt to commit any transaction fails. Specifically, we have the following nonblocking definitions for transactions.
Wait-free transactions: A transaction implementation is wait-free if all its operations are wait-free and any thread that repeatedly attempts to commit transactions eventually performs a successful commit.
Lock-free transactions: A transaction implementation is lock-free if all its operations are lock-free and if some thread repeatedly attempts to commit transactions, then eventually some thread performs a successful commit.
Obstruction-Free transactions: A transaction implementation is obstruction-free if all its operations are obstruction-free and if some thread repeatedly attempts to commit transactions, and runs in isolation after some point, then it eventually performs a successful commit.
Obstruction-Free Implementations
Clearly, obstruction-freedom is a weaker property than lock-freedom and wait-freedom. Here, we explain why we believe that it is nonetheless an important property to consider.
First, we believe that obstruction-free implementations are likely to be substantially simpler to design than lock-free and especially wait-free ones. This has numerous benefits including ease of modification, ease of verification, etc. In this specification, we describe the first nonblocking implementation of dynamic software transactional memory (STM); our implementation guarantees obstruction-freedom but not lock-freedom. It is simpler and more efficient than lock-free implementations of static STM.
Second, in some scenarios, we can exploit properties of the environment to ensure that every obstruction-free operation execution completes. For example, in a uniprocessor where threads are scheduled by time slice, relatively short obstruction-free operations may be guaranteed to run alone for long enough to complete. Another example is in priority-scheduled uniprocessors: an operation runs in isolation unless it is preempted by a higher priority operation.
Third, in some scenarios, we might reason that, even though the system does not guarantee operations will run in isolation for long enough to complete, we may determine by analysis or experiments that the "livelock" scenario that lock-freedom precludes but obstruction-freedom admits does not occur in practice.
Finally, an obstruction-free implementation can be augmented with a variety of different mechanisms that attempt to control the interactions between concurrent operations in order to ensure that operations eventually complete. A simple example is to use "backoff." Using this approach, operations wait before retrying upon encountering interference. Various schemes can be chosen for deciding how long to wait. One choice is a combination of randomization and exponential back off, which is very likely to cause operations to run long enough in isolation to complete. Such schemes can be effective for improving the performance of lock-free implementations by reducing contention, and we expect that they will be similarly effective in allowing obstruction-free operations to complete. Other "out of band" contention reduction mechanisms can also be employed, including mechanisms yet to be developed. The beauty of our approach is that the obstruction-free implementations themselves will not have to be modified (and therefore will not have to be reverified) in order to use a different contention reduction mechanisms.
Other possible approaches include queuing and time stamping approaches, in which threads agree amongst themselves to "wait" for each other to finish. While simplistic applications of these ideas would give rise to some of the same problems that the use of locks does, we have much more freedom in designing more sophisticated approaches for contention reduction than when using locks, because correctness is not jeopardized by interrupting an operation at any time and allowing another operation to continue execution. We expect that contention between operations will typically be quite rare, and that repeated retries will rarely be necessary. In scenarios where this is true, we benefit from the simple and efficient obstruction-free designs and only rarely invoke the more heavy-weight contention reduction mechanisms. In contrast, in most lock-free and wait-free implementations, the mechanisms that are used to ensure the respective progress properties impose significant overhead in the typical case.
Accordingly, building on these insights, we have developed simple, efficient nonblocking implementations of single-modification transactions, including nonblocking implementations structured as an atomic k-location-compare single-swap (KCSS) operation. KC SS verifies the contents of k locations and modifies one of them, all as a single atomic operation. One implementation of KCSS, when executed without contention, requires only two CAS operations, two stores, and 2 k non-cached loads. It requires no memory barriers under the TSO memory model.
The nonblocking progress condition that our implementation meets is obstruction-freedom. As detailed above, obstruction-freedom is a progress condition that tends to simplify the design of nonblocking algorithms by removing the need to provide strong progress guarantees in the algorithm itself (as required by wait-freedom or lock-freedom). Simply put, obstruction-freedom guarantees a thread's progress if other threads do not actively interfere for a sufficient period. The definition is thus geared towards the uncontended case, handling contended cases through orthogonal contention management mechanisms. Lock-based algorithms are not obstruction-free because a thread trying to acquire a lock can be blocked indefinitely by another thread that holds the lock. On the other hand, a lock-free algorithm is also obstruction-free because lock-freedom guarantees progress by some thread if some thread continuously take steps.
A Motivating Example: Manipulating: Linked Data Structures
KCSS is a natural tool for linked data structure manipulation; it allows a thread, while modifying a pointer, to check atomically that related nodes and pointers have not changed. An exploitation of general applicability is the implementation of nonblocking linked data structures with arbitrary insertions and deletions.
Examples presented in
In the example of
In short, the naive CAS based implementations simply do not work. Although effective (and rather ingenious) nonblocking algorithms do exist for ordered list-based sets (see e.g., T. Harris, A Pragmatic Implementation of Non-blocking Linked Lists, In Proc. 15th International Symposium on Distributed Computing (2001); and M. Michael, High Performance Dynamic Lock-free Hash Tables and List-based Sets, In Proc. 14th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 73-82 (2002)), these algorithms do not generalize easily to arbitrary linked data structures. For example, it is not clear how to modify these algorithms to implement multisets.
By employing KCSS instead of CAS, we can simplify the design of arbitrary nonblocking linked-list operations. In particular, KCSS allows us to confirm that other pointers of the illustrated lists remain unchanged at a linearization point at which we atomically perform the single swap used to effectuate the insert or delete operation. Furthermore, more complex data structures may also be supported.
In designing some implementations of our KCSS algorithm, we provide a simple and novel implementation of load-linked/store-conditional (LL/SC) using CAS synchronization; this implementation improves on previous results in that it can accommodate pointer values on all common architectures. In particular, ABA avoidance tags or ids need not be encoded integrally with pointer representations. We believe this algorithm is of independent significance: it extends the applicability of LL/SC-based algorithms to all common architectures that support CAS.
A k-location-compare single-swap (KCSS) operation takes k locations a1 . . . ak, k expected values e1 . . . ek, and a new value n1. If the locations all contain the expected values, the KCSS operation atomically changes the first locational from e1 to n1 and returns true; in this case, we say that the KCSS succeeds. Otherwise, the KCSS returns false and does not modify any memory location; in this case we say that it fails. In the next section, we present an implementation for KCSS using particular read, load-linked (LL), store-conditional (SC) and snapshot operations that we have also implemented. In this section, we describe more precisely the interface and semantics of the various operations, the correctness requirements, and our assumptions about the system.
Operation Semantics
We now describe the semantics of the operations for which we provide implementations in the next section. We consider a collection of locations. At any point in time, each location has an abstract value from a set of application values. As explained below, our implementation assumes some mild restrictions on this set.
A KCSS(k,a[1 . . . k], expvals[1 . . . k], newval) operation returns false if for some i ε[1,k], the abstract value of location a[i] differs from expvals[i]. If this operation returns true, then it also changes the abstract value of location a[1] to newval. The locations specified by a must all be distinct.
READ(a) and LL(a) operations return the abstract value of location a. An LL operation of thread p is said to be outstanding until p invokes an SC operation on the same location. The behavior of all operations is undefined if LL or KCSS invoked by process p while p has an outstanding LL operation on any location. While, it is straightforward to remove this restriction (see e.g., M. Moir, Practical Implementations of Non-blocking Synchronization Primitives, In Proc. 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 219-228 (1997) (presenting an efficient technique for generalizing LL/SC implementations so that LL/SC sequences can be executed concurrently on different locations)), retaining it simplifies our presentation. Accordingly, for simplicity of description and without limitation, we assume that LL and SC are used in pairs on the same location.
The behavior of an SC(a) operation S by process p is undefined if it is invoked before any LL(a) operation by process p has completed, or if there is not a previous LL(a) operation L by process p such that there is no LL, SC or KCSS operation invoked by process p between L and S. Otherwise, an SC(a) operation by process p returns true only if no other operation that changes the abstract value of location a has occurred since the preceding LL(a) operation by process p. We say that a SC operation succeeds if it returns true, and fails otherwise. To ensure that this operation is useful for implementing obstruction-free data structures, we further require that an SC(a) operation succeeds if no other operation that accesses location a takes a step between the invocation of p's preceding LL(a) operation and the completion of the SC(a) operation. Observe that this specification allows a concurrent READ(a) operation to cause a SC(a) operation to fail; in fact, it would do so in our implementation. Although this possibility does not jeopardize obstruction-freedom, eliminating it would allow some concurrent operations to succeed that would otherwise fail, and thus, may be desirable. As later described, our implementation can easily be modified to come close to this goal.
A SNAPSHOT(m, a[1 . . . m]) operation returns an array V [1 . . . m] such that, for each iε[1,m], V[i] is the abstract value of location a[i]. The locations specified by a must be distinct.
Correctness Condition
Below we present obstruction-free, linearizable implementations of the operations described above. Linearizability implies that each operation appears to take effect instantaneously at some point between its invocation and its response; this point is the operation's linearization point. Obstruction-freedom requires that if a thread p executes an operation, and after some point p runs without interference for long enough, then that operation will terminate.
Interoperability with Dynamic Data Structures and Memory Management
In our implementations of the above operations, each location initially holds its initial abstract value. Thus, locations can be dynamically allocated and initialized by a single thread, which is important for dynamic-sized data structures. Our implementations also allow a location to be freed if no operation that specifies this location as an argument is executing or will be invoked. Furthermore, they guarantee that there will always be a pointer to an object that could be accessed in the future. Thus, our operations do not affect memory management, and in particular, data structures based on our implementations "play nicely" with garbage collection and nonblocking memory management techniques. The garbage collector would need to be modified slightly to distinguish between pointers and tagged ids, which are described below.
System Model
We assume a machine architecture (typically a shared memory multiprocessor) that supports linearizable load, store, and CAS operations. It is straightforward to transform these algorithms to work in systems that provide LL and SC rather than CAS. In this case, native LL and SC operations should be directly used to replace the use of CAS in our implementations. Native LL and SC operations do not replace our implementations of the LL and sc operations because our implementations of these operations include additional functionality designed to be compatible with the SNAPSHOT operation. Appropriate LL/SC for CAS substitutions are known in the art (see e.g., M. Moir, Practical Implementations of Non-blocking Synchronization Primitives, In Proc. 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 219-228 (1997)).
The semantics of a CAS operations will be understood with reference to the following atomic code fragment:
boo1 CAS(1oc *a, value expval, value newval){
if (*a != expval)
return false;
*a = newval;
return true;
Although we assume linearizability, our algorithms are correct on multiprocessors that provide only the TSO memory model, without adding memory barrier instructions; this is a side effect of the way we use CAS.
An Exemplars Implementation
We now describe our implementations of the READ, LL, SC, SNAPSHOT, and KCSS operations. We begin by explaining a restricted version of the LL, SC, and READ operations, which is correct if we need only these operations. We then explain how LL can be modified slightly to support a simple SNAPSHOT operation. Finally we explain how we implement KCSS using LL, SC, and SNAPSHOT.
Recall that an SC(a,v) operation by process p should succeed only if no other operation that modifies location a is linearized between the linearization points of p's preceding LL(a) operation and p's SC(a,v) operation. To overcome the ABA problem, previous implementations of LL/SC from CAS have employed special "tags" or "version numbers" to be stored together with the application value in a location that can be accessed by CAS. This requirement severely restricts the range of values that can be stored by those SC implementations, and in particular, makes these implementations inapplicable for storing pointers in many architectures.
Our goal is to design implementations that place much milder restrictions on the set of application values, in particular so that our implementations can access pointers on all common multiprocessor architectures. Below we specify these restrictions, which are too weak to allow tag/version number techniques, and then explain how we can achieve our implementations despite these weaker restrictions.
Each location can store either an application value or a tagged process id. The abstract value of a location that contains an application value is always that value; when the location contains a tagged id, it is a little more complicated, as we explain below. A tagged process id (tagged id for short) contains a process id and a tag.
The only restriction we place on application values is that we have some way to distinguish them from tagged ids. One simple way to achieve this when the application value of interest is a pointer is to "steal" the low-order bit to mark tagged ids: we can arrange that all locations are aligned on even byte boundaries so that the low-order bit of every pointer is zero (locations that will be targets of CAS instructions are usually required to be word-aligned anyway).
For convenience, we treat tags as if they were unbounded integers. In today's 64-bit architectures, we can use one bit to distinguish tagged ids, 15 bits for the process id and 48 bits for the tag, which is more than enough to avoid the ABA problem that potentially arises as the result of tags wrapping around.
LL and SC
We now explain a simplified version of our implementations of the LL and SC operations using the code that follows.
typedef struct loc_s {
taggedid_t tid; // used for SNAPSHOT
value_t val; // atomically CASable
} loc_t;
void RESET (loc_t *a) {
1: value_t oldval = a−>val;
2: if (TAGGED-ID(oldva1))
CAS(&a−>val, oldval, VAL_SAVE[ID(oldval)]);
value_t LL (loc_t *a) {
4: while (true) {
INC_MY_TAGGED_ID; // increment local tag
value_t val = READ (a);
VAL_SAVE [MY_ID] = val;
if (CA (&a−>val, val, MY_TAGGED_ID)) {
a−>tid = MY_TAGGED_ID; // needed for SNAPSHOT
return val;
bool SC(loc_t *a, value_t newval) {
11: return CAS(&a−>val, MY_TAGGED_ID, newal);
value_t READ (loc_t *a) {
12: while (true) {
value_t val = a−>val;
if (!TAGGED_ID(val)) return val;
For the purposes of this simplified version, the reader should ignore the tid field of the location record (i.e., a location record is simply a memory location that contains an application value or a tagged id), and any code that accesses it, namely line 9.
In order to implement LL(a) and SC(a,v) operations for process p, we need a way to determine whether the abstract value of location a has changed since the LL(a) operation was linearized. Our approach is to have p's LL (a) operation store a previously unused tagged id in location a (line 8). We ensure that the tagged id is new by having p maintain a local tag, which it increments each time it needs a new tagged id (line 5). As explained below, we do not allow any operation that changes the abstract value of location a to be linearized while the tagged id of another process is in that location. Thus, if the SC(a,v) operation changes the contents of location a from the tagged id stored by the preceding LL(a)f the same process to v (i.e., the CAS in line 11 succeeds), then it changes the abstract value of location a to v while ensuring that the abstract value of location a has not changed since the previous LL (a) operation, as required.
To guarantee obstruction-freedom, it is not sufficient to prevent other operations from being linearized between the linearization points of p's LL (a) and SC(a,v) operations: we must guarantee that a thread that runs without interference will make progress. Therefore, it must be possible for a concurrent operation to remove p's tagged id from location a (thereby causing p's SC to fail), without changing the abstract value of location a; this is achieved by the auxiliary RESET operation, which is explained below. To make this possible, before attempting to store a new tagged id in location a, p's LL (a) operation first stores the application value it intends to replace with its tagged id (line 6) in a special location VAL_SAVE [p] (line 7). (Recall that p can have at most one outstanding LL operation, so a single location is sufficient.) For now, we can consider the abstract value of a location that contains a tagged id of process p to be VAL_SAVE [p]. Thus, it is easy to see that when p's LL(a) operation replaces the application value in location a with a tagged id (line 8), the abstract value of location a does not change. Similarly, another operation that uses CAS to remove p's tagged id can correctly determine the abstract value of location a in order to replace p's tagged id with the correct abstract value by reading VAL_SAVE [p] (line 3). (Process p does not change VAL_SAVE [p] while any location contains its tagged id. Also, there is no ABA problem when either p or another process removes p's tagged id from location a, because p uses a fresh tagged id each time it stores a tagged id in location a and only process p stores a tagged id with p's process id.)
This completes the description of the LL(˜) and SC(˜,Vop) erations, except that we have not explained the READ(^) operation, which is used by LL(˜( ) line 6).
The READ operation determines the abstract value of location a. It first reads location a (line 13). If the value read is an application value, then this was the abstract value of location a when line 13 was executed, so it can be returned (line 14). Otherwise, the abstract value of location a when line 13 was executed was VAL_SAVE [p] here p is the process whose id is in the tagged id read at line 13. Simply reading that location would not necessarily provide the correct abstract value of location a because p might have changed the contents of this location since the READ(a) operation executed line 13. However, because there can be no ABA problem on tagged ids, the READ(a) operation could read VAL_SAVE [p] and then reread location a to confirm that the same tagged id is still in location a. In this case, it could correctly linearize a read of the abstract value of location a at any point between the two reads of location a. If we wanted to support only LL, SC, and READ operations, this would be correct and would allow a location to be read without causing a concurrent LL/SC sequence on the same location to fail. However, in code above, if a READ operation encounters a tagged id, it calls RESET in order to attempt to set location a back to its abstract value. As explained later, this is useful to support the SNAPSHOT and KC SS operations that are presented next.
We have adapted a well-known nonblocking technique, see Y. Afek, H. Attiya, D. Dolev, E. Gaffii, M. Merritt, and N. Shavit, Atomic Snapshots of Shared Memory, Journal of the ACM (JACM), 40(4):873-890 (1993), to obtain an atomic snapshot of a number of locations. We repeatedly "collect" (i.e., read each location individually and record the values read) the values from the set of locations until we encounter a collect in which none of the values collected has changed since it was read in the previous collect. In this case, it is easy to see that, when the first value is read in the last collect, all of the values read during the previous collect are still in their respective locations. A tricky detail is how to determine that a value has not changed since the last time it was read. Because of the ABA problem, it is not sufficient to simply determine that the two values read were the same: the location's value may have changed to a different value and then changed back again between these two reads. As explained below, we can determine a value has not changed using the tid field (which we have been ignoring until now) associated with each location. This field serves the same purpose as the tags (or version numbers) discussed earlier. However, our implementation does not require them to be modified atomically with the val field, and therefore does not restrict applicability, as discussed earlier.
Exemplary code for SNAPSHOT follows.
Value_t[l . . m] COLLECT_VALUES(int m, (loc_t *) a[l..m]){
Value_t V[l . . m];
S1: for (i = 1; i <= m; 1++) V[i] = READ(a[i]);
S2: return V;
tag_t[l..m] COLLECT_TAGGED_IDS(int m, (loc_t *) a[l . . m]){
taggedid_t T[l . . m];
S3: for (i = l; i <= m; 1++) T[i] = a[I]−>tid;
S4: return T;
value_t [l..m] SNAPSHOT(int m, (loc_t *) [l..m] a){
taggedid_t TA[l . . m], TB[l . . m];
value_t VA[l . . m], VB[l . . m];
S5: while (true) {
TA[l . . m] = COLLECT_TAGGED IDS(m,a);
VA[l . . m] = COLLECT_VALUES(m,a);
VB[l . . m] = COLLECT_VALUES(m,a);
TB[l . . m] = COLLECT_TAGGED_IDS(m,a);
if (for all i,
(TA[i] == TB[i]) &&
(VA[i] == VB[i]))
return VA;
Observe that the basic structure (if we ignore tags for a moment longer) is essentially as described above: we collect the set of values twice (lines S7 and S8) and retry if any of the values changed between the first read and the second (line S10). Observe further that COLLECT_VALUES uses READ to read the value of each location. Thus, it ensures that the abstract value it reads from a location a is stored in location a itself. As described earlier, for the abstract value of a location to change, some process must install a fresh tagged id in that location and subsequently change that tagged id to the new abstract value. This entire sequence must occur between the READ in the first collect and the READ in the second. Therefore, line 9 of the LL operation, which stores the fresh tagged id in the tid field of the location, must be executed between the first and second reads of the tid field by the SNAPSHOT operation, which will therefore retry (see lines S6 and S9). This argument is simple, but it depends on the fact that READ resets a location that contains a tagged id. Below, we explain how our implementation can be modified to avoid this requirement.
Our KC SS implementation can be built using the operations described above and will be understood with reference to the exemplary code that follows:
boo1 KCSS(int k, (loc_t *) a[l . . k],
value_t expvals [l . . k], value_t newval){
value_t oldvals [l . . k];
while (true) {
oldvals [l] = LL(a[l]);
oldvals[2 . . k] = SNAPSHOT(k−l, a[2 . . k]);
if (for some i, oldvals[I] != expvals[i]) {
SC(a[l], oldvals [l]);
return false;
// try to commit the transaction
if (SC(a[l], newval)) return true;
} // end while
The implementation itself is straightforward, but the linearization argument is trickier. The basic idea is to use LL and sc to change the value of location a[1] from expvals[1] to newval (lines K2 and K7), and to use SNAPSHOT to confirm that the values in locations a[2 . . . k] match expvals[2 . . . k] (lines K3 and K4). If any of the k values is observed to differ from its expected value (line K4), then the KCSS and returns false, as required (line K6). However, before returning, it attempts to restore a[1] to expvals[1] using SC (line K5), so that the previous LL operation is no longer outstanding, and thus, the process may subsequently invoke another LL or KCSS operation.
If the sc in line K7 succeeds, then we know that the abstract value of location a[1] is expvals[1] for the entire interval between the linearization point of the LL in line K2 and the linearization point of the SC in line K7. In particular, this holds at the linearization point of the SNAPSHOT called in line K3, when the abstract values of a[2 . . . k] match expvals[2 . . . k]. Thus, we can linearize the successful KCSS operation at that point. This is where the linearization argument becomes slightly tricky: The actual value in location a[1] does not change to newval until the SC in line K7 is linearized. However, the abstract value of that location changes at the linearization point of the KCSS operation, which occurs earlier. Therefore, if any other operation observes the abstract value of that location between the linearization points of the SNAPSHOT in line K3 and the SC in line K7, it will see the wrong abstract value and the implementation will not be linearizable. To prevent this problem, we require READ to reset a location, rather than simply reading the VAL_SAVE entry of the process whose tagged id is in the location, and then confirming that the tagged id is still in the location (as described earlier). This ensures that no process observes the wrong abstract value in the interval between the SNAPSHOT and the successful SC. As described below, we can relax this requirement somewhat; we have presented our implementations without these modifications in order to keep the presentation simple and clear.
We have presented a simple and efficient nonblocking implementation of a dynamic collection of locations that supports READ, LL, SC, SNAPSHOT and KCSS operations. We have also explained a simple extension by which we can support transactions that modify at most one location. These operations form a powerful set of tools for designing relatively simple obstruction-free implementations of important shared data structures such as linked lists. Because of the way in which we solve the ABA problem, our implementation is more efficient, more flexible, and more widely applicable for implementing linked data structures than the techniques used in recent direct implementations of lock-free linked lists.
From the basic ideas we have presented in this paper, numerous possible optimizations, extensions, and generalizations are possible. We describe a few of them here.
Optimizing READ
Our READ operation can be optimized by observing that if the CAS in line 3 thereof succeeds, then we have already determined the abstract value of the location being accessed, which can be returned immediately without rereading.
Improving Concurrency
As stated earlier, we can modify our implementation so that READ does not always have to reset a location that contains a tagged id: in some cases, reading a value from the VAL_SAVE location of the process whose tagged id is encountered, and then confirming that the tagged id is still in the location is sufficient to determine the correct abstract value. This does not work, however, in cases in which we linearize a modification to the location accessed by a LL/SC pair at a point other than the linearization point of the SC operation. In the operations we have presented, this is the case only for LL/SC sequences that are part of a higher-level KCSS operation. Therefore, if we extend the interface of LL so that the invoker can specify whether or not this is a "dangerous" use of LL/SC, then this information could be stored in the tagged id. Thus, READ could reset only when it encounters such LL/SC sequences, while allowing other, simpler uses of LL/SC to proceed concurrently.
This modification would complicate the SNAPSHOT implementation slightly. Recall that the argument given earlier for the linearizability of SNAPSHOT operations depends on READ always resetting a location if it contains a tagged id. This can be overcome by having SNAPSHOT also collect the tagged ids from locations for which it has determined values without resetting the location. As this would be done only if the tagged id is in the location on behalf of a nondangerous LL/SC sequence, the abstract value of the location does not change before that tagged id is removed from the location, so it is sufficient for SNAPSHOT to confirm that it has not.
DCSS and CAS
To implement a double-compare single-swap (DCSS) operation (i.e., KC SS with k=2), we can replace the SNAPSHOT of k−1=1 location in our KCSS implementation with a simple READ. Similarly, for a CAS on these locations, which is simply a KCSS operation with k=1, the snapshot can be eliminated entirely.
In some cases, such as the multiset example mentioned earlier, locations that support only read, CAS and DCSS operations are sufficient. In cases such as this one, we can eliminate the tid field (and the code that accesses it), as this field was used only for the SNAPSHOT operation. We can also implement CAS by using the native CAS instruction, resetting the location if it contains a tagged id.
Optimizations to SNAPSHOT and KCSS
The implementation of SNAPSHOT can be improved at the cost of muddying the presentation slightly. For example, the tags collected at line S9 can be used for the first set of tags in the next iteration (we collect the tags again in the next iteration at line S6). Also, one can eliminate a complete sequence of reads from the snapshot, at the cost of a slightly more complex proof. We can also improve the performance of the KCSS by breaking the snapshot abstraction (for example, there is no need to take an entire snapshot if one of the early values read does not match the expected value).
Single Modification Transactions
We chose the KCSS API to demonstrate our ideas because its semantics is easy to state and understand. However, the ideas presented here can be extended to support transactions that modify only a single location. The basic idea is to have transactional loads record the information collected in the first half of the snapshot in our KCSS implementation, and transactional commit do the second half of the snapshot to determine if any of the values read had been modified by a concurrent operation since being read by the transactional load. Interestingly, the implementation of this stronger semantics would actually be somewhat more efficient than using READ and KC SS for the same purpose, because the READs and the first half of the snapshot in KCSS are collapsed together into the transactional load. It would also be straightforward to provide a transactional "validate" operation that rechecks the values read so far in the transaction.
We believe that the ability provided by KCSS to "confirm" the abstract value of some locations, while modifying an-other, will significantly reduce the impact of ABA issues on algorithm designers. However, such issues may still arise in some cases, and implementing the transactions as discussed above would completely relieve designers of the burden of dealing with this problem.
While the invention(s) is (are) described with reference to various implementations and exploitations, it will be understood that these embodiments are illustrative and that the scope of the invention(s) is not limited to them. Terms such as always, never, all, none, etc. are used herein to describe sets of consistent states presented by a given computational system, particularly in the context of correctness proofs. Of course, persons of ordinary skill in the art will recognize that certain transitory states may and do exist in physical implementations even if not presented by the computational system. Accordingly, such terms and invariants will be understood in the context of consistent states presented by a given computational system rather than as a requirement for precisely simultaneous effect of multiple state changes. This "hiding" of internal states is commonly referred to by calling the composite operation "atomic", and by allusion to a prohibition against any process seeing any of the internal states partially performed.
In some embodiments, the current invention may comprise a computer program product embodied in one or more computer readable media.
Many variations, modifications, additions, and improvements are possible. For example, while application to particular concurrent shared objects and particular implementations thereof have been described, applications to other shared objects and other implementations will also be appreciated by persons of ordinary skill in the art. While much of description herein has focused on compare and swap (CAS) based synchronization, other synchronization primitives may be employed. For example, based on the description herein, persons of ordinary skill in the art will appreciate that other suitable constructs, including load-linked and store-conditional operation pairs (LL/SC) may be employed, as well. Plural instances may be provided for components, operations or structures described herein as a single instance. Finally, boundaries between various components, operations and data stores are somewhat arbitrary, and particular operations are illustrated in the context of specific illustrative configurations. Other allocations of functionality are envisioned and may fall within the scope of the invention(s).
In general, structures and functionality presented as separate components in the exemplary configurations may be implemented as a combined structure or component. Similarly, structures and functionality presented as a single component may be implemented as separate components. These and other variations, modifications, additions, and improvements may fall within the scope of the invention(s).
|Cited Patent
|Filing date
|Publication date
|Jun 27, 1984
|Apr 22, 1986
|Motorola, Inc.
|Method and apparatus for a compare and swap instruction
|Oct 15, 1985
|Jul 11, 1989
|International Business Machines Corporation
|Extended atomic operations
|Jul 13, 1990
|Jun 29, 1993
|International Business Machines Corporation
|Message queue processing among cooperative processors having significant speed differences
|Mar 12, 1992
|Jun 27, 1995
|Digital Equipment Corporation
|System for achieving atomic non-sequential multi-word operations in shared memory
|Jun 5, 1998
|Oct 3, 2000
|International Business Machines Corporation
|Method utilizing a set of blocking-symbol resource-manipulation instructions for protecting the integrity of data in noncontiguous data objects of resources in a shared memory of a multiple processor computer system
|Sep 24, 1997
|Nov 7, 2000
|Sony Corporation
|Performing memory management in an object-oriented programming environment
|Jun 23, 1998
|Jan 23, 2001
|Microsoft Corporation
|System and method for recycling numerical values in a computer system
|Dec 9, 1998
|Apr 24, 2001
|Sun Microsystems, Inc.
|Platform independent double compare and swap operation
|Dec 16, 1998
|Mar 19, 2002
|Gemstone Systems, Inc.
|Object queues with concurrent updating
|Dec 31, 1998
|Mar 19, 2002
|Microsoft Corporation
|Lock-free methods and systems for accessing and storing information in an indexed computer data structure having modifiable entries
|Jun 24, 1999
|Apr 2, 2002
|International Business Machines Corporation
|Apparatus and method for accessing an object oriented object using a smart passive reference
|Jun 15, 2000
|Jun 17, 2003
|International Business Machines Corporation
|Method and apparatus for maintaining a linked list
|Feb 24, 2000
|Nov 18, 2003
|International Business Machines Corporation
|Method and apparatus for managing access contention to a linear list without the use of locks
|Apr 18, 2001
|Nov 30, 2004
|Sun Microsystems, Inc.
|Lock-free implementation of concurrent shared object with dynamic node allocation and distinguishing pointer value
|Sep 24, 2003
|Nov 6, 2007
|Sun Microsystems, Inc.
|Efficient non-blocking k-compare-single-swap operation
|Apr 18, 2001
|Nov 29, 2001
|Sun Microsystems, Inc.
|Concurrent shared object implemented using a linked-list with amortized node allocation
|Sep 28, 2001
|Apr 3, 2003
|Bonola Thomas J.
|Concurrent non-blocking FIFO array
|Feb 6, 2002
|Jun 5, 2003
|Tse-Yu Yeh
|Mechanism for processing speclative LL and SC instructions in a pipelined processor
|Jan 10, 2003
|Jul 24, 2003
|Sun Microsystems, Inc.
|Single-word lock-free reference counting
|Jan 10, 2003
|Sep 18, 2003
|Sun Microsystems, Inc.
|Non-blocking memory management mechanism for supporting dynamic-sized data structures
|Jan 10, 2003
|Sep 25, 2003
|Sun Microsystems, Inc.
|Value recycling facility for multithreaded computations
|Jan 10, 2003
|Sep 25, 2003
|Sun Microsystems, Inc.
|Lock-free implementation of dynamic-sized shared data structure
|May 9, 2003
|Nov 20, 2003
|Broadcom Corporation
|Load-linked/store conditional mechanism in a CC-NUMA system
|Jul 16, 2003
|Jan 22, 2004
|Sun Microsystems, Inc.
|Obstruction-free synchronization for shared data structures
|Jul 16, 2003
|Jan 22, 2004
|Sun Microsystems, Inc.
|Software transactional memory for dynamically sizable shared data structures
|Jul 16, 2003
|Feb 19, 2004
|Sun Microsystems, Inc.
|Obstruction-free mechanism for atomic update of multiple non-contiguous locations in shared memory
|Jul 16, 2003
|Aug 5, 2004
|Sun Microsystems, Inc.
|Space- and time-adaptive nonblocking algorithms
|May 17, 2005
|Sep 28, 2006
|Nemirovsky Mario D
|Mechanism for managing resource locking in a multi-threaded environment
|Sep 12, 1989
|May 2, 1990
|International Business Machines Corporation
|Method for comparing and swapping data in a multi-programming data processing system
|Jun 14, 1991
|Jan 15, 1992
|International Business Machines Corporation
|A method of passing task messages in a data processing system
|Apr 16, 1985
|Jan 16, 1986
|Motorola, Inc.
|Method and apparatus for a compare and swap instruction
|Jan 2, 2001
|Jul 26, 2001
|Sun Microsystems, Inc.
|Double-ended queue with concurrent non-blocking insert and remove operations
|Jan 2, 2001
|Jul 26, 2001
|Sun Microsystems, Inc.
|Double-ended queue with concurrent non-blocking insert and remove operations
|Apr 18, 2001
|Oct 25, 2001
|Sun Microsystems, Inc.
|Concurrent shared object implemented using a linked-list with amortized node allocation
|Apr 18, 2001
|Nov 1, 2001
|Sun Microsystems, Inc.
|Lock-free implementation of concurrent shared object with dynamic node allocation and distinguishing pointer value
|Jan 10, 2003
|Jul 24, 2003
|Sun Microsystems, Inc.
|Lock-free implementation of dynamic-sized shared data structure
|Jan 10, 2003
|Jul 24, 2003
|Sun Microsystems, Inc.
|Value recycling facility for multithreaded computations
|Afek, "Atomic Snapshots of Shared Memory," Journal of the ACM, vol. 40, No. 4, pp. 873-890, 1993.
|Afek, et al., "Disentangling Multi-Object Operations," Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 111-120, Aug. 1997.
|Afek, Yehuda et al., "Long-Lived Renaming made Adaptive", 18th Annual ACM Symposium on Principles of Distributed Computing, pp. 91-104, 1999.
|Agesen, et al., "DCAS-Based Concurrent Deques," SPAA 2000. Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 137, 146, ACM Press, ISBN: 1-58113-185-2, 2000.
|Agesen, et al., "DCAS-Based Concurrent Deques," Theory of Computing Systems., vol. 35, No. 3, pp. 349-386, May 2002.
|Agesen, Ole et al., "An Efficient Meta-Lock for Implementing Ubiquitous Synchronization," ACM SIGPLAN Notices, vol. 34, No. 10, pp. 207-222, Oct. 1999.
|Anderson, et al., "Universal Constructions for Large Objects," IEEE Transactions on Parallel and Distributed Systems, vol. 10, No. 12, pp. 1317-1332, 1999.
|Arora, et al., "Thread Scheduling for Multiprogrammed Multiprocessors," Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architecture, pp. 119-129, ACM Press, 1998.
|Attiya Hagit et al., "An Adaptive Collect Algorithm with Applications", Dept. of Computing Science, The Technion, Israel, May 10, 2001.
|Attiya, et al., "Are Wait-Free Algorithms Fast?," Journal of the ACM, 41(4):725-763, Jul. 1994.
|Attiya, et al., "Atomic Snapshots in O(n log n) Operations," SIAM Journal on Computing, 27(2):319-340, Apr. 1998.
|Attiya, et al., "Universal Operations: Unary Versus Binary," Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, pp. 223-232, ACM Press, 1996.
|Barnes, Greg, "A Method for Implementing Lock-Free Shared Data Structures", 5th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 261-270, 1993.
|Bershad, "Practical Considerations for Highly Concurrent Data Objects," Proceedings 13th IEEE International Conference on Distributed Computing Systems, pp. 264-273, IEEE Computer Society Press, 1993.
|Detlefs, et al., "Even Better DCAS-Based Concurrent Deques," Lecture Notes in Computer Science, vol. 1914, pp. 59-73, Springer-Verlag, Berlin, German, ISBN: 3-540-41143-7, 2000.
|Detlefs, et al., "Lock-Free Reference Counting," Proc. 20th Annual ACM Symposium on Principles of Distributed Computing, pp. 190-199, ACM Press, 2001.
|Greenwald, "Non-Blocking Synchronization and System Design," PhD Thesis, Technical Report STAN-CS-TR-99-1624, Aug. 1999, 241 pages.
|Greenwald, et al., "The Synergy Between Non-Blocking Synchronization and Operating System Structure," Proceedings of the 2nd Symposium on Operating Systems Design and Implementation, pp. 123-136, Usenix Association, 1996.
|Herlihy, "A Methodology for Implementing Highly Concurrent Data Objects," ACM Transactions on Programming Languages and Systems, 15(5):745-770, Nov. 1993.
|Herlihy, "Wait-Free Synchronization," ACM Transactions on Programming Languages and Systems, 11(1): 124-149, Jan. 1991.
|Herlihy, et al., "Linearizability: A Correctness Condition For Con-Current Objects," ACM Transactions on Programming Languages and Systems, 12(3): 463-492, Jul. 1990.
|Herlihy, et al., "Transactional Memory: Architectural Support for Lock-Free Data Structures," Proc. 20th International Symposium in Computer Architecture pp. 289-300, IEEE Computer Society, Washington, DC, 1993.
|Herlihy, Maurice et al., "Obstruction-Free Synchronization: Double-Ended Queues as an Example" 23rd International Conference on Distributed computing, May 2003.
|Herlihy, Maurice et al., "The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized Lock-Free Data Structures", Sun Microsystems Technical Report SMLI TR-2002-112, Jun. 2002.
|Herlihy, Maurice, "Dynamic-Sized Lockfree Data Structures", Sun Microsysems Technical Report SMLI TR-2002-112, Jun. 2002.
|Israeli, Amos et al., "Disjoint-Access-Parallel Implementations of Strong Shared Memory Primitives", 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 151-160, 1994.
|Lamarca, "A Performance Evaluation of Lock-Free Synchronization Protocols," Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 130-140, ACM Press, 1994.
|Lamport, "A Fast Mutual Exclusion Algorithm," ACM Transactions on Computer Systems, vol. 5, No. 1, pp. 1-11, 1987.
|Luchangco, et al., "Nonblocking k-compare-single-swap," Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 314-323, ACM Press, 2003.
|Massalin, "Synthesis: An Efficient Implementation of Fundamental Operating System Services," 158 pages, 1992.
|Massalin, et al., "A Lock-Free Multiprocessor OS Kernel," Technical Report TR CUCS-005-9, Columbia Univ., New York, NY, 1991, 21 pages.
|Michael, et al., "Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes," Proceedings of the 21st Annual ACM Symposium on the Principles of Distributed Computing, pp. 21-30, ACM Press, 2002.
|Michael, et al., "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms," Proceedings of PODC, pp. 267-275, May 1996.
|More, "Laziness Pays! Using Lazy Synchronization Mechanisms to Improve Non-Blocking Constructions," Proc. 19th Annual ACM Symposium on Principles of Distributed Computing, pp. 61-70, ACM Press, 2000.
|More, "Practical Implementation of NOn-Blocking Synchronization Primitives," Proceedings of the 16th Annual Symposium on Principles of Distributed Computing, pp. 219-228, ACM Press, 1997.
|More, "Transparent Support for Wait-Free Transactions," Proceedings of the 11th International Workshop on Distributed Algorithms, pp. 305-319, Springer-Verlag, 1997.
|More, et al., "Wait-Free Algorithms for Fast, Long-Lived Renaming," Science of Computer Programming, vol. 25, No. 1, pp. 1-39, Aug. 1995.
|Shavit, et al., "Combining Funnels: A Dynamic Approach to Software Combining," Journal of Parallel and Distributed Computing, vol. 60, No. 11, pp. 1355-1387, Nov. 2000.
|Shavit, et al., "Combining Funnels: A New Twist on an Old Tale . . . ," Proceedings of the 17th Annual ACM Symposium on Principals of Distributed Computing, pp. 61-70, ACM Press, 1998.
|Shavit, et al., "Software Transactional Memory," Distributed Computing, vol. 10, No. 2, pp. 99-116, Feb. 1997.
|Timothy L. Harris, et al., "A Practical Multi-Word Compare-and-Swap Operation," 2002, University of Cambridge, 13 pages.
|Treiber, "Systems Programming: Coping with Parallelism," IBM Technical Report RJ5118, Apr. 23, 1986.
|Turek, John et al., "Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking", 11th ACM SIGACT-SIGMOND-SIGART Symposium on Principles of Database Systems, 1992.
|Turek, John et al., "Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking", 11th ACM SIGACT—SIGMOND-SIGART Symposium on Principles of Database Systems, 1992.
|U.S. Appl. No. 11/864,574, filed Sep. 28, 2007.
|U.S. Appl. No. 11/864,624, filed Sep. 28, 2007.
|U.S. Appl. No. 11/864,667, filed Sep. 26, 2007.
|Citing Patent
|Filing date
|Publication date
|Nov 25, 2013
|Jun 9, 2015
|Freescale Semiconductor, Inc.
|Multi-threaded system for performing atomic binary translations
|Jul 6, 2012
|Sep 15, 2015
|Oracle International Corporation
|Efficient non-blocking K-compare-single-swap operation
|U.S. Classification
|711/147, 711/100, 711/154
|International Classification
|Cooperative Classification
|European Classification


text:
BTV National Biss keys asiasat 7 105.5'E Update last 11.09.2017 Asiasat 7 105.5'E MPEG-4 TP:3690 V 11110 Sid:000B Biss : D2 BE 5A EA BC 67 F8 1B PowerVu By: India, Bangladesh, sri lanka The Cantharis Of Live Sports Bangladesh Television (BTV), a state-owned national TV station began its …Read More »
Home / Tag Archives: 1055e
Sony Network Asiasat 7 @ 105.5E 10.06.2016
Sony Network PowerVu Asiasat 7 @ 105.5E 10.06.2016 Asia Satellite Telecommunications Co. Ltd. (commonly AsiaSat, SEHK: 1135) is a commercial operator of communication spacecraft. AsiaSat is based in Hong Kong with two major shareholders, CITIC (34.8 per cent) and General Electric (34.1 per cent). In December 2013, AsiaSat commissioned AsiaSat …Read More »
AsiaSat 7 105.5E Zee Premier Cinema News
AsiaSat 7 105.5E Zee Premier Cinema News Palapa D 113.0E 3574 V "TV Parlemen" has left again. Palapa D 113.0E 3792 H "BNI Life +1" has left again. AsiaSat 7 105.5E 3820 V "Zee Premier Cinema has started on , Conax.Zee Premier and Ten 3" have left. Yamal 401 90.0E …Read More »

subset: commoncrawl


text:
|www.BedandBreakfast-Directory.co.uk - The Bed and Breakfast Directory.
Home > England > Cambridgeshire > Cambridge
Worth House
Recommended by 'Which?'s' The Good Bed and Breakfast Guide - ETC 4 Diamond Guest Accommodation Rating, Silver Award
|Worth House offers comfortable, spacious accommodation, to include hospitality trays, TV, ironing facilities, centrally heated. All rooms are en suite. Easy access to Cambridge's City centre, colleges and river by bus or a short walk.


text:
The new year is a time for new beginnings. I've been considering re-designing this blog for some time now. I've hunted some design resources and thought you might like a share of what I've found so far. The main thing that has stopped me from doing a re-design is that I like too many colors! […]Read More
Free Photoshop Custom Shapes – Tags 3
Up for grabs today is a sweet mixed set of 5 free photo shop custom shapes. (PNG are included for those who are running gimp or PSP). I really lucked out with the poll results last week because I happened to have some created shapes stocked up to deliver to you! If you don't know […]Read More
Freebie Label Bookplate Template CU4CU
Well… I opened my Etsy shop for digital goods monnnths ago, and finally got some items posted. In celebration of getting a round tuit, ::wink:: here's a freebie clipart label/bookplate template download in PNG format. This item is high resolution, and perfect for jar labels, invitations, announcements, blog graphics, etc… Enjoy! Linking Up HereRead More
Free Photoshop Custom Shapes – Tags 2
After an uber busy web dev week. I just had to take some time out to do a freebie! This pack has been a work in progress for some time now and I just had to finish them up. I'm not sure how often I'll be releasing CU digital scrapbooking freebies once things start warming […]Read More
25 Beautiful Seamless Patterns for Web Design Inspiration
Every now and then one needs a little jump start to get those creative juices flowing when designing a website. When I'm experiencing a creative block, creative sites that offer free resources, textures and patterns always get me back in the groove again. I've put together this hand picked set of patterns for you, […]Read More
Free Vintage Grunge Textures Patterns & Items Collection 2
Here's another hand picked list of free vintage grunge textures and patterns, including an additional vintage butterfly broach and Magnifying glass. Enjoy!If you missed it, here's the link for Collection 1. Antique Ornamental Paper by: Bittbox Vintage and Retro Textures by: ericalw | Terms: Credit and Notify on DA Vintage Wallpaper Stock by: apple-pai | Terms: Credit for […]Read More
Up for grabs today is a lovely set of tag and ribbon custom shapes. I'll likely be making some variations of them as the ribbons turned bit too fat for my liking. There's definitely room for improvement here. They are my very first shapes, so all in all they turned out pretty well. With this set […]Read More


text:
10281 N Old 27, Gaylord, MI 49735Request info Add to list
To view building contacts please sign in with your Pro account or create a pro account.
Kevin E.
Company: requires Pro account
Email: requires Pro account
Phone: requires Pro account
Building Details:
• Year Built: 1970
10281 N Old 27 is an industrial property for lease in Gaylord, MI.
36,000sf of office, warehouse and storage space available for lease or purchase. Situated on 6 acres complete with a fenced in yard, and located very near the access to I-75, this site is ideal for a light industrial business. The 2,500 square foot office building has a reception area, private office spaces, fireplace, and two kitchen areas. Two warehouse buildings consisting of 33,500sf including overhead radiant heat, 5 dock seals, 40 yard McBain trash compactor and a paint room with two bays that is EPA certified with an eye wash station.
Request Property Information
Please describe your commercial real estate requirements. We'll introduce you to local properties that match your criteria.


text:
The McLaughlin GroupHost: John McLaughlinPanel: Pat Buchanan, Author and Columnist; Eleanor Clift, The Daily Beast; Mort Zuckerman, U.S. News & World Report; Clarence Page, Chicago TribuneBroadcast: Weekend of December 21-22, 2013
Copyright © 2013 by Federal News Service, LLC, 1120 G Street NW, Suite 990, Washington, DC 20005-3801 USA. Federal News Service is a private firm not affiliated with the federal government. No portion of this transcript may be copied, sold or retransmitted without the written authority of Federal News Service, LLC. Copyright is not claimed as to any part of the original work prepared by a United States government officer or employee as a part of that person's official duties. For information on subscribing to the FNS Transcripts Database or any other FNS product, please email HYPERLINK "mailto:firstname.lastname@example.com" firstname.lastname@example.com or call 1-202-347-1400. ANNOUNCER: It's the 32nd annual McLaughlin Group year-end awards, 2013, part one. Here's the master of ceremonies, John McLaughlin. JOHN MCLAUGHLIN: Biggest winner of 2013. Pat Buchanan. PAT BUCHANAN: Cardinal Bergoglio becomes Pope Francis I, the most famous and popular man in the world. MR. MCLAUGHLIN: Eleanor. ELEANOR CLIFT: Wall Street topped 16,000 and markets are doing fine. And I'm glad the pope is pointing out all the inequality that represents, because Main Street is still waiting for its turn. MR. MCLAUGHLIN: Mort. MORT ZUCKERMAN: Vladimir Putin, the ruler of Russia, who outmaneuvered the United States in virtually every strategic corner of the world. MR. MCLAUGHLIN: Clarence. CLARENCE PAGE: Most exciting political race of the year, Bill de Blasio, mayor -- new mayor of our biggest city. MR. MCLAUGHLIN: The envelope, please, Mort. Thank you, Mort. Is this your Johnny Carson routine? MR. ZUCKERMAN: I can't tell you what's in there, John. You've got to read it. MR. MCLAUGHLIN: Carnac the Magnificent? MR. ZUCKERMAN: Magnificent, yes, but not Carnac. MR. MCLAUGHLIN: Carnac knew only the questions. Johnny had the answers, right? MR. PAGE: Yeah. MR. MCLAUGHLIN: God bless his soul. The biggest winner of 2013 is Russian President Vladimir Putin. MR. PAGE: You win, Mort. (Laughs.) MR. MCLAUGHLIN: He resolved the Syrian crisis largely by a brilliant op-ed in The New York Times that ended the military action against Syria. And in December, Putin snatched Ukraine away from the West just before Ukraine signed a trade pact with the European Union, boosting Russia's international prestige. Biggest winner: Vlad. OK, biggest loser of 2013. Pat Buchanan. MR. BUCHANAN: Barack Hussein Obama and "Obamacare." MR. MCLAUGHLIN: Eleanor. MS. CLIFT: You've got a small point there, Pat. (Laughter.) But I -- the president still has his job. I think the biggest loser is the president of Egypt, Mr. Morsi, who was deposed in a military coup and hasn't been heard from since. MR. MCLAUGHLIN: Clarence. MR. PAGE: I think the -- well, the Republicans' lack of a coherent strategy to deal with the "Obamacare" setbacks is an even bigger loser than President Obama. MR. MCLAUGHLIN: Mort. MR. ZUCKERMAN: I've got a tie -- the city of Detroit, which went bankrupt, and the average American working-class individual, whose real wages have declined at a time of relative prosperity. MR. MCLAUGHLIN: The biggest loser is the concept of red lines. Obama drew them, then smudged them, then erased them completely. It will be a long, long time before any president invokes red lines to signal prohibited behavior. OK, best politician. Pat. MR. BUCHANAN: Hasan Rouhani, the prime minister of -- the president, rather, of Iran. MR. MCLAUGHLIN: Eleanor. MS. CLIFT: I give it to Pope Francis, because he loves people, and that really is a key ingredient if you're going to be a politician. MR. MCLAUGHLIN: Are you stuck in that track, or what? MS. CLIFT: (Laughs.) MR. MCLAUGHLIN: Mort. MS. CLIFT: Stuck in what track? MR. MCLAUGHLIN: Pope Francis. MS. CLIFT: He deserves all the plaudits we can all give him. MR. MCLAUGHLIN: Mort. MR. ZUCKERMAN: Hillary Clinton, who kept herself out of the dispute of "Obamacare," and therefore preserved all that she needs for the next presidential campaign. MR. MCLAUGHLIN: Clarence. MR. PAGE: Well, I give it to Governor Chris Christie of New Jersey for walking a tightrope between different factions, if he doesn't get bogged down by some little bridge scandal by the end of the year. (Laughs.) MR. MCLAUGHLIN: Excellent, Pat -- I mean, Clarence. Best politician is Vladimir Putin. He moved Ukraine away from the West. He wrested control over the Syrian crisis away from Obama. No other statesman played his hand so deftly in 2013. OK, worst politician. Pat. MR. BUCHANAN: Mayor Rob Ford of Toronto, probably. And the silver goes to Anthony Weiner, your friend. (Laughter.) MS. CLIFT: Pat, I have to agree with you on that. But I would add Ted Cruz to the list, because in his short year as a senator he's managed to offend virtually all the Republicans in the Senate, which was really tough, because they're his party. MR. MCLAUGHLIN: Mort. MR. ZUCKERMAN: Well, I'm putting my vote in for the San Diego mayor, Bob Filner. I think 17 women have now basically asserted that they've had sexual harassment moments with him. That is no small achievement for a public figure. MR. MCLAUGHLIN: Clarence. MR. PAGE: (Laughs.) Well, I -- well, I think Rob Ford wins the international prize. I'll give Ted Cruz the domestic award. (Laughs.) MR. MCLAUGHLIN: The worst politician is Egypt's former president, Mohamed Morsi. The army gave him an ultimatum to quit the Muslim Brotherhood and reconcile with the political opposition. Morsi refused. The army ousted him. And Morsi is now on trial. Worst politician. OK, the most defining political moment. Pat Buchanan. MR. BUCHANAN: August. The American people rise up and say no to Barack Obama's war on Syria. MR. MCLAUGHLIN: Eleanor. MS. CLIFT: The 16-day government shutdown. MR. MCLAUGHLIN: Mort. MR. ZUCKERMAN: I would say President Obama, his red line that he drew; his public assertion of that red line. And then he walked away from it, undermining his credibility both at home and abroad. MR. MCLAUGHLIN: Very well stated, Mort -- (ripped from me ?), though. Clarence. MR. PAGE: I think Democrats ending the 60-vote filibuster rule in the Senate is emblematic of the state of gridlock in the city. MR. MCLAUGHLIN: The most defining political moment is Obama's on-air apology for misleading Americans into believing him when he promised they could keep their health insurance. OK, turncoat of the year. Pat Buchanan. MR. BUCHANAN: Edward Snowden. MR. MCLAUGHLIN: That's it? MR. BUCHANAN: That's a pretty good name. (Laughs.) MS. CLIFT: That -- yeah, that pretty much says it all. MR. MCLAUGHLIN: Eleanor. MS. CLIFT: I would add Marco Rubio to that, who championed immigration reform and then campaigned against the bill that he helped create. MR. MCLAUGHLIN: Mort. MR. ZUCKERMAN: Well, if you're talking raincoats, as a turncoat, I would put Anthony Weiner as the man of the year. MR. MCLAUGHLIN: Well stated. Clarence. MR. PAGE: Governor Lincoln Chafee went from Republican to independent to Democrat, his latest change this year. MR. MCLAUGHLIN: All right, let's try some originality. Listen closely. The turncoat of the year is French actor Gerard Depardieu. In January, Depardieu relinquished his French citizenship in favor of a Russian passport to avoid new wealth taxes imposed by the socialist government of Francois Hollande. You got me so far, Pat? MR. BUCHANAN: Uh-huh. (Acknowledging.) MR. MCLAUGHLIN: That hiked Depardieu's tax bracket from 41 percent to 75 percent. So he went to Russia. OK, the most boring. MR. BUCHANAN: He didn't go to Russia. He went to Belgium. MR. MCLAUGHLIN: No, he went to Russia. MR. BUCHANAN: Well, he might have gone to visit. (Laughs.) MS. CLIFT: He doesn't (look ?) Russian. MR. BUCHANAN: So would you if you were taxed 75 percent. (Laughs.) MR. MCLAUGHLIN: Read the whole story. MR. BUCHANAN: OK. MR. MCLAUGHLIN: The most boring. MR. BUCHANAN: Harry Reid. MR. MCLAUGHLIN: Harry Reid? MR. BUCHANAN: (Laughs.) MR. MCLAUGHLIN: Is that it? MR. BUCHANAN: Well, yes. MS. CLIFT: I feel compelled -- MR. BUCHANAN: There are some Republicans in there too. (Laughs.) MR. MCLAUGHLIN: Eleanor. MS. CLIFT: I feel compelled to defend Harry Reid. He's a good legislative mechanic. He's not the best -- MR. BUCHANAN: OK, I agree. MS. CLIFT: -- front man on TV. Most boring is the 40-odd attempts to repeal "Obamacare." MR. MCLAUGHLIN: Mort. MS. CLIFT: Going nowhere. MR. ZUCKERMAN: It was Ron Paul droning on for hours and hours and hours. MR. MCLAUGHLIN: Clarence. MR. PAGE: Ted Cruz droning on for hours and hours until he got to "Cat in the Hat." That was the high point. MR. MCLAUGHLIN: All right, here's more wisdom for you. The most boring are reports that on international tests, Americans fall behind on math and science. What you don't hear is that America ranks number two in the world, top 10 countries, for economic innovation. So there. OK, most charismatic. Pat Buchanan. MR. BUCHANAN: Will and Katherine, the duke and duchess of Cambridge, and the new papoose. (Laughs.) MR. MCLAUGHLIN: Eleanor. MS. CLIFT: OK. U.S. Senator Cory Booker from New Jersey, who went from Newark mayor to becoming the only elected black senator in a body of 100, basically on the strength of his use of social media. He's got a great Twitter following -- millions. MR. MCLAUGHLIN: Well stated, Eleanor. Mort. MR. ZUCKERMAN: Well, internationally it's Pope Francis. But domestically it's Chris Christie, the governor of New Jersey. MR. MCLAUGHLIN: That's good too, Mort. Clarence. MR. PAGE: I give it to the late Nelson Mandela, whose strength as a charismatic leader lasted even after he passed. MR. MCLAUGHLIN: Very well stated. The most charismatic is World Trade Organization director -- watch this, Pat -- General Roberto Azevedo. He has resurrected the WTO back into relevancy after taking the lead in negotiating the Bali package. It includes a trade facilitation agreement that will make it easier to flow goods around the world. Next success for Azevedo: The 12-year-old Doha Round of negotiations. Good work, Roberto. Check out the story in Politico. MR. MCLAUGHLIN: Can you stand the excitement? MS. CLIFT: (Laughs.) I know. MR. BUCHANAN: (Laughs.) MR. MCLAUGHLIN: Do you realize the importance of the WTO? MR. BUCHANAN: I know it. I -- MR. MCLAUGHLIN: See that. Your vision is so narrow. MR. BUCHANAN: I opposed its creation, John. (Laughs.) MR. MCLAUGHLIN: (Inaudible.) OK, bummest rap. Pat Buchanan. MR. BUCHANAN: The big lie that the tea party shut down the government. They never voted to shut down the government. MR. MCLAUGHLIN: Eleanor. MS. CLIFT: The big lie -- or the bummest rap: Susan Rice doctored the talking points on Benghazi; had nothing to do with it. MR. BUCHANAN: Who did? (Laughs.) MR. MCLAUGHLIN: Mort. MS. CLIFT: She didn't. (Laughs.) CIA, Pat. MR. ZUCKERMAN: The question -- the stop, question and risk (sic/means frisk) in New York, that that is a racist policy, because it -- MR. BUCHANAN: You mean stop and frisk? MR. ZUCKERMAN: Stop and frisk, excuse me -- because it was disproportionately focused on minorities, who were the ones who were the most vulnerable to the crime that it was trying to prevent. MR. MCLAUGHLIN: Bum rap. MR. ZUCKERMAN: Bum rap. MR. MCLAUGHLIN: Clarence. MR. PAGE: Accusation of a Benghazi cover-up on the part of the administration; just hasn't held water. MR. MCLAUGHLIN: The bummest rap is the rap that Apple evades $9 billion a year in U.S. taxes by keeping its earnings overseas. Apple CEO Tim Cook was hauled before a Senate committee, which finally acknowledged that Apple is in full compliance with U.S. tax law. Senator Rand Paul warned that CEOs who have not done anything illegal should not be dragged before Congress. Paul is right. OK, fairest rap. Pat Buchanan. MR. BUCHANAN: Fairest rap? MR. MCLAUGHLIN: Fairest rap. MR. BUCHANAN: The charge that Barack Obama did not tell the American people the truth and the fact that his credibility has sunk as a consequence. It is deserved. MR. MCLAUGHLIN: Yeah, you paused an awfully long time. Were you just thinking of the fairest rap? MR. BUCHANAN: No, I was thinking of another category. MR. MCLAUGHLIN: You're supposed to prepare for this show. MR. BUCHANAN: (Laughs.) MR. MCLAUGHLIN: Fairest rap. MS. CLIFT: I would phrase it slightly differently. I think the president underestimated the difficulty of remaking basically a sixth of the U.S. economy. But "Obamacare" will eventually be a huge success -- MR. MCLAUGHLIN: Mort. MS. CLIFT: -- and as much a part of American life as Medicare. MR. ZUCKERMAN: I'm glad I'm following -- MR. MCLAUGHLIN: All right, let's keep it rolling, quickly. MR. ZUCKERMAN: I would say the absolute incompetence of the website for "Obamacare" that basically revealed the unbelievable incompetence of the Obama administration in dealing with this issue. That's the fairest rap. MR. PAGE: Let me sum it up. MR. MCLAUGHLIN: Is that the fairest rap? MR. PAGE: Let me sum it up. The fairest rap is that Barack Obama thought that "Obamacare" was going to sell itself once it was passed. That was the biggest mistake. MR. MCLAUGHLIN: Close, but no reward. The fairest rap is the Republican rap that "Obamacare" should have been delayed for a year. The major embarrassment is not with the rollout, October 1st rollout of the law, coupled with Obama himself delaying key features of the Affordable Care Act. They proved that the GOP was right. The law should have been delayed. Fairest rap. OK, best comeback. Pat Buchanan. MR. BUCHANAN: The Egyptian army. They came back -- (laughs) -- and overthrew the Muslim Brotherhood -- MR. MCLAUGHLIN: Eleanor. MR. BUCHANAN: -- and seized power. MS. CLIFT: Clever. Speaker Boehner, finally, in the last days of the congressional session, rising up against the right-wing forces, saying it's ridiculous that they have this veto and hold on his party. MR. MCLAUGHLIN: Mort. MR. ZUCKERMAN: Secretary of State John Kerry, who came from being a relatively innocuous senator to being a real force in the Obama administration as the secretary of state. MR. MCLAUGHLIN: Well stated. Clarence. MR. PAGE: Good for -- I say former South Carolina Governor Mark Sanford, who I thought was lost on the Appalachian Trail, but now he's in Congress. (Laughs.) MR. MCLAUGHLIN: OK, brace yourself, Eleanor. The best comeback goes to the NRA, which appeared on the ropes after President Obama decided to push for gun control after Adam Lanza's Sandy Hook Elementary School murder spree. The NRA, buttressed by 2 million new members, handed Obama a political defeat. OK, most original thinker. Pat Buchanan. MR. BUCHANAN: The scientific team that found the Higgs boson, the God particle, John; the missing particle in -- MR. MCLAUGHLIN: Right, right, right. MR. BUCHANAN: OK. MR. MCLAUGHLIN: Yeah. That's it? (Laughter.) Eleanor. MS. CLIFT: Jeff Bezos, who envisions drones delivering packages from Amazon to our front door, and who also purchased The Washington Post. And I look forward to how he's going to reinvigorate a favorite property -- MR. MCLAUGHLIN: Yeah. MS. CLIFT: -- of this country. MR. MCLAUGHLIN: Mort. MR. ZUCKERMAN: Pope Francis, who has brought the Catholic church into the 21st century in a brilliant and widely appealing way. MR. MCLAUGHLIN: Clarence. MR. PAGE: Google's driver-free cars. Just don't ask me to ride one. MR. MCLAUGHLIN: The most original thinker is Michael Fumento, an investigative writer and attorney living in Colombia. Fumento has painstakingly documented the unfulfilled and erroneous predictions of climate-change computer models. Now a growing list of scientists reject the so-called consensus that manmade climate change is real. Fumento's patient debunking of the prevailing orthodoxy makes him the most original thinker of 2013. OK. Most stagnant thinker. Pat Buchanan. MR. BUCHANAN: The neocons compare the freeze on Iran's nuclear program to Neville Chamberlain at Munich again. MR. MCLAUGHLIN: Eleanor. MS. CLIFT: I'll give you an amen on that. MR. BUCHANAN: (Laughs.) MS. CLIFT: And I would add the Republican governors who are refusing to expand Medicaid and are hurting their own constituents. MR. MCLAUGHLIN: Thank you, Eleanor. MR. BUCHANAN: Those (lousy ?) governors. (Laughs.) MR. MCLAUGHLIN: Amen chorus over there. Mort. MR. ZUCKERMAN: I would -- the tea party would be my candidate here, because I think they've just repeated themselves to the point where nobody's listening to them outside of their own constituency. MR. MCLAUGHLIN: Well, they're coming back, Mort. Clarence. MR. PAGE: Senator Rand Paul for plagiarizing WikiLeaks in a speech. MR. MCLAUGHLIN: Most stagnant thinker is a joint award to Rahm Emanuel and Ezekiel Emanuel. The two Emanuel brothers were so fixated on the passage of "Obamacare" in the first term that they let President and First Lady Michelle Obama make false promises about Americans keeping their insurance and doctors. Stagnant thinking -- the Emanuel brothers. OK, best photo op. Pat Buchanan. MR. BUCHANAN: Obama at the Mandela funeral flirting with that Danish pastry while Michelle gives her thousand-yard stare. MR. MCLAUGHLIN: Eleanor. MS. CLIFT: The Danish pastry was the prime minister of Denmark. (Laughs.) MR. BUCHANAN: (Laughs.) MR. MCLAUGHLIN: Have you seen her picture? MS. CLIFT: Yeah, but Pat needs a little educating in how to talk to women. MR. MCLAUGHLIN: Quickly. MS. CLIFT: OK. I like the photo op on Air Force One of President Bush showing photos of his paintings to Hillary Clinton. I like that kind of bipartisanship. MR. MCLAUGHLIN: Very -- (inaudible). Mort. MR. ZUCKERMAN: I love the photo of the president with the Danish prime minister, which I have to say -- MS. CLIFT: Good, Mort. MR. ZUCKERMAN: -- really, really helped -- it kept me going for a couple of days after that. There's hope for all of us. MR. MCLAUGHLIN: Did you see the full-length one on page one of the -- MR. ZUCKERMAN: Yes, I saw them all. MR. MCLAUGHLIN: -- New York Post? MR. ZUCKERMAN: I saw the full -- MR. MCLAUGHLIN: Clarence. MR. PAGE: Reunion of Governor Chris Christie and Barack Obama on the beach in May. It was, what, 2012 redux. MR. MCLAUGHLIN: I have to go along with this. The best photo op is the picture of very chummy President Obama taking a selfie with Danish female Prime Minister Helle Thorning-Schmidt at the memorial service for Nelson Mandela while First Lady Michelle Obama glares at both. Check out the New York Post website for the series of pictures that depict the unfolding drama. OK. The enough, already award. Pat Buchanan. MR. BUCHANAN: Alec Baldwin's serial battles with the paparazzi in Greenwich Village. (Laughs.) MR. MCLAUGHLIN: Excellent. Eleanor. MS. CLIFT: Tea party. MR. MCLAUGHLIN: Is that it? MS. CLIFT: Enough, already. Yes, tea party. (Laughs.) MR. MCLAUGHLIN: Well, Eleanor, that's quite -- (inaudible). MR. ZUCKERMAN: Italian Prime Minister Silvio Berlusconi, who was finally sentenced to four years in prison after God knows how many years of ripping off everything, and everything Kardashian. Those are the two categories. MR. MCLAUGHLIN: The Kardashians. MR. ZUCKERMAN: Yes, absolutely. MR. MCLAUGHLIN: Really? MR. ZUCKERMAN: I've had enough of them. MR. MCLAUGHLIN: Clarence. MR. PAGE: Anthony Weiner's political career. May it stay buried this time. MR. MCLAUGHLIN: The enough, already award goes to global warming, the theory that now masquerades under the pseudonym of climate change. Even its most honest supporters now admit that there has been no increase in the earth's surface temperatures for 15 years. It's time to admit the theory is flawed. OK, the worst lie. Pat Buchanan. MR. BUCHANAN: If you like your health care plan, you can keep your health care plan, period. MR. MCLAUGHLIN: What do you mean by that? MR. BUCHANAN: (Laughs.) MR. MCLAUGHLIN: What do you mean? MR. BUCHANAN: Eleanor will understand. (Laughs.) MS. CLIFT: That was the president's oft-stated comment when he was referring to people who already have insurance. And it was -- it did not prove to be fully accurate. (Laughter.) I will give my -- MR. MCLAUGHLIN: Don't overstate it. MS. CLIFT: I would give the lie to director of international intelligence James Clapper, who told a congressional committee that the NSA was not collecting data on millions of Americans. He later had to apologize for what he called his least most untruthful answer. In other words, he lied. MR. MCLAUGHLIN: Yeah, but he's a (normal ?) guy. Did you see that one-hour interview with him? MS. CLIFT: On "60 Minutes"? MR. MCLAUGHLIN: I don't know where it was, but it was one hour. It wasn't an interview. He was giving a prepared talk, and you may have found it on -- you may find it on CNN. MS. CLIFT: Well, he admitted he lied. MR. MCLAUGHLIN: Quickly. MR. ZUCKERMAN: The number one, you have to add you can keep your health insurance and your doctor, both of which, I think, qualify. But there's one other: Rand Paul, who said, and I quote, "extending unemployment benefits is a disservice to the recipient, because it causes them to become part of the perpetual unemployed." MR. MCLAUGHLIN: Clarence. MR. PAGE: Without being redundant, I've never used performance- enhancing drugs and I never will. Lance Armstrong. MR. MCLAUGHLIN: Wow. MR. ZUCKERMAN: Wow, yes. MR. MCLAUGHLIN: (He's ?) still kicking that around. The worst lie is that wind energy is environmentally friendly. Wind turbines kill thousands of birds, including rare and endangered species like golden and bald eagles. Also, the broad environmental impact of these birds and bats, (their kills ?) on insect population growth, the environment is little understood. OK, capitalist of the year. Pat Buchanan. MR. BUCHANAN: The Ayatollah Khamenei, whom I just discovered, John, has $95 billion salted away, which he has control of. He's done a great job. MR. MCLAUGHLIN: Eleanor. MS. CLIFT: Capitalist of the year, JPMorgan Chase, a $13 billion fine, which is for their practices that they used in capitalizing on derivatives and home mortgages. It's -- unfortunately it's chump change to them, and they can deduct a lot of it. But finally, some of the big banks and investment companies are getting punished, belatedly. MR. MCLAUGHLIN: You're beating up on capitalists all the time, Eleanor. Mort. MR. ZUCKERMAN: George Mitchell, the fracking pioneer from Texas who died this year at the age of 94. He is credited with pioneering the economic extraction of shale gas through the process of fracking, which has done as much to change the entire world as any other businessman I know. MR. MCLAUGHLIN: Clarence. MR. PAGE: Jeff Bezos for suckering up in the media into taking his drone delivery plan seriously. MR. MCLAUGHLIN: 2013's capitalist of the year award goes to the world's richest woman, Christy Walton. The Wal-Mart heiress has a net worth of -- get this -- $35.4 billion. Her late husband, John Walton, was a former Green Beret and son of Wal-Mart founder Sam Walton. OK, honorable mention. Pat Buchanan. MR. BUCHANAN: Vladimir Putin, John, who has made dramatic moves, not only in the Middle East but worldwide. He's trying to make himself the leader, basically, of conservative traditionalist, nationalist forces against cultural and moral imperialism, as represented by the United States of America of Barack Obama. MR. MCLAUGHLIN: Eleanor. MS. CLIFT: I'm totally overdosed on Putin. And it makes me want to point out that Michelle Bachelet just won an extraordinarily strong victory for a second term, not consecutive, in Chile. And she ran against a woman from the right. And it was the first time in this very machismo country that two women faced off against each other, and the socialist won. But actually, my real honorable mention is the victims of violence in this country, from the Boston Marathon to the Washington Naval Yard to the 28 school shootings that have happened in the year since Sandy Hook. So maybe the NRA has come back, John, but that's not good news. MR. MCLAUGHLIN: Well, it was a tough year. (Inaudible.) Mort. MR. ZUCKERMAN: Stephen Harper, the prime minister of Canada, who has run that government and led that country in the most extraordinary way, being able to resist the creeping effects of a weakened American economy, which is directly to the south, and has a huge impact on Canada. And he's done a major job at keeping that country together in terms of all the problems and tensions between the French- and the English-speaking people. MR. MCLAUGHLIN: He's also a fan of the McLaughlin Group. True or false? MR. ZUCKERMAN: That might be so. MR. MCLAUGHLIN: They see it in Canada, do they not? MR. ZUCKERMAN: Yes, they do. MR. PAGE: I'm glad to hear something more positive than Toronto Mayor Rob Ford coming out of Canada right now. But my honorable mention goes to Pope Francis, because he really revived the moral dimension of the income-inequality debate, which needs more attention in this country. Globalization and other economic forces have put new pressures on the working class, and now increasingly the lower middle class in the country. MR. MCLAUGHLIN: Well, if he's all that good, why do you only give him honorable mention? MR. PAGE: Because Malala Yousafzai, the 16-year-old Pakistani girl who was shot by the Taliban just for advocating education for girls, is staying on a global crusade that I think is going to make a real difference. MR. MCLAUGHLIN: So she's superior to the pope. MR. PAGE: In my view, in this year, on that scale, yes. MR. BUCHANAN: You've had Putin superior to the pope all day long. (Laughter.) MR. MCLAUGHLIN: Eleanor's on the right track. The honorable mention goes to Secretary of State John Kerry, who, in his first year in the job, has achieved a breakthrough in starting nuclear talks with Iran, helped defuse the Syrian crisis as a prelude to a January 22nd, 2014 peace conference, jumpstarted Israeli-Palestinian peace talks, and is actively mediating the Ukrainian standoff between pro-Russian President Yanukovych and pro-European protesters. It's good to have someone in the job who understands that diplomacy involves more than globetrotting handshakes and photo ops. I think you'd agree with that, wouldn't you, Pat? MR. BUCHANAN: Yeah. But, listen, John, there's one point. Look, John Kerry and Barack Obama, whatever you say, helped cause the Syrian crisis. They were running around talking about attacks and threatening bombings and red lines. And they had to climb down from that. And they were rescued thanks to your man of the year, your winner and all the rest of it, Vladimir Putin. MS. CLIFT: I don't think you can call this administration causing the Syrian crisis. That is a civil war within the country. MR. BUCHANAN: (Inaudible.) MR. ZUCKERMAN: The statement by the president that he was drawing a red line and walked away from it has undermined his credibility all through the region. We've lost the alliances, such as they were, with the Saudis and all the Sunni countries. We have a real problem that is brewing, in part because they no longer have confidence in the leadership of the United States. MS. CLIFT: And chemical weapons are being destroyed. MR. BUCHANAN: He had no right -- he has no right to issue a red line, which means we're going to go to war if the Syrians do something. Congress has not authorized any war on Syria. MR. MCLAUGHLIN: Did we give any award to the new head of state in Iran? MS. CLIFT: Yeah, Pat did. MR. BUCHANAN: I got Hasan -- I said the best politician is -- listen, John. MR. MCLAUGHLIN: Yeah. Well, I was paying attention to it, but somehow that flew right over my head. (Laughter.) MS. CLIFT: I don't think -- pulling back from using lethal force, I do not see as a bad thing. I give the president kudos in the end for the way that the Syrian confrontation has worked out. MR. PAGE: (Inaudible.) That's OK in my book. MS. CLIFT: That's right. Exactly. MR. PAGE: Right on. MS. CLIFT: Thank you, Clarence. MR. MCLAUGHLIN: That's in your book too. MR. PAGE: You got it, pal. MR. MCLAUGHLIN: Yeah, but who's responsible for the pullback? MR. PAGE: The pullback? MR. MCLAUGHLIN: Yeah. MR. PAGE: The most interesting man in the world, the Dos Equis man, Vladimir Putin. (Laughs.) MS. CLIFT: (Laughs.) MR. MCLAUGHLIN: The editorial -- the editorial in The New York Times, the op-ed in The New York Times. MR. PAGE: Yes. MR. MCLAUGHLIN: It suddenly broke in half, didn't it? MR. BUCHANAN: Yeah. MR. MCLAUGHLIN: It broke the situation in half. MR. BUCHANAN: Send a tape of this show to Putin, John. (Laughter.) MR. MCLAUGHLIN: Dedicated to him? MR. BUCHANAN: Send it to him. MR. MCLAUGHLIN: Will you sign the letter? MR. BUCHANAN: I'll sign it, yeah. MR. MCLAUGHLIN: OK. Well, we'll think about this. Maybe it should be a joint signature from everyone. MR. BUCHANAN: (Laughs.) MR. MCLAUGHLIN: OK, person of the year, Pat Buchanan. MR. BUCHANAN: Xi Jinping of China. He has declared a Monroe doctrine in the East China Sea and the South China Sea and the Yellow Sea and the Taiwan Straits, claimed every island there, is imposing an air defense identification zone, which could lead to trouble with the Japanese, the Americans and the South Koreans, the Philippines and the Vietnamese. This is historic, John. He is trying to push the United States back away from the first chain of islands in the Pacific. MR. MCLAUGHLIN: Interesting. Eleanor. MS. CLIFT: Secretary of State John Kerry, who, through his travels and his willingness to take risks and pushing at the White House and demanding, really, that he press ahead on important agendas, has opened up two potential areas for big breakthroughs, one with Iran and one in the Middle East between the Israelis and Palestinians. MR. MCLAUGHLIN: Well stated. Mort. MR. ZUCKERMAN: Every under-25 techie who invents a new app -- and this has become a part of a new technological revolution that is transforming America in directions that we can't even anticipate, but it's already had huge effects on the way the business world and the private world conducts itself. MR. MCLAUGHLIN: Clarence. MR. PAGE: Sixteen-year-old Malala Yousafzai, the Pakistani girl who was shot by the Taliban, survived, because she's campaigning for education for kids. She is -- for girls. She's exciting a new generation that's coming up now. MR. MCLAUGHLIN: In Afghanistan. MR. PAGE: Around the world. MR. MCLAUGHLIN: 2013's person of the year is obviously Vladimir Putin. He seized the world's spotlight on the Syrian crisis and drew Ukraine back into the Russian orbit -- both stunning demonstrations of the relevance of Russia as a world power and a relative decline of American influence. On that note, Merry Christmas and happy holidays. Bye-bye. (C) 2013 Federal News Service