5. 프로세스 동기화

Process Synchronization 

---

이번 글에서는 프로세스 동기화에 대해 알아보겠습니다.

 

---

프로세스 동기화

• 프로세스 동기화의 필요성 

오늘 날 대부분 컴퓨터 시스템은 하나의 하드웨어 안에 여러 개의 프로세스가 존재할 수 있는 멀티테스킹 시스템/멀티프로세스 시스템입니다. 

하나의 하드웨어 안에서 동작하는 여러 프로세스들은 각각 독립적으로 동작하기 때문에 기본적으로는 프로세스 간 동기화가 전혀 이루어져 있지 않습니다. 이는 프로세스들이 공유 자원에 접근하려 할 때, 공유 자원의 integrity를 손상시킬 수 있기 때문에 문제가 발생합니다. 

따라서 공유 자원에 대한 동기적 접근시 데이터 무결성을 해치지 않기 위해 운영체제는 프로세스 동기화 (process synchronization) 매커니즘을 가지고 있습니다. 

---

경쟁 조건 Race Condition

race condition은 여러 프로세스들이 같은 데이터에 동시에 접근하거나 조작하려하는 상황을 의미합니다. 

• race condition의 문제 상황  
  1. 두 개의 독립적인 프로세스 Pi 와 Pj 가 count라는 하나의 변수에 동시에 접근하려 한다.
  2. preemption, interrupt 등으로 인해 하나의 프로세스(Pi)가 중단된 상황에서 context swtiching을 위해 Pi의 context 정보를 일시적으로 context saving을 한다. 
  3. Pj가 count 데이터를 write한다.
  4. Pi가 다시 돌아와 count에 접근하려고 하면 이미 Pj에 의해 변경된 값에 접근하게 된다. 
  5. 공유 데이터 count의 integrity (무결성)가 손상된다. 
• 위와 같은 race condition의 문제 상황을 방지하기 위해 process synchronization이 필요합니다. 

---

임계 구역 문제 Critical Section Probelm

Termimologies

• Critical Data  : 여러 개의 프로세스가 동시에 접근할 수 있는 데이터

• Critical Section  : 공유 데이터에 접근하는 코드 영역 (프로세스 코드 중 공유 데이터에 접근하는 영역) 
• Mutual Exculsion (상호 배제) :  2개 이상의 프로세스가 동시에 같은 공유 데이터를 접근하는 critical section 을 동시에 실행할 수 없게하는 것으로, race condition 방지하기 위한 기본 원칙 

이번 섹션에서는 mutual exclusion을 보장하기 위한 방식의 여러 버전에 대해 알아보겠습니다.

Mutual Exclusion Methods

1. mutual exclusion primitive 

각 프로세스마다 enterCS(Critical  Section)와 exitCS를 추가하여 CS에 진입하기 전에 다른 프로세스가 공유 데이터가 있는 critical section에 진입해 있는지 enterCS에서 검사하도록 합니다. 

즉, 공유 데이터에 접근하기 전에 해당 코드 영역에 하나의 프로세스만 진입할 수 있도록 입장 전 검사하는 방식입니다. 

그리고,  공유 데이터 사용을 마치고 critical section을 나오면서 exitCS에서 critical section 사용 가능해졌음을 다른 프로세스들에게 알립니다. 

• enterCS와 exitCS는 Mutul exclusion을 보장해야 합니다.
• progress requirement : critical section에 진입한 프로세스가 없다면 즉, 접근 가능한 상태라면 반드시 진입할 수 있게 해야 합니다.
• bounded waiting : 특정 프로세스의 critical section이 계속 밀리는 경우를 의미합니다. 이 경우, 진입 시도 횟수를 제한하여 일정 횟수 이상 진입을 시도한다면 적어도 한번은 진입할 수 있도록 해야 합니다.

2. mutual exclusion primitives version 1

turn 변수를 도입합니다. 이 변수는 0 또는 1 을 값으로 가집니다.

1. P0, P1 프로세스 둘 다 critical section에 접근하려고 한다. 
2. turn = 1이면 P0이 진입할 수 있고, turn = 0 이면 P1이 진입할 수 있다.

이 방식은 turn 변수로 mutual exclusion은 보장할 수 있지만 progress requirement는 해결할 수 없습니다. 

3. mutual exclusion primitives version 2

각 프로세스가 flag를 가지고 있습니다. P0은 flag[0]을, P1은 flag[1]을 갖습니다.

따라서 critical section에 진입하려는 프로세스는 다른 프로세스의 flag 상태를 검사하여 진입 가능 여부를 결정합니다. 

1. flag[i] = 1 은 프로세스 Pi 가 critical section에 진입해 있음 -> 진입 불가
2. flag[i] = 0 은 진입하지 않았음 -> 진입 가능 

이 방식은 mutual exclusion을 보장할 수 없습니다. 예를 들어 다음과 같은 상황이 있습니다. 

