(WIL) WEEK08 : pintOS Project 01 - 미완

Interrupt 통해서 sleep 상태의 스레드 깨우기

• interrupt
  • 현 프로그램의 실행을 일시적으로 중단시키고 다른 프로그램이나 서브루틴을 시작하게 하는 외부 장치 혹은 내부의 이벤트에 의해 프로세서에 보내지는 신호
  • 인터럽트는 동시성 관리나 현대 컴퓨터 시스템 상에서의 flow of control(실행 흐름 제어)에 있어서 중요한 메커니즘
  • 인터럽트 발생 → 프로세서: 스택으로 향하는 PC와 다른 레지스터를 포함하는 현재 프로그램 상태를 저장 → 프로세서: 메모리 내 인터럽트 핸들러(== ISR, interrupt service routine)가 위치한 곳으로 jump → 인터럽트 핸들러 completes its task → 미리 저장된 인터럽트 발생 프로그램으로 returns back → 인터럽트 발생 위치에서부터 다시 실행(인터럽트 발생한 적이 없던 것처럼 running)
  • 인터럽트는 주로 real-time systems에서 외부 이벤트에 신속 응답하면서, 메인 프로그램 실행의 지연을 방지하는 데에 사용됨
  • 인터럽트 ⇒ 단일 프로세서에서 여러 프로그램을 동시에 실행시키는(동시성 적용) 멀티태스킹 os을 가능하게 함

 

Design of the Priority Scheduling

1. ready list를 검사하고, next thread to run을 선택해야할 때, highest priority의 스레드를 가져옴
2. wait list에서 lock을 기다리는 스레드들이 있고, lock이 available하면, OS가 가장 우선순위가 높은 스레드를 선택

• 우선순위 반전 문제는 운영 체제의 특정 이벤트 시퀀스 때문에 발생합니다.이 문제는 중간 우선순위 작업이 실행 중일 때 낮은 우선순위 작업이 보유한 공유 리소스에 액세스해야 할 때 발생합니다. 중간 우선순위 작업은 우선순위가 낮은 작업을 선점하고 실행을 시작합니다. 그러나 작업을 진행하기 전에 우선순위가 더 높은 작업이 완료되어야 한다는 것을 곧 깨닫게 됩니다. 우선순위가 높은 작업은 낮은 작업이 공유 리소스를 해제할 때까지 기다리면서 차단되지만 중간 우선순위 작업이 현재 프로세서를 잡고 있어 우선순위가 높은 작업이 실행되지 못합니다. 이러한 상황을 우선순위 반전이라고 합니다.
• 요약하면, 우선순위 반전 문제는 중간 우선순위 작업이 더 높은 우선순위 작업에 필요한 공유 리소스를 보유하고 있고, 더 높은 우선순위 작업이 리소스를 기다리는 동안 차단되기 때문에 발생합니다. 한편, 우선순위가 낮은 작업이 중간 우선순위 작업을 선점하고 실행을 시작하면 우선순위가 높은 작업이 실행되지 못하고 우선순위 반전이 발생합니다.
• 여러 작업이 동시에 실행 중인 시스템에서 우선순위가 높은 작업은 우선순위가 낮은 작업에서 현재 사용 중인 공유 리소스에 액세스해야 할 수 있습니다. 그러면 우선순위가 높은 작업은 뮤텍스 또는 세마포어와 같은 동기화 메커니즘을 사용하여 공유 리소스를 획득하려고 시도합니다. 그러나 우선 순위가 높은 작업이 액세스를 요청할 때 우선 순위가 낮은 작업이 여전히 공유 리소스를 사용하고 있는 경우 우선 순위가 높은 작업은 리소스를 획득하기 전에 우선 순위가 낮은 작업이 완료될 때까지 기다려야 합니다.

 

Priority Donation (== Inheritance)

• Priority Inversion을 해결하기 위한 Technique
• the lock holder thread에게 우선순위를 상속해줘라
  • Lock holder thread is A. C requested the lock but A has the lock already.
  • 이 상황에서 C는 그의 우선순위를 A에 상속해줌 → A의 priority가 C와 같은 priority로 boost됨
  • B는 boosted된 A보다 우선순위가 낮은 것으로 판단되고, blocked (preempt될 수 없음)

 

Nested Donation (단계적 Donation)

