[운영체제 Atomic방법]test_and_set, Compare_and_Swap, Bounded-waiting

운영체제 목차

 

자ㅏ아ㅏ아 운영체제의 lock문제를 해결하기 위한 방법으로 3가지가 있다고 저번에 설명을 했었어요

 

 

1. 소프트웨어적 방법

2. 더 이상 쪼개지지 않는 원자적 명령어로 구현하는 방법 (즉 하드웨어 명령어 이용하는 것)

3. 인터럽트 제어로 해결하는 방법

 

 

이렇게 세가지가 있던 거 기억나시나요? (lock문제에 대해서는 이 포스팅을)

그리고 이어서 전 포스팅에서는 1번 소프트웨어적의 대표적 방법 피터슨 알고리즘에 대해서 알아봤어요

하지만 요새 컴퓨터 구조에는 더 이상 이러한 1번 즉 소프트웨어적 방법을 쓰지는 않아요 주로 2,3번 방법을 이용해서

동기화 문제를 예방한답니다.ㅎㅎ

 

오늘은 2번에 관련된 대표적인 방법 test_and_set에 대해서 알아볼거예요.

 

testAndSet이란? Lock과 비교하면서 이해하기

 

저번시간에 lock의 함수 코드 부분 기억나시나요??

lock과 test_and_set 방식의 비교대조를 위해서 lock함수코드를 다시 가져와서 설명해보겠습니다.

void lock(struct lock *I) {
    while(I->held);
    I->held=1;
}

 

저번에 lock이 가지고 있는 문제점에 대해서 말했었는데 복습겸 간략하게 다시 볼게요

자 문제가 왜 발생했었죠? 2번이 수행되고 3번이 수행되기 전에 즉 그 사이에 재수없게 인터럽트가 걸려서 프로세스가 바껴버리면 문제가 됐었어요. 2번코드에서 held가 0이라 아 아무도 안쓰는구나 이러고 3번코드에 진입하려고 하는데..! 내가 즉 2번 while문을 빠져나와서 임계영역에 진입할 수 있는 상태가 됐는데..! 나 이제 진입했어!!! 이거 이제 held가 1이야!! 라고 말해줘야하는데

진입하고 말해주기 전에 어이쿠 인터럽트에 의해서 전환이 된거죠.

그럼 다른 프로세스는 그 상황을 모르고 어라 held가 아직 0이네 아무도 없나보다 하고 얘도 진입해버리기 때문에 동시진입이 되버린다는 설명이었습니다.

 

즉 이런 문제가 발생하는 이유는, 내가 진입하자마자 바로 held를 1로 올려줘야하는데

이 코드가 한번에 이루어지지 않고 두 라인(2라인 3라인)에 걸쳐서 작성되었기 때문에 그 사이에 남이 낄 수 있는 여지를 줬기 때문에 발생한거예요

 

그럼 testAndSet은 뭐길래 이걸 해결할 수 있다는 걸까요?

저 2~3번 두 줄에 해당하는 코드를 짠 아래처럼 한 라인으로 구현할 수 있어요 

 

while (TestAndSet(lock));

이렇게 한 라인에 구현하게 되면 낑길때가 없으니까 사이에 인터럽트가 발생되서 꼬일일이 없는거죠.

더 이상 쪼개질 수 없이 한 번에 쭉 수행을 해야 한다고 그래서 atomic operation이라고 합니다. (atomic operation은 인터럽트가 발생할 수 없는 하나의 unit입니다) 

이 TestAndSet은 하드웨어 명령어 API를 이용한거예요. 또 다른 atomic operation으로 대표적으로 compare_and_swap()이 있어요! 이렇게 하드웨어 명령어를 이용하였기 처리하는 속도도 훨씬 빠르고 쪼개질 수도 없는 특징을 가지고 있습니다. 

 

대표적 하드웨어 명령어 동작방식과 함수 구현

 

이 TestAndSet(lock)이라고 하는 명령어가 어떻게 동작하느냐~~

