- 개념!!

군 생활을 하다 보면, 개념 없는 사람들을 많이 보게 됩니다. 가끔은 '내가 평생 이런 놈을 다시 볼 수 있을까?'싶은 사람도 보게되죠. 그리고 인간관계란 과연 무엇인지 원점에서 다시 생각해 보게 됩니다. 개념 없는 사람들도 사회에서 담당하는 역할이 있는 셈이죠. 오늘은 병렬 프로그래밍에 필요한 개념들을 같이 채워볼까 합니다. 개념 충만한 사람들은 훠이훠이~ 절로 가시고(저는 종교의 다양성을 존중합니당. 교회로 가실 분은 교회로..), 개념 없는 사람들만 저랑 같이 개념을 채워 보시져. 훗.


- 기본 개념!!!

스레드(Thread)

스레드는 다른 순차적 명령 집합(sequence of instructions)과 동시적으로 실행 가능한 순차적 명령 집합을 이야기 합니다. 예를 들면, 뭔가 작업을 처리하는 스레드가 있고, 그 작업의 현황을 화면에 표시하는 스레드가 있는 것 처럼 말이죠. 두 스레드는 서로 다른 순차적 명령 집합을 가지며, 동시적으로 실행 가능하죠. 그리고 두 개 이상의 스레드를 동시적으로 실행하는 것을 멀티스레딩(multithreading)이라고 합니다. 흔히 이야기 하는 동시성이나 병렬성도 최대한 효율적으로 스레드를 여러개 사용하는 것이므로, 멀티스레드의 범주에 들어간다고 할 수 있겠습니다. 운영체제는 이런 멀티 스레드를 동시적으로 처리하는 것 처럼 보여주기 위해서 시간 쪼개기(time slicing)이라는 기법을 활용합니다. 즉, 사람이 눈치채지 못할 정도로 빠른 시간만큼 한번에 하나씩 스레드를 처리하는 것이죠. 단순하게 생각해서, 음악을 들으면서 비주얼 스튜디오로 코딩을 한다면, 사람이 눈치채지 못할 정도의 속도로, 예를 들면 1/24초 정도의 속도로 한번은 음악재생, 한번은 비주얼 스튜디오, 또 한번은 음악 재생, 또 한번은 비주얼 스튜디오 이런식으로 번갈아 가면서 처리하는 것이죠. 이걸 문맥 교환(context switching)이라고 합니다. <그림1>을 보시죠.

<그림1>본격 OS 스케쥴링 그림.jpg

<그림1>에서 나온 것 처럼, 사용자가 눈치채지 못 할만큼의 속도로 두 작업을 번갈아 가면서 CPU가 처리하도록 OS가 스케쥴을 조절하는 것이죠. 그런데 만약, 스레드가 너무 많아서 제대로 CPU를 점거하지도 못하고, 작업을 계속해서 교체하게 되면 어떻게 될까요? 실제로 CPU가 작업을 처리하는 시간보다, 문맥 교환에 더 많은 시간이 들어가게 되므로, 음악이 벅벅 끊기는 등의 지름유발상황이 생기겠죠. 그럼, 시간 쪼개기를 한번 시뮬레이트 해 볼까영? 어헣.

using System;
using System.Threading.Tasks;

namespace Exam2
{
    class Program
    {
        static void Main(string[] args)
        {
            const int max = 10000;

            //현재 작업중인 스레드외에 추가로 스레드를 생성
            Task task = new Task(() =>
                {
                    for (int count = 0; count < max; count++)
                    {
                        Console.Write("|");
                    }
                });

            //추가 스레드 시작
            task.Start();

            //현재 작업중인 스레드에서도 반복문 시작
            for (int count = 0; count < max; count++)
            {
                Console.Write("-");
            }

            //혹시 현재 스레드가 빨리 끝나더라도,
            //추가 스레드가 끝날 때 까지 기다리기.           
            task.Wait();
        }
    }
}

