default pintOS는 semaphore를 대기하고 있는 스레드들의 list읜 waieters가 FIFO로 구현되어있다. 이를 여러 스레드가 lock, semaphore, condition variable을 얻기 위해 기다릴 경우 우선순위가 가장 높은 thread가 CPU를 점유하도록 수정해보자.

🌸🌸🌸블로그 글은 복습 겸 gitbook의 순서에 따라 번역 및 관련 내용에 JK피셜을 달아 정리할 예정이다. 말그대로 JK피셜인 칸큼 100%맞는 말은 아닐 수 있다는 거 참고해주길 바란다.

---

📖 Gitbook 내용(in APPENDIX) 📖

gitbook을 다시 읽어보니 중요한 내용들과 힌트들이 이안에 다 있었다. 눈 먼 장님이라는게 이런건가!

Synchronization

스레드 간의 자원 공유가 신중하고 통제된 방식으로 처리되지 않으면 일반적으로 큰 문제가 발생합니다. 특히 운영 체제 커널에서는 잘못된 공유로 인해 전체 시스템이 충돌할 수 있습니다. Pintos는 이러한 문제를 해결하기 위해 여러 동기화 기본 요소를 제공합니다.

Disabling Interrupts

가장 원시적인 동기화 방법은 인터럽트를 비활성화하는 것입니다. 즉, CPU가 인터럽트에 응답하지 못하도록 일시적으로 막는 것입니다. 인터럽트가 꺼져 있으면 다른 스레드는 실행 중인 스레드를 선점하지 않습니다. 왜냐하면 스레드 선점은 타이머 인터럽트에 의해 제어되기 때문입니다. 인터럽트가 켜져 있는 경우, 일반적으로 그렇습니다. 실행 중인 스레드는 두 개의 C 문 사이 또는 하나의 실행 내에서도 언제든지 다른 스레드에 의해 선점될 수 있습니다.

그런 관점에서 Pintos는 "선점 가능한 커널(preemptible kernel)" 입니다. 즉, 커널 스레드는 언제든지 선점될 수 있습니다. 전통적인 Unix 시스템은 "비선점 가능한(nonpreemptible)" 커널이라고 할 수 있습니다. 즉, 커널 스레드는 명시적으로 스케줄러를 호출하는 지점에서만 선점될 수 있습니다. (사용자 프로그램은 두 모델 모두에서 언제든지 선점될 수 있습니다.) 선점 가능한 커널은 명시적인 동기화가 더 필요하다는 점에서 상상할 수 있습니다.

여러분이 인터럽트 상태를 직접 세팅할 필요는 별로 없습니다. 대부분의 경우 이어지는 섹션에서 설명해드릴 synchronization 함수들을 사용하면 됩니다. 인터럽트를 비활성화 시키는 주된 이유는 외부의 인터럽트 핸들러와 커널 쓰레드를 동기화 시키기 위해서 입니다. 외부 인터럽트 핸들러는 잠들게 할 수 없어서, 비활성화시키지 않고 다른 방법으로는 동기화가 거의 불가능 합니다.

몇가지 외부 인터럽트는 인터럽트 비활성화로도 막아둘 수 없습니다. 이런 인터럽트들은 마스크 불가능 인터럽트(NMIs) 라고 하는데, 컴퓨터가 불이났을 때(화재상황)처럼 긴급한 경우에만 사용되어야 합니다. Pintos는 마스크 불가능 인터럽트를 다루지 않습니다.

인터럽트를 비활성화하고 활성화하기 위한 유형과 함수는 include/threads/interrupt.h에 정의되어 있습니다.

INTR_OFF 또는 INTR_ON 중 하나로, 각각 인터럽트가 비활성화되었거나 활성화되었음을 나타냅니다.

enum intr_level;

현재 인터럽트 상태(inter_level)를 리턴하는 함수입니다.

enum intr_level intr_get_level (void)

현재 상태(inter_level)에 따라 인터럽트를 활성화하거나 비활성화하는 함수입니다. 인터럽트의 이전 상태를 리턴합니다.

enum intr_level intr_set_level (enum intr_level level);

인터럽트를 활성화하는 함수입니다. 인터럽트의 이전 상태를 리턴합니다.

enum intr_level intr_enable (void);

인터럽트를 비활성화 해주는 함수입니다. 인터럽트의 이전 상태를 리턴합니다.

enum intr_level intr_disable (void);

Semaphores

