[운영체제] 프로세스 동기화

모의면접으로 학습하는 CS 스터디
- 운영체제 4주차

병행성(동시성)

• 정의
  • 여러 작업이 실행되는 것처럼 보이는 것
  • 실제로는 하나의 프로세스에서 여러 작업이 번갈아가면서 실행됨
• 특징
  • 싱글코어
  • 싱글코어에서 멀티 스레드를 동작시키는 방식
  • 문맥 교환 발생
    

병렬성

• 정의
  • 여러 프로세서가 동시에 작업을 처리하며 여러 작업이 실제로 동시에 실행됨
• 특징
  • 작업은 독립적. 각각의 프로세서에서 병렬로 처리
  • 멀티코어
  • 동작 방식 : 멀티코어에서 멀티스레드를 동작시키는 방식

프로세스 동기화

• 정의
  • 여러 프로세스가 공유하는 자원의 일관성을 유지하는 것
• 특징
  • 여러 프로세스가 공유자원을 사용하는 상황 발생
  • 경쟁 조건이 발생하면 공유 자원의 신뢰성이 떨어짐
  • 이를 방지하기 위해 프로세스들이 공유자원을 사용할 때 특별한 규칙을 만듦

Critical Section

• 정의
  • 공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역
  • 하드웨어 자원을 사용할 때도 적용되는 개념
    
    
• 임계 구역 문제
  • 생산자-소비자 문제
    • 각 생산자, 소비자 프로세스는 서로 독립적으로 작업함
    • 이 두 프로세스가 동시에 전역 변수에 접근할 경우 문제 발생
      
      
• 임계 구역 문제 해결 조건
  • 상호 배제
    • 한 프로세스가 임계 구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없음
      
      
  • 한정 대기
    • 어떤 프로세스도 무한 대기하지 않아야 함
      
      
  • 진행의 융통성
    • 한 프로세스가 다른 프로세스의 진행을 방해해서는 안됨

Race Condition

• 정의
  • 실행 결과가 조작의 타이밍이나 접근 순서에 의해 결정되는 현상
  • 두 개의 스레드 또는 프로세스가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황
    
    
• 발생하는 경우
  • 커널 코드 실행 중 인터럽트 발생
    • 커널은 서로 다른 프로세스가 공유하기 때문에 문제가 될 수 있음
    • 해결 : 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 함
      
      
  • 프로세스가 시스템 콜을 해 커널모드 진입해서 작업 수행하는 도중 문맥교환 발생
    • 한 프로세스가 데이터를 조작하는 도중 시간이 초과되어 CPU 제어권이 넘어가고 다른 프로세스에서 똑같은 데이터를 조작할 때 문제 발생
    • 해결 : 시간이 초과되어도 CPU 제어권이 넘어가지 않도록 함
      
      
  • 멀티 프로세서에서 공유 메모리 내의 커널 데이터에 접근할 경우
    • 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
    • 해결 : 커널 내부에 있는 공유 데이터에 접근할 때마다 데이터에 대한 lock 설정

Race Condition 해결 방법

• 해결법
  • 세마포어
  • 뮤텍스

Mutual Exclusion

• 정의
  • 하나의 프로세스가 임계 구역에 들어가 있으면 다른 프로세스는 들어갈 수 없음
    
    
• 특징
  • 다중 프로세스들의 공유 리소스 접근을 조율하기 위해 locking, unlocking을 사용
  • 이진 세마포어 같이 초기값을 0,1로 가짐
  • 임계 영역에 들어갈 때 lock을 걸어 다른 프로세스가 접근 못하도록 함

Mutual Exclusion 구현 방법

• 데커 알고리즘
  

  • 작동 방식 - P1입장에서 살펴봄.
    • turn 공유 변수 사용. turn == 현재 차례 프로세스
    • P1은 우선 잠금을 검(lock1=true)
    • P2의 잠금이 걸렸는지 확인(while(lock2=true))
    • 만약 P2도 잠금을 걸었다면 누가 먼저인지 확인(if(turn==2))
      • P1 차례라면 임계구역으로 진입. P2의 차례라면 다음 차례로 이동
    • P1은 잠금을 풀고(lock1=false) P2의 작업이 끝날때까지 기다림(while(turn==2))
    • P2가 작업을 마치면 잠금을 걸고(lock1=true) 임계구역으로 진입
  • 특징
    • 하드웨어 도움 없이 임계구역 문제 해결할 수 있음
    • 구현이 매우 복잡함
    • 임계 구역을 보호하기 위해 복잡한 알고리즘을 구현하는 것은 바람직하지 않음
      
      
      
      

• 피터슨 알고리즘

• 작동 방식

  • turn 공유 변수 사용
  • P1은 임계구역 진입 전 먼저 잠금을 검(lock1=true)
  • turn 2로 설정
  • while(lock2==true && turn==2)문을 실행
  • P2가 잠금을 설정하지 않았거나 설정했더라도 곧바로 turn=1로 바꾸면 P1은 임계구역 진입 가능

