basis

classification

The mutex

  1. A mechanism used in multithreaded programming to prevent two threads from simultaneously reading and writing to the same common resource, such as a global variable, to ensure the integrity of shared data operations.
  2. Implementation: Slice the code into critical sections.
  3. classification
    • Recursive lock:@synchronized,pthread_mutex(recursive),NSRecursiveLock.
    • Non-recursive lock:NSLock,pthread_mutex.

spinlocks

  1. Spin lock = mutex + busy etc
  2. The thread repeatedly checks that the lock variable is available. Because the thread keeps executing during this process, it is a busy wait. Once a spin lock is acquired, the thread holds it until the display releases the spin lock.
  3. Spin-locks avoid the scheduling overhead of the process context and are therefore effective in situations where threads block only for short periods of time.

Read-write lock

  1. Special spinlocks, which divide visitors to a shared resource into readers and writers, improve concurrency compared to spinlocks, because in a multiprocessor system, multiple readers are allowed to access the shared resource at the same time, with the maximum possible number of readers being the actual number of logical cpus.
  2. Writers are exclusive; a read/write lock can have only one writer or more readers at a time (depending on the number of cpus), but not both readers and writers.
  3. If the read-write lock currently has no reader and no writer, then the writer can acquire the lock immediately, otherwise it must keep spinning until there are no writers/readers.
  4. If the read-write lock has no writer, the reader can acquire the lock immediately, otherwise the reader must spin until the writer releases the lock.

Conditions for the lock

  1. A conditional variable that goes to sleep (that is, locked) when some resource requirement of the process is not met. When the resource is allocated, the conditional lock is opened and the process continues.
  2. NSCondition,NSConditionLock.

A semaphore

  1. semaphoreMutex is a more advanced synchronization mechanism. Mutex is a special case of a semaphore with a value of 0/1 only.
  2. Semaphores can have more value space for more complex synchronization, rather than just mutual exclusion between threads
  3. dispatch_semaphore

Common lock

  1. OSSpinLock
  2. dispatch_semaphore
  3. os_unfair_lock
  4. pthread_mutex_t
  5. NSLock
  6. NSCondition
  7. pthread_mutex_t(recursive)
  8. NSRecursiveLock
  9. NSConfitionLock
  10. @synchronized

The performance comparison

@synchronized

For example, we now have code like this in our main function

int main(int argc, char * argv[]) {
    NSString * appDelegateClassName;
    @autoreleasepool {
        appDelegateClassName = NSStringFromClass([AppDelegate class]);
        @synchronized (appDelegateClassName) {
        }
    }
    return UIApplicationMain(argc, argv, nil, appDelegateClassName);
}
Copy the code

Generate an intermediate file using xcRun-sdk iphoneOS clang-arch arm64-rewrite-objc main.m. You can see that the @synchronized word is no longer found in this file. The lock part of the code looks like this

