목차
race condition은 cpu가 여러개인 컴퓨터 뿐만아니라 한개인 컴퓨터에서도 발생함.
Producer/Consumer Problem이란 프로듀서 프로세스 P 여러개와 컨슈머 프로세스 C 여러개가 함께 작업을 하는 상황에서 발생하는 Race condition을 설명하는 문제.
아래 그림과 같음.
그림에서는 P가 여러개 C가 한개지만 P가 한개이거나 C가 여러개여도 됨.
producer process는 정보를 생산하는 일을 하고, consumer process는 생산된 정보를 소비해서 다른 처리를 하는 일을 함.
이때 producer가 생산한 정보를 consumer에게 전달하기 위에 IPC를 이용한다고 가정해보자. 이 문제에서는 shared memory를 사용한다.
각 producer는 정보를 생산해서 shared memory에 만들어진 buffer의 빈 자리에 집어넣으면 consumer가 buffer에서 정보를 꺼내간다. buffer를 공유하게 되는 것.
(이때 어느 프로세스든 shared memory에 접근할 때 mutal exclusion이 보장되어야함. 그렇지 않으면 race condition이 발생해 프로그램이 잘못 동작할 수 있음)
위 그림에서 shared memory 안에 b[10]을 보자. 이는 buffer의 크기를 10으로 잡은 것. 이후 in, out, counter를 shared memory에 선언하였다. producer/consumer process는 shared memory에 본인 메모리 영역처럼 접근 가능하다.
이때 in이라는 변수는 buffer b에 정보를 집어 넣을때 어디에 넣을지 index 값을 알려주는 변수.
out은 buffer b에서 정보를 어디서 꺼내갈것인지, index 값을 알려주는 변수.
in과 out을 이용해 buffer는 circular queue로 구현됨.
in과 out의 초기값은 0. 그래서 처음에는 둘 다 b[0]을 가리키고 있음. 이때 producer가 아이템을 생산하면 b[0]에 넣고, 두번째 아이템을 넣게 될 경우에 그 다음 자리에 넣어야 하므로 in이 1이 될 것.
이런식으로 아이템이 들어갈수록 in은 1씩 증가한다.
이후 b[0]와 b[1]에 있던 아이템을 소비 후 아래 그림과 같은 상태가 됨.
아이템이 나갈수록 out은 1씩 증가한다.
만약 in과 out이 계속 증가되다가 b[n-1]에 가게 되면 더이상 진행을 못하는 것이 아니라 다시 b[0]으로 연결되어 circular buffer로 구현됨.
producer process는 다음과 같이 구현된다.
이때 % 연산은 b[n-1] 이후 b[0]으로 연결하기 위한 연산.
만약 counter와 BUFFER_SIZE가 같은 경우, buffer 안에 아이템이 꽉 찬 경우를 말함.
이때 buffer에 아이템을 더 넣으려고 하면 기존의 아이템이 덮어져 깨지기 때문에 안됨.
때문에 빈자리가 생길때까지 기다리도록 만들고, 새로운 아이템을 생성하지 못하도록 하는게 위 코드.
이때 while(counter == BUFFER_SIZE)에 body가 없는데 이를 null statement라고 함.
해당 코드는 cpu가 아무것도 없는 instruction을 실행함.
그리고 다시 while(counter == BUFFER_SIZE)로 돌아가 비교후 또 조건이 성립하면 instruction 실행X.
이런식으로 counter가 BUFFER_SIZE와 같지 않을때까지 조건을 체크하고 while문을 반복함.
위와 같이 어떤 조건이 성립할때까지 반복문을 실행하면서 기다리는 방법을 busy waiting이라고 한다.
이때 busy waiting이 끝나려면 consumer가 아이템을 빼갈때까지 기다려야함.
그런데 이때 consumer가 아이템을 빼가려면 consumer가 실행되어야하는데, 현재 producer 하나가 busy waiting을 하면서 while문장을 실행중이기 때문에 cpu를 사용중이다.
때문에 consumer를 cpu가 실행시킬 수 없어서, producer가 time slice를 전부 소비할때까지 계속 busy waiting한 후에 cpu가 consumer로 넘어갈 수 있을 것이다.
이때 consumer가 실행될 수 있는 것.
consumer process는 다음과 같이 구현된다.
가장 먼저 counter가 0인지, 즉 buffer에 아무것도 없는지 확인 후 아이템이 들어올때까지 busy waiting을 한다.
만약 producer가 busy waiting하다가 consumer로 cpu가 넘어온 상태라면 buffer가 0이 아닐것이다. 때문에 바로 다음 코드를 실행 가능하다.
buffer의 out 위치에서 아이템을 꺼내고, out 포인트를 옆으로 하나 옮긴다. 이때 마찬가지로 circular queue 구현을 위해 % 연산을 수행한다.
위에서 사용한 counter 변수는 현재 buffer에 아이템이 몇개 들어있는지를 나타내고, producer와 consumer가 같이 값을 읽고 변경시킬 수 있는 공유변수이다. 공유메모리에 있기 때문에 가능하다.
* producer가 buffer가 가득 차서 아이템을 못넣은 이후에 consumer가 아이템을 하나 소비하더라도 producer가 바로 알아차리고 실행하는 것이 아니다. 두 프로세스는 동시에 실행되고 있는 것이 아니라, producer의 busy waiting이 끝나고 consumer가 실행되면 producer는 cpu를 가지고 있지 않은 ready 상태이며, consumer가 이후 time slice를 모두 소비한 후에 ready 상태이던 producer가 실행될 수 있는 가능성을 가지는 것이기 때문이다. consumer가 counter를 감소시켰다고 ready상태에 있는 producer가 바로 알 수 있는게 아니고, consumer가 실행되는 동안에는 consumer만 counter의 변화 사실을 아는 것이다.
하지만 위 두 프로그램 코드는 문제없이 동작하지 않는다. race condition이 발생할 수 있다.
위 코드에서 counter++와 counter-- 는 critical section이다. critical section은 mutal exclusion하게 실행되어야하는데, 그런다는 보장이 없다.
구체적으로 race condition이 발생하는 방식.
counter++와 counter--는 한 문장으로 보이지만, 이 high level language는 컴파일되면서 아래와 같이 저수준 언어인 assembly language 세 개로 변환된다.
위 instruction 실행 중 interrupt 때문에 race condition이 발생한다.
📁 Interrupt
컴퓨터 하드웨어 장치가 cpu에게 어떤 이벤트가 발생했음을 알리는 방법.
하드웨어 장치가 전기적인 신호를 띄우면 신호가 PIC칩으로 전달되고 이 PIC칩이 CPU에 연결돼있어서 CPU에 신호를 전달한다.
예를 들어 clock 하드웨어가 신호를 띄웠을때, cpu는 인스트럭션 하나 실행 후에 전기적인 신호가 떴는지 확인한다. 만약 없을 경우 다음에 실행할 assembly instruction을 메모리에 가져와서 실행한다.
만약 instruction 실행 후 신호가 있을 경우 커널은 현재 하던 일을 중단하고, 커널에 구현된 interrupt 처리 함수를 실행 후 다시 되돌아와서 실행하던 프로그램 다음 instruction을 이어 실행한다.
위 사진을 보면 clock과 cpu가 연결되어있다. clock은 하드웨어와 운영체제에 따라 정해지는 주기마다 interrupt를 발생시킨다.
예를 들어 intel 프로세서에서 실행되는 리눅스 운영체제의 경우 1/1000초(1msec)마다 interrupt를 걸도록 설정되어있다. 타임슬라이스의 길이가 100msec이므로 한 번의 타임슬라이스동안 100번 clock interrupt를 받게 된다.
cpu는 clock interrupt를 받으면 커널로 모드체인지해서 interrupt를 처리한다. 이때 clock interrupt가 몇번 걸렸는지를 카운트하는 별도의 카운터가 있어서, 이 카운트 값이 100이 되었는지 체크하는데 되지 않았으면 사용자 코드로 돌아가서 계속 실행하고, 100이 되었으면 타임슬라이스가 다 지나갔다는 의미이므로 cpu를 회수해서 스케줄러를 불러 다른 프로세스를 선정한 후에 새로 선정된 프로세스에게 cpu를 배정한다. (-> 프로세스 스위치)
위와 같이 clock interrupt 처리 후 context switch가 발생할수도 발생하지 않을수도 있다.
만약에 counter++ 코드를 실행중이라고 가정하자. 이를 위해서는 5 값을 레지스터에 load하고, 레지스터값을 증가시키고, counter에 저장하는 세 instruction을 거쳐야한다. 하지만 cpu는 각 instruction 실행 후에 interrupt 신호가 떴는지 확인하는데, 만약에 register값을 증가시킨 두번째 instruction 후에 clock interrupt가 걸렸고, 해당 clock interrupt가 100번째여서 context switch가 일어난다. 이후 새로 cpu를 받은 프로세스가 consumer라면, consumer process는 buffer에서 아이템을 빼오고 counter를 감소시키려고 할 것이다. 그런데 이때 buffer에는 아이템을 빼기 전에는 6개의 아이템이 있었겠지만, store insturction을 실행하기 전에 context switch가 일어났기 때문에 counter값은 5이다. 그래서 consumer가 counter--를 실행하게 되면 counter는 4가 된다. consumer 입장에서는 정상적으로 실행되는것.
이후 consumer 타임슬라이스가 소진되고 중단됐던 producer에 다시 cpu가 주어졌다고 해보자. 그런데 이때 pcb에 레지스터 값을 저장하는 부분이 있기 때문에 과거에 저장했던 6이 레지스터에 복구되고 store instruction을 실행하게 되기 때문에 이전 counter값이 뭐였던간에 6이되고만다.
이는 producer가 counter값을 증가시키는 instruction 중간에 consumer가 counter값을 바꾸는 코드가 끼어들어가 문제가 된 것이다.
consumer와 producer가 실행해야하는 instruction 세 개가 나란히 계속 실행된다는 보장이 있다면 문제가 없을것이다.
race condition은 위와 같이 프로세스들 사이의 공유 메모리에서만 일어나는 현상이 아니라, 한 프로세스 내에서 여러 쓰레드들 사이에서도 발생한다.
같은 프로세스 내의 여러 쓰레드는 프로세스 안에 있는 데이터 영역을 공유한다. 만약 하나의 쓰레드가 데이터 영역에 있는 어떤 변수 값을 변경하는 과정에서 다 끝내지 못한 채로 쓰레드 스위치가 일어나게 되면 데이터 영역의 global variable에 race condition이 발생할 수 있다.
📁 Race condition을 방지하는 방법
위 코드의 문제점은 producer와 consumer의 critical section이 겹친것이다. 이는 두 critical section이 mutal exclusion하게 실행되지 않은 것이다.
mutal exclusion하게 실행이 됐다면 producer가 counter 값을 변경하는 동안에 consumer가 counter값에 접근하지 않았을 것이다. 이렇게 하기 위해선 producer의 critical section을 실행하는 동안에 consumer외에도 다른 프로세스가 counter 변수에 접근하지 못하도록 하면 된다.
1. critical section을 atomic opertaion으로 만드는 방법
automic하게 실행한다 : critical section을 assembly instruction 한 문장인것처럼 실행해서 실행 도중에 중단되지 않도록 하는 것.
automic operation으로 실행시키기 위해 interrupt를 disable시켜야한다. 이는 interrupt가 걸려와도 실행을 하지 않고 interrupt가 왔는지 조사하지 않는 것이다. interrupt disable 선언 후 assembly instruction을 실행하면 cpu가 instruction 하나를 실행한 후에 interrupt를 조사해야하지만 그러지 않고 다음 instruction을 바로 실행할 것이다. 이후 counter++ 코드를 예시로 들면 3개의 instruction이 끝난 후 interrupt를 다시 활성화 시킨다.
이때 interrupt disable한다는 것은 interrupt가 발생하지 않도록 막는 것이 아니라, 발생을 하지만 그 당시에는 조사하지 않았다가 interrupt가 활성화되면 그 때 조사하는 것이다. 만약 automic operation 실행 도중에 interrupt가 발생했었다면 활성화 이후 커널로 모드체인지하여 처리하는것이고, 발생하지 않았다면 다음 instruction을 실행한다.
하지만 이건 좋은 방법이 아님.
만약 critical section의 instruction이 위처럼 3줄이 아니라 수많다면, 그 automic operation을 수행하는데 많은 시간이 걸릴 것이다. 즉 disable부터 able까지 interrupt를 전혀 처리하지 않고, interrupt를 처리할때까지 시간이 굉장히 오래걸리기 때문에 시스템 운영에 문제가 생길 수 있다.
예를 들어 네트워크로부터 다른 컴퓨터에서부터 패키지에 도착한다고 할때 통신 인터페이스(예를 들어 이더넷 컨트롤러 하드웨어)가 interrupt를 발생시켜서 커널이 빨리 패킷을 수신해야하는데 interrupt가 비활성화되어있으면 패킷을 빨리 받지 못하고 그 다음으로 오는 패킷과 겹쳐서 내용이 깨질수가 있다.
또 다른 이유는, 만약 마우스나 키보드로 OS에 어떤 명령을 내리려고 해도 OS가 감지하지 못해서 바로 실행하지 못할 수 있다.
2. critical section 주변에 fence를 치는 방법
critical section 코드를 실행할 때 담장 문을 잠그고, 담장 안에는 하나의 프로세스만 들어올 수 있도록 하여 mutal exclusion이 보장되도록 한다.
담장 안에 들어와 있는 프로세스가 instruciton을 실행할때 automic operation처럼 disable하지 않고 정상적으로 걸릴 수 있게 해서 context switch가 일어날 수도 있게 한다.
결국 critical section 자체가 automic operation이 되는것이 아니라, interrupt가 걸릴 수 있는 보통 instruction이다.
예를 들어 producer가 critical section의 두번째 instruction까지 실행했다가 consumer로 context switch했다고 가정하자. 이때 critical section에는 담장이 있고 기존의 producer 프로세스가 잠궜기 때문에 consumer는 접근하지 못하고 time slice가 다 소비될때까지 기다려야한다. 이후 다시 producer에게 cpu가 주어지면 마지막 instruction을 실행하고 담장 밖으로 나온다. 이후에 consumer가 담장 안으로 들어갈 수 있는 것이다.
다음 포스팅에서 자세히 설명한다.
