개요
Seqlock (Sequence lock)은 리눅스에서 공유 변수의 빠른 Write operation을 지원하기 위해 사용되는 Lock이다. 리눅스 2.6.x 커널 버전부터 도입되었다. Seqlocks는 Stephen Hemminger에 의해 개발되었다.
Seqlock은 read-write lock의 일종으로, Write starvation을 회피하는 기법이다. System time counter업데이트에 처음 적용되었으며, 인터럽트가 발생할때 마다, System time을 update하는 매커니즘에 사용되었다.
Seqlock을 사용하는 경우 한 가지 미묘한 문제는 디버거를 사용하여 seqlock을 디버깅하는 것이 불가능 하다는 점이다. 디버거가 읽기 경쟁을 항상 발생시킬 만큼 충분히 느리기 때문에 재시도 로직이 항상 트리거 된다는 문제가 발생한다.
알고리즘
Seqlock은 Lock과 Sequence number을 저장하기 위한 저장소로 구성된다. Lock은 Writer간의 동기화를 위해서 사용되며, Counter는 Writer가 Sequential하게 접근하는 것을 보장하기 위해서 사용된다.
데이터를 Update할 경우, Writer가 Lock을 획득할 경우, 그리고 Writer가 Lock을 Release하는 모든 경우에, Sequence number을 증가시킨다. 이때 (Reader입장에서)데이터를 읽기 전과 후에 Sequence number가 다르면, 데이터를 읽는 동안 Writer가 Lock을 가져가서 데이터를 변경한 것이다. 두 경우 모두 Reader는 동일한 짝수 Sequence number을 읽을 때까지 Loop를 사용해서 다시 시도한다.
이 방식은 전통적인 Read/writer Lock대비하여 데이터가 수정되지 않는 경우가 많을 경우 잠금을 획득할 필요가 없어서 속도가 증가한다는 장점이 있다. Writer가 Reader를 기다릴 피요가 없기 때문에, Reader가 많은 환경에서도 성능저하를 피할 수 있다.
한계
Writer가 너무 많거나 Reader의 속도가 느리면 Livelock이 발생할 수 있다.
포인터가 포함된 데이터에 대해서는 이 기법이 작동하지 않는다. 이는 Writer가 포인터를 무효화 시킬 수 있기 떄문이다. 만약 메모리 블록을 업데이트하는 경우라면 Read-copy-update를 사용하는 것이 좋다.