Peterson & Mutex Lock & Semaphore

이유석·2022년 3월 7일
0

CS - Operating System

목록 보기
10/20

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을 가리킴

profile
https://github.com/yuseogi0218

0개의 댓글