티켓 잠금 알고리즘 성능?

Question

리눅스 커널의 기본 스핀 록 알고리즘을 대체하는 티켓 잠금 알고리즘에 익숙한 사람이 있습니까? 나는 이것에 대한 전문가를 찾고 싶다. 순진한 알고리즘은 모든 스레드가 동시에 잠금을 얻으려는 CPU 버스를 압도하기 때문에 티켓 잠금 알고리즘이 더 빠르다고 가정 한 몇 가지 온라인 자료를 읽었습니다. 누구든지 나를 확인/거부 할 수 있습니까?

나는 내 자신의 실험을했다. 티켓 잠금 장치는 실제로 공정하지만 성능은 pthread 스핀 록 알고리즘과 비슷합니다. 실제로, 그것은 단지 느린 접촉 일뿐입니다.

내가 보는 방식대로, 부당한 알고리즘은 잠금 장치를 빨리 먹어 버리는 스레드가 더 빨리 끝나기 때문에 스케줄러의 작업량이 적기 때문에 불필요한 알고리즘이 더 빨라야합니다.

이 점에 대해 더 자세히 살펴보고 싶습니다. 속도가 더 빠르다면 왜 커널에서 티켓 잠금이 구현되고 사용자 공간에서 사용되지 않는 이유는 무엇입니까? 감사!

Answer 1

Linux 커널의 기본 스핀 록 알고리즘을 대체하는 티켓 잠금 알고리즘에 익숙한 사람이 있습니까? 나는 이것에 대한 전문가를 찾고 싶다. 순진한 알고리즘은 모든 스레드가 동시에 잠금을 얻으려는 CPU 버스를 압도하기 때문에 티켓 잠금 알고리즘이 더 빠르다고 가정 한 몇 가지 온라인 자료를 읽었습니다. 누구든지 나를 확인/거부 할 수 있습니까?

나는 내 자신의 실험을했다. 티켓 잠금 장치는 실제로 공정하지만 성능은 pthread 스핀 록 알고리즘과 비슷합니다. 실제로, 그것은 단지 느린 접촉 일뿐입니다.

ticket lock의 소개는 공정성 이유로 주로 생각합니다. 티켓 잠금과 스핀 록의 속도와 scalability은 MCS와 같은 확장 가능한 잠금과 거의 같습니다. 둘 다 CPU 버스를 압도하는 많은 캐시 라인 무효화 및 메모리 읽기를 도입합니다.

내가 보는 방식대로, 불공정 알고리즘은 잠금 장치를 빨리 먹는 스레드가 더 빨리 끝나기 때문에 스케줄러의 작업량이 적기 때문에 더 신속해야합니다.

관련 스케줄러가 없습니다. 티켓 잠금 및 스핀 록은 대기 중일 때 차단되지 않는 통화 대기 잠금이지만 잠금 값을 계속 확인합니다. 잠금 장치가 해제되면 프로그램이 계속 진행됩니다. 제어 흐름은 결코 스케줄러로 되돌아 가지 않습니다. 블록 웨이크 업 잠금 대신 스핀 록을 사용하는 이유는 블록 웨이크 업이 비용이 많이 드는 컨텍스트 스위치를 필요로하기 때문입니다. 따라서 바쁜 대기 잠금은 "짧은"중요 섹션에서만 사용할 수 있습니다.

이 점에 대해 더 자세히 살펴보고 싶습니다. 속도가 더 빠르다면 왜 커널에서 티켓 잠금이 구현되고 사용자 공간에서 사용되지 않는 이유는 무엇입니까? 감사!

커널 코드에 중요한 섹션이 있기 때문에 커널에 있으므로 커널 데이터를 보호하기 위해 커널 공간 잠금이 필요합니다. 물론 공간 티켓 잠금 장치를 구현하여 응용 프로그램에서 사용할 수 있습니다.