# CAL: Core-Aware Lock for the big.LITTLE Multicore Architecture
## 3 Design
### Design of CAL Lock Algorithm  
**Core-aware queue insertion:** Once a thread issues a lock request, the CAL first checks whether the underlying ticket lock is locked. If it is not locked and _no_steal_ is 0, it meansthat the current state is under low contention, and the thread directly obtains the ticket lock and returns success. Otherwise, the thread checks the core type on which it runs. If it is running on a big core, it enters the big-core waiting queue. Otherwise, it enters the little-core waiting queue. _Tenqueue_ and _Talone_ (we calculate the _Talone_ of each critical region in the warm-up phase) are recorded when the thread enters the queue. After enqueuing, if it is at the head of the current queue, _no_steal_ is modified to 1, to prevent the following threads from stealing the ticket lock, which could cause the queue threads to suffer from the unfair block. At the same time, the CAL appoints the head of the queue as the rearranger, and it is responsible for the reordering process. **Core-aware node reordering:** In the second stage, the internal reordering of big- and little-core queues is realized. In the real application, multiple critical sections often need to be protected by the same lock (e.g., the same variable shared by muti-threads is used in different procedures). This way, threads running on the same core type would also have different processing times because of access to different critical sections. Stage 2 aims to achieve fairness goal in reordering within the big and little core queues. Figure 5 shows the reordering process of the big-core queue (same in the little-core queue). For each new arriving thread, it should go through the queue two times to find the best insertion position: the first time, CAL calculates the slowdown ratio of each thread from the rearranger thread to the new entrant thread. Note that the _Tshared_ of the thread \(i\) is equal to the sum of the completion time of the previous 0 \(i-1\) threads and the _Talone_ of thread \(i\) itself. In the second time, for each available insertion position, CAL is required to recalculate the slowdown ratio of two thread nodes (the new enqueue node and the delayed node) in reverse order and then recalculate the fairness of the queue. We record the insertion position that provides the maximum fairness and then insert the new entrant node into the position that provides the maximum fairness. In this way, we give a certain priority to the thread with a shorter critical section, letting it be as close to the head of the queue as possible while not letting threads with long critical sections wait too long so as to maintain a high level of fairness within the big and little-core queues. **Node selection:** Then we need to select a node from the head of big-core queue and the head of little-core queue to obtain the ticket lock. The thread successfully obtains the ticket, which means the lock operation executes successfully. In order to have a higher fairness, we need to take into account the computing performance and waiting time of the big core and little core. We refer to the classic high response ratio scheduling algorithm and make appropriate modifications to make it more in line with our design requirements. We define the proportional wait time [5] of the thread:  
\[PW=(T^{wait}+T^{other})/T^{clone} \tag{3}\]  
In the above formula, _Twait_ is the time the thread has been waiting since it joined the queue, _Talone_ is the individual completion time of the current thread itself, and _Tother_ is the _Talone_ of the thread at the head of another queue. We calculate the \(PW\) of the thread at the  
Figure 5: The second stage in CAL, when a new coming thread arrives and enqueues the queue (big-core queue above), it goes through the queue two times to find the most suitable insertion position. head of the big-core queue and the little-core queue respectively, and then select the thread with a larger \(PW\) to dequeue the queue to obtain the underlying ticket lock.