동기화 툴(프로세스 동기화)

운영체제 관련 글 순서

- 프로세스란
- 쓰레드
- CPU 스케줄링
- 동기화 툴
- 동시성 제어 예제
- 데드락
- 주 메모리
- 페이징과 스와핑
- 가상 메모리와 디맨드 페이징
- 페이지 교체 알고리즘(FIFO, OPT, LRU), 쓰레싱, working set

 

 

 

 

Cooperating processes(협력 프로세스)

 

서로 다른 프로세스가 데이터를 공유하는 것.

 

(≠그렇지 않고 서로에게 영향이 없을 경우 independent)

 

 

협력 프로세스는 데이터를 주고 받기 위해 IPC를 요구한다.

 

(IPC[Inter-Process Communication] : 프로세스간 통신 )

 

 

 

이런 프로세스들간의 통신이 일어나다보면 문제가 생길 수가 있음!

 

 

 

 

경쟁상태(Race Condition)

 

: 공유 자원에 대해서 서로 다른 프로세스가 동시에 접근하여 결과값에 영향을 줄 수 있는 상태를 뜻 함.

어떤 순서에따라 엑세스가 일어나냐에따라 결과값이 달라진다.

• concurrent execution(병행 수행)
  • 1개의 core에서 두개 이상의 프로세스가 수행될 때
• Parallel execution(병렬 수행)
  • 서로 다른 core에서 두개 이상의 프로세스가 수행될 때

 

경쟁상태가 발생하는 경우

1. 커널 작업을 수행하는 중에 인터럽트 발생
   • 문제점 : 커널모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우
   • 해결법 : 커널모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.
2. 프로세스가 'System Call'을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환이 발생할 때
   • 문제점 : 프로세스1이 커널모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우 ( 프로세스2가 작업에 반영되지 않음 )
   • 해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함
3. 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때
   • 문제점 : 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
   • 해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법

 

경쟁상태 발생 경우 교글 깃 블로그 참조

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖

 

임계 영역(Critical Section)

 

 

: 둘 이상의 프로세스(쓰레드)가 공유 데이터에 접근하여 작업을 하는 부분의 코드 블록

 

 

임계영역 코드섹션

• entry-section: 임계영역의 시작
• critical-section: 임계영역
• exit-section: 임계역역 끝
• remainder-section: 임계영역이 아닌 일반 코드

 

 

임계영역문제

 

 

동시에 실행할 경우 데이터의에 문제가 생길 수 있음. 한 프로세스가 사용중엔 사용하지 못하도록 막아야함.

 

 

동기화의 필요조건

• 상호 배제
  • 한 프로세스가 사용중일때, 다른 프로세스는 임계영역을 사용할 수 없음
• Progress (Deadlock 해결)
  • 임계영역을 실행하고 있는 프로세스가 없다면 요청하는 프로세스가 임계영역을 실행하도록 함.
  • DeadLock: 아무 프로세스도 임계영역에 진입 못하는 상황
• Bounded Waiting (기아현상 해결)
  • 임계영역 진입 요청부터 진입까지 일정 시간 이상 기다리지 않게 함.
  • 기아현상: 프로세스가 무한대기하는 현상

 

 

임계영역의 소프트웨어 해결

• Dekker's Algorithm
  • flag와 turn을 사용하여 프로세스가 두 개인 상황을 해결
• Eisenberg and McGuire's Algorishm
• Bakery Algorithm
• Peterson's Algorithm
  • 두개의 프로세스로 임계영역과 리마인더 영역에서 반복하는것.
  • 이론적으론 필요조건을 다 만족하지만, 데이터의 정합성이 이뤄지진 않음.
  • 기계어안에서 컨텍스트 스위칭이 일어났을때, 문제가 생김.
  • Shared Data
  •  
  • int turn; boolean[] flag = new boolean[2];​
  • Entry Section
  •  
  • flag[this] = true; turn = another; while(flag[another] && turn == another);​
  • Exit Section

  • flag[this] = false;​

 

 

하드웨어적인 해결

 

• memory barriers or force
• hardware instructions
  • 모두 실행되거나 실행되지 않는 명령어
  • test_and_set()
  •  
  • boolean test_and_set(boolean* target){ boolean rv = *target; *target = true; return rv; }
  • compare_and_swap()

  • int compare_and_swap(int* value, int expected, int new_value){
    	int tmp = *value;
        if(*value == expected)
        	*value = new_value;
        return tmp;
    }

• atomic variables
  • 기계적으로 한 번만에 변경할 수 있는 변수
  • Java의 AtomicBoolean이 있다.

 

 

Higher-Level Software에서의 임계영역 해결방법

• Mutex Lock (Mutual Exclusion Lock)
  • 가장 간단한 동기화 도구. 공유자원에 한 프로세스만 접근 가능.
  • 열쇠를 가지고 있는 프로세스가 들어갈 수 있고 나올땐 키를 반납하는 형태로 진행.
  • Atomical Operation인 acquire()과 release()를 사용
  • Shared Data
    

    AtomicBoolean avaliable;​

  • Atomical Operation

  • void acquire(){
    	while(!available);
    	available = flase; // 키 사용
    }
    
    void release(){
    	available = true; // 키 반납
    }

  • 문제점
    • 무한 루프를 돌며 대기하는 Busy Waiting 문제가 발생하여 CPU를 쓸데없이 사용하게 됨
    • → Multicore 환경에서는 데이터를 점유하고 있던 프로세스가 끝나면 Context Switch없이 바로 진입할 수 있다는 장점이 있음
  • Spin Lock : 무한루프(Busy Waiting)를 돌며 대기하는 방식의 Lock

 