• 특징

  • turn 변수
    • 두 프로세스가 동시에 lock을 설정해 임계구역에 못 들어가는 상황을 대비
    • turn을 사용해 다른 프로세스에 양보
  • 데커 알고리즘과 유사하나 상대방에게 진입 기회를 양보함(turn=1같이)
    
    
    
    

• 베이커리 알고리즘
  

  • 특징
    • 준비 상태 큐에서 기다리는 프로세스마다 번호표를 주고 번호표 순으로 프로세서 할당
    • 가장 적은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입
    • 여러 개의 프로세스 혹은 스레드에 대한 처리가 가능

• 세마포어

  • 아래에서 자세히 설명
    
    
    
    

세마포어

• 정의
  • 프로세스가 작업을 마치면 다음 프로세스에게 임계구역을 사용하라는 동기화 신호를 보내는 방식
• 작동방식
  • 프로세스가 임계 구역 진입 전 스위치를 사용중으로 변경
  • 이후 도착한 프로세스는 스위치의 상태 확인
  • 사용중이면 작업 끝날 때까지 기다림
  • 작업이 끝나면 동기화 신호를 보냄
• 코드 세부 내용
  • Semaphore(N) : 사용 가능한 자원의 개수 N
  • P() : 임계 구역 진입 전 사용중 표시
    • 사용 가능한 자원 N-1로 줄어듦
  • V() : 작업 끝난 뒤 사용 끝났음을 표시
    • 사용 가능한 자원 N으로 다시 돌아옴
• 특징
  • 세마포어 큐에 저장되어 있다가 신호를 받으면 임계구역에 진입함
  • 바쁜 대기를 하는 프로세스가 없음
  • 그러나 내부 코드가 실행되는 도중 다른 코드가 실행되면 상호 배제와 한정 대기 조건을 보장하지 못함

뮤텍스 VS 세마포어

• 동기화 대상의 개수
  • 뮤텍스 : 동기화 대상이 한 개일때 사용
  • 세마포어 : 동기화 대상이 여러개일때 사용
    
    
• 자원 소유 가능 여부
  • 뮤텍스 : 자원 소유 가능. 책임 가짐
  • 세마포어 : 자원 소유 불가능
    
    
• 매커니즘 차이
  • 뮤텍스 : Locking 매커니즘으로 locking을 걸은 스레드만이 임계구역 나갈 때 lock 해체 가능
  • 세마포어 : Signaling 매커니즘으로 lock을 걸지 않은 스레드도 signal 이용해 lock 해제 가능
    
    
• 범위의 차이
  • 뮤텍스 : 프로세스 범위
  • 세마포어 : 시스템 범위
    

모니터

• 정의
  • 임계 구역을 내부적으로 숨기고 임계 구역에 접근하기 위한 인터페이스만을 제공
  • 자원을 보호. 프로세스 간에 동기화
    
    
• 작동 방식
  • 프로세스는 모니터를 통해 작업 요청
  • 모니터 큐에 요청 작업을 저장한 뒤 순서대로 처리
  • 그 결과만 해당 프로세스에게 알려줌
    
    
• 특징
  • 모니터는 상호 배제 보장
  • 모니터 안 데이터는 모니터 내 프로시저를 통해서만 접근 가능
    
    
• 생긴 이유
  • 세마포어를 잘못 사용했을 경우에 발생하는 문제를 방지하기 위함
  • 예시
    
    1. 세마포어를 쓰지 않고 임계구역에 들어간 경우
       
       
    2. P()를 두번 써 프로세스 무한 대기가 발생하는 경우
       
       
    3. V()와 P()를 반대로 써 상호 배제가 적용되지 않은 경우

데드락

• 정의
  • 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴때 무한 대기에 빠지는 상황
  • 교착상태
    
    
• 특징
  • 아사현상과 다르다
    • 아사현상 : 잘못된 정책으로 특정 프로세스 작업이 지연되는 문제
    • 데드락 : 여러 프로세스가 작업을 진행하다보니 발생하는 자연적인 현상
      
      
• 발생하는 경우

  • 시스템 자원 사용

    • 다른 프로세스와 공유할 수 없는 자원(임계구역) 사용 시 발생

  • 잠금

    • 임계구역 문제 해결을 위해 잠금을 구현했다 무한대기가 발생

  • 응용 프로그램

    • 데이터베이스의 경우 일관성을 위해 잠금을 사용
    • 이때 데드락이 발생할 수 있음

데드락 발생 조건

• 네 가지 조건을 동시에 만족해야 교착 상태가 발생
  
  
• 조건의 특징

  • 각 조건이 중요하게 생각하는 특징

    • 자원의 특징 : 상호 배제, 비선점
    • 프로세스의 행위 : 점유대기, 원형대기

  • 상호 배제, 비선점 조건은 임계구역과 관련이 있음

  • 그러나 임계구역이라도 데드락은 발생함

1. 상호배제

   • 한번에 프로세스 하나만 해당 자원을 사용할 수 있음
   • 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야함

2. 점유대기

   • 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 함
   • 다른 프로세스가 필요로 하는 자원 점유하는 동시에 또 다른 자원을 기다리는 상태여야 데드락이 발생하기 때문

