본 글은 KOCW 이화여대 반효경 교수님의 운영체제 강의를 듣고 정리한 내용입니다.
http://www.kocw.net/home/m/search/kemView.do?kemId=1226304
- 동기화의 문제에 대해 알아본다
- 동기화 문제의 해결방법에 대해 알아본다.
- 세마포 연산에서 생길 수 있는 문제인 데드락과 동기화와 관련된 전통적인 세가지 문제에 대해 알아본다
- 동기화 문제 해결을 위해 세마포 이외의 모니터 방식에 대해 알아본다.
- 데드락의 문제, 발생 조건, 처리방법 네 가지중 하나인 프리벤션을 알아본다.
✔ Race Condition
-
하나의 공유데이터를 여럿이 동시에 접속할때 생기는 문제점
-
CPU가 하나있든 여러개있든 문제가 생기는 이유 - 운영체제가 끼어드는 경우
- ex) 한개일때,
- A 라는 프로세스가 실행 중일때 프로세스는 운영체제에게 system call을 할 수 있고 할당시간이 끝나면 프로세스 B에게 넘어간다. B 또한 운영체제에게 system call 할 경우에는 운영체제의 동일한 데이터에 접근이 가능
- 그 과정에서 race condition 문제가 생길 수 있음
- ex) 한개일때,
-
Race condition이 언제 발생하는가
-
kernel 수행 중 인터럽트 발생시
- 해결책 : 변수를 건드리기 전에 disable 시키고 interrupt가 끝나면 다시 enable 시킴
-
Process가 system call을 하여 kernel mode 로 수행중인데 context switch 가 일어난 경우
- 해결책 : 커널모드에서 수행중일때는 CPU를 preempt하지 않고, 사용자모드로 다시 돌아갈때 preempt
-
Multiprocessor에서 shared memory 내의 kernel data
- CPU 가 여러개있는 상황 (운영체제가 관여할때)
- 1번 방법은 운영체제 커널 전체가 lock, 2번은 각 데이터별로 lock
- CPU 가 여러개있는 상황 (운영체제가 관여할때)
-
🔹 동기화 문제
- 공유데이터의 동시접근은 데이터의 불일치 문제를 발생시킬 수 있음
- 일관성 유지를 위해 협력프로세스간의 실행순서를 정해주는 메커니즘이 필요
- Race condition을 막기위해서는 concurrent process 는 동기화되어야함
- The Critical-Section Problem : 공유데이터를 건드리는 문제
- N개의 프로세스가 공유데이터를 동시에 사용하기를 원하는 경우
- 각 프로세스의 code segment에는 공유데이터를 접근하는 코드인 critical section 이 존재
- 문제점 : 하나의 프로세스가 critical section 에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야함
🔹 Solve Problem
-
Initial Attempts to solve..
-
Algorithms
-
Algorithm 1
- Synchronization variable
- 차례를 왔다갔다 하면서 하겠다
- 동시에 들어가면 안되는 문제는 해결했지만 아무도 안들어가있을때 들어가게해주는 part가 없음
-
Algorithm 2
- flag 를 두어 프로세스마다 critical section 에 들어가고싶다는 의중을 표함
- 눈치를 보다 아무도 못들어가는 경우 생길 수 있음
- flag 를 두어 프로세스마다 critical section 에 들어가고싶다는 의중을 표함
-
Algorithm 3 (Peterson's Algorithm)
- Algo1,2 모두 사용
- 깃발을 든 경우에 한해 turn 을 주어 알고리즘이 제대로 동작
- spin lock (busy waiting) : 자원 낭비
-
-
충족 조건
1. Mutual Exclusion
- 동시에 들어가면 안됨 (상호배타적으로)
- 프로세스 p가 critical section 부분을 수행중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안됨
2. Progress (진행)
- 아무도 critical section 에 있지않은상태에서 들어가고자하는 프로세스가 있으면 들어가게해줘야함
3. Bounded Waiting (유한대기)
- 프로세스가 들어가려고 요청한 후 그 요청이 허용될때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야함
-
Synchronization Hardware
- 하드웨어적으로 Test & modify를 atoic 하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결됨
- Test & Set (a)
- a라는 값을 읽어가고 그걸 True 로 만드는걸 한번에 수행하는 hardware
- a라는 값을 읽어가고 그걸 True 로 만드는걸 한번에 수행하는 hardware
🔹 1. Semaphore
- 일종의 추상자료형
- S ; integer variable
- 아래의 두가지 atomic 연산에 의해서만 접근 가능
- P 연산 : 자원을 획득하는 과정, V 연산 : 자원을 반납하는 과정
-Critical Section of n Processes
- 아래의 두가지 atomic 연산에 의해서만 접근 가능
- Block / Wakeup Implementation
- Semaphore를 구두체처럼 정의해서 값이 하나있고, 줄세우는 리스트구조로
- block 과 wakeup을 다음과 같이 가정
- block : 커널은 block 을 호출한 프로세스를 suspend 시킴,
- 이 process의 PCB를 semaphore에 대한 wait queue 에 넣음
- wakeup(P) : block 된 프로세스 P를 wakeup 시킴
- 이 process의 PCB 를 ready queue로 옮김
- 이 process의 PCB 를 ready queue로 옮김
- block : 커널은 block 을 호출한 프로세스를 suspend 시킴,
- Implementation version of P() & V()
- Semaphore 연산이 다음과 같이 정의됨
- Semaphore 연산이 다음과 같이 정의됨
- Then.. Which one?
- Busy-wait 보단 Block/wakeup 이 더 좋음
- 굳이 여분이 없는 상황에서 cpu를 계속 쓰는 busy-wait 은 비효율적
- Block/wakeup overhead vs Critical section의 길이
- Critical section 의 길이가 긴 경우(or 경쟁이 치열하면) block/wakeup이 적당
- " 이 매우 짧은 경우(or 경쟁이 치열하지않으면)엔 block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
- 일반적으로는 Block/wakeup 방식 WIN
- Busy-wait 보단 Block/wakeup 이 더 좋음
- Two types of semaphores
- Counting semaphore
- 도메인이 0이상인 임의의 정수값
- 주로 resource counting에 사용 (자원의 갯수)
- Binary semaphore (=mutex)
- 0 또는 1값만 가질 수 있는 semaphore
- 1인 경우는 동시접속을 못하게 하는 것 - lock
- 주로 mutual exclusion (lock/unlock)에 사용
- 0 또는 1값만 가질 수 있는 semaphore
- Counting semaphore
🔹 Deadlock and Starvation
-
Deadlock
- 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
- 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
-
Starvation
- Indefinite blocking. 프로세스가 suspend 된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
🔹 Classical Problems of Synchronization
-
Bounded-buffer problem
- Synchronization variables
: Semaphore full = 0, empty = n, mutex = 1;
-
Readers and Writers Problem
- 한 process가 DB에 write 중일 때 다른 프로세스가 접근하면안됨
- read는 동시 가능
- solution
- writer가 DB에 접근 허가를 아직 얻지못한 상태에선 모든 대기중인 readers를 다 DB에 접근하게해줌
Shared data:
- DB 자체
- readcount; //현재 DB에 접근중인 reader의 수
Synchronization Variables
- mutex // 공유변수 readcount를 접근하는 critical section의 mutual exclusion 보장을 위해 사용
- db // Reader와 writer가 공유 DB 자체를 올바르게 접근하게하는 역할
- Starvation 발생가능
-
Dining-Philosophers Problem
- Synchronization variables
- 앞의 solution의 문제점
- Deadlock 가능성 있음
(모든 철학자가 동시에 왼쪽젓가락을 집은 경우)
- Deadlock 가능성 있음
- Solution
- 4명의 철학자만이 테이블에 동시에 앉도록
- 젓가락 두개 모두 집을 수 있을때만 젓가락을 잡도록
- 짝수 철학자는 왼쪽부터 홀수철학자는 오른쪽부터 (비대칭적)
- Synchronization variables
🔹 2. Monitor
