[OS] Operating System - Synchronization Tools(1)

배경지식

 

• 프로세스끼리의 협력
  
  • 프로세스가 동작하며 실행이 되는 결과들은 서로에게 직접적으로 영향을 줄 수 있다.
  • 프로세스들은 논리적 주소 공간을 공유하거나, 데이터를 공유할 수 있다. 해당 자원을 공유하면서 프로세스 간의 효율성이 증가하고, 관리의 복잡성도 증가한다.
    • 공유 자원 : 공유 메모리, 파일 시스템, DB, etc..
• 공유된 데이터와 처리된 데이터 간의 데이터 불일치
  • 여러 프로세스가 동시에 공유 데이터에 접근할 때, 데이터 불일치 문제 발생 가능성 존재
  • Ex 
    • 두 프로세스가 동시에 같은 데이터를 수정할 때 하나의 프로세스에 의해 변경된 데이터가 다른 프로세스로 인해 데이터가 변할 수 있다. 
• 데이터 일관성 유지의 중요성
  • 공유 자원을 사용하는 프로세스간의 협력은 질서 있는 실행을 통해서 프로세스 간의 상호작용을 제어하고, 데이터의 일관성을 유지
• Race Condition
  • 여러 프로세스나 스레드가 공유 자원에 동시에 접근할 때, 그 결과가 접근 순서에 따라 달라지는 상황
  • 데이터 일관성 및 정확성을 해칠 수 있으며, 결과 예측이 불확실해짐
  • 특징
    • 동시접근
    • 순서 의존성
    • 데이터 불일치
    • 예측 불가능성
  • 예시
    • 변수 업데이트
    • 파일 시스템 접근
  • 해결 방법
    • 락(Locks) - 기본적인 동기화 매커니즘
      • 하나의 스레드만 특정 자원 혹은 섹션에 접근할 수 있도록 한다
      • 스레드가 공유자원에 접근하기 전에 락을 획득하고, 작업이 완료된 후 락을 해제함
      • 락을 얻지 못한 스레드는 락이 해제될 때까지 대기해야 함
    • 세마포어(Semaphores) - 일반화된 락
      • 한정된 수의 스레드가 동시에 공유자원에 접근 가능
      • 세마포어는 내부적으로 카운터를 유지하며, 스레드가 세마포어를 획득하면 카운터 감소, 해제하하면 카운터 증가
      • 카운터가 0이 되면 다른 스레드들은 자원에 접근 불가
    • 모니터(Monitor) - 고급 동기화 메커니즘
      • 공유 자원과 그 자원에 대한 접근을 제어하는 락 및 조건 변수를 포함하는 객체 or 모듈
      • 모니터 내의  모든 메서드들은 자종적으로 뮤텍스 락(일반적인 락)을 사용하여 공유 자원에 대한 동시 접근 방지
        • 조건 변수 :  스레드가 특정 조건이 충족될 때까지 대기시키는 변수

race condition

Critical Section - 임계 구역

 

Critical Section - 임계 구역

structure of a typical process

 

• 프로세스가 공유 자원에 접근할 때 발생하는 동기화 문제
• 프로세스가 공유 데이터에 접근하고 업데이트하는 코드의 부분을 의미
• 시스템 내의 각 프로세스는 자신만의 임계구역을 가지며, 해당 구역에서 공유 자원에 접근
• 동시 실행 제한
  • 한 프로세스가 자신의 임계구역에서 실행 중일 때, 다른 어떤 프로세스도 자신의 임계구역에서 실행되서는 안됨
  • 공유 자원에 대한 동시 접근 방지 및 데이터 불일치와 race condition을 방지
• 분류
  • 진입 구역 - 임계 구역 진입 전 실행하는 코드 부분, 임계구역 진입을 위한 허가를 요청
    • 다른 프로세스가 임계 구역을 사용하는지 확인 후 진입을 결정 -> 상호 배제를 보장 
  • 임계 구역 - 공유자원에 접근하는 프로세스의 코드 부분
    • 해당 구혁에서 공유 데이터를 읽거나 수정
    • 임계 구역의 코드는 한 번에 하나의 프로세스만 실행해야 함
  • 퇴장 구역 - 임계 구역에서 작업을 마친 후, 프로세스가 이어서 실행하는 코드 부분
    • 다른 프로세스가 임계 구역에 진입할 수 있도록 허가 제공
    • 프로세스가 임계 구역을 떠나고 있음을 시스템에 알리는 역할
  • 나머지 구역 - 임계 구역과 관련이 없는 나머지 코드가 실행되는 부분
    • 일반적인 작업 수행 및 임계 구역이나 상호 배제에 대한 고려 없이 실행
