13장 동기화

임베디드 OS 개발 프로젝트를 읽고 작성하였습니다.

시작하기 전에

 

나빌로스

비선점형 스케줄링

태스크가 명시적으로 Kernel_yield()를 호출해야만 다른 태스크로 컨텍스트가 넘어가므로 싱글코어 환경에서는 동기화 문제가 발생x

=> 동기화를 다루지 않아도 됨

 

동기화 (synchronization)

: 운영체제에서 어떤 작업을 아토믹 오퍼레이션 (atomic operation)으로 만들어 준다는 의미

 

아토믹 오퍼레이션 (atomic operation)

: 억지로 번역을 하면 '단일 작업' 혹은 '원자 작업' 정도가 되는데, 번역이 실제 의미를 제대로 전달하지 못함

=> 아토믹 오퍼레이션 혹은 아토믹 동작이라는 용어 사용

 

어떤 작업이 아토믹하다

= 해당 작업이 끝날 때까지 컨텍스트 스위칭이 발생하지 않는다는 말

 

멀티코어 환경에서 아토믹 동작이 진행 중일 때, 컨텍스트 스위칭뿐만 아니라 다른 코어가 해당 동작에 끼어들지 못하게 하는 것

=> 해당 작업을 원자처럼 더 이상 쪼갤 수 없다는 의미를 살리기 위해 아토믹이라는 이름이 붙은 것

 

어떤 작업이 아토믹하게 구현되어야만 한다면

= 해당 작업을 크리티컬 섹션 (critical section)이라고 부름

 

동기화란

어떤 작업이 크리티컬 섹션이라고 판단되었을 경우, 해당 크리티컬 섹션을 아토믹 오퍼레이션으로 만들어 주는 것

- 세마포어 (semaphore)

- 뮤텍스 (mutex)

- 스핀락 (spin lock)

---

13장 동기화

13.1 세마포어

- 동기화 알고리즘 중에서 가장 유명한 알고리즘 중 하나

- 가장 많이 쓰이는 알고리즘

- 개발된 지도 오래된 알고리즘

- 간단하고 직관적이면서 쉬움

 

세마포어의 개념

의사 코드 (pseudo code)

Test(S)
{
	while S <= 0 ; // 대기
	S--;
}

Release(S)
{
	S++;
}

세마포어
Test() 함수	Release() 함수
크리티컬 섹션에 진입 가능한지 확인해 보는 함수 다른 의미로는 세마포어를 잠글(lock) 수 있는지 확인한다는 의미도 가짐	크리티컬 섹션을 나갈 때 호출해서 세마포어를 놓아주는(release) 혹은 세마포어의 잠금을 푸는(unlock) 역할을 함

 

동기화를 구현하는 두 가지 중요한 개념

- 잠금

- 잠금의 해제

 

크리티컬 섹션에 들어갈 때 잠그고 크리티컬 섹션을 나올 때 잠금을 푸는 것

잠겨 있는 도중에는 컨텍스트 스위칭도 발생하지 않고 다른 코어가 끼어들지 못함

 

kernel/synch.c

#include "stdint.h"
#include "stdbool.h"

#include "synch.h"

#define DEF_SEM_MAX 8 //나빌로스는 1부터 8까지를 세마포어의 값으로 지정 가능

static int32_t sSemMax;
static int32_t sSem;

void Kernel_sem_init(int32_t max) //세마포어 초기화 함수
{
    sSemMax = (max <= 0) ? DEF_SEM_MAX : max;
    sSemMax = (max >= DEF_SEM_MAX) ? DEF_SEM_MAX : max;

    sSem = sSemMax;
}

bool Kernel_sem_test(void)
{
    if (sSem <= 0) //세마포어를 잠글 수 없을 때
    {
        return false; //false를 리턴
    }

    sSem--;

    return true;
}

void Kernel_sem_release(void) //세마포어 변수가 증가하는 함수
{
    sSem++;
    
    if (sSem >= sSemMax) //정해놓은 최댓값을 넘지 않도록 조정
    {
        sSem = sSemMax;
    }
}

