[운영체제] 3. 프로세스 동기화 (1) - 상호배제와 Busy Waiting

프로세스는 단독으로 자원을 경쟁적으로 사용하면서 실행되기도 하지만 서로 통신하고 협력하면서 실행되기도 한다.

프로세스 사이에 통신할 때는 크게 3가지 문제점이 있다.

 

1. 어떻게 하나의 프로세스에서 다른 프로세스로 정보를 넘길 것인가?

2. 어떻게 각 프로세스가 중요한 동작을 하고 있을 때 서로를 방해하지 않도록 보장할 것인가?

3. 프로세스와 프로세스의 동작 사이에는 의존성이 존재할 수 있는데, 어떻게 올바르게 실행되도록 순서를 조정할 것인가?

(프로세스 A가 생성한 데이터를 프로세스 B가 출력한다면, 프로세스 B는 프로세스 A의 동작이 끝날 때까지 기다려야 한다.)

 

이 문제를 해결하는 것을 가리켜 '프로세스 동기화' 라고 한다.

 

우선 첫 번째 문제인 하나의 프로세스에서 다른 프로세스로 정보를 넘기는 것은 단순하게 생각했을 때 두 프로세스가 모두 공동으로 사용하는 저장공간에 데이터를 저장함으로써 해결할 수 있다.

 

하지만 여전히 2번, 3번 문제가 남아있다.

먼저 이번 글에서는 2번 문제를 해결하기 위한 '상호 배제' 에 대해 정리해보고자 한다.

 

 

경쟁 상태 (Race Condition)

두 개 이상 프로세스가 공유 데이터를 동시에 읽거나 쓸 때, 최종 결과는 마지막으로 접근하여 동작을 수행한 프로세스에 의해 결정된다.

이렇게 두 개 이상의 프로세스가 동시에 공유 데이터에 접근하여 문제가 발생하는 경우를 '경쟁 상태' (Race Condition) 이라고 한다.

 

 

예를 들어 위와 같은 스풀러 디렉토리가 있다고 해보자.

프로세스는 파일을 출력하고 싶으면 이 스풀러 디렉토리에 출력할 파일의 이름을 적으면 된다.

이 스풀러 디렉토리에는 2개의 변수가 있는데 in 변수는 출력할 파일을 집어넣을 위치를 가리키고, out 은 앞으로 출력할 파일의 위치를 가리킨다.

out 은 파일이 출력될 때마다, in은 출력할 파일을 추가할 때마다 값이 1씩 증가한다.

 

만약 프로세스 A, B 가 모두 스풀러 디렉토리에 접근해서 파일을 추가하기를 원한다고 해보자.

이때 프로세스 A가 7번 위치에 출력할 파일을 작성했는데, in 변수를 증가시키기 전에 프로세스 A에게 할당된 시간이 끝나서 프로세스 B에게 CPU가 할당될 수도 있다. (문맥 교환, Context Switching 또는 프로세스 스위칭가 발생한 것)

그러면 프로세스 B는 똑같은 7번 위치에 출력할 파일을 작성하고자 할 것이므로 기존에 프로세스 A가 써둔 출력할 파일을 덮어쓰게 되고, 프로세스 A는 분명히 스풀러 디렉토리에 출력할 파일을 등록했음에도 파일을 출력할 수 없는 문제가 발생한다.

 

레이스 컨디션은 바로 이렇게 실행 순서가 교묘하게 뒤섞였을 때, 여러 프로세스가 공유 데이터에 접근해서 의도치 않은 결과가 나오는 것을 말한다.

 

 

 

상호 배제 (Mutual Exclusion)

레이스 컨디션 문제를 방지하기 위해서는 한 프로세스가 공유 데이터에 접근해서 사용하고 있을 때, 다른 프로세스가 접근해서 사용할 수 없도록 막는 방법이 필요하며, 이 알고리즘을 가리켜 '상호 배제' 라고 한다.

 

 

임계 구역 (Critical Region / Critical Section)

임계 구역은 프로그램에서 공유 메모리 또는 파일에 접근하는 소스코드가 위치한 부분을 말한다.

(공유 데이터가 아니라 공유 데이터에 접근하는 프로그램의 영역을 말한다!)

 

임계 구역에 여러 프로세스가 동시에 접근하는 문제를 해결하는 방법은 여러가지가 있는데,

