반효경교수님 운영체제 2017 수업을 참고하여 작성하였습니다.

병행제어 2

Two Types of Semaphores

• Counting semaphore
  • 도메인이 0 이상인 임의의 정수값
  • 주로 resource counting에 사용
• Binary semaphore(=mutex)
  • 0 또는 1 값만 가질 수 있는 semaphore
  • 주로 mutual exclusion 상호배제(lock/unlock)에 사용

Deadlock

• 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

Stravaition

• indefinite blocking 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

Classical Problems of Synchronization

• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem

Bounded-Buffer Problem

• 강의 내에서 buffer를 사탕으로 비유한다.
• consumer는 사탕을 가져가고, producer는 사탕을 채워둔다.
• Empty/full buffer의 시작위치(포인터)를 shared data로 lock이 필요하다.
• producer는 empty buffer를, consumer는 full buffer를 자원으로 획득한다.
  • counting semaphore
• 자원을 획득하면, 다른 프로세스가 접근할 수 없도록 lock을 건다.(mutex)(semaphore)
  

Readers and Writers Problem

• 하나의 프로세스가 DB에 write 중이라면 다른 process가 접근하면 안된다.
• reader는 동시에 접근해도 문제없음
  

solution

• writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 reader들은 DB에 접근을 허용한다.

• writer는 대기중 인 reader가 없다면, DB접근을 허용한다.

• writer가 DB에 접근 중이라면 reader는 DB애 접근할 수 없다.

• writer가 DB에서 빠져나가면, reader의 접근이 허용된다.

• writer와 reader모두 동시접근을 막는다면 코드가 단순하지만, reader끼리는 동시접근을 허용하게 함으로써 readCount를 공유변수를 두게되어 코드가 조금 더 복잡해진다.

• Reader가 lock을 해제하기전에 readerCount가 계속 추가되었을경우 writer가 starvation 가능성 있음.

• 일정시간까지 도착한 reader만 동시접근을 가능하게한다면, writer에게 접근할 수 있도록하면 starvation 가능성을 제거할 수 있다.

Dining-Philosophers Problem

• 철학자에게 주어진 일
  1. 생각하는 것
  2. (학자도 사람이기때문에)식사를 하는것
• 젓가락이 공유자원, 상호배제가 필요함
• 모든 철학자가 식사를 동시에 하려고 한다면, 젓가락을 하나 집어든 뒤, 다른 젓가락을 계속 기다리고 있어서 deadLock이 발생한다.

solution

• 4명의 철학자만의 테이블에 동시에 앉을 수 있도록 한다.

• 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
  

  • 테스트( 동시에 잡을 수 있는지 체크)를 통과한다면, 접근 권한을 가지게 된다.
  • 젓가락을 내려놓고 옆의 철학자가 젓가락을 기다리는 상태인지 테스트를 한다.

• 비대칭 : 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다.(우선순위를 정해줌)

Monitor

Semaphore의 문제점

• 코딩하기 힘들다.
• 정확성의 입증이 어렵다
• 자발적 협력이 필요하다
• 한번의 실수가 모든 시스템에 치명적 영향

세마포어의 문제점을 극복하기 위해서 등장한 monitor

• 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct

• 공유데이터의 접근은 monitor내의 함수로만 접근을 가능하도록 함

• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능하다.

• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다. (프로그래머가 책임을 지지않는다.)

• 프로세스가 모니터 안에서 기다릴 수 있도록 condition variable을 사용한다.

  condition x, y;
  
  x.wait();
  /* x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend된다. */
  
  x.signal();
  /* x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. suspend된 프로세스가 없으면 아무 일도 일어나지 않는다. */

  • condition variabledms wait 와 signal연산에 의해서만 접근이 가능하다.

Bounded-Buffer Problem(monitor)

monitor bounded_buffer
{ int buffer[N];
	condition full,empty;
	/* condition variable은 값을 가지지 않고 자신의 큐에 프로세스를 줄 세워서 sleep 시키거나 큐에서 프로세스를 깨우는 역할만 함 */

	void produce(int x)
	{ if there is no empty buffer
				empty.wait();
    add x to an empty buffer
		full.signal();
	}
	
	void consume(int *x)
	{ if there is no full buffer
				full.wait();
    remove an item from buffer and store it to *x
    empty.signal();
	}
	
}

Dining-Philosophers Problem(monitor)

monitor dining_philosopher 
{
 		enum {thinking, hungry, eating} state[5];
  	condition self[5];
  	
  	void pickup(int i) {
      state[i] = hungry;
      test(i);
      if(state[i] != eating)
        	self[i].wait();
    }
  	
  	void putdown(int i) {
      state[i] = thinking;
      /* test left and right neighbors */
      test((i+4) % 5);
      test((i+1) % 5);
    }
  
  	void test(int i) {
      if( (state[(i+4) % 5] != eating) && (state[i] == hungry) && (state[i+1 % 5] != eating) ){
        	state[i] = eating;
        	self[i].signal();
      }
    }
  
  	void init() {
      for (int i = 0; i < 5; i++)
        	state[i] = thinking;
    }
}


