앞서 언급했듯이, 뮤텍스가 보호하는 영역이 너무 넓으면 스레드가 여럿이라 하더라도 하나일 때와 별반 차이가 없습니다. 여러 CPU가 각 스레드의 연산을 실행하여 동시 처리량을 올리는 것을 병렬성(parallelism)이라고 합니다. 그런데 어떤 이유로 이러한 병렬성이 제대로 나오지 않는 것, 즉 병렬로 실행되게 프로그램을 만들었는데 정작 한 CPU만 연산을 수행하는 현상을 시리얼 병목(serial bottleneck)이라고 합니다.

앞서 소수 구하는 프로그램의 각 스레드가 하는 일을 의사 코드로 살펴봅시다.

1. num을 잠급니다.

2. num에서 값을 하나 가져옵니다.

3. num을 잠금 해제합니다.

4. num이 소수인지 판별합니다.

5. 소수면 primes를 잠급니다.

6. primes에 소수를 넣습니다.

7. primes를 잠금 해제합니다.

1~3 사이에서는 잠금이 발생합니다. 다른 스레드가 1~3을 실행하려고 하면 그 스레드는 일시 정지됩니다. 마찬가지로 5~7에서도 같은 일이 발생합니다.