[운영체제] - 30강. 프로세스 동기화

이 글은 한빛미디어 '혼자 공부하는 컴퓨터 구조 + 운영체제'를 공부하고, 추가적인 부분을 찾아 정리한 내용입니다.

---

운영체제의 프로세스 관리 서비스 중 가장 중요한 두 가지는 스케줄링과 동기화이다.
그렇다면 동기화란 무엇일까??

---

● 동기화 (Synchronization)

 

- 멀티 프로세스 혹은 멀티 스레드가 공유하는 자원의 일관성을 유지하는 것

- 두 개 이상의 프로세스(혹은 스레드)가 공유 자원(Shared Data)에 동시 접근하면 데이터 불일치가 발생할 수 있기 때문에 데이터 일관성을 유지하기 위한 매커니즘이다.

---

 

● 고전적 동기화 문제 (Classical Problems of Synchronization)

- 동기화와 관련된 유명한 고전적 문제로 3가지의 경우가 있다.

 

1) 생산자 - 소비자 문제 (Producer-Consumer Problem (Bounded-Buffer Problem))

- 생산자 스레드와 소비자 스레드, 그 사이에 공유 버퍼가 있다고 가정한다.

- 둘 이상의 생산자가 버퍼의 비어 있는 공간에 동시에 데이터를 만들어 넣거나, 둘 이상의 소비자가 동시에 동일 버퍼의 데이터를 사용하려고 한다면 문제가 발생한다. (레이스 컨디션 발생)

- 또는 공간이 꽉 찬 상태에선 생산자는 반드시 소비자가 데이터를 사용하기를 기다려야 하고, 버퍼가 빈 상태에서 소비자는 생산자가 버퍼를 채우기를 기다려야 한다.

 

- 문제 발생 원인 : 소비자가 생산자의 작업이 끝나기도 전에 총합을 수정하고, 반대로 생산자도 소비자의 작업이 끝나기 전에 총합을 수정하기 때문. (생산자와 소비자간의 동기화가 이루어지지 않아 생기는 문제)

- 해결 방안 : 락을 걸고 푸는 용도, 자원의 개수를 카운팅하는 용도로 세마포어 변수를 사용

 

 

2) 읽기 - 쓰기 문제 (Readers - Writers Problem)

- 한 프로세스가 데이터를 수정하는 작업을 수행할 때 다른 프로세스가 접근하면 안되고, 읽는 작업은 여러 프로세스가 동시에 수행 가능하도록 하는 문제.

- 데이터에 대해 하나의 lock을 사용하게 되면 데이터의 일관성을 지킬 수는 있으나, 여러 프로세스가 동시에 읽을 수 있는 상황에서도 한 프로세스만 접근하도록 강제하는 것이므로 비효율적인 상황이 발생한다.

- 수정하려는 프로세스가 없다면 모든 대기 중인 Reader들의 접근은 허용하고, Writer는 Reader가 없는 경우에만 접근할 수 있다. 또한 Writer가 접근 중이면 Reader들은 접근할 수 없다.

 

- 문제 발생 원인 : 프로세스가 실행되어야 하는 순서와 각 프로세스의 사용 가능 여부를 판단해야 하는 상황. (Reader와 Writer가 서로 동기화 되지 않으면 각 프로세스의 실행순서도 뒤죽박죽)

 

- 해결 방안 :  n개의 Reader가 기다리고 있다면, 제일 처음 Reader만 Wrt 세마포어에 넣고 나머지 n-1개의 Reader는 mutex 세마포어 큐에 넣어둔다. 단 해당 해결책은 기아(Starvation) 현상의 가능성이 있기 때문에, 큐에 우선순위를 부여하여, 일정 시간이 지나면 자동으로 Write or Read가 되도록 해야한다.

 

3) 철학자들의 만찬 문제 (Dining-Philosophers Problem)

- 5명의 철학자가 원탁에 둘러 앉아 있고, 젓가락은 각 철학자의 사이에  5개가 놓여있다고 가정한다.

