3. IPC
IPC(Inter Process Communication)는 프로세스간 상호 통신을 말한다.
구현방법에서 크게 두가지 방법으로 나눌수 있는데 하나는 공유 메모리이고 두번째는 메시지 전달 방식이다.

공유메모리 방식은 송신측과 수신측이 일정한 메모리 공간을 공유하고 송신측이 이 공간에 데이터를 쓰면 수신측이 읽어 가는 형태이다.
공유 메모리 방식의 동기화를 위해서는 수신측은 송신측이 데이터를 기록하였는지 알아야 하고 송신측은 수신측이 데이터를 읽어갔는지 여부를 알아야 하며 이를 활용하는 프로그래머는 적절한 동기화 절차를 거쳐야 한다.
데이터를 바로 읽어가기 때문에 오버헤드가 크지 않기 때문에 큰 데이터를 전달할 때 유용하지만 동기화문제를 신경써야한다.

메시지 전달 방식은 운영체제가 커널 내부에서 메시지를 기록할 수 있는 공간을 두고 적절한 시스템 콜을 통해 메시지의 송수신을 운영체제에게 요구할 수 있도록 하는 방식이다. 즉 커널이 메시지를 받아 전달시켜주는 방식이다. 대표적인 예가 메일박스이다. 이 방식의 동기화의 경우 메시지를 위한 공간이 꽉 찼을 경우 송신측이 대기하여야 하고 반대로 비어있을 경우 수신측이 대기해야한다. 메시지를 커널로 복사하고 이 메시지를 다시 수신측에게 복사해야하므로 오버헤드가 큰 대신 동기화에 대한 문제를 크게 신경쓰지 않아도 되어서 메시지 양이 작은 경우 사용하면 유용하다.

picoKernel에는 프로세스간 통신을 위해 메일박스, 랑데부, 시그널이 구현되어 있다.

3.1 메일박스
메일박스는 메시지 전달방식으로 내부에 버퍼를 두고 송신측이 이 버퍼에 데이터를 전달하고 수신측이 이 버퍼에서 데이터를 받아가는 형식으로 되어 있다.
메일박스의 엔트리를 보면 해당 메일박스가 비어있는지 차있는지에 대한 세마포어와 순환 버퍼의 시작과 끝을 가르키는 인덱스, 메시지 버퍼(순환 버퍼)로 구성되어 있다. 또한 메일박스를 사용하기 위한 뮤택스와 사용하고 있는 메일박스의 엔트리 개수를 나타내는 변수가 있다.

메일박스의 생성은 mboxCreate이고 초기화시 메일박스 테이블에 대한 초기화, 해당 메일박스가 비어있는지 꽉차있는지를 확인하고 기다리는 세마포어의 초기화 후 메일박스의 id를 리턴한다.

mboxSend는 메시지를 전송하는 함수이다. 매개변수로 메일박스의 id와 메시지에 대한 포인터를 받는다.
메시지를 전달할 때 세마포어를 통해 메시지 버퍼가 비어있기를 대기한다. 메시지가 비어있게 되면 메시지를 버퍼 공간에 쓰기 위해 뮤택스로 락을 걸어두고 메시지를 저장후 버퍼공간의 헤드와 테일 인덱스를 업데이트 한다. 락을 해제한 후 수신측이 읽어도 된다고 세마포어를 통해 시그널을 보낸다.

mboxRecive는 메시지를 수신하는 함수이며 마찬가지로 매개변수를 id와 메시지를 받을 포인터를 받는다.
메시지가 저장되었다는 세마포어의 시그널을 기다렸다가 시그널이 오면 뮤택스로 락을 걸고 데이터를 읽어온다. 헤드 인덱스를 초기화 한 다음 뮤택스 락을 해제한 후 버퍼가 비었다는 세마포어의 시그널을 보내 다음 메시지가 버퍼에 저장될 수 있도록 한다.

3.2 랑데부
랑데부는 극단적으로 버퍼가 0인 통신이다. 말 자체로 송신측과 수신측이 만나서 데이터를 전달 받는 형식이다. 메일박스가 내부의 버퍼를 두고 통신을 하는데 반해 랑데부는 버퍼 없이 송신측이 수신측으로 바로 데이터를 전달한다.

