Data Race

• 동기화는 프로세스 내에서 사용되는 **데이터의 일관성(Data Consistency)**를 보장하는 행위
• 해당 데이터를 여러 프로세스 혹은 쓰레드에 의해 공유되고 조작하려는 행위로부터 보호하는 것
• 데이터가 경쟁 상태로 존재하는 것은 Data Race라고 부름
  • 공유된 데이터가 동기화 되지 않으면 Data Race 때문에 데이터 일관성이 유지되지 않음

Atomic

• 원자성을 의미하는 단어
  • 문자 그대로 기능적으로 분할할 수 없는 성질을 의미
  • 원자성 조작(Atomic Operation)은 Atomic 성질을 보장하기 위한 의도적인 조작
• 프로그램 상에서 Atomic하다는 것의 판단 기준은 Interruptible
  • 원자성이 보장된 코드들은 Interrupt를 받지 않음
• Instruction은 Atomic하기 때문에, 이를 수행하는 중에는 Interrupt가 발생하지 않음
• 하지만 코드 한줄에는 여러 Instruction이 구성되기 때문에 Atomic하지 않음
• Context Switch는 Dispatcher의 Interrupt에 의해 발생
  • 따라서 코드 한 줄 수행 중에도 Context Switch가 발생할 수 있음

Critical Section

• 여러 프로세스 혹은 쓰레드들이 공유하는 데이터들이 있을 때 이를 접근하는 코드 영역
• Critical Section에 대해서는 하나의 프로세스 혹은 쓰레드가 진입했을 때 다른 프로세스나 쓰레드가 진입하면 안됨
• 동기화를 성공적으로 제공하기 위해서는 아래 3조건을 모두 만족해야 함
  • 특히 Mutual Exclusion과 Progress는 필수적임

Mutual Exclusion

• 하나의 프로세스 혹은 쓰레드가 Critical Section에 진입해있다면, 다른 프로세스들은 Critical Section에 진입할 수 없어야 함

Progress

• Critical Section이 어떤 프로세스에게도 점유되어 있지 않고 Critical Section에 진입하려는 프로세스가 존재한다면, 그 중 한 프로세스는 Critical Section에 진입할 수 있어야 함

Bounded Waiting

• 어떤 프로세스가 Critical Section에 진입하고자 할 때, 해당 프로세스가 무한히 기다리지 않도록 대기시간에 적절한 제한이 필요함

Synchronization

Perterson Solusion

/*
** Shared Variables
** int turn;
** bool flag[2];
** turn = 0;
** flag[0] = flag[1] = false;
** turn == 1 이고 flag[1] == true 라면, 프로세스 A가 대기
** turn == 0 이고 flag[0] == true 라면, 프로세스 B가 대기
*/

/*
** 프로세스 A
*/

flag[0] = true;
turn = 1;
while (flag[1] && turn == 1)
	;
		Critical Section
flag[0] = false;
		Remainder Section

/*
** 프로세스 B
*/

flag[1] = true;
turn = 0;
while (flag[0] && turn == 0)
	;
		Critical Section
flag[1] = false;
		Remainder Section

• 공유변수 turn과 flag 배열을 모두 이용한 방법
• Mutual Exclusion을 만족
• 동일한 프로세스가 연속적으로 스케줄링 되더라도 flag 배열 때문에 문제 없음
• 다른 프로세스가 동시에 flag를 true로 만드는 부분도 공유 변수 turn이 막음
• Progress를 만족하면 Bounded Waiting은 적절히 제어할 수 있음
• 다만 확장성에서 한계가 있음

Instruction Solution

/*
** Acquire LOCK
**     Critical Section
**
** Release LOCK
**     Remainder Section
*/

• 결국 동기화를 위한 해결 방안은 Atomic을 보장하는 것
• Critical Section 진입에 대한 알고리즘을 Instruction으로 두어 Atomic하게 만들음
  • 기존 소프트웨어 알고리즘으로 복잡하게 해결하던 것을 하드웨어 상에서 해결
• Critical Section에 진입하기 위한 권한을 획득하는 행위 (Acquire)을 Lock
• Critical Section에서 나갈 때 권한을 넘기는 행위 (Release)를 Unlock
• 동기화를 위한 Atomic한 Instruction으로는 Test-and-Set과 Swap이 있음
  • Lock을 잡는 과정에서는 Context Switch가 발생하지 않음
  • Lock을 잡고 난 후 Critical Section을 처리할 때는 Context Switch가 발생할 수 있음
    • Context Switch된 다른 프로세스는 Lock을 가지고 있지 않음
    • Critical Section에 진입하지 못한 채로 Busy Waiting을 하게 됨
  • Mutual Exclusion와 Progress에 대한 확장성은 보장하나 Bounded Waiting까지는 해결하지 못함
• Bounded Waiting을 처리하기 위해서는 보다 Primitive한 해결방법이 요구됨