목표
동기화 문제의 해결 방법에 대해 알아본다.
The Critical-Section Problem
공유데이터를 여러 시스템에서 동시 접근할 때 생기는 문제.
공유데이터는 사용자 프로세스에서는 없고, 운영체제엔 공유데이터가 존재하고, 동시 접근할 때 문제가 생긴다. 동시라는 표현이 약간 불명확하다. cpu가 여러개 있다면 공유 데이터를 동시에 접근하면 문제가 있겠지만 보통 cpu가 1개인데, 또, 동시 접근이라는 문제가 생기는가? => 동시접근의 문제라기 보단 데이터를 읽어오고 연산하고 저장하는 단계를 automic하게 한번에 처리할 수 없기 때문에 생기는 문제다.
소프트웨어적으로 이 앞뒤에다가 어떤 코드를 붙이면 해결할 수 있는지 알고리즘적으로 알아보자.
Algorithm 1
turn 이번 차례가 누구 차롄지 알려준다.
turn이 0이면 내 차례고 turn이 1이면 상대방 차례.
내 차례일 때 critical section에 들어가서 그 코드가 다 끝나면 turn을 상대방으로 돌려준다.
분명, 둘이 동시에 들어가는 일은 없다. turn을 둬서, 보장한다.
그럼 어떤 문제가 있을까? => 엄격하게 critical section에 차례로 돌아가도록 하게 되어있다. 나 한번 너 한번 나한번 너한번. 내가 다시 들어가고 싶어도 상대방이 갔다 올 때까지 난 못들어가. => 굉장히 불합리해. 내 프로그램은 critical section에 자주 들어가는, 상대방은 한번도 안들어가는 코드였다. 상대방이 만약 사용안하면 내 차례는 영원히 안들어와.
프로그램적 해결법의 충족 조건
알고리즘들이 어떤 조건을 만족해야 하는지?
- mutual exclusion : 상호 배타적으로 critical section에 들어간다. 동시에 들어가면 안된다는 것이다.
- progress : 진행이 안된다~ 아무도 critical section에 없고, 난 들어가고 싶은데 못들어가는 상황.
- bounded waiting : 기다리는 시간이 유한해야 한다~ starvation을 막아야 한다는 뜻 . 특정 process가 영원히 자원을 못쓰는 문제.
Algorithm2
파란색 코드가 두줄이 붙어있죠~
프로세스마다 각자 flag가 있다. critical section에 들어가고 싶으면 본인의 깃발을 든다. 그런 다음에 바로 못들어가고. 혹시 상대방도 깃발을 들고 있는지 확인해서 동시 접근 불가하게 한다. i라는 프로세스가 자기 깃발을 들었고, j프로세스 깃발이 들려있는지 확인해서, while문 돌면서 critical section에 안들어간다. 난 기다리겠다. 상대바아의 깃발이 내려지만 critical section에 들어간다. 상대방의 깃발은 critical section에 들어갔다 오면! .
문제해결이 잘 될까요/?
=> 일단 동시문제는 해결이 잘 된다. mutual exclusion 해결
=> progress 문제는 생길 수 있다. j 프로세스가 깃발을 들었다는게 아직, critical section에 들어간건 아니다. 근데 그걸 보고 겁이 나서 못들어가는 것이잖아. 내가 깃발을 들고 들어가기 전 상태에서 cpu를 빼앗겼고, 상대방도 깃발을 들었는데 상대방 깃발이 들려있으니까 또 넘긴다? 모두다 깃발만 들고 눈치만 보다가 아무도 못들어가는 문제가 생긴다. 즉, 진행이 더이상 안되는 문제가 생길 수 있음
Algorithm3
앞에 두개 알고리즘에서 사용했던 두개의 변수를 모두 사용한다.
깃발을 이용해서 critical section에 들어가겠다고 표현하고
상대방이 들고 있는지 확인하는 절차가 들어감.
둘다 깃발을 들고 있으면? => turn을 이용해서 니차례인지, 내차례인지
그리 간단하진 않는다.
synchronization hardware
이런 synchronization 문제를 도와줄 수 있는 하드웨어 지원이 있으면 이 문제는 대단히 쉽게 풀린다. 만약에 하드웨어적으로 automic하게 데이터를 읽어가고 변경하고 저장한다면? cpu를 중간에 빼앗기거나 쪼개질 수 없어진다. 한꺼번에 반드시 실행을 하면 문제가 안생길 것 !!!!
semaphores
여전히 synchronization 문제를 푸는건데 앞에처럼 직접 코드를 만드는게 아니고, 인제는 추상적인 무언가가 제공이 될 때 프로그래밍 하는 사람들은 그 도구를 가져다 써서 이 문제를 쉽게 푼다.
2가지를 소개할 것임.
1) semaphores (쎄마포어)
2) monitor
mutual exclusion 문제에서는 semaphores에서 변수를 1로 준다. 변수가 1이라는 것은 자원이 하나라는 뜻이고, 하나밖에 없을 때 p연산을 하면 lock을 획득하는 과정이다.
critical section of n processes
만약 critical section같은 경우에 semapheres같은 추상 자료형이 지원이 되면 이렇게 코드를 작성하면 된다.
block/ wakeup implementation
semaphore을 마치 구조체처럼 정의해서 값이 하나 있고, semaphore을 갖다가 줄 세우는 list를 구조. semaphore 변수 l에 대해서 process를 잠재우고 줄세워서 기다리게 한다.
누군가가 semaphore를 쓰고 있는 프로세스가 v연산을 통해 반납하면, 가장 앞에 있는 process를 깨우면 된다.
implementation
which is better?
critical section을 얻는 경쟁이 치열한지 안한지를 기준으로 잡는게 더 나은 의미인 것 같다!1
two types of semaphores
