12강 Process Synchronization 1

https://core.ewha.ac.kr/publicview/C0101020140404144354492628?vmode=f 

반효경 [운영체제] 12. Process Synchronization 1

임의의 프로세스 코드를 보면 두가지로 구성되어있다

 

->공유데이터를 접근하는 critical section 과 그것이 아닌 코드

 

공유 데이터에 동시에 두가지 프로세스가 접근하면 race condition 이 생기니까

critical section 에 들어가기전에 lock을 거는 entry section 을 넣어서 여러 프로세스가 critical section 에 들어가는것을 막고

critical section 이 끝났으면 lock 을 풀어서 다른 프로세스가 critical section 에 접근할수 있도록 해줘야함

-> entry section 과 exit section 의 코드들을 붙여서 소프트웨어적으로 해결해줄수 있다.

 

소프트웨어적으로 코드를 넣어서 race condition 문제를 해결하는 방법을 살펴볼것이다.(3가지 방법)

 

이러한 critical section 에서 일어나는 문제들을 해결하기위한 방법들이 만족해야하는 조건들을 살펴보면 다음과 같다.

1.Mutual Exclusion(상호 배제)

어떤 프로세스가 critical section 에 들어가있으면 다른 모든 프로세스는 critical section에 들어가지 못하게 해야한다.

2.progress(진행)

아무도 critical section 에 들어가 있지 않으면 들여 보내줘야한다는것이다 (당연한거 아님?)

3.bounded waiting(유한 대기)

기다리는 시간이 유한해야한다는 뜻이다.

특정 프로세스 입장에서 critical section에 들어가지 못하고 starvation 이 생기는일이 없어야 한다는 뜻이다.

(3개의 프로세스가 critical section 에 들어가려하는데 1개는 왕따시키고 나머지 두개만 쓸때 이런 조건을 만족 못한다는 것이다.)

 

1번째 알고리즘

이제 프로세스가 2개가 있다고 가정해보자 위의 코드는 p0이다

 

turn 이라는 변수를 사용하는데

보면 while 문인지로 검사해서 본인차례인지 계속 확인한다 (turn 이 0 이 아니라면 대기하는것이다 while 문에서)

->본인 차례가 아니라면 while 문에서 계속 대기한다.

최초에 turn 변수가 0이니까 while 문은 통과해서 critical section 을 거쳐서 마지막에 다른 프로세스가 쓰라고 turn 을 다른 프로세스의 번호로 바꿔준다.

 

이러면 문제가 progress 를 만족하지 못한다 -> 아무도 critical section 에 들어가지 않았는데 들어가지 못하는 현상이 일어난다.

 

이런방식이라면 프로세스들은 한번씩 교대로 critical section 에 들어갈수있는 권한이 주어지는건데

각 프로세스 마다 critical section 에 들어가는 빈도수는 다 다르다 극단적으로 프로세스0은 여러번 접근하는데 프로세스1은 1번 접근하면

프로세스 0은 critical section에 접근하려해도 교대로만 접근할수 있기때문에 한번만 접근할수있는 문제가 생긴다.

 

이런 문제로 인해 사용할수 없는 방법이다.

2번째 알고리즘

이번에는 flag라는 변수를 사용하는데 각각의 프로세스 마다 flag 가 있는것이다.

flag는 critical section 에 들어가려는 의중을 boolean 으로 표현한다.

그래서 최초에는 flag 가 false 이고 

이제 critical section에 들어가려고 entry section 에서 flag 값을 ture 로 만들어주고 다른 프로세스의 flag가 true 인지 while 문으로 검사한후 만약 다른 프로세스에서 flag 값이 true 라면 while 문에 걸려서 대기 그것이 아니라면 critical section 을 실행하고 다실행후 flag 를 false 로 바꿔주는 형식이다.

 

이 알고리즘의 문제점은 프로세스가 깃발을 드는 flag를 true 로 바꾼 시점에 cpu 를 뺏기고 다른 프로세스가 critical section 에 들어가면 또 깃발을 들고 서로 깃발을 들고 대기하면서 양보해서 progress 기준에서 미달된다.

서로 계속 양보한다.

 

 