메일박스와 비슷하게 rendCreate, rendSend, rendRecive로 구성되어 있다. 랑데부의 엔트리는 송신측과 수신측의 thread id, 대기와 완료를 알리는 세마포어, 메시지로 구성되어 있다.

랑데부를 생성하게 되면(rendCreate), 송신측과 수신측의 thread 번호를 등록하고 세마포어를 초기화한 후 랑데부 아이디를 리턴한다.

rendSend는 랑데부 id와 메시지를 매개변수로 받고 수신측이 대기상태가 될때까지 세마포어를 통해 기다린다. 수신측 대기상태의 세마포어 시그널을 보내면 메시지를 복사하고 완료했다는 세마포어 시그널을 보낸다.

rendRecive 역시 id와 메시지를 저장할 공간을 매개변수로 받아 포인터를 연결시킨다음 대기상태라는 세마포어 시그널을 송신측에 보내 데이터를 전달 받은 다음 완료했다는 세마포어 시그널을 보낸다.

3.3 시그널
시그널이 구현되기 위해서는 thread control block에 시그널 번호별로 해당 핸들러 함수를 등록해야하고 초기화시 0으로 세팅한다.

signalSet함수는 시그널 번호에 따른 핸들러 함수를 등록시키는 함수이고 signalSend는 시그널을 보내는 함수이다. signalSend함수를 호출해서 해당 핸들러가 성공적으로 호출되었으면 1로 설정되어있던 비트를 다시 초기화 시켜준다.

해당 스레드가 running상태가 아니라면 running가 된 후 즉 문맥교환이 이루어진 후에 시그널이 왔는지를 확인해야한다.

2. 동기화
멀티태스킹으로 일을 처리하게 되면 둘 이상의 프로세스 혹은 스레드가 동시에 한 데이터에 접근하는 경우가 발생하는데 이럴 때 동기화 문제가 발생한다.
A와 B라는 두개의 스레드가 있고 alpha라는 공유변수가 있다고 가정할 때
두 스레드 A, B가 동시에 alpha라는 변수에 접근하여 데이터를 변경한다면 문제가 발생할 수 있다.
또한 두 스레드 A, B에서 변수 alpha에 접근하는 부분을 크리티컬 섹션 혹은 크리티컬 리젼이라고 부르며
이 섹션들 간에는 상호 배재 즉 상대방이 실행하고 있으면 다른 녀석들은 이에 접근할 수 없도록 조치해야한다.
picoKernel 에서는 이러한 상황을 해결하기 위한 동기화 방법에는 아래와 같은 방법이 있다.
뮤텍스(mutex)
세마포어(semaphore)
조건변수(condition variable)

2.1 뮤텍스
뮤텍스는 일종의 변수이고 해당 크리티컬 섹션에 대해 lock상태인지 아닌지에 대한 정보를 가지고 있다.
크리티컬 섹션에 진입할 때 해당 섹션이 lock상태이면 unlock이 될 때까지 기다리게 되는데
unlock이 될 때까지 계속 체크하는 비지 웨이팅방식이 아니라 해당 스레드 혹은 프로세스가 running상태에서
waiting상태로 넘어가게 된다. 다시 크리티컬 섹션에 진입할 때 unlock상태이면 자신이 진입했다는 표시로
lock을 걸어둔다. lock을 걸어둔 스레드 혹은 프로세스가 unlock을 할 때는 프로세스의 대기 목록에서 lock이 풀리기를 기다리는 프로세스들 중 하나를 깨워준다.

picoKernel에서는 뮤텍스로 사용할 변수를 선언하고 mutexCreate함수를 호출한다.
내부적으로 전체 뮤텍스의 엔트리를 가지고 관리하며 아직 할당하지 않은 뮤텍스의 id를 반환한다.
뮤텍스 엔트리의 구조체는 unlock을 기다리는 thread의 리스트를 가리키기 위한 thread엔트리 포인터(mHead, mTail)와 현재 lock을 걸어둔 thread의 엔트리 포인터(mOwner)를 가지고 있다.