<코드1>아주 단순한 코드

<코드1>은 아주 단순한 코드입니다. 콘솔 어플리케이션의 실행을 담당하는 스레드 외에, 추가로 스레드를 하나 더 생성해서, 두 스레드에서 똑같은 반복문을 돌면서 서로 다른 문자를 출력하게 하는 거죠. 결과를 볼까요?

-|---||||||||||||||||------|||||||||||||||---------------|||||||||||||-----------||||||--------------|||||||||||||--------------|||||||||||||------------||||||||--------------||||||||||||----------||||||||||||||---------|||||||||||||--------|||||||||||||||--------------|||||||||||||||-------------||||||||||||-||||||||||-----------------|||||||||||||||-------------||||||||||||||--|||||||||||||-------|||||||---------------|||||||||||||||----------||||||||||||||---------|||||||||-----------------||||||||||||||-------------|||||||||||||-------------||||||||||-----------------|||||||||||||------------|||||||||||||-----------||||||||------|||||||||||||--------|||||||||||||||-----||||||||||||||-------------||||||||||||----------------|||||||||||||---------------|||||--------------|||||||||||||----||||||||||||||||--------------|||||||||||||||---------||||||||||||-----------|||---------------||||||||||||||||----------------||||||-------------|||||||||----|||||||||||||||||-------------||||||||||||||-||||||||||||||-------------||||||||-------|||||||||||||||--------|--|||---------|||||||||||||--------|||||||||||---|||||||||||||||----------------|||||||||||||||--------------||||-----------------------------------------------------------------------------------------------
계속하려면 아무 키나 누르십시오 . . .

<결과1>평범한 결과

서로 다른 문자가 출력되는 곳이 바로, 시간 쪼개기로 인한 문맥 교환이 일어나는 곳입니다. 정해진 시간만큼 한 스레드가 CPU를 점거하고 작업을 하는 것이죠. 그러면, 약간 방해를 해볼까요? 코드를 다음과 같이 약간 수정해봅니다.

Console.ReadLine();

//추가 스레드 시작
task.Start();

<코드2>수정된 아주 평범한 코드

그리고 이 프로그램이 사용자의 입력을 기다리는 동안, 다음과 같이 프로세스의 우선순위를 낮춰버립니다.

<그림2>프로세스 우선순위 낮추기 ㅋ

그리고 한번 실행해 볼까요? 프로세스의 우선순위가 낮아지면, 실행중인 작업이 우선순위가 높은 다른 프로세스에게 방해를 받을 가능성이 높아지는 거죠.

---------|||||||----||||||||||||||||-----||||||||||||--------||||||||||||||------------|||||||||----------------||||||||||||||------------||||||||||||||-------------|||||||||||----------------|||||||||||||-----------||||||||||||||-------------||||||||||||--------||||||||||||||------------|||||||||||||||-------------|||||||||||||------||||||||||||||-------------||||||||||||||--------------|||||||||||-----------||||---------------|||||||||||||-------------||||||||||||||-------|||||||||||||----|||||||||||||--------------|||||||||||||||-------------|||||||||||||-|||||||||||---------------||||-------------|||||||||||||-------------|||||||||||||---------|----------------|||||||||||||-------------||||||||||||||-----------||||||||||||---------------|||||---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
계속하려면 아무 키나 누르십시오 . . .

<결과2>낮은 우선순위 결과

그런데, <결과2>를 보니, 얼마나 방해를 받은 건지 솔직히 잘 모르겠네요.('-'가 마지막에 막 출력된 건, '|'를 출력하는 스레드가 빨리 작업을 끝내서 입니당) 제 컴이 쿼드에 2.7GHz짜리인데, 아마도 이정도로는 방해가 안되는 거 같습니다. 그래서! 비주얼 스튜디오 2010 20개랑, 음악을 틀고, 바이러스 검사를 돌리고, 인터넷 익스플로러 8도 창을 7개정도 띄워놓고 실험을 해봤습니다.