코드 13.1 세마포어 구현 synch.c

 

kernel/Kernel.c

세마포어는 커널 API를 통해서 사용함

void Kernel_lock_sem(void)
{
    while(false == Kernel_sem_test())
    {
        Kernel_yield(); //while 무한 루프 대신 사용
    }
}

void Kernel_unlock_sem(void)
{
    Kernel_sem_release();
}

코드 13.2 세마포어용 커널 API Kernel.c

Kernel_yield()를 사용한 이유

>크리티컬 섹션의 잠금을 소유하고 있는 다른 태스크로 컨텍스트가 넘어가서 세마포어의 잠금을 풀어줄 수 있기 때문

멀티태스킹에서 대기(waiting)를 어떻게 구현하는지 보여주는 코드

 

hal/rvpb/Uart.c

static void interrupt_handler(void)
{
    uint8_t ch = Hal_uart_get_char();

    if (ch != 'X')
    {
        Hal_uart_put_char(ch);
        Kernel_send_msg(KernelMsgQ_Task0, &ch, 1);
        Kernel_send_events(KernelEventFlag_UartIn);
    }
    else
    {
        Kernel_send_events(KernelEventFlag_CmdOut);
    }
}

코드 13.3 X 키를 누를 때 CmdOut 이벤트 발생 Uart.c

키보드에서 대문자 X를 입력했을 때 다른 동작을 하도록 코드를 수정함

=> Task0에서 이벤트를 받음

 

boot/Main.c

void User_task0(void)
{
    uint32_t local = 0;
    
    debug_printf("User Task #0 SP=0x%x\n", &local);
    
    uint8_t  cmdBuf[16];
    uint32_t cmdBufIdx = 0;
    uint8_t  uartch = 0;

    while(true)
    {
        KernelEventFlag_t handle_event = Kernel_wait_events(KernelEventFlag_UartIn|KernelEventFlag_CmdOut);
        switch(handle_event)
        {
        case KernelEventFlag_UartIn:
            Kernel_recv_msg(KernelMsgQ_Task0, &uartch, 1);
            if (uartch == '\r')
            {
                cmdBuf[cmdBufIdx] = '\0';
                
		while(true)
		{
		    Kernel_send_events(KernelEventFlag_CmdIn);
		    if (false == Kernel_send_msg(KernelMsgQ_Task1, &cmdBufIdx, 1))
		    {
			Kernel_yield();
		    }
		    else if (false == Kernel_send_msg(KernelMsgQ_Task1, cmdBuf, cmdBufIdx))
		    {
			uint8_t rollback;
			Kernel_recv_msg(KernelMsgQ_Task1, &rollback, 1);
			Kernel_yield();
		    }
		    else
		    {
			break;
		    }
		}
                
                cmdBufIdx = 0;
            }
            else
            {
                cmdBuf[cmdBufIdx] = uartch;
                cmdBufIdx++;
                cmdBufIdx %= 16;
            }
            break;
        case KernelEventFlag_CmdOut: //CmdOut 이벤트를 받음
            Test_critical_section(5, 0); //크리티컬 섹션에 5를 보냄
            break;
        }
        Kernel_yield();
    }
}

static uint32_t shared_value; //공유 자원 역할을 하는 로컬 전역 변수
static void Test_critical_section(uint32_t p, uint32_t taskId) //(공유 자원의 값을 바꿀 입력 값, 함수를 호출한 태스크의 번호)
{
    debug_printf("User Task #%u Send=%u\n", taskId, p); //태스크의 번호와 어떤 입력을 넘겼는지 출력
    shared_value = p; //공유 변수의 값을 바꿈
    Kernel_yield(); //Kernel_yield() 함수를 호출해서 억지로 스케줄링 (공유 자원 문제를 만들기 위해 삽입한 억지스러운 코드)
    delay(1000); //테스트를 쉽게 하기 위한 딜레이
    debug_printf("User Task #%u Shared Value=%u\n", taskId, shared_value); //태스크 번호와 공유 변수의 값을 출력
}