mutexLock함수로 크리티컬 섹션에 진입할 때 내부적으로 mOwner가 null이 아니면 lock상태이고
null이면 unlock상태이다. null이 아니어서 lock상태라면 자신(thread)의 상태를 waiting상태로 바꾸고
해당 뮤텍스의 대기 리스트에 저장후 대기하고 있던 리스트안에 있는 thread를 실행하게 된다.

mutexUnlock함수는 대기중인 스레드 중에서 하나만 ready상태로 전환한다.
해당 뮤택스의 mOwner를 null로 바꾸고 내부에 해당 뮤텍스에 등록되어 있는 대기 리스트를 업데이트 한다.

2.2 세마포어
세마포어는 뮤택스보다는 조금 확장된 개념으로 볼 수 있는데 뮤택스가 해당 크리티컬 섹션에 진입할 수 있는 스레드나 프로세스의 개수가 하나라면 세마포어는 하나 이상으로 설정할 수 있다.
개념은 뮤택스와 비슷하다.
picoKernel에서는 세마포어 엔트리로 세마포어를 관리하는데 하나의 엔트리는 뮤택스와 마찬가지로 대기하고 있는 thread 엔트리 포인터(sHead, sTail)가 있고 세마포어 값으로 구성되어 있다.

세마포어를 사용하기 위해 초기에 semCreate 함수를 호출하는데 매개변수로 세마포어의 값을 입력받는다.
비어있는 세마포어 id를 리턴한다.

semWait함수는 해당 세마포어가 가진 값이 0보다 크면 해당 크리티컬 섹션에 진입이 가능하며 초기에 세마포어를 생성했던 값을 -1하게 된다. 여러 thread들이 semWait를 호출하게 되여 세마포어의 값이 0이 되면 더 이상 다른 스레드의 진입이 불가능하고 이 때 해당 스레드가 waiting상태로 넘어가게 된다.

semSignal함수는 반대로 크리티컬 섹션에서 나올 때 세마포어의 값을 1 증가시키며 대기하고 있던 스레드중에 하나를 깨우게 된다. 뮤택스와 마찬가지로 대기리스트를 업데이트한다.

2.3 조건변수
조건변수로 선언후 wait, signal로 사용하는데 해당 변수 예를 들어 a라는 조건 변수가 있을 때
a.wait()을 호출하면 다른 프로세스 혹은 다른 thread에서 a.signal()을 호출할 때까지 무조건 대기한다.

picoKernel에서는 condCreate함수로 초기화를 하고 조건변수의 id를 리턴한다.
조건변수의 엔트리는 해당 조건을 기다리고 있는 스레드의 개수와 동기화를 위한 세마포어로 구성되어 있다.

condWait함수는 id와 모니터로 사용하는 뮤텍스를 인자로 넘겨받아 조건변수 엔트리의 대기 스레드 개수를 +1 해주고 다른 스레드에서 Signal을 보낼때까지 기다릴 수 있도록 semWait하게 된다. 이 때 뮤택스로 조건변수와 semWait를 보호한다.

condSignal함수는 해당 조건변수의 대기 스레드 카운터가 0보다 크면 즉 비어있지 않으면 카운터값을 -1시키고 해당 세마포어를 semSignal하게 된다. 역시 이 부분도 뮤택스로 보호해주어야 한다.

1.3 picoKernel의 thread 생성
picoKernel에서 함수는 thread로 등록할 수 있다.
thread의 생성은 threadCreate()함수로 처리한다.
thread의 관리는 thread entry structure로 처리한다.

아래는 thread하나의 entry structure이다.
----------------------------------------------------------------------
typedef struct threadEnt {
    struct threadEnt *tNext;        // point to next thread entry

    enum threadState tState;        // thread state
    int tPrio;              // thread priority

    int (*tStart)(int);         // start function address
    int tArg;               // argument of tStart()

    char *tStack;           // stack base address
    int tStackSize;         // stack size in bytes

    unsigned long tContext;     // address of context area

#ifdef KERNEL2 // .........
    // fields for signal operation
    void (*tSigTab[NUM_SIGNAL])(int);   // handler functions
    unsigned short tSignals;        // signal bits
#endif // KERNEL2 .........

#ifdef PROCESS
    struct procEnt *tProc;      // the process of this thread
    struct threadEnt *tSibling;     // threads of the same process
#endif

} threadEntT;
----------------------------------------------------------------------