세마포어는 0 이상의 정수와 함께 사용되는 두 가지 atomic한(race condition이 없도록 한가지만 접근하도록 한) 조작 연산인 "Down" 또는 "P"와 "UP" 또는 "V"로 구성됩니다. 이 연산자들은 다음과 같은 역할을 수행합니다:

• "Down" 또는 "P": 값이 양수가 될 때까지 대기한 후 값을 감소시킵니다.
• "UP" 또는 "V": 값을 증가시킵니다 (그리고 대기 중인 스레드 중 하나를 깨웁니다).

0으로 초기화된 세마포어는 정확히 한 번 발생할 이벤트를 기다리는 데 사용될 수 있습니다. 예를 들어, 스레드 A가 다른 스레드 B를 시작하고 B가 어떤 작업이 완료될 때까지 기다리려고 할 때, A는 0으로 초기화된 세마포어를 생성하고 B에게 전달한 후 세마포어를 "down"합니다. B가 작업을 완료하면 세마포어를 "up"합니다. A가 세마포어를 "down"하거나 B가 "up"하는 순서에 상관없이 이 방법은 작동합니다.

예시:

struct semaphore sema;

/* Thread A */
void threadA (void) {
    sema_down (&sema);
}

/* Thread B */
void threadB (void) {
    sema_up (&sema);
}

/* main function */
void main (void) {
    sema_init (&sema, 0);
    thread_create ("threadA", PRI_MIN, threadA, NULL);
    thread_create ("threadB", PRI_MIN, threadB, NULL);
}

이 예시에서, threadA는 sema_down() 함수를 사용하여 threadB가 sema_up() 함수를 호출할 때까지 실행을 멈춥니다.

1로 초기화된 세마포어는 주로 리소스 접근을 제어하는 데 사용됩니다. 리소스를 사용하기 전에 해당하는 코드 블록은 세마포어를 "down" (감소)시키고, 리소스 사용이 끝나면 "up" (증가)시킵니다. 이러한 경우에는 락 (lock)이 더 적합할 수 있습니다.

세마포어는 1보다 큰 값을 가지도록 초기화될 수도 있습니다. 그러나 이러한 경우는 드물게 사용됩니다. 세마포어는 Edsger Dijkstra가 개발한 것으로, THE 운영 체제에서 처음 사용되었습니다. Pintos의 세마포어 타입과 연산은 include/threads/synch.h 헤더 파일에 선언되어 있습니다.

세마포어를 나타냅니다.

struct semaphore;

주어진 초기값을 가지고 새로운 세마포어를 초기화합니다.

void sema_init (struct semaphore *sema, unsigned value);

sema에 대해 "down" 또는 "P" 연산을 수행하여 값이 양수가 될 때까지 기다리고, 그 후에 값을 1 감소시킵니다.

void sema_down (struct semaphore *sema);

sema에 대해 "down" 또는 "P" 연산을 시도하며, 대기하지 않습니다. sema가 성공적으로 감소되면 true를 반환하고, 이미 0이기 때문에 대기 없이 감소할 수 없는 경우 false를 반환합니다. 이 함수를 반복문 안에서 계속 호출하는 것은 CPU 시간을 낭비하므로, sema_down()를 사용하거나 다른 접근 방식을 찾는 것이 좋습니다.

bool sema_try_down (struct semaphore *sema);

sema에 대해 "up" 또는 "V" 연산을 실행하여 값을 증가시킵니다. sema에 대기 중인 스레드가 있다면 그 중 하나를 깨웁니다. 대부분의 동기화 기법과는 달리, sema_up()은 외부 인터럽트 핸들러 내에서 호출될 수 있습니다.

void sema_up (struct semaphore *sema);

세마포어는 인터럽트 비활성화(disabling interrupt) 및 스레드의 차단 및 차단 해제(thread_block() 및 thread_unblock())를 내부적으로 사용하여 구축됩니다. 각 세마포어는 lib/kernel/list.c의 연결 리스트 구현을 사용하여 대기 중인 스레드의 목록을 유지합니다.

Locks

락은 초기 값이 1인 세마포어와 유사합니다(세마포어 참조). 락의 "up"과 동등한 작업은 "release"로 불리며, "down" 작업은 "acquire"로 불립니다.

세마포어와 비교하여 락은 추가적인 제한이 있습니다: 오직, 락을 갖고있는 “owner” 쓰레드만이 락을 놓아줄 수 있습니다. 만약 이 제약때문에 문제가 되는 경우는 락대신에 세마포어를 써야한다는 좋은 신호입니다.

