# CAL: Core-Aware Lock for the big.LITTLE Multicore Architecture
## 3 Design  
### Overview  
Traditional locks become sub-optical in big.LITTLE multicore architecture, mainly because the fairness of the lock is deteriorated, which is caused by the inherent asymmetry of cores. Therefore, we design a Core-Aware Lock for the big.LITTLE multicore architecture named CAL, based on the fairness computational model.  
The CAL is built on the ticket lock and MCS lock to perform lock reordering operations, as the ticket lock mainly deals with low contention and reduces lock paths. The MCS lock performs better under medium and high contention. Furthermore, we expanded the MCS node information for our reordering operation, including the enqueue time \(T^{enqueue}\), Individual execution time \(T^{alone}\), rearranger, the forward pointer (we expand the MCS queue into a double linked list) and \(at\_head\) indicate whether the node is at the head of the queue. Figure 4 shows the CAL lock structure and MCS node information. The bottom layer of the CAL lock structure contains a native ticket lock. In addition, CAL includes the pointers to the head and tail of the queue, \(pop\_flag\) indicates whether a thread is exiting the queue, and \(no\_steal\), whether to use a shorter lock path under low contention.  
The CAL algorithm is divided into three stages, as shown in Algorithm 1: the first stage is the core-aware queue insertion, which inserts the threads of requesting lock into the tail of the corresponding waiting queue according to the core type they are in. The  
Figure 4: CAL lock structure and MCS node information.  
Figure 3: Fairness and the slowdown ratio of ticket lock in big.LITTLE multicore architecture.  
second stage is the fairness-aware node reordering, which tunes the thread into the most suitable position in the current queue to maximize the fairness of the whole queue. The third stage is the item selection, which selects an item from the head of the big-core waiting queue and the head of the little-core waiting queue to obtain the underlying ticket lock. After the processing of the three stages, the big-core threads can obtain a certain degree of priority, maximizing the fairness of the system at the same time.  
```
1:int\(\textbf{CAL\_mutex\_lock}(CAL\_mutex\_lock)\{
2:if\(lock\_Ticket=UNILOCK\&\&lock\_no\_steal=0\)then
3: go to FastPath;
4:endif
5:// If FastPath is unavailable, the thread enqueues into the corresponding wait queue
6:\(node=\textbf{init\_node}(T^{enqueue},T^{alone},at\_head=0,rearranger=0, pre,next=NULL)\);
7:ifis_perf_core0 then
8:// Threads on performance cores are enrolled in the wait queue for performance
9:\(pre\_node=\textbf{SWAP}(\&lock\_perf\_tail,\&node)\);
10:if\(pre\_node=NULL\)then
11:// The thread that is the first to join the queue
12:\(\textbf{CAS}(\&lock\_perf\_no\_steal,0,1)\);
13:// Disabling the FastPath to prevent starvation
14:\(node\_at\_head=1\);
15:\(node\_rearranger=1\);
16:// The head node serves as the initial reordering node
17:else
18:wait_until_to_head(\(lock,pre\_node,\&node\));
19:// Spin-waiting until the thread becomes the head node
20:endif
21:whileTrue do
22:if\(node\_rearranger=1\)then
23:\(\textbf{reorder}(lock,\&node,true)\);
24:endif
25:if\(!lock\_eff\_popflag\&\&\textbf{PW\_get}(\&node,lock\_eff\_head)=node\)then
26:// The thread is selected for dequeuing
27:\(lock\_perf\_popflag=true\);
28:break;
29:endif
30:endwhile
31:pop_from_perqueue(\(lock,\&node\));
32:// Dequeuing acquires the underlying Ticket lock
33:else
34:// Threads executing on efficiency cores are added to the wait queue for efficiency core
35:... // Handling is analogous to that on the performance core queue
36:endif
37:\(FastPath\) :
38:\(\textbf{Ticket\_mutex\_lock}(\&lock.Ticket)\);
39:// The thread successfully acquiring the Ticket lock signifies a successful locking operation
30:return 0;
31:}
```  
**Algorithm 1** CAL algorithm