운영체제 - 반효경 #6 Process Synchronization

# 6-1 Process Synchronization 1

Initial Attempts to Solve Problem

• 공유 데이터에 그냥 접근하게 할 순 없지
• 공유 데이터에 접근하기 전, entry section 만들어서 lock 걸고
• Critical section 끝나면 exit section 으로 unlock

 

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

Mutual exclusion

• 여러 프로세스 동시 접근 불가하게
• 모든 프로세스의 접근을 막음

Progress

• Mutual exclusion 을 잘못 구현하면 아무도 critical section 에 없는데 어떤 프로세스도 접근할 수 없는 상황을 초래할 수 있음
• Progress는 위 문제 발생하지 않도록, critical section이 비어있을 때 한 프로세스가 사용할 수 있게 해줌

Bounded waiting

• 특정 프로세스가 critical section 에 못 들어가고 오래 기다릴 때 starvation 안 생기게
• 애초에 이런 문제들은 CPU를 빼앗기기에 생기는 문제임
• CPU가 단일 인스트럭션만 실행한다면 이런 문제는 발생하지 않겠지
• 근데 고급언어의 문장들이 단일 인스트럭션이 아니기에 작업 도중 CPU를 빼앗길 수 있어서 문제 발생

 

Algorithm 1

Turn

• 누구 차례냐
• Turn 기준으로 critical section 에 접근

문제점

• 프로세스 a 는 critical section 에 빈번하게 들어가고 싶고, 프로세스 b는 한 번만 들어가고 더 이상 안 들어간다고 하면
• 프로세스 a 도 상대방인 프로세스 b 가 더 안 들어가서 turn 을 바꿔주지 않기 때문에 영원히 들어갈 수 없음

 

Algorithm 2

• Flag 로 critical section 접근을 구별

문제점

• 프로세스 A가 본인 flag 를 든 상태에서 CPU 뺏기면
• CPU가 프로세스 B에 넘어가고, B가 flag 든 상태에서 critical section 에 아직 안 들어갔다?
• 근데 while 문 접근하게 되면 A와 B 모두 flag 를 들고 있어서 critical section 에 아무도 못 들어가게 됨

 

Algorithm 3

• Turn, flag 모두 활용
• 프로세스 A가 critical section 에 들어가겠다고 flag 를 true 로 변경하며 의사 표현을 함 + 프로세스 B의 turn 을 j로 변경
• Flag = 의사 세팅하고
• Turn = 순서를 정하는
• 둘이 동시에 들어가려 할 때만 두 가지 조건을 만족시키는지 확인 후 critical section 에 접근하도록
• 둘이 동시에 못 들어가지만 아무도 없을 땐 하나만 들어갈 수 있게,
• 특정 프로세스만 너무 오래 기다리지 않게 하는 알고리즘
• 최적화된 코드이긴 하나, busy waiting 문제가 있긴 함

Busy waiting

• Spin lock
• Lock 을 계속 걸어서 다른 프로세스의 접근을 막는
• 내가 CPU 잡아서 while 돌고 있을 때, CPU와 메모리를 계속 사용하며 wait 하기에 낭비의 문제가 생길 수 있음
• CPU는 하나의 인스트럭션이 끝나면 빼앗길 수 있는 가능성이 생기기에 이런 알고리즘을 사용

 

Synchronization Hardware

• 데이터를 읽고 쓰는 걸 하나의 인스트럭션으로 처리할 수 없기에 data sync 문제가 발생
• 하나의 인스트럭션이 끝나면 CPU를 빼앗길 수 있으니까

• 그래서 데이터 읽고 쓰기를 하나의 인스트럭션으로 처리 = test and set
• 원래 값 읽어낸 후 세팅하는 과정이, 한 번에 진행되기에 atomic
• Test and set instruction 실행하면 Peterson’s algorithm 처럼 복잡할 필요 없음

• While(test and set(lock)) = 이미 사전에 락이 걸려있는지 확인
• Test and set 통과하면 lock = 0 ➡️ lock = 1 로 바뀌면서, critical section 으로 접근 가능
• Lock 을 걸고 푸는 과정을 통해 atomic 하게 실행 가능

