1. 原子操作 (Atomic Operations)

编写多线程代码最重要的一点是：对共享数据的访问要加锁。

Shared data is any data which more than one thread can access.

原子操作(Atomic Operations)满足只有一个线程可以访问Shared data, 同时不需要加锁。

原子操作中的"原子"是不可分割的意思。

OSAtomic是OS X的原子操作库。

2. OSAtomic

OSAtomic函数在OSAtomic.h文件中，路径：/usr/include/libkern/OSAtomic.h

在用户域的代码中也可以使用OSAtomic函数。

#import <libkern/OSAtomic.h>

这些方法分为5类:

• Integer operations
• Fundamental operations
• Spinlocks
• Queues
• Memory barriers

整数类型

"Due to the finnicky and low-level nature of atomic operations, there are significant limits on data types

and alignments. Atomic operations are only available for 32-bit and 64-bit data types, and on some

platforms (PowerPC being the only OS X one that I know of) they are only available for 32-bit. Always

use data types with a guaranteed size, such as int32_t, rather than built-in types ilke int. " Ref[1]

地址对齐

"The values must also be aligned to their size. This means that the address of the value has to be

a multiple of the value's size. " Ref[1]

"Alignment should only be a worry if you're messing around with addresses trying to set up your own

packing or using packed structs. And, well, don't use atomic operations with those." Ref[1]

2.1 Integer Operations (整数操作)

x += 1; // 该操作不是原子的

x++; // 也不是原子的

OSAtomicAdd32()

OSAtomicIncrement()

OSAtomicDecrement()

OSAtomicOr() OSAtomicAnd() OSAtomicXor()

2.2 Fundamental Operations (基本操作)

整数操作概念上基于基本的原子操作: compare and swap, 即CAS.

CAS函数接受3个参数：old value, new value, a pointer to a variable.

如果variable的值和old value匹配，则将new value赋值给variable，并返回true.

CAS 如下：

bool CompareAndSwap(int old, int new, int *value)

    {

        if(*value == old)

        {

            *value = new;

            return true;

        }

        else

            return false;

    }

" If the new value is assigned and the function returns true then you can be absolutely certain

that the value transitioned directly from old tonew without any other intermediate value." Ref[1]

OSAtomic提供了OSAtomicCompareAndSwap函数族。

用CAS来实现 OSAtomicAdd32函数:

"First, fetch the original value. Then add to obtain a new value. Finally, use compare and swap

with the original and new values. If it failed, go back and try everything again." Ref[1]

  int32_t OSAtomicAdd32(int32_t howmuch, volatile int32_t *value)

  {

        bool success;

        int32_t new;

        do {

            int32_t orig = *value;

            new = orig + howmuch;

            success = OSAtomicCompareAndSwap32(orig, new, value);

        } while(!success);

        return new;

   }

TODO: 关键字  volatile

OSAtomicCompareAndSwapPtrBarrier()函数的使用：

ListNode *StealList(ListNode * volatile *head)

{

    bool success;

    ListNode *orig;

    do {

        orig = *head;

        success = OSAtomicCompareAndSwapPtrBarrier(orig, NULL, (void *)head);

    } while(!success);

 return orig;

}

"This kind of structure can be really useful in multithreaded programming. Many threads can safely

useAddNode to add new nodes to the structure. A worker thread can then use StealList to grab the

list and process it." Ref[1]

ABA Problem (ABA问题)

关于ABA问题参考: TODO　　

Ref[1] ABA Problem 这一节中讲解的很明了。

2.3 Spinlocks (自旋锁)

"A spinlock is a primitive type of lock that does not use any OS facilities." Ref[1]

普通锁的概念:

"A lock in general is a facility which provides mutual exclusion between threads.

Two threads attempt to acquire a lock. One succeeds, the other waits. When the first one unlocks the lock,

the second one then acquires it.

Generally, when the second thread is waiting, we want it to be blocked so that it does not take any CPU

time while it's blocked. This requires intervention by the OS to stop the thread, and start it again when unlocking.

This OS intervention comes with a certain amount of overhead that is not always desirable. " Ref[1]

普通锁需要系统OS的介入。

Spinlock的概念:

Spinlock很轻量，完全在用户空间，不需要OS介入。副作用是当线程在waiting时，该线程并不会blocked，

而是不停的检查spinlock直到其unlocked。

"Spinlocks perform very well when a lock is not contended (only one thread at a time is accessing it)

but perform poorly when a lock is contended for an extended period." Ref[1]

TODO: 那么适用spinlock的场景是什么呢?

You should generally use those higher-level (pthread_mutex, NSLock) abstractions, but spin locks are useful when performance

is absolutely critical and contention is rare.

2.4 Queues

"Unfortunately, after some additional investigation, I discovered that OSQueue

is not entirely thread safe and thus should not be used. Since I have no idea if or

when this will be fixed, you should avoid the use of OSQueue."  Ref[1]

TODO: OSQueue的调研

2.5 Memory Barriers (内存屏障，内存围墙)

"Some architectures reorder memory reads and writes for extra speed.

These reorderings are hidden from the program by the CPU, but they are not hidden

from code executing on other CPUs at the same time. This can cause serious problems." Ref[1]

Memory Barries 的作用:

"A memory barrier forces all all reads before the barrier to complete before any

reads after the barrier complete. The same goes for writes. Technically, there can be

separate barriers for reads and writes, but OSAtomic rolls them both into a single concept."

TODO: 使用OSMemoryBarrier 的例子。

3. OSAtomicIncrement64 vs. OSAtomicIncrement64Barrier

Reference

1. Friday Q&A 2011-03-04: A Tour of OSAtomic (AAAAA)

https://www.mikeash.com/pyblog/friday-qa-2011-03-04-a-tour-of-osatomic.html

2.

http://cocoadev.com/OSAtomic

3. 自旋锁spinlock剖析与改进  (未读)

http://kb.cnblogs.com/page/105657/