데이터의 접근

Race Condition

여러 E-Box가 S-Box를 공유하는 경우 Race Condition의 가능성이 있다. 경쟁상태란 둘 이상의 입력 또는 조작이 타이밍이나 순서에 따라 결과값에 영향을 줄 수 있는 상태를 뜻한다.

OS에서 race condition은 언제 발생하는가?

커널 수행 중 인터럽트가 발생한 경우
프로세스가 시스템콜을 하여 커널모드 수행 중일 때 문맥교환이 일어나는 경우
멀티 프로세서에서 공유데이터를 사용하는 프로세스들이 커널 내부 데이터를 접근하는 경우

[1번 경우 해결방안]

interrupt disable/enable로 인터럽트의 처리여부를 조정한다. 데이터를 건드리는 경우에 인터럽트가 들어와도 작업이 끝날 때까지 인터럽트를 처리하지 않도록(disable) 한다. 데이터 처리 작업이 완료된 후, 인터럽트로 넘겨서 인터럽트를 수행(enable)한다.

[2번 경우 해결방안]

두 프로세스 간에 데이터 공유가 없다고 하더라도 시스템 콜이 일어나서 커널모드로 작동하는 경우에는 커널주소공간의 데이터를 공유할 수 있게 된다. 이 경우 중간에 CPU를 빼앗아 가면(preempt) 경쟁상태가 발생한다. 해결방안은 커널모드에서 수행중일 때는 CPU를 뺏는(preempt) 것을 금지한다.

[3번 경우 해결방안]

멀티 프로세서 환경의 경우 어떤 CPU가 마지막으로 데이터에 접근해서 값을 조정했는지에 따라 경쟁상태가 일어날 수 있다. interrupt disable/enable로 해결이 불가하다. 해결방안으로 1. 한번에 하나의 CPU만 커널에 진입가능하게 하는 방법, 2. 커널 내부에 있는 각 공유데이터에 접근할 때마다 그 데이터에 대해 lock/unlock을 하는 방법 이 있다. 1번 방법은 하나의 CPU에만 접근하게 되니 멀티 프로세서의 장점을 살리지 못하고 상당히 비효율적이다.

Process Synchronization

공유데이터에 대한 동시접근은 데이터 불일치 문제를 발생시킬 수 있다. 데이터의 일관성을 유지하기 위해서는 협력 프로세스 간의 실행순서를 정해주는 메커니즘이 필요하다. 경쟁상태를 막기 위해서는 concurrent process는 동기화(synchronization) 되어야 한다. low-level 언어로 작성하지 않는 프로그램에서 기계어 수준으로 작동하기 위해서는 여러 줄의 코드가 실행되기 때문에 그 시간차이(코드수행의 시간차이)에 의해서 프로세스 동기화 이슈가 중요하게 되는 것 같다.

Critical-Section(임계구역)

여러개의 프로세스가 공유데이터에 동시에 접근할 경우 critical-section problem이 발생할 수 있다. 각 프로세스의 코드영역에는 공유데이터를 접근하는 코드인 critical section이 존재한다. 동시에 critical section에 들어갈 수 없게 만들어 이 문제를 해결한다. 다시 말해서 하나의 프로세스가 critical section에 있다면 다른 모든 프로세스는 critical section에 들어갈 수 없도록 한다.

프로그램적 해결법의 충족조건

상호배제(Mutual Exclusion) : critial section 부분을 수행 중인 프로세스가 있다면 다른 모든 프로세스들은 critical section에 들어가면 안 된다.
진행(Progress) : 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있다면 들어가게 해주어야 한다.
유한대기(Bounded Waiting) : 프로세스가 critical section에 들어가기 위해 무한정 기다리는 상황이 발생하면 안 된다. 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.

알고리즘1 (Alternating algorithm)

자신의 turn에만 critical section을 수행하는 방식이다. 프로세스가 P0,P1이 있는 경우를 가정하여 수도코드로 예를 들어보자.

//Synchronization variable
	int turn;
	intially turn = 0; 
      // P[i]인 프로세스가 자신의 턴이 되기 위해서는 turn = i 가 되어야 한다

//Process P0
	do{
	  while (turn != 0); // turn이 본인 순서가 아니면 대기한다
	  critical section // 본인 순서이면 critical section을 수행
	  turn = 1; // critical section 사용이 끝나면 다른 프로세스의 turn으로 바꿔준다.
	  remainder section //  critical section 이 아닌 다른 section의 작업을 수행
	} while (1);