3번째 알고리즘 피터슨 알고리즘 이라고도 부른다 -> 이름걸고 장사하면 맛집이다(잘돌아감)

turn 변수와 flag 변수를 동시에 다 사용한다.

최초에 entry section 에 들어가면서 flag 를 세우고

turn 을 상대편으로 바꿔준다.

다음 이제 조건검사를해서 기다릴지 실행할지를 결정하는데 조건이 상대방이 flag를 들었고 turn 도 상대방것이여야지만 대기한다

그것이 아니라면 critical section 을 실행하고 flag 를 false 로 변경해준다

결국 flag 가 중복된 경우에만 turn 을 따져서 turn 을 가지고있는 놈이 들어가는 방법이다

이렇게되면 어디에서든 cpu를 뺏겨도 앞의 3가지 조건을 모두 만족하게 된다.(둘이 동시에 안들어가며 특정프로세스만 기다리지않고 서로 양보하면서 기다리는 일이 없다)

 

잘짜여진 코드라고한다 -> 코드 순서 하나만 달라져도 제대로 동작하지 않는다고함

 

이 알고리즘도 문제점이있다 -> busy waiting(sipn lock 라고도 부른다) while 문을 돌면서 lock 을 걸고있는 형태이다. 조건이 안맞는다면 본인의 cpu 시간을 그냥 낭비하는것이다. cpu와 메모리를 계속 쓰면서 기다리게 되는것이다. 비효율적이된다.

 

 

하드웨어적인 해결책

이런게 critical section 이 문제되는 이유가 고급언어 한가지 명령이 여러개의 instruction 으로 구성되어있어서임 중간에 cpu를 빼앗길수 있기 때문에 일어나는 일이다.

사실은 하드웨어적으로 하나의 instruction 만 주어진다면 이런 critical section 문제는 아주 쉽게 해결된다.

-> 하드웨어 적으로 이렇게 쉽게 해결할수있는 고유한 instruction 이 제공되는 경우가 많은데

test_and_set이라는 instruction .

이런 문제가 생긴 이유는 어떤 데이터를 읽고 쓰는것을 하나의 instruction 으로 처리할수 없어서이다.

만약에 어떤데이터를 메모리에서 읽으면서 동시에 메모리에 쓸수있는 instruction이 있다면 적어도 instruction 을 실행하는 도중에 cpu를 뺏길일은 없기 때문에 문제가 생기지 않게 된다.

 

test_and_set 이라는 instruction 이있는데 이런것이 하드웨어적으로 해결한것의 예시이다

이것은 변수를 읽고 내용을 1(true)로 바꿔주는것이 하나의 instruction 안에 이루어진다

-> 변수가 기존내용이 1이여도 1로 무조건 결과물을 만들어준다.

 

이게 지원이 된다면 위의 flag 와 turn 같이 여러개 변수를 썻던것을 저런식으로 하나의 lock 이라는 변수를 통해서 한방에 해결할수있다

test_and_lock 는 일단 읽어서 읽은 내용을 가지고 while문 조건을 제공하고 이제 통과하면서 1로 바꿔주는것이다.

그래서 최초 lock 가 0이였다면 아무도 안들어가 있는거니 while 문을 통과하면서 lock를 걸어주고(lock 변수를 1로 만들어주고)

만약 lock 변수가 1인상태에서 while 문 조건을 만난다면 1을 일단 read 해서 결과물을 반환해주니까 lock 가 걸려있는 true 이므로 while 문에서 대기하면서 lock 변수는 1로 계속 변하는것이다 그러므로 다른 프로세스에서 critical section 이 끝나면 lock을 false 로 바꿔줘야 다른 프로세스도 돌아갈수있게된다. 

 

프로그래머가 매번 이렇게 코드를 짜는것은 개빡칠 것이다

그래서 좀더 추상화된 세마포어 라는걸 제공한다. 오오 드디어 세마포어 뮤텍스 오오오오오

그래서 이러한 위에서 공부했던 작업을 프로그래머가 하는게아니라 연산만 해줘서 lock 를 걸고 풀수있는 세마포어에 대해서 공부할것이다.