{
    id _rethrow = 0;
    id _sync_obj = (id)appDelegateClassName;
    objc_sync_enter(_sync_obj); / / the point!
    try {
        struct _SYNC_EXIT { _SYNC_EXIT(id arg) : sync_exit(arg) {}
        ~_SYNC_EXIT() {objc_sync_exit(sync_exit); }/ / the point!
        id sync_exit;
        } _sync_exit(_sync_obj);
    } catch(id e) {_rethrow = e; }Copy the code

It is not hard to see that the core keys are objc_sync_Enter and objc_sync_exit. Go to the objC source code to see the implementation

int objc_sync_enter(id obj) {
    int result = OBJC_SYNC_SUCCESS;
    if (obj) {
        SyncData* data = id2data(obj, ACQUIRE); / / the point!...// Data lock, corresponding to tryUnlock in objc_sync_exit
        data->mutex.lock(a); }else{...// if obj is empty, do nothing
    }
    return result;
}

int objc_sync_exit(id obj)
{
    int result = OBJC_SYNC_SUCCESS;
    if (obj) {
        SyncData* data = id2data(obj, RELEASE); / / the point!
        // Unlock data, corresponding to the lock in objc_sync_Enter
        bool okay = data->mutex.tryUnlock(a); ...// Error handling}}else {
        // if obj is empty, do nothing
    }
    return result;
}
Copy the code
// The SyncData structure
typedef struct alignas(CacheLineSize) SyncData {
    struct SyncData* nextData; // Form to linked list
    DisguisedPtr<objc_object> object; // Associate objects
    int32_t threadCount; // The number of threads currently using the block
    recursive_mutex_t mutex; / / recursive locking
} SyncData;
Copy the code

SyncData* ID2Data (ID object, enum usage why)

id2data(id object, enum usage why)

TLS: Thread Local Storage. The operating system provides a separate private space for threads, usually with limited capacity. Common apis: pthread_key_create(), pthread_getSpecific (),pthread_setspecific(),pthread_key_delete()

enum usage { ACQUIRE, RELEASE, CHECK };
Copy the code
  1. fromsDataListsIn order toobjforkeyTo obtain the lock and the corresponding storageSyncDataThe list of
spinlock_t *lockp = &LOCK_FOR_OBJ(object);
SyncData **listp = &LIST_FOR_OBJ(object);
Copy the code
/ / related macro
#define LOCK_FOR_OBJ(obj) sDataLists[obj].lock
#define LIST_FOR_OBJ(obj) sDataLists[obj].data

// global static variables sDataLists
static StripedMap<SyncList> sDataLists;

// SyncList
struct SyncList {
    SyncData *data;
    spinlock_t lock;
    constexpr SyncList(a) : data(nil), lock(fork_unsafe_lock) {}};Copy the code
  1. If temporary storage space is supported fromtlsIf anydataExisting and stored internallyobjectFor the incomingobjectObject,whyforswitchOperation and return after operationdata
SyncData *data = (SyncData *)tls_get_direct(SYNC_DATA_DIRECT_KEY); ...switch(why) {
            case ACQUIRE: {
                lockCount++;
                tls_set_direct(SYNC_COUNT_DIRECT_KEY, (void*)lockCount);
                break;
            }
            case RELEASE:
                lockCount--;
                tls_set_direct(SYNC_COUNT_DIRECT_KEY, (void*)lockCount);
                if (lockCount == 0) {
                // When lockCount is 0, unlock!
                    tls_set_direct(SYNC_DATA_DIRECT_KEY, NULL);
                    OSAtomicDecrement32Barrier(&result->threadCount);
                }
                break;
            case CHECK:
                break;
            }
Copy the code
  1. [If temporary space is not supported] or [second step data is empty], obtaincache, if there is cache, andlistinitem->data->objectFor the incomingobject, the implementation ofswitchAction and return thisdata

If TLS temporary space is supported, go to the second step. If TLS temporary space is not supported or does not exist, go to the cache. Since TLS is currently supported on all MAC /ios, the third step will not be covered.

Copy the code
  1. If steps 2 and 3 are empty, traverse the listp to perform the lock
OSAtomicIncrement32Barrier(&result->threadCount);
Copy the code
  1. Create a new SyncData and add it to the list
posix_memalign((void**)&result, alignof(SyncData), sizeof(SyncData));
result->object = (objc_object *)object;
result->threadCount = 1;
new (&result->mutex) recursive_mutex_t(fork_unsafe_lock);
result->nextData = *listp;
*listp = result;
Copy the code
  1. Storage [Analysis only heretlsTemporary Storage Space Scheme
tls_set_direct(SYNC_DATA_DIRECT_KEY, result);
tls_set_direct(SYNC_COUNT_DIRECT_KEY, (void*)1);
Copy the code

Core processing

  • Storage structure
    • Global static hash tablesDataLists
    • Elements forSyncList->SyncData
  • Storage solution
    • TLS
    • Cache
  • Add lock, unlock implementation
    • OSAtomicIncrement32Barrier(&result->threadCount);
    • OSAtomicDecrement32Barrier(&result->threadCount);
  • Reentrant, recursive, multithreaded implementation reasons
    • TLS guarantees threadCount to indicate how many threads have locked the lock object
    • LockCount marks how many times it has come in

NSLock & NSRecursiveLock

  • Underlying implementation:pthread
  • NSLock
  • NSRecursiveLock

NSCondition

  • NSConditionThe object actually acts as aThe lockAnd aThread checker
    • Lock: Primarily to protect data sources when detecting conditions and perform tasks triggered by conditions
    • Thread checker: Determines whether to continue running a thread based on conditions, that is, whether the thread is blocked
  • Commonly used API
// The data source can be accessed and modified only once by multiple threads at the same time. The commands of other threads must wait outside the LOCK until the UNLOCK is accessed
[condition lock];

// Use with lock
[condition unlock];

// Make the current thread wait
[condition wait];

// Let the CPU signal the thread to stop waiting and continue executing
[condition signal];
Copy the code

NSConditionLock

  • NSConditionLockOnce one thread acquires the lock, the other threads must wait.conditionIt’s integers, internally comparing conditions by integers
  • Commonly used API
// Indicates that the lock expects to acquire the lock. If no other thread acquires the lock (and does not need to judge the internal condition), it can execute the following code; If another thread has already acquired the lock (conditional/unconditional), wait until another thread has unlocked it
[lock lock];

// If no other thread has acquired the lock, but the condition inside the lock is not A, it still cannot acquire the lock and still waits
// If the internal condition is A and no other thread acquires the lock, it enters the code area and sets it to acquire the lock, and any other thread will wait for the code to complete until it unlocks[lock lockWithCondition:A condition];// Release the lock and set the internal condition to A. [Change the current value first, then broadcast][lock unlockWithCondition:A condition];// If the thread is locked (the lock is not acquired) and the time is exceeded, the thread is no longer blocked. The return value is NO, it does not change the state of the lock, the purpose of this function is to achieve both state processing.
return= [lock lockWhenCondition:A condition beforeDate: specify condition]Copy the code

The sample analysis

NSConditionLock *conditionLock = [[NSConditionLock alloc] initWithCondition:2];
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0), ^{
    [conditionLock lockWhenCondition:1];
    NSLog(Thread 1 "@");
    [conditionLock unlockWithCondition:0];
});

dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{
    [conditionLock lockWhenCondition:2];
    sleep(0.1);
    NSLog(Thread 2 "@");
    [conditionLock unlockWithCondition:1];
});

dispatch_async(dispatch_get_global_queue(0.0), ^{
   [conditionLock lock];
   NSLog(Thread @ "3");
   [conditionLock unlock];
});
Copy the code

The output is 3 -> 2 -> 1

  1. Thread 1 call[conditionLock lockWhenCondition:], because the current condition is not satisfied. So enter waiting and release the current mutex
  2. Now the current thread 3 calls[conditionLock lock].It’s essentially a call[conditionLock lockBeforeDate:], there is no need to compare conditional values, so thread 3 prints
  3. Thread 2 execution[conditionLock lockWhenCondition:], thread 2 prints because the condition value is met, and calls when the print is complete[conditionLock unlockWhenCondition:]In this case, value is set to 1 and broadcast is sent. Thread 1 receives the current signal, wakes up and prints.