Keep going
동기화 하드웨어 본문
어떤 프로그램이 임계 구역에서 실행하고 있다. = 공유 데이터를 건드리는 일을 하고 있기 때문에 다른 프로젝트가 공유 데이터를 건드리는 임계 구역에서 실행하고 있으면 안된다. 어느 한 순간에는 임계구역에 하나의 프로세스만 들어가 있어야 한다.
peterson's 방법 - 속도가 느리고 현대 컴퓨터에서 사용할 수 없는 솔루션 이라는 문제가 있기 때문에 하드웨어 자원을 받아서 임계 구역 해결하는 기법들 알아볼 필요가 있다.
현재 컴퓨터는 실행속도를 빠르게 하기 위해 컴파일러가 필요하면 명령어 실행 순서를 바꾸기도 한다.
Peterson 방법이 명령어가 재배치가 되면 상호 배제를 보장하지 못한다. → 현재 컴퓨터에는 Peterson 방법 맞지 않다.
하드웨어가 지원하는 기능들
memory barrier(Fences)
- barrier 전에 일어나는 명령이랑 barrier 이후 일어나는 명령 사이에 memory barrier가 있다면 뒤에 명령이 실행되기 전 위에 명령이 반드시 다 실행 된다.
- memory barrier 라는 명령이 일어나게 되면 메모리 barrier 이전의 read, write 명령이 다 실행되고 난 다음에 memory barrier 아래에 있는 명령이 실행 된다. (뒤 바뀌는 문제 해결! )
→ peterson 방법과 memory barrier를 같이 사용하면 상호 배제 문제를 해결할 수 있다.
하드웨어 명령은 기계어 명령어다.
기계어 명령은 한꺼번에 실행이 된다. (Interrupt x , atomic 한 명령)
test_and_set instruction
- atomic 하게 실행
- 원래 target 이 가지고 있던 값을 결과로 돌려줌
- 그와 동시에 target 값 true로 변경
- test, set 이 한꺼번에 실행되어야 함 (두 개가 떨어진 명령이라면 임계구역 보장 x)
- 프로세스가 여러개가 있다면 무한대기 문제 빠질 수 있다.
- 한계 대기로 바꾸기 위해서 프로세스가 나가면서 자기 뒤에 있는 프로세스가 들어가도록 만들어 준다.
- 기계어가 test_and_set 명령을 제공하게 되면 임계구역 문제를 풀 수 있다.
- 여러개의 process 가 있을 때 한번씩 상호 배제를 하는게 보장이 되는데 자기 뒤에 있는 프로세스를 들어가게 해주면서 한계대기 보장 받을 수 있다.
compare_and_swap Instruction
- atomic 하게 실행
- value에 기대하고 있는 값이 들어가 있다면 새로운 값으로 저장, 원래 있던 값 return
- lock이 0 이면 1로 놓고, 그 이전 값 돌려줌
- lock이 1이면 expected 값이 1이 아니므로 set을 안하고 현재 값 돌려줌
test_and_set 이나 compare_and_swap instruction 둘 다 하드웨어 명령(기계어 명령) 이기 때문에 일반적으로 고급 언어를 사용하는 사용자 입장에서는 이 명령어를 사용할 수 없는 경우가 많다. (c, java에 이런 명령 들어가 있지 않다.)
운영체제를 설계하는 사람들은 임계구역 문제를 더 쉽게 해결하도록 더 간단한 기능 제공한다. 가장 간단한 구조가 mutex lock 이다.
mutex lock
- acquire() : lock 을 얻는 것
- release() : lock 을 풀어주는 것
- 이런 기능이 제공 된다면 상호 배제 쉽게 해결 가능하다.
- critical section에 들어갈 때 acquire lock 을 먼저 걸고, critical section 나갈 때 release lock 하면 된다.
- acquire()과 release() 는 atomic 연산이어야 한다. (한꺼번에 실행 되어야 한다.)
- available 이라는 자체 변수를 가지고 있다.
- acquire() : available 아니면 기다리고, 필드가 available이면 마지막에 available 을 false로 바꾸고 나가주면 된다. spin lock(cpu를 사용하면서 루프를 돌면서 lock이 available 풀리는 걸 기다리는 것)이라고 한다. lock을 얻기 위해 다른 process는 계속 돌고 있다. 스레드가 cpu를 쓰고 있기 때문에 cpu를 소비한다. busy waiting이라고도 한다. (현재 사용하고 있으면 다른애가 기다려서)
- release() : available을 true로 놓으면 된다.
- atomic 하게 만들기 위해서 available을 바꿀 때 test_and_set이나 compare_and_swap 명령을 이용해서 어느 순간에 하나만 available을 쓸 수 있도록 (상호배제 되도록) 구현하면 된다.
- 많은 운영체제들이 mutex lock 기능을 제공을 한다.
- mutex lock을 이용하면 상호 배제 문제를 해결할 수 있지만 상호배제보다 더 복잡한 동기화 문제를 해결 하기 곤란할 수 있다.
- A명령 끝나야 B명령 실행되게 하기
- Buffer 상태에 따라서 producer consumer 가 기다리는 동기화 문제
- 더 다양한 동기화문제를 해결하기 위해 제시된 것이 semaphore
semaphore
- 세마포어는 하나의 정수 변수
- 3가지 연산만 허용 한다.
- 초기화 init()
- wait() == acquire()
- signal() == release()
- semaphore 가 binary semaphore면 mutex와 같은 의미, counting semaphore 라면 mutex와 다른 의미이다.
- wait(s)은 s가 0보다 작으면 busy wait, 아니면 s 감소
- signal(s)는 s를 1 증가
- wait()과 signal()은 atomic 한 연산
- semaphore를 이용하면 여러가지 동기화 문제를 풀 수 있다.
- 세마포어를 busy waiting 방식으로 구현하기
- wait(), signal() 하는 과정이 critical section이다. wait이 semaphore 건드리고 있으면 signal()이 semaphore 건드리지 못하게 한다. → busy waiting 방식으로 구현한다.
- 세마포어를 실행하는 프로세스가 한개만 있어야 한다.
- 세마포어를 no busy waiting 방식으로 구현하기
- process가 세마포어를 기다릴 때 사용중인 세마포어가 있다면 세마포어 기다리는 프로세스 큐로 간다. 세마포어 열리게 되면 대기하고 있는 프로세스 들 중 하나를 실행시킬 수 있도록 만든다.
- block : 프로세스가 세마포어를 보고 사용이 되고 있구나 알면 자기 스스로를 block 시켜서 세마포어 대기하는 곳에 붙는다.
- wakeup : 세마포어를 사용하던 프로세스가 세마포어를 다 사용했다면 대기하고 있는 프로세스 누군가를 깨워주는 기능
- value는 세마포어를 기다리고 있는 개수, 0이면 세마포어 사용 가능
deadlock
- 세마포어를 여러개 사용할 때 순서를 잘 못 사용하면 deadlock 이 발생할 수 있고, starvation 문제도 발생할 수 있다.
- deadlock은 영원히 기다리는 것이다.
- starvation : 기약이 없는 blocking, 기다리고 있는데 다른애가 계속 차지해서 계속 기다리게 되는 상황
- priority inversion (우선순위 역전) : 프로세스가 여러 개 있을 때 아주높은 프로세스, 우선순위가 아주 낮은 프로세스, 중간 프로세스가 있다고 하자. 낮은 프로세스가 자원을 가지고 있는데 높은 우선순위 프로세스가 그 자원을 사용해야 해 block 되어 기다리고 있다. 중간 우선순위와 낮은 우선순위 중에서 중간 우선순위가 더 높으니 중간이 사용한다. 이런 방식이 반복되어 낮은 우선순위를 가진 프로세스가 실행될 기회가 적다. 문제는 높은 우선순위 가진 프로세스가 낮은 우선순위 프로세스가 자원을 내놓을 때까지 대기하고 있었기 때문에 자기보다 낮은 우선순위의 프로세스가 먼저 실행된다. → priority-inheritance protocol 을 사용해야 한다. (높은 우선순위를 가진 프로세스가 요구하는 자원을 가진 프로세스는 그 높은 우선순위를 상속을 받도록 만들어주는 방법이다.)
test_and_set, compare_and_swap < mutex lock, semaphore (고급 언어에서 지원하긴 하나 비교적 낮은 수준의 지원수준, 잘 못 쓰기 쉽다)
잘 못 사용한 경우들 : signal하고 wait, wait하고 wait,,,,
