프로세스에서의 동기화 (Process Synchronization) [운영체제]

 

프로세스 동기화를 왜할까...?

 

우리 컴퓨터는 사실 여러가지의 프로세스가 진행중이기 때문에

실행 중인 다른 프로세스의 실행에 영향을 주거나 받을 수 있다.

 

• Processes can execute concurrently
• May be interrupted at any time, partially completing execution
• Concurrent access to shared data may result in data inconsistency
• Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes

 

우리는 이미 프로세스가 병렬로 실행 가능하다는 것을 알고있다.  

단적으로 스케줄링(scheduling)에서  CPU 스케줄러가 프로세스 사이를 오가며 빠르게 모든 프로세스를 병행 실행시키는 것이라는 것도 알고 있다.

데이터의 일관성을 위해서는 협력 프로세스 간의 실행순서를 정해주는 메커니즘이 필요하다.

 

프로세스는 논리 주소 공간(코드 및 데이터) 를 직접 공유하거나 공유 메모리 또는 메세지 전달을 통해서만 데인터를 공유할 수 있는데 공유 데이터에 동시에 접근하면 데이터의 일관성이 깨질 수 있다.

 

논리 주소 공간을 공유하는 프로세스의 질서 있는 실행을 보장해서 데이터를 일관성 있게 하는데에 동기화가 쓰인다.

 

현재는 대부분 쓰레드 기준으로 스위칭을 하므로, Thread synchronization으로 많이 불린다.

 

예를 들어 LCK 표를 파는데

LCK 관전표를 100개 가지고 있는 storage에서 해당 표가 팔리거나 환불되면 Storage에서도 해당 결과를 받아서 표의 수를 업데이트해야하는데 결과가 도달하기 전에 환불도 되고 팔리기도 하였다.

 

그래서 수익을 보니 엉망이 되어있었다. 환불되어 표가 생기기도 전에 팔리는 경우가 있었고

환불되었음에도 표가 살 수 없는 경우가 일어났다.

 

이는 데이터의 갱신, 동기화가 이루어지지 않아 생긴 일이다.

 

이렇게 같은 공유데이터에 접근하는 작업(프로세스)가 여러 개 있을 경우 서로 접근에 충돌이나는 경쟁상태가 생긴다.

임계구역은 여러 개의 쓰레드가 수행되는 시스템에서 각 쓰레드들이 공유하는 데이터(변수, 테이블, 파일 등)를 변경하는 코드 영역을 말한다.(메모리가 아니다)

 

이것을 Race Condition이라고 한다.

**CPU가 하나라면 어차피 연산이 끝나고 다른 프로세스가 진행되니까 문제가 없겠지만

Multiprocessor system의 경우 CPU가 동시에 접근이 되니까..?

 

 

사실 프로세스 간에는 문제가 별로 되지는 않지만

Kernel 접근 시 그 부분이 문제가 된다.

OS에서 race condition이 발생하게 된다.

 

---

 

 

단일 코어 환경에서는 공유 변수를 수정하는 동안 인터럽트가 발생하는 것을 막을 수 있다면 임계구역 문제는 간단히 해결될 수 있다.

이렇게 하면 현재 실행 중인 명령어들을 선점 없이 순서대로 실행될 수 있다는 것을 확신할 수 있다.

다른 명령어는 실행되지 않으므로 공유 변수를 예기치 않게 수정될 일이 없다.

 

그렇지만...?

다중 처리기 환경에서는 안된다. (MultiProecessor System의 경우)

 

메시지가 모든 프로세서에 전달되므로 다중 처리기에서 인터럽트를 비활성화 하면 시간이 많이 걸릴 수 있다.

-> 오버헤드가 늘어남.

 

그래서 운영체제 내에서 임계구역을 다루기 위하여

선점형 커널, 비선점형 커널의 2가지 일반적인 접근법이 사용된다.

 

1. 선점형 커널

선점형 커널에서는 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용한다. 

 

2. 비선점형 커널

비선점형 커널은 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고 커널 모드 프로세스는 커널을 빠져나갈 때까지 또는 봉쇄될 때까지 또는 자발적으로 CPU의 제어를 양보할 때까지 수행된다.

 

**비선점형 커널은 한순간에 커널 안에서 실행 중인 프로세스는 하나밖에 없으므로 커널 자료구조에 대한 경쟁 조건을 염려할 필요는 없다.

 

**선점형은 반대로 경쟁 조건을 만들지 않도록 신중하게 설계되어야 한다.

 

비선점형 커널이 오히려 생각할 것이 없어 좋아보이지만

그렇게 막는 것은 비효율적인 수행을 가져와

현재는 대부분 선점형으로 쓰고 그에 따른 동기화 기법을 쓴다.

 

커널 모드 프로세스가 대기 중인 프로세스에 처리기를 양도하기 전에 오랫동안 실행할 위험이 적기 때문에 선점형 커널은 더 응답이 민첩할 수 있다.

게다가 실시간 프로세스가 현재 커널에서 실행 중인 프로세스를 선점할 수 있기 때문에 실시간 프로그래밍에 더 적합하다.

 

아래 예시를 보고 잘 이해해보자.

 

---

 

 

1. 커널 수행중 인터럽트가 발생한다.

**커널에서 수행중이라면 인터럽트가 왔을 때 해당 커널 작업이 끝나고 인터럽트 핸들링을 하는 것으로 해결이가능하다.

 

 

2. Process가 system call을 하여 커널모드,Kernel-mode(not user)에서 context swtich가 일어난다.

