운영체제 CH6(9주차) -2

Bounded-waiting Mutual Exclusion with compare-and-swap

CAS(compare-and-swap)을 사용하여 CS(Critical Section)에 순차적으로 들어가는 알고리즘

while (true){
    waiting[i] = true;//다른 프로세스가 CS에 있으니 i는 가다려야한다.
    key =1;
    while(waiting[i] && key == 1)//waiting[i]가 False이면 누군가 CS에서 나왔음을 의미
        key = compare_and_swap(&lock,0,1);//key는 lock의 현재 값으로서 key=1이면 누군가 CS에 있다는 뜻이다. Key=0일때까지 기다린다.
    waiting[i] = false;
    /*Critical Section*/
    j = (i+1)%n;
    while((j != i) && !waiting[j])//돌아 돌아 자기 자리가 아니면 j를 하나 올린다.
        j = (j + 1) % n;
    if (j == i)//만일 다음 사라밍 나라면 기다리는 사람이 없음 lock을 풀어준다.
        lock = 0;
    else
        waiting[j] = false;//기다리는 프로세서가 있어서 lock을 걸고 들어가도록 함. lock을 다시 복원시켜주는 역할 
    /*remainder section*/

}

Atomic Variables

변경하는 과정에 inturrupt 같은 중간 방해를 받지 않는 변수

//다음은 한번에 실행되는 Hardware instruction을 풀어 쓴것이다.
void increment(atomic_int *v){
    int temp;
    do{
        temp = *v;//v를 읽고 저장
    }
    while(temp != (compare_and_swap(v,temp,temp+1)))//저장된 temp와 비교해 다르다면 중간에 inturrupt된것 임으로 다시 while loop로 다시 수행
}

Mutex Locks

• Hardware-based solution은 개발자 입장에서는 복잡하고 inaccessible함 => Hardware-based solution을 이용하는 소프트웨어상의 추상화된 도구

• 상호베타 진행을 지원하는 가장 단순한 형태이다

• acquire(): lock을 획득하는 행위(CS에 진입함) / release(): CS를 풀고 빠져나옴

• Mutext lock은 CPU를 소모하며 기다리는 Spin lock을 사용한다.(프로세스 경쟁이 치열하지 않은 다중코어 시스템에서는 Spin lock(busy waiting)을 많이 사용함)

  Spin lock

  CPU를 소모하지만 context switching이 필요없기에 유리한 면도 있다. 그래서 다중코어 시스템에서는 우수한 성능을 보이고 Context Switching을 2번 할 시간보다 lock을 걸고 있는 시간이 짧으면 spinlock이 유리하다

while(true){
    acquire lock
        /*critical section*/
    release lock
        /*reminder lock*/
}

aquire(){//atomic하게 수행되어야함 -> test_and_set과 compare_and_swap을 이용해 구현
    while(!avaliable)
        ; /*busu Waiting*/
    avaliable = false;
}

release(){//atomic하게 수행되어야함 -> test_and_set과 compare_and_swap을 이용해 구현
    avalibale = true;
}

Semaphore

• 상호 베타 진행을 지원하는 가장 일반적인 방식
• Semaphore S - 정수형 변수 [S값이 0보다 크면 CS에 들어갈수 있다.]
• wait()와 signal()[atomic하게 이루어져야함]

wait(S){
    while(S <= 0)
        ; // busy wait
    S--;
}

signal(S){
    S++
}

Semaphore 의 사용

• Binary Semaphore : 이진수를 가지는 Semaphore
• Counting Semaphore: 정수형 변수를 가지는 Semaphore

예시: P1, P2 프로세서가 있다. 여기 있는 서로다른 프로세서에 각각 S1, S2가 있는데 S1을 먼저 일으키고 S2를 일으키려고 한다. Semaphore 사용법은?

//처음에 Semaphore synch를 0으로 초기화한다.
P1:
    S1;
    signal(synch);
P2:
    wait(synch);//S1, S2의 순서를 보장하기 위한 방법
    S2;

Semaphore 구현

• 2개 이상의 프로세스가 동일한 Semaphore 를 동시에 사용할수 없도록 함
• Semaphore 변수에 대한 CS문제를 다루는 거라고 볼수 있다.
• wait()는 synch가 0보다 클때까지 Busy waiting을 한다. 단, 프로세스가 cs에 오래 토록 머무르지 않을때 유리함

Busy waiting 없이 Semaphore 구현

• 각각의 Semaphore를 waiting queue에 집어 넣음

• waiting queue의 entry에는 Semaphore 변수 값과 리스트의 다음 변수를 가리키는 포인터를 설정한다.