- 각 철학자는 식사하기를 원하고, 철학자는 반드시 양쪽 젓가락을 모두 집어야 한다.

- 만약 모든 철학자가 왼쪽의 젓가락을 집는다면, 더 이상 아무런 작업도 수행할 수 없는 교착상태(데드락 : Dead Lock)에 빠지게 된다. (이건 이후의 글에서 자세하게 다룸)

 

---

 

 

● 경쟁 상태 (레이스 컨디션 : Race Condition)

- 여러 프로세스들이 동시에 데이터에 접근하는 상황에서, 어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라질 수 있는 상황으로, 이런 공유 데이터의 동시 접근(Concurrent Access)은 데이터의 불일치 문제를 발생시킨다.

---

★ 대표적 레이스 컨디션 사례 3가지

 

1) 커널 모드로 수행 중 인터럽트가 발생하는 경우

- 의도한 동작 : count++과 count-- 가 모두 반영되어 count가 초기값을 유지하는 것.

- 오류 동작 : Load를 한 후에 인터럽트가 발생하는 경우, 인터럽트 서비스 루틴의 결과는 반영되지 않고 count++만 반영.

 

- 해결 방안 : 커널 모드의 수행이 끝나기 전에는 인터럽트를 받지 않도록 하는 방법 (disable/enable)으로 문제 해결.

 

 

2) 프로세스가 시스템 콜을 호출해서 커널 모드로 수행 중인데 문맥교환(Context Switch)가 발생하는 경우

- 두 프로세스의 주소 공간에서는 데이터를 공유하지 않지만, 시스템 콜을 수행하는 동안에는 둘 다 커널 주소 공간의 데이터를 접근하게 된다. 이 때 커널 주소 공간에서 작업을 수행하는 도중 CPU를 빼앗으면 레이스 컨디션이 발생한다.

 

- 해결 방안 : 커널 모드를 수행 중일 땐 CPU가 선점(Rreempt) 되지 않도록 하고, 커널 모드에서 유저 모드로 돌아갈 땐 선점 되도록 하여 문제 해결 .

 

3) 멀티 프로세서에서 공유 메모리 내의 커널 데이터에 접근하는 경우

 

- CPU가 여러개인 상황에서 메모리 접근을 할 경우, 동일 메모리 주소에 접근하여 레이스 컨디션이 발생할 수 있는 상황.

- 싱글 프로세서인 경우라면 1번과 같이 인터럽트 disable/enable 방법으로 해결할 수 있지만, 멀티 프로세서인 경우라면 인터럽트 제어로는 해결할 수 없다.

- 한 번에 한 CPU만 커널에 들어갈 수 있도록 하는 방법이 있지만 비효율적이다. 만약 두 프로세서가 서로 다른 데이터에 접근하여 레이스 컨디션의 가능성이 없음에도 불구하고 한 번에 한 CPU만 커널에 들어갈 수 있기 때문이다.

 

- 해결 방안 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대해서만 lock/unlock을 하는 방식으로 해결.

 

---

 

● 임계 구역 (크리티컬 섹션 : Critical Section)

- 코드 상에서 레이스 컨디션이 발생할 수 있는 특정 부분. 공유 데이터를 접근하는 코드 부분을 말한다.

- 소프트웨어적 해결 방법과 하드웨어적 해결 방법이 있다.

 

○ 소프트웨어적 해결 방법

- 코드를 작성한 개발자가 직접 크리티컬 섹션을 관리하는 방법으로, 3가지 조건을 만족해야 한다.

1. 상호 배제 (Mutual Exclusion)
   - 이미 한 프로세스가 크리티컬 섹션에서 작업 중이라면 다른 모든 프로세스는 크리티컬 섹션에 진입하면 안된다.
2. 진행 (Progress) - 데드락(Dead Lock) 회피
   - 크리티컬 섹션에서 작업중인 프로세스가 없을 때, 크리티컬 섹션에 진입하고자 하는 프로세스가 존재하는 경우 진입할 수 있어야 한다.