이 방법은 기본적으로 다음 4가지 조건을 만족해야 한다.

 

1. 서로 다른 프로세스는 동시에 임계구역에 존재할 수 없다.

2. 임계 구역 문제를 해결하는 알고리즘은 CPU 개수나 성능을 가정하면 안된다.

3. 임계 구역 밖에서 돌아가는 프로세스는 다른 프로세스의 작업을 방해해서는 안된다.

4. 임계 구역에 들어가기를 기다릴 때는 무한히 기다려서는 안된다.

 

 

이 그림은 임계 구역을 설정해서 상호 배제를 구현한 모습을 나타낸다.

T1 시점에 프로세스 A 가 임계구역에 들어오면 프로세스 A는 다른 프로세스가 임계 구역에 들어오지 못하도록 막고,

T2 시점에 프로세스 B 가 임계구역에 접근하면 이미 프로세스 A에 의해 임계구역이 사용중이므로 B는 접근이 막힌다.

T3 시점에 프로세스 A 가 임계구역을 떠나면 그 때 프로세스 B가 임계구역에 들어올 수 있게 된다.

 

 

Busy Waiting

상호 배제를 구현하는 가장 간단한 방법 중 하나는 Critical Region 에 있는 동안에는 해당 프로세스가 계속 running 상태를 유지하도록 하는 것이다. 물론 이 순간에 다른 프로세스는 계속해서 자신의 차례를 기다릴 것이다.

이때 기다리는 프로세스는 가만히 기다리는 것이 아니라, 계속 문을 두드리면서 내가 임계 구역에 들어갈 수 잇는지 확인하게 되는데, 이를 가리켜 Busy Waiting 이라고 한다. (바쁜 대기)

 

Disabling Interrupt

하드웨어의 고유 시간을 나타내는 clock 신호가 일정 시간 흐르면 스케줄링에 따라 현재 프로세스를 내리고 다른 프로세스를 실행 상태로 만들려는 인터럽트가 발생한다.

이때 임계 구역에 존재하는 프로세스가 내려오지 않도록 하려면 CPU가 인터럽트를 받아들이지 못하도록 막아야하는데, CPU에는 disable interrupt 라는 명령어를 통해 인터럽트를 받지 못하도록 할 수 있다.

 

단점은 이렇게 인터럽트 신호를 무시하는 로직은 프로그래머가 작성해야 하는데, 일반 프로그래머에게 하드웨어에 가까운 로직을 직접 작성하도록 하면 문제가 발생할 수도 있다. (임계 구역을 나가면 인터럽트를 다시 받도록 해야하는데 깜빡하고 키지 않았다거나)

 

운영체제의 핵심 프로그램인 커널이 동작할 때는 중요한 순간에 이렇게 직접 인터럽트를 꺼서 작업을 하기도 하지만, 일반 응용프로그램을 다루는 프로그래머에게 이런 권한을 주는 것은 위험하다.

 

Lock Variable

Disabling Interrupt 가 하드웨어적으로 인터럽트 신호 수신을 막는 해결방법이었다면,

Lock Variable 방식은 소프트웨어적인 해결 방법이다.

먼저 여러 프로세스가 공유하는 Lock 변수를 만들고 0으로 초기화해둔다.

Criticla Region 에 들어가는 프로세스는 이 Lock 변수를 확인해서 0이면 임계구역에 들어간 뒤 1로 설정하고,

만약 1이라면 이 값이 0이 될 때까지 기다린다. (이때는 단순히 기다리는 게 아니라 주기적으로 1인지 확인할 것이다)

 

하지만 이 방법은 완벽한 해결책이 될 수 없다.

바로 위에서 보았던 프린터 스풀링 디렉토리 문제가 그대로 발생할 수 있기 때문이다.

하드웨어적으로는 아무것도 막혀있지 않아서 어떤 프로세스가 임계구역에 들어가기 위해 Lock 변수를 확인했더니 0이었다고 해보자.

그런데 이 순간에 프로세스 스위칭이 발생하면 다른 프로세스가 임계구역에 들어가서 Lock 변수를 1로 설정해버린다.

이 상태에서 다시 기존 프로세스 차례가 돌아오면 이 프로세스는 자신이 마지막으로 확인했던 변수 값이 0이었으므로 의심없이 임계구역에 들어가고 이미 Lock은 1이지만 한번 더 1로 설정하게 된다.

 

 

