# CAL: Core-Aware Lock for the big.LITTLE Multicore Architecture
## 2 Background and Research Motivation
### Motivation  
#### 2.3.1 Problem Statement  
For multiprocessing programs, the lock works as a coordinator to synchronize operations among threads on CPU, and should give each thread to enter the critical section with an equal probability (i.e., locking fairness), preventing any thread from being blocked for a long time. These popular lock algorithms, such as FIFO lock, competition-based lock, cohort lock, and their variants, always ensure locking fairness explicitly or implicitly. FIFO lock assigns the lock to the thread/process following their coming order. TAS (Test-and-Set) lock, one of the variants of competition-based lock, lets these threads call an atomic instruction to apply for the lock, and the success rate of atomic operations is equal between cores. Cohort lock is suitable for NUMA architecture; it prefers to assign the lock inside one CPU socket, reducing the traffic transmission overhead across sockets. This scheme sacrifices the short-term fairness of locks, but by periodically rotating on each NUMA node, cohort lock provides a long-term fairness [10]. Running on homogeneous computing architecture, these locks work effectively.  
However, the above locks become sub-optimal solutions on big.LITTLE multicore architecture, the reason comes from the following folds. As shown in Figure 2. It shows the issue exists in the FIFO-based locks. Due to the strict locking order, the little core has the same chance as the big core to obtain the lock and execute the critical section, but for the same critical section, the little core runs more slowly than the big core, which causes more critical paths to stay on the little core much longer, resulting in locking unfairness and a decrease in throughput. Otherwise, competition-based locks rely on atomic operations to lock. However, the success ratio of atomic operations is no longer the same between big core and little core, resulting in extreme unfairness. As shown in Figure 2(II), once the success rate of atomic operations is higher on the little core (we name it little-core-friendly), the big core almost cannot get the lock, resulting in a significant increase in tail latency. In addition, the critical path mainly falls on the slower little core; the throughput is also significantly reduced. On the other hand, when the success ratio of atomic operations is higher on the big core (we name it big-core-friendly), the throughput benefits from this condition, but the tail latency could be much longer, which is illustrated in Figure 2(III).  
To observe the fairness issue existing in lock, we conducted a preliminary experiment based on the 13 th Intel Core i5 processor, which contains 6 big cores and 4 little cores. Four locks (i.e., Ticket lock, spinlock, tas lock, and Cptltkt), which are used widely, are picked up to evaluate the performance deviation on big.LITTLE multicore architecture. The result is shown in Figure 1. As we discussed above, FIFO-based locks, such as ticket lock, suffer a throughput drop when beginning to schedule little core. Spinlock and tas lock are competition-based locks. The difference is that tas is big-core-friendly, so it has the highest throughput, but its tail latency rises significantly compared to FIFO-based locks. Spinlockhere shows little-core-friendly. As a result, both its throughput and tail latency collapse. Cptltkt lock exhibits a similar performance as ticket lock. All these lock algorithms suffer from performance issues.