• Semaphore
  • 열쇠가 여러개인 동기화 도구. 공유자원에 여러 프로세스가 접근 가능.
  • 정수값 s에 대해 Atomic Operation wait()와 signal()을 사용
  • s는 자원에 동시에 접근 가능한 프로세스 개수
  • s가 1이면 Mutex Lock과 같음
  • Shared Data 
    
    • Integer s;​
  • Atomical Operation

  • void wait(Integer s){
    	while(s <= 0);
    	s--;
    }
    
    void signal(Integer s){
    	s++;
    }

  • Producer & Consumer 처럼 작업해야하는 순서가 있다면 다음과 같이 동기화 가능
    • 초기화

      • s = 0;​

        
        
        
    • Producer

      • //....
        signal(s);

    • Consumer

      • wait(s);
        //.....

    • Producer가 먼저 작업한 후 Consumer가 작업해야할 때
    • 위와 같이 Producer가 작업한 후에 S를 증가하여 그뒤에 Consumer가 작업하게 함.

 

• Busy Waiting을 해결한 Semaphore
  • Mutex와 마찬가지로 Semaphore도 Busy Waiting 문제가 발생
  • → 무한루프로 기다리지 않고 Waiting Queue에서 대기하도록 하여 문제 해결
  • 한 프로세스가 임계영역에서 나온 경우, Waiting Queue에서 대기 중인 프로세스에 알림을 줘서 ready Queue로 이동
  • Shared Data

  • class Semaphore {
    	int value;
    	List<Process> list;
    }
    
    Semaphore s;

  • Atomical Operation

  • void wait(Semaphore s){
    	s.value--;
    	if(s.value < 0){
    		s.list.add(thisProcess);
    		sleep();
    	}
    }
    
    void signal(Semaphore s){
    	s.value++;
    	if(s.value <= 0){
    		while(s.list.isEmpty()){
    			Process p = s.list.get(0);
    			wakeup(p);
    		}
    	}
    }

  • 문제점
    • 임계영역을 실행하고 있는 프로세스들이 같은 데이터에 접근할 경우 기존의 경쟁상황이 나타남
    • signal()과 wait()의 순서가 잘 지켜지지 않을 경우 초기화한 값보다 많은 프로세스가 데이터에 접근할 수 있음

 

• Monitor
  • Mutex와 Semaphore의 단점을 해결한 동기화 도구
  • 프로그래머의 실수를 줄이기 위해 Monitor와 Condition을 사용하여 동기화
  • Monitor : Shared Data, Operation, Initail Code로 이루어진 추상클래스
  • Condition : Monitor 내에 저장되는 Shared Data의 타입. Condition 별로 wait()와 signal()을 사용
    

    

 

• Java Monitors
  • Java에서 사용하는 스레드 동기화 도구
  • synchronized 와 wait(), notify() 사용
  • synchronized
    • 임계영역 코드 블럭을 명시하는 키워드. 모니터락을 획득한 스레드만 실행 가능

    • synchronized (object){
      	// 임계영역 코드
      }
      
      // or
      
      public synchronized int method(){
      	// 임계영역 코드
      }

      모니터락은 객체 별로 생성됨
  • wait() / notify()
    • notify() : 대기중인 스레드를 하나 깨움
    • notifyAll() : 대기중인 스레드를 모두 꺠움
    • wait() : 모니터락을 획득할 때까지 대기

 

• Liveness
  • 상호배제 뿐 아니라 Progress도 보장해주는 동기화 도구
  • Deadlock과 Priority Inversion 문제가 있다.
  • Deadlock
    • 두 프로세스가 자원을 두고 경쟁하는 상태일 때 순서가 꼬여 두 프로세스 모두 대기만 하게되는 상황
  • Priority Inversion
    • 우선순위가 낮은 프로세스가 자원을 점유하고 있어서, 그 자원이 필요한 높은 우선순위를 가진 프로세스의 순서가 밀리는 현상
    • 해결방법 -> Priority Inheritance : 자원을 점유하는 동안 그 프로세스의 우선순위를 높여주어 일을 빨리 끝내도록 함
      
      • ex) 우선순위 a -> b -> c 일때 c가 자원을 가지고 있으면, 기존대로라면 자원을 가지고 있는 c가 수행하다 우선순위가 높은 b가 수행. a는 c가 자원을 반납하기전까지 대기.
      • b -> c -> a 순으로 우선순위가 가장높은 a가 가장 늦게 실행.
      • Priority Inheritance 해결 : c의 우선순위를 a로 맞추어서 c 를 b보다 빨리 작업한 후 a에게 자원 반환.
      • c -> a -> b 순으로 작업하게 됨.

 

 

참조

주니온님의 인프런 운영체제강의(공룡책)