코드 13.4 억지로 만든 동기화 테스트 코드 Main.c

 

결과

X 키를 누를 때마다 Task0이 숫자 5를 shared_value 변수에 전달했다는 것을 디버그 메시지로 출력함

User Task #0 Send=5            -> Task0이 숫자 5를 전달
User Task #0 Shared Value=5    -> Task0에서 출력한 공유 변수의 값은 5임

 

Test_critical_section() 함수는 반드시 입력으로 전달한 값과 공유 변수의 값이 같아야만 제 역할을 했다고 볼 수 있음

 

 

만약 같은 Test_critical_section() 함수를 Task2에서 동시에 호출한다면 어떤 일이 생길까?

 

boot/Main.c

void User_task2(void)
{
    uint32_t local = 0;

    debug_printf("User Task #2 SP=0x%x\n", &local);

    while(true)
    {
        Test_critical_section(3, 2); //크리티컬 섹션에 3을 전달
        Kernel_yield();
    }
}

코드 13.5 Task2를 수정 Main.c

 

결과

Task2의 출력이 계속 나옴

X를 누르면 Task2가 Task0이 shared_value에 5를 넣는 동작을 방해하는 형태가 됨

그래서 shared_value의 값을 출력하는 시점에서 다음과 같이 Task0에서 호출한 디버그 출력이 shared_value의 값을 3으로 출력하는 결과가 보임

User Task #0 Shared Value=3

Test_critical_section() 함수의 중간에 억지로 호출한 Kernel_yield() 함수 때문

 

=> 여러 코어가 공유하는 자원에 대한 값을 바꾸고 사용하는 코드라면 개발자가 판단해서 이것을 크리티컬 섹션으로 식별하고 반드시 동기화 처리를 해야만 함

=> 바이너리 세마포어를 만들어서 크리티컬 섹션에 동기화 처리하기

 

boot/Main.c

바이너리 세마포어 만들기

static void Kernel_init(void)
{
    uint32_t taskId;

    Kernel_task_init();
    Kernel_event_flag_init();
    Kernel_msgQ_init();
    Kernel_sem_init(1); //세마포어의 잠금 개수를 1로 한다는 것 (=바이너리 세마포어)

    taskId = Kernel_task_create(User_task0);
    if (NOT_ENOUGH_TASK_NUM == taskId)
    {
        putstr("Task0 creation fail\n");
    }

    taskId = Kernel_task_create(User_task1);
    if (NOT_ENOUGH_TASK_NUM == taskId)
    {
        putstr("Task1 creation fail\n");
    }

    taskId = Kernel_task_create(User_task2);
    if (NOT_ENOUGH_TASK_NUM == taskId)
    {
        putstr("Task2 creation fail\n");
    }
    
    Kernel_start();
}

코드 13.6 바이너리 세마포어 초기화

 

Test_critical_section() 함수의 구현 수정

static uint32_t shared_value;
static void Test_critical_section(uint32_t p, uint32_t taskId)
{
	Kernel_lock_sem();
    
    debug_printf("User Task #%u Send=%u\n", taskId, p);
    shared_value = p;
    Kernel_yield();
    delay(1000);
    debug_printf("User Task #%u Shared Value=%u\n", taskId, shared_value);
    
    Kernel_unlock_sem();
}

코드 13.7 세마포어로 크리티컬 섹션 지정

 

크리티컬 섹션으로 식별된 Test_critical_section() 함수의 동작을 아토믹 오퍼레이션으로 만든 것

 

결과

Task2의 결과가 출력되는 동안 키보드의 대문자 X 키를 계속 타이핑해서 Task0의 결과가 섞이도록 함

=> Task0일 때는 shared_value의 값이 항상 5이고 Task2일 때는 shared_value의 값이 항상 3임

다른 태스크가 동작을 방해하지 않음!

13.2 뮤텍스

- 바이너리 세마포어의 일종

 

