Blocking semaphore, scheduler

1. Wait와 Signal의 새로운 흐름도 (음수 세마포어의 비밀)

이전 Lab 2에서는 세마포어 값이 무조건 0 아니면 양수였습니다. 하지만 진짜 블로킹 세마포어에서는 값이 음수(-)로 떨어질 수 있으며, 이 음수 값이 대기자의 수를 의미합니다.

[Wait 함수 논리]

1. s = s - 1을 먼저 실행합니다.
2. 만약 s < 0이 되었다면? 자원은 이미 남이 쓰고 있는데 내가 하나 더 빼버린 상황이므로, 현재 스레드를 블록(Block) 시킵니다.

[Signal 함수 논리]

1. s = s + 1을 먼저 실행합니다.
2. 만약 s <= 0이라면? 누군가 음수 상태로 대기하고 있었다는 뜻이므로, 잠들어 있는 스레드 중 하나를 깨워줍니다(Wake up).

세마포어 값(free)의 의미 완벽 해석
1: 자원이 비어있음 (아무도 안 씀)
0: 누군가 자원을 쓰고 있음 (대기자는 없음)
-1: 1명이 사용 중이고, 1명이 대기 중
-2: 1명이 사용 중이고, 2명이 대기 중

2. 공평성을 위한 유한 대기 (Bounded Waiting) 2가지 방식

스레드가 억울하게 영원히 자원을 못 받는 일(Starvation)을 막기 위해, 순서를 공평하게 보장하는 복잡한 방법들입니다.

방법 A (대기열 큐 분리): 블록된 스레드를 현재 돌아가고 있는 원형 연결 리스트에서 아예 빼버립니다. 그리고 그 세마포어만의 전용 줄(선형 리스트)에 세웁니다. 늦게 오면 줄 맨 뒤에 서고, Signal로 깨울 때는 줄 맨 앞부터 차례대로 깨워줍니다 (완벽한 선입선출, FIFO).

방법 B (타임스탬프 기록): 스레드를 리스트에서 빼지 않고 그대로 둡니다. 대신 TCB에 '잠든 시간'을 기록합니다. Signal로 누군가를 깨워야 할 때, 리스트 전체를 싹 다 뒤져서 가장 오래 기다린 스레드를 찾아내어 깨웁니다.

3. Scheduler

교수님이 아주 기쁜 소식을 적어두셨네요. "You do not need to implement bounded waiting in any of the labs." 즉, 우리 랩에서는 위에서 말한 복잡한 공평성 로직을 짤 필요가 없습니다!

단순한 방식에서는 스레드들이 잠들든 깨어있든 여전히 하나의 원형 연결 리스트 안에 같이 빙글빙글 돌고 있습니다. 대신, 깨울 사람을 고를 때 누가 먼저 왔는지 안 따지고 그냥 아무나 하나 골라서 깨웁니다.

[스케줄러 (Scheduler) 코드 완벽 해부]

void Scheduler(void){
    RunPt = RunPt->next;       // 1. 일단 다음 스레드로 턴을 넘겨봅니다.
    
    while(RunPt->blocked){     // 2. 만약 넘어간 스레드의 명찰(blocked)에 뭔가 적혀있다면? (잠들어 있다면?)
        RunPt = RunPt->next;   // 3. 실행하지 않고 바로 그 다음 스레드로 건너뜁니다 (Skip).
    }
}

코드 설명: SysTick 타이머가 울릴 때마다 실행되는 Scheduler입니다. 턴을 넘겨받은 스레드(RunPt)의 blocked 필드를 검사합니다. 만약 0이 아니라 특정 세마포어 주소(&free 등)가 적혀있다면, 이 스레드는 잠들어 있다는 뜻이므로 while문을 통해 깨어있는 스레드를 찾을 때까지 계속 다음으로 건너뜁니다(Skip).

중요한 점: 누군가 OS_Signal을 불렀다고 해서 곧바로 CPU 화면이 전환(Thread Switch)되는 것이 아닙니다. Signal은 그저 잠들어 있던 TCB의 blocked 명찰을 지워줄(0으로 만들) 뿐입니다. 진짜 실행은 나중에 타이머가 울려 이 Scheduler가 그 스레드를 찾아냈을 때 비로소 시작됩니다.

4. OS_Wait

이 함수는 스레드가 자원(열쇠)을 요청할 때 불립니다. 자원이 없으면 스핀락처럼 빙글빙글 도는 게 아니라, 스스로 명찰을 달고 수면 상태에 빠집니다.

