[운영체제] 프로세스 동기화 1

다중 프로그래밍 환경에서는 여러 개의 프로세스가 CPU를 차지하기 위해서 경쟁하고

각 프로세스는 경우에 따라서 다른 프로세스와 데이터를 공유하기도 한다.

 

이렇게 여러개의 프로세스가 하나의 데이터를 같이 사용하게 되는 경우 해당 데이터에 대한 동기화 처리가 필요하다.

그래야 각 프로세스가 데이터를 사용할 때 문제 없이 사용할 수 있다. (= 공유 데이터에 대한 무결성이 보장된다.)

 

---

데이터 접근

컴퓨터 시스템에서 데이터에 접근하는 패턴은 아래와 같다.

1. 데이터가 저장되어 있는 곳에서 데이터를 읽어와
2. CPU에서 연산을 한 후
3. 다시 데이터를 갖고 온 곳에 가서 저장한다.

 

데이터를 읽기만 한다면 문제가 되지 않는다. 여러 프로세스가 읽기만 하면 데이터가 변경되는 경우가 없다.

하지만 대부분의 경우 데이터를 조작하기 때문에 문제가 발생한다. A 프로세스가 데이터를 조작하는데 도중에 B 프로세스가 같은 데이터를 조작하게 되면 데이터의 일관성이 깨지기 때문이다. 

 

그래서 데이터를 조작하는 프로세스 간이 동기화를 맞춰줘야 한다.

 

---

Race Condition

위에서 말한 것과 같이 하나의 자원에 대해서 여러 프로세스들이 경쟁하는 상태를 race condition이라고 한다.

 

두개 이상의 프로세스가 공통 자원을 병행적으로 읽거나 쓸 때 공용 데이터에 대한 접근이 어떤 순서로 이뤄졌는지에 따라 실행 결과가 달라지는 상황을 말한다.

 

프로세스가 자신의 주소 공간에 접근하는 경우는 문제가 되지 않지만,

시스템 콜로 운영체제가 커널 코드에 접근하는 경우는 문제가 될 수 있다.

 

또한 멀티 프로세서 환경의 경우 프로세스의 메모리 공간을 공유하기 때문에 문제가 발생할 수 있다.

 

경쟁 상태가 발생하게 되면 모든 프로세스의 제대로 된 결과를 보장할 수 없기 때문에 이런 상황을 지양해야한다.

 

---

OS에서 언제 경쟁 상황이 발생하는가?

🟠 커널 수행 중 인터럽트가 발생한 경우

운영체제가 커널 모드에서 커널 내부의 count + 1 연산을 수행하던 도중에 인터럽트가 발생하게 되면 

인터럽트 핸들러는 커널의 count 값을 -1하고 원래 위치로 돌아오게 되는데

 

이 때 count 값은 핸들러 전의 count 값만 저장되기 때문에 실제로는 count + 1 한 값만 반영된다.

 

🟢  커널 모드에서 작업을 하는 경우 도중에 인터럽트가 걸려도 무시하고 작업이 끝나면 인터럽트를 처리한다.

 

---

🟠프로세스가 시스템 콜을 해서 커널 모드로 수행 중인데 문맥 교환이 일어나는 경우

A 프로세스가 시스템 콜을 호출해서 커널의 count + 1 연산을 수행하던 도중에 CPU 시간이 끝나서 B 프로세스에게 CPU가 넘어간다.

ㅠ 프로세스 역시 시스템 콜을 호출해서 커널의 count + 1 연산을 수행하고 A 프로세스에게 CPU를 넘긴다.

 

이 때 A 프로세의 context의 count는 B 프로세스가 count + 1 결과가 반영되지 않기 때문에 실제적으로는 +2 가 되어야하지만 count + 1 만 결과만 반영된다.

 

🟢 어떤 프로세스가 커널 모드에 있는 경우 CPU 시간이 끝나도 CPU를 빼앗지 않고 작업이 끝나서 사용자 모드일 때 CPU를 뺏는다.

 

---

🟠 Multiprocessor에서 shared memory 내의 kernel data

1,2의 경우 cpu가 하나이지만 multiprocessor 환경의 경우 cpu가 여러개 이기 때문에 인터럽트를 막는다고 해결되지 않는다.

 

🟢 이런 경우는 공유 데이터에 대해 lock/unlock을 해주어야 한다.

 

이는 곧 데이터에 대한 접근을 제한하는 것이다.

🟢 또한 이런 문제는 kernel 영역에 대한 접근때문에 발생하기 때문에 매 순간 하나의 cpu만 kernel에 접근하도록 해주는 방법도 있다.

 

---

임계 구역

Critical Section이라고도 하며,

n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드가 존재하는데 이를 Critical Section이라고 한다.

 

하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 합니다.

---

임계 구역 문제를 해결하기 위한 충족 조건

1. Mutual Exclusion

상호배제,

프로세스A가 임계영역에 들어가 있으면 다른 모든 프로세스들은 임계영역에 들어가면 안된다.

 

2. Progress

진행,