세마포어는 잠금에 대한 소유 개념이 없으므로 누가 잠근 세마포어이든 간에 누구나 잠금을 풀 수 있음

but 뮤텍스는 소유의 개념이 있음, 뮤텍스는 잠근 태스크만이 뮤택스의 잠금을 풀 수 있음

 

💡 뮤텍스 = 바이너리 세마포어 + 소유의 개념

 

 

kernel/synch.h

뮤텍스 관련 자료 구조와 함수 프로토타입을 선언

#ifndef KERNEL_SYNCH_H_
#define KERNEL_SYNCH_H_

typedef struct KernelMutext_t
{
    uint32_t owner; //뮤텍스의 소유자
    bool     lock; //뮤텍스의 잠김 표시 변수
} KernelMutext_t;

void Kernel_sem_init(int32_t max);
bool Kernel_sem_test(void);
void Kernel_sem_release(void);

void Kernel_mutex_init(void);
bool Kernel_mutex_lock(uint32_t owner);
bool Kernel_mutex_unlock(uint32_t owner);

#endif /* KERNEL_SYNCH_H_ */

코드 13.8 뮤텍스 함수 선언 추가 synch.h

 

kernel/synch.c

뮤텍스 구현

KernelMutext_t sMutex; //뮤텍스 자료 구조를 전역 변수로 선언
...
중략
...
void Kernel_mutex_init(void) // 전역 변수 sMutex를 초기화하는 함수
{
    sMutex.owner = 0;
    sMutex.lock = false;
}

bool Kernel_mutex_lock(uint32_t owner)
{
    if (sMutex.lock) //뮤텍스가 잠겨있다면
    {
        return false; //함수를 끝냄
    }

    sMutex.owner = owner; //소유자 등록
    sMutex.lock = true; //뮤텍스 잠금
    return true;
}

bool Kernel_mutex_unlock(uint32_t owner)
{
    if (owner == sMutex.owner) //소유자 확인
    {
        sMutex.lock = false; //잠금 해제
        return true;
    }
    return false; //소유자가 아니면 요청 무시
}

코드 13.9 뮤텍스 구현 코드 synch.c

 

kernel/Kernel.c

뮤텍스를 커널 API로 제어할 수 있도록 커널 API를 만듬

void Kernel_lock_mutex(void)
{
    while(true)
    {
        uint32_t current_task_id = Kernel_task_get_current_task_id();
        if (false == Kernel_mutex_lock(current_task_id))
        {
            Kernel_yield();
        }
        else
        {
            break;
        }
    }
}

void Kernel_unlock_mutex(void)
{
    uint32_t current_task_id = Kernel_task_get_current_task_id();
    if (false == Kernel_mutex_unlock(current_task_id))
    {
        Kernel_yield();
    }
}

코드 13.10 뮤텍스 커널 API Kernel.c

 

뮤텍스의 커널 API는 뮤텍스 함수가 false를 리턴할 때 Kernel_yield() 함수를 호출하는 것 외에 다른 작업을 해줌

뮤텍스의 소유자를 뮤텍스 함수에 알려주는 작업

 

kernel/task.c

Kernel_task_get_current_task_id()

: 현재 동작 중인 태스크의 태스크 ID를 리턴하는 함수

uint32_t Kernel_task_get_current_task_id(void)
{
    return sCurrent_tcb_index;
}

코드 13.11 현재 동작 중인 태스크 ID를 받는 함수 task.c

 

kernel/event.h

새로운 이벤트 추가

