운영체제(OS) - 6. Process Synchronization

Doyun Geum·2020년 1월 2일
Operating System동기화
3

Operating System

목록 보기
6/9
  • concurrent하게 동작: A라는 process가 동작할 때 인터럽트가 어느 때든 올 수 있고 부분적으로만 수행하고 잠시 멈추게 되는 경우가 있을 수 있다.
    inconsistency가 일어나기에 consistency가 보장될 필요성이 있다.
  • consumer-producer problem
    • 하나는 버퍼를 계속 채우려고, 다른 하나는 비우려고 했을 때(버퍼를 하나씩), 버퍼 counter를 늘리고 줄인다.
    • producer 입장에서 버퍼를 채웠을 때 카운터는 증가해야 하고, consumer 입장에서 버퍼를 비웠을 때 카운터는 감소해야 한다.

Race condition

동시에 여러 개의 프로세스가 동일한 자료를 접근하여 경쟁하는 현상을 말한다.

Critical Section Problem

  • Race condition이 일어나지 않기 위해

    • 이 Section에 있는 code는 무조건 아무런 반응없이 한 번에 수행되어야 한다.
      스케쥴러가 원하는대로 스케쥴링을 해주지는 않지만, 프로그램에서 이 자원만큼은 접근을 막는 즉, 하나의 프로세스가 이 자원을 관리할 때 다른 프로세스들이 접근을 못 하도록 해주는 것을 말한다.
    • entry section: critical section에 들어간다.
    • exit section: critical section에서 나간다.
    • remainder section: critical이 아닌 다른 section을 처리한다.
    • concurrent 환경에서는 예측이 불가능하여 따로 보호가 필요하다. 공유 자원, 외부 장치, 네트워크 통신에서는 특히 critical section이 필요하다.

  • 동기화 문제

    • 공유 자원에 접근하는 concurrent threads가 race condition이 생김
    • 디버그 어려움
    • 스케쥴러 조절을 못하지만 concurrency를 억제시키는 방법이 있다.

Critical Section Problem 해결책

1. Mutual Exclusion: P1이 critical section에서 돌고 있으면 다른 P들은 critical section에서 수행될 수 없다.

2. Progress: critical section에서 수행되고 있는 P가 없을 때, 이곳에서 수행되길 원하는 P들이 존재, 이 중 하나라도 critical section에서 곧바로 수행되도록 보장되어야 한다.(무제한 연기 No !)

3. Bounded Waiting: P 하나가 cs에 들어가길 원하는데 다른 P들이 들어갔다 나왔다를 반복하여 들어가길 원하는 P가 수행되지 못하는 경우가 생길 수 있기에 starvation을 방지하는 것이 필요하다. (A bound must exit)

Peterson’s solution

    // Process i
    do {
    	flag[i] = true:
    	turn = j;
    	while(flag[j] && turn == j);
    		// critical section
    	flag[i] = false;
    		// remainder section
    } while(true);
    // Process j
    do {
    	flag[j] = true:
    	turn = i;
    	while(flag[i] && turn == i);
    		// critical section
    	flag[j] = false;
    		// remainder section
    } while(true);

다음은 프로세스 i와 j 2개가 임계구역에 들어가는 과정이다.

  • 가정: 최종적으로 turn = i 가 되었다.( 프로세스 i가 임계구역에 진입가능)
    → Mutual exclusion 만족
  1. Process i에서 turn == j 부분이 False가 되어 임계구역에 진입한다.
  2. 임계구역에서 수행 후 flag[i] = False로 바꾸어 프로세스 j가 while문을 빠져나와 임계구역에 들어갈 수 있도록 해준다.
    → Progress 만족
  3. 프로세스 j가 임계구역에 진입하여 작업을 수행한다.
  4. 각 프로세스는 처음에 turn을 상대 프로세스의 값으로 바꿔준 후 유지하도록 하여 Bounded waiting을 만족한다.

→ 현대 컴퓨터 구조는 기계어를 수행하기에 올바르게 수행된다는 보장은 없다.

Critical section problem은 공유 자원이 변경되는 동안 interrupt를 발생하지 않도록 하면 해결된다고 생각할 수 있지만, Multiprocessing 환경에서는 불가능하다는 것을 알 수 있다.