-||||||||||||||||-------------|---------------|--------------||||||||||----------||||||||||||||-----------||||||||||||--------------|||||||||||---------||||||||-|||||||----|||||||||------------|||||||||||||-------------|||-----------||||||||---------------||||||||||||||-------------||||||-------------||||||||||--------||||||||||||||----|||||||||||||||--------------||||||||||||-----------||||||||||----------------|||||||||||----------|------------||-|||||||||------||-------|||--------------|||||||||||||------------|||||||||||||-------------|||||||||||----|||||||||||-----||||||||||||||---------------||||||||||||||------------|||||||||----------------||||||||||||--------|||||||||||||-------------|||||||||-------|||------------|||||-----|||||||------||||||||||||||||---------------------||||||------|||||||||||||||-------------||||||||||||||-------------||||||||||||--------||||||||||||||||-------------||||||||||--------------|||||||||-------||||------|----||||||-----||||||||||||||-------------|||||||||------------|||||||||||-------||||||||||||||--------------||||||||||||||--------------||||||||||--------||||
|--------------||||||||||||||||-----------|||||||||||||--|||||||||||------||||||||----------------||----||||||||||||||-----||||||||||||||||||||||||||||||||||||||
계속하려면 아무 키나 누르십시오 . . .

<결과3>갖가지 태클을 가한 결과

<결과3>을 보시면, 어느 정도 패턴이 불안정 해진 걸 보실 수 있습니다. 제대로 처리도 못하고, '|'이거 딱 한개 출력하고 문맥 교환이 일어난 부분도 꽤 보이네요.


원자성(Atomicity)

원자성은 뭘까요? 원자성을 만족하는 조건을 보지요. 아래 조건 중에서 하나를 만족하면 원자성을 만족하는 것입니다.

1. 작업을 처리하기 위한 명령어 집합은 다른 작업이 끼어들기 전에 반드시 완료되어야 한다.
2. 작업을 처리 중인 시스템의 상태는, 작업을 처리하기 전의 시스템의 상태로 돌아갈 수 있어야 한다. 즉, 아무 작업도 처리되지 않은 시스템의 상태로 돌아갈 수 있어야 한다.

예를 들면, 은행 계좌에서 돈을 송금하는 걸 생각해보면요. 돈을 송금하기위한 몇가지 단계가 있습니다. 일단 계좌에 돈이 있는지 확인하고, 보낼 계좌가 존재하는지 확인하고, 그리고 돈을 실제로 송금하는 것이죠. 이렇게 송금을 위한 각 단계를 밟는 와중에, 돈을 인출한다던가 하는 작업이 끼어들면 안되겠죠. 그리고 송금 절차가 완료되기 전에는 계좌에 아무런 변화가 없어야 하는 거죠.

C#에서 num++같은 연산을 보면, num의 값을 가져오고, num의 값을 1 증가시키고, num에 증가된 값을 넣는 절차를 밟는데요. ++연산자는 원자성을 만족하지 못합니다. 그래서 num에 증가된 새 값을 넣기 전에, 다른 스레드가 원래 값을 변경 시켜버린다던가 하는 일이 벌어질 수 있죠.


데드락(Deadlock)

데드락은 죽음을 잠근다는 뜻이므로, 죽지 않는다는 뜻입니다. 네, 저를 죽이려고 달려드는 사람들의 모습이 보이네요. 모두들 잠깐만 진정하시고....-_- 이건 서로 볼을 꼬집고서, '니가 먼저 안놓으면, 나도 안놓을 꺼임'하고 외치고 있는 꼬마들을 생각하시면 됩니다. 꼬맹이들은 괜한데서 자존심을 세우죠. 그래서 먼저 놓으면 지는거라고 생각해서 안 놓습니다. 그래서 서로 계속해서 볼을 꼬집고 질질 짜게 되는 거죠. ㅋㅋㅋ