3. 한정 대기 (Bounded Waiting) - 기아(Starvation) 현상 회피
   - 프로세스가 크리티컬 섹션에 들어가기 위해 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 크리티컬 섹션에 들어가는 횟수에 한계가 있어야 한다. 즉 무한정 기다리는 프로세스가 없어야 한다.

---

 

○ 동기화 알고리즘 (Synchronization Algorithms)

- 임계 구역 문제 (CSP : Critical Section Problem)을 해결하기 위한 대표적 3가지 알고리즘이 있으며, 두 개의 프로세스 Pi 와 Pj, 공유하는 공통 변수가 존재한다고 가정한다.

 

 

[Algorithm 1]

- 크리티컬 섹션에 들어갈 프로세스가 어떤 프로세스인지를 한 변수로 나타내어 일치하는 프로세스만 진입하도록 하는 방법.

- turn 이라는 공유 변수를 만들어 프로세스가 들어가면 turn 공유변수를 변경시켜서 접근

 

- 한계점 : Pi는 빈번하게 크리티컬 섹션에 진입하고 Pj는 1번만 접근한다고 가정할 때, Pi가 여러번 접근 하고 싶어도 Pj가 접근해주어 다시 변경 해주지 않는 한 Pi는 접근할 수 없다. 때문에 위 3가지 요건중 Progress를 만족시키지 못하므로 좋은 알고리즘은 아니다.

 

 

[Algorithm 2]

- 특정 프로세스가 크리티컬 섹션에 진입할 준비가 되었다는 것을 나타내는 변수를 두어, 다른 프로세스가 크리티컬 섹션에 진입하려고 한다면 현재 프로세스는 기다리는 방법.

 

- 한계점 : 플래그를 설정하고, 나의 플래그와 프로세스의 플래그를 검사하여 크리티컬 섹션에 접근하는 방식이지만, 두 프로세스가 flag = true를 수행하고 나면 두 프로세스 모두 무한히 크리티컬 섹션에 진입하지 못하고 기다리는 상황이 발생한다. 이 또한 Progress를 충족시키지 못하는 알고리즘.

 

 

[Algorithm 3]

- 위의 1,2 알고리즘을 합쳐놓은 개념으로, 수학자 개리 피터슨의 이름을 따 피터슨 알고리즘(Peterson's Algorithm)이라고 한다. turn 변수와 flag 변수를 동시에 사용한다.

- 과정 :  Pi 프로세스에 대해서, Pi는 flag[i] = true로 바꾸면서 크리티컬 섹션에 진입하려 한다. 그리고 turn = j 로 바꿔주면서 상대방이 들어가게 한다. 만약 상대방(Pj)이 들어가고 싶고 (flag[j] == true), 현재 상대방이 크리티컬 섹션에 들어가 있다면 (turn == j) Pi는 기다린다. 그렇지 않으면 Pi가 들어간다. 이후 크리티컬 섹션을 빠져나오면 들어가고 싶지 않다고 flag[i] == false로 변경한다.

 

- 이 방식은 위의 3가지 요건을 모두 만족하지만, 크리티컬 섹션 진입을 기다리면서 계속 CPU와 메모리를 사용하는 바쁜 대기(Busy Waiting)의 문제점이 있다.

 

---

 

○ 하드웨어적 해결 방법

 

- Tree and Set

- 동기화 알고리즘 2번이 동작하지 않는 이유는 읽고 쓰는 작업이 서로 다른 명령에서 이뤄지기 때문인데, 만약 읽기와 쓰기가 하나의 명령에서 이루어진다면 프로그램적으로 간단하게 코드를 작성 할 수 있다.

- 하지만 이러한 하드웨어적 명령어는 bounded waiting 조건을 만족하지 못하는 단점이 있다. 이를 해결하기 위해 waiting array라는 배열을 추가로 사용할 수 있다.

---

※ 참고자료

 

https://rebro.kr/176

[운영체제(OS)] 6. 프로세스 동기화(Process Synchronization)

 

https://sihyung92.oopy.io/os/6#4401f752-9c38-4f82-b427-840bf5c2c920

프로세스 동기화