threadCreate()는 3개의 매개변수를 받는데
첫번째 매개변수가 우선순위, 두번째 매개변수가 함수의 주소, 세번째 매개변수가
함수의 매개변수이다.
threadCreate()가 실행되면 threadEntT 를 하나 만들고 넘어온 thread의 정보를
threadEntT에 저장하고 context정보를 할당한다. context정보가 있어야
다른 thread가 동작하다가 context switch가 일어나도 상태를 유지할 수 있다.
tContext에 이 정보가 저장된다.

context정보는 스택에 저장되는데 처음 threadInit()함수에서 영역을 할당하고
threadCread함수에서 해당 context정보를 스택에 저장한다. 그리고 context의 위치정보를
tContext가 가지고 있다.
context정보를 담는 stack은 여러 thread의 context를 담고 있는 stack이다.
하나의 블록이 하나의 thread의 문맥정보를 가지고 있으며
각 thread는 이 위치를 알아야 문맥교환이 가능하다.

일련의 과정이 끝나면 thread가 스케줄러에 등록이 되면서
등록되어 있는 thread목록중에서 가장 우선순위가 높은 thread가 실행된다.
다른 thread가 동작하고 있다가도 새로운 thread가 등록되었을 때
새로 등록한 thread의 우선순위가 높다면 새로운 thread가 실행되게 된다.
(schedRunHighest())

threadExit()는 현재 동작하고 있는 thread를 종료하겠다는 의미이다.
현재 동작하고 있는 thread의 제어권을 다른 thread로 넘기고
thread의 리스트에서 자신의 목록을 제거하고
schedRunHighest()로 우선순위가 가장 높은 thread를 실행한다.

threadYield()는 동작하던 일을 멈추고 다른 thread에게 제어권을 양보하는 것이다.
제어권을 다른 thread에게 넘기고 자신의 정보를 스케줄러의 ready list에 등록한다.

대략 정리하자면
thread를 생성하려면 thread의 정보를 가진 구조체에 thread의 내용을 저장해야한다.
이 내용에는 자신의 함수 주소, 매개변수, 우선순위, context의 위치, thread의 상태
를 저장하고 스케줄러에 자신을 등록한다.

1.4 picoKernel scheduling
picoKernel에서는 thread의 리스트를 Running, Ready, Free 3개로 나타낸다.
3개의 포인터 모두 thread의 리스트를 가리키고 있다.
scheduling의 시작은 thread의 생성부터 시작된다.
thread를 생성하게 되면 상태를 ready상태로 두고 스케줄러의 Ready리스트에 등록하고
우선순위가 가장 높은 thread를 실행하게 한다.

schedInsertReady()함수가 thread를 생성할 때 ready 리스트에 등록하는 함수인데
링크드리스트로 되어 있는 ready 리스트에 우선순위 순서대로 등록된다.

schedRunHighest()함수는 현재 우선순위가 가장 높은 thread로 문맥교환하게 된다.
만약 현재 동작하고 있는 thread와 readlist에 있는 첫번째 thread의 우선순위가
같다면 문맥교환을 하지 않는다. 문맥교환을 하게 되면
현재 동작하고 있는 thread는 readlist로 이동하게 된다.

OS를 공부하는데 있어서 OS가 동작하는 이론적인 문제도 중요하지만
실제로 OS가 어떻게 동작하는지 알아보는 일도 중요하다.
초보자 입장에서 현재 동작하고 있는 최신 리눅스 커널 소스를 보는 일은
이제 막 걸음마를 시작한 애가 장대 높이 뛰기 선수들이 쓰는 장대를 만지작
거리는 일과 다르지 않으리라 생각한다.
그래서 시작은 picoKernel과 linux 커널 0.1 버전을 분석해보는 일부터 시작하려 한다.