• 해결을 위한 조건
  
  • Mutual Exclusion - 상호 배제
    • 한 프로세스가 자신의 임계 구역에서 실행 중인 경우, 다른 모든 프로세스는 자신의 임계 구역에서 실행 불가
    • 공유 자원이 동시에 여러 프로세스에 의해 변경되는 것을 방지
  • Progress
    • 임계 구역에서 실행 중인 프로세스가 없고, 임계 구역에 진입하기를 원하는 하나 이상의 프로세스가 있는 경우, 임계 구역에 진입할 프로세스는 무기한 연기될 수 없음
    • 시스템이 DeadLock-교착상태에 빠지는 것을 방지
    • 진입하고자 하는 프로세스 사이에서 공정성 보장
  • Bounded Waiting 
    • 한 프로세스가 임계 구역에 진입하려고 요청한 뒤, 요청에 대한 승인 전까지 다른 프로세스가 자신의 임계 구역에 진입할 수 있는 횟수에는 한계가 존재
    • 모든 프로세스가 임계 구역에 공정하게 접근할 수 있도록 조건 설정
      • Starvation - 기아 상태 방지 = 프로세스가 무한히 대기하는 상황 방지
• 해결 방법
  • 단일 코어 환경에서 실행
    • 다중 프로세서 환경에서는 실행 불가
    • 인터럽트를 전체적으로 제한하는 것이 다중 프로세서에서는 효율적이지 않음
  • 비선점형 커널
    • 커널 모드에서 실행 중인 프로세스는 커널 모드를 종료, 블록, 자발적으로 CPU를 양보할 때까지 실행
    • 커널 데이터 구조에 대한 레이스 컨디션으로부터 자유로움 -> 커널 모드에서 실행되는 동안 다른 프로세서 개입 x
  • 선점형 커널
    • 커널 모드에서 실행 중인 프로세스가 선점 
    • 다른 프로세스가 커널 모드에서 실행 중인 프로세스를 중단시키고 CPU 차지
    • 커널 내에서 레이스 컨디션을 관리해야 하기에 설계의 어려움이 존재
    • 시스템의 반응성이 더 좋을 수 있고, 멀티태스킹 환경에서 유리하다는 장점 존재

Peterson’s Solution

 

Peterson’s Solution

• 임계 구역 문제를 해결하기 위한 (전통적인) 설루션
  • 두 프로세스의 동기화 문제를 해결하는 방법 중 하나
  • 진입 구역(Entry Section)에서 다른 프로세스의 임계 구역 접근을 확인하고, 자신의 임계 구역에 진입하기 전에 대기
  • 현대 컴퓨터에서는 기본적인 기계어 명령어(Load / Store)의 실행을 보장하지 않기에, 해당 알고리즘이 항상 정확하게 동작한다는 보장이 없음 
    • 명령어의 실행 순서가 프로세스에 따라 다를 수 있음

int turn; // 들어갈 수 있는 프로세스를 나타내는 변수
boolean flag[2]; // 들어갈 준비 상태를 나타내는 변수

while (true) {
    
    flagli] = true; // 임계 구역 진입 전 -> 프로세스 i가 임계 구역에 진입하고자 함을 표현
    
    turn = j； // 다른 프로세스 j에게 임계 구역에 진입할 차례를 주어, 상호 배제를 보장
    
    while (flag[j] && turn == j); // 임계 구역에 진입할 수 있을 때까지 대기
    
    /* critical section = 해당 부분에서 프로세스 i는 공유자원을 사용 */ 
    
    flagli] = false; // 임계 구역 탈출 // 프로세스 i가 임계 구역에서 떠났음을 표현
    
    /*remainder section = 관련이 없는 나머지 작업 수행*/
    
｝

 

• Dekker's Algorithm
  • 두 개의 프로세스를 위한 알고리즘
• Eisenberg and McGuire's Algorithm
  • 프로세스들에 대한 대기 횟수의 하한선을 가지는 알고리즘

 

Hardware Support for Synchronization

 

Hardware Support for Synchronization

 

• 소프트웨어 기반 동기화 메커니즘의 한계 극복
• 임계 구역 문제를 해결하기 위한 하드웨어 지원을 제공
  • 하드웨어 명령어들은 직접적인 동기화 도구로 사용 및 추상적인 매커니즘의 기반으로 사용
• Memory Barriers / Fences
  • 메모리 연산의 순서를 제어하며 프로세스 간의 일관성을 보장하는 명령어
• 하드웨어 명령어
  • 특정 하드웨어 수준의 명령어는 동기화를 위해 직접 사용될 수 있음
  • 높은 레벨의 동기화 메커니즘을 구현하는데 기반
• Atomic Variable
  • Atomicity - 원자성
    • 특정 연산이 중단 불가능한 아주 작은 단위로 수행되는 것을 의미
    • 다중 프로세스 또는 스레드 환경에서 동기화와 데이터 일관성을 유지하는데 필수 요소
  • 데이터의 최소단위의 읽기와 쓰기를 보장하는 변수
  • 원자적 연산 수행 및 레이스 컨디션에 취약한 단일 변수 상황에서 상호 배제 보장
  •  복잡한 동기화 메커니즘 없이도 데이터 일관성 및 무결성 보장 가능
    • 멀티스레딩 프로그래밍에서의 신뢰성 확보 가능