Peterson & Mutex Lock & Semaphore

Peterson (피터슨) 알고리즘

정의

• 2 프로세스의 동기화 문제에 대한 해결책
• 현재 컴퓨터 구조에 대해서는 동작하지 않지만, 좋은 구조를 가지고 있다.

용어

• load, store : 해당 지시어들은 atomic 이다. (can not be interrupted)
• 두 프로세스들이 공유하는 변수 들
  • int turn : critical section에 들어갈 차례의 프로세스를 가리킴
  • boolean flag[2] : 해당 인덱스의 값이 true일 경우에, critical section에 들어갈 준비가 되었음을 표시

알고리즘

• critical section 의 3가지 요구사항 충족 확인
  • Mutual Exlusive : turn은 i or j 이기 때문에, 두 while 문이 동시에 실행 될 수 없음
  • Progress
    • Pi & Pj in entry(while문)
      - turn에 따라서 하나의 프로세스만 critical section에 진입 가능
    • Pi in entry(while문), Pj in remainder
      - flag[j] = false이므로, Pi while문 벗어남
  • Bounded Waiting
    • Pi & Pj in entry(while문)
      - turn에 따라서 하나의 프로세스만 critical section에 진입 가능

한계점

• 성능 향상을 위해, 프로세서들 and/or 컴파일러들은 운영(코드의 순서)를 재정렬 한다.

• Single Thread : 재정렬 전/후의 결과가 같음
• Multi Thread : 재졍렬 전/후의 결과가 불일치 or 예상치 못한 결과 반환

Mutex Lock (뮤텍스 락) 알고리즘

정의

• Mutual Exlusion Lock의 줄임말

용어

• acquire() : critical section에 진입할 때, available을 false로 변경하여 다른 프로세스들이 critical section에 진입하지 못하도록 한다.
• release() : critical section을 벗어날 때, available을 true로 변경하여 다른 대기중인 프로세스들이 critical section에 진입하도록 한다.

• Busy Wait 필요 : critical section에 진입하고자 할때, 대기하는 동안 CPU자원을 낭비한다.

알고리즘

• Acquire
  
• Release
  

Semaphore(세마포어)

정의

• Mutex Lock보다 더 정교한 방식을 제공하는 동기화 도구

용어

• Semaphore, S
  • 정수 및 공유 변수
  • 두개의 atomic 연산 (wait() & signal())에 의해서만 접근 가능
• Wait()
  • Critical Section내에 다른 프로세스들이 없을때까지 해당 프로세스는 대기한다.
    
• Signal()
  • 프로세스가 Critical Section을 탈출할 때, Signal()호출하여 다른 프로세스들이 Critical Section에 진입하도록 함
    

종류

• Counting Semaphore : 변수 S는 어떤 정수도 가능하다.
• Binary Semaphore : 변수 S는 0 or 1 만 가능 - Mutex Lock 과 동일하다.

Busy Waiting 으로 구현된 Semaphore의 한계

• 2개의 프로세스들이 동시에 동일한 Semaphore에 대하여 Wait()와 Signal()을 수행하면 안된다.
• 즉, Wait()와 Signal()이 Critical Section의 내부에 있으면 된다.
• 하지만, 많은 application들은 다른 프로세스들과 공유 불가능한 자원을 사용하는 Critical Section에서 최대한 많은 시간을 유지하고 싶다.
• 이렇게 되면, Busy Waiting 시간이 길어지고 좋지 못한 해결책이 된다.

Busy Waiting 이 없는 Semaphore

• 각 Semaphore은 대기 queue와 협력한다. (1:1 대응)
• 대기 queue 구성 요소
  • value (of type integer)
  • pointer : 대기 queue의 다음 item을 가리킴