이 lock이라고 하는 변수의 값을 먼저 test를 합니다. 그래서 얘가 0인지 1인지를 return을 하고 그리고 lock이라는 변수의 값을 바로 1로 설정하는 겁니다. 똑같은 기능을 수행하지만 소프트웨어적 코딩이 아닌 하드웨어 명령어를 이용해서 두 줄을 한 줄에 다 처리하도록 해버렸다는거~~! 이렇게 프로그래밍 할 때 하드웨어 특징을 활용하면 시스템의 효율을 더 높여주거나 문제를 더 쉽게 해결하는 데 종종 큰 도움이 된답니다.

 

함수는 사실 lock과 똑같아요 두 줄이 한줄로 바꼈을 뿐. 그래서 설명은 생략하고 넘어가도록 하겠습니다 포스팅에 이미 다 설명되어있으니까요.

do{
  while(test_and_set(&lock));
   --critical section
  lock = false;
   --remainder section
}while(true);

반면 compare_and_swap은 세 개의 매개변수를 필요로 합니다 동작방식 설명은 코드 부분에 주석으로 이어서 넣겠습니당

do {
  while(compare_and_swap(&lock, 0, 1) != 0);
  //lock이 즉 첫번째 매개변수가 두 번째 매개변수와 같을 때만 (lock이 0일 때만) lock을 1로 설정합니다.
  //하지만 return값은 2,3매개변수에 상관 없이 항상 lock의 상태를 반환해줘요 
  //즉 lock이 아무것도 안걸려있으면 0을 반환하고 lock을 1로 바꿔주고.
  //lock이 걸려있으면 1을 반환하고 lock은 그대로 1로 내비둡니당. 
  //즉 lock이 1이면(다른 애가 수행되고 있다는 뜻이니) 계속 while문에서 빠져나오지 못하고 기다리는거죠 
  //다른 하드웨어 명령어를 사용했지만 결국 test_and_set 구현한거랑 같은 역할을 수행합니다.
  --critical section
  lock =0;
  --remainder section
} while(true);

 

Bounded-Waiting mutual exclusion~?

이 위의 간단한 코드로 끝나면 좋으려만...

저 친구는 mutual-exclusion을 만족시키지만 3번째 조건(임계영역 해결조건)이었던 bounded-waiting requirement를 만족시키지 않는다는 문제가 있습니다. 그래서 이러한 문제를 해결하기 위해 test_and_set()을 이용하면서도 모든 임계영역 해결조건을 모두 만족시키는 또 다른 알고리즘이 바로 요 아이예요.

 

코드를 살펴볼게요 이 알고리즘은 내가 자원을 쓰고 싶다고 표현하는 걸 waiting이라는 변수로 표현했네요

i라는 프로세스가 자원을 쓰고 싶으면 waiting[i]=true 이렇게 나 자원쓰려고 기다리고 있어 알려주고 있어요 

do{
      waiting[i]=true;
     key =true; 
      while(waiting[i] && key)
    key = test_and_set(&lock);
      waiting[i] = false;
       // 이쯤되면 여기서 key가 무엇인지는 감이 잡히죠? 내가 쓰고 싶은데 key가 true이면 
       // 들어가지 못하고 계속 while에 머물러있겠네요 
       // 짐작한대로 key는 test_and_set명령어를 이용해서 lock을 반환해주니 lock과 같은 변수예요.
       // 즉 너가 사용하고 싶어도 누가 사용하고 있으면 잠겨있으니 못들어가~~
       // 내가 cs에 접근할 수 있는 6라인 코드로 들어가게 되면 
       //나는 이제 cs를 수행하고 있으니 기다리는 대기 라인에서 빼줍니다
 
      --critical section
 
     j= (i+1) % n;   
     while((j != i) && !waiting[j])
    j= (j+1) % n;
       // 3번의 조건을 위해서(bounded-waiting) 이 코드가 추가 되었어요. 
       // 내가 cs를 사용했으면 내가 독차지 하지 않도록 다른 프로세스에게 권한을 넘겨주는 거~
       // 실행시켜줄 프로세스 j를 정하는 일이예요. 
       // 16라인에 의해서 내 프로세스가 1이라면 j는 2가 되고 내 프로세스가 2면 j는 3이 되겠죠 (총 n개의 프로세스)
       // 이 때 j가 자원을 쓰고 싶어하지 않으면 수행시켜줄 필요가 없으므로 자원을 쓰고 싶어하는 j가 나올 때까지 
       // j를 올려줍니다. 
 
      if(j==i)  //j가 i가 될 경우는 한 바퀴 다 돌았을 때가 될거에요 쭉 살펴봤는데 자원쓰고 싶어하는 애가 없더라
         lock =false;  //그러면 넘겨줄 사람이 없으니 lock을 해제해줍니다.
    else   //이 코드는 이 자원을 쓰고 싶어하는 j를 찾았다는 거겠죠?
      waiting[j] = false;  
       //그러면 이제 얘를 수행시켜줄거니까 waiting[j]=true를 false로 바꿔줘요 왜냐!! 
        // j프로세스는 내가 쓰고 있느라 4번 코드 라인에서 while에 빙빙 돌고 있었거든요.
        // 내가 false로 풀어주면 while문을 빠져나와 cs에 접근할 수 있을 거예요.
        // 이렇게 j에게 넘겨주고 나는 cs 자원을 다썼으니 남은 코드(35)들을 수행하고 종료하는겁니다.
        //(lock은 풀 필요 없어요 j가 쓰고 있으면 lock은 어차피 1이어야 하니까요)
      --remainder section
} while(true);