Pintos에서의 락은 "재귀적(recursive)"이 아닙니다. 즉, 현재 락을 소유한 스레드가 해당 락을 다시 획득하려고 시도하는 것은 오류입니다. 락의 유형과 함수는 include/threads/synch.h에 선언되어 있습니다.

락을 나타냅니다.

struct lock;

lock을 새로 초기화합니다. 이 락은 초기 상태에서 어떤 스레드에게도 소유되지 않습니다.

void lock_init (struct lock *lock);

현재 스레드가 락을 획득합니다. 필요한 경우 현재 소유자가 락을 해제할 때까지 대기합니다.

void lock_acquire (struct lock *lock);

현재 스레드가 사용하기 위해 락을 획득하려고 시도합니다. 대기하지 않고 바로 획득할 수 있는 경우 true를 반환하고, 이미 다른 스레드에 의해 소유되었을 경우 false를 반환합니다. 이 함수를 반복적으로 호출하는 것은 CPU 시간을 낭비하므로 lock_acquire()를 사용해야 합니다.

bool lock_try_acquire (struct lock *lock);

현재 스레드가 소유한 락을 해제합니다.

void lock_release (struct lock *lock);

running thread가 lock을 소유하면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 임의의 스레드가 lock을 소유하는지 테스트하는 함수는 없습니다. 왜냐하면 호출자가 그 결과에 대한 조치를 취하기 전에 상황이 변경될 수 있기 때문입니다.

bool lock_held_by_current_thread (const struct lock *lock):

Monitors

모니터는 세마포어나 락보다 더 높은 수준의 동기화 형식입니다. 모니터는 동기화되는 데이터와 모니터 락이라고 불리는 락, 그리고 하나 이상의 조건 변수로 구성됩니다. 스레드가 보호된 데이터에 접근하기 전에 먼저 모니터 락을 획득합니다. 이때 스레드는 "모니터 안에 있다"고 말합니다. 모니터 안에 있는 동안 스레드는 보호된 모든 데이터에 대한 제어권을 가지며, 자유롭게 검사하거나 수정할 수 있습니다. 보호된 데이터에 대한 접근이 완료되면 모니터 락을 해제합니다.

컨디션 변수는 특정 컨디션(조건)이 참이 될 때까지 모니터안의 코드가 기다릴 수 있게합니다. 각 컨디션 변수는 추상적인 조건과 관련있습니다. 예를 들면 “프로세스가 진행되는 동안 몇가지 데이터가 도착하는 조건”, “유저의 마지막 키보드 입력으로 부터 10초가 넘게 지나는 조건” 입니다. 모니터안의 코드가 특정 조건이 참이 되기를 기다릴 때, 그 코드는 원하는 조건과 관련된 컨디션 변수를 기다립니다(wait). 그 컨디션 변수는 락을 놓아주고 컨디션이 신호받는 것을 기다립니다. 반대로 이 코드가 특정 조건이 참이되도록 만드는 경우에는, 그 참이된 조건을 신호로 보내서(signal) 기다리는 코드 하나를 깨우거나, 전부한테 알려서(broadcast) 자는 코드를 전부 깨웁니다.

모니터의 이론적인 기반은 C.A.R.호어가 마련했습니다. 실제적인 사용법은 나중에 Mesa 운영 체제에 관한 논문에서 더 발전되었습니다. 조건 변수의 타입과 함수는 include/threads/synch.h에 선언되어 있습니다.

조건 변수를 나타냅니다.

struct condition;

cond를 새로운 조건 변수로 초기화합니다.

void cond_init (struct condition *cond);

원자적으로 lock(모니터 락)을 해제하고 다른 코드에서 cond(조건 변수)가 시그널을 받을 때까지 대기합니다. cond가 시그널을 받은 후, 반환하기 전에 다시 lock을 얻습니다. 이 함수를 호출하기 전에 lock을 보유해야 합니다. 시그널을 보내고 대기에서 깨어나는 것은 원자적인 연산이 아닙니다. 따라서 일반적으로 cond_wait() 호출자는 대기가 완료된 후 조건을 다시 확인하고 필요한 경우 다시 대기해야 합니다. 예제는 다음 섹션에서 설명합니다.

void cond_wait (struct condition *cond, struct lock *lock);