1. 초기에 두 flag가 모두 false
2. P0이 자신의 flag를 true (1)로 바꾸고 진입
3. P0이 사용 완료 후 flag를 false(0)으로 바꾸어야 하는데 그 전에 프로세스가 중단 
4. P1은 P0이 바꾸지 않은 flag = 1로 인해 critical section에 진입할 수 없다고 판단

3. mutual exclusion primitives version 3

version 2와 유사하지만 flag에 상태를 반영하는 순서가 다릅니다. 

enterCS에서 가장 먼저 자신의 flag에 상태를 반영한 뒤, 상태의 flag를 검사합니다. 

이 방식은 mutual exclusion을 보장할 수 있지만 역시나 다음과 같은 경우 progress requirement가 보장되지 않습니다. 

1. P0이 flag = true 로 자신의 상태를 표시하고 진입해있음을 표시한 상태에서 중단
2. P1도 진입전 flag=true로 바꿨지만 상태 flag가 1 인 상태로 중단되어 있기 때문에 진입 불가
3. P0 과 P1 모두 무한 루프를 돌게 됨 

4. Dekker's Algorithm

version3 과 유사한 골격으로 enterCS에서 자신의 flag를 검사한 뒤, 상태 flag를 검사하는데 여기에 turn 변수를 추가합니다. 

P0이 critical section을 사용하고 있는데 P1이 접근할때, turn 을 확인합니다. 그리고 turn = 1 이면 진입하지 않고, 0이 될때까지 자신의 flag=false로 바꾸고 계속 기다립니다. 

version 3에서 둘다 flag 만 true 이고 critical section을 사용하지 않는 경우 무한 루프에 빠지는 상황을 turn을 이용해 빠져나올 수 있게 한 방식입니다. 

5.  이외의 방식 

이외에도 mutual exclusion을 보장하기 위한 다양한 알고리즘이 존재하지만 수업에서는 다루지 않았기 때문에 무엇이 있는지만 알아보고 자세한 설명은 생략하도록 하겠습니다. 

• Dijkstra's 

• Kunth's

• Eisenberg and mcqurie's

• Lamport's

• Bakery

---

Hardware Instruction

지금까지 설명한 방식은 모두 소프트웨어 측면에서의 솔루션입니다. 그러나 소프트웨어 솔루션은 속도가 느리고, 이 역시 프로세스이기 때문에 실행 중 preemption이 일어날 위험이 있습니다. 따라서 보다 안정적인 하드웨어 측면의 솔루션을 활용하게 됩니다. 

Special Machine Instruction 

mutual exclusion을 위한 기계어 명령은 다음과 같습니다.

1. TS (test and set) instruction 

TS 인스트럭션은 target이 가리키고 있는 대상 (rv)에 true 값이 set 되면 원래 값을 return 합니다. 

atomic하게 실행되기 때문에 빠르고, preemption될 위험이 없습니다.  

TS 인스트럭션은 다음과 같은 mutual exclusion에 활용됩니다. 

1. lock 변수의 초기값은 false 
2. 진입을 시도하면 TS가 false를 반환할 때까지 검사하며 대기 
   1. lock = false 면 TS 가 false를 반환하여 critical section에 진입할 수 있음
   2. lock = true 면 TS 가 true를 반환하여 critical section에 진입하지 못하고, while문을 돔 
3. critical section 사용을 마친 프로세스는 exitCS에서 lock을 다시 false로 바꿈 

이 방식은 mutual exclusion은 해결할 수 있지만 특정 프로세스의 진입이 계속해서 밀릴 수 있습니다. 

2. Swap()

swap() 함수는 두개의 포인터 값을 인자로 받아 두 값이 가리키는 값을 교환합니다. 

각 프로세스마다 key와 lock이라는 local 변수를 가지고 있어야 합니다.

1. 프로세스가 critical section에 진입하려고 하면 key = true로 바꿔줍니다. 
2. key=true인 동안 lock 값과 계속 swap 을 시도하다가 lock이 false가 되면 key가 false로 swap 되면서 반복문을 탈출하여 critical section에 진입할 수 있게 됩니다. 
3. critical section 사용을 완료하고 exti 하면서 lock을 false 합니다. 이 변화가 critical section 진입을 대기하는 프로세스의 swap 함수에 영향을 주어 다음 프로세스가 진입할 수 있도록 합니다. 

---

 

이번 글에서는 프로세스 동기화, mutual exclusion method (software version, hardware version)에 대해 알아보았습니다. 

다름 글에서는 이번 글에 이어 mutual exclusion method에서 발생할 수 있는 문제점과 그 해결방법에 대해 알아보도록 하겠습니다. 

감사합니다 :) 

---

References

• 성균관대학교 소프트웨어대학 엄영익 교수님 <운영체제> 수업