Concurrency는 프로그램의 성질이고 parallism은 기계의 성질이다.
Concurrency(병행성) - 프로그램 여러 부분들이 순서에 상관없이 부분순서(partial-order)로 수행될 수 있는 능력을 일컫는다. 어떤 프로그램이나 알고리즘이 순서에 상관없이 동시에 수행될 수 있다면 concurrent하다고 말한다. 예를들어 1부터 100까지 숫자를 더하는 과정을 생각해보자면 숫자 100개를 여러 부분 집합으로 나눈 뒤 동시에 부분합을 구한다. 그리고 이 부분합을 다시 더하면 원래 얻고자 하는 값을 얻을 수 있다. 이 때 이 알고리즘을 concurrent하다고 말한다.
그런데 이 알고리즘이 정말 물리적으로 병렬로 돌아갈지 아닐지는 이 알고리즘이 어떤 하드웨어 위에서 돌아가는지 알아야 확답을 할 수 있다. 만약 알고리즘이 멀티 프로세서 머신에서 돌아간다면 병렬 실행 된다고 말 할 수 있다. 따라서 parallism은 프로그램의 성질이 아닌 하드웨어의 성질이라고 할 수 있다.
Concurrency는 Single Core의 프로세서라면 Time-sharing통해 CPU를 나눠 사용함으로서 Concurrency를 느낄 수 있도록 한다.
Multi Core의 경우엔 물리적으로 병렬로 작동할 수 있다.
Parallelism(병렬성)
Concurrency와 다르게 실제로 작업이 병렬적으로 처리가 되는것이다.
오직 Multi Core에서만 가능하다.
Race Condition(경쟁 조건 상태)
Spolling기법은 프린터에 대표적으로 적용된다. 프린트를 할 때 인쇄를 맞긴 프로그램(Word)은 프린터가 인쇄를 다 할때까지 사용이 불가능한게 아니다. 프린트할 file들을 프린터디스크로 옮기면 Word입장에서의 프린트는 이미 끝났다. 이 떄 옮겨진 파일들은 Spoller directory에 저장되며 이는 Queue와 비슷하다.
만약 프로세스A와 프로세스B가 모두 Spoler에 파일을 동시에 기록하려한다. Spoler에는 6번 메모리까지만 file이 쓰여있다.
이럴 경우 7번 메모리에는 어떤 파일이 쓰여있을지 알 수 없다. 각각이 다른 타이밍에 차례대로 메모리에 접근한다면 이런 문제는 없을 것이지만 파일이 언제 쓰여질지를 전부 알 수 없다.
이를 동일한 메모리에 동시에 접근하려한다. -> 경쟁상태(race condition)이라 한다.
Race condition의 예)
각각의 지역의 투표수를 counting하는 장치가 있고 이 장치들은 메인서버로 신호를 보낸다. 또한 각각의 신호는 메인서버의 프로세스들이 담당한다. 3개의 프로세스들은 total이라는 메모리 공간을 공유한다. 이런상황에 발생하는 문제가 있다.
프로세스 A와 B가 동일한 주소공간인 R1이라는 장소에 접근한다. Total을 Load해와서 CPU의 R1레지스터에 저장을 한다(메모리에서는 연산이 불가능 하므로) 이 후 1을 더해서 다시 Memory에 저장을 한다. 이럴 경우 동시에 같은 메모리에 접근하지 않기 때문에 문제는 발생하지 않는다. 하지만 이런 이상적인 시스템 코드의 진행은 말 그대로 이상적이기만하다. 왜냐하면 스케쥴러에 의해 어떤 코드가 어느 타이밍에 실행 될 지는 모르는 것이기 때문이다.
만약 프로세스A의 Add명령어가 실행되고 Store가 실행되지 못한 채 스케쥴러에 의해 CPU의 사용권이 A에서 B로 넘어가면서 레지스터 값들을 메모리에 저장했다고 가정할 경우 문제가 생긴다.
1. 프로세스 A가 메모리에서 Total 의 3이란 값을 R1레지스터로 가져옴.
2. 프로세스 A가 R1의 값에 1을 더해서 4가됨.
3. 스케쥴러에의해 CPU 사용권은 프로세스 B로 넘어가고 R1에 있던 값들은 메모리(TOTAL이 아님) 임시저장소에 저장됨
4. 프로세스B가 TOTAL을 가져옴 이 때 TOTAL의 값은 3번에서 TOTAL에 저장되지 못하였으므로 여전히 3임.
5. 프로세스B가 1을 더해서 4를 TOTAL메모리에 저장됨.
6. 프로세스A가 CPU사용권을 넘겨받아 임시저장소에 저장한 4를 가져오고 값을 TOTAL메모리에 저장함.
7. TOTAL메모리에는 4가 저장됨
분명 프로세스 2개가 2번을 더했지만 3->5가 아닌 3->4가 되었다. 이를 Race condition이라고 한다.
두 개 이상의 프로세스가 어떤 공유 데이터를 읽거나 쓰려고 할 때, 최종 결과는 누가 언제 수행되느냐에 따라 달라지는 상황을
Race condition이라고 한다.
Race condition을 피하기 위한..
Race condition을 피하기 위해선 둘 이상의 프로세스가 동시에 공유데이터에 대해 작업해서는 안된다.
이를 상호배제(Mutual exclusion)라고 한다.
Critical section(critical region): 공유 데이터를 접근하는 프로그램 코드부분
Race condition을 회피하는 단순한 방법
어떤 두 프로세스도 동시에 critical region에 있지 않도록 한다. 이는 명확한 해결책이 될 수 없다.
Race condition을 해결하기 위한 4가지 조건
1. 어떤 두 프로세스도 동시에 critical region에 있지 않아야 한다.
2. CPU 개수나 속도에 대해서는 어떤 가정도 하지 않는다.
3. Critical region밖에서 실행중인 어떤 프로세스도 다른 프로세스를 블록(차단)시켜서는 안된다.
4. Critical region에 들어가려는 어떤 프로세스도 무한히 기다려서는 안된다.
4가지 조건을 해결하는 부적절한 방법
인터럽트 금지
스케쥴러가 작동하려면 컴퓨터 내부 어딘가에는 Timer가 존재해야한다. 이 타이머를 꺼버려서 스케쥴러의 작동을 멈추는 방법이다. 이는 적절하지 않다.
lock변수(공유변수) 사용
어떤 공유 변수를 사용해서 critical region에 접근을 막는 방법도 있을 것이다. 하지만 이 변수부터 공유변수이기 떄문에 적절하지 않다
Mutual Exclusion(상호배제)의 실현
상호배제의 실현을 위해선 여러 이론이 존재한다.
Pure software solution vs hardware support
busy waiting vs non-bysy wating(sleep & wake)
solution 1. 엄격한 교대
프로세스간 번갈아가며 critical region에 진입시키겠다는 개념이다. 이는 Pure Software Approach로 Busy Wating방식이다.
단지 무한루프를 반복하며, CPU time을 소비한다. 즉 프로세스는 기다리는 동안 running상태가 된다.
프로세스는 turn이란 변수에 의해 제어된다. 0일경우엔 0번프로세스가 실행, 1일경우 1번 프로세스가 실행되는 방식이다.
하지만 이는 0과 1의 교대가 필수적이며 한 프로세스가 지속적으로 critical region에 접근할 수 없다. 즉 프로세스A가 지속적으로 counting할 수 없다.
또한 turn이란 변수 자체도 공유데이터다.
그리고 3번조건에 위배된다 프로세스 0은 critical region 밖에있는 프로세스 1에의해 블록(차단)될 수 있다.
solution 2
Dekker's solution(1965)- 프로세스 2개에 대하여
Peterson's solution(1981)- 프로세스 N개에 대하여
1. critical region에 들어가도 되는지 검사한다.
2. critical region에 들어간다.
3. critical region을 떠난다.(다른 프로세스가 진입할 수 있도록 한다.)
Peterson's Solution
void enter_region(int process) //process는 해당 프로세스 번호
{
int other; //다른 프로세스 번호
other = 1 - process; //0번 프로세스일 경우 1
interested[process] = TRUE; // 해당프로세스를 true로 설정
turen = process; //해당 프로세스인지 검사
while(turen == proocess && interested[other] == TRUE); //두 조건이 맞으면 critical region에 진입하고
// 아니면 busy waiting함
}
void leave_region(int process) //false로 설정해주어서 다른 프로세스가 들어갈 수 있도록
{
interested[process] = FALSE;
}interested배열에는 처음에 모두 false값이 들어가있다.
처음엔 어떤 프로세스도 critical region에 들어가있지 않은 상황에 프로세스 0이 enter_region을 불렀다고 한다면
interested[0] = true가 되며 turn = 0이 된다.
interested[1]값은 false이므로 enter_region을 바로 빠져나가게 된다. 이 상황에 프로세스1이 enter_region을 호출한다면 interested[0]이 false가 될 때까지 기다리게 되는데 이 상황은 프로세스0이 critical secion을 빠져나가기 위해 leave_region을 부를 경우에만 발생한다.
만약 두 프로세스가 거의 동시에 enter_region을 호출한 경우 각 호출은 turn의 값을 자기 프로세스 번호로 설정하게된다. 하지만 turn은 전역변수이므로 각 스레드는 trun변수를 공유한다 즉 둘 중 나중에 호출된 것만이 기록된다. 예를 들어 프로세스 1이 나중에 값을 변경하였다면 turn값은 1이된다. 두 프로세스가 while문에 이르게 되면 프로세스 0은 루프를 바로 빠져나가 critical_region에 들어가게 되는데 프로세스 1은 while문에 걸려 기다리게 되고 critical_region에 들어가지 못한다.
이러한 방식은 현대의 CPU구조에서는 메모리 읽기/쓰기 작업이 프로그램 코드의 제시된 순서대로만 진행되지 않는다. 명령어의 순차가 작성된 code순서로만 진행될 때에 가능한데 현대 cpu는 성능 향상을 위해 코드의 순서를 바꾸기도 하기때문에 이러한 방식은 사용이 불가능하다.