3. 비선점

   • 이미 할당된 자원을 강제로 빼앗을 수 없음

4. 원형대기

   • 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 함

• 예시
  

  • 식사하는 철학자 문제

    • 상호배제
      • 포크는 한 사람이 사용하면 다른 사람이 사용할 수 없는 배타적 자원
    • 비선점
      • 옆사람의 포크를 빼앗을 수 없다
    • 점유대기
      • 한 철학자가 두 자원을 모두 점유하거나 모두 기다리는 상태라면 데드락은 발생하지 않음
      • 선후 관계를 만드는 것이기 때문
      • 한 프로세스가 자원을 점유한 상태에서 다른 프로세스 자원을 기다리면 진행을 방해하는 것이므로 데드락 발생
    • 원형대기
      • 원형 식탁에서 식사하는 것은 선후 관계를 결정할 수 없어 문제가 계속 맨돎

데드락 해결 방법

• 해결법 분류

  • 데드락 예방
  • 데드락 회피
  • 데드락 검출
    
    

• 데드락 예방

  • 데드락을 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식
  • 하나라도 막으면 데드락은 발생하지 않음
  • 단점 : 시스템 처리량과 효율성을 떨어뜨림
  • 예방 종류
    • 상호 배제 예방
      • 시스템 내 상호 배타적인 모든 자원을 없애버리는 방법
      • 시스템 내 모든 자원을 공유할 수 있음
      • 단점
        • 현실적으로 모든 자원을 공유할 수 없음
          
          
    • 비선점 예방
      • 모든 자원을 빼앗을 수 있도록 만드는 방법
      • 단점
        • 우선순위로 빼앗으면 아사현상 발생할 수 있음
        • 에이징 방법이 있지만 이는 다시 비선점 자원으로 만들어 데드락 발생
          
          
    • 점유대기 예방
      • 프로세스가 사용하려는 모든 자원을 한꺼번에 점유하거나 모두 반납하는 방식
      • 프로세스 자원 사용방식을 바꿔 데드락을 해결한단 점에서 의미가 있음
      • 단점
        • 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
        • 자원의 활용성이 떨어짐
        • 많은 자원을 사용하는 프로세스가 불리함
        • 일괄 작업 방식으로 동작됨
          
          
    • 원형대기 예방
      • 점유대기를 하는 프로세스들이 원형을 이루지 못하도록 하는 방법
      • 자원을 한방향으로만 사용하도록 설정
      • 점유대기 예방보단 완화된 방법
      • 단점
        • 프로세스 작업 진행에 유연성이 떨어짐
          
          

• 데드락 회피
  

  • 자원 할당량을 조절해 데드락을 해결하는 방식

  • 자원을 할당하다 데드락 유발 가능성이 있으면 자원 할당 중단

  • 단점

    • 얼만큼 할당해야 데드락이 발생하지 않는다는 보장이 없어 실효성 적음
    • 자신이 사용할 모든 자원을 미리 선언해야함
    • 시스템 전체 자원 수가 고정적이어야 함
    • 자원 낭비

  • 안정상태 VS 불안정상태

    • 안정상태 : 프로세스들이 자원 요청했을 때 데드락 발생하지 않고 모두에게 할당할 수 있는 상태
    • 불안정상태 : 데드락 발생 가능성이 있는 상태

  • 구현 방법 : 은행원 알고리즘

    • 사용하는 변수

      변수	설명
      전체 자원	시스템 내 전체 자원의 수
      가용 자원	시스템 내 현재 사용할 수 있는 자원의 수
      	가용자원 = 전체자원-모든 프로세스 할당 자원
      최대 자원	각 프로세스가 선언한 최대 자원의 수
      할당 자원	각 프로세스에 현재 할당된 자원의 수
      기대 자원	각 프로세스가 앞으로 사용할 자원의 수

    • 안정 상태 => 기대자원 <=가용자원

    
    

• 데드락 검출과 회복

  • 자원 할당 그래프를 모니터링하며 데드락이 발생하는지 살펴보는 방식

  • 데드락 발생 시 데드락 회복 단계 진행

  • 데드락 검출 방법

    • 가벼운 데드락 검출
      • 타임아웃 : 일정 시간 동안 작업이 진행되지 않는 프로세스를 처리하는 방법
      • 단점
        • 엉뚱한 프로세스가 강제 종료될 수 있음
        • 모든 시스템에 적용할 수 없음
    • 무거운 데드락 검출
      • 자원 할당 그래프 이용
      • 장점
        • 프로세스 작업 방신을 제한하지 않고 데드락을 검출할 수 있음
      • 단점
        • 자원 할당 그래프를 유지하는 과정에서 오버헤드 발생

  • 데드락 회복 방법

    • 데드락 일으킨 모든 프로세스 동시 종료
      • 다시 실행할 때 어떤 프로세스를 먼저 실행할 것인지 기준을 정해야함
    • 데드락 일으킨 프로세스 중 하나를 골라 순서대로 종료
      • 프로세스 종료 순서를 정하는 기준이 필요함