[OS] 동기화 관련 문제들

1. 우선순위 역전

• Priority inversion
  • 스레드의 동기화로 인해 높은 순위의 스레드가 낮은 스레드보다 늦게 스케줄링되는 현상
  • 우선순위를 기반으로 스케줄링하는 실시간 시스템에서 스레드 동기화로 인해 발생
• 실시간 시스템의 근본이 붕괴된다는 점에서 큰 문제
  • 높은 순위의 쓰레드가 늦게 실행되면 심각한 문제 발생 가능
  • 낮은 순위의 스레드가 길어지면 더욱 더 심각한 문제 발생
    • 보통 높은 우선순위의 작업이 더 중요한 경우가 많기에…

1.1. 예제

• 3가지 가정
  1. 3개의 스레드
     • T3 : 높은 순위의 스레드
     • T2 : 중간 순위의 스레드
     • T1 : 낮은 순위의 스레드
  2. T1과 T3가 공유 변수 사용
     • 세마포로 동기화
  3. T2는 공유 변수 사용하지 않음
• 상황 발생
  1. T1이 먼저 도착, P 연산 후 자원 할당
  2. 그 다음 T3 도착, T1 중단시키고 T3 실행, T3는 P 연산 내에서 잠듦
  3. T1 다시 실행
  4. T2 도착, T2는 T1보다 순위가 높고 공유 변수 사용하지 않기 때문에 실행 → 우선순위 역전 발생!
  5. T2 종료 후 T1 실행
  6. T1의 V 연산 후 T3 실행

1.2. 해결책

• 우선순위 올림(priority ceiling)
  • 스레드가 공유 자원을 소유하게 될 때, 스레드의 우선순위를 미리 정해진 높은 우선순위로 일시적으로 올림
  • 선점되지 않고 빨리 실행되도록 유도
• 우선순위 상속(priority inheritance)
  • 낮은 순위의 스레드가 공유 자원을 가지고 있는 동안,
  • 높은 순위의 스레드가 공유 자원을 요청하면,
  • 공유 자원을 가진 스레드의 우선순위를 요청한 스레드보다 높게 설정하여 빨리 실행시킴

2. 생산자-소비자 문제

• Producer-consumer problem
  • 공유버퍼를 사이에 두고, 공유버퍼에 데이터를 공급하는 생산자들과 데이터 읽고 소비하 는 소비자들이 공유버퍼를 문제 없이 사용하도록 생산자와 소비자를 동기화시키는 문제
• 코드 및 실행 순서에 따른 결과
  • 생산자는 수를 증가시켜가며 물건을 채우고 소비자는 생산자를 쫓아가며 물건을 소비
  • 생산자 코드와 소비자 코드가 동시에 실행되면 문제가 발생
  • ⇒ 그냥 if(buf_cnt == 0) 로 하면 안되는 이유

생산자 소비자 문제

실행순서에 따른 결과 차이

2.1. 아주 자주 발생하는 문제

• 키보드 입력도 생산자-소비자 관계임
  • 가끔씩 입력이 씹히는 것이 곧 생산자-소비자 문제

생산자-소비자 문제 예

2.2. 생산자-소비자에서 고려해야할 3가지 문제점

• 상호 배제 해결
  • 생산자들과 소비자들의 공유 버퍼에 대한 상호 배제
• 비어 있는 공유 버퍼 문제
  • 비어 있는 공유버퍼를 소비자가 읽으면 안된다!
• 꽉 찬 공유버퍼 문제
  • 꽉 찬 공유버퍼에 생산자가 더 이상 데이터를 입력하면 안된다!

(< 이미지삽입필요 >)

2.3. 해결법: 세마포어 2개 이용

• 세마포어1. 읽기용 세마포어: 비어있는 버퍼 문제 해결(읽기 가능한 버퍼 개수 확인)
• 세마포어2. 쓰기용 세마포어: 비어있는 버퍼 문제 해결 (쓰기 가능한 버퍼 갯수 확인)

알고리즘

• R : 버퍼에 읽기 가능한 버퍼의 개수. 0이면(비어있는 경우) 대기
• W : 버퍼에 있는 쓰기 가능한 버퍼의 개수. 0이면(꽉 차있는 경우) 대기
• M : 뮤텍스. 생산자 소비자 모두 사용

Consumer { // 소비자 스레드
    while(true) {
        P(R); // 세마포 R에 P/wait 연산을 수행하여
        // 버퍼가 비어 있으면(읽기 가능한 버퍼 수=0) 대기한다.
        /*
            뮤텍스(M)를 잠근다.
            공유버퍼에서 데이터를 읽는다. // 임계구역 코드
            뮤텍스(M)를 연다.
        */
        V(W); // 세마포 W에 대해 V/signal 연산을 수행하여
        // 버퍼가 비기를 기다리는 Producer를 깨움
    }
}

Producer { // 생산자 스레드
    while(true) {
        P(W); // 세마포 W에 P/wait 연산을 수행하여
        // 버퍼가 꽉 차 있으면(쓰기 가능한 버퍼 수=0) 대기
        /*
            뮤텍스(M)를 잠근다.
            공유버퍼에 데이터를 저장한다. // 임계구역 코드
            뮤텍스(M)를 연다.
        */
        V(R); // 세마포 R에 대해 V/signal 연산을 수행하여
              // 버퍼에 데이터가 저장되기를 기다리는 Consumer를 깨움.
    }
}