동기화 도구들이 왜 필요할까?
- 협력적 프로세스가 데이터를 공유하는 방법
협력적 프로세스 : 시스템 내에 실행 중인 다른 프로세스에게 영향을 주거나 받는 프로세스- 논리 주소 공간(코드, 데이터)을 직접 공유, 공유 메모리, 메시지 전달
→ 공유 데이터를 동시에 접근하면 데이터의 일관성을 망칠 수 있음
- 데이터의 일관성을 유지하기 위해
- 논리 주소 공간을 공유하는 협력적 프로세스의 질서 있는 실행을 보장
- 프로세스가 병행 또는 병렬로 실행될 때 공유하는 데이터의 무결성에 문제를 일으킴
문제가 발생하는 예시
static int count = 0; // 전역 변수
// 스레드 t1은 count를 1씩 더함
Task t1 = new Task(() => { for (int i = 0; i < 10000; i++) count++; });
// 스레드 t2는 count를 1씩 뺌
Task t2 = new Task(() => { for (int i = 0; i < 10000; i++) count--; });
t1.Start();
t2.Start();
t1.Wait();
t2.Wait();
Console.WriteLine($"count : {count}");
- C# 코드인데, 병행적으로 두 스레드를 실행시킨다.
- count라는 공유 데이터를 건드린다.
- 둘 다 똑같은 횟수를 더하고 빼기 때문에 출력은
- count : 0이 나와야 한다.
실행 결과
- 전혀 다른 값이 나온다.(실행할 때마다 달라짐)
이러한 결과가 나오는 이유 - 경쟁 상황(race condition)
- count++는 기계어로 변환될 때 3가지 코드로 나뉜다.
- register1 = count
register1 = register1 + 1
count = register1
- register1 → 한 CPU만 접근할 수 있는(local) 레지스터
- count— 또한 마친가지
- register2 = count
register2 = register2 - 1
count = register2
- register1과 register2가 동일한 물리적 레지스터라도,
레지스터의 내용은 인터럽트 처리기에 의해 메모리에 보관됐다가 다시 적재된다.
- count++와 count— 문장을 병행하게 실행하는 것은 앞의 기계어 문장들을 뒤섞어 실행하는 것과 같음
기계어들의 순서가 뒤섞임
- 이러한 상황을
경쟁 상황이라고 함
경쟁 상황(race conditon)
- 동시에 여러 개의 프로세스가 동일한 자료에 접근하여 조작
- 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황
- 경쟁 상황을 보호하기 위해 하나의 프로세스만이 변수를 조작할 수 있도록 보장해야 함
→ 어떤 형태로든 프로세스 동기화가 필요함
- 많은 부분이 협력하는 프로세스 간의 프로세스 동기화와 조정에 할애됨
임계구역 문제(The Critical-Section Problem)
- 각 프로세스에는 임계구역(Critical section)이라고 부르는 코드 부분이 포함
- 그 안에서 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신 가능
- 한 프로세스가 자신의 임계구역에 들어와 있는 동안
다른 프로세스들은 그들의 임계구역에 들어갈 수 없다.
→ 두 프로세스는 동시에 각각의 임계구역을 실행할 수 없음
전형적인 프로세스의 일반적인 구조
임계구역 문제 : 프로세스 협력적 데이터 공유를 위해 자신의 활동 동기화 시 사용 가능한 프로토콜 설계
프로세스 일반적인 구조
entry section(진입 구역)
- 각 프로세스가 자신의 임계 구역으로 진입하기 위해서는 진입 허가를 요청해야 한다
- 이러한 요청을 구현하는 코드 부분
critical section(임계 영역)exit section(퇴출 구역) : 임계 구역에서 나가는 부분remainder section(나머지 구역) : 코드의 나머지 부분들을 총칭
임계 구역 해결을 위한 세 가지 요구 조건
상호 배제(mutual exclusion)
- 하나의 프로세스가 자신의 임계구역에서 실행된다면,
다른 프로세스들은 자신의 임계구역에서 실행될 수없다.
진행(progress)
- 현재 임계 구역에서 실행되는 프로세스가 없고, 임계 구역으로 진입하려는 프로세스들이 있는 경우
→ 나머지 구역에서 실행 중이지 않은 프로세스들만 임계 구역 진입의 후보가 될 수 있음
한정된 대기(bounded waiting)
- 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후부터 그 요청을 허용될 때까지,
다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용하는 횟수에 한계가 있어야 함
운영체제에서의 경쟁 조건 해결책
- 임의의 한순간에 많은 커널 모드 프로세스들이 운영체제 안에서 활성화될 수 있다.
→ 운영체제를 구현하는 코드(커널 코드)는 경쟁 조건이 발생하기 쉽다.
- 예시
- 시스템의 모든 열린 파일의 리스트를 유지하는 커널 자료구조
- 새 파일이 열리거나 닫히면 수정되어야 한다.
- 두 프로세스가 동시에 파일을 열려고 한다면,
리스트에 대한 개별적인 갱신으로 경쟁 조건 발생
- 두 프로세스가 fork() 시스템콜로 자식 프로세스를 생성할 때
- 프로세스 식별자를 부모 프로세스로 반환한다.
- 반환받을 때 커널 변수에서 경쟁 조건 발생
- 경쟁 조건이 발생하기 쉬운 커널 자료구조
- 메모리 할당 관리하는 자료구조
- 프로세스 리스트를 유지하는 자료구조
- 인터럽트 처리를 위한 자료구조
- 운영체제에서 경쟁조건이 발생하지 않도록 보장하는 것은 커널 개발자의 책임
- 단일 코어 환경일 경우
- 공유 변수를 수정하는 동안 인터럽트 발생하는 것을 막을 수 있다면 임계구역 문제 해결 가능
- 현재 실행 중인 명령어들을 선점 없이 순서대로 실행할 수 있는 확신 가능
- 다른 명령어가 실행되지 않으므로 공유 변수를 예기치 않게 수정되지 않는다.
- 다중 처리기 환경일 경우
- 단일 코어 환경일 때의 방법은 실현되지 않을 수 있음
- 메시지가 모든 프로세서에 전달 → 다중 처리기에서 인터럽트를 비활성화하면 시간이 많이 걸림
- 메시지 전달은 각 임계구역으로의 진입을 지연시키고 시스템 효율성을 떨어뜨림
- 클록이 인터럽트로 업데이트되는 경우 시스템 클록에 미치는 영향도 고려해야 함
- 일반적으로 선점형 커널과 비선점형 커널 2가지 방식이 사용
선점형 커널과 비선점형 커널
선점형 커널
- 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용
- 한순간에 커널 안에서 실행 중인 프로세스가 하나밖에 없다는 확신이 없음
→ 커널 자료구조에서 경쟁 조건이 발생하지 않는다는 것을 보장하도록 신중히 설계해야 함
- SMP(대칭형 다중 처리) 구조에서 선점형 커널을 설계하는 것이 특히 어려움
→ 서로 다른 처리기의 두 프로세스가 동시에 커널 모드에 있을 수 있기 때문
비선점형 커널
- 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않는다.
- 커널 모드 프로세스는 커널을 빠져나가거나 봉쇄되거나,
자발적으로 CPU를 양보할 때까지 계속 실행
- 한순간에 커널 안에서 실행 중인 프로세스가 하나밖에 없다는 것을 보장
→ 커널 자료구조에 대한 경쟁 조건을 염려할 필요 없음
- 비선점형 커널보다 선점형 커널을 선호하는 이유
- 선점형 커널이 응답에 더 민첩하다.
← 커널 모드 프로세스가 대기 중인 프로세스에 처리기를 양도하기 전에 장기간 실행할 위험이 적음
- 선점형 커널은 실시간 프로세스가 현재 커널에서 실행 중인 프로세스를 선점할 수 있음
→ 실시간 프로그래밍에 더 적합
Peterson의 해결안
- 임계구역에 대한 고전적인 소프트웨어 기반 해결책
- 임계구역 문제를 해결하기 위한 좋은 알고리즘적인 설명을 제공
- 임계구역 요구 조건을 중점으로 소프트웨어 설계에 필요한 복잡성을 잘 설명
- 현대 컴퓨터 구조가 기본적인 기계어를 수행하는 방식 때문에 현대 컴퓨터 구조에는 안 맞을 수도 있음
Peterson 해결안 구조
- 두 개의 프로세스 P(i)와 P(j)가 있다고 가정
왼쪽 : P(i)의 구조 // 오른쪽 : P(j)의 구조
- 임계구역과 나머지 구역을 번갈아 가며 실행하는 두 개의 프로세스로 한정
- 두 프로세스가 두 데이터 항목을 공유하도록 하여 해결
- int turn;
turn : 임계구역에 진입할 순번
- turn == i 면 프로세스 P(i)가 임계 구역에서 실행될 수 있음
- boolean flag [2];
flag 배열 : 프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타냄
- flag [i] == true면 P(i)가 임계구역으로 진입할 준비가 되었다는 것을 나타냄
- 임계구역 진입을 위해 P(i)는 먼저 flag [i]를 true로 하고 turn = j로 지정
→ 프로세스 j가 임계구역 진입을 원한다면 진입 가능을 보장
- 두 프로세스가 동시에 진입하려면? → turn이 동시에 i와 j로 지정되어야 함
→ 그것은 불가능
임계구역 요구조건 충족 증명
1. 상호 배제가 제대로 지켜진다는 사실
- P(i)가 임계구역에 들어가기 위해서는 flag [j] == false 또는 turn == i
- 두 프로세스가 모두 자기 임계 구역을 수행 중이기 위한 조건
- flag [0] == flag [1] == true → turn의 변수 값이 0과 1이 동시에 될 수 없음
→ 둘 중 하나만이 while문을 지나갈 수 있음 → 상호배제는 지켜짐
2. 진행에 대한 요구조건, 3. 대기시간이 한없이 길어지지 않는다는 사실
- 임계 구역에 진입 못하도록 막는 방법은 while문에서 무한 루프를 돌리는 방법
- P(i)나 P(j)가 임계구역에서 나올 때 상대방의 flag를 false로 바꾼다.
- 무한루프를 돌 때는 turn 값을 바꾸지 않는다.
→ 두 프로세스 중 하나가 예전에 진입했다면 이번엔 자기도 한 번은 들어갈 수 있게 보장받는다.
Peterson의 해결안이 최선 컴퓨터에 작동하지 않는 이유
- 프로세서 및 컴파일러가 종속성 없는 읽기 및 쓰기 작업은 재정렬할 수 있기 때문
→ 다중 스레드 응용 프로그램의 경우 명령 순서가 바뀌면서 데이터 일관성이 깨짐
- Peterson의 해결안에서 미치는 영향
- 진입 구역에 나타나는 첫 두 문장의 순서가 바뀔 수 있다.
- 두 스레드가 동시에 임계구역이 활성화될 수 있음