This paper presents two new concurrent queue algorithms: a non-blocking concurrent queue and a two-lock concurrent queue. Both algorithms are simple, fast, and practical. The non-blocking queue outperforms existing alternatives on machines with universal atomic primitives like compare_and_swap. The two-lock queue outperforms a single lock when multiple processes compete for access, making it suitable for machines with non-universal atomic primitives like test_and_set. The non-blocking algorithm is immune to delays in process execution, making it suitable for systems with unpredictable delays. The two-lock algorithm is livelock-free and allows concurrent enqueues and dequeues. The paper also discusses the correctness and performance of these algorithms, showing that the non-blocking algorithm performs well on both dedicated and multiprogrammed systems. The two-lock algorithm is recommended for heavily-utilized queues on machines with simple atomic primitives like test_and_set. The paper concludes that the non-blocking algorithm is a good choice for multiprocessor systems with universal atomic primitives, while the two-lock algorithm is suitable for systems without such primitives. The paper also discusses the trade-offs among alternative mechanisms for atomic update of common data structures.This paper presents two new concurrent queue algorithms: a non-blocking concurrent queue and a two-lock concurrent queue. Both algorithms are simple, fast, and practical. The non-blocking queue outperforms existing alternatives on machines with universal atomic primitives like compare_and_swap. The two-lock queue outperforms a single lock when multiple processes compete for access, making it suitable for machines with non-universal atomic primitives like test_and_set. The non-blocking algorithm is immune to delays in process execution, making it suitable for systems with unpredictable delays. The two-lock algorithm is livelock-free and allows concurrent enqueues and dequeues. The paper also discusses the correctness and performance of these algorithms, showing that the non-blocking algorithm performs well on both dedicated and multiprogrammed systems. The two-lock algorithm is recommended for heavily-utilized queues on machines with simple atomic primitives like test_and_set. The paper concludes that the non-blocking algorithm is a good choice for multiprocessor systems with universal atomic primitives, while the two-lock algorithm is suitable for systems without such primitives. The paper also discusses the trade-offs among alternative mechanisms for atomic update of common data structures.