[리눅스 커널] Synchronization - sequential locks

글의 참고

- Linux Device Driver 3rd Edition

- UnderStanding The Linux Kernel 3rd Edition

- Linux Kernel Development (3rd Edition)

- https://mirrors.edge.kernel.org/pub/linux/kernel/people/christoph/gelato/gelato2005-paper.pdf

---

글의 전제

- 밑줄로 작성된 글은 강조 표시를 의미한다.

- 그림 출처는 항시 그림 아래에 표시했다.

---

글의 내용

- Overview

: seqlock 은 2.6 커널에 등장한 lock-free 동기화 메커니즘이다. `sequence counter`를 통해서 동기화를 구현한다. readers 들은 크리티컬 섹션에 `진입 전` 과 `진입 후` 에 sequence coutner 를 읽어서 비교한다. 만약, counter 의 값이 동일하다면, write 가 없었다는 뜻이다. 즉, 값이 유효하다는 뜻이다. 만약, 값이 다르다면, 이 값은 유효하지 않다는 뜻이다. 그러므로, reader는 유효한 값이 읽힐 때 까지, 다시 이 과정을 반복한다.

 

: 아래 그림에서 볼 수 있다시피, wrtier의 seqlock은 spinlock과 sequence counter로 구성되어 있다. write가 seqlock의 spinlock을 얻으면, sequence counter가 1 증가한다. 그리고, seqlock의 spinlock을 해제할 때, 또 sequence counter가 1 증가한다. 즉, 이것은 2가지 케이스를 보장한다.

 

: seqlock은 writer에게 `higher priority`를 준다. 왜냐면, reader가 critical section에서 작업을 하는 도중에도 writer가 들어가서 값을 변경할 수 있기 때문이다(물론, 다른 writer들은 난입하지 못한다. writers들 끼리는 preemption disable 관계다). 결국, seqlock의 장점은 writer는 작업을 하기 위해 별도의 뭔가를 기다릴 필요가 없다. 단점은 reader가 무한 반복으로 값을 읽어야 할 수도 있다. 왜냐면, reader가 값을 읽는 과정에서 wrtier가 난입할 때 마다, 무효가 되기 때문이다(writer 가 이렇게 직접적으로 공유 데이터를 수정함으로써 reader 가 값을 반복적으로 읽는 문제가 발생. 이러한 문제 때문에 간적접으로 공유 데이터를 수정하는 RCU 가 등장)

https://mirrors.edge.kernel.org/pub/linux/kernel/people/christoph/gelato/gelato2005-paper.pdf

 

: seqlock 은 일반적으로 아래와 같은 형태로 구성된다. 

....
do {
	seq = read_seqcount_begin(&seqlock);
	/* critical section */
} while (read_seqcount_retry(&seqlock, seq));
....

: read_seqcount_begin 함수는 현재 seqlock_t 의 seqence counter를 리턴한다. read_seqcount_retry 함수는 sequence counter가 홀수이거나(현재 wrtier가 critical section에서 작업 중이거나), critical section 전에 읽은 값과 후에 읽은 갑이 다를 경우에 `1`을 반환한다(홀수가 아닌데, 값이 아닌 경우는 리더가 critical section에서 작업을 진행하는데, writer가 critical section에 들어와서 값을 후다닥 바꾸고 reader보다 먼저 나간 경우다.). 이럴 경우, `do { ... } while`을 다시 진행한다. reader는 이런 방식으로 값이 유효할 때 까지 계속 반복하게 된다.

 

 

- Use case

: 아래의 경우는 sequence coutner가 홀수가 된 경우다. reader가 critical section에서 작업을 하는 도중에 writer가 들어와서 counter값이 변경 바뀌었다. 이럴 경우, reader는 read_seqcount_retry 함수에서 `1`을 반환받게 된다. 즉, 무효다.

 

: 아래의 경우는 홀수는 아니지만, 진입 전과 후에 값이 다른 경우다. writer가 작업하는 도중에 reader가 난입했다. writer가 작업이 먼저 끝나버려서, 최종적으로 reader의 counter값이 변경되었다. 즉, 무효다.

 

: writer가 작업하는 도중에 reader가 난입했다. 그런데, reader의 counter값이 진입 전과 후와 동일하다. 이럴 경우, 유효할까? 무효다. 왜냐면, reader의 최종 값(read_seqcount_retry)이 홀수기 때문이다.

 

: reader가 작업하는 도중에 writer가 난입했다. 그런데, reader의 처리해야 할 작업이 많다보니, writer가 먼저 작업을 끝냈다. 결국, reader는 진입 전과 후에 coutner값이 달라졌다. 이렇게 되면 무효다.

: 주의할 점은 seqlock은 writer만 preemption을 disable 한다는 것이다. seqlock에서 reader는 값을 변경시키지 않아야 한다. wrtier만 값을 변경시킬 수 있다. 그래서 writer는 critical section에 들어갈 때, preemption을 disable 하기 위해 spinlock을 얻고 들어간다.

 

: 아래 케이스만 유효하다. 즉, reader와 writer가 동시대에 critical section에 들어가면 안된다.

 

: seqlock을 사용하기 가장 적합한 구조는 아래와 같다.

1. reader의 양은 많지만, reader가 critical section에서 작업하는 양은 굉장히 작아야 한다.
2. writer는 seqlock을 아주 드물게 획득해야 한다.

: reader가 critical section에서 작업하는 양이 많아지면, 중간에 writer가 난입할 수 있는 확률이 높아진다. 그렇게 되면, read가 계속 반복되고 이건 심각한 오버헤드 문제를 야기하게 된다. 이와 같은 예로 `jiffies`가 있다. jiffies는 일반적으로 10ms(HZ = 100)에 한 번씩 증가한다. 그런데, 리눅스 커널에서 jiffies는 이곳저곳 엄청나게 많이 읽히고 있다.