퇴근 후 운영체제 시리즈 - 동기화
운영체제 스터디 기록
해당 썸네일은 Wonkook Lee 님이 만드신 Thumbnail-Maker 를 이용하였습니다
데이터의 접근
- 하나의 공유 데이터를 여러 연산에 쓴다면 어떻게 될까? → 데이터의 무결성이 깨진다!
- Race Condition 문제가 생김
- Single CPU : 커널에 의해 동기화 문제가 생길 수 있음
OS에서 race condition은 언제 발생하는가?
Kernel 모드 수행 중 인터럽트 발생 시
커널 모드 수행 중 인터럽트(더 중요한 일)가 발생하여 인터럽트 처리 루틴이 수행
⇒ 양쪽 다 커널 코드이므로 커널 주소 공간 공유
해결
커널 모드 중에는 인터럽트를 받지 않겠다 → 범용 컴퓨터에서는 그렇게 급박한 인터럽트가 생기지 않음 (Real time 에서나 생길 듯)
Process가 system call 을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
- 두 프로세스의 주소 공간 간에는 data sharing은 없음
- 다만 시스템콜을 통해 커널모드로 들어가게 되면 커널 주소 공간의 데이터를 access 하게 됨
- 이 작업에서 race condition 이 일어날 수 있음
🏰 해결책
- 커널 모드에서 수행 중일 때는 CPU를 선점하지 않음
- 커널 모드에서 사용자 모드로 돌아갈 때 선점
Multi-processor 에서 shared memory 내의 kernel data 변경
문제가 발생하는 근본적인 이유는 운영체제가 끼어있기 때문!
CPU가 여러 개라면 인터럽트가 의미가 없어짐 → 서로 다른 프로세서이기에
- 하나의 CPU만이 커널에 들어갈 수 있다~ → 멀티 프로세서의 장점이 사라짐 + 오버헤드가 급격히 늘어남
- 커널 내부에 있는 각 공유 데이터에 대한 lock / unlock 을 걸어줌 → 다른 프로세서가 접근하려 해도 이미 쓰고 잇기에 막음
프로세스 간 동기화 문제
🪢 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킴
⇒ 따라서! 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요
Race Condition
✔︎ 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
✔︎ 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
Race Condition을 막기 위해서는 프로세스끼리 동기화가 되어야 한다.
임계 구역 (critical section)
각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 임계 구역이 존재함
보통 커널코드가 경쟁 조건이 발생하기 쉽다
하나의 프로세스가 임계 구역에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
해결법
만족되어야 하는 해결법 조건
✓ 상호배제
- 프로세스 Pi가 임계 구역 부분을 수행 중이면 다른 모든 프로세스들은 들어가면 안됨
✓ Progress (진행)
- 아무도 임계 구역에 있지 않은 상태에서 임계 구역에 들어가고자 하는 프로세스가 있으면 임계구역에 들어가게 해줘야됨 → 효율성
✓ 유한대기
프로세스가 임계구역에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 임계 구역에 들어가는 횟수에 한계가 있어야 됨
ex) A, B, C 프로세스가 있는데 A와 B만 계속 들어가는 문제 → C가 대기하는 시간이
유한해야 한다는 의미
선점형 커널 vs. 비선점형 커널
선점형 커널
프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용
✓ 경쟁 조건을 보장할 수 없음 → 신중하게 짜야됨
✓ 커널 모드 프로세스가 대기 중인 프로세스에 프로세서를 양도하기 전에 오랫동안 실행할 위험이 적음 → 민첩성
✓ 실시간으로 선점에 용이하기에 실시간 프로그래밍에 더 적당
비선점형 커널
커널 모드를 빠져나가기 전까지는 봉쇄된다.
✓ 경쟁 조건이 일어나는 것을 걱정할 필요가 없음
Algorithm 1.
동기화 변수를 두어서 나의 차례인지 다른 프로세스 차례인지 처리함
즉 내 차례일 때만 임계구역을 들어감
단점
⇒ 과잉양보 문제가 생김. 상대방이 한번 들어갔다 나와야 내가 들어갈 수 잇기에 비효율적임. 내가 자주 들어가야하는데 상대방이 들어가야 하는 차례라면? 즉, 동기화 부분은 해결됐지만 비효율
Algorithm 2
- 내가 들어가고 싶다는 flag를 true로 해줌
- 상대방이 flag가 켜져있다면 꺼질때까지 기다림
- 꺼지는 순간 임계 구역에 들어갔다가 나도 꺼줌
단점
✔︎ 상호 배제는 만족하나 여전히 진행 문제가 잇음 → 비효율적
아무도 임계 구역에 없는데 무한 양보 → 내가 들어가기 전에 깃발을 드는 건 들어갔다가 아니라 들어가겠다 라는 의미이기 때문
Algorithm 3. 피터슨 알고리즘
- 알고리즘 1과 2를 모두 사용함
- flag를 통해 intention을 확인하고 turn 을 통해 상대방을 확인함
- 알고리즘 1에서는 꼭 swap 이 일어나야했지만 이 알고리즘은 flag를 활용해서 기다리는 상황 자체를 좁힘
- Busy Waiting (Spin Lock) → 계속 확인하면서 기다려야 하기 때문에 CPU와 메모리를 잡아먹음
- 이 관점은 프로세스 Pi에 대한 관점임을 이해해야 됨
- 프로세스 Pi 가 CPU를 차지하고 한다는게 while 기다리는 거면 Pj 프로세스가 들어갈 틈이 없음
- 그렇기에 cpu를 놔줘야 되는데 안 놔주는 문제가 생기는 것
하드웨어 해결법
하드웨어가 이 문제를 도와주면 정말 간단히 해결됨
⇒ 하드웨어가 원자적으로 데이터를 처리하는 것이 이뤄지면 Test & Set 이 만족되어 해결이 쉬워짐
✓ a 라는 값을 읽는 일과 세팅하는 일을 따뤄두면 괜찮다.