이런 환경에서 interrupt를 발생시키지 않으면 메시지가 모든 처리기에 전달되어야 하고 이는 상당한 시간을 소비하고 시스템 효율을 떨어뜨린다. → 현대 기계들은 인터럽트 되지 않는 특별한 Hardware 명령어를 제공하여 이를 간단히 해결한다.

Synchronization Hardware

원자적으로(atomic) 즉, 인터럽트되지 않는 명령어를 사용한다.

  • Atomic 변수 (인터럽트를 못한다는 것을 명시)
  • atomic: atomic구문으로 이루어진 구간은 처음부터 끝까지 preemption이 일어날 수 없다.(방해할 수 없다.)
  • atomic hardware instruction을 구현하는 방법
    • acquire lock, release lock
    • HW 자체에서 test_and_set 명령어를 구현해준다. (atomic)
        boolean test_and_set(boolean *target) {
        	boolean rv = *target;
        	*target = ture;
        	return rv;
        }
        // lock initialization: "false"
        do {
        	while(test_and_set(&lock)); 
        		// critical section
        		lock = false;
        		// remainder section
        } while(true);
1. test_and_set(&lock)은 현재의 lock 값(false)을 리턴한다. 단, lock 값은 true로 바뀌어있음. while문에서 빠져나오지 못하면 계속 true의 값을 가진다.(atomic)
→ **Mutual exclusion 만족**
2. lock의 초기값이 false이기에 처음에 임계구역에 진입한다.
3. 작업이 끝나면 lock을 false로 바꾸어주어 다른 프로세스가 while문을 빠져나올 수 있게 한다.
→ **Progress 만족**
- compare_and_swap 명령어 (atomic)
	
        void compare_and_swap(int *value, int expected, int new_value) {
        	int temp = *value;
        	
        	if(*value == expected) {
        		*value = new_value;
        	}
        	return temp;
        }
        // lock initialization: "0"
        do {
        	while(compare_and_swap(&lock, 0, 1) != 0); 
        		// critical section
        		lock = 0;
        		// remainder section
        } while(true);
1. compare_and_swap(&lock, 0, 1)은 lock의 원래 값을 리턴한다. 단, lock이 0일 때만 1로 변경된다. 처음에 0인 lock의 값이 1로 바뀌어지고 임계구역으로 들어가면 이후 진입하려는 프로세스들은 1만 리턴하기에 while문을 빠져나오지 못한다.
→ **Mutual exclusion 만족** 

2. 임계구역에 진입한 프로세스가 작업을 수행한 뒤 lock을 0으로 바꾼다.

3. 기다리던 프로세스가 while문을 빠져나오면서 임계구역에 진입한다.
→ **Progress 만족**

하지만 위 명령어 모두 Bounded waiting을 아직 만족하지 못한다.
한 프로세스가 lock의 값을 바꾸자마자 다시 진입이 가능하기 때문이다.

  • explicit하게 어떤 프로세스에게 양보를 할지 명시해야 한다.
  • lock은 풀렸으면 들어가서 수행하자라는 식이기에 보장은 못 한다.
  • Bounded-waiting Mutual Exclusion with test_and_set
    • Bounded Waiting을 explicit하게 명시함
    // waiting[], lock initialization "false"
    do {
    	waiting[i] = true;
    	key = true;
    	while(waiting[i] && key) {
    		key = test_and_set(&lock);
    	}
    	waiting[i] = false;
    	// critical section
    	j = (i+1) % n;
    	while((j != n) && !waiting[j]) {
    		j = (j+1) % n;
    	}
    	if(j == i) lock = false;
    	else waiting[j] = false;
    	// remainder section
    } while(true);