void OS_Wait(int32_t *s){
    DisableInterrupts();  // Enter critical section
    (*s) = (*s) - 1;      // 1) Decrement the semaphore first
    
    if((*s) < 0){         // 2) If it's less than 0, the resource is taken!
        RunPt->blocked = s; // 3) Put a nametag on: "I am blocked by semaphore 's'"
        EnableInterrupts(); // Open interrupts before suspending
        OS_Suspend();       // 4) Go to sleep and yield the CPU to the next thread
    }
    EnableInterrupts();   // Exit critical section (if resource was available)
}

• 핵심 포인트: 먼저 묻지도 따지지도 않고 열쇠 개수를 하나 뺍니다(s = s - 1).

• 빼고 났더니 음수(< 0)가 되었다면? 내가 억지로 빚을 냈다는 뜻이므로, 내 TCB의 blocked 필드에 해당 세마포어의 주소(s)를 적어둡니다. (이게 바로 "나 여기서 막혔어!"라는 명찰입니다.)

• 그리고 OS_Suspend()를 불러서 내 남은 시간을 포기하고 기절해 버립니다.

5. OS_Signal

이 함수는 스레드가 자원 사용을 다 끝내고 반납할 때 불립니다. 만약 자원을 기다리며 잠들어 있는 스레드가 있다면 찾아서 깨워줍니다.

void OS_Signal(int32_t *s){
    tcbType *pt;
    DisableInterrupts();   // Enter critical section
    (*s) = (*s) + 1;       // 1) Increment the semaphore (return the key)
    
    if((*s) <= 0){         // 2) If it's 0 or less, someone is sleeping!
        pt = RunPt->next;  // 3) Start searching from the next thread
        
        // 4) Loop until we find the thread blocked by THIS specific semaphore 's'
        while(pt->blocked != s){ 
            pt = pt->next; 
        }
        pt->blocked = 0;   // 5) Wake it up by removing the nametag!
    }
    EnableInterrupts();    // Exit critical section
}

• 핵심 포인트: 열쇠를 반납(s = s + 1)했는데도 여전히 값이 0 이하(<= 0)라면? 누군가 대기열에서 자고 있다는 뜻입니다.

• 그래서 다음 스레드(RunPt->next)부터 시작해서 원형 연결 리스트를 빙글빙글 돌며 검사합니다.

• pt->blocked == s인 녀석을 찾으면, 그 스레드의 명찰을 떼어줍니다(pt->blocked = 0).

• [매우 중요] 명찰만 떼어줄 뿐, 여기서 바로 OS_Suspend()를 부르지 않습니다. (Calling the signal will not invoke a thread switch). 즉, 깨어난 스레드는 당장 실행되는 게 아니라, 나중에 스케줄러가 차례를 주면 그때부터 달리게 됩니다.

6. Question "잠든 스레드를 리스트에 그냥 둬도 괜찮을까?"

이 질문은 아주 현실적이고 날카로운 엔지니어링 질문입니다.
우리가 짠 방식은 잠든 스레드를 리스트에서 빼내지 않고(Unchaining 안 함) 같이 빙글빙글 돌려두고, 스케줄러가 while(RunPt->blocked)로 하나씩 건너뛰는(Skip) 방식이었습니다.

질문: "건너뛰는 것도 결국 150ns(나노초)라는 CPU 연산 시간이 드는데, 잠든 스레드가 많으면 이 스킵하는 시간 때문에 시스템이 느려지지 않을까? 그냥 아예 대기 전용 리스트로 빼버리는 게(Unchaining) 낫지 않을까?"

답변(계산 결과): 스레드가 총 8개고 5개가 잠들어 있다고 가정해 봅시다. 최악의 경우 스케줄러는 5번을 건너뛰어야 하므로 5 * 150ns = 750ns의 시간을 낭비합니다.

하지만 스케줄러는 1ms(1,000,000ns)마다 한 번씩 돕니다. 전체 시간 중 고작 0.075%의 시간만 낭비할 뿐입니다.

결론: 낭비되는 시간(0.075%)이 너무나도 미미하기 때문에, 굳이 리스트를 뗐다 붙였다 하는 복잡한 코드를 짤 필요가 전혀 없습니다! 지금 우리가 배운 "단순한 방식(Simple Approach)"이 효율성과 코드의 간결함 측면에서 완벽한 정답이라는 것을 증명하는 계산입니다.