동기화

동기화(Synchronization)

* 프로세스와 쓰레드 모두 해당되는 문서입니다. 편의를 위해 프로세스로 작성하였습니다

동기화(synchronization)

• 병행 프로세스들이 서로 데이터를 주고 받으면서 수행 될 때, 이 프로세스들 간의 동기화가 필요하다
• 병행 프로세스들이 공유 데이터에 접근할 때, 병행 접근하면 데이터의 일관성(data consistency)이 잘못될 수 있다
• 데이터의 일관성을 유지하려면 데이터 접근을 순서화 해야한다.

---

임계 구역(Critical Section)

• 각 프로세스는 공유 데이터를 접근하는 코드 세그먼트를 갖고 있는데 이것을 임계 구역 이라고 함

  임계 구역 문제

• 임계 구역의 수행을 순서화 해서 수행하자

• 오직 한 프로세스 만이 임계 구역을 수행하게 하자

  문제 해결

• 각 프로세스는 임계 구역을 수행하기 전에 허가를 요청해서 승인받고, 임계 구역을 마친후에는 이를 알려준다.

• 진입 구역(entry section) : 임계 구역 수행 전에 허가를 요청하는 코드 구역

• 출구 구역(exit section) : 임계 구역 다음에 위치하여 임계 구역 수행을 끝낸다는 것을 알리는 코드 구역

임계 구역 문제를 해결하기 위한 조건

• 상호 배제(Mutual Exclusion) : 프로세스 P가 임계 구역에서 실행된다면, 다른 프로세스들은 임계 구역에서 실행될 수 없다
• 진행(Progress) : 임계 구역에서 실행되는 프로세스가 없고 임계 구역을 수행하려는 프로세스들이 있다면, 임계 구역을 수행할 다음 프로세스의 선택은 잔류 구역에 있지 않은 프로세스들 중에서 선택하되 무한하게 연기되지 않는다.
• 한계 대기(Bounded Watiting) : 프로세스가 임계 구역의 수행에 대한 요청을 하고 요청이 허용될 때까지 다른 프로세스가 임계 구역을 수행하도록 허용하는 횟수에 한계를 두어야 한다

---

임계 구역 문제의 해결 방법

피터슨(Peterson) 알고리즘

• 오직 두 프로세스만을 가정한다
• 두 프로세스는 다음 두 변수를 공유한다
  • int turn : 임계 구역에 어떤 프로세스가 들어갈 지를 나타냄
  • boolean flag[2] : 프로세스가 임계 구역에 들어갈 준비가 되었는 지를 나타냄. flag[i] == true이면 준비가 된 상태

---

세마포어(Semaphore)

• 공유된 자원의 데이터를 여러 프로세스, 스레드가 접근하는 것을 막는 것

• 세마포어 s : 정수 변수로서 오직 두 개의 연산으로만 접근 가능함

  • wait(s) or P(s) : 임계 구역에 들어가기 전에 수행하는 연산
  • signal(s) or V(s) : 임계 구역에서 나올 때 수행하는 연산

• 이 두 연산에서 세마포어 변수의 접근은 원자적으로 수행됨(접근 도중 인터럽트 되지 않음)

• 현재 수행중인 프로세스가 아닌 다른 프로세스가 세마포어를 해제할 수 있다

세마포어의 종류

• Binary Semaphore : 오직 0과 1값을 사용
  • 세마포어의 초기값을 1로 한다
  • mutex locks 이라고도 알려져 있다
• Counting Semaphore : 제약이 없는 정수 값을 사용
  • N개 프로세스의 병행 접근을 허용하고자 할 때
  • 세마포어의 초기값을 N으로 함

세마포어의 문제점

• 교착상태가 발생할 수 있다
  • 두 개 이상의 프로세스들이 다른 프로세스가 해주어야 하는 사건을 무한하게 기다리는 현상

---

뮤텍스 락(Mutual Exclusion Lock)

• Binary Semaphore
• 뮤텍스 객체는 두 프로세스가 동시에 사용할 수 없다
• 락(lock)을 획득한 프로세스만이 락을 해제할 수 있다

세마포어 vs 뮤텍스

• 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다
• 세마포어는 파일 시스템 상 파일형태로 존재, 뮤텍스는 프로세스 범위입니다
• 세마포어는 소유할 수 없는 반면, 뮤텍스는 소유할 수 있습니다
• 세마포어의 경우, 세마포어를 소유하고 있지 않은 쓰레드도 세마포어를 해제할 수 있지만, 뮤텍스는 락을 소유한 쓰레드만 락을 해제할 수 있습니다

---

모니터(Monitor)

• 동기화를 자동적으로 제공하기 위하여 새로운 언어 구조를 개발
• 여러 프로세스들이 추상 데이터 타입(abstract data type)을 안전하고 효과적으로 공유할 수 있도록 한 기법
• 한번에 한 프로세스만이 모니터 안에서 수행될 수 있다
• 프로그래머가 직접 동기화 제약을 코딩할 필요가 없다

모니터의 구성

• 공유 자원 + 공유 함수로 구성됨
• 2개의 queue 운영
  • 배타동기(Mutual exclusion queue)
  • 조건동기(Conditional synchronization)

모니터의 운영

• 공유 자원 접근 함수에는 최대 1개의 프로세스만이 진입가능 : 나머지는 큐에서 진입못하고 기다리고 있어야 한다
• 진입 프로세스가 조건 동기로 블록되면 새 프로세스 진입 가능
• 새 프로세스는 조건 동기로 블록된 프로세스를 깨울 수 있다
• 깨워진 프로세스는 현재 프로세스가 나가면 재진입 할 수 있다

---

참고

• 동기화의 또다른 도구, 모니터(Monitors)

• [System Software & Security Lab @ Myongji Univ. - Operating System ppt]