IT/모바일
리눅스 커널의 이해(4): Uni-Processor & Multi-Processor 환경에서의 동기화 문제
저자: 서민우
출처: Embedded World
[ 관련 기사 ]
♠ 리눅스 커널의 이해(1) : 커널의 일반적인 역할과 동작
♠ 리눅스 커널의 이해(2): 리눅스 커널의 동작
♠ 리눅스 커널의 이해(3): 리눅스 디바이스 작성시 동기화 문제
이번 기사부터 3-4회에 걸쳐 리눅스 디바이스 드라이버 작성시 Uni-Processor 또는 Multi-Processor 환경에 따라 발생할 수 있는 동기화 문제의 여러 가지 패턴을 살펴보고 그에 대한 해결책을 알아보기로 하자.
리눅스 커널의 기본적인 동작
[그림 1]은 각각 system call에 의한 리눅스 커널의 동작, hardware interrupt에 의한 리눅스 커널의 동작, nested interrupt에 의한 리눅스 커널의 동작을 나타낸다. 여기서는 시그널을 처리하는 do_signal() 함수를 생략하였다. 일반적으로 리눅스 디바이스 드라이버는 do_signal() 함수와 직접적으로 관련이 없으며, 따라서 여기서는 설명의 편의상 이 부분을 생략하였다.
[그림 1] 리눅스 커널의 기본적인 동작
우리는 지난 기사에서 디바이스 드라이버의 주요한 동작을 크게 세가지로 나누었다. 그 세가지는 각각 [디바이스에 쓰기 동작], [동기적으로 디바이스로부터 읽기 동작], [비동기적으로 디바이스로부터 읽기 동작]이다. 이 각각의 동작에 대하여 먼저 Uni-Processor 상에서 발생할 수 있는 동기화 문제와 그에 대한 해결책을, 다음으로 Multi-Processor 상에서 발생할 수 있는 동기화 문제와 그에 대한 해결책을 차례로 살펴보기로 한다.
먼저 위의 세 가지 동작에 대하여 Uni-Processor 상에서 발생할 수 있는 동기화 문제와 그에 대한 해결책을 살펴보자.
[디바이스에 쓰기 동작]에 대한 Uni-Processor 상에서의 동기화 문제와 그에 대한 해결책
지난 기사에서 우리는 [디바이스에 쓰기 동작]과 관련한 커널의 흐름을 보았다. 그 흐름을 좀 더 구체적으로 나타내면 다음과 같다.
▶ 시스템 콜 루틴 내부
i) 디바이스를 사용하고 있지 않으면
디바이스를 사용한다고 표시하고,
데이터를 디바이스 버퍼에 쓰고 나간다
ii) 디바이스를 사용하고 있으면
데이터를 데이터 큐에 넣고 나간다
▶ 하드웨어
디바이스가 데이터를 다 보냈다 → hardware interrupt 발생
▶ top half 루틴 내부
bottom half 요청
▶ bottom half 루틴 내부
i) 데이터 큐가 비어 있으면
디바이스를 다 사용했다고 표시하고 나간다
ii) 데이터 큐가 비어 있지 않으면
데이터를 하나 꺼내서 디바이스 버퍼에 쓰고 나간다
이 흐름은 프로세스를 기준으로 볼 때 논리적으로 두 가지 흐름으로 나눌 수 있으며 각각 다음과 같다.
1) 다른 프로세스가 디바이스를 사용하고 있지 않을 경우
2) 다른 프로세스가 디바이스를 사용하고 있을 경우
각각의 경우를 구체적으로 보자.
디바이스에 쓰기 1
1) 다른 프로세스가 디바이스를 사용하고 있지 않을 경우
▶ 시스템 콜 루틴 내부
i) 디바이스를 사용하고 있지 않으면
디바이스를 사용한다고 표시하고(ⓐ),
데이터를 디바이스 버퍼에 쓰고 나간다
▶ 하드웨어
디바이스가 데이터를 다 보냈다 → hardware interrupt 발생
▶ top half 루틴 내부
bottom half 요청
▶ bottom half 루틴 내부
i) 데이터 큐가 비어 있으면
디바이스를 다 사용했다고 표시하고 나간다
[그림 2]를 통해서 첫번째 흐름을 좀 더 구체적으로 이해해 보자.
[그림 2] 디바이스에 쓰기 1
[그림 2]에서 어떤 프로세스 P1이 시스템 콜을 통해 커널 영역에서 어떤 디바이스를 사용하고자 할 때 다른 프로세스가 그 디바이스를 사용하고 있지 않으면 디바이스를 사용한다고 표시하고, 데이터를 디바이스 버퍼에 쓰고 나간다. 그러면 디바이스는 쓰기 동작을 수행하기 시작한다. 어느 정도의 시간이 지나면 그 디바이스는 쓰기 동작을 완료하고 hardware interrupt를 발생시킨다.
여기서 hardware interrupt는 임의의 프로세스 Pn을 수행하는 중에 발생한다. hardware interrupt가 발생하면 top half 루틴과 bottom half 루틴을 차례로 수행한다. top half 루틴에서는 특별한 일을 하지 않고 bottom half 루틴이 수행되기를 요청한다. 그러면 bottom half 루틴에서는 데이터 큐가 비어 있는지 보고 비어 있으면 디바이스를 다 사용했다고 표시하고 나간다.
여기서 디바이스의 사용은 ① 지점에서 시작해서 ② 지점에서 끝난다. 즉, 시스템 콜 영역에서 시작해서 bottom half 영역에서 끝난다. 일반적으로 이 구간은 CPU를 기준으로 볼 때 시간상으로 무척 길며 얼마나 걸릴지 예측할 수 없다.
[그림 3] 디바이스에 쓰기 2
2) 다른 프로세스가 디바이스를 사용하고 있을 경우
▶ 시스템 콜 루틴 내부
ii) 디바이스를 사용하고 있으면
데이터를 데이터 큐에 넣고 나간다
▶ 하드웨어
디바이스가 데이터를 다 보냈다 → hardware interrupt 발생
▶ top half 루틴 내부
bottom half 요청
▶ bottom half 루틴 내부
ii) 데이터 큐가 비어 있지 않으면
데이터를 하나 꺼내서 디바이스 버퍼에 쓰고 나간다
[그림 3]을 통해서 두 번째 흐름을 좀 더 구체적으로 이해해 보자
[그림 3]에서 어떤 프로세스 Pk가 시스템 콜을 통해 커널 영역에서 어떤 디바이스를 사용하고자 할 때 임의의 프로세스 P1이 그 디바이스를 이미 사용하고 있으면 데이터를 데이터 큐에 넣고 나간다. 디바이스는 이전에 프로세스 P1에 의해 쓰기 동작을 수행하기 시작했다. 어느 정도의 시간이 지나면 그 디바이스는 쓰기 동작을 완료하고 hardware interrupt를 발생시킨다.
이 때 hardware interrupt는 임의의 프로세스 Pm을 수행하는 중에 발생한다. hardware interrupt가 발생하면 top half 루틴과 bottom half 루틴을 차례로 수행한다. top half 루틴에서는 특별한 일을 하지 않고 bottom half 루틴이 수행되기를 요청한다. 그러면 bottom half 루틴에서는 데이터 큐가 비어 있는지 보고 비어 있지 않으면 데이터를 하나 꺼내서 디바이스 버퍼에 쓰고 나간다. 그러면 디바이스는 쓰기 동작을 수행하기 시작한다. 어느 정도의 시간이 지나면 그 디바이스는 쓰기 동작을 완료하고 hardware interrupt를 발생시킨다.
여기서 hardware interrupt는 임의의 프로세스 Pn을 수행하는 중에 발생한다. hardware interrupt가 발생하면 top half 루틴과 bottom half 루틴을 차례로 수행한다. top half 루틴에서는 특별한 일을 하지 않고 bottom half 루틴이 수행되기를 요청한다. 그러면 bottom half 루틴에서는 데이터 큐가 비어 있는지 보고 비어 있으면 디바이스를 다 사용했다고 표시하고 나간다.
여기서 데이터 큐 사용구간 ⒜와 데이터 큐 사용구간 ⒝는 논리적으로 순서를 이루어야 한다. 그렇지 않을 경우에는 문제가 발생하며 이에 대해서는 뒤에 좀 더 구체적으로 다루기로 한다.
지금까지 우리는 [디바이스에 쓰기 동작]과 관련한 커널의 두 가지 논리적인 흐름을 보았다. 이러한 논리적인 흐름이 제대로 지켜지지 않을 경우엔 동기화 문제가 발생할 수 있다.
[디바이스에 쓰기 동작]과 동기화 문제
그러면 지금부터 [디바이스에 쓰기 동작]과 관련한 두 가지 논리적인 흐름에서 생길 수 있는 동기화 문제와 이에 대한 해결책을 생각해 보자.
먼저 지난 기사에서도 말했듯이, 동기화란 논리적으로 흐름이 다른 루틴(예를 들어, 시스템 콜 루틴, top half 루틴, bottom half 루틴)간에 순서를 지키는 일이다. 이러한 루틴간에 순서를 지키지 않는 상황을 루틴간 경쟁 상태라고 한다. 즉, 동기화 문제는 루틴간 경쟁 상태에서 발생한다.
[디바이스에 쓰기 동작]과 관련한 논리적인 흐름에서 생길 수 있는 루틴간 경쟁 상태는 두 가지가 있을 수 있다. 먼저 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]간에 경쟁 상태가 있을 수 있다. 다음으로 [시스템 콜 루틴 내부의 ii) 항목]과 [bottom half 루틴 내부의 i) 항목]간에 경쟁 상태가 있을 수 있다. 좀 더 엄밀히 말하면, [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]에 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]이 끼어 드는 상황과, [시스템 콜 루틴 내부의 ii) 항목]에 [bottom half 루틴 내부의 i) 항목]이 끼어 드는 상황이 있을 수 있다.
시스템 콜 루틴간의 경쟁 상태
[그림 4]는 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]간에 경쟁 상태를 나타낸다.
[그림 4]에서 프로세스 P1이 시스템 콜을 통해 커널 영역에서 ⓐ의 앞부분([그림 4]의 ① 부분)을 수행하는 도중에
1) A 지점에서 nested interrupt가 발생하고,
2) B 부분을 포함해 한 번 이상의 프로세스 스케쥴링을 거쳐,
어느 시점에 프로세스 Pn을 수행하고, 프로세스 Pn이 시스템 콜을 통해 커널 영역에서
3) C 지점을 거쳐 ⓐ 부분([그림 4]의 ② 부분)을 수행하고,
이후에 한 번 이상의 프로세스 스케쥴링을 거쳐 어느 순간 프로세스 P1이 h 지점으로 나와(이전에 B 부분의 g 지점으로 들어감) ⓐ의 뒷부분([그림 4]의 ③ 부분)을 수행할 경우 두 프로세스가 같이 디바이스를 사용한다고 표시하는, 그래서 두 프로세스가 디바이스 버퍼를 같이 접근하는, 동기화 문제가 발생한다. 즉, [그림 4]에서 ①과 ③은 논리적으로 연속이어야 하는데 이 사이에 ②가 끼어 드는 상황이 발생한다. 즉, [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]간에 경쟁 상태가 발생한다.
[그림 4] 시스템 콜 루틴간의 경쟁 상태
그러면 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]간에 경쟁 상태가 발생하는 이유를 알아보자.
[그림 4]를 보면
1) A 지점에서 nested interrupt를 허용함으로써 동기화 문제가 발생할 가능성이 생기고,
2) B 지점에서 프로세스 스케쥴링을 허용함으로써 동기화 문제가 발생할 가능성이 생기고,
3) C 지점에서 문제가 되는 영역을 접근함으로써 동기화 문제가 구체적으로 발생한다.
일반적으로 동기화 문제는 첫째는 임의의 지점에서 hardware interrupt를 허용함으로써, 둘째는 임의의 지점에서 프로세스 스케쥴링을 수행함으로써 발생한다.
시스템 콜 루틴간의 경쟁 상태에 대한 해결책
그러면 이러한 경쟁 상태를 어떻게 막을지 생각해 보자. 앞에서 우리는 루틴간 경쟁 상태가 발생하는 이유 세 가지를 보았다. 이에 대한 해결책은 각각 다음과 같다.
1) A 지점에서 hardware interrupt를 허용하지 않거나,
2) B 지점에서 프로세스 스케쥴링을 허용하지 않거나,
3) C 지점에서 문제가 되는 영역을 접근하지 못하게 하면 된다.
시스템 콜 루틴간의 경쟁 상태에 대한 해결책
그러면 이러한 경쟁 상태를 어떻게 막을지 생각해 보자. 앞에서 우리는 루틴간 경쟁 상태가 발생하는 이유 세 가지를 보았다. 이에 대한 해결책은 각각 다음과 같다.
1) A 지점에서 hardware interrupt를 허용하지 않거나,
2) B 지점에서 프로세스 스케쥴링을 허용하지 않거나,
3) C 지점에서 문제가 되는 영역을 접근하지 못하게 하면 된다.
좀 더 구체적으로 해결책을 알아보자.
1) 일반적으로 CPU마다 hardware interrupt를 허용하지 않게 하거나 허용하게 하는 명령어를 가지며 이를 이용하여 루틴내의 적당한 구간에서 hardware interrupt를 허용하지 않을 수 있다. 우리는 이 두 명령어를 각각 cli, sti라고 하자. 이 두 명령어를 이용하여 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]을 다음과 같이 처리할 수 있다.
여기서 한 가지 주의할 점은 일반적으로 디바이스 버퍼를 접근할 때는 시간상 연속으로 접근할 때 디바이스에 대한 활용도가 높다. 따라서 위의 루틴은 다음과 같이 처리하기로 한다.
2) 일반적으로 프로세스 스케쥴링을 허용하지 않는 것을 schedule lock 또는 preemption lock이라 한다. 리눅스 커널 2.5 버전 이후부터는 preempt_disable(), preempt_enable()이라는 함수를 이용하여 프로세스 스케쥴링을 허용하지 않을 수 있다. preemption lock은 다음에 볼 flag나 lock에 해당하는 변수를 이용하여 논리적으로 독립적인 루틴간에 경쟁 상태를 해결하는 방법이다. 따라서 여기서는 이 방법에 대해 더 이상 구체적으로 다루지 않는다.
3) 논리적으로 flag나 lock에 해당하는 변수를 두어 문제가 되는 영역을 동시에 접근하지 못하게 한다. 예를 들어 문제가 되는 영역에 들어가고자 할 땐 flag를 내리고 들어가고 나올 땐 flag를 올리고 나오는 개념이다. 좀 더 구체적으로 보자. 문제가 되는 영역에 들어가고자 할 땐 다음과 같은 루틴을 수행한다.
즉, 문제가 되는 영역에 들어가고자 할 땐 flag가 올려져 있는지 보고 올려져 있으면 flag를 내리고 들어가고 그렇지 않으면 flag가 올려질 때까지 기다린다.
문제가 되는 영역에서 나올 땐 다음과 같은 루틴을 수행한다.
즉, 문제가 되는 영역에서 나올 땐 flag를 올리고 나온다.
이 두 루틴을 이용하여 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]을 다음과 같이 처리할 수 있다.
그런데 이 루틴의 ⓐ 부분과 ⓑ 부분은 논리적으로 구조가 같다. 따라서 ⓑ 부분에서 발생할 수 있는 동기화 문제가 ⓐ 부분에서도 발생한다. 따라서 이 루틴을 그대로 사용할 경우 문제가 있으며, ⓒ 부분을 다음과 같이 바꾼다.
ⓓ 부분도 다음과 같이 바꾼다.
이 두 루틴을 이용하여 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]을 다음과 같이 처리할 수 있다.
그런데 앞에서도 보았던 것처럼 이 루틴의 ⓐ 부분과 ⓑ 부분은 논리적인 구조가 같다. 따라서 굳이 이와 같은 방법을 사용하지 않고 1)과 같은 방법을 사용하면 된다.
참고로 flag와 같은 속성을 갖는 변수를 세마포어 변수라고 한다. 또 뮤텍스 변수도 이와 같은 속성을 갖는다.
이상에서 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]은 1)과 같이 처리하기로 한다.
시스템 콜 루틴과 bottom half 루틴간의 경쟁 상태
다음은 [시스템 콜 루틴 내부의 ii) 항목]과 [bottom half 루틴 내부의 ii) 항목]간에 경쟁 상태와 이에 대한 해결책을 알아보자.
[그림 5]와 [그림 6]은 [시스템 콜 루틴 내부의 ii) 항목]과 [bottom half 루틴 내부의 i) 항목]간에 경쟁 상태를 나타낸다.
[그림 5] 시스템 콜 루틴과 bottom half 루틴간의 경쟁 상태 1
먼저 [그림 5]에서 프로세스 Pn이 시스템 콜을 통해 커널 영역에서 [시스템 콜 루틴 내부의 ii) 항목]의 앞부분([그림 5]의 ① 부분)을 수행하는 도중에
1) A 지점에서 nested interrupt가 발생하고, B 지점에서 bottom half가 수행되기를 요청하면,
2) C 지점을 거쳐 [bottom half 루틴 내부의 i) 항목]([그림 5]의 ② 부분)을 수행하고 (논리적으로는 [bottom half 루틴 내부의 ii) 항목]을 수행해야 함)
A 지점으로 다시 나와 [시스템 콜 루틴 내부의 ii) 항목]의 뒷부분([그림 5]의 ③ 부분)을 수행한다.
[그림 6] 시스템 콜 루틴과 bottom half 루틴간의 경쟁 상태 2
다음은 [그림 6]에서 프로세스 Pk가 시스템 콜을 통해 커널 영역에서 [시스템 콜 루틴 내부의 ii) 항목]의 앞부분([그림 6]의 ① 부분)을 수행하는 도중에
1) A 지점에서 nested interrupt가 발생하고,
B 부분을 포함해 한 번 이상의 프로세스 스케쥴링을 거쳐, 어느 시점에 프로세스 Pn을 수행하고, 프로세스 Pn의 C 지점에서 hardware interrupt가 발생하여 top half 루틴과 bottom half 루틴을 차례로 수행한다. bottom half 루틴에서는,
2) D 지점을 거쳐 [bottom half 루틴 내부의 i) 항목]을([그림 6]의 ② 부분을) 수행하고 (논리적으로는 [bottom half 루틴 내부의 ii) 항목]을 수행해야 함)
이후에 한 번 이상의 프로세스 스케쥴링을 거쳐 어느 순간 프로세스 Pk가 h 지점으로 나와 (이전에 B 부분의 g 지점으로 들어감) [시스템 콜 루틴 내부의 i) 항목]의 뒷부분([그림 6]의 ③ 부분)을 수행한다.
[그림 5]와 [그림 6]과 같은 경우 디바이스는 사용하지 않으면서 데이터는 데이터 큐에 남아 있는 상황이 발생하며, 일반적으로 이런 상황을 starvation이라 한다. 이와 같은 상황은 데이터 큐 사용구간에서 hardware interrupt에 의한 시스템 콜 루틴과 bottom half 루틴간 경쟁 상태가 발생하여 나타난다. [그림 5]와 [그림 6]에서는 [데이터 큐 사용구간 ⒜]와 [데이터 큐 사용구간 ⒝]간에 경쟁 상태가 발생하였다. 이와 같은 경쟁 상태는 [그림 3]의
[데이터 큐 사용구간 ⒜], [데이터 큐 사용구간 ⒝]와 같은 순서가 되도록 해결해야 한다. 즉, 데이터 큐 사용구간이 겹치지 않도록 한다.
그러면 [시스템 콜 루틴 내부의 ii) 항목]과 [bottom half 루틴 내부의 i) 항목]간에 경쟁 상태가 발생하는 이유를 알아보자.
[그림 5]와 [그림 6]을 보면
1) A 지점에서 nested interrupt를 허용함으로써 동기화 문제가 발생할 가능성이 생기고,
2) 각각 C 지점과 D 지점에서 문제가 되는 영역을 접근함으로써 동기화 문제가 구체적으로 발생한다.
시스템 콜 루틴과 bottom half 루틴간의 경쟁 상태에 대한 해결책
이에 대한 해결책은 이미 앞에서 본 것처럼 각각 다음과 같다.
1) A 지점에서 hardware interrupt를 허용하지 않거나,
2) 각각 C 지점과 D 지점에서 문제가 되는 영역을 접근하지 못하게 하면 된다.
좀 더 구체적인 해결책은 다음과 같다.
1) [시스템 콜 루틴 내부의 ii) 항목]을 다음과 같이 처리하면 된다.
2) 먼저 [시스템 콜 루틴 내부의 ii) 항목]과 [bottom half 루틴 내부의 i), ii) 항목]을 각각 다음과 같이 처리해 본다.
그러나 이렇게 처리할 경우 각각 C 지점과 D 지점에서 데드락이 발생한다. 따라서 C 지점과 D 지점에 다음과 같은 루틴을 사용한다.
그러나 이렇게 처리할 경우 [bottom half 루틴 내부의 ii) 항목]을 [시스템 콜 루틴 내부의 ii) 항목]이후에 수행할 수 있도록 적절한 루틴을 추가해 주어야 하는데 이럴 경우 루틴이 많이 복잡해진다.
[시스템 콜 루틴 내부의 ii) 항목]의 경우 루틴을 수행하는 시간을 예측할 수 있으며, 또한 그 시간이 충분히 짧기 때문에 일반적으로 리눅스 커널에서는 1)과 같은 방법을 사용하여 동기화 문제를 처리한다.
이상에서 [디바이스에 쓰기 동작]에 대하여 Uni-Processor 상에서 발생할 수 있는 동기화 문제와 그에 대한 해결책을 알아보았다. 다음 기사에는 일단 [디바이스에 쓰기 동작]에 대한 구체적인 예를 들여다보기로 하자.
서민우 / minucy@hanmail.net
과학기술정보연구소 및 여러 대학교에서 임베디드 리눅스 실무과정을 강의하면서 리눅스 커널 초기버전을 분석하는 작업을 통해 초보자들도 OS 의 설계 및 구현에 대해 체계적으로 접근할 수 있는 방법에 대한 자료를 제작하는 데에 힘을 쏟고 있다. 50개 정도의 명령어, pipeline 등을 포함한 32 bit RISC CPU 를 설계 및 구현한 경험이 있고 uCOS/II 정도 수준의 OS 설계 및 구현에 대한 체계적인 접근 방법에 대한 자료까지 완성한 상태이며 지속적인 작업을 통해 커널과 OS에 관한 유용한 정보를 널리 공유하고자 노력하고 있다.
출처: Embedded World
[ 관련 기사 ]
♠ 리눅스 커널의 이해(1) : 커널의 일반적인 역할과 동작
♠ 리눅스 커널의 이해(2): 리눅스 커널의 동작
♠ 리눅스 커널의 이해(3): 리눅스 디바이스 작성시 동기화 문제
이번 기사부터 3-4회에 걸쳐 리눅스 디바이스 드라이버 작성시 Uni-Processor 또는 Multi-Processor 환경에 따라 발생할 수 있는 동기화 문제의 여러 가지 패턴을 살펴보고 그에 대한 해결책을 알아보기로 하자.
리눅스 커널의 기본적인 동작
[그림 1]은 각각 system call에 의한 리눅스 커널의 동작, hardware interrupt에 의한 리눅스 커널의 동작, nested interrupt에 의한 리눅스 커널의 동작을 나타낸다. 여기서는 시그널을 처리하는 do_signal() 함수를 생략하였다. 일반적으로 리눅스 디바이스 드라이버는 do_signal() 함수와 직접적으로 관련이 없으며, 따라서 여기서는 설명의 편의상 이 부분을 생략하였다.
[그림 1] 리눅스 커널의 기본적인 동작
우리는 지난 기사에서 디바이스 드라이버의 주요한 동작을 크게 세가지로 나누었다. 그 세가지는 각각 [디바이스에 쓰기 동작], [동기적으로 디바이스로부터 읽기 동작], [비동기적으로 디바이스로부터 읽기 동작]이다. 이 각각의 동작에 대하여 먼저 Uni-Processor 상에서 발생할 수 있는 동기화 문제와 그에 대한 해결책을, 다음으로 Multi-Processor 상에서 발생할 수 있는 동기화 문제와 그에 대한 해결책을 차례로 살펴보기로 한다.
먼저 위의 세 가지 동작에 대하여 Uni-Processor 상에서 발생할 수 있는 동기화 문제와 그에 대한 해결책을 살펴보자.
[디바이스에 쓰기 동작]에 대한 Uni-Processor 상에서의 동기화 문제와 그에 대한 해결책
지난 기사에서 우리는 [디바이스에 쓰기 동작]과 관련한 커널의 흐름을 보았다. 그 흐름을 좀 더 구체적으로 나타내면 다음과 같다.
▶ 시스템 콜 루틴 내부
i) 디바이스를 사용하고 있지 않으면
디바이스를 사용한다고 표시하고,
데이터를 디바이스 버퍼에 쓰고 나간다
ii) 디바이스를 사용하고 있으면
데이터를 데이터 큐에 넣고 나간다
▶ 하드웨어
디바이스가 데이터를 다 보냈다 → hardware interrupt 발생
▶ top half 루틴 내부
bottom half 요청
▶ bottom half 루틴 내부
i) 데이터 큐가 비어 있으면
디바이스를 다 사용했다고 표시하고 나간다
ii) 데이터 큐가 비어 있지 않으면
데이터를 하나 꺼내서 디바이스 버퍼에 쓰고 나간다
이 흐름은 프로세스를 기준으로 볼 때 논리적으로 두 가지 흐름으로 나눌 수 있으며 각각 다음과 같다.
1) 다른 프로세스가 디바이스를 사용하고 있지 않을 경우
2) 다른 프로세스가 디바이스를 사용하고 있을 경우
각각의 경우를 구체적으로 보자.
디바이스에 쓰기 1
1) 다른 프로세스가 디바이스를 사용하고 있지 않을 경우
▶ 시스템 콜 루틴 내부
i) 디바이스를 사용하고 있지 않으면
디바이스를 사용한다고 표시하고(ⓐ),
데이터를 디바이스 버퍼에 쓰고 나간다
▶ 하드웨어
디바이스가 데이터를 다 보냈다 → hardware interrupt 발생
▶ top half 루틴 내부
bottom half 요청
▶ bottom half 루틴 내부
i) 데이터 큐가 비어 있으면
디바이스를 다 사용했다고 표시하고 나간다
[그림 2]를 통해서 첫번째 흐름을 좀 더 구체적으로 이해해 보자.
[그림 2] 디바이스에 쓰기 1
[그림 2]에서 어떤 프로세스 P1이 시스템 콜을 통해 커널 영역에서 어떤 디바이스를 사용하고자 할 때 다른 프로세스가 그 디바이스를 사용하고 있지 않으면 디바이스를 사용한다고 표시하고, 데이터를 디바이스 버퍼에 쓰고 나간다. 그러면 디바이스는 쓰기 동작을 수행하기 시작한다. 어느 정도의 시간이 지나면 그 디바이스는 쓰기 동작을 완료하고 hardware interrupt를 발생시킨다.
여기서 hardware interrupt는 임의의 프로세스 Pn을 수행하는 중에 발생한다. hardware interrupt가 발생하면 top half 루틴과 bottom half 루틴을 차례로 수행한다. top half 루틴에서는 특별한 일을 하지 않고 bottom half 루틴이 수행되기를 요청한다. 그러면 bottom half 루틴에서는 데이터 큐가 비어 있는지 보고 비어 있으면 디바이스를 다 사용했다고 표시하고 나간다.
여기서 디바이스의 사용은 ① 지점에서 시작해서 ② 지점에서 끝난다. 즉, 시스템 콜 영역에서 시작해서 bottom half 영역에서 끝난다. 일반적으로 이 구간은 CPU를 기준으로 볼 때 시간상으로 무척 길며 얼마나 걸릴지 예측할 수 없다.
[그림 3] 디바이스에 쓰기 2
2) 다른 프로세스가 디바이스를 사용하고 있을 경우
▶ 시스템 콜 루틴 내부
ii) 디바이스를 사용하고 있으면
데이터를 데이터 큐에 넣고 나간다
▶ 하드웨어
디바이스가 데이터를 다 보냈다 → hardware interrupt 발생
▶ top half 루틴 내부
bottom half 요청
▶ bottom half 루틴 내부
ii) 데이터 큐가 비어 있지 않으면
데이터를 하나 꺼내서 디바이스 버퍼에 쓰고 나간다
[그림 3]을 통해서 두 번째 흐름을 좀 더 구체적으로 이해해 보자
[그림 3]에서 어떤 프로세스 Pk가 시스템 콜을 통해 커널 영역에서 어떤 디바이스를 사용하고자 할 때 임의의 프로세스 P1이 그 디바이스를 이미 사용하고 있으면 데이터를 데이터 큐에 넣고 나간다. 디바이스는 이전에 프로세스 P1에 의해 쓰기 동작을 수행하기 시작했다. 어느 정도의 시간이 지나면 그 디바이스는 쓰기 동작을 완료하고 hardware interrupt를 발생시킨다.
이 때 hardware interrupt는 임의의 프로세스 Pm을 수행하는 중에 발생한다. hardware interrupt가 발생하면 top half 루틴과 bottom half 루틴을 차례로 수행한다. top half 루틴에서는 특별한 일을 하지 않고 bottom half 루틴이 수행되기를 요청한다. 그러면 bottom half 루틴에서는 데이터 큐가 비어 있는지 보고 비어 있지 않으면 데이터를 하나 꺼내서 디바이스 버퍼에 쓰고 나간다. 그러면 디바이스는 쓰기 동작을 수행하기 시작한다. 어느 정도의 시간이 지나면 그 디바이스는 쓰기 동작을 완료하고 hardware interrupt를 발생시킨다.
여기서 hardware interrupt는 임의의 프로세스 Pn을 수행하는 중에 발생한다. hardware interrupt가 발생하면 top half 루틴과 bottom half 루틴을 차례로 수행한다. top half 루틴에서는 특별한 일을 하지 않고 bottom half 루틴이 수행되기를 요청한다. 그러면 bottom half 루틴에서는 데이터 큐가 비어 있는지 보고 비어 있으면 디바이스를 다 사용했다고 표시하고 나간다.
여기서 데이터 큐 사용구간 ⒜와 데이터 큐 사용구간 ⒝는 논리적으로 순서를 이루어야 한다. 그렇지 않을 경우에는 문제가 발생하며 이에 대해서는 뒤에 좀 더 구체적으로 다루기로 한다.
지금까지 우리는 [디바이스에 쓰기 동작]과 관련한 커널의 두 가지 논리적인 흐름을 보았다. 이러한 논리적인 흐름이 제대로 지켜지지 않을 경우엔 동기화 문제가 발생할 수 있다.
[디바이스에 쓰기 동작]과 동기화 문제
그러면 지금부터 [디바이스에 쓰기 동작]과 관련한 두 가지 논리적인 흐름에서 생길 수 있는 동기화 문제와 이에 대한 해결책을 생각해 보자.
먼저 지난 기사에서도 말했듯이, 동기화란 논리적으로 흐름이 다른 루틴(예를 들어, 시스템 콜 루틴, top half 루틴, bottom half 루틴)간에 순서를 지키는 일이다. 이러한 루틴간에 순서를 지키지 않는 상황을 루틴간 경쟁 상태라고 한다. 즉, 동기화 문제는 루틴간 경쟁 상태에서 발생한다.
[디바이스에 쓰기 동작]과 관련한 논리적인 흐름에서 생길 수 있는 루틴간 경쟁 상태는 두 가지가 있을 수 있다. 먼저 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]간에 경쟁 상태가 있을 수 있다. 다음으로 [시스템 콜 루틴 내부의 ii) 항목]과 [bottom half 루틴 내부의 i) 항목]간에 경쟁 상태가 있을 수 있다. 좀 더 엄밀히 말하면, [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]에 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]이 끼어 드는 상황과, [시스템 콜 루틴 내부의 ii) 항목]에 [bottom half 루틴 내부의 i) 항목]이 끼어 드는 상황이 있을 수 있다.
시스템 콜 루틴간의 경쟁 상태
[그림 4]는 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]간에 경쟁 상태를 나타낸다.
[그림 4]에서 프로세스 P1이 시스템 콜을 통해 커널 영역에서 ⓐ의 앞부분([그림 4]의 ① 부분)을 수행하는 도중에
1) A 지점에서 nested interrupt가 발생하고,
2) B 부분을 포함해 한 번 이상의 프로세스 스케쥴링을 거쳐,
어느 시점에 프로세스 Pn을 수행하고, 프로세스 Pn이 시스템 콜을 통해 커널 영역에서
3) C 지점을 거쳐 ⓐ 부분([그림 4]의 ② 부분)을 수행하고,
이후에 한 번 이상의 프로세스 스케쥴링을 거쳐 어느 순간 프로세스 P1이 h 지점으로 나와(이전에 B 부분의 g 지점으로 들어감) ⓐ의 뒷부분([그림 4]의 ③ 부분)을 수행할 경우 두 프로세스가 같이 디바이스를 사용한다고 표시하는, 그래서 두 프로세스가 디바이스 버퍼를 같이 접근하는, 동기화 문제가 발생한다. 즉, [그림 4]에서 ①과 ③은 논리적으로 연속이어야 하는데 이 사이에 ②가 끼어 드는 상황이 발생한다. 즉, [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]간에 경쟁 상태가 발생한다.
[그림 4] 시스템 콜 루틴간의 경쟁 상태
그러면 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]간에 경쟁 상태가 발생하는 이유를 알아보자.
[그림 4]를 보면
1) A 지점에서 nested interrupt를 허용함으로써 동기화 문제가 발생할 가능성이 생기고,
2) B 지점에서 프로세스 스케쥴링을 허용함으로써 동기화 문제가 발생할 가능성이 생기고,
3) C 지점에서 문제가 되는 영역을 접근함으로써 동기화 문제가 구체적으로 발생한다.
일반적으로 동기화 문제는 첫째는 임의의 지점에서 hardware interrupt를 허용함으로써, 둘째는 임의의 지점에서 프로세스 스케쥴링을 수행함으로써 발생한다.
시스템 콜 루틴간의 경쟁 상태에 대한 해결책
그러면 이러한 경쟁 상태를 어떻게 막을지 생각해 보자. 앞에서 우리는 루틴간 경쟁 상태가 발생하는 이유 세 가지를 보았다. 이에 대한 해결책은 각각 다음과 같다.
1) A 지점에서 hardware interrupt를 허용하지 않거나,
2) B 지점에서 프로세스 스케쥴링을 허용하지 않거나,
3) C 지점에서 문제가 되는 영역을 접근하지 못하게 하면 된다.
시스템 콜 루틴간의 경쟁 상태에 대한 해결책
그러면 이러한 경쟁 상태를 어떻게 막을지 생각해 보자. 앞에서 우리는 루틴간 경쟁 상태가 발생하는 이유 세 가지를 보았다. 이에 대한 해결책은 각각 다음과 같다.
1) A 지점에서 hardware interrupt를 허용하지 않거나,
2) B 지점에서 프로세스 스케쥴링을 허용하지 않거나,
3) C 지점에서 문제가 되는 영역을 접근하지 못하게 하면 된다.
좀 더 구체적으로 해결책을 알아보자.
1) 일반적으로 CPU마다 hardware interrupt를 허용하지 않게 하거나 허용하게 하는 명령어를 가지며 이를 이용하여 루틴내의 적당한 구간에서 hardware interrupt를 허용하지 않을 수 있다. 우리는 이 두 명령어를 각각 cli, sti라고 하자. 이 두 명령어를 이용하여 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]을 다음과 같이 처리할 수 있다.
cli
디바이스를 사용하고 있지 않으면
디바이스를 사용한다고 표시하고
sti
여기서 한 가지 주의할 점은 일반적으로 디바이스 버퍼를 접근할 때는 시간상 연속으로 접근할 때 디바이스에 대한 활용도가 높다. 따라서 위의 루틴은 다음과 같이 처리하기로 한다.
cli
디바이스를 사용하고 있지 않으면
디바이스를 사용한다고 표시하고
데이터를 디바이스 버퍼에 쓰고 나간다
sti
2) 일반적으로 프로세스 스케쥴링을 허용하지 않는 것을 schedule lock 또는 preemption lock이라 한다. 리눅스 커널 2.5 버전 이후부터는 preempt_disable(), preempt_enable()이라는 함수를 이용하여 프로세스 스케쥴링을 허용하지 않을 수 있다. preemption lock은 다음에 볼 flag나 lock에 해당하는 변수를 이용하여 논리적으로 독립적인 루틴간에 경쟁 상태를 해결하는 방법이다. 따라서 여기서는 이 방법에 대해 더 이상 구체적으로 다루지 않는다.
3) 논리적으로 flag나 lock에 해당하는 변수를 두어 문제가 되는 영역을 동시에 접근하지 못하게 한다. 예를 들어 문제가 되는 영역에 들어가고자 할 땐 flag를 내리고 들어가고 나올 땐 flag를 올리고 나오는 개념이다. 좀 더 구체적으로 보자. 문제가 되는 영역에 들어가고자 할 땐 다음과 같은 루틴을 수행한다.
while(1) {
if(flag]0) {
flag--;
break;
}
}
즉, 문제가 되는 영역에 들어가고자 할 땐 flag가 올려져 있는지 보고 올려져 있으면 flag를 내리고 들어가고 그렇지 않으면 flag가 올려질 때까지 기다린다.
문제가 되는 영역에서 나올 땐 다음과 같은 루틴을 수행한다.
flag++;
즉, 문제가 되는 영역에서 나올 땐 flag를 올리고 나온다.
이 두 루틴을 이용하여 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]을 다음과 같이 처리할 수 있다.
그런데 이 루틴의 ⓐ 부분과 ⓑ 부분은 논리적으로 구조가 같다. 따라서 ⓑ 부분에서 발생할 수 있는 동기화 문제가 ⓐ 부분에서도 발생한다. 따라서 이 루틴을 그대로 사용할 경우 문제가 있으며, ⓒ 부분을 다음과 같이 바꾼다.
while(1) {
cli;
if(flag]0) {
flag--;
sti;
break;
}
sti;
}
ⓓ 부분도 다음과 같이 바꾼다.
cli;
flag++;
sti;
이 두 루틴을 이용하여 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]을 다음과 같이 처리할 수 있다.
그런데 앞에서도 보았던 것처럼 이 루틴의 ⓐ 부분과 ⓑ 부분은 논리적인 구조가 같다. 따라서 굳이 이와 같은 방법을 사용하지 않고 1)과 같은 방법을 사용하면 된다.
참고로 flag와 같은 속성을 갖는 변수를 세마포어 변수라고 한다. 또 뮤텍스 변수도 이와 같은 속성을 갖는다.
이상에서 [시스템 콜 루틴 내부의 i) 항목의 ⓐ 부분]은 1)과 같이 처리하기로 한다.
시스템 콜 루틴과 bottom half 루틴간의 경쟁 상태
다음은 [시스템 콜 루틴 내부의 ii) 항목]과 [bottom half 루틴 내부의 ii) 항목]간에 경쟁 상태와 이에 대한 해결책을 알아보자.
[그림 5]와 [그림 6]은 [시스템 콜 루틴 내부의 ii) 항목]과 [bottom half 루틴 내부의 i) 항목]간에 경쟁 상태를 나타낸다.
[그림 5] 시스템 콜 루틴과 bottom half 루틴간의 경쟁 상태 1
먼저 [그림 5]에서 프로세스 Pn이 시스템 콜을 통해 커널 영역에서 [시스템 콜 루틴 내부의 ii) 항목]의 앞부분([그림 5]의 ① 부분)을 수행하는 도중에
1) A 지점에서 nested interrupt가 발생하고, B 지점에서 bottom half가 수행되기를 요청하면,
2) C 지점을 거쳐 [bottom half 루틴 내부의 i) 항목]([그림 5]의 ② 부분)을 수행하고 (논리적으로는 [bottom half 루틴 내부의 ii) 항목]을 수행해야 함)
A 지점으로 다시 나와 [시스템 콜 루틴 내부의 ii) 항목]의 뒷부분([그림 5]의 ③ 부분)을 수행한다.
[그림 6] 시스템 콜 루틴과 bottom half 루틴간의 경쟁 상태 2
다음은 [그림 6]에서 프로세스 Pk가 시스템 콜을 통해 커널 영역에서 [시스템 콜 루틴 내부의 ii) 항목]의 앞부분([그림 6]의 ① 부분)을 수행하는 도중에
1) A 지점에서 nested interrupt가 발생하고,
B 부분을 포함해 한 번 이상의 프로세스 스케쥴링을 거쳐, 어느 시점에 프로세스 Pn을 수행하고, 프로세스 Pn의 C 지점에서 hardware interrupt가 발생하여 top half 루틴과 bottom half 루틴을 차례로 수행한다. bottom half 루틴에서는,
2) D 지점을 거쳐 [bottom half 루틴 내부의 i) 항목]을([그림 6]의 ② 부분을) 수행하고 (논리적으로는 [bottom half 루틴 내부의 ii) 항목]을 수행해야 함)
이후에 한 번 이상의 프로세스 스케쥴링을 거쳐 어느 순간 프로세스 Pk가 h 지점으로 나와 (이전에 B 부분의 g 지점으로 들어감) [시스템 콜 루틴 내부의 i) 항목]의 뒷부분([그림 6]의 ③ 부분)을 수행한다.
[그림 5]와 [그림 6]과 같은 경우 디바이스는 사용하지 않으면서 데이터는 데이터 큐에 남아 있는 상황이 발생하며, 일반적으로 이런 상황을 starvation이라 한다. 이와 같은 상황은 데이터 큐 사용구간에서 hardware interrupt에 의한 시스템 콜 루틴과 bottom half 루틴간 경쟁 상태가 발생하여 나타난다. [그림 5]와 [그림 6]에서는 [데이터 큐 사용구간 ⒜]와 [데이터 큐 사용구간 ⒝]간에 경쟁 상태가 발생하였다. 이와 같은 경쟁 상태는 [그림 3]의
[데이터 큐 사용구간 ⒜], [데이터 큐 사용구간 ⒝]와 같은 순서가 되도록 해결해야 한다. 즉, 데이터 큐 사용구간이 겹치지 않도록 한다.
그러면 [시스템 콜 루틴 내부의 ii) 항목]과 [bottom half 루틴 내부의 i) 항목]간에 경쟁 상태가 발생하는 이유를 알아보자.
[그림 5]와 [그림 6]을 보면
1) A 지점에서 nested interrupt를 허용함으로써 동기화 문제가 발생할 가능성이 생기고,
2) 각각 C 지점과 D 지점에서 문제가 되는 영역을 접근함으로써 동기화 문제가 구체적으로 발생한다.
시스템 콜 루틴과 bottom half 루틴간의 경쟁 상태에 대한 해결책
이에 대한 해결책은 이미 앞에서 본 것처럼 각각 다음과 같다.
1) A 지점에서 hardware interrupt를 허용하지 않거나,
2) 각각 C 지점과 D 지점에서 문제가 되는 영역을 접근하지 못하게 하면 된다.
좀 더 구체적인 해결책은 다음과 같다.
1) [시스템 콜 루틴 내부의 ii) 항목]을 다음과 같이 처리하면 된다.
cli
디바이스를 사용하고 있으면
데이터를 데이터 큐에 넣고 나간다
sti
2) 먼저 [시스템 콜 루틴 내부의 ii) 항목]과 [bottom half 루틴 내부의 i), ii) 항목]을 각각 다음과 같이 처리해 본다.
while(1) {cli; if(flag]0) {flag--; sti; break;}sti;}
디바이스를 사용하고 있으면
데이터를 데이터 큐에 넣고 나간다
cli; flag++; sti;
while(1) { cli; if(flag]0) {flag--; sti; break;}sti;}
데이터 큐가 비어 있으면
디바이스를 다 사용했다고 표시하고 나간다
데이터 큐가 비어 있지 않으면
데이터를 하나 꺼내서 디바이스 버퍼에 쓰고 나간다
cli; flag++; sti;
그러나 이렇게 처리할 경우 각각 C 지점과 D 지점에서 데드락이 발생한다. 따라서 C 지점과 D 지점에 다음과 같은 루틴을 사용한다.
cli; if(flag]0) {flag--; sti; return;} sti;
그러나 이렇게 처리할 경우 [bottom half 루틴 내부의 ii) 항목]을 [시스템 콜 루틴 내부의 ii) 항목]이후에 수행할 수 있도록 적절한 루틴을 추가해 주어야 하는데 이럴 경우 루틴이 많이 복잡해진다.
[시스템 콜 루틴 내부의 ii) 항목]의 경우 루틴을 수행하는 시간을 예측할 수 있으며, 또한 그 시간이 충분히 짧기 때문에 일반적으로 리눅스 커널에서는 1)과 같은 방법을 사용하여 동기화 문제를 처리한다.
이상에서 [디바이스에 쓰기 동작]에 대하여 Uni-Processor 상에서 발생할 수 있는 동기화 문제와 그에 대한 해결책을 알아보았다. 다음 기사에는 일단 [디바이스에 쓰기 동작]에 대한 구체적인 예를 들여다보기로 하자.
서민우 / minucy@hanmail.net
과학기술정보연구소 및 여러 대학교에서 임베디드 리눅스 실무과정을 강의하면서 리눅스 커널 초기버전을 분석하는 작업을 통해 초보자들도 OS 의 설계 및 구현에 대해 체계적으로 접근할 수 있는 방법에 대한 자료를 제작하는 데에 힘을 쏟고 있다. 50개 정도의 명령어, pipeline 등을 포함한 32 bit RISC CPU 를 설계 및 구현한 경험이 있고 uCOS/II 정도 수준의 OS 설계 및 구현에 대한 체계적인 접근 방법에 대한 자료까지 완성한 상태이며 지속적인 작업을 통해 커널과 OS에 관한 유용한 정보를 널리 공유하고자 노력하고 있다.
TAG :
이전 글 : 윈도우 디스크 정리 팁
최신 콘텐츠