만약 cond(모니터 락 lock으로 보호되는)에 대기 중인 스레드가 있다면, 이 함수는 그 중 하나를 깨웁니다. 대기 중인 스레드가 없다면 어떤 동작도 수행하지 않고 반환합니다. 이 함수를 호출하기 전에 lock을 보유해야 합니다.

void cond_signal (struct condition *cond, struct lock *lock);

cond(모니터 락 lock으로 보호되는)에 대기 중인 모든 스레드(있는 경우)를 깨웁니다. 이 함수를 호출하기 전에 lock을 보유해야 합니다.

void cond_broadcast (struct condition *cond, struct lock *lock);

Monitor Example

모니터의 전형적인 예는 하나 이상의 "생산자" 스레드가 문자를 작성하고 하나 이상의 "소비자" 스레드가 문자를 읽는 버퍼 처리입니다. 이를 구현하기 위해서는 모니터 락 외에도 not_full과 not_empty라고 부를 두 가지 조건 변수가 필요합니다.

char buf[BUF_SIZE];     /* Buffer. */
    size_t n = 0;         /* 0 <= n <= BUF SIZE: # of characters in buffer. */
    size_t head = 0;        /* buf index of next char to write (mod BUF SIZE). */
    size_t tail = 0;         /* buf index of next char to read (mod BUF SIZE). */
    struct lock lock;         /* Monitor lock. */
    struct condition not_empty; /* Signaled when the buffer is not empty. */
    struct condition not_full;     /* Signaled when the buffer is not full. */

    ...initialize the locks and condition variables...

    void put (char ch) {
      lock_acquire (&lock);
      while (n == BUF_SIZE)    /* Can't add to buf as long as it's full. */
        cond_wait (&not_full, &lock);
      buf[head++ % BUF_SIZE] = ch;    /* Add ch to buf. */
      n++;
      cond_signal (&not_empty, &lock);    /* buf can't be empty anymore. */
      lock_release (&lock);
    }

    char get (void) {
      char ch;
      lock_acquire (&lock);
      while (n == 0)        /* Can't read buf as long as it's empty. */
        cond_wait (&not_empty, &lock);
      ch = buf[tail++ % BUF_SIZE];    /* Get ch from buf. */
      n--;
      cond_signal (&not_full, &lock);    /* buf can't be full anymore. */
      lock_release (&lock);
    }

위의 코드가 완전히 정확하려면 BUF_SIZE가 SIZE_MAX + 1로 나누어 떨어져야 함에 유의하세요. 그렇지 않으면 head가 0으로 되돌아갈 때 처음으로 실패할 수 있습니다. 실제로는 BUF_SIZE가 보통 2의 거듭제곱수가 될 것입니다.

Optimization Barriers

최적화 장벽(optimization barrier) 은 컴파일러가 장벽을 통과하는 메모리 상태에 대해 가정을 할 수 없도록 하는 특별한 문장입니다. 컴파일러는 장벽을 통과하는 변수의 읽기 또는 쓰기를 재배열하지 않거나, 변수의 값이 장벽을 통과하는 동안 변경되지 않았다고 가정하지 않습니다. 다만, 주소가 사용되지 않는 로컬 변수에 대해서는 예외입니다. Pintos에서는 include/threads/synch.h에서 barrier() 매크로를 최적화 장벽으로 정의하고 있습니다.

최적화 장벽을 사용하는 이유 중 하나는 데이터가 비동기적으로 변경될 수 있는 경우입니다. 다른 스레드나 인터럽트 핸들러와 같은 요소에 의해 컴파일러의 알지 못하는 상황에서 데이터가 변경될 수 있습니다. devices/timer.c의 too_many_loops() 함수가 이를 예로 들 수 있습니다. 이 함수는 타이머 틱이 발생할 때까지 루프를 돌면서 busy-waiting으로 시작됩니다.

    /* Wait for a timer tick. */
    int64_t start = ticks;
    while (ticks == start)
        barrier();

루프에서 최적화 장벽이 없는 경우, 컴파일러는 start와 ticks가 처음에 동일하며 루프 자체에서 변경되지 않기 때문에 루프가 종료되지 않을 것이라고 결론을 내릴 수 있습니다. 그러면 컴파일러는 함수를 무한 루프로 "최적화"할 수 있으며, 이는 분명히 원하지 않는 결과입니다.

최적화 장벽은 다른 컴파일러 최적화를 피하기 위해 사용될 수도 있습니다. devices/timer.c에 있는 busy_wait() 함수가 이를 예로 들 수 있습니다. 이 함수에는 다음과 같은 루프가 포함되어 있습니다.

    while (loops-- > 0)
      barrier ();