---

# 6-2 Process Synchronization 2

Semaphores

• 일종의 추상 자료형
• 정수값을 가질 수 있음
• Operation (연산) 필요
  • P 연산
  • V 연산

• 락을 걸고 풀 때 semaphore 통해 간단히 구현 가능
• Semaphore 가 공유자원 획득 / 반납 처리를 해줌
  • 공유자원 획득 = p 연산 = 자원을 가져간다
  • 공유자원 반납 = v 연산 = 자원 다 사용하고 나면 다시 돌려주는

락의 관점에서 바라보는 semaphore

• P 연산 – 락을 걺, 자원이 있으면 1개 가지고 감(busy-wait 문제는 발생하긴 함)
• V 연산 – 락을 풂, 자원을 반납

 

Critical Section of n Processes

• Semaphore 통해 간단한 프로그래밍 가능
• P 연산 = while 돌면서 CPU 계속 소비하면서 대기하는, busy-wait 발생 가능성 있음(자원 낭비)

 

Block / Wakeup Implementation

• 지금 semaphore 획득 못하면 그 프로세스를 block 시키고
• 누군가 semaphore 쓰고 반납하면 block 된 프로세스 중 하나를 wake 시킴

• Semaphore 를 기다리며 잠들어 있는 프로세스들의 PCB를 semaphore 변수 큐에 줄줄이 연결시킴

 

Implementation

• 여기서의 s = semaphore
• S.L = semaphore list

P 연산

• Block 도 해줘야
• 여기선 s 값을 다 마이너스(-)해주고 잠듦(block) = 자원을 쓰고 싶어 대기하는 상태

V 연산

• Wakeup 도 해줘야
• 여기서 s 가 ++ 라는 말은 현재 기다리는 프로세스 없이 자원을 쓰고 있는 상태라는 뜻

 

Which is better?

Block–wakeup 이 더 효율적임

• 공유자원을 얻고자 loop 도는 동안, CPU가 불필요하게 낭비되는 현상을 막을 수 있음
• 근데 얘도 overhead 가 있음 : ready ➡️ block 케이스 혹은 block ➡️ ready 케이스로 상태 변경 시 overhead 발생
• Critical section 길이가 짧으면 busy-wait 가 효율적일 수도 있음

 

Two Types of Semaphores

자원의 개수가 하나인 경우

• 락을 걸고 풀 때
• Binary semaphore

자원의 개수가 여러 개일 때

• 여분이 있으니 남은 걸 가져다 쓸 수 있음
• Counting semaphore

 

Deadlock and Starvation

Deadlock

• 상대방이 가진 걸 기다리며, 내 것은 내놓지 않는 현상
• 자원 획득 순서를 정해주면 문제 해결 가능

 

Dining-Philosophers Problem

• Starvation / deadlock 모두 발생 가능

---

# 6-3 Process Synchronization 3

Algorithm 1

 

Synchronization Hardware

 

Semaphores

Semaphore

• 추상 자료형
• 정수를 가질 수 있음
• P 연산 / V 연산이 있음

P 연산

• Semaphore 변수인 s 의 값을 1 감소시키며 자원 획득

V 연산

• 자원 반납
• P 연산 / V 연산 : 1개의D 데이터(mutex)에 대한 락에 활용될 수 있음

 

Block / Wakeup Implementation

 

Implementation

 

Classical Problems of Synchronization

 

Bounded-Buffer Problem

생산자 프로세스

• Producer
• 공유 버퍼에 데이터 하나 만들어 집어넣는 역할

주황색 버퍼

• 데이터가 들어있는 버퍼
• 생산자가 데이터를 만들어 넣어 놓은 상태

 

소비자 프로세스

• consumer

비어 있는 버퍼

• 처음부터 비어 있거나, 생산자가 데이터를 넣어 놨으나 소비자가 가져가서 빈 상태

 

버퍼 동시 접근 문제

