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

프로세스 동기화

# 데이터의 접근
# OS에서 race Condition은 언제 발생하는가?
# Process Synchronization 문제
# 프로그램적 해결법의 충족 조건
# Algorithm 1
# Algorithm 2
# Algorithm 3

---

✍️ 본 포스팅은 이화여자대학교 반효경 교수님의 "운영체제" 강의를 들으며 정리한 내용입니다.

 

---

＊데이터의 접근

1. 어떤 데이터가 저장되있는 위치에서 저장된 데이터를 읽어온다
2. 연산을 한다
3. 연산된 결과를 다시 원래 위치에 저장한다

- Race Condition

• 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
• 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐

- race condition을 막기 위해서는 동시 접근은 동기화 되어야 한다.

---

-> 다시 아까 예제를 보면

-> 위처럼 누가 먼저 읽어왔는지 등에 따라 synchronization 의 문제 발생 가능성이 생긴다.

---

＊OS에서 race Condition은 언제 발생하는가?

1. kernel 수행 중 인터럽트 발생 시

• 중요한 작업을 하는 도중이면 interrupt를 disable 시켰다가, 작업이 끝나면 인터럽트 수행해서 해결

2. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우

• 두 프로세스의 address space 간에는 data sharing이 없음
• 그러나 system call 하는 동안에는 kernel address space의 access하게 됨 (share)
• 이 작업 중간에 CPU를 선점해가면 race condition이 발생

• 위 그림에서 P의 A에서 Count 1증가시키고, Cunel에서 1증가 시켜서 2가 증가해야하지만
• Cunel에서 증가시킨건 반영이 안되는 문제
• 해결책 : 커널 모드에서 수행 중일 때는 CPU를 선점하지 않는다.
  -> 커널 모드에서 사용자 모드로 돌아갈 때 선점

3. Multiprocessor에서 shared memory 내의 kernel data

• 위 예제들과 달리, CPU 작업 주체가 여러 개 있고, 동일 메모리에 접근해서 발생하는 문제
• 어떤 CPU가 마지막으로 count를 store 했는가? -> race condition
  -> multiprocessor의 경우 interrupt enable/disable로 해결되지 않음(두 프로세스가 동시접근하니까)
• (방법 1) 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
  (다른 CPU는 커널에서 다른작업들 못하니 비효율적이다)
• (방법 2) 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법

---

＊Process Synchronization 문제

- 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터 불일치 문제를 발생시킬 수 있다

- 일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)를 해주는 메커니즘이 필요

---

＊The Critical-Section Problem

• n 개의 프로세스가 공유 데이터를 동시에 사용하기 원하는 경우
• 각 프로세스의 code segment에는 공유데이터를 접근하는 코드인 critical section이 존재
• Problem
  • 한 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 함

---

＊Initial Attempts to Solve Problem

• 두 개의 프로세스가 있다고 가정 P0, P1
• 프로세스들의 일반적인 구조

• 프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있다 -> synchronization variable

---

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

1. Mutual Exclusion (상호 배제)

• 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 해당 critical section에 들어가면 안됨

2. Progress (진행)

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

3. Bounded Waiting (유한 대기)

• 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지, 다른 프로세스들이 critical section에 들어가는 회수에 한계가 있어야 한다. (우선순위 높은 2개만 번갈아 들어가는 상황이면, 3번째부터는 모두 starvation이 발생할 수 있음 -> 이걸 방지하기 위한 목적)

※ 가정

• 모든 프로세스의 수행 속도는 0보다 크다
• 프로세스들 간 상대적인 수행 속도는 가정하지 않는다.

---

＊Algorithm 1

• turn : 누구 차례인지 나타내는 변수
• 0번에서 시작하게되면 critical section에 들어갔다 나와서, turn을 바꿔준다.
• 문제점 : 프로그램적 해결법의 충족 조건의 Progress 조건을 만족시키지 못한다.
  즉, 위 예제를 보면 turn 1번 차례가 되려면 turn 0번이 반드시 수행되어야한다. 1번을 사용하고 싶을 때, 아직 0번을 사용하지 않았고 앞으로도 사용하지 않는다면, 1번도 영원히 사용할 수가 없다.

---

＊Algorithm 2

• flag : 한 프로세스가 critical section에 들어가고자하는 의중을 나타내는 boolean 타입 변수
  각 프로세스마다 가지고 있다.
• 한 프로세스가 critical section에 들어가기 직전에 다른 프로세스가 flag가 true이면,
  양보하고 끝날 때까지 기다린 후 진입한다.
• 문제점 : 둘 다 2행까지 수행 후, 끊임없이 양보하는 상황이 발생 가능하다.

---

＊Algorithm 3 (Petersion's Algorithm)

1. flag를 true로 하여, critical section에 들어갈 의사를 표현한다.
2. turn을 상대방 turn으로 바꿔준다.
3. 상대방이 critical section에 들어갈 의사가 없거나, 있다고하더라도 이번 턴이 상대가 아니라 내 차례면
   critical section에 진입한다.
4. critical section에서 빠져나오면 flag를 false로 바꿔 상대방이 진입 가능하도록 만들어준다.

• 문제점 : Busy Waiting(=spin lock)!
  한 프로세스가 critical section에 이미 진입해있고 다른 프로세스가 진입을 시도할 때, 기다리면서 계속 들어갈 수 있는지 while문을 돌면서 끊임 없이 체크를 할 것이다. 즉 기다리는 동안 CPU와 memory를 쓸데없이 소비한다는 문제

---

＊Synchronization Hardware

• 하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 위 문제들은 간단히 해결 가능하다.

a 가 0이었다고 하면 0을 읽고나서, a를 1로 바꿔준다. a가 원래 1이었으면, 1을 읽고나서, a를 1로 바꾼다(그대로).

• Mutual Exclusion with Test & Set

• lock이 거짓일 때는, lock을 true로 걸고 진입한다(코드에는 안나와있는데, 교수님이 "lock이 아무도 안걸려있으면 lock을 걸고 진입한다"라고 말씀하신 것을 이렇게 이해한대로 적었습니다,,).
• 만약 lock이 true였으면 Test_and_Set(lock)이 참으로 읽혀 while문 돌며 계속 기다리게 된다.
• 빠져나올 때 lock을 false로 풀어준다.