임계 구역 문제 솔루션: SW solution, HW solution

이전 시간에,

공유 자원에 여러 프로세스가 동시에 access하는 상황인 race condition,

공유 자원에 접근하는 코드 영역인 critical section에 대해서 배웠고 이떄 data integrity가 깨지는 문제를 인지했다.

해결을 위해선 synchronization이 필요하다.

구체적으로 mutual exclusion, progress, bounded waiting을 충족해야 한다.

이 3가지를 충족해서 '이론적으로는' 좋은 해결책이 peterson's solution이다.

 

---

피터슨 이전의 단순한 해결책: lock(flag)만 사용

진입 후 잠금 → 잠금 직전에 타임아웃이 걸려 동시 진입 (mutual exclusion 위배)

잠금 후 진입 → 잠금 직후에 타임아웃이 걸려 둘 다 무한 루프 (progress 위배, deadlock)

 

Peterson’s Algorithm: lock과 turn

두 프로세스가 동시에 lock(flag)를 설정했더라도 turn에 따라 진행이 가능

mutual exclusion, progress, bounded waiting을 모두 충족하는 좋은 알고리즘.

전역 변수인 turn과 lock(flag)을 둘 다 활용해 상호 배제를 지키면서 데드락을 피함

 

하지만.. 실제로는 하드웨어의 도움없이는 동기화를 보장할 수 없다.

 

왜 동기화를 보장하지 못하는가?

 

앞서 배웠듯, 프로그래밍 언어로 쓴 한 줄의 명령어가 기계어로는 세 줄의 명령어 일 수 있기 때문이다.

즉 명령어가 load와 store 등으로 구성되는 경우 명령어 중간에 interrupt가 걸릴 수 있다는 것이다.

counter++ ▷ register1=counter; register1=register1+1; counter=register1

 

Atomic operation: Hardware Support for Synchronization

임계 영역 문제를 해결하기 위한 하드웨어 솔루션은 Atomicity(원자성)를 보장하는 명령어를 제공하는 것이다.

Atomic 하다는 것은 쪼갤 수 없다는, 즉 중간에 인터럽트가 걸리거나 문맥 교환이 일어나지 않는다는 것이다.

• atomic instructions
  하드웨어의 지원을 받아 타임아웃이 중간에 발생하지 않도록 한다.
  ex) test_and_set() and compare_and_swap()
  
  
• atomic variable
  atomic instructions을 이용해 atomic variable을 구현한다.
  atomic variable은 atomic operation을 제공하고, 상호 배제를 지원해준다.

[하드웨어의 도움(automic variable)을 받은 버전. 동기화 보장]

import java.util.concurrent.atomic.AtomicBoolean;

public class PetersonAlgorithm {
    static int count = 0;
    static int turn = 0;
    static AtomicBoolean[] flag; //automic variable

    static {
        flag = new AtomicBoolean[2];
        for (int i = 0; i < flag.length; i++)
            flag[i] = new AtomicBoolean();
    }


    static class Producer implements Runnable {
        @Override
        public void run() {
            for (int k = 0; k < 10000; k++) {
                /* entry section */
                flag[0].set(true); //명령어가 쪼개지지 않고 온전히 실행된다.
                turn = 1;
                while (flag[1].get() && turn == 1) ;
                /* critical section */
                count++;
                /* exit section */
                flag[0].set(false);
                /* remainder section */
            }
        }
    }

    static class Consumer implements Runnable {
        @Override
        public void run() {
            for (int k = 0; k < 10000; k++) {
                flag[1].set(true);
                turn = 0;
                while (flag[0].get() && turn == 0) ;
                count--;
                flag[1].set(false);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Thread t1 = new Thread(new Producer());
        Thread t2 = new Thread(new Consumer());
        t1.start(); t2.start();
        t1.join(); t2.join();
        System.out.println(PetersonAlgorithm.count);
    }
}

 

하드웨어의 도움을 받음으로써 동기화 문제를 해결할 수 있게 되었다.

하지만, 코드가 복잡하다.

여러 프로세스가 하나의 임계구역을 사용하려면 공유 변수를 추가하고 코드를 변경해야 하고, 바쁜 대기를 하게된다.

 

다음 시간에는 좀 더 간단하게 상호 배제만을 지원하는 뮤텍스, 세마포어, 모니터에 대해서 알아보겠다.

 

 

 

---

 

참고 자료 & 이미지 출처
운영체제 공룡책 강의 (주니온 님)
Operating System Concepts, 10th Ed (Silberschatz et al)
쉽게 배우는 운영체제 (조성호 님)