• 여러 생산자가 동시에 도착해, 비어 있는 하나의 버퍼를 동시에 쓰고, 동시에 데이터를 넣으려 하면 sync 문제 발생
• 공유 버퍼에 락을 건 후, 하나의 생산자 or 소비자가 공유 버퍼에 접근해 데이터를 사용할 수 있게 해야

버퍼의 유한성

• 생산자가 도착해 버퍼 n 개를 다 채워 넣으면 그 다음 생산자가 도착했을 때 데이터를 채워 넣을 수 있는 버퍼가 없어짐
• 생산자 입장 : 비어 있는 버퍼 필요
• 소비자 입장 : 앞서 여러 소비자들이 데이터가 있는 버퍼들에서 자원을 다 꺼내 버리면 데이터를 가져갈 수 없음

 

Shared data

• 접근하려면 락을 걸고 푸는 작업 필요, 이를 위해 semaphore 변수 필요

자원 개수 카운팅

• Mutual exclusion
  • 데이터 1개를 다루는 경우
  • 생산자 입장
  • 락을 걸고 풀 때 생산자 입장에서 자원의 개수 = 비어 있는 버퍼 개수
• Resource count
  • 데이터 여러 개 다루는 경우
  • 소비자 입장
  • 소비자 입장에서 자원의 개수 = 내용 있는 버퍼 개수

Mutex

• 공유 버퍼에 1개 프로세스만 접근할 수 있게 함

Producer

1. P(empty) = 빈 버퍼가 있다면 빈 버퍼 획득
2. P(mutex) = 빈 버퍼에 락을 걸고
3. Add x to buffer = 빈 버퍼에 데이터 넣고
4. V(mutex) = 데이터 넣은 버퍼에서 락 해제
5. V(full) = 내용이 들어간 버퍼 개수 + 1

Consumer

1. P(full) = 내용이 들어 있는 버퍼가 있다면(생산자가 데이터 하나 만들어서 버퍼에 넣고, 내용 있는 버퍼 개수 + 1 될 때까지 기다림)
2. … 이후 로직 실행
3. V(empty) = 비어 있는 버퍼의 개수 + 1

 

Readers-Writers Problem

Read

• 여러 명이 동시에 접근해도 sync 문제 없음

Write

• 한 명만, 배타적, 독점적

DB

• DB 에 락을 걸기 위해 small DB라는 binary semaphore 사용

Mutex

• Readcount라는 변수에 대해 락을 걸 땐 mute라는 binary semaphore 사용

Reader

• 얘도 writer 같은 로직을 타고, 락을 걸면 안됨
• 근데 얘도 락이 필요하긴 함, read 중인데 writer가 접근할 때 락이 없으면 막 들어와 써버리니까

Readcount

• 공유 변수
• 현재 읽고 있는 프로세스 수
• 최초에 read를 시작한 프로세스가 있다면(내가 읽으려는 최초의 변수) 그 때 락을 걸면 되니,
• 그 다음에 read 하는 다른 프로세스는 락을 걸 필요가 없음

Readcount == 0

• 다 읽어서 내가 마지막으로 빠져나가는 프로세스라면 락을 풀어줘야

이 코드 상의 로직

• Reader가 락을 건 상태에서 writer가 대기하고 있는데,
• 다른 reader들이 우르르 들어온다면 writer는 모든 reader가 끝날 때까지 계속 기다려야 함 = starvation

근데 이 코드를 개선해서

• Reader / writer의 순서를 보장해줄 수 있게 보완한다면 자원을 보다 효율적으로 사용할 수 있게 됨

 

Dining-Philosophers Problem

• Initially all values are 1 = 한 명만 먹을 수 있음
• 젓가락 한 쌍을 잡아야 식사 가능

문제점

• 이 소스는 deadlock 위험이 있음(모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버리면 아무도 먹을 수 없음)
• 철학자가 동시에 배가 고파지고 특정인들이 계속 먹는다면 그 사이에서 젓가락 한 짝을 얻을 수 없는 철학자는 계속 굶어야

