Abstract: With the multi-core chip wildly used in the embedded real-time system, the traditional lock synchronization may cause deadlock, priority inversion and cpu starvation. It may degrade performance and cause inestimable loss to the real-time system. This paper proposed a lock-free alogrithm for the Skip-list data structure and gave the proof for its linear consistency and used it as a shared priority queue for mixed-critical system. The experimental results show that this method has much better than the lock mechanism on average response time and utilization rate of multi-core processor and have the higher system throughput rate.