Each Philosopher:
{
   pickup(i); /* enter moniter */
	 eat();
   putdown(i); /* enter moniter */
   think();
} while(1)

교착상태(deadlock)

• 일련의 프로세스들이 서로가 가진 자원을 기다리면서 block된 상태

Resource

• 하드웨어, 소프트웨어 등을 포함하는 개념

• ex) I/O device, CPU cycle, memory space, semaphore 등

• 프로세스가 자원을 사용하는 절차

  • Request, Allocate, Use, Release

• Deadlock Example 1

  • 시스템에 2개의 tape drive가 있다
  • 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다.

• Deadlock Example 2

  • Binary semaphores A and B

    Process0
    P(A);
    P(B);
    
    Process1
    P(B);
    P(A);

Deadlock 발생의 4가지 조건

• Mutual exclusion
  • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
• No preemption
  • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
• Hold and wait
  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
• Circular wait
  • 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
  • Pn-1은 Pn이 가진 자원을 기다림
  • Pn은 P0이 가진 자원을 기다림
    
    

Deadlock의 처리 방법

• Deadlock Prevention
  • 자원 할당 시 deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
• Deadlock Avoidance
  • 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
  • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
• Deadlock Detection and recovery
  • deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover
• Deadlock Ignorance
  • deadlock을 시스템이 책임지지 않음
  • UNIX를 포함한 대부분의 OS가 채택

Deadlock Prevention

• Hold and wait
  • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야한다.
    1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
    2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
• no preemption
  • state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)
  • Process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점된다.
• Circular Wait
  • 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당

-> Utilization 저하, throughput 감소, starvation 문제

Deadlock Avoidance

• 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로 부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.
• safe state
  • 시스템 내의 프로세스들에 대한 프로세스들에 대한 safe sequence가 존재하는 상태
• safe sequence
  • 프로세스의 sequence<P1,P2, ..., Pn>이 safe하려면 Pi의 자원 요청이 가용자원+모든 Pj(j<i)의 보유자원에 의해 충족되어야 함
  • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
    • Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj가 종료될 때까지 기다린다.
    • Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다.

• 미래에 deadlock 가능성이 있으면 보수적으로 가용자원도 할당시켜주지 않는다.
• 데드락이 생길 가능성이 있다면, (cycle이 생길 가능성, 불완전한 상황) 자원을 주지 않는다. (시스템이 그러한 가능성을 차단하는 것을 보장)
• 시스템이 safe state에 있으면, 데드락이 생기지 않는다.
• 시스템이 unsafe state에 있다면, 데드락이 생길 가능성이 있다.
• Unsafe state가 되지않도록 차단한다.

Banker's Algorithm

• Available 자원으로 process가 MAX로 사용할 자원을 감당할 수 있는 상황에서만, 해당 process에게 자원을 할당한다.
• Available 자원으로 처리를 할 수 있는 프로세스가 있기 때문에, 그러한 프로세스에게 자원을 몰아주고, 반납함으로써 sequence가 존재한다. -> safe state
• Safe sequence를 따지는 것은 banker's algorithm이 하는 것이 아니다.

Deadlock Detection and recovery

• Deadlock Detection

  • Resource type 당 single instance인 경우
    • 자원할당 그래프에서의 cycle이 곧 deadlock을 의미
  • Resource type 당 multiple instance인 경우
    • 뱅커스 알고리즘과 같이 테이블을 그리는 방법과 유사하게 활용
  • 현재 자원을 요청하지 않은 프로세스들이 자원을 반납할 것이라고 가정하여 deadlock을 체크한다. (낙관적)
    

• Wait-for graph 알고리즘

  • Resource type 당 single instance인 경우
  • Wait-for graph(자원할당 그래프의 변형)
  • 프로세스만으로 node를 구성(자원을 체크하지않음)
  • Pi가 가지고 있는 자원을 Pj가 기다리는 경우 Pj -> Pi
  • Algorithm
    • Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
    • O(n^2)

• Recovery

  1. Process termination
     • 데드락에 연루된 모든 프로세스들을 다 종료시키는 방법
     • 데드락에 연루된 프로세스들을 하나씩 종료시키는 방법
  2. Resource Preemption
     비용을 최소화할 victim의 선정
     safe state로 rollback하여 process를 restart
     Starvation 문제
     동일한 프로세스가 계속해서 victim으로 선정되는 경우
     * cost factor에 rollback 횟수도 같이 고려
     

Deadlock Ignorance

• Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
  • Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있다.
  • 만약, 시스템에 데드락이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처한다
  • UNIX, Windows 등 대부분의 범용 OS가 채택