1. picoKernel
분석해보려는 picoKernel은 우리 교수님께서 만든 교육용 커널이다.
실제 소스의 길이도 2000정도 밖에 안되는 교수님 말을 빌리면 만만한 커널이다.
가벼워도 OS의 핵심적인 기능은 대부분 갖추고 있다.
물론 이것을 실제 운영체제로 사용하려면 각종 유틸들이나 파일시스템등 여러가지가
필요하지만 picoKernel 은 실제 OS 내부에서 사용하는 멀티태스킹, 스케줄링,
동기화에 필요한 뮤텍스, 세마포어, 공유메모리등이 구현되어 있다.
예전에 프로젝트 때문에 임베디드용 OS를 몇개 본적이 있었는데 그 구조가
picoKernel과 크게 다르지 않았다. 세부적인 내용은 조금씩 차이는 있지만
대략적인 구동방식이나 구조는 대동소이했다.
MicroC/OS나 ETRI에서 얼마전에 공개한 nanoQplus, 콜로라도 대학의 MANTIS 등과
같은 소형 임베디드 OS들은 모두 picoKernel과 같이 멀티태스킹과 동기화와 IPC를 위한
기능을 지원한다.

1.1 picoKernel 특징
picoKernel은 멀티태스킹이 가능한 OS이다. picoKernel자체가 하나의 프로세스이므로
프로세스내에서의 멀티태스킹은 thread방식이다.
picoKernel은 비선점형 스케줄링에 해당하는데 비선점형 자발적인 종료나 wait, 양보의 경우에만
다른 작업으로 제어권을 넘기게 되고 다른 인터럽트나 새로운 작업의 등록으로 인해
현재 작업중인 제어권이 바뀌지 않는 형태를 비선점형 스케줄링라고 한다.
picoKernel는 인터럽트의 처리를 제외하면 선점형 스케줄링으로 볼 수 도 있다.
picoKernel이 선점형 스케쥴링이 되려면 인터럽트에 대한 처리를 따로 처리해야하며
이때 발생하는 크리티컬 섹션 문제가 해결되어야만 선점형 스케쥴링이 될 수 있다.

여담..
프로젝트 할 때 AVR에 타이머 인터럽트를 통해서 선점형 스케쥴러 비스므리하게
강제적으로 시간이 지나면 스케줄링이 일어나게 했던 적이 있었는데.
OS와 통신모듈을 통합하고 나니까 통신모듈이 동작을 안하는 것이다.
통신모듈에 문제가 있는 줄 알고 몇주를 헤맸는데 결국 문제는 타이머 인터럽트로 인한
강제적인 스케줄링으로 인해 통신중에 문맥이 바뀌어버리는 것이다.
당연히 데이터가 날라가는 중에 스케줄링이 일어나면 데이터가 전송되다 만다..
타이머 인터럽트는 생각도 안하던 문제여서 통신 모듈상에 인터럽트 방지도 안해놨고
문맥교환시 데이터의 동기화역시 생각도 안하던 문제여서 결국 타이머 인터럽트에
걸려있던 강제 스케줄링을 삭제했던 기억이 있다.

1.2 picoKernel의 동작
picoKernel은 실제 OS라기보다는 교육목적으로 만들어졌기 때문에 리눅스나
Cygwin같은 환경에서 하나의 프로세스로 동작한다. 커널 하나가 하나의 프로세스로 동작하고
그 안에서 여러 thread를 생성해서 동작한다.

picoKernel은 기본적으로 nullMain과 userMain 2개의 thread로 동작한다.
nullMain은 말 그대로 비어있는 루틴이고 userMain은 사용자가 일을 처리할 때
사용하는 루틴이다. 두개의 thread가 등록이 되고 우선순위에 따라 동작한다.
thread생성시 userMain의 우선순위가 높기 때문에 userMain함수안에서
다른 thread를 생성하지 않는다면 userMain을 먼저 처리하고 끝나면
nullMain을 실행하고 종료한다.
nullMain을 보면 thread가 실행되면 바로 threadYield로 다른 thread로 제어권을 넘긴다.
userMain에서 thread를 생성하면 그 우선순위에 따라 thread를 실행하고
종료하게 된다.