CS/운영체제

[운영체제] 동기화

삶_ 2022. 7. 7. 22:06

 

 

동기와 비동기의 차이

  • 동기 : 동시에 일어남
    • 설계가 간단하고 직관적.
    • 결과가 나올 때 까지 아무것도 못하고 대기해야 하는 단점
  • 비동기 : 동시에 일어나지 않음
    • 동기보다 복잡함
    • 결과가 나올 때 까지 다른 작업을 할 수 있어 효율적

 

 

Race Condition

  • 데이터를 동시에 접근하면서 생기는 문제
    • CPU가 여러개 있는 상황에서 여러 CPU가 운영체제를 건드리게됨 (시스템콜)
    • 사용자 모드에선 괜찮은데, 커널모드 중에 CPU를 빼앗기게 되면 문제 발생
    • 운영체제가 일하는 중인데 인터럽트 처리 요청이 들어옴.
  • 일반적으로 생기는 문제는 아님

 

 

 

 

 

 

 

프로세스 동기화 문제

  • 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다
  • 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘 필요
  • 여러 연산 알고리즘들을 통해 해결한다
  • Critical-Section Problem
    • 이미 작업중인 공유데이터에 접근해서 문제를 일으키는 것들
    •  critical section : 공유데이터
      • 여러개의 프로세스가 수행되는 시스템에서
      • 각 프로세스들이 공유하는 데이터를 변경하는 코드 영역
        1. 오직 한 프로세스만 진입 가능하게
        2. 섹션이 비어있다면, 어느 프로세스가 들어갈 것인지 적절한 선택이 필요
        3. 한번 들어갔다 나온 프로세스는 다음에 들어갈 때 제한을 줌
  • 프로그램적 해결법의 충족 조건
    • Mutual Exclusion (상호 배제)
      • 동시에 공유데이터에 들어가면 안된다
    • Process (진행)
      • 아무도 critical section에 있지 않은 상태에서 들어가고자 하는 프로세스가 있으면
      • critical section에 들어가게 해줘야 한다
    • Bounded Waiting (유한대기)
      • 프로세스가 critical section에 들어가려고 요청한 후부터 
      • 그 요청이 허용될때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다

 

 

Semaphores

  • 추상자료형
  • Process Synchronization 문제를 해결하는 방식들을 추상화시킴
  • semaphores 의 두가지 타입
    • 개수 세마포어 : 0 이상의 더 큰 수를 값으로 할수있음. 값이 여러개 있는 상황
    • 이진 세마포어 : 값을 0 또는 1로만 가질수있는 semaphore. 상호 배타적.
  • 아래의 두가지 atomic 연산에 의해서만 접근 가능
    • P와 V를 번갈아가며 씀 (자원의 획득과 반납) 
    • 둘 사이에 critical section을(공유작업) 넣고 번갈아가면 됨
    • Syncronization Hardware이 Semaphores 를 정의해줌

  • CPU가 계속 P와 V를 번갈아가며 while문을 반복함 (busy-wait)
  • block 상태로 만듬

 

  • Block / Wakeup Implemention
    • 위 문제를 해결하는 법
    • Semaphore를 쓰고있는 프로세스가 V연산을 통해 반환하면 block,wakeup 친구들을 데려옴
    • 만약 semaphore의 값이 음수면 (<0) block() 하고, (이미 프로세스 작업상태)
    • 1 더했는데 음수면 깨어야하기 때문에 wakeup() 을 함
  • Busy-wait 와 Block/Wakeup
    • Busy-wait는 비효율적 (자원이 없을때도 쓰고있으니)
    • Critical section 길이가 긴 경우, Block/Wakeup 이 적당
    • Critical section 길이가 매우 짧은 경우(경쟁이 심할때),
      • Block/Wakeup 오버헤드가 Busy-wait 오버헤드보다 더 커질 수 있음
    • 일반적으로는 Block/Wakeup 방식이 더 좋음

 

 

  • Deadlock and Starvation
    • Deadlock : 둘 이상의 프로세스가 서로 필요한 것들을 하나씩만 갖고있어 기다려야하는 현상

 

 

