[운영체제] Implementing Semaphores

단순화된 버전의 세마포어

• wait(s): 임계영역을 진입하기 전 스레드가 호출하는 함수 
  • 세마포어 값을 먼저 감소시키고, 이 값이 0보다 작으면 스레드를 블록한다.
  • 그렇지 않으면 세마포어 값이 0 이상이면 임계영역이 진입한다.
  ⇒ 깃발이 1개 있어야 진입이 가능

• signal(s): 임계영역에서 작업을 마친 스레드가 호출하는 함수
  • 세마포어 값을 먼저 증가시키고 이 값이 0 이상이면 블록된 스레드 중 하나를 깨운다.
  ⇒ 깃발을 1개 늘리고 이 값이 0개 이상이면 블록된 스레드 중 하나를 깨움

Classical 버전의 세마포어

• wait(s)
  • 세마포어 값이 0 이하이면 해당 스레드를 블록하고, 세마포어 값이 양수가 될 때까지 대기한다. 양수가 되면 세마포어 값을 감소시키고(깃발을 가지고) 임계영역에 진입

• signal(s)
  • 블록된 스레드가 있다면, 스레드를 한 개 깨우고 세마포어 값을 증가시킨다.

Busy Waiting을 이용한 구현

• wait(s)
  • 세마포어 값이 0 이하이면 아무것도 수행하지않고 대기하고 세마포어 값을 감소한다.
• signal(s)
  • 세마포어 값을 증가시킨다.
• 평가
  • 세마포어에 대기중인 스레드의 대기열을 지원하지 않음
  • 대기 중인 스레드는 busy waitingㅇ을 수행하며 시간을 낭비함
  • wait(s)와 signal(s) 내부의 코드는 세마포어 값을 변경하는 임계영역이므로, 여러 스레드가 동시에 접근할 때 문제가 발생할 수 있음

이 구현은 세마포어를 단순하게 구현하는 방법 중 하나이지만, 효율성과 안정성 측면에서 좋은 방법이 아님. 대기 중인 스레드의 대기열을 지원하고, busy waiting 대신 대기 중인 스레드를 블록하는 방법을 사용하는 것이 더 효율적인 구현 방법임

Disable interrupts를 이용한 구현

• wait(s)
  • 먼저 인터럽트를 비활성화한다. 즉 다른 스레드가 현재 실행 중인 코드를 중단시키는 인터럽트를 막는다
  • 그 다음 세마포어 값이 0 이하인지 확인하여 busy waiting을 수행. 이는 세마포어 값이 양수가 될 때까지 아무것도 하지 않고 기다림
  • 세마포어 값이 양수가 되면(즉 앞선 스레드가 작업을 마치고 세마포어를 증가한 상황임) 세마포어 값을 감소시킨다(즉 깃발을 가지고 이제 임계영역에 진입).
  • 그 다음 인터럽트를 다시 활성화 함
• signal(s)
  • 인터럽트를 비활성화한다
  • 세마포어 값을 증가시킨다
  • 인터럽트를 다시 활성화 한다.
• 평가
  • 대기 중인 스레드의 대기열을 지원하지 않는다
  • 대기 중인 스레드는 busy waiting을 수행하며 시간을 낭비
  • 멀티프로세스에서 작동하지 않음
  • 다른 응용 프로그램에서 필요한 타이머와 충돌할 수 있음
  • 사용자가 인터럽트를 비활성화할 수 없다면 이 구현은 사용자 코드에서 사용될 수 없음. 인터럽트를 비활성화하면 시스템의 안정성과 신뢰성이 떨어질 수 있기 때문이다.

테스트와 세트 명령어를 이용한 구현

• wait(s)
  • 먼저 락을 사용하여 잠금을 획득한다. 이때 락은 초기값 =0
  • 이후 테스트와 세트 명령어를 사용하여 잠금의 상태를 확인하고 변경
    • 만약 락이 자유로우면 0을 읽고 1로 설정한 후 0을 반환 ⇒ 루프테스트 실패
    • 만약 락이 사용중이면 1을 읽고 1로 설정한 후 1을 반환 ⇒ 루프 테스트 성공
  • 이후 세마포어 값이 양수인지 확인하여 busy waiting 수행
  • 양수가 되면, 세마포어 값 감소하고(깃발을 가지고) 락을 해제
• signal(s)
  • 락을 사용하여 잠금을 획득
  • 이후 테스트와 세트 명령어를 사용하여 잠금의 상태를 확인하고 변경함
    • 락을 해제
• lk라는 락은 초기값으로 0을가짐
• 동작
  • 만약 lk가 자유로우면 (lk=0), 테스트와 세트는
    • 0을 읽고 1로 설정한 후 0을 반환
    • 루프 테스트를 실패하므로 락이 지금 사용 중이지 않음을 의미함
  • 만약 lk가 사용 중이면(lk=1), 테스트와 세트는
    • 1을 읽고, 1로 설정한 후 1을 반환
    • 루프 테스트는 성공하므로 락이 현재 사용중임을 의미함, 이후 락 해제
• Test&set은 원자성 읽기-수정-쓰기(RMW) 명령의 예시임.
  • 테스트와 세트는 메모리에서 값을 읽고 수정한 후 새로운 값을 메모리에 쓰는 RMW 명령어의 한 예이다. 대부분의 CPU 아키텍처에서 테스트와 세트 명령어 사용, 다른 아키텍처에서는 테스트와 교환, 비교와 교환과 같은 유사한 명령어가 사용됨
    • 테스트와 세트: 대부분의 CPU에서 사용되며, 메모리와 레지스터 사이의 값을 스왑
    • 교환: x86에서 사용되며, 메모리와 레지스터 사이의 값을 스왑
    • 비교와 교환: Motorola 68xxx 아키텍처에서 사용되며, 메모리에서 값을 읽은 후, 레지스터와 메모리의 값을 비교하여 일치할 경우 스왑
  • 이러한 명령어를 사용하여 세마포어를 구현할 수 있지만, 이 구현은 여전히 대기 중인 스레드의 대기열을 지원하지 않으며, busy waiting을 수행하여 시간을 낭비, 또한 멀티 프로세서에서 캐시 일관성 문제가 발생할 수 있음.