• Purpose of Nested Donation
  • Nested donation는 시스템 프로그래밍에서 multiple donation 개념의 확장입니다. 우선순위가 낮은 작업이 보유한 리소스를 대기 중인 우선순위가 높은 작업이 다른 우선순위가 낮은 작업에 필요한 리소스를 보유하고 있을 때 발생합니다.
  • 이 시나리오에서 우선순위가 높은 작업은 multiple donation에서와 같이 필요한 리소스를 보유하고 있는 우선순위가 낮은 작업에 자신의 우선순위를 donate할 수 있습니다. 그러나 우선순위가 낮은 작업에도 우선순위가 높은 작업이 보유한 리소스가 필요할 수 있으므로 잠재적인 priority inversion이 발생할 수 있습니다.
  • 이 문제를 해결하기 위해 nested donation를 사용하면 우선순위가 낮은 작업도 우선순위가 높은 작업에 우선순위를 기부하여 우선순위가 낮은 작업에 필요한 리소스를 해제할 수 있을 때까지 일시적으로 우선순위를 올릴 수 있습니다. 이를 통해 시스템은 priority inversion을 방지하는 동시에 공유 리소스를 효율적으로 사용할 수 있습니다.
  • nested inversion는 특히 많은 작업과 공유 리소스가 있는 대규모 시스템에서 복잡하고 관리하기 어려울 수 있습니다. 하지만 특정 상황에서는 priority inversion을 방지하고 시스템 성능을 개선하는 효과적인 방법이 될 수 있습니다.
  

• 그림 과정
  • 3개의 thread, 3개의 lock이 chained lock holding relationships
  • thread 4는 lock에 made a request
  • C → B → A 순으로 donation이 발생하여, t3, t2, t1의 priority가 각각 모두 t4의 priority를 상속받음

 

Multiple Donation

• Purpose of Multiple Donation
  • 컴퓨터 시스템 프로그래밍에서 multiple donation의 목적은 priority inversion을 해결하는 것입니다. 이 문제는 현재 공유 자원을 소유하고 있는 낮은 우선 순위 작업에 의해 높은 우선 순위 작업이 차단되는 경우 발생합니다. 이 경우 높은 우선 순위 작업은 공유 자원이 해제될 때까지 기다려야 합니다.
  • 다중 기부는 이러한 문제를 해결하기 위해 사용됩니다. 높은 우선 순위 작업이 차단된 동안, 낮은 우선 순위 작업이 잠시 높은 우선 순위 작업의 우선 순위를 빌려 받아 임시로 높은 우선 순위를 갖게 됩니다. 이렇게 함으로써, 공유 자원을 사용하는 동안 낮은 우선 순위 작업의 우선 순위를 높게 유지하면서 높은 우선 순위 작업이 실행되도록 할 수 있습니다.
  • 다중 기부를 사용함으로써, 시스템은 자원을 효율적으로 사용할 수 있으면서도 높은 우선 순위 작업이 시간에 적시에 실행되도록 보장할 수 있습니다. 이는 시스템 성능을 향상시키고 deadlock 및 기타 synchronization problem의 위험을 줄일 수 있습니다.
  
• 그림 과정
  • T1이 A, B, C lock을 모두 가지고 있음 → T1의 priority는 각 A, B, C lock에 요청한 thread의 priority와 비교하여 T1의 priority 보다 큰 priority를 상속받음
  • 즉, T1의 본래 priority인 10 → T2의 priority인 12로 변경(상속), T3의 priority인 11은 12보다 작으므로, 변경 X → T4의 priority인 13으로 재 변경
  • T1이 최종 상속 받은 priority의 thread(T4)가 요청한 lock을 unlock(C를 unlock)
  • Lock C allocates T4 → T1의 priority는 12로 돌아감(T4의 priority인 13을 상속 받기 전의 priority)

 

Synchronization

• race condition
  • 동시에 공유 자원에 둘 이상의 스레드 혹은 프로세스가 접근할 때 발생하는 동시성 이슈의 한 유형
  • race conditions는 동시적인 작업의 타이밍과 실행의 순서의 비결정적인 특성으로 인해 발생, 어떤 작업이 먼저 완료될 지 예상하기 어려움
  • synchronization이 이 race condition을 막기 위한 기법 중 하나인데, 공유 자원에 대한 배타적인 접근을 강화함으로써 적용됨
    • 전형적으로 락, 세마포어, 동기화 원시함수(primitives) 등을 이용하여 한 번에 오직 하나의 스레드나 프로세스만 해당 자원에 접근할 수 있도록 함으로써 동기화할 수 있음
  • interrupt에 의해 race conditions가 발생할 수 있음
    • 적절하게 interrupt가 handle되지 않으면, 동시에 여러 interrupt가 발생하고, 여러 이벤트가 서로를 간섭하거나 예상치 못한 결과(오류)가 발생할 수 있음
  • 결국, ‘Concurrency’가 멀티 프로세서나 멀티 스레드 프로그램 실행에 있어 큰 목적 / 프로그램들의 ‘동시성’을 위해, race condition을 방지해야 하고, 이전에 interrupt 핸들링을 잘 할 수 있도록 설계해야 함 / 이를 위해 ‘Synchronization techniques’가 필요함