6번 라인코드가 생략되면 어떤 현상이 발생하느냐! 끊임없이 무한루프를 돌게 됩니다. ㅎㅎ

do{
      waiting[i]=true;
     key =true; 
      while(waiting[i] && key)
    key = test_and_set(&lock);
      waiting[i] = false;
       // 이쯤되면 여기서 key가 무엇인지는 감이 잡히죠? 내가 쓰고 싶은데 key가 true이면 
       // 들어가지 못하고 계속 while에 머물러있겠네요 
       // 짐작한대로 key는 test_and_set명령어를 이용해서 lock을 반환해주니 lock과 같은 변수예요.
       // 즉 너가 사용하고 싶어도 누가 사용하고 있으면 잠겨있으니 못들어가~~
       // 내가 cs에 접근할 수 있는 6라인 코드로 들어가게 되면 
       //나는 이제 cs를 수행하고 있으니 기다리는 대기 라인에서 빼줍니다

      --critical section

     j= (i+1) % n;   
     while((j != i) && !waiting[j])
    j= (j+1) % n;
       // 3번의 조건을 위해서(bounded-waiting) 이 코드가 추가 되었어요. 
       // 내가 cs를 사용했으면 내가 독차지 하지 않도록 다른 프로세스에게 권한을 넘겨주는 거~
       // 실행시켜줄 프로세스 j를 정하는 일이예요. 
       // 16라인에 의해서 내 프로세스가 1이라면 j는 2가 되고 내 프로세스가 2면 j는 3이 되겠죠 (총 n개의 프로세스)
       // 이 때 j가 자원을 쓰고 싶어하지 않으면 수행시켜줄 필요가 없으므로 자원을 쓰고 싶어하는 j가 나올 때까지 
       // j를 올려줍니다. 

      if(j==i)  //j가 i가 될 경우는 한 바퀴 다 돌았을 때가 될거에요 쭉 살펴봤는데 자원쓰고 싶어하는 애가 없더라
         lock =false;  //그러면 넘겨줄 사람이 없으니 lock을 해제해줍니다.
    else   //이 코드는 이 자원을 쓰고 싶어하는 j를 찾았다는 거겠죠?
      waiting[j] = false;  
       //그러면 이제 얘를 수행시켜줄거니까 waiting[j]=true를 false로 바꿔줘요 왜냐!! 
        // j프로세스는 내가 쓰고 있느라 4번 코드 라인에서 while에 빙빙 돌고 있었거든요.
        // 내가 false로 풀어주면 while문을 빠져나와 cs에 접근할 수 있을 거예요.
        // 이렇게 j에게 넘겨주고 나는 cs 자원을 다썼으니 남은 코드(35)들을 수행하고 종료하는겁니다.
        //(lock은 풀 필요 없어요 j가 쓰고 있으면 lock은 어차피 1이어야 하니까요)
      --remainder section
} while(true);

같은 코드인데 혹시 가운데정렬이 불편하신 분들을 위해 추가!