이 루프의 목표는 원래 값부터 0까지 루프를 카운트하여 바쁜 대기(busy-wait)를 수행하는 것입니다. 최적화 장벽이 없는 경우 컴파일러는 유용한 출력을 생성하지 않으며 부작용도 없기 때문에 루프를 완전히 삭제할 수 있습니다. 장벽은 컴파일러에게 루프 본문이 중요한 효과가 있다고 가정하도록 강제합니다.

마지막으로, 최적화 장벽은 메모리 읽기 또는 쓰기의 순서를 강제하기 위해 사용될 수도 있습니다. 예를 들어, 타이머 인터럽트가 발생할 때마다 글로벌 변수 timer_put_char에 저장된 문자를 콘솔에 출력하는 "기능"을 추가한다고 가정해보겠습니다. 단, 글로벌 부울 변수 timer_do_put이 true인 경우에만 출력해야 합니다. 이 경우 x를 출력하기 위해 최적화 장벽을 사용하는 것이 가장 좋습니다.

    timer_put_char = 'x';
    barrier ();
    timer_do_put = true;

장벽이 없으면 컴파일러는 연산을 재배열할 자유가 있기 때문에 코드에 버그가 있을 수 있습니다. 컴파일러는 연산의 순서를 유지할 이유가 없다고 판단하면 연산의 순서를 바꿀 수 있습니다. 이 경우, 컴파일러는 할당문의 순서가 중요하다는 것을 알지 못하기 때문에 최적화 기능이 할당문의 순서를 바꿀 수 있습니다. 실제로 이렇게 할지는 알 수 없으며, 컴파일러에게 다른 최적화 플래그를 전달하거나 다른 버전의 컴파일러를 사용하면 다른 동작이 발생할 수 있습니다.

다른 해결책은 할당문 주변에서 인터럽트를 비활성화하는 것입니다. 이는 재배열을 방지하지는 않지만, 인터럽트 핸들러가 할당문 사이에 개입하는 것을 방지합니다. 그러나 인터럽트를 비활성화하고 다시 활성화하는 런타임 비용이 추가로 발생합니다.

    enum intr_level old_level = intr_disable ();
    timer_put_char = 'x';
    timer_do_put = true;
    intr_set_level (old_level);

두 번째 해결책은 timer_put_char와 timer_do_put의 선언을 volatile로 표시하는 것입니다. 이 키워드는 컴파일러에게 변수가 외부에서 관찰 가능하며 최적화의 자유도를 제한한다고 알려줍니다. 그러나 volatile의 의미는 명확하게 정의되어 있지 않으므로 일반적인 해결책으로 사용하기에는 적절하지 않습니다. 기본 Pintos 코드는 전혀 volatile을 사용하지 않습니다.

다음은 해결책이 아닙니다. 왜냐하면 락은 인터럽트를 방지하지 않으며, 락이 보유된 영역 내에서 코드의 재배열을 컴파일러로부터 방지하지 않기 때문입니다.

    lock_acquire (&timer_lock);        /* INCORRECT CODE */
    timer_put_char = 'x';
    timer_do_put = true;
    lock_release (&timer_lock);

컴파일러는 외부에서, 즉 다른 소스 파일에서 정의된 함수의 호출에 대해서는 최소의 최적화 장벽으로서 대합니다. 구체적으로 말해보면, 컴파일러는 외부에서 정의된 함수들이 정적, 동적으로 할당된 어떤 데이터나 주소가 정해진 어떤 지역변수들에도 접근 할 수 있다고 가정합니다. 이건 명시적인 장벽이 생략될 수 있다는 뜻입니다. Pintos가 명시적인 장벽을 거의 갖고있지 않는 이유입니다.

같은 소스 파일안에서 정의된 함수나 포함된 헤더를 최적화 장벽으로 기대하면 안됩니다. 최적화 장벽은 심지어 함수를 정의하기 전에도, 해당 함수의 사용에 대해 적용될 수 있습니다. 이유는 컴파일러는 최적화를 수행하기 전에 먼저 전체 소스 파일을 읽고 파싱하기 때문입니다.

---

⌨️ 코드 구현 ⌨️

