[OS] Process Synchronized

프로세스 동기화 (Process Synchronized)

 - 다중 프로세스(스레드) 프로그래밍환경에서 논리주소공간을 직접공유하게 될 경우

   여러개의 프로세스(스레드)에서의 동시접근으로 인한 비일관성이 발생할 수 있다.

 - 이러한 비일관성을 방지하고 공유자원에대한 일관성을 책임져주는 것이 동기화이다.

 

예를들어 counter++ 라는 명령어가 존재한다고 하자.

우리 눈에는 한줄의 명령어지만 사실 컴퓨터입장에서보면 3개의 아래의 명령어로 동작한다.

 

register = counter

register = register + 1

counter = register 

 

그런데 동시에 3개의 프로세스가 이 명령어를 실행한다고 가정하자.

그러면 이 9개의 명령어가 뒤섞여 비일관성을 야기할 수 있다.

 

이렇게 프로세스가 어떤 순서로 스케줄링 되냐에 따라서 결과가 달라지는 것을 "경쟁상태에 있다" 라고 표현한다. 한 순간에 한 프로세스만 접급하게 하여 경쟁상태로부터 보호해야한다.

 

 

임계구역이란 ?

위의 counter예시처럼 여러 프로세스(스레드)가 공유하는 자원이 있다면,

그러한 부분을 임계구역이라 한다. 임계구역은 반드시 경쟁상태로부터 보호되어야한다.

 

임계구역을 경쟁상태로부터 보호하기위한 해결조건에는 아래 3가지가 반드시 지켜져야한다.

1. 상호 배제. (Mutex Exclusion)

  - 간단하게 말하면 임계구역엔 한번에 한놈만!! 이라는 뜻.

2. 한정된 대기. (Bounded Waiting)

  - 즉당히 기다리고 임계구역에 들어갈 수 있어야한다.

3. 진행. (Progress)

  - 임계구역에 아무도 없으면 들어가야한다.

 

어찌보면 당연한거지만 의외로 이를 만족한다는 것을 설명하는게 까다롭다...

 

우리는 임계구역의 경쟁상태로부터 보호를 위해 Lock이라는 방법을 이용할 것이다.

즉, 임계구역에 열쇠를 만들어 그 열쇠를 가진 프로세스(스레드)만 임계구역에 들어갈 수 있도록 하는것이다. 이 때 열쇠를 한개만 만든다면 자연스럽게 임계구역에는 하나의 프로세스(스레드)만 들어갈 수 있을 것이다.

 

그러나 너무나 간단하게 Lock을 만들게 된다면 위 3가지 조건을 만족하지 못하는 결과가 나올 수 있다.

예를들면 이와같이 Lock을 구현하게된다면, 무슨일이 벌어질까?

만약에 P1, P2가 동시에 실행(준비완료큐에 들어갔다면)되었다고 가정하면 P1도 P2도 lock이 false기 때문에 동시에 임계구역에 들어가버리게 된다.

 

 

또 운영체제의 Interrupt에 의해서도 잘못된 결과가 나올 수 있다. 

A → B  두가지 명령어를 거쳐야 정상적으로 lock에대한 설정이 완료되는데 A를 실행하고, B를실행하기 그 직전 사이에 우연히 Interrupt가 발생하게되면, 잘못된 결과가 나오는 것이다.

 

이러한 일들을 막기위한 세가지 방법을 소개한다.

1. 소프트웨어적 알고리즘을 통한 해결법. 

  - 피터슨 알고리즘, 데커 알고리즘

2. 더이상 쪼개지지 않는 하드웨어 명령어로 구현.

  - test_and_set(), compare_and_swap() 함수를 사용

    이렇게 더이상 쪼개지지 않아서 Interrupt가 낑길곳이 없는 것을 원자적 계산이라한다.

                           ( Atomic operation )

3. 인터럽트를 Disable, Enable하는 과정을 통한 해결법.

  - 멀티처리기 환경에서는 더이상 불가능한 방법이다. 

     단일처리기 환경에서 사용하던 방법.

 

---

 

1. 소프트웨어적 알고리즘을 통한 해결법.

  - 피터슨 알고리즘 

피터슨 알고리즘 및 데커 알고리즘의 치명적인 단점은 2개의 프로세스(스레드)밖에 적용할 수 없다는 점이다. 그리고 데커 알고리즘도 위의 피터슨 알고리즘과 내용이 비슷하므로 따로 설명하진 않겠다.

 

2. 쪼개지지않는 하드웨어 명령어로 구현.

이 또한 위의 코드만봐도 충분히 이해가 가능할 것이다.

당연히 test_and_set() 대신 compare_and_swap() 함수를 사용해도 된다.

 

---

 

Spin Lock

  → Busy Waiting 상태로 Lock이 풀리기를 Loop를 돌며 대기하는 방법을 사용한 Lock.

 

  * 계속해서 while문을 순회하기 때문에 CPU의 자원을 계속해서 소모한다. 

    그러나 Context Switch가 발생하지 않는다는 이점이 존재한다.

    그렇기 때문에 특정 Process가 Lock을 보유하는 시간이 짧다면 이득이다 !!

 

  * Spin Lock을 적용하기가 싫다면 Loop를 돌며 대기하는 것이아니라 잠을 자는 것이다.

    그러면 Lock을 반환하는 프로세스가 자고있는 프로세스를 깨워주게 된다.

 

  * 위에 모든 예제는 지금 Spin Lock이 적용되어있다.

    당연히 간단한 코드수정을통해 Break, Wakeup 기법을 적용할 수 있다고 본다.

 

 

 

Mutex 라는 용어는 여러곳에서 등장하는 것같다..

그냥 상호배제(Mutex Exclusion)이라는 곳에서도 등장하고, Spin Lock에도 적용되고 뭐 그런다.

그러나 우리가 여기서 통상적으로 말하는 Mutex란 Spin Lock이 적용된 것도 아니고,

break, wakeup이 적용된 응용프로그램을 말한다.

 

이와 같이 Semaphore라는 개념도 같이 등장한다. 사실 비슷하다...

   ( 단지 Lock의 갯수의 차이이다. 화장실 칸이 여러개냐 한개냐 뭐 그거지.. )

그 중에서도 Binary Semaphore은 Mutex랑 거의 동일하게 동작한다.

 

Moniter은 Mutex/Semaphore을 사용할 때 사용자의 실수로 교착상태가 발생할 수 있는 것을 방지해 만들어진 고급 언어 구조물이라고 생각하면된다. ( 나중에 아예 따로 다뤄볼 생각 )