[07] 운영체제 - 충돌-1

안녕하세요. 이번 포스팅이 1차 중간고사까지의 범위로 결정이 됐습니다!

저번 주까지는 스케줄링의 방법들에 대해서 공부를 해보았는데요

이 강의에서 우리는 프로세스에서 살펴보았는데 이때 여러 프로세스가 

동시에 공유 메모리에 접근을 하게 될 때 충돌이라는 문제가 발생한다는 것을 배웠습니다.

오늘은 바로 그 충돌의 해결방안들에 대해서 살펴보도록 하겠습니다.

충돌은 동시에 다른 프로세스가 하나의 메모리에 접근을 하여 값이 원하는 대로 나오지 않는 현상인데요.

쉽게 와 닿지 않으실 수 있으실 테니까 간단히 코드를 보며 설명을 해보도록 하겠습니다.

위의 코드를 대략적으로 설명하자면 Producer 프로세스가 buffer를 통해 Consumer 프로세스에게 작업을

하나씩 넘겨주고 Producer는 넘겨주었으니 buffer의 크기를 1증가 시키고 Consumer 프로세스는 buffer에서

하나를 꺼내 처리를 하기 때문에 buffer의 크기를 하나 줄여주는 코드입니다.

하지만 여기서 두 프로세스 모두 counter라는 메모리에 있는 값에 접근을 하여 조작을 시도하게 되는데요

조작하고 있는 사이에 Context Switching이 일어나게 되면 그 값은 원하는 결과를 가져오지 못 할  수도 있습니다.

바로 밑의 사진과 같은 결과가 일어나게 됩니다.

이렇게 한 메모리의 값에 동시에 접근하는 현상을 Race Condition이라고 하고 

이러한 Race Condition의 원인이 되게 하는 코드를 Critical Section이라고 합니다.

즉 이 예시에서 Critical Section은 counter++; 와 counter--; 가 되게 됩니다.

이러한 Critical Section 문제를 해결을 하기 위해서는 해당 부분의 코드에 동시에 

두 프로세스가 접근하지 못하게 해야 하는데요. 이를 해결하기 위해서는 해당 코드의

위와 아래에 별도의 이를 방지하는 코드를 작성해주어야 하는데 이를 각각

Entry Section과 Exit Section이라고 합니다.