thread가 priority에 따라 실행이 되도록 구현하려면 '질서'를 만들어야한다. pintOS에서는 이를 lock&semaphore로 구현한다. 앞서 gitbook에 나와있듯이 pintOS에서는 lock를 semaphore 1로 구현한다. 하지만 lock과 semaphore의 차이점은 lock을 가지고 있는 thread가 lock을 놓아줄 수 있다는 것이다.

코드로 구현하기 위해 먼저 sema_init()코드를 확인해보자.

//thread/synch.c

void sema_init(struct semaphore *sema, unsigned value)
{
	ASSERT(sema != NULL);
	sema->value = value;
	list_init(&sema->waiters);
}

assert를 통해 세마포어가 null이 아닌지 확인하고, 세마포어 구조체의 value에 주어진 인자 값을 초기값으로 할당한다.
이후 세마포어 구조체 내부의 waiters리스트를 list_init()함수를 사용해 초기화 한다.

---

sema_down()을 수정해주자.

기존에 있던 sema_down()은 아래와 같다.

//thread/synch.c

/* Down or "P" operation on a semaphore.  Waits for SEMA's value
   to become positive and then atomically decrements it.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but if it sleeps then the next scheduled
   thread will probably turn interrupts back on. This is
   sema_down function. */
void
sema_down (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);
	ASSERT (!intr_context ());

	old_level = intr_disable ();
	while (sema->value == 0) {
		list_push_back (&sema->waiters, &thread_current ()->elem);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

intr_disable 함수를 호출하여 현재 인터럽트 레벨을 저장하고 인터럽트를 비활성한 뒤, while 루프를 사용하여 세마포어의 값이 0인 동안 대기한다.
while 루프를 빠져나오면 세마포어의 값을 1 감소시킨다. 이후 intr_set_level 함수를 호출하여 이전 인터럽트 레벨을 복원하고 인터럽트를 다시 활성화한다.

이말을 정리해보면, threadA는 세마포어가 0인 동안 블록되고 대기상태에 있다가 running상태에 있는 다른 thread가 해당 세마포어를 1로 올려주면 기다리고 있던 threadA가 while문을 빠져나오고 threadA가 세마포어를 가져갔다는 뜻으로 0으로(sema->value--;) 만들어주는 것이다. 이를 통해 다른 스레드가 동시에 접근하지 못하도록 한다.

우리팀 수정 코드 🤓

//thread/synch.c

void sema_down(struct semaphore *sema)
{
	enum intr_level old_level;

	ASSERT(sema != NULL);
	ASSERT(!intr_context());

	old_level = intr_disable();
	while (sema->value == 0) /* sema에 접근할 수 없을 때 */
	{
		list_insert_ordered(&sema->waiters, &thread_current()->elem, &priority_less, NULL); /* 접근 권한이 생기기를 기다리는 스레드를 waiters에 추가 */
		thread_block();																		   /* 해당 스레드 block */
	}
	sema->value--;
	intr_set_level(old_level);
}

waiters list에 들어갈 때, priority 순으로 정렬되어 넣어져서 priority에 따라 ready_list가 정렬될 수 있도록 수정했다.

---

sema_up()을 수정해주자.

기존에 있던 sema_up()은 아래와 같다.

//thread/synch.c

/* Up or "V" operation on a semaphore.  Increments SEMA's value
   and wakes up one thread of those waiting for SEMA, if any.

   This function may be called from an interrupt handler. */
void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters))
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	sema->value++;
	intr_set_level (old_level);
}

인터럽트 비활성화를 통해 현재 실행 중인 코드가 중단되지 않도록 한다. 세마포어의 대기 리스트에 대기 중인 스레드가 있는지 확인하고, 대기중인 스레드가 있다면 list_pop_front 함수를 사용하여 첫 번째 스레드를 꺼내고, 이 스레드를 thread_unblock 함수를 호출하여 준비 상태로 변경한다. 이를 통해 세마포어를 기다리고 있던 스레드가 실행 가능한 상태로 전환한다.

세마포어의 값을 1 증가시킴으로써 현재 running상태에 있는 thread는 해당 세마포어가 지키고 있는 자원을 다썼음을 알리고, waiters list의 head에 있는 thread가 해당자원에 접근 가능하도록 한다.
마지막으로, 이전의 인터럽트 레벨을 복원하고 인터럽트를 다시 활성화한다.

우리팀 수정 코드 🤓

//thread/synch.c