• block() : Semaphore 변수가 0이라면 프로세스를 멈추로 waiting queue에 들어감

• wakeup(): wating queue에서 나와서 Ready queue에 들어감

  // Single Core 에서 Semaphore 구현
  typedef struct ={
      int value;//Semaphore 값
      struct process *list;// 대기열
  }semaphore;
  
  wait(semaphore *S){
      /*멀티 코어 에서 있다면 다음처럼 test_and_set을 이용해 lock을 얻어서 동일하게 동작시킴
      while(test_and_set(&mutext))
          SpinLock
      */
      disable inturrupts;
      S->value--;
      if(S -> value <0){
          add this process to S-<list;
          block();
      }
      enable inturrupts;
  }
  
  signal(semaphore *S){
      /*멀티 코어 에서 있다면 다음처럼 test_and_set을 이용해 lock을 얻어서 동일하게 동작시킴
      while(test_and_set(&mutext))
          SpinLock
      */
      disable inturrupts;
      S->value++;
      if(S -> value <= 0){//증가 시켰는데도 음수나 0이라면 waiting queue에 누군가 있다는 뜻이다. 
          remove a process P from S-<list;//waiting queue에서 Ready Queue으로 이동한다.
          wakeup(P);
      }
      enable inturrupts;
  }

Semaphore의 문제점

• Signal와 waiting을 둘중하나만 편향적으로 균형있지 않게 사용하면 굉장히 많은 오류를 범할수 있다.

Monitors

단 하나의 프로세서만 Monitor 함수를 사용할수 있도록 하는 도구

어떠한 이유로 프로세스를 진행할 수 없다면 condition variable를 이용해 스스로 Suspend할수 있다.

Condition variable은: 대기열의 이름

x.wait() : x대기열엣 가다려라, 누군가 x대기열에 신호를 보내줄때까지 대기하라

x.signal(): x대기열에 대기하는 얘를 깨워라, 만약 없다면 아무 효과가 없는것이다.

프로세스가 Monitor 내에서 방해받지 않고 실행될것을 보장한다. 만일 타 프로세스와 병행 실행을 허용하고 싶다면 조건변수 wait()를 실행한다. 즉 Monitor함수는 스스로 preemption의 위치를 스스로 지정할수 있다.

Semaphore와 Monitors의 차이점

Semaphore	Monitor
wait(s) : [--s >= 0이면 진행 아니면 suspend]	x.wait(): [무조건 suspended]
signal(s): [++s <= 0이면 suspended process을 하나 깨움]	x.signal(): [Suspended process 가 있으면 깨우고 없으면 무시]

그럼 P가 x.signal을 통해 Q를 깨웠다. P와 Q는 동시에 실행될수 없는데 이때는 어떻게 해야하는가?

1. Signal and wait: P가 Q를 깨우면 P가 Q가 끝날때까지 기다린다.
2. Signal and Continue: P가 Q를 깨우면 Q를 꺠워 놓고 P는 자기 할일 을 마저 한다. 그다음에 Q를 실행한다.

2가지 방법 모두 장단점이 있다.

Consurrent Pascal: P가 signal을 받자 마자 빠져나간다.

aquire(t) 함수는 t 매개변수로서 t가 짧을수록 혹은 aquire 내부에 x.wait(t)에 t가 짧을수록 더 높은 우선순위를 가질수 있도록 해줄 수 있다.

관련 코드를 확인하십시오

Liveness

Mutex lock이나 semaphore를 동해 동기화하는 과정에서 무한 대기 상황이 발생할수 있다. 이러한 상황의 대표적인 예가 Deadlock이다. Liveness는 대기 상황 자체를 한정지음으로서 Deadlock 상황을 타개한다.

대표적인 Liveness-failure, Deadlock

진퇴양난의 상황으로 만약 S와 Q를 동기화 시킨다고 하면 P1과 P2가 동시에 S, Q를 wait 해버리면 아무것도 진행되지 않고 둘다 대기하는 Deadlock 상태에 진입하게 된다.

• Starvation : 프로세스가 전혀 제거되지 않고 Semaphore Queue에서 영원히 suspended 되어있는 상황
• Priority inversion: 낮은 우선순위의 프로세스가 lock되어있어 높은 우선순위의 프로세스가 진행되지 못하는 상황
  • 이 문제는 현재 자원을 소유한 프로세스의 우선순위를 자원을 요청하는 높은 우선순위의 프로세스의 우선 순위를 할당해주는 Priority-inheritance Protocal로 해결가능하다.