do { // entry section critical section // exit section }while(TRUE)

Entry Section에서 별도의 코드를 작성해줌으로써 먼저 들어온 프로세스가 Critical Section에 접근하게 되면 

그다음에 접근하는 프로세스는 Entry Section에 의해 막혀 먼저 들어온 프로세스가 Critical Section에서의 작업을 마치고

Exit Section 코드를 수행하게 된 후에야 Critical Section에 접근을 할 수 있게 됩니다.

이와 같이 Critical Section 문제를 해결하려는 방법들은 다음의 세 가지를 만족해야 합니다.

1. Mutual Exclusion

    하나의 프로세스가 Critical Section에 접근하였으면 다른 프로세스는 접근하지 못해야 한다.

2. Progress

    어떤 프로세스도 Critical Section에 들어가 있지 않았을 때  어느 프로세스를 들어가게 해야 하는지 결정해주어야 하고 이러한

    결정과정은 무한정으로 지연돼서는 안된다.

3. Bounded Waiting

    프로세스가 Critical Section에 들어가기로 했으면 무한정 기다려서는 안된다. 일정 시간 안에 들어가야 한다.

그리고 가장 중요한 가정이 있는데 그것은 바로

LOAD/STORE 명령어들은 atomic 하게 작동한다는 것입니다.

atomic 하게 작동한다는 의미는 해당 명령어가 실행될 때는 interrupt가 발생하지 않아야 한다는 것입니다.

그럼 이제 Critical Section 문제를 해결하는 방법에 대해서 하나씩 알아보도록 하겠습니다.

첫 번째 방법으로는 Entry Section에서 Lock을 얻고 Exit Section에서 해당 Lock을 반납하는 방법입니다.

do { //Acquire lock critical section //Release lock}while(TRUE)

쉽게 설명하자면 어떠한 방에 동시에 두 사람이 들어가려 할 때 먼저 도착한 사람에게 열쇠를 주고 그 방에 들어가면 

문은 안에서 잠기게 됩니다. 그리고 들어가 있는 사람이 문을 열고 나와 다음 사람에게 그 열쇠를 건네주고 그다음 사람이

방안에 들어가게 하는 방법입니다.

이렇게 이해하면 쉽죠?

현대 기계들은 특별한 하드웨어 명령어를 제공하는데 그 명령어들은 위에서 언급했던 atomic 하게 작동합니다.

특별한 명령어 두 가지는 다음과 같습니다.

1. TestAndSet()

2. Swap()

각각의 명령어들의 내부를 살펴보도록 하겠습니다.

//TestAndSet Instructionboolean TestAndSet(boolean *target){ //여기서 target은 lock이며 FALSE로 초기화되어 있다. boolean rv = *target; *target = TRUE; return rv;}//Swap Instructionvoid Swap(boolean *a, boolean *b){ boolean temp = *a; *a = b; *b = temp;}

그럼 각각의 명령어들이 어떻게 작동하면서 Critical Section 문제를 해결하는지 천천히 살펴보도록 하겠습니다.

여기서 알아야 할 것은 target 즉 lock은 FALSE로 초기화되어 있고 전역변수로서 공유되는 자원이라는 것입니다.

코드를 보고 머리 속으로 상상하실 때 두 개의 프로세스가 동시에 접근한다는 것을 인지하시고 상상하셔야 합니다.

TestAndSet() 명렁어는 다음과 같은 방식으로 사용될 수 있습니다. 

do{ while(TestAndSet(&lock)); //critical section lock = FALSE; //remainder section}while(TRUE)

먼저 들어온 프로세스 P1가 TestAndSet 함수를 통과하면서 lock이 TRUE가 되고 반환값으로 FALSE를 받게 됩니다.

그러므로 while 문을 벗어나서 Critical Section에 들어가게 됩니다.

그리고 P1이 Critical Section에 들어가 있는 동안 프로세스 P2가 Critical Section에 접근하려 하는데 현재 lock의 값은

앞선 P1에 의해 TRUE로 바뀐 상태이므로 P2는 계속 while 문을 돌면서 Critical Section 앞에서 대기하게 됩니다.

그리고 P1이 작업을 끝내고 Critical Section을 벗어나고 lock을 FALSE로 바꿔놓고 나머지 코드를 수행하게 되면

그제야 P2는 lock이 FALSE이므로 while 문을 벗어나 Critical Section에 들어갈 수 있게 됩니다.

위에서 들어본 예시와 같이 생각해보면 P1이 먼저 TestAndSet 함수를 통과하면서 lock을 TRUE로 바꿔놓는 것이 열쇠를

얻게 되는 과정이고 Critical Section에서 벗어나 lock을 FALSE로 바꿔 놓는 것이 열쇠를 반납하는 과정이라고 할 수 있습니다.

Swap() 명령어도 위와 같은 방법으로 같은 효과를 가져옵니다.

하지만 위의 두 가지 방법도 완벽한 것은 아닙니다. 

바로 Bounded Waiting을 만족하지 않는데요.

그 이유는 P1이 lock을 반납하고 바로 P2로의 Context Switching이 보장되지 않기 때문입니다.

P1이 lock을 반납하고 다시 얻은 상태에서 Context Switching이 일어나게 된다면 

P2는 여전히 기다리게 되기 때문입니다.

즉 하나의 프로세스가 lock을 반납하고 어떤 프로세스가 들어가야 하는지 결정을 해주지 않기 때문에

발생하는 문제입니다.

그래서 이와 같은 문제를 해결하기 위한 것이 바로 하나의 프로세스가 lock을 반납하고 나오면서

다음에 실행되어야 할 프로세스를 지정해주는 방법입니다. 바로 코드를 살펴보도록 하겠습니다.

do{ // waiting 배열은 프로세스들 waiting[i] = TRUE; // ---- 1 key = TRUE; while(waiting[i] && key) // ---- 2 key = TestAndSet(&lock); waiting[i] = FALSE; //critical section // n은 프로세스의 갯수 = 배열의 크기 j = (i+1) % n; // ---- 3 while((j != i) && !waiting[i]) j = (j+1) % n; if(j == i) lock = FALSE; else waiting[j] = FALSE; //remainder section}while(TRUE)

위의 코드를 천천히 설명해보도록 하겠습니다.

예를 들어 0번부터 6번까지 7개의 프로세스가 있다고 가정해보겠습니다.

그러면 waiting 배열의 크기는 7이 되고 각 인덱스는 해당 프로세스의 준비 상태를 나타나게 됩니다.

배열의 값들은 모두 FALSE로 초기화되어 있고 아직 Critical Section에 들어갈 준비가 된 프로세스가 없다는 뜻입니다.

그럼 이제 하나하나 살펴보도록 하겠습니다.

// ---- 1. 각각의 프로세스들이 해당 코드에 진입하게 되면 각 프로세스의 해당하는 waiting 배열의 값을 TRUE로 바꿈으로써

Critical Section에 들어갈 준비가 됐다는 것을 의미합니다. 예를 들어 P0, P2, P4, P5가 진입하여 준비가 되었다고 하고

그중에 P2가 가장 먼저 도착했다고 가정해봅시다.

// ---- 2. P2가 먼저 도착하여 while 문을 들어가게 되면 TestAndSet 함수를 통해 lock을 얻고 P2는 진입한다는 의미로 waiting 배열의 값을 FALSE로 바꿔 준 후 Critical Section에 진입하고 나머지 프로세스들은 lock이 TRUE로 인한 TestAndSet의 반환값이 TRUE이므로 계속해서 while 문에서 대기하게 됩니다.

// ---- 3. P2가 Critical Section을 수행하고 자기 보다 큰 번호의 프로세스들 중 가장 작은 프로세스를 선택하게 됩니다. i는 현재 2이고 배열의 크기는 7이기 때문에 j의 값은 3이 되게 됩니다. 하지만 P3은 준비가 되어 있지 않은 상태이기 때문에 다시 한번 while 문 안으로 들어가 다음 프로세스가 준비되어 있는지를 검사하게 됩니다. 그리하여 j는 4가 되어 P4가 선택되고 waiting[j]가 FALSE가 되기 때문에 P4는 2번의 while 문을 벗어나 Critical Section을 들어가게 됩니다. 이런 식으로 모든 waiting 배열의 값이 FALSE가 되어 전부 통과되었다면 마지막 프로세스의 차례에서는 i와 j가 같아지게 됩니다. 그렇게 되면 서로 돌려가지던 lock을 최종 반납하고 모두 Critical Section을 벗어나게 됩니다.

오늘은 충돌을 피하는 방법으로 TestAndSet(), Swap() 명령어들을 살펴보았는데요.

다음 방법도 설명하려면 글이 길어지기 때문에 일단 여기서 끊고

다음 포스팅에서는 Semaphore에 대해 알아보도록 하겠습니다.

감사합니다.