🧭 CS Study - 운영체제

🚩 주제 : Process Synchronization

🎥 강의 : KOCW 운영체제 강의 - 이화여자대학교 반효경 교수님

Process Synchronization

데이터 접근 패턴

1. Data 저장 위치 찾기
2. 연산할 Data 가져오기
3. 연산
4. 연산 결과 저장

Race Condition

여러 주체가 하나의 데이터(공유메모리)에 접근하려고 할 때의 상황이다. 이때 발생하는 문제를 조율하는 방법이 필요하다. 커널 내부 데이터를 접근하려는 루틴들 간에도 발생할 수 있다.

Race Condition 발생 예시

1. Kernel 코드 수행시에 Interrupt가 발생하는 경우
   : 커널 코드이기 때문에 커널 주소를 공유한다.
   : 인터럽트를 무시했다가 원래 하던일이 마무리 되면 인터럽트를 받아들이는 방식으로 문제를 해결한다.

2. Process가 System call을 해서 Kernel mode수행 중인데 context switch가 발생하는 경우
   : 커널 모드에서 수행중일 때는 CPU를 빼앗지 않는다. 사용자 모드로 돌아갈 때 CPU를 빼앗는다.

3. CPU가 여러개 있는 환경
   : 커널 내부 공유 데이터에 접근할 때 데이터에 lock을 걸고 저장이 끝나면 unlock을 하는 방식으로 해결한다.

Process Synchronization 문제

공유 데이터에 동시 접근할 때 데이터 불일치의 문제가 발생할 수 있다. 일관성 유지를 위해서는 공유데이터에 접근하는 프로세스 간의 실행 순서를 정해주는 구조가 필요하다.
Race Condition은 여러 프로세스들이 동시에 공유 데이터에 접근할 때 발생한다. 이를 막기 위해서는 concurrent process가 동기화 되어야 한다.

Critical Section

• 공유 데이터에 접근하는 코드이다.
• 공유데이터를 접근하는 코드 이전에 entry section을 걸어서 lock을 주고 exit section을 해결하는 문제도 있다.

Critical section문제를 해결하기 위한 충족 조건

• Mutual Exclusion(상호 배제) : 어떤 프로세스가 critical section에 들어가 있으면 다른 모든 프로세스는 들어가면 안된다.
• Progress(진행) : critical section에 아무도 들어가 있지 않은 상태에서 접근하고 싶어하는 프로세스가 있다면 들어가게 해주어야 한다.
• Bounded Waiting(유한 대기) : starvation이 생기지 않기 위해서, 어떤 프로세스가 critical section에 들어가려고 요청한 이후부터는 그 요청이 허용될 때까지 다른 프로세스가 거기에 접근하는 횟수에 한계가 있어야 한다.

위 세 가지 조건을 잘 만족하면서 entry section에서 lock을 걸고 exit section에서 lock을 풀어주는 알고리즘은 아래와 같다.

알고리즘 1. 동기화 변수(turn)를 사용한다.

int turn;  //turn은 프로세스의 차례를 이야기함
turn = 0;

do{
	while(turn != 0); //내 차례(0)가 아니라면 계속 기다림
    critical section  //내 차례가 되면 critical section 수행
    turn = 1; 		  //다른 프로세스에게 차례를 넘긴다.
    remainder section
}while(1);

• Progress 조건을 만족하지 못한다.
• Mutual Exclusion은 만족한다.
• critical section이 프로세스 교대로 동작하게 만든다.
• 프로세스들의 critical section에 들어가야햐는 빈도가 다를 수 있는데 동일하게 교대로 동작하기 때문에 제대로 동작하지 않는다.

알고리즘 2. 동기화 변수(flag)를 사용한다.

boolean flag[k];  //프로세스의 차례를 이야기함, flag가 true이면 critical seciton에 접근
flag[0] ~ flag[k-1] = false;

do{
	flag[i] = true;
	while(flag[j]); 	//내 차례(i)가 아니라면 계속 기다림
    critical section  	//내 차례가 되면 critical section 수행
    flag[i] = false;	//다른 프로세스에게 차례를 넘긴다.
    remainder section
}while(1);

• progress 조건을 만족하지 못함 : 둘 다 true가 되어 끊임없이 양보하는 상황 발생

알고리즘 3. Peterson의 알고리즘 - flag과 turn을 둘 다 사용함

do{
	flag[i] = true; //의사표현
    turn = j; //상대방 turn으로 바꿔둠
	while(flag[j] && turn == j;); 	//내 차례(i)가 아니라면 계속 기다림
    critical section  	//내 차례가 되면 critical section 수행
    flag[i] = false;	//다른 프로세스에게 차례를 넘긴다.
    remainder section
}while(1);

• 모든 충족 조건을 만족함
• Busy Waiting(=Spin lock)이 발생함(계속 CPU와 메모리를 사용하면서 wait한다.)

고급 언어의 코드에서는 명령어 중간에 cpu를 빼앗길 수 있기 때문에 이렇게 소프트웨어적으로 복잡한 코드가 만들어진다. 이러한 문제는 하드웨어적으로, test & modify를 atomic하게 처리할 수 있게 하면 해결된다.(Test_and_Set() 명령어 사용) 보통의 경우는 프로그래머를 위해 Semaphores라는 것을 지원한다.