typedef enum KernelEventFlag_t
{
    KernelEventFlag_UartIn      = 0x00000001,
    KernelEventFlag_CmdIn       = 0x00000002,
    KernelEventFlag_CmdOut      = 0x00000004,
    KernelEventFlag_Unlock      = 0x00000008,
    KernelEventFlag_Reserved04  = 0x00000010,
    KernelEventFlag_Reserved05  = 0x00000020,
    KernelEventFlag_Reserved06  = 0x00000040,
    KernelEventFlag_Reserved07  = 0x00000080,
    KernelEventFlag_Reserved08  = 0x00000100,
    KernelEventFlag_Reserved09  = 0x00000200,
    ...
    중략

코드 13.12 Unlock 이벤트 추가 event.h

 

hal/rvpb/Uart.c

UART 인터럽트 핸들러 수정

static void interrupt_handler(void)
{
    uint8_t ch = Hal_uart_get_char();
    
    if (ch == 'U')
    {
        Kernel_send_events(KernelEventFlag_Unlock); //Task1에서 받아서 처리
        return;
    }

    if (ch != 'X')
    {
    	Kernel_send_events(KernelEventFlag_CmdOut);
    	return;
    }
    
    Hal_uart_put_char(ch);
    Kernel_send_msg(KernelMsgQ_Task0, &ch, 1);
    Kernel_send_events(KernelEventFlag_UartIn);
}

코드 13.13 Unlock 이벤트를 보내는 UART 인터럽트 핸들러 Uart.c

 

boot/Main.c

void User_task1(void)
{
    uint32_t local = 0;
    
    debug_printf("User Task #1 SP=0x%x\n", &local);
    
    uint8_t cmdlen = 0;
    uint8_t cmd[16] = {0};

    while(true)
    {
        KernelEventFlag_t handle_event = Kernel_wait_events(KernelEventFlag_CmdIn|KernelEventFlag_Unlock); //비트 연산 사용
        switch(handle_event)
        {
            case KernelEventFlag_CmdIn:
		memclr(cmd, 16);
		Kernel_recv_msg(KernelMsgQ_Task1, &cmdlen, 1);
		Kernel_recv_msg(KernelMsgQ_Task1, cmd, cmdlen);
		debug_printf("\nRecv Cmd: %s\n", cmd);
		break;
            case KernelEventFlag_Unlock: //이벤트 핸들러 작성
		Kernel_unlock_sem(); //세마포어를 해제하는 커널 API 호출
		break;
        }
        Kernel_yield();
    }
}

코드 13.14 Unlock 이벤트를 처리하는 Task1

대문자 U를 입력하면 Task1은 그냥 다짜고짜 세마포어를 해제한다는 것

-> 크리티컬 섹션 함수에도 변화를 줘야 함

 

static uint32_t shared_value;
static void Test_critical_section(uint32_t p, uint32_t taskId)
{
    Kernel_lock_sem();

    debug_printf("User Task #%u Send=%u\n", taskId, p);
    shared_value = p;
    Kernel_yield();
    delay(1000);
    debug_printf("User Task #%u Shared Value=%u\n", taskId, shared_value);

    // Kernel_unlock_sem(); 함수를 호출하는 코드를 제거..
}

코드 13.15 크리티컬 섹션 함수 변경 Main.c

크리티컬 섹션 함수에서는 12번째 줄과 같이 세마포어를 해제하는 Kernel_unlock_sem() 함수 호출 코드를 지움

크리티컬 섹션에 진입하면서 세마포어를 잠그기만 하고 해제는 하지 않음

 

결과 

실행을 하면 멈춰있음

U 키를 누르면 동작

Task2가 크리티컬 섹션에 진입해서 출력을 하긴 함

-> 그러나 세마포어의 잠금을 해제하지 않음

-> 다시 스케줄링을 받아서 크리티컬 섹션에 진입했을 때, Task2 자신이 잠갔던 세마포어에 걸려서 크리티컬 섹션에 진입하지 못함

-> QEMU의 출력으로 보면 그냥 멈춰있는 것처럼 보임

 

이 상태에서 키보드의 대문자 U를 입력하면 Task1이 세마포어를 품

-> 세마포어가 풀렸으므로 Task2가 크리티컬 섹션을 한 번 실행하고 다시 또 멈춤

-> 반복

 

세마포어 커널 API를 뮤텍스 커널 API로 바꿔서 테스트하면?

 

static uint32_t shared_value;
static void Test_critical_section(uint32_t p, uint32_t taskId)
{
    Kernel_lock_mutex(); //뮤텍스 수정
    
    debug_printf("User Task #%u Send=%u\n", taskId, p);
    shared_value = p;
    Kernel_yield();
    delay(1000);
    debug_printf("User Task #%u Shared Value=%u\n", taskId, shared_value);
    
}
...
중략
...
void User_task1(void)
{
...
중략
...
        case KernelEventFlag_Unlock:
			Kernel_unlock_mutex(); //뮤텍스 수정
			break;
        }
        Kernel_yield();
    }
}