한 스레드는 A라는 자원을 점거하고, B를 가지고 와야 A를 놓아줍니다. 그리고 또 다른 스레드는 B라는 자원을 점거하고, A를 가져와야 B를 놓아준다고 해보죠. 그러면 이 스레드들은 서로 상대방이 가진 자원을 하염없이 기다리는 상황이 됩니다. 죽을 때까지 그 상태로 기다리겠죠. 그래서 이건 데드락입니다. 어헣.


- 정리하면서

위에서 설명드린 원자성이나 데드락은 여러개의 스레드에서 어떤 순서로 명령어를 실행하느냐에 따라서 복잡하게 발생합니당. 이런 프로그램을 짜려면 머리 빠지겠죠. 아이 무셔워라. 그래서 조심해야 하는 것이고, 이런 실수를 최대한 줄여주는 도구가 있어야 하는 것이죠!!

이게 왠 운영체제 수업이냐 하고 반감을 가지시는 분덜도 있으시리라 생각이 됩니다. 모.. 복습했다 생각하시고 어헣. 좋은게 좋은거니깐.. 어헣.


- 참고자료

1. http://www.cafeaulait.org/course/week11/03.html
2. Essential C# 4.0, Mark Michaelis, Addison Wesley

저작자 표시 비영리 변경 금지
신고
이 글은 MSDN 글, "Solving The Dining Philosophers Problem With Asynchronous Agents"를 참고하여 작성되었습니다.

Asynchronous Agents Library로 Dining Philosophers 문제 해결하기 - 1
Asynchronous Agents Library로 Dining Philosophers 문제 해결하기 - 2

오래 기다리셨습니다; 그간 일이 바빠서;; 어쨌든 지난번에 Concurrecy::agent 에서 상속받은 Philosopher 클래스를 살펴봤었죠. 아래 두 함수만 제외하고 말입니다.

자 먼저 젓가락을 집는 함수입니다. 젓가락 한쌍을 동시에 집어야지 하나만이라도 먼저 집으려고 하다간 서로 젓가락 하나씩 잡고 기다리는 데드락 상황이 발생할 수 있습니다. 이를 위해 쓰이는 것이 지난 회에 잠깐 언급했든 join 메시지 블록입니다. 그 중에서도 non_greedy 버전을 사용해야 합니다. non_greedy 버전은 명시된 타겟을 모두 얻을 수 있을 때에만 실제 획득을 시도합니다. gready 버전을 사용하면 전술한 것처럼 데드락이 발생할 수 있습니다.

   73     std::vector<Chopstick*> PickupChopsticks()

   74     {

   75         //join 생성

   76         Concurrency::join<Chopstick*,Concurrency::non_greedy> j(2);

   77         m_LeftChopstickProvider->link_target(&j);

   78         m_RightChopstickProvider->link_target(&j);

   79 

   80         //젓가락 한쌍을 집습니다.

   81         return Concurrency::receive (j);

   82     } 


젓가락을 내려놓은 것은 간단합니다. 비동기 메시지 전송 함수인 Concurrency::asend()를 사용하여 젓가락이 이용가능함을 알리면 끝입니다.

   83     void PutDownChopsticks(std::vector<Chopstick*>& v)

   84     {

   85         Concurrency::asend(m_LeftChopstickProvider,v[0]);

   86         Concurrency::asend(m_RightChopstickProvider,v[1]);

   87     }