void sema_up(struct semaphore *sema)
{
	enum intr_level old_level;

	ASSERT(sema != NULL);

	old_level = intr_disable();
	if (!list_empty(&sema->waiters))
	{
		list_sort(&sema->waiters, &priority_less, NULL); /* 우선 순위가 변경됐을 경우 waiters 정렬 */
		thread_unblock(list_entry(list_pop_front(&sema->waiters),
								  struct thread, elem)); /* prioirty가 가장 높은 스레드를 unblock */
	}
	sema->value++;
	test_max_priority();
	intr_set_level(old_level);
}

waiters리스트에 있는 head를 뽑아올때 priority에 따라 한번 더 정렬시키고 뽑아옴으로써 priority에 따라 구현될 수 있도록 수정했다.
이후, 현재 실행 중인 스레드의 우선순위보다 높은 우선순위를 가진 스레드가 준비 리스트에 있는 경우에만 현재 스레드를 양보하는test_max_priority()함수를 추가함으로써 prioirty가 가장 높은 스레드가 running thread가 되도록 구현한다.

---

cond_wait()을 수정해보자.

//threads/thread.c

/* Atomically releases LOCK and waits for COND to be signaled by
   some other piece of code.  After COND is signaled, LOCK is
   reacquired before returning.  LOCK must be held before calling
   this function.

   The monitor implemented by this function is "Mesa" style, not
   "Hoare" style, that is, sending and receiving a signal are not
   an atomic operation.  Thus, typically the caller must recheck
   the condition after the wait completes and, if necessary, wait
   again.

   A given condition variable is associated with only a single
   lock, but one lock may be associated with any number of
   condition variables.  That is, there is a one-to-many mapping
   from locks to condition variables.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep. */

cont_wait에 달려있는 주석을 해석해보면 다음과 같다.

LOCK을 원자적으로 해제하고 COND가 다른 코드에 의해 시그널되기를 기다립니다. COND가 시그널되면 반환하기 전에 LOCK을 다시 획득합니다. 이 함수를 호출하기 전에 LOCK을 보유해야 합니다.
이 함수로 구현된 모니터는 "Mesa" 스타일 이며 "Hoare" 스타일이 아닙니다. 따라서 보통 호출자는 대기가 완료된 후 조건을 다시 확인하고 필요한 경우 다시 대기해야 합니다.
특정 조건 변수는 하나의 락에만 연결되지만, 하나의 락은 여러 조건 변수에 연결될 수 있습니다. 즉, 락에서 조건 변수로의 일대다 매핑이 있습니다.
이 함수는 sleep이 발생할 수 있으므로 인터럽트 핸들러 내에서 호출해서는 안됩니다. 인터럽트가 비활성화된 상태에서 호출되더라도, sleep이 필요한 경우 인터럽트가 다시 활성화됩니다.

주석에서 언급된 mesa 스타일과 hoare스타일에 대해 알아보자.

Mesa 스타일:

• 신호(signal)와 대기(wait) 연산이 원자적이지 않습니다. 즉, 대기 중인 스레드가 신호를 기다리는 동안 신호를 보낸 스레드가 대기 중인 스레드를 깨우지 않을 수 있습니다.
• 대기 중인 스레드가 깨어난 후에는 다시 조건을 확인해야 합니다. 만약 여전히 조건이 충족되지 않았다면, 다시 대기해야 할 수 있습니다.

Hoare 스타일:

• 신호(signal)와 대기(wait) 연산이 원자적입니다. 즉, 신호를 보낸 스레드는 대기 중인 스레드를 깨우고, 대기 중인 스레드는 신호를 받을 때까지 대기합니다.
• 대기 중인 스레드가 깨어난 후에는 조건이 충족되었음을 가정할 수 있습니다. 따라서 조건을 확인할 필요 없이 진행할 수 있습니다.

대기 중인 스레드가 깨어난 후에는 다시 조건을 확인해아 하는 것을 염두해두고, 이번에는 기존 코드에 대해 알아보자.

//thread/synch.c