코드 13.16 다른 태스크에서 뮤텍스 해제 

 

결과  

 

크리티컬 섹션의 내용이 한 번 출력되고 반응이 없음

U 키를 눌러도 동작하지 않음

 

WHY?

뮤텍스를 잠근 태스크는 Task2이므로 Task1에서 아무리 Kernel_unlock_mutex() 커널 API를 호출해 봤자 뮤텍스는 풀리지 않기 때문!

 

static uint32_t shared_value;
static void Test_critical_section(uint32_t p, uint32_t taskId)
{
    Kernel_lock_mutex();
    
    debug_printf("User Task #%u Send=%u\n", taskId, p);
    shared_value = p;
    Kernel_yield();
    delay(1000);
    debug_printf("User Task #%u Shared Value=%u\n", taskId, shared_value);
    
    Kernel_unlock_mutex();
}

코드 13.17 뮤텍스를 제자리로 옮긴 크리티컬 섹션

 

결과  

세마포어를 테스트했던 결과와 같은 결과가 나옴

Task2의 출력이 계속되는 중간에 키보드의 대문자 X를 계속 입력하여 Task0이 크리티컬 섹션에 끼어들게 만듦

뮤텍스로 크리티컬 섹션을 보호하고 있으므로 Task2가 잠근 뮤텍스는 Task2가 풀고 나오고 Task0가 잠근 뮤텍스는 Task0이 풀고 나옴

 

13.3 스핀락

바쁜 대기(busy waiting) 개념의 크리티컬 섹션 보호 기능임

 

바쁜 대기

: 스케줄링을 하지 않고 CPU를 점유한 상태, 즉 CPU가 여전히 바쁜 상태에서 락이 풀리는 것을 대기한다는 말

 

스케줄링을 하지 않고 짧은 시간 동안 CPU를 점유하면서 잠금이 풀리는 것을 기다린다는 아이디어이므로 멀티코어 환경에서 유용하게 쓰임

BUT, 싱글코어 환경에서는 다른 태스크가 잠금을 풀려면 어차피 스케줄링을 해야 하므로 스핀락의 개념을 사용할 수 없음

 

QEMU의 RealViewPB도 싱글코어로 에뮬레이팅되므로 스핀락을 사용할 수 없음

 

스핀락 개념

실제 스핀락 구현은 바쁜 대기 자체가 완전히 아토믹해야 하기 때문에 배타적 메모리 연산을 지원하는 어셈블리어 명령으로 구현됨

static bool sSpinLock = false;

void spin_lock(void)
{
	while (sSpinLock); // 대기
    sSpinLock = true;  // 잠금
}

void spin_unlock(void)
{
	sSpinLock = false; // 해제
}

바이너리 세마포어와 같은 동작을 함

 

대기할 때 스케줄러를 호출하지 않고 그냥 while loop로 CPU를 점유한 채로 대기

 

멀티코어 환경이라면

아마 다른 코어에서 동작 중인 스핀락을 잠갔던 태스크가 spin_unlock() 함수를 호출해서 공유 변수인 sSpinLock 변수를 false로 바꿔 줄 것이므로 while loop에 바쁜 대기 중인 코어의 대기가 풀리면서 크리티컬 섹션에 진입할 수 있음

 

13.4 요약

나빌로스의 설계상 싱글코어 환경에서는 동기화 문제가 발생하지 않지만

코드를 바꿔 실습해봄!

 

동기화를 어떤 식으로 설계하고 구현하는지 개념을 이해하고 있으면 실제로 필요한 상항에 직면했을 때 해결할 수 있을 것!