Strict Alternation Solution (엄격한 교대)

엄격한 교대 방식은 말 그대로 두 프로세스가 서로 번갈아가면서 임계 경로에 들어가도록 하여 상호배제를 구현하는 방법이다.

 

 

 

 

이 소스코드를 살펴보자.

프로세스 1과 0이 있을 때 두 프로세스는 turn 이라는 공유변수를 갖고 있다. (일종의 락 변수)

 

프로세스 0 입장에서는 turn == 0 일 때만 임계 구역에 들어갈 수 있다.

따라서 turn 이 0이 아닐때는 계속해서 무한루프를 돌며 기다리고, 만약 turn == 0 이 되면 루프에서 빠져나와 임계 구역에 들어간다.

이렇게 바쁜 대기 방식에 사용되는 lock 변수를 Spin Lock 이라고 부른다.

임계구역을 빠져나온 뒤에는 (critical_region() 함수의 호출이 끝난 뒤) turn 변수 값을 1로 바꾸고 noncritical_region() 함수를 호출하여 임계구역 밖의 코드를 실행한다.

 

프로세스 1 입장에서는 turn이 1이 되는 순간 임계 구역에 있는 코드를 실행하고 빠져나와서 turn = 0 으로 바꾼 뒤 noncritical_region() 코드를 실행한다.

 

그런데 이 방법도 완벽한 해결책은 될 수 없다.

왜냐하면 상호배제를 구현하는 좋은 알고리즘의 조건 4가지 중 세 번째 조건, 임계 구역에 있지 않은 코드는 다른 프로세스의 동작을 방해해서는 안된다는 조건을 위반하기 때문이다.

 

만약 위와 같이 프로세스 1이 차례를 마친 상태에서 noncritical_region() 영역의 코드 실행을 1번 프로세스가 먼저 마쳤다고 해보자.

그러면 이 프로세스는 다시 while 문으로 돌아가는데, 이때의 turn 변수는 아직 0이다.

그런데 아직 프로세스 0은 noncritical_region() 에서 빠져나오지 않은 상태이다.

그러면 임계구역에 아무도 존재하지 않은 상태임에도 불구하고, '엄격하게 교대하는 순서에 맞춰 아직 0번 프로세스가 임계구역을 사용하지 않았다'는 이유만으로 1번 프로세스는 대기하게 된다.

 

(이 방식을 위의 프린트 스풀링 문제에 적용해 본다면, 한 프로세스가 한번에 하나의 인쇄만 가능한 것과 같다.

한번 인쇄하고 난 뒤에는 다른 프로세스가 인쇄를 해야 다시 자신의 파일을 인쇄할 수 있다.)

 

이런 문제 외에도 이 방식은 계속해서 공유된 락 변수 값을 체크해야 하므로 CPU 자원을 낭비하고, 두 프로세스 사이의 한 사이클 실행시간 차이가 클수록 효율이 떨어지는 문제가 있다.

그럼에도 상호 배제 (mutual exclusion)은 확실하게 제공을 하기 때문에 이 방식은 두 프로세스의 대기 시작이 매우 짧을 것으로 예상될 때 사용하는 것이 좋다.

 

 

 