아무도 임계영역에 있지 않은 상태에서 임계영역에 들어가고자 하는 프로세스가 있으면 임계영역에 들어가게 해야 한다.

 

3. Bounded Waiting

유한 대기,

프로세스가 임계영역에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 임계영역에 들어가는 횟수에 한계가 있어야 한다. (기아 방지)

 

---

임계 구역 문제 해결을 위한 알고리즘

🤔 왜 이런 알고리즘이 필요한가?

먼저 이러한 알고리즘이 필요한 이유는 임계영역의 코드가 기계어로 바뀌면 한줄씩 실행되기 때문입니다. 그렇기 때문에 한 줄, 한 줄 실행다가 그 사이에 인터럽트가 발생하게 되면 다른 프로세스로 cpu가 이양 되기 때문에 문제가 생기는 것입니다. 만약 이러한

명령어를 단 1줄로 표현할 수 있다면 아주 간단하게 critical section문제를 해결할 수 있습니다.

 

소프트웨어 알고리즘

1.  turn 변수

 

turn 변수는 자신의 차례인지를 나타내기 위한 변수로 turn 0은 P0의 차례, turn 1은 P1의 차례가 된다.

 

처음 turn이 0으로 초기화 되어있다면 먼저 P0이 임계영역에 들어가 일을 수행하고 나오면서 turn을 1로 세팅한다. 그러면 다음에 P1이 임계영역에 들어가 일을 수행하고다 다시 turn 0으로 만들고 .. 이런 과정을 반복한다.

 

🔴 하지만 위의 코드는 상호배제 조건을 만족하지만 진행조건을 만족하지 않는다. 임계영역에 들어가 있는 프로세스가 없지만 임계영역에 들어가지 못하게 됩니다.

코드를 보게 되면, turn 변수로 프로세스가 무조건 교대로 동작하게 되어 있습니다. P0이 임계영역에 들어갈 필요가 없어 들어가지 않으면 P1은 절대 임계영역에 들어가지 못하게 된다. (turn을 바꾸지 않기 때문에) 

 

2.  flag 표시

 

여기에서는 flag[]를 사용하는데, 여기에 자신이 임계영역에 들어가고 싶다라고 표시를 한다.

그리고 while문에서 다른 프로세스가 임계영역에 들어가 있는지 검사하고 만약 들어가 있다면 계속 대기하며 그렇지 않은 경우 임계영역에 들어가게 된다.

작업을 마치면 임계영역을 나오면서 자신의 flag값을 false로 만들어 놓는다.

 

🔴 하지만 만약 flag[i]=true를 하고 바로 cpu를 다른 프로세스에게 뺏기면 해당 프로세스도 flag에 체크를 하는데, 이렇게 되면 두 프로세스 모두 flag에 체크만 하고 실제로 임계영역에 들어간 프로세스는 없게 된다.

들어간 프로세스가 없다 보니 자신의 flag를 false로 못하기 때문에 영원히 서로 양보하는 상황이 발생하게 된다. 

 

3. Peterson's Algorithm

 

피터슨 알고리즘은 turn과 flag를 모두 사용한 방법이다.

 

프로세스가 임계영역에 들어가기 전에 flag에 자신이 임계영역에 들어가고 싶다고 체크를 한다. 그리고 turn을 상대방으로 바꾸고 상대방이 현재 임계영역에 들어가고 싶어하고 상대방 턴인지 검사를 한다. 그렇지 않은 경우 내가 임계영역에 들어가고 나올때 나의 flag를 false로 만든다.

 

>  하지만 이 알고리즘도 문제가 있는데 자신의 턴이 아니여서 임계영역에 들어갈 수 없지만 cpu를 할당받은 동안 계속 while문 조건을 검색하면서 cpu를 낭비하게 된다. 이를 busy waiting(=spin lock)이라고 한다. 

 

---

하드웨어 알고리즘

대부분 데이터를 읽고/쓰는 명령어를 나누어져 있기 때문에 여러 문제가 발생한다. 명령어 사이에 다른 인터럽트가 들어와 도중에 공유 데이터를 조작할 수도 있으며 이로 인해 각 프로세스 context의 데이터값이 달라져 원하는 결과를 얻을 수 없다. 

 

이런 문제는 하드웨어 적으로 해결할 수 있으며 Test_and_set()은 읽고/쓰는 작업을 동시에 수행할 수 있다.

 

Test_and_set(a)는 a라는 값을 읽고 a값을 1로 세팅하는 과정을 한번의 명령어로 처리한다.

만약 a=0이고 Test_and_set(a)을 하면 한번에 a=1로 바뀌며 a=1이라면 그대로 a=1이 된다. 다음 사진을 보면 이해하는데 도움이 될 것이다.

 

프로세스가 임계영역에 들어가기 전에 Test_and_set(lock)을 검사하는데 lock=false여서 임계영역에 들어간다. 들어갈 때 lock은 Test_and_Set에 의해 true가 된다. 때문에 다른 프로세스는 while()에서 대기하게 된다. 임계영역을 나올 때 lock=false가 되어 다른 프로세스가 임계영역에 들어오게 된다.