마지막으로 철학자들과 젓가락, 젓가락제공자를 가지고 이들 모두를 셋업하는 역할을 하는 Table 클래스입니다. 주석을 참고하시면 쉽게 이해하실 수 있을 겁니다.

  100 template<class PhilosopherList>

  101 class Table

  102 {

  103     PhilosopherList & m_Philosophers;

  104     std::vector<ChopstickProvider*> m_ChopstickProviders;

  105     std::vector<Chopstick*> m_Chopsticks;

  106 

  107     //이 생성자는 Table 클래서에서 유일한 public 메소드로 vector 변수들을 초기화하고 각 철학자에게 젓가락제공자를 할당합니다:

  108 public:

  109     Table(PhilosopherList& philosophers): m_Philosophers(philosophers)

  110     {

  111         //젓가락 및 젓가락제공자 vector를 채웁니다

  112         for(size_t i = 0; i < m_Philosophers.size();++i)

  113         {

  114             m_ChopstickProviders.push_back(new ChopstickProvider());

  115             m_Chopsticks.push_back(new Chopstick("chopstick"));

  116             //젓가락제공자에 젓가락을 놓습니다

  117             send(m_ChopstickProviders[i],m_Chopsticks[i]);

  118         }

  119         //철학자들을 식탁 자리에 앉힙니다

  120         for(size_t leftIndex = 0; leftIndex < m_Philosophers.size();++leftIndex)

  121         {

  122             //rightIndex 계산

  123             size_t rightIndex = (leftIndex+1)% m_Philosophers.size();

  124 

  125             //왼쪽,오른쪽 제공자를 해당 철학자에 부여합니다

  126             Concurrency::asend(& m_Philosophers[leftIndex].LeftChopstickProviderBuffer,

  127                 m_ChopstickProviders[leftIndex]);

  128             Concurrency::asend(& m_Philosophers[leftIndex].RightChopstickProviderBuffer,

  129                 m_ChopstickProviders[rightIndex]);

  130         }

  131     }

  132     ~Table(){

  133         m_ChopstickProviders.clear();

  134         m_Chopsticks.clear();

  135     }

  136 

  137 };


드디어 대망의 main() 함수입니다. 상태표시를 위한 call 블록과 C++0x 람다의 사용 이외에는, 전술할 클래스들을 사용하고 있을 뿐입니다.

  206 int main()

  207 {

  208     //tr1 array를 사용해 철학자들을 생성합니다

  209     std::tr1::array<Philosopher,5> philosophers = {"Socrates", "Descartes", "Nietzche", "Sartre", "Amdahl"};

  210     Table<std::tr1::array<Philosopher,5>> Table(philosophers);

  211     //상태표시에 이용할 call 블록들의 목록을 생성합니다

  212     std::vector<Concurrency::call<PhilosopherState>*> displays;

  213     //철학자 에이전트를 구동하고 상태표시 항목을 생성합니다

  214     std::for_each(philosophers.begin(),philosophers.end(),[&displays](Philosopher& cur)

  215     {

  216         //상태표시용 call 블록을 하나 만듭니다

  217         Concurrency::call<PhilosopherState>* consoleDisplayBlock = new Concurrency::call<PhilosopherState>([&](PhilosopherState in){

  218             //cout은 각 출력 사이의 스레드안정성을 보장하지 않습니다

  219             if(in == Eating)

  220                 std::cout << cur.m_Name << " is eating\n";

  221             else

  222                 std::cout << cur.m_Name << " is  thinking\n";

  223         });

  224         //상태표시 블록을 연결하고 벡터에 저장해둡니다

  225         cur.CurrentState.link_target(consoleDisplayBlock);

  226         displays.push_back(consoleDisplayBlock);

  227         //그리고 에이전트를 구동합니다

  228         cur.start();

  229     });

  230     //모두 완료되기를 대기

  231     std::for_each(philosophers.begin(),philosophers.end(),[](Philosopher& cur)

  232     {

  233         cur.wait(&cur);

  234     });

  235 

  236     displays.clear();

  237 };


이상을 실행하면 다음과 유사한 결과를 확인하실 수 있습니다.


주석에도 나와있듯이 스레드에 안전하지 않은 cout 출력으로 가끔 상태 메시지가 섞여였음을 확인할 수 있습니다. 그것 이외에는 철학자들이 사이좋게 식사를 하고 있음을 알 수 있습니다.

