프로세스 동기화 (Process Synchronization)

공유 데이터 (shared data)의 동시 접근 (concurrent access)은 데이터의 불일치 문제 (inconsistency)를 발생시킬 수 있다. 일관성 (consistency) 유지를 위해서는 협력 프로세스 (cooperating process) 간의 실행 순서 (orderly execution)를 정해주는 메커니즘이 필요하다

목차

1. 데이터의 접근
2. Race Condition
3. OS에서의 Race Condition
4. Process Synchronization 문제
5. The Critical-Section Problem
6. Initial Attempts to Solve Problem
7. Synchronization Hardware

 

 

---

데이터의 접근

 

컴퓨터에서 연산을 할 때에는 항상 데이터를 읽어와서 연산을 하고, 연산 결과를 다시 어딘가로 저장하고 내보내도록 되어 있다.

 

 

---

Race Condition

 

만약 count를 플러스도 하고 마이너스도 했다면 원래 값이 되어야 하지만 마이너스만 반영된다. 이렇게 하나의 데이터를 여럿이 동시에 접근하게 되면 문제가 생긴다. 이러한 문제를 Race Condition, 즉 경쟁 상태라고 한다. 

 

Race Condition 문제는 정말 생기는 것일까 ? 

 

문제가 안 생긴다는 관점에서 이야기를 시작해보자. CPU가 한 개든 여러 개든 문제는 안 생긴다. count와 같은 데이터는 프로세스 내부에 있는 데이터이다. 프로세스는 자기 자신의 주소 공간에 있는 데이터만 접근할 수 있다. 따라서 서로 다른 프로세스 간에는 애초에 데이터를 공유할 수 없다.

 

하지만 문제는 운영체제가 끼어드는 경우이다. 이러한 경우는 CPU가 하나만 있어도 문제가 생긴다. 예를 들어 프로세스 A가 CPU에서 실행 중인 경우를 생각해 보자. 프로세스는 본인이 스스로 할 수 없는 일을 운영체제에게 부탁하는 system call을 한다. 프로세스 A가 system call을 하고 운영체제 내 데이터 값을 바꾸려던 찰나 자신의 CPU 할당 시간이 종료되어 CPU는 프로세스 A로부터 프로세스 B로 넘어갔다고 해보자. B 또한 system call을 했는데 우연히 A가 건드리던 똑같은 운영체제 내 데이터 값을 변경하는 상황이 발생했다면 Race Condition 문제가 발생할 수가 있다. 

 

 

---

OS에서의 Race Condition

" OS에서 race condition은 언제 발생할까 ? "

 

 

1) kernel 수행 중 interrupt 발생하는 경우

Interrupt handler VS kernel

 

 

 

2) process가 system call을 하여 kernel mode로 수행 중, context switch가 일어나는 경우

preempt a process  running in kernel ?

 

 

➳ 두 프로세스의 address space 간에는 data sharing이 없다.

➳ 그러나 system call을 하는 동안에는 kernel address space의 data를 access 하게 된다. (share)

➳ 이 작업 중간에 CPU를 preempt 해가면 race condition이 발생한다.

 

If you preempt CPU while in kernel mode,

 

 

3) multiprocessor에서 shared memory 내의 kernel data인 경우

CPU가 여러 개 있는 경우 생기는 문제점이다.

 

 

방법 1은 운영체제 전체에 lock을 걸어 혼자 독점하는 방법이다. 하지만 방법 2는 운영체제 내 각 데이터 별로 사용 중일 때 lock을 거는 방법이다. 따라서 여러 CPU가 운영체제를 수행 중이어도 해당 데이터를 건드리지만 않는다면 충분히 운영체제 코드를 동시에 실행할 수 있다.

 

 

---

Process Synchronization 문제

공유 데이터 (shared data)의 동시 접근 (concurrent access)은 데이터의 불일치 문제 (inconsistency)를 발생시킬 수 있다. 일관성 (consistency) 유지를 위해서는 협력 프로세스 (cooperating process) 간의 실행 순서 (orderly execution)를 정해주는 메커니즘이 필요하다.

 