• self[5] = 0; 젓가락 두 개를 잡을 수 있는 권한을 가진 인물의 수
• self[3] = 1; 3번 철학자는 젓가락 두 개를 다 잡을 수 있다
• state[5] : 철학자의 상태
• Mutex = 락 / 옆의 철학자가 나(또다른 철학자)의 상태를 바꿀 수 있다 = 공유 변수
• test(i) : 젓가락을 잡을 권한이 있는지 확인
• v(self[i]) : 주변 철학자가 밥 안 먹고, 내가 배가 고프면, 내가 젓가락을 잡을 권한을 얻는 연산
• self[i] = 1 : 젓가락 두 개를 잡을 권한 생김

여기서의 Semaphore

• 자원의 개수를 카운팅
• 초기 값이 얼마냐를 두고 보통 일을 하는데
• 여기서는 젓가락 두 개를 잡을 권한을 처음에 = 0 으로 두고,
• test 에서 조건 만족 시 = 1 로 바꾸기에 semaphore 의 개념과 약간 맞지 않지만 큰 틀의 관점에선 맞음

 

Monitor

• 프로그래밍 언어 차원에서 문제 해결
• 어떤 객체 중심으로 operation이 정의되는 개념처럼,
• 내부의 procedure를 통해서만 공유 데이터 개념에 접근할 수 있게 모니터 내부에 공유 변수 선언 후(= shared variable declarations),
• 모니터 내의 하나의 프로시저만 작동하도록

• Monitor 안의 procedure를 통해서만 공유 데이터에 접근하도록
• Monitor가 원천적으로 내부의 procedure는 동시에 여러 개 실행될 수 없게 통제하는 권한을 줌 = 락을 걸 필요가 없음
• 모니터는 모니터에 대한 동시 접근을 허락하지 않음
• 모니터가 알아서 하나의 프로세스만 모니터에 접근할 수 있게 통제함
• Semaphore와 달리, 락을 걸 필요가 없다는 게 큰 장점

Semaphore

• 자원의 개수 세는 기능 필요
• 자원이 있으면 접근 가능하게, 자원이 없으면 불가하게 등을 확인

모니터

• Semaphore처럼 condition variable이 자원이 있으면 바로 접근하게 해주고, 없으면 기다리게 하는 그런 역할을 함

 

Bounded-Buffer Problem

• Semaphore ➡️ monitor 버전으로 conversion
• 모니터에서는 락을 걸거나 풀 필요 없음
• 공유 버퍼가 모니터 안에 정의되어 있어서, 생성자 / 소비자 들 중 하나의 프로세스만 모니터 내부에서 활성화됨
• ➡️ 굳이 락을 걸지 않아도 다른 생성자나 소비자가 접근하는 문제를 고민할 필요 없음

---

# 6-4 Process Synchronization 4 (Concurrency Control)

 

Semaphores

 

Classical Problems of Synchronization

 

Monitor

• 락을 모니터가 관리해주기에 내가 락을 걸고 풀 필요가 없음

Condition variable

• wait() 연산 : 어떤 프로세스를 잠들게 하기
• signal() 연산 : x 를 다 쓰고 난 후 잠든 프로세스가 있다면 그 중 하나를 깨워주기

 

Bounded-Buffer Problem

생산자 프로세스

• 버퍼에 공유 자원을 넣어주는

소비자 프로세스

• 버퍼에서 공유 자원을 가져가는

• Semaphore 와 monitor 비교

Mutex

• Semaphore 변수
• 락을 걸고 풀어주는 역할 vs 모니터는 락을 자동 관리해줌
• 어떤 값을 가지고 진행 vs 모니터는 값이 아닌 조건을 개발자가 필터링해서 진행

모니터

• 동시 접근을 막음

Semaphore

• 자원 획득 위해 프로그래머가 p 연산 / v 연산을 직접 해줘야

Semaphore 와 모니터

• 목적이 아예 다름

 

Dining Philosopohers Example

• 모니터 버전의 철학자가 밥을 먹는 문제

state[i]

• 모니터 안의 공유 데이터
• 락을 걸거나 풀 필요가 없음
• 모니터가 락을 자동 관리해주니까

self[i].signal()

• 혹시 이 프로세스가 잠들어있다면 깨워주기

 

Dining Philosophers Problem

• Semaphore 코드와 비교해보기