이렇듯 AAL을 사용하면 저수준의 스레드 함수나 동기화 개체들을 직접 다루지 않고도 쉽게 병렬 수행 작업을 작성할 수 있습니다. 병렬화에 고민하지 않고, 해당 응용프로그램의 도메인 문제에만 집중할 수 있는 것이죠.


이상입니다. 이제 새로운 로고와 함께 VS2010의 베타2도 나왔으니, 새로운 주제로 다시 찾아뵙지요. ^^
신고
이 글은 MSDN 글, "Solving The Dining Philosophers Problem With Asynchronous Agents"를 참고하여 작성되었습니다.

오늘은 AAL(Asynchronous Agents Library)의 액터기반프로그래밍을 사용하여, 동기화 개체들로는 해법이 상당히 골치아프기로 유명한 "철학자들의 식사(Dining Philosophers) 문제"를 풀어보겠습니다. 내용이 길어질듯 하여 3회의 연재글로 구성하려 합니다.

먼저 간단히 철학자들의 식사 문제를 소개하면,


간단히 위 그림과 같은 상황입니다. 철학자 다섯명이 식사를 하는데 젓가락(그림에는 포크지만 상관없습니다;)이 보시는바와 같이 역시 다섯개뿐입니다. 그들은 철학자답게 생각하다가 한입 먹다가를 반복합니다. 한입 먹으려면 젓가락 한쌍이 필요해서 옆사람이 사이에 놓인 젓가락을 이미 선점해 먹고 있다면 기다려야 하는 것이죠. 공유 상태를 고려하지 않고 구현하면 데드락 등으로 철학자가 굶는(starvation) 상황이 발생할 수 있습니다. 이 문제는 저명한 컴퓨터과학자 다익스트라가 처음 제시하였습니다. 모니터 등의 동기화 개체를 사용하여 해결하는 방법이 기존에 많이 설명되어 있습니다만... 솔직히 이해하기가 쉽지 않고 구현도 어렵습니다.

이때 AAL이 제공하는 액터모형을 이용하면 그러한 난해함이나 복잡함 없이 이 문제를 해결할 수 있습니다. 액터모형은 독립적으로 동작하며 서로간에는 오로지 메시지만으로 소통하는(즉, 공유 상태를 가지지 않는) 액터들로 시스템을 모델링하는 방법이라 하겠습니다.

본 예제에서는 철학자를 액터(AAL 용어로는 에이전트)로 보고 메시지 전달을 위해 AAL에서 제공하는 몇몇 메시지 블록(message block)들을 사용하여 철학자들의 식사 문제를 해결합니다.

다음과 같은 다섯 클래스들을 작성하게 됩니다.

  • Chopstick 클래스
  • 식탁 위의 젓가락을 실제 소유하며 요청에 따라 철학자에게 제공하는 역할을 하는 ChopstickProvider 
  • 생각하고 먹는 에이전트 역할의 Philosopher 클래스. 이 클래스는 한쌍의 ChopstickProvider와만 소통합니다.
  • 생각하고 먹는 상태를 나타내는 PhilosopherState 열거형
  • 젓가락들과 철학자들이 배치될 Table 클래스

이 과정에서 다음과 같은 AAL의 클래스 및 함수들을 이용합니다.
  • Concurrency::agent - 에이전트 기반 클래스
  • 이하는 메시지 블록에 속하는 여러 타입들
    • Concurrency::unbounded_buffer
    • Concurrency::overwrite_buffer
    • Concurrency::join
    • Concurrency::call
  • 이상의 메시지 블록들에 메시지를 주고 받는데 사용하는 함수들
    • Concurrency::send
    • Concurrency::asend - 위의 비동기 버전으로, 받음 여부를 확인하지 않고 바로 리턴
    • Concurrency::receive

본격적인 구현 과정은 다음 회에 계속됩니다~ ^^
신고