Process Synchronization1

• 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다.
• 일관성(consistency)유지를 위해서는 협력 프로세스 (cooperating process)간의 실행 순서(orderly execution)을 정해주는 메커니즘 필요

Race Condition

• 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
• 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐

• S-Box(Memory address space) 를 공유하는 E-Box(CPU-Process)가 여럿 있을 경우 Race Condition의 가능성이 있음
  • ( -> count = 5일때 각 E-Box가 연산 후 저장할때 4,6 어떤값이 저장될지 모름)
• OS에서 Race Condition은 언제 발생하는가?
  • kernel 수행 중 인터럽트 발생 시
    • 해결책 : 중요 변수 값을 변경하는 중에는 Interrupt가 발생해도 인터럽트 처리 루틴으로 보내는 것이 아니라 Interrupt가 발생하지 않도록 조치
  • Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
    • 해결책 : 커널 모드에서 수행중일 때는 CPU를 preempt하지 않음.
    • 커널 모드에서 사용자 모드로 돌아갈 때 preempt
  • Multiprocessor에서 shared memory 내의 kernel data
    • 해결책 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 하는 방법

race condition을 막기 위해서는 concurrent process는 동기화(syschronize)되어야 한다.

 

Critical Section Problem

• n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
• Problem
  • 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

 

Initial Attempts to Solve Problem

• 두 개의 프로세스가 있다고 가정 P0, P1
• 프로세스들의 일반적인 구조

• 프로세스들은 수행의 동기화(Synchronize)를 위해 몇몇 변수를 공유할 수 있다. -> synchronization variable

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

• Mutual Exclution
  • 프로세스 Pi가 critical section 부분을 수행중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안됨
• Progress
  • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있다면 critical section에 들어가게 해준다.
• Bounded Waiting
  • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
• 가정
  • 모든 프로세스들의 수행 속도는 0보다 커야 한다.
  • 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

Algorithm 1

• Synchronization variable
  • int turn;
  • initially turn = 0;   =>   Pi can enter its critical section if(turn == 1)
• Process P0

• Satisfies mutual exclusion, but not progress
  
  • 즉, 과잉 양보 : 반드시 한번씩 교대로 들어가야만 함(swap - turn), turn 값을 내 값으로 바꿔줘야만 내가 들어갈 수 있음. 특정 process가 더 빈번히 critical section을 들어가야 한다면?

Algorithm 2

• Synchronization variable
  • boolean flag[2];
  • initially flag[모두] = false;
  • Pi ready to enter its critical section if(flag[i]==true)
• Process Pi

• Satisfies mutual exclution, but not progress requirement
• 둘 다 2행까지 수행 후 끊임 없이 양보하는 상황 발생 가능

Algorithme 3 (Peterson's Algorithm)

• Combined synchronization variables of algorithm 1 and 2
• Process Pi

• Meets all three requierments; solves the critical section problem for two processes
• Busy Waiting = spin lock (계속 CPU와 memory를 쓰면서 wait)

Synchronization Hardware

• 하드웨어 적으로 Test&Modify를 atomic 하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결 가능

• Mutual exclution with Test & Set instruction