waiting 배열과 key라는 불린 변수가 추가되었다.

  1. 처음 false 값을 가지고 있는 waiting[i]와 key는 true로 바뀌고 while문이 수행된다.
  2. test_and_set 명령어를 통해 초기값 false인 lock 값이 false를 반환하고 true로 lock 값을 바꾼다.
  3. 처음에 key는 false 값을 가지게 되고 임계구역에 진입한다. (임계구역에 들어간 프로세스만 waiting 값을 false로 바꾼다. 나머지는 while문에서 true 값이 반복된다.
    → Mutual exclusion 만족
  4. 작업이 끝나면 waiting 배열을 순회하면서 임계구역에 들어갈 프로세스를 찾는다. waiting 값이 true이면(임계구역을 기다리는 프로세스) while문을 빠져나온다.
    → Bounded waiting 만족 (최대 n-1회만 양보하면 임계구역에 진입 가능)
  5. 찾는다면, 그 프로세스의 waiting 값을 false로 바꾸어 임계구역에 들어갈 수 있도록 한다.
    → Progress 만족
  6. waiting 배열 값이 false가 되어 전부 통과되면 j==i 조건문이 수행되어 lock을 false로 변경함으로써(처음 lock의 초기값과 같아짐) 최종 반납하고 모두 임계영역을 벗어나게 된다.

Mutex Locks

Mutual exclusion의 축약형태로 임계구역에 들어가기 전에 lock을 획득하고 빠져 나올 때 lock을 반환한다.

  • acquire(): entry section
  • release(): exit section

불린 변수 available를 통해 락의 가용 여부를 표시한다. 

    acquire() {
    	while(!available); // busy waiting
    	available = false;
    }
    release() {
    	available = true;
    }
  1. available의 초기값이 true로 처음 acquire( ) 함수를 호출하면 available을 false로 변경하고 함수를 빠져나온다.
  2. 빠져나온 프로세스는 임계구역에 진입하고 나머지 프로세스들은 acquire( ) 함수에서 lock이 사용될 수 있기를 기다린다. (while문에서 빠져나오질 못한다.)

→ Busy waiting : 프로세스가 임계구역에 있는 동안 기다리는 다른 프로세스들은 acquire( ) 함수의 반복문을 계속 실행해야 한다.

lock이 사용될 수 있기를 기다리면서 프로세스가 계속 회전을 하고 있어 spinlock이라고도 한다. 이러면 다른 프로세스가 실행되지 못하기에 CPU 사이클 낭비를 초래하며, 위의 명령어 모두 이런 단점을 지니고 있다.

하지만 lock을 기다리는 동안은 context switching을 필요로 하지 않기에(프로세스가 상태가 변경되었다가 다시 돌아오는게 아닌 계속 실행 상태이기에) multiprocessing에서 spinlock이 사용된다.
→ 조금만 기다리면 바로 쓸 수 있다는 점을 이용해서 lock-unlock의 타임이 짧을 때 유용하다.

  1. 작업을 모두 수행하였으면 release( ) 함수를 호출하여 available을 true로 바꾸어 lock을 반환한다. 이제 다른 프로세스가 임계구역에 진입할 수 있게 된다.
  • bounded waiting은 보장이 안된다.
  • 두 opeartion은 atomic하게 일어난다.(OS에서 설계가 그렇게 됨)

Semaphore

  • S라는 정수형 변수, wait( )와 signal( ) 함수로 접근
    S는 동시에 변경할 수 없다. (atomic)
  • Mutex와 다른점은 counting이 가능하다는 것이다. 가용할 수 있는 프로세스들을 동시에 실행시키는게 가능하다.
    wait(S) {
    	while(S <= 0); // busy waiting
    	S--;
    }
    
    signal(S) {
    	S++;
    }
  • Counting semaphore: 몇 개가 접근하고 있는지 셀 수 있다.(0~N)
    • 자원을 사용하려는 프로세스는 wait( )를 호출하여 S를 감소시킨다.
      자원을 방출할 때는 signal( )를 호출하여 S를 증가시킨다.
  • Binary는 0, 1이니 boolean인 Mutex와 같다.
  • 프로세스 작업 순서를 정해줄 수 있게 된다.
    S1; // Process 1
    signal(S);
    
    wait(S);
    S2; // Process 2

S가 0으로 초기화 되어있다면 P1이 S1 작업 이후, S가 1로 증가될 때 비로소 P2가 S2 작업을 수행할 수 있게 된다.

busy waiting 해결하기

프로세스를 대기 큐(wait queue)에 넣고 대기 상태로(waiting) 전환하여 다른 프로세스가 실행되도록 한다. → wait( )

임계구역을 나온 프로세스의 signal( ) 함수 호출에 따라 대기 상태인 프로세스가 준비 큐(ready queue)로 들어가 프로세스를 재시작하여 임계구역에 진입하게 된다.

  • block( )과 wakeup( )을 사용해 이를 해결한다.(링크드 리스트 사용)

    	```java
  typedef struct {
  	int value;
  	struct process *list;
  }semaphore;
  
  void wait(semaphore *S) {
  	S->value--;
  	if(S->value < 0) {
  		// insert process into S->list.
  		block();
  	}
  }
  
  void signal(semaphore *S) {
  	S->value++;
  	if(S->value <= 0) {
  		// delete process from S->list.
  		wakeup(P);
  	}
  }
	```

    block( ) 함수는 자기를 호출한 프로세스를 중지시킨다.

    wakeup(P)은 봉쇄된 프로세스 P를 재시작한다.

    • pooling방식이 아닌 인터럽트 기반 방식으로 구현되며 빈번한 context switching이 발생한다.

    • queue를 만들기 위해 링크드 리스트를 사용

      → 임계구역이 짧으면 busy waiting, 길면 block & wake-up 방식을 사용한다.

Deadlock and Starvation (Semaphore의 문제점)

Deadlock

P0은 P1이 Q를 놔주기를, P1은 P0이 S를 놔주기를 바랄 때를 말한다.
        // P0              // P1
        wait(S);           wait(Q);
        wait(Q);           wait(S);
        ...                ...
        signal(S);         signal(Q);
        signal(Q);         signal(S);

starvation

하나의 프로세스가 오랜기간 선택되지 못하여 실행되지 못 할 때를 말한다.
이는 프로세스가 임계구역을 기다릴 때 대기 큐에 들어가기 때문에 발생한다.

Priority Inversion

셋 이상의 우선순위를 가진 시스템에서만 발생한다.
우선순위가 P0 < P1 < P2이고 P2가 자원 R을 필요로 하고 R은 현재 P0이 사용하고있는 상황이다.

P2는 P0이 자원을 다 사용할 때까지 기다리는게 보통이지만, P1이 P0을 선점한다고 할 때 P2는 상대적으로 낮은 P1이 자월을 양도할 때까지 이를 더 기다려야 한다.

→ Priority-inheritance protocol
더 높은 우선순위 프로세스가 필요로하는 자원을 사용하는 프로세스에게 더 높은 우선순위를 부여한다. 위의 경우 P0이 임시적으로 P2의 우선순위를 상속받아 P1이 선점되는 것을 방지한다. (사용 후 원래의 우선순위로 돌아간다.)

The Bounded-Buffer Problem

  • 총 n개의 버퍼, 각각 한 개의 item을 가질 수 있다.
  • mutex = 1, full = 0(차있는 버퍼의 개수), empty = n(비어 있는 버퍼의 개수)
  • 다양한 방식으로 풀 수 있음(여기서는 semaphore)
  • producer - consumer
    // producer                    //consumer
    do {                             do {
    	// produce an item                
    	wait(empty);                      wait(full);
    	wait(mutex);                      wait(mutex);
    	// add an item to buffer          // remove an item from buffer
    	signal(mutex);                    signal(mutex);
    	signal(full);                     signal(empty);
    } while(true);                      // consume the item
       				     } while(true);

Readers-Writers Problem

  • 하나의 data set에 여러 개의 프로세스들이 동시에 접근하려고 한다.
    • Readers: data set을 오직 읽기만 한다.
    • Writers: data set에 뭔가를 쓴다.
  • Writing은 exclusive, Reading은 여러 명이든 상관없이 냅둔다.
    Problem 1. writer가 기다리고 있는 경우, reader들은 다른 reader를 기다리지 않고 읽기 시작해야 한다.
    → starvation: writer
    Problem 2. writer가 준비가 되어 쓰게되면, reader들이 읽기를 기다리고 있기 때문에 가능한 빨리 써야한다.
    → starvation: reader

Solution for problem 1.

Data set

  • semaphore rw_mutex=1 : writers mutual exclusion을 위해 사용됨
  • semaphore mutex=1 : read_count mutual exclusion을 위해 사용됨
  • int read_count = 0 : 몇 개의 프로세스들이 읽고 있는지
  • First var : reader에게 우선순위
  • Second var : writer에게 우선순위
    // Reader
    do {
    	wait(mutex); // 다른 reader는 여기서 대기
    	read_count++; // mutual exclusion
    	if(read_count == 1) // first reader
    		wait(rw_mutex); // writer가 없다는 것을 확실히 한다
    	signal(mutex); // release critical section
    	// reading is performed.
    	wait(mutex); // 
    	read_count--;
    	if(read_count == 0) // no one is reading, 1이면 아직 읽는 중
    		signal(rw_mutex); // writers 원할 때 접근 가능
    	signal(mutex); // critical section 수행됨
    } while(true);
    ```
	```java
    // Writer
    do {
    	wait(rw_mutex);
    	// writing is performed.
    	signal(rw_mutex);
    } while(true);

read_count가 감소하거나 늘어날 때는 wait(mutex)와 signal(mutex)로 감싸주고 reader가 있을 때는 wait(rw_mutex)로 writer의 접근을 막고 reader가 없을 때 signal(rw_mutex)를 통해 writer의 접근을 허용하게끔 한다.

Dining-Philosophers Problem(synchronization 상식)

5명의 철학자가 원형 테이블에 앉아 있고 테이블 중앙에는 밥이, 테이블에는 5개의 젓가락이 놓여 있다.(쌍이 아닌) 배고픈 철학자가 동시에 젓가락을 2개 집으면, 식사를 마칠 때까지 젓가락을 놓지 않고 식사를 한다.
→ deadlock과 starvation을 발생시키지 않고 여러 스레드에게 자원을 할당해야 할 필요를 표현한 것이다.

  • 5명 모두가 동시에 배고파서 왼쪽 젓가락 잡고 각자 자신의 오른쪽 젓가락 잡게되면 없기에 deadlock & starvation
  • 5개의 semaphore(젓가락)가 상호 의존성을 지니면 deadlock이 생길 수 있다.
  • deadlock handling
    • 4명만 앉아라
    • 동시에 2개를 잡을 수 있는 경우에만 젓가락을 잡아라 → critical section
    • 홀수 먹은 후 짝수 먹고 이런식

Monitors

Semaphore를 사용할 때에도 특정 실행 순서로 진행되었을 때만 발생하는 타이밍 오류는 여전히 발생한다. (순서가 항상 일정하지 않기 때문)

  • signal( ) → wait( )
    이 둘의 순서가 바뀌어 임계구역에 프로세스들이 동시에 진입하게 될 수 있다.
  • wait( ) → wait( )
    deadlock이 발생한다.

Monitor는 항상 하나의 프로세스만이 실행되도록 한다. 이에 condition 변수를 추가하여 동시 접근과 동기화 문제를 해결한다.

  • condition 변수
    x.wait( ): 이를 호출한 프로세스는 다른 프로세스가 x.signal( )을 호출할 때까지 일시중단 되어야 한다.
    x.signal( ): 정확히 하나의 일시중단된 프로세스를 재시작한다.
  • Dining-Philosophers solution
    monitor DiningPhilosophers {
    	enum {THINKING, HUNGRY, EATING} state[5];
    	condition self[5];
    
    	void pickup(int i) {
    		state[i] = HUNGRY; // 배고프면 waiting에 넣기
    		test(i);
    		if(state[i] != EATING) self[i].wait();
    	}
    	
    	void putdown(int i) {
    		state[i] = THINKING;
    		test((i + 4) % 5); // 다 먹은 state가 오른쪽인지 확인
    		test((i + 1) % 5); // 다 먹은 state가 왼쪽인지 확인
    	}
    	
    	void test(int i) { // 양쪽 state가 먹지 않는 상태이고 자신이 배고플 때 먹는다
    		if((state[(i + 4) % 5] != EATING && (state[(i + 1) % 5] != EATING)) {
    			state[i] = EATING;
    			self[i].signal(); 
    	}
    
    	init() {
    		for(int i = 0; i < 5; ++i) {
    			state[i] = THINKING;
    		}
    }
profile
Doyun Geum
안녕하세요, 서버 개발자 도유니입니다.
이전 포스트

운영체제(OS) - 5. Scheduling

다음 포스트

운영체제(OS) - 7. Deadlocks

0개의 댓글