• 동기화를 위한 기법
  • 공유 자원이나 임계 영역(critical section)에 하나의 스레드만 접근할 수 있도록 보장하는 동기화(synchronization primitive) 방법</aside>
    • 멀티스레드 또는 멀티프로세서 환경에서 공유 자원에 대한 액세스를 제어하는 데 사용되는 low-level abstraction (함수로서 간단한 매커니즘 제공)
    • 원시 함수는 락 자체의 획득 및 해제라고 할 수 있음
    • semaphores, monitor 역시 synchronization primitive
  • <aside> 💡 synchronization primitive ?
  • mutually exclusive한 접근 방식을 제공함으로써 작동 → 한 스레드가 lock을 확보하면, 다른 스레드는 락이 해제될 때까지 차단됨
  • 파일, 데이터 구조 및 기타 시스템 자원과 같은 공유 자원을 보호하는 데 사용</aside><aside> 💡 Can you show the example code of which thread gets and loses the lock in C lang?A scenario where multiple threads compete for a lock:In this code, there are two threads that both execute the increment_counter function. This function increments the counter variable 1,000,000 times, but only one thread can access the variable at a time because of the mutex lock.The output of the program will be the final value of counter, which should be 2,000,000 because each thread increments it 1,000,000 times.
  • The pthread_mutex_lock function is called to get the lock before accessing the counter variable, and pthread_mutex_unlock is called to release the lock after the variable has been updated.
  • #include <stdio.h> #include <pthread.h> int counter = 0; pthread_mutex_t lock; void* increment_counter(void* arg) { int i; for (i = 0; i < 1000000; i++) { pthread_mutex_lock(&lock); // get the lock counter++; pthread_mutex_unlock(&lock); // release the lock } return NULL; } int main() { pthread_t thread1, thread2; pthread_mutex_init(&lock, NULL); pthread_create(&thread1, NULL, increment_counter, NULL); pthread_create(&thread2, NULL, increment_counter, NULL); pthread_join(thread1, NULL); pthread_join(thread2, NULL); pthread_mutex_destroy(&lock); printf("Counter value: %d\\n", counter); return 0; }
  • </aside>
  • 
  • <aside> 💡 ‘Lock’에 대한 직관적인 설명, lock이 정확히 어디에서 발생하는 것인지?
  Semaphores
  • 여러 스레드가 동시에 공유 자원에 접근할 수 있는 동기화 매커니즘(synchronization primitive)
  • Binary Semaphore
    • 가장 간단한 semaphore 유형 / locked (0) & unlocked (1) 두 가지 상태만 가지고 있음
    • 공유 자원에 mutual exclusion을 제공 → 한 번에 하나의 프로세스 또는 스레드만 리소스에 액세스 할 수 있도록 함
    • BS(binary sem)의 값은 0 또는 1
      • 0 ⇒ sem이 잠겨있음을 의미
      • 1 ⇒ sem이 잠금 해제되어 있음을 의미
      • 프로세스 혹은 스레드가 sem을 얻으려 할 때, sem이 0이면(sem이 잠겨 있으면) 사용 가능해질 때까지 blocked
    • BS에서 수행할 수 있는 기본 작업
      • sem_wait() - sem의 값이 0(locked)인 경우 호출하는 프로세스 혹은 스레드는 sem이 해제 될 때까지 차단
      • sem_post() - sem을 해제하여 값을 1로 설정

    #include <stdio.h>
    #include <semaphore.h>
    #include <pthread.h>
    
    sem_t binary_semaphore;
    
    void* thread_function(void* arg) {
        // Semaphore를 기다립니다.
        sem_wait(&binary_semaphore);
        
        // Critical section
        printf("Thread %ld is in the critical section.\\n", (long)arg);
        
        // Semaphore를 해제합니다.
        sem_post(&binary_semaphore);
        
        return NULL;
    }
    
    int main() {
        pthread_t thread1, thread2;
        
        // 값이 1 인 binary semaphore를 초기화합니다.
        sem_init(&binary_semaphore, 0, 1);
        
        // 두 개의 스레드를 생성합니다.
        pthread_create(&thread1, NULL, thread_function, (void*)1);
        pthread_create(&thread2, NULL, thread_function, (void*)2);
        
        // 스레드가 완료될 때까지 기다립니다.
        pthread_join(thread1, NULL);
        pthread_join(thread2, NULL);
        
        // Semaphore를 파괴합니다.
        sem_destroy(&binary_semaphore);
        
        return 0;
    }
    

  • Counting Semaphore
    • binary보다 일반적으로 쓰임, 양의 정수 값을 가짐
    • 동시에 여러 프로세스 혹은 스레드에서 액세스할 수 있는 공유 자원에 대한 액세스를 제어하는 데 사용됨
    • 세마포어 값 == 사용 가능한 자원의 수
      • 프로세스 혹은 스레드가 자원에 액세스하려면 세마포어 값을 감소시키고 (양수인 경우) 작업을 지속 / 세마포어 값이 0이면 프로세스 혹은 스레드는 자원이 사용 가능할 때까지 차단됨
    • CS에서 수행할 수 있는 기본 작업
      • sem_wait() - 세마포어 값이 0이면 호출하는 프로세스 혹은 스레드는 자원이 사용 가능해질 때까지 차단(세마포어 값 증가)
      • sem_post() - 세마포어 값을 증가시켜, 자원이 사용 가능하다는 것을 나타냄
  Monitoring
• Mutex locks ⇒ for mutual exclusion
• Dead lock issue