void
cond_wait (struct condition *cond, struct lock *lock) {
	struct semaphore_elem waiter;

	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	sema_init (&waiter.semaphore, 0);
	list_push_back (&cond->waiters, &waiter.elem);
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

cond_wait 함수는 모니터안의 코드가 특정 조건이 참이 되기를 기다릴 때, 그 코드는 원하는 조건과 관련된 컨디션 변수를 기다리는 함수다.(gitbook참고)

gtibook에서는 "생산자" 스레드가 문자를 작성하고 하나 이상의 "소비자" 스레드가 문자를 읽는 버퍼 처리를 예시로 들고있는데, 한 '생산자'스레드는 해당 list(waiters)가 비었으면 buffer를 계속 쌓고, '소비자' 스레드는 버퍼가 list(waiters)에 쌓이면 buffer를 비어내도록 하는 방법이다.

struct condition
{
	struct list waiters; /* List of waiting threads. */
};

struct condtion을 보면 해당 list를 선언하도록 되어있다. 기존 코드에서는 대기 스레드의 semaphore_elem이 waiters 리스트에 뒤쪽에 추가되는 방식이다. 이를 우선순위로 정렬된 위치에 삽입되도록 변경하자. 그리고 대기 스레드의 semaphore_elem에 스레드의 우선순위를 저장하도록 추가하자.

우리팀 수정 코드 🤓

//thread/synch.c

void cond_wait(struct condition *cond, struct lock *lock)
{
	struct semaphore_elem waiter;

	ASSERT(cond != NULL);
	ASSERT(lock != NULL);
	ASSERT(!intr_context());
	ASSERT(lock_held_by_current_thread(lock));

	sema_init(&waiter.semaphore, 0);

	list_insert_ordered(&cond->waiters, &waiter.elem, &sem_priority_less, NULL);
	lock_release(lock);
	sema_down(&waiter.semaphore);
	lock_acquire(lock);
}

기존 코드에서는 대기 스레드들이 순서대로 waiters 리스트에 추가되고 깨어난다.
수정한 코드에서는 대기 스레드들이 우선순위 순으로 정렬된 위치에 삽입되고 깨어난다. 또한 대기 스레드의 우선순위를 저장하여 정렬 기준으로 활용된다.

---

cond_signal()을 수정하자.

아래는 cond_signal()의 기본코드다.

//threads/synch.c

/* If any threads are waiting on COND (protected by LOCK), then
   this function signals one of them to wake up from its wait.
   LOCK must be held before calling this function.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to signal a condition variable within an
   interrupt handler. */
void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	if (!list_empty (&cond->waiters))
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
}

cond_signal 함수는 조건 변수 cond와 락 lock을 인자로 받아와서 사용하고, 대기 중인 스레드 중 하나를 깨운다. 이를 condition variable의waiters list를우선순위로 재정렬 하도록 수정하자.

우리팀 수정 코드 🤓

//threads/synch.c

void cond_signal(struct condition *cond, struct lock *lock UNUSED)
{
    ASSERT(cond != NULL);
    ASSERT(lock != NULL);
    ASSERT(!intr_context());
    ASSERT(lock_held_by_current_thread(lock));

    if (!list_empty(&cond->waiters))
    {

        list_sort(&cond->waiters, sem_priority_less, NULL);
        sema_up(&list_entry(list_pop_front(&cond->waiters),
                            struct semaphore_elem, elem)
                     ->semaphore);
    }
}

sema_up()을 하기 전 list_sort 함수를 사용하여 waiters 리스트를 sem_priority_less 비교 함수를 기준으로 정렬하도록 하자. sem_priority_less()는 아직 구현을 안해줬지만 이전에 priority_less()함수와 구조가 비슷했다.

---

sema_cmp_priority()함수를 구현해보자.

//include/threads/synch.h
bool sem_priority_less(const struct list_elem *a, const struct list_elem *b, void *aux);


//threads/synch.c

bool sem_priority_less(const struct list_elem *a, const struct list_elem *b, void *aux){
	struct semaphore_elem *sa = list_entry(a, struct semaphore_elem, elem);
	struct semaphore_elem *sb = list_entry(b, struct semaphore_elem, elem);

	struct thread *thread_a = list_entry(list_begin(&sa->semaphore.waiters), struct thread, elem);
	struct thread *thread_b = list_entry(list_begin(&sb->semaphore.waiters), struct thread, elem);

	return thread_a->priority > thread_b->priority;
}

sem_priority_less() 인자로 들어오는 는 두 개의 semaphore_elem 구조체를 list_entry()함수를 타고 올라가 thread 구조체 안에 있는 priority값으로 비교하여 우선순위 순서를 결정하는 비교 함수다.
이러한 방식으로 sem_priority_less 함수는 waiters 리스트에서 semaphore_elem을 우선순위에 따라 정렬하는 데 사용된다.

---

길고도 긴 synch 내용정리가 끝났다. 여기까지 정상적으로 구현이 되었다면 다음과 같은 14개의 fail을 볼 수 있다. 😮‍💨