Chapter 6. 동기화 도구들 - 2부

안녕하세요 파피몬입니다! 운영체제 6단원에 대해 공부해 보았습니다. 우선... 2부입니다! 몇부작일지는 모르겠네용

Abraham Silberschatz의 Operating System Concepts 10th edition과 학부 수업을 듣고 정리한 내용입니다. 오개념이 있다면 알려주세요~~

 

1부에서 우리는 빠른 시스템 멀티 코어 + 선점형 커널을 사용하고 있고, 프로세스 동기화를 어떤 방식으로 해결할까? 라는 질문을 던진채 마무리 했다. 이제 컴공 형님들이 어찌 해결해 오셨는지 하나씩 살펴보자. 

 

<Peterson's Solution>

클래식한 SW기반 해결책인 Peterson's Solution는 Critical section과 나머지 구역을 번갈아 가며 실행하는 2개의 프로세스의 행동 양상을 제안한다. 이 솔루션에는 LOAD, STORE instruction이 원자적으로 작동하여, 인터럽트 될 수 없음을 가정한다. 

해당 솔루션에는 다음 자료구조가 사용된다. 

 - int turn //Critical section 들어갈 프로세스는 어떤 것인가?

 - Boolean flag[2] //프로세스가 Critical section에 들어갈 준비가 되었는지 결정 (True면 준비 완료)

 

Peterson's Solution

Peterson's Solution이 1부에서 제안한 mutual exclusion, progress, bounded waiting을 어찌 보장하는지 살펴보자. 

Mutual Exclusion

만약 두 프로세스 i,j가 critical section에 진입하고 싶은 경우, flag[0] == flag[1] == true; 가 된다. 

하지만 turn 같은 경우에는 0 아니면 1 둘 중 하나여야한다. 따라서 두 프로세스 중 하나는 무조건 while문에서 통과를 못하고 다른 프로세스가 Critical Section을 모두 수행하고 자신의 flag를 false로 바꿔줄 때 까지 기다려야한다. 

 

Progress

만일 프로세스 j가 Critical section에 들어갈 준비가 안되어 있으면 flag[j] == false 이다. 이 상황에서 프로세스 i가 Critical section에 들어가고 싶어, while문 조건을 체크해보면 flag[j]가 false라서 바로 Critical section에 진입할 수 있게 된다. 

 

Bounded Waiting

만일 프로세스 i와 j 둘 모두 Critical section에 들어가고 싶어하는 경우, turn이 i라면 프로세스 i가 진입을, turn이 j라면 프로세스 j가 진입을 하게 된다. 하지만 둘 중 하나의 프로세스가 critical section을 수행하자 마자 해당 프로세스의 flag값이 false로 전환되어, 대기 중인 다른 프로세스도 최대 1번만 기다리고 바로 critical section을 수행할 수 있다. 

 

하지만 Perterson's solution은 최신 컴퓨터 아키텍쳐에서는 안 먹힐 수도 있다. 종속성이 없는 읽기/쓰기 작업을 컴파일러/프로세서가 재정렬 할 수도 있기 떄문이다. 

따라서 동기화를 위한 하드웨어 지원을 살펴보겠다!

 

<동기화를 위한 하드웨어 지원>

결국 이러한 Critical Section 문제는 하나의 단순한 도구 LOCK만 있으면 해결이 된다. 따라서 최신 시스템들은 원자적으로 동작하는 (그니까 수행 중간에 인터럽트 되지 않는) 특별한 하드웨어 instruction을 지원하는데, 그 중에서 본 책은 test_and_set()과 compare_and_swap()에 대해서 알아본다. 

동기화에 필요한 건 LOCK!

TestAndSet

lock 변수는 False로 초기화 된다. 

 

1. 처음 lock은 False 상태로 test_and_set() 함수 호출, false 리턴 받음

2. 그 사이 *target = true를 통해 lock 변수는 true 상태

3. 해당 프로세스 Critical section 진입

  3-1. 만일 다른 프로세스가 그 사이 test_and_set() 함수 호출한다면, lock이 true이기 때문에 while문에서 걸려있다. 

4. 해당 프로세스 Critical section 수행 완료 후 lock 다시 false로 바꿈

  4-1. 그제서야 다른 프로세스가 test_and_set() 함수에서 false를 반환받아 자신의 Critical section으로 진입한다. 

 

 

 

 

 

CompareAndSwap

compare_and_swap() 정의/구현

위의 test_and_swap()과 로직은 비슷하다. 다만 파라미터를 넘겨받아, *value와 expected의 값이 동일할 때만, *value를 변경시켜주게 된다.

 

위의 두 가지 모두 Mutual Exclusion, Progress를 만족시키지만, Bounded Waiting을 만족시키진 않는다. 이를 만족시키고자 compare_and_swap() 명령어를 사용한 또 다른 알고리즘을 소개한다. 

이젠 완벽한 LOCK구현!

초기값으로 waiting 배열의 원소는 false, lock은 0을 준다. Bounded waiting은 한 프로세스가 Critical Section을 떠나면서 대기 중인 프로세스 중에 무엇을 Critical Section에 넣어줄지 판단하게 된다. 이는 waiting 배열을 순환하며 조사하는데, 이에 따라 임계구역에 들어가고자 하는 프로세스는 최대 n-1회면 된다!