CPU 점유가 끝난 시점이 커널데이터를 쓰는 도중이라면 Race Condition이 발생할 수도 있다는 것이다.

**커널모드에 있을 때는 CPU 점유를 빼앗기지 않도록 함으로써 해결할 수 있음.

 

 

3. Multiprocessor에서 shared memory 내의 kernel data 접근

 

CPU가 여러개 있는 상황에서는

앞의 해결방법으로는 해결되지 않는다.

 

해당 데이터에 lock을 걸어 다른 프로세스가 접근하는 것을 막는 것이다.

해당 데이터에 대한 작업이 끝나면 다른 프로세스도 이용할 수 있게 unlock을 한다.

또는 위의 모든 3경우는 커널에 접근하는 상황에 발생하므로

한 번에 하나만의 CPU만이 커널에서 작업할 수 있게 함으로써 해결할 수 있다.(비효율적이긴함)

 

 

---

 

 

 

컴퓨터 구조를 배웠다면 우리는 CPU를 Pipeline으로 돌려서 실행시키는 것을 알 것이다.

또한 MultiProcessor의 경우 CPU 여러개를 돌린다고 생각해야 한다.

 

결국 먼저한 연산이 Hazard를 가져오지 않게 해야 한다는 말이다.

위의 Load X가 같은 X값을 가져오느냐? 또는 Store X가 정말 올바른 값을 저장하느냐?

 

결국 n개의 프로세스가 공유 데이터를 동시에 사용할 때

각 프로세스의 code segment에는 공유 데이터(shared memory)를 접근하는 코드인

critical section, 임계구역이 존재한다.

 

**임계구역은 Shared Memory 그 자체가 아니라 해당 Memory에 접근하는 프로세스의 code segment의 부분이다.

 

즉, 하나의 프로세스(스레드)가 critical section이 있다면 해당 작업 중에는 다른 프로세스(스레드)가 임계구역을 수행하지 못하도록 해야할 것이다.

다시 말해서 프로세스A가 해당 작업 중 CPU를 다른 프로세스가 넘겨받더라도 A가 작업중이라면

해당 Critical Section에 대한 접근을 할 수 없게 막아야 한다는 말이다.

 

 

 

그것이 바로 동기화 작업이다. 이 다음에서는 어떻게 동기화를 하는지 알아보자.

 

동기화 작업에는 아래 조건이 충족되어야 한다.

 

 

1. 임계구역 수행중인 프로세스가 있다면 다른 프로세스는 해당 임계구역을 수행해서는 안된다.

 

2. 임계구역 수행중인 프로세스가 없으면 프로세스는 해당 임계구역을 수행할 수 있다.

(동시에 임계구역을 수행하려고 하는 경우, 둘 다 수행하지 않는 상황도 발생한다)

 

3. 임계구역에 들어가려고 기다리는 시간이 너무 길어지면 안된다.

(다른 프로세스들이 계속 먼저 들어가버리면 해당 프로세스를 수행할 수 없다)

 

 

 

---

구현해보자면

 

아래 예시는 turn으로 자기 차례에만 들어갈 수 있게함.

하지만 무한대기가 될 수 있다. 

0번에 들어가서 turn이 1로 바뀌었지만 다시는 0에게 critical section을 접근하지 못하게 한다.

 

그래서 개선한 알고리즘이다.

flag가 생겼다.  flag는 해당 프로세스가 critical section에 들어가야하는 가? 를 결정한다.

프로세스가 critical section에 들어가기 위해

자신의 flag[i]를 true로 바꾸고 상대방의 flag[j]를 체크한다.

상대방의 flag도 true이면 해당 프로세스가 Critical Section에서 수행 중인 줄 알고 기다린다.

 

하지만 여기서도 문제가 생기는데

process A가 수행중이다.

flag를 true로 만들고  즉, 라인 2행 수행을 하자마자 CPU를 뺏겼다고 하자

process B는 자신이 들어가기 위해 flag를 true로 만들고 A의 flag를 확인했더니 true라서 대기하게 된다.

다시 프로세스 A에 CPU가 점유됐을 때 다시 A도 B의 플래그를 확인했더니 true다. 

결국 아무도 Critical section에 들어가지 않았지만 아무도 들어가지 못하는 상황이 발생한다.

 

그래서 해결하기 위해 또 개선하였다.

앞의 알고리즘을 합쳐서 flag와 turn을 같이 사용한다.

 

**Peterson's Algorithm

 

처음에 자신이 들어가겠다고 flag를 true로 하지만 

turn은 상대방 것으로 바꾸어 놓는다.그리고 현재 상대의 flag가 true이고 상대방 turn이라면 계속 기다린다.그렇게 되면상대방이 flag가 false거나 상대방 turn만 아니면 나는 critical section을 수행할 수 있다.그 후 내가 critical section을 빠져나올 때 내 flag를 false를 시켜 상대방이 들어올 수 있게 한다.

 

turn에 따라 교대로 들어갈 수 있게하고 flag로 아무도 들어가있지 않으면 turn에 관계없이 누구나 들어갈 수 있게 해서 무한 대기같은 상황을 막았다.

 

위 3가지 조건을 만족한다.

하지만  Busy Wait이다. Spin lock이다.

 

**쉬운 코드라고 생각하지만 처음 해내는 생각이 다 어렵다. 콜럼버스의 달걀과 같다.

 

이어서 다른 동기화 기법을 알아보도록 하자.