강의 링크 : https://core.ewha.ac.kr/publicview/C0101020140401134252676046?vmode=f
데이터의 접근
컴퓨터 시스템에서 데이터가 저장되어 있는 위치에서 데이터를 가져오고 ,
가져온 데이터를 연산 후 결과값을 저장되어 있는 위치에 재저장한다.
이렇게 원래 값과 연산된 값, 수정된 값을 동기화 하기 때문에 process syncronization 이라고 한다.
만약 같은 저장소를 공유하는 다른 연산 공간이 있을 때 동시에 일어난 서로의 연산 값이 반영되지 않는 race condition의 가능성이 발생한다.
각자의 연산 공간에선 본인만의 개별적인 저장 공간을 가지고 있다고 생각하기 때문에 발생하는 문제이다.
이런 문제를 어떻게 해결할까 ?
주로 이런 문제는 멀티 CPU 를 사용하는 경우 자주 발생한다. 같은 메모리 공간을 공유 하는 멀티 프로세서들 간의 경쟁이 일어 날 수 있다.
혹은 프로세스 별로 일어나는 커널 내부의 데이터들을 변경 할 때 생긴다. (프로세스는 프로세스 별 개별적인 주소 공간을 갖지만 , 커널 모드일 때는 커널 내부의 데이터 공간을 공유한다.)
커널 모드에서 수행 중 인터럽트 발생 시
커널 모드에서 어떤 값을 1 증가시키는 첫 번째 인터럽트 가 시행 도중 그 값을 1 감소 시키는 두 번째 인터럽트 가 발생했다고 생각해보자
첫 번째 인터럽트를 보낸 프로세스는 해당 값이 +1 되었기를 기대 하지만
그럼 해당 값은 감소 되었다가 다시 더해지면서 값이 변하지 않았을 것이다.
첫 번째 프로세스 어리둥절
그런 문제를 해결하기 위해서
인터럽트가 발생했을 때, 다른 인터럽트를 허용하지 않는 방법 으로 race condition 을 해결해줄 수 있다.
프로세스가 커널 모드에서 작업 중 context switch 가 일어나는 경우
동일하게 어떤 프로세스가 커널 모드에서 어떤 값을 1 증가시키려고 하던 도중 , time interupt 가 발생하여 다른 프로세스에게 넘어갔을 때
해당 프로세스도 커널 모드에서 해당 값을 1 증가시켜버리게 된다면
결론적으로 첫 번째 프로세스는 다른 프로세스가 1 증가 시켜버린 값을 받은 후 1을 또 더해지게 된다.
첫 번째 프로세스는 값이 1만 증가 되었기를 기대했는데 2가 증가되었으니 당황한다
이 또한 커널 모드에서 수행중일 때에는 CPU 를 선점당하지 않도록 한다. 커널 모드가 종료되면 그 때 선점시킨다.
멀티 프로세서에서의 race condition
멀티 프로세서에서의 해결법은 어떤 데이터에 접근 할 때
해당 데이터에 lock 을 걸어 다른 프로세서가 해당 데이터에 접근하지 못하도록 한다.
syncronization 이 끝나면 lock 을 종료한다.
Process synchronization 문제
Process synchronization 문제는 공유 데이터에 동시 접근으로 인해 발생하는 문제이다.
일관성 유지 위해서는 협력 프로세스 간 실행 순서를 정해주는 메커니즘이 필요하다.
공유 데이터에 동시에 접근하는 경우를 race condition 이라고 하며 , race condition 을 막기 위해서는 동기화가 잘 되어야 한다 .
The Critical section problem
우리 나라 말로는 임계구역 이라고 하긴 한다 .
여러 프로세스가 개별적인 주소 공간이 아닌 같이 공유하는 데이터가 존재할 때
프로세스에서 공유 데이터에 접근 하고자 하는 코드의 문맥을 critical section 이라고 한다.
다른 프로세스가 critical section 에 있을 때 다른 프로세스는 동일한 critical section 에 접근하지 못하게 해야 한다.
프로그램적 해결법의 충족 조건
Mutual Exclusion(상호배제)
특정 프로세스가critical section을 수행중이면 다른 프로세스는 해당 영역에 들어가면 안된다.Progress(진행)
아무도critical section에 있지 않은 상태에서critical section에 들어가려고 한다면 들어가게 해줘야 한다.들어갈 애는 들어가야지 ~!!
Bounded Waiting(유한 대기)
프로세스가critical section에 들어가려고 요청한 후 부터 그 요청이 허용될 때 까지 다른 프로세스들이critical section에 들어가려는 횟수에 한계가 있어야 한다.들어가려고 하는 애가 있으면 다른 애들이 너무 많이 들어가게는 하지마 ~!
기다리는 시간이 유한해야 해
다양한 알고리즘
알고리즘 1
turn 이란 변수에 critical section 에 들어갈 변수의 번호를 저장한다.
이후 해당 프로세스가 들어갈 차례가 되면 critical section 에 들어가고
수행이 종료되면 다음 critical section 에 들어가고자 하는 번호로 turn 을 업데이트 한다.
자기 turn 이 아닌 경우엔 계속 반복문을 돌며 기다린다.
turn은 다른 프로세스가critical section을 다녀온 후 변경된다.
그것의 의미는 본인의 차례를 위해서는 다른 프로세스가critical section에 들어간 후turn을 바꿔줘야 한다는 것이다. (적어도 다른 프로세스가 다녀와야critical section에 들어갈 수 있음)
이는 Mutual Exclusive 는 만족한다. 그 이유는 critical section 에 한 프로세스만 들어갈 수 있게 하니까
하지만 문제는 특정 프로세스가 다른 프로세스들에 비해 더 빈번히 critical section 에 들어간다고 가정했을 때는 어떻게 해야 할까 ? 현재의 알고리즘은 내가 한 번 쓰고 나면 턴이 뺏기기 때문에 다른 프로세스가 다녀와야 내가 다시 들어 갈 수 있다.
이 알고리즘은
progress를 만족시키지 못한다.
쓰는 사람이 없을 때는 내가 들어가야하는데 쓰는 사람이 없으면 나도 영원히 못들어간다.
알고리즘 2
이 알고리즘은 배열 형태에 프로세스 별 flag 를 boolean 값으로 설정해둔다.
모든 프로세스의 기본 flag 는 false값이다.
프로세스들은 critical section 에 들어가기 전 본인의 flag 를 true 로 바꿔주고 사용 한 후에는 본인의 flag 를 false 로 바꿔준다.
이 때 critical section 에 들어가기 전 한 가지 조건을 만족해야 한다.
본인을 제외한 다른 프로세스들의 flag 들이 모두 false 여야 한다는 것이다.
이는 현재
critcal section에 들어가있는 프로세스가 없어야 한다는 것이다. 만약 하나라도true인 상태라면 현재critical section에 다른 프로세스가 작업중이다.
만약 다른 프로세스가 critical section 에서의 작업이 종료되면 본인의 flag 를 false 로 바꾸기 때문에 그 때서야 다른 프로세스가 critical section 에 들어갈 수 있다 .
와우 완벽해 이건
progress도 만족시킬 수 있지 않을까
근데 문제가 있다 얘도
만약 어떤 프로세스가 본인의 flag 를 true 로 설정하고 critical section 에 들어가려고 하기 전에 time interupt 가 걸렸다고 해보자
그래서 걍 들기만 하고 뻇겨버린거야
근데 다른 프로세스도 들어가기 전에 본인의 flag 를 true 로 설정하고 지켜보니 ?
이전에 애가 flag 를 true 로 설정해뒀기 때문에 얘도 못들어가
그럼 둘 다 계속 멍청하게 기다리기만 한다.
나는 밑에서 후술할 알고리즘 3를 보기 전에
ㅋㅋ 아 그러면 flag 설정을 while 문 안에서 하면 되는거 아니냐고 ㅋㅋ생각했다.
근데 알고리즘3는 다르더라
흠 .. 그렇게 해도 돌아가긴 할 것 같은데 .. 다만 이렇게 되면time interupt가 발생 했을 떄 어떤 프로세스는time interupt를 당한 프로세스가critical section에 다녀와서 본인의flag를 끄기 전까지 사용하지 못해서 비효율적인가 ?
알고리즘 3
이거는 본인의 flag 를 true 로 설정할 뿐 아니라 다음 critical section 에 들어갈 프로세스의 번호도 turn 에 저장해준다.
현재 알고리즘은
i번째 프로세스와j번쨰 프로세스만 존재한다고 가정하고 설명한다. 그런데 몇 개의 알고리즘이 있든 상관없다. 그냥 인덱스 역할만 한다고 생각하자
이후 내가 설정한 조건 flag가 true 면서 다음 turn 이 다른 프로세스를 가리킬 때 를 만족한다면 critical section 에 들어간다.
이 또한 내가 위에서 후술한 것처럼, 재수없에 time interupt 가 flag , turn 을 설정한 후 걸리게 되면
다음 프로세스는 while 문을 통과하지 못해 계속 본인의 점유 시간동안 기다리게 된다.
이러한 문제를 Busy Waiting 이라고 하며 spin lock이라고 하기도 한다.
본인의 차례 때 계속 반복문을 도는게 의미 없이 기다린다는 것이다. 계속 반복문을 돌면 뭐하나 , 돌아도 바뀌는게 없는데
Synchronization Hardware
이런 문제가 생겼던 이유는 (Busy Waiting) critical section 에 들어가기 전 flag , turn 을 설정하던 중 time interupt 가 발생했기 때문이다.
그러면 critical section 에 들어가는 것과 flag , turn 을 설정하는 행위가 모두 동시에 일어날 수 있다면 time interupt 를 걱정하지 않아도 되지 않을까 ?
그러기 위해 생긴게 Test_and_set 이다.
Test_and_set 은 해당 값을 읽고, 해당 값을 변경하는 것을 모두 한 번의 instruction 으로 할 수 있게 도와주는 하드웨어 장치이다.
그럼 맨 처음 lock 이란 값을 flase 로 설정해주고
while(Test_and_set(lock)) 문을 해석해보자
코드가 실행되는 순서는 lock 을 읽어오고 , while 문을 해석하고 , lock 값을 true 로 바꾼다.
-
lock이 처음에true일 경우 :while문 내에서lock을 읽고 ,while문이 진행되어 반복적으로lock값을 계속true로 변경한다.
-
lock이 처음에flase일 경우 :while문 내에서lock을 읽고while문이 진행되지 않아 다음 코드 섹션인critical section으로 이동한다. 이동 할 때lock의 값은true로 변경한다.변경하는 이유는
time interupt가 발생했을 때 다른 프로세스가 들어가지 못하게 하기 위해서이다.이후
critical section을 다녀오면 다른 프로세스가 들어 갈 수 있도록lock을flase로 변경한다.
하지만 나는 여전이 의아하다. 얘네들도 결국
Busy wating이 존재하는거 아닌가 ?
