Background
- 여러개의 process 혹은 thread가 동작할 때 공유하고 있는 데이터를 동시에 접근하여 읽고 바꾸는 경우, 최종 데이터 값이 의도치 않게 변할 수 있다.
- 따라서 동시에 접근할 때 제어해줄 시스템이 필요하다
Race condition
- 여러 프로세스가 공유하고는 데이터를 동시에 접근하고 바꾸려고하는 상황
- 마지막에 write한 값으로 결정된다
synchronization으로 race condtion 방지하자! -> 동시에 못하도록 만들자
Example of Race Condition
- Load -> 연산 -> Store operations
- 정상적으로 계산하면 X = 2가 저장되어야 한다
- 만약 P1, P2가 번갈아 가며 operation을 수행한다면 (interleaved execution) X = 1이 되버린다
Critical Section Problem
- n개 process들이 공유 데이터에 대해 접근하고 있는 상황이다
- 이때 각 process가 공유 데이터에 접근하는 코드가 critical section이다
GOAL: 어떤 프로세스가 자신의 critical section을 수행중이면 다른 프로세스들은 자신의 critical section을 수행하지 못하도록 해야한다
- Critical Section Problem의 해결책은 다른 프로세스를 막는 방법이다
Requirements for the Solution
Mutual Exclusion
- 상호 배제
- 어떤 프로세스가 자신의 critical section을 수행중이면 다른 프로세스들은 자신의 critical section을 수행하지 못하도록 해야한다
사실 상호 배제하기 위해 막는건 쉽다. 하지만 들어갈 수 있을 때 들어가게해 throughput을 유지하는 것이 어렵다. 따라서 막기는 막되 성능 저하가 일어나지 않도록 해야한다
Progress
- critical section을 수행중인 process가 없을 때 critical section에 들어갈 수 있도록 해야한다
- 과도하게 막으면 안된다
- 알고리즘에 문제가 있으면 progress를 못하는 경우가 생긴다
Bounded Waiting
- 어떤 process가 critical section에 들어가려고 기다리는 시간에는 bound가 있어야한다
- 나만 계속 못들어가면 안된다
- starvation과 유사
Initial Attemp
- 프로세스 2개 있다고 가정
-
critical section 앞뒤로 entry, exit section이 필요하다
-
critical section에 들어가도 되는지 확인하는 entry section이 필요하다
-
critical section에서 나올 때 다른 프로세스들에게 알려줄 exit section이 필요하다
-
따라서 entry, exit section에는 프로세스들이 서로의 상태를 알 수 있도록 공유 데이터가 필요하다
공유되는 critical section 때문에 문제가 생긴건데.... 해결책으로 공유 데이터를 쓴다고..?
Algorithm 1
- 공유 변수 turn
- P0 입장에서 turn!=0이 아니면 while을 계속 돌며 기다린다
- critical section 이후에 turn=1로 바꿔준다
- Swap-turn으로만 동작 가능!: 반드시 프로세스가 번갈아가며 실행
Mutual exclusion은 보장되지만 progress하지 않는다!
Swap-turn 방식이라 P1이 critical section에 들어가려는 의지가 없으면 P0은 계속 기다려야만 한다
- critical section에 들어가려는 의지가 없는 process를 기다려야하는 문제
Algorithm 2
- critical section에 들어가려는 의지가 있는 process만 turn을 주면된다
- flag하기!
- 먼저 자신의 flag = true 설정
- 다른 process flag가 true면 기다리고 아니면 critical section 실행 -> flag를 보고 양보
- 실행 후 자신의 flag = false 설정
- Swap-turn 하지 않는다!
Mutual exclusion은 보장되지만 progress하지 않는다!
문제는 flag[i] = true; -> 모든 process의 flag가 true면 서로 양보하며 계속 기다린다
- critical section에 들어가려는 의지를 동시에 가졌을때 생기는 문제
Peterson's Algorithm (SOLUTION)
- algo 1의 turn와 algo 2의 flag 둘다 사용하기
- 내 flag를 true로 만들고 turn은 상대방에게 양보
- 상대방이 while문 빠져나오면서 자신의 flag를 false로 만들면 내 while문 빠져나옴
- 그럼 이제 내 차례임
- turn = false인 경우가 있어 Swap turn이 일어나지 않는다
- 둘다 flag가 true라도 공유 변수 turn이 있어 무조건 누군가는 critical section을 수행한다
Limitation
- while문은 cpu를 쓰면서 대기한다 -> Busy waiting
- entry, exit section이 모든 critical section 앞뒤로 코딩되어야한다
Locks
- 개발자 입장에서 동기화 알고리즘에 대한 이해가 없이도 사용가능해야 한다
- 알고리즘을 담고 있는 acquire lock, release lock 함수 제공
- 열쇠를 확보해야 진입할 수 있다 -> acquire lock
- 열쇠를 반납한다 -> release lock
- 전제조건: 열쇠는 한 프로세스에게만 줄 수 있다
Synchronization Hardware
- interleaved execution이 왜 일어날까?
- cpu가 하나라면 cpu scheduling 때문에 interleaved execution이 발생한다
- load -> 연산 -> store 하는 경우- load만 했는데 scheduling되어서 다른 프로세스로 넘어간 경우
- critical section 끝날때까지 cpu scheduling이 안일어나도록 race condition 방지
critical section 들어가기전에 time quantum이 지나면 발생하는 timer interrupt를 disable! -> 빠져나오면 enable
Limitation
- 멀티코어 혹은 cpu가 여러개면 의미 없음.
Solution
- Atomic Hardware -> 특별한 HW 회로 제공하여 single cycle에 기능을 다 수행한다
- Atomic hardware를 사용하는 함수를 제공하여 문제 해결
Synchronization Hardware
TestAndSet
- 이 함수를 HW회로로 구현
- 한 프로세스가 먼저 회로를 사용하면 다른 프로세스는 절대로 사용 못한다
- target 값을 true로 바꾸기
- 원래 target 값을 return
Mutual Exclusion with TestAndSet
- TestAndSet에서 사용하는 공유 변수 lock
- while(false)라 critical section 수행
- critical section 수행중 lock은 true인 상태
- 다른 process에서 lock이 true라 기다린다
- 현재 process가 lock을 false로 바꾸면 다른 process에서 while문을 나간다
TestAndSet이 atomic하지 않다면?
TestAndSet이 동시에 호출되면 모두 false를 return하여 동시에 critical section을 수행한다
Swap
- 이 함수를 HW회로로 구현
Mutual Exclusion with Swap
- key: me lock: he
- while문 돌때 lock과 key값을 swap한다
- 다른 process에서는 key=true,lock=true인 상태라 swap해도 key는 true
- 현재 process가 나오면서 lock을 false로 만들면 다른 process에서 key가 false로 swap된다
Atomic한 HW가 있으면 Peterson algo보다 쉽게 해결할 수 있다
Semaphore
- SW 도구
- 정수 변수 하나와 변수에 접근하는 함수 두개 제공
- 두 함수로만 semaphore 변수에 접근할 수 있어야한다
P(S)
- atomic function
- wait function
V(S)
- atomic function
- signal function
Critical Section of n Processes
-
semaphore mutex 초기값 1
-
P enter V exit
-
현재 프로세스는 mutex가 1이라 P에서 while문 나오고 mutex 0 만들기
-
다른 프로세스는 mutex가 0이라 P에서 while문 돈다
-
현재 프로세스가 critical section 나와서 mutex++하여 1로 만든다
-
다른 프로세스는 while문 나오고 mutex--하여 0으로 만들어 또 다른 프로세스를 P while문에 가둔다
-
P,V atomic하지 않으면 동시에 critical section 수행한다
어떻게 SW로 atomic 함수를 구현할 수 있는거지?
Semaphore Implementation
- 단일 cpu, core이라면 critical section 앞 뒤에 interrupt disable, enable하면 됨
- 멀티코어라면 Peterson algorithm 사용!
- P,V의 S값을 Peterson algorithm으로 보호하여 동시 접근 제한
처음부터 semaphore없이 Peterson algorithm 쓰면 되는거 아닌가..?
-> critical section 만날때마다 Peterson algorithm 구현해야함
-> 따라서 P,V 구현할 때 Peterson algorithm을 한번만 적용하면 나중에 사용만 하면된다!!
Limitation
- while문 busy waiting in P
- critical section이 크면 overhead가 커짐
Block Wakeup Semaphore
- while문 대신에 프로세스를 sleep 시키면 CPU 안씀
- struct안 포인터 -> 연결리스트로 프로세스 관리
- block: sleep 시키기
- wakeup(P): ready queue에 넣기
Implementation
-
현재 프로세스의 value는 1
-
value-- 하고 P 나가서 critical section
-
다음 프로세스의 value는 0
-
value-- 하고 if문에 들어가 block -> sleep 상태로 전환
-
현재 프로세스가 V 호출하여 value++
-
증가했는데 <=0 라는 것은 누군가가 기다리고있다는 뜻이다
-
그래서 wakeup시킴 -> 바로 critical section 실행
S.value가 양수인지 음수인지 확인하여 현재 연결리스트에 기다리고있는 process가 있는지 확인 가능하다
- integer semaphore: # of waiting processes
하지만 critical section의 길이에 따라 그냥 semaphore을 쓸지 block wakeup semaphore을 쓸지 개발자가 선택해야한다
- HW적으로는 locking, Sw적으로는 semaphore 사용하자
CS problem in OS
OS 내부에서 process가 동시에 일어나는 경우가 있을까..?
Interrupt Handler vs kernel
- interrupt handler 또한 kernel 변수를 사용한다
- 동시에 count 조작하는 경우
Solution
- 양쪽에 interrupt disable, enable
- algorithm 써도 됨
Preempt CPU while in kernel mode
- Pa가 system call 호출 -> kernel 코드 접근 -> load/inc/store 과정 도중에 schedudling 발생!
- Pb도 같은 system call 호출 -> 동작 완료 -> Pa로 돌아옴
- Pa가 아까 하던 load/inc/store 이어서 하면 Pb가 수행한 값의 효과가 없어진다
Solution
- system call할 때는 cpu scheduling 막기 ex) UNIX
Multiprocessor
- interrupt disable enable은 소용없음
Solution1
- semaphore, peterson, atomic hw로 모든 kernel 변수 보호
- 너무 복잡하지만 성능 저하 덜함
Solution2
- OS자체를 critical section으로 취급하기
- program status word bit를 보고 kernel mode, user mode 구분 가능
- 어떤 cpu가 kernel mode면 다른 cpu는 kernel mode 못들어감- 그럼 kernel mode 접근을 동기화할 수 있다
- 과도한 blocking 때문에 성능 저하 발생