➳ race condition

    • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황

    • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다.

 

race condition을 막기 위해서는 concurrent process는 동기화 (synchronize) 되어야 한다.

 

Example of a Race Condition

 

공유 데이터를 접근하는 코드를 critical-section이라고 부른다.

 

 

---

The Critical-Section Problem

➳ n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우에 발생한다.

➳ 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재한다.

➳ Problem

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

 

 

 

---

Initial Attempts to Solve Problem

➳ 두 개의 프로세스가 있다고 가정한다. 

➳ synchronization variable : 프로세스들은 수행의 동기화 (synchronize)를 위해 몇몇 변수를 공유할 수 있다. 

 

프로세스들의 일반적인 구조

 

 

critical section 앞(= entry section), 뒤(= exit section)로 어떤 코드를 붙여야 문제를 해결할 수 있을까 ?

다음은 동기화 문제를 해결해주는 알고리즘들을 살펴볼 것이다.

그전에 프로그램적 해결법의 충족 조건을 알아본다.

 

 

프로그램적 해결법의 충족 조건

➳ Mutual Exclusion (상호 배제)

    • 특정 프로세스가 critial section을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.

➳ Progress (진행)

    • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.

➳ Bounded Waiting (유한한 대기)

    • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.

 

🔮 가정

✔ 모든 프로세스의 수행 속도는 0보다 크다.

✔ 프로세스 간의 상대적인 수행 속도는 가정하지 않는다.

 

 

Algorithm 1

 

synchronization variable로 turn 변수를 사용한다. turn이 1이라면 상대방 차례로 바꾼 것이다. 반드시 한 번씩 교대로 들어가야만 하므로 단점도 존재한다. 프로그램적 해결법의 충족 조건을 보면 mutual exclusion은 충족하지만 progress는 충족하지 않는다. 

 

 

Algorithm 2

 

boolean 변수 flag를 활용해 들어가고 싶은 경우 깃발을 들어 의사를 알린다. 상대방의 깃발이 들려있는지 확인하고, 없다면 critical section에 들어갈 수 있다. 누구나 critical section에 들어가서 나올 때에는 깃발을 내려 다른 사람이 들어올 수 있도록 해준다. 프로그램적 해결법의 충족 조건을 보면 Algorithm 1과 마찬가지로 mutual exclusion은 충족하지만 progress는 충족하지 않는다. 깃발은 들고 critical section은 실행하지 않은 상태에서 CPU를 빼앗긴 경우, 새로 CPU를 잡은 다른 프로세스도 깃발을 들기 때문에 서로 끊임없이 양보하는 문제가 있을 수 있다는 것이다.

 

따라서 Algorithm 1과 Algorithm 2 둘 다 제대로 작동하지 않는다.

 

 

Algorithm 3 (Peterson's Algorithm)

 

깃발도 들고, turn 변수도 사용한다. 즉, 상대방이 깃발을 들고 있으면서 동시에 상대방 차례인 경우에만 기다린다. 프로그램적 해결법의 충족 조건을 모두 충족한다 ! 하지만 비효율적이라는 문제가 있다. 계속 critical section에 들어가지 못하는 경우에 불필요하게 계속 while문을 돌기 때문이다. 이를 busy  waiting 혹은 spin lock이라고 한다. 쓸데없이 바쁘게 기다리고, 자원을 낭비한다는 것이다. 

 

 

---

Synchronization Hardware

➳ 하드웨어적으로 Test & modify를 atomic 하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결된다.

 

 

lock이 true라면 애초에 while문을 읽어 내려갈 수가 없다. lock이 풀렸을 때 스스로 lock을 걸고 critical section을 실행해나갈 수 있다.

 

다음 글에서는 앞서 소개한 세 가지 알고리즘 방식처럼 코드를 직접 작성하지 않고, 좀 더 추상화시킨 process synchronization 문제 해결 방안을 알아본다.  이는 프로그래머로 하여금 도구를 가져다 좀 더 쉽고 효율적으로 문제를 풀 수 있도록 한다.

 

 

---

Reference

KOCW 운영체제 강의 (이화여자대학교, 반효경 교수님)