피터슨 솔루션 (Peterson's solution)

기존의 엄격한 교대법이 한 프로세스가 연속적으로 임계 구역에 들어가는 것을 보장하지 못하는 한계를 지니는 것을 극복하고자 데커라는 사람이 솔루션을 제시했었다.

그런데 그 알고리즘이 너무 복잡해서 피터슨이라는 사람이 더 간결한 솔루션을 제시했다.

 

 

피터슨의 코드는 위와 같다.

먼저 기존의 엄격한 교대법과 마찬가지로 turn 이라는 공유변수를 둔다.

이때 추가적으로 interested 라는 배열을 공유변수로 둔다.

이 배열의 값은 초기에 모두 False 로 설정이 되어있으며, 현재 프로세스가 임계 구역에 들어가고 싶어하는지 (기다리고 있는지)를 나타내는 변수이다. 만약 i 번 프로세스가 임계구역에 들어가기를 희망하고 있다면 interested[i] = True 가 된다.

이 코드에서는 2개의 프로세스가 교대로 들어가는 상황을 보여준다.

 

피터슨 해결책은 임계구역에 들어가는 메서드와 나가는 메서드로 구성되어있다.

임계구역에 들어가는 메서드는 들어가는 프로세스의 번호를 매개변수로 받으며, 상대방 번호를 other 에 계산해서 넣는다.

여기에서 1 - process 로 상대방 번호를 계산한 것은 프로세스 번호가 0, 1 두 개 밖에 없기 때문에 가능한 테크닉이다.

(1을 넣으면 0이 되고, 0을 넣으면 1이 된다)

 

임계 구역에 들어가게 되면 interested 를 참으로 만들고 turn 변수를 자신의 번호로 세팅한 뒤 while 문을 돈다.

이때 반복문의 조건을 살펴보면

 

만약 내가 지금 들어갈 차례인데, 다른 프로세스가 관심을 갖고 있다면 (즉, 이미 임계 영역에 들어가 있다면) 반복문의 계속 돌면서 임계구역에 들어가는 메서드가 종료되지 않는다. (즉, 임계구역에 들어가지 못한다.)

 

다른 프로세스가 만약 임계 영역 코드 실행을 끝내면 그때는 leave_region() 메서드를 호출하는데, 이 메서드는 단순히 intersted 배열에서 해당 프로세스의 값을 False 로 설정한다. 그러면 기존에 대기하던 프로세스는 interested[other] 이 False 가 되므로 반복문을 탈출하면서 함수가 종료되고 임계 영역에 들어갈 수 있게 된다.

 

 

이렇게만 보면 상호 배제가 잘 일어나는 것 같은데 한가지 의문이 든다.

어차피 직전에 turn 값을 자신의 번호로 세팅했는데 왜 while 문에서는 turn 값이 자신과 같은지 한번 더 체크하는걸까?

 

그 이유는 지금 enter_region() 이라는 함수의 코드 자체는 '임계 영역' 에 있는 코드가 아니라서 실행 중에 얼마든지 프로세스 스위칭 당할 수 있기 때문에 그렇다.

 

조금 더 극단적으로 두 프로세스가 거의 동시에 접근하는 상황을 생각해보자.

그러면 두 프로세스 모두 enter_region() 메서드를 실행하면서 interested 배열의 값을 True로 설정한다.

 

여기까지 두 프로세스가 모두 온 뒤에 두 프로세스 중에 프로세스 0이 간발의 차이로 만저 실행된다고 해보자.

그러면 처음엔 프로세스 0이 while 문을 돌 때는 turn 변수 값이 0, other 프로세스의 interested 도 true 이므로 무한반복을 돌게 된다.

이때 간발의 차이로 나중에 들어온 프로세스 1은 이후에 turn 값을 1로 바꾸고 while 문을 돌게 되는데 이때도 turn = 1, other 프로세스의 interested 도 true 이므로 무한루프를 돈다.

하지만 turn 값이 1로 갱신되며 바뀌었기 때문에 기존의 프로세스 0의 반복문 조건이 바뀌면서 탈출하고 프로세스 0이 먼저 임계 영역에 들어가게 된다.

 

프로세스 0이 임계 영역에서 할 일을 마치고 빠져나오면 interested[0] = False 로 바뀌고 (leave_region() 실행)

이 순간 프로세스 1의 while 문 조건이 False 가 되면서 프로세스 1이 임계 영역에 들어가게 된다.

이렇게 아슬아슬한 상황에서도 피터슨 솔루션은 문제없이 안전하게 상호배제를 제공하고 있음을 알 수 있다.

 

 

 

TSL instruction

busy waiting 방법으로 상호 배제를 제공하는 또 다른 방법으로 TSL instruction을 사용하는 방법이 있다.

TSL 은 Test and Set Lock 의 줄임말로, 이름 그대로 확인해보고 락을 건다는 의미이다.

 

 

TSL 명령어는 말그대로 '명령어', 즉 어셈블리 코드 (CPU가 사용하는 명령어) 이다.

먼저 enter region 부분을 보면, TSL 명령어를 실행하면 Lock 변수의 값이 레지스터로 넣고 Lock 변수의 값을 1로 세팅한다.

(TSL 명령어 자체가 Lock 변수의 값을 레지스터에 넣고 Lock 을 1로 세팅하는 단위로 동작하는 하나의 명령어이므로, 이 동작 사이에 다른 명령어는 실행될 수 없다.)

그 다음으로 레지스터의 값을 0과 비교해서 0이 아니라면 다시 처음으로 돌아가고 (무한 반복)

레지스터의 값이 0이라면 반복문을 빠져나와 함수를 탈출한다.

(기존의 엄격한 교대 방법에서의 초기 while 문과 비슷한 역할)

 

임계 영역에 있는 코드를 다 실행하고나면 그 다음에는 leave_region 코드가 실행되며, Lock 변수에 0을 세팅한다.

기존의 Lock Variable 의 방법과 완전히 동일하지만, 그 방법이 Lock 변수의 값을 세팅하기 전에 프로세스 스위칭이 일어나서 문제가 발생할 수 있었다면, 이 방법은 하드웨어적으로 끼어들 수 없기 때문에 문제가 발생하지 않는다.

 

 

---

지금까지 레이스 컨디션 문제와 이 문제가 발생하는 공간인 임계 공간 (critical region), 그리고 레이스 컨디션을 방지하기 위한 상호 배제에 대해 정리하였다.

 

상호 배제를 달성하는 간단한 방법으로 Disabling Interupt, Lock Variable, Strict Alternation, Peterson's Solution, TSL instruction 5가지 방법을 소개하였다.

 

이 방법들은 모두 busy waiting, 즉 매번 문을 두드리면서 내가 들어갈 수 있는지 확인하는 방법으로 동작하였다.

이 방법은 CPU 시간을 낭비하는 단점이 있으며, 우선순위가 높은 순대로 프로세스 실행 순서를 스케줄링 할 때 우선순위 역전 문제를 일으키는 단점이 있다.

 

예를 들어 높은 우선순위를 가진 프로세스가 실행이 되다가 read() 와 같은 입출력 시스템콜을 호출해서 blocked 상태로 빠졌다고 해보자.

그러면 우선순위가 낮은 프로세스들이 running 상태로 올라와서 여러가지 코드를 실행할 것이다.

그리고 입출력이 끝나서 blocked 상태에 있던 프로세스가 ready 상태로 올라오면, 우선순위 방식의 스케줄링에서는 우선순위가 높은 프로세스를 우선적으로 실행한다.

 

이때 우선순위가 높은 프로세스가 실행되면서 기존 프로세스를 끌어내리는데, 하필 기존 프로세스가 임계 공간에 들어가서 공간을 잠가둔 상태였다면 어떻게 될까?

(임계 공간에 들어갔다는 것은 프로세스가 끌어내려지지 않는다는 것을 의미하지 않는다. 내가 끌어내려지더라도, 다른 프로세스가 그 공간에 들어올 수 없고, 내가 다시 돌아왔을 때 이어서 임계 공간을 계속 쓸 수 있다는 것을 의미한다.)

 

busy waiting 방식에서는 우선순위가 높은 프로세스가 계속해서 변수를 두드리면서 체크를 하다가 자신의 차례가 끝나면 ready 상태로 내려올 것이다.

그런데 우선순위 방식의 스케줄링에서는 계속 높은 우선순위에 있는 프로세스가 먼저 실행이 되기 때문에, 만약 상대적으로 낮은 우선순위를 갖는 프로세스가 임계 영역을 잠가두면 높은 우선순위에 있는 프로세스는 그 공간에 접근할 수가 없게 된다.

 

즉, 낮은 우선순위를 가진 프로세스에 의해 높은 우선순위를 가진 프로세스의 동작이 막히는 것이다.

(우선순위의 역전이 발생했다고 표현한다.)

 

그래서 이 문제를 해결하고자 busy waiting 대신 다른 방법을 고안했는데, 이 방법이 바로 Sleep and Wake up 방식이다.

계속 문을 두들기면서 기다리는게 아니라, 사용중이야? 그러면 난 자고 있을게 끝나면 깨워줘! 라고 동작하는 것이다.

이러면 문을 두들기는데 CPU를 사용하지 않으므로 CPU 시간이 낭비되지 않는 장점이 있다.

 

이 Sleep And Wake up 방식을 구현하는 알고리즘도 다양하게 있는데, 이 알고리즘에 대해서는 다음 글에서 정리하겠다.