다른 프로세스가 critical section를 수행하고 나서 턴을 바꿔줘야 자신이 차례가 될 수 있다. 누군가 crtical secion에 접근하지 않으면 turn도 바꿔주지 않기 때문에 progress 문제가 발생한다.

알고리즘2

flag를 사용하여 자신이 critical section을 사용하고 있음을 알리는 방식이다. 프로세스 P0,P1이 있는 경우를 가정하여 수도코드의 예를 들어보자.

//Synchronization variables
	boolean flag[2];
	initially flag[모두] = false; // 처음에는 모두 false로 초기화
	// if (flag[i] == true) 이면 P[i]가 critical section에 들어갈 준비가 된 것이다.

//Process P[i]
	do{
    	  flag[i] = true; // 자신의 flag를 true로 설정
          while (flag[j]); // 다른 flag가 true로 설정되어 있는지 확인하고, true 이면 대기
          critical section // 다른 flag가 true가 아니라면 critical section 수행
          flag[i] = false; // 자신의 flag를 다시 false로 설정
          remainder section // 그 외 section을 수행
	} while (1);

서로 아직 critical section을 수행하지 못했는데 둘 다 flag를 true로 설정한 상태라면 계속 critical section에 접근할 수 없기 때문에 progress 문제가 발생한다. 이 경우에도 critical section에 들어갔다 와야 flag를 내릴 수 있기 때문에 누구도 진입하지 못하게 된다.

알고리즘3 (Peterson's algorithm)

turn과 flag를 모두 사용하는 방식이다. 역시 프로세스 P0,P1이 있는 경우를 가정하여 수도코드의 예를 들어보자.

//Combinated synchronization variables of algorithm 1 and 2

//Process P[i]
    do{
      flag[i] = true; // 깃발들기
      turn = j; // 상대편으로 순서 바꿔주기
      while (flag[j] && turn == j); // 상대방이 깃발을 들고 상대방 순서일때 대기
      critical section // 아닐 경우 자신의 critical section 진행
      flag[i] = false; // 자신의 깃발 내려놓기
      remainder section // 나머지 코드 실행
    } while (1);

자신의 깃발을 들고, 턴은 상대로 바꿔준다. 상대방의 턴과 순서가 본인일 경우에만 critical section이 진행되기 때문에 3가지 해결법의 충족조건을 만족한다.

여기서의 문제점은 busy wait (spin lock)이 발생할 수 있다는 것이다. 이것은 CPU 자원을 계속 사용하면서 critical section에는 들어가지 못하고 기다리는 경우를 의미한다. critical section을 사용할 수 있는 조건인지 계속 확인하는 과정 (수도코드에서 while문)을 뜻한다.

Synchronization Hardware

멀티 프로세서 환경에서는 critical section으로 프로그램적으로 동기화를 관리하는 것은 비효율적이기 때문에 hardware 수준에서도 동기화를 위한 명령어나 메커니즘이 존재한다. 다음 시리즈에서 synchronization hardware를 정리해보도록 하겠다.

정리

데이터 자원을 공유하는 경우, 다른 프로세스가 작업 중인 데이터 자원에 접근해서 값을 변경한다면 데이터의 일관성이 깨질 수도 있다. 이런 상태를 race condition (경쟁상태)라고 한다. 접근하는 순서에 따라 데이터의 결과 값이 달라질 수도 있다. 이런 문제를 해결하기 위해서 동기화(synchronization)로 데이터의 값을 유지하고자 하는 메커니즘들이 존재한다. critical section과 프로그래밍적 측면에서 해결방법 3가지 충족조건, 해결 알고리즘에 대해 정리해 보았다. 멀티 프로세서 환경에서는 프로그래밍 측면에서만 동기화를 진행하는 것은 비효율적인 측면이 많기 때문에 다음 시리즈에서는 하드웨어 측면에서의 동기화에 대해 정리해보려고 한다.

(프로그래밍적 부분과 하드웨어 부분으로 동기화를 나누는 부분이 맞는지, 약간 혼란스러움을 느꼈다. 특히, 이 부분은 자료를 찾아보며 내가 이해한 방식으로 정리하고 있기 때문에 틀린 내용일 수도 있다.)

운영체제 시리즈는 반효경 교수님의 운영체제 강의 와 "운영체제와 정보기술의 원리"라는 책을 바탕으로 정리한 내용입니다.

저작자표시