Synchronization의 문제

  • Bounded-Buffer Problem (Producer-Consumer Problem) : 공유버퍼의 크기가 유한한 버퍼임
    • 생산자 프로세스 : 데이터를 만들어서 빈 버퍼에 집어넣는 역할
    • 소비자 프로세스 : 데이터를 꺼내 빈 버퍼를 만드는 역할
    • 여러 프로세스가 동시에 같은 Producer에 접근하는 문제
      • 다른 프로세스가 들어오기 전 공유 버퍼에 lock을 걸어야 한다

 

  • Readers-Writers Problem
    • 한 프로세스가 DB에 write 중일때 다른 프로세스가 접근하면 안됨
    • read는 동시에 여럿이 해도 됨
    • Shared data : DB자체
      • readcount : 현재 DB에 접근중인 reader 수 (0이면 lock을 풀어줌. 1이되면 lock을 검)
      • readcount도 결국 공유데이터기 떄문에 동시에 접근하는걸 막아야함 (mutex로 막기)
    • Synchronization variables
      • mutex : 공유 변수 readcount 를 접근하는 코드의 동시접근을 막기위해 사용

 

 

  • Dining-Philosophers Problem
    • 대략 의미 : 5명의 철학자가 저녁을 먹는다 (생각하다가-먹다가-생각하다가... 반복) - 서로 충돌할수있음(교착상태)
    • 해결방안 : 4명의 철학자만이 테이블에 동시에 앉고, 젓가락을 두개 모두 집을수있을때만 집을수있게.

 

 

 

 

Monitor

  • Semaphore의 문제점 : 정확성 입증 어려움. 한번의 실수가 모든 시스템에 치명적인 영향을 줌
  • 위 문제점을 해결하고, 동시 수행중인 프로세스 사이에서 안전한 공유를 보장하기 위해 만들어진 것
  • Semaphore와 연산은 비슷하지만, 프로그래머가 체감할 때, Monitor은 알아서 해주기 때문에 훨씬 수월하다
  • 공유데이터에 락을 걸 필요 없고 모니터가 알아서 해줌
    • 모니터 내에선 한번에 하나의 프로세스만 활동 가능 
    • 프로세스가 모니터 안에서 기다릴 수 있게함 (condition variable 사용)
      • wait 함수를 사용 : 다른프로세스가 끝날때까지 잠들게함
      • signal 함수를 사용 : 빈 버퍼가 있는데 잠든 프로세스가 있으면 깨움 (만약 없으면 아무일도 일어나지 않음)

 

 

 

Deadlock

  • 데드락 : 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태 (교착 상태)
  • 데드락의 발생 4가지 조건 (4가지 모두를 만족해야 함)
    • Mutual exclusion (상호 배제) : 한번에 하나의 프로세스만이 자원을 사용할 수 있음
    • Hold and wait : 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유 자원을 놓지 않고 계속 가지고 있음
    • No preemption (빼앗기지않음) : 이미 할당된 자원은 다른 프로세스에 의해 강제로 자원을 빼앗기지 않음
    • Circular wait : 자원을 기다리는 프로세스 간의 사이클이 형성되어야 함 (a는 b를 기다리고 b는 c를 기다리고..)
  • 데드락의 처리 방법
    • Deadlock Prevention : 데드락 발생의 4가지 조건 중 어느 하나가 만족되지 않도록 함
      • ▼비효율적이고 기아현상이 발생할수있음 
        1. 공유자원이 존재해야 함 (Mutual exclusion 무효화)
        2. 프로세스를 실행시키기 위해 필요한 자원을 미리 다 확보해야 동작하는 것 (Hold and wait 무효화)
        3. 이미 다른 프로세스에게 할당된 자원이 선점권이 없을때, 높은 우선순위의 프로세스가 먼저 선점함 (No preemption 무효화)
        4. 모든 자원 유형에 할당 순서를 정해, 정해진 순서대로만 자원 할당 (Circular wait 무효화) (이 방법이 제일 좋음)
    • Deadlock Avoidance : 데드락의 가능성이 없는 경우에만 자원을 할당
      • Circular wait 무효화
      • 평생에 쓸 자원의 양을 아는 전제 하에 할수있음
      • 자원의 상태를 판단하여 할당/미할당 을 판단 (safe state 상태를 찾기 = 데드락에 빠지지 않은 상태)
        • 사용 가능한 자원의 수 : Available
        • 할당된 자원의 수 : Allocation
        • 프로세스가 요구한 최대 자원의 수 : Max
        • 필요한 자원의 수 : Need
      • 여러개의 인스턴스가 있을때 자원 할당하는 법 (Banker's Algorithm)
        • Safety Algorithm : 보통이걸 이용
        • Resource Request Algorithm
    • Deadlock Detection and recovery : 데드락 발생은 허용하되, 그에 대한 detection 루틴을 적용한다
      • Process Termination : 프로세스를 죽임
      • Resource Preemption : 프로세스는 죽이지 않고, 자원만 뺏음
    • Deadlock Ignorance : 데드락을 시스템이 책임지지 않음
      • 데드락이 일어나지 않는다고 생각하고, 아무런 조치도 취하지 않음

 

 

Deadlock Avoidance

 

Deadlock Detection and recovery

 

 

 

 

저작자표시