데이터의 접근
- CPU, DeviceController(컴퓨터 내부?), 프로세스 등 실행의 주체는 저장공간인 Memory, 디스크, 해당 프로세스의 주소 공간을 사용함
- E-box에서 데이터를 읽어와서 연산결과를 S-box에 저장
- 이러한 S-box를 공유하는 연산 과정으로 인해 Race Condition 문제가 발생
Race Condition
-
CPU나 프로세스의 접근 순서에 따라 공유하는 저장 공간 영역의 데이터에 대한 연산 결과가 달라짐
-
발생 가능한 경우
- Multiprocessor system
- 커널 모드 수행 중 timer interrupt 등의 interrupt로 다른 프로세스의 요청에 따른 커널 모드를 수행할 경우
- 커널 모드 수행 중 스케줄링에 따른 선점으로 context switch가 발생해 다른 process에게 CPU를 빼앗기고 해당 프로세스가 System call을 하여 커널 모드를 수행할 경우
Race Condition 1
- 커널모드에서 count 변수를 증가시키는 작업이 수행 중
- instruction이 increase까지 수행 중 interrupt 발생
- 인터럽트 처리 루틴이 count 변수를 1 감소 시키고 저장
- 인터럽트 처리 루틴: 기기마다 인터럽트를 처리하기 위해 정의해 놓은 O.S 상의 함수
- 기존 프로세스로 돌아와서 1 증가시킨 값을 저장
- 결과적으로 -1이 반영되지 않음
- 중요한 변수, 공유 영역을 처리 중일 시에는 interrupt를 disable하는 방법으로 문제를 해결할 수 있음
Race Condition 2
- Kernel mode에 time sharing 하면서 접근할 때 문제가 발생할 수 있음
- 이 경우에도 접근 순서에 따라 결과가 달라질 수 있음
- 커널 모드에서 수행 중일 때 CPU를 선점하지 못 하도록 하여 문제를 해결할 수 있음
- CPU 할당 시간이 정확하게 지켜지지 않을 수 있으나, real time system이 아니기 때문에 크게 문제가 발생하지 않음.
Race Condition 3
- Multiprocessor 환경의 경우 CPU가 2개 이므로 특정 CPU에 대한 interrupt를 disable 한다고 해서 다른 CPU가 데이터를 읽지 못하는 것이 아님.
- 해결책
- 한번에 하나의 CPU만 커널에 접근 가능하도록 함
- 공유 데이터에 접근 했을 때 그 데이터에 대한 lock을 걸어 lock 상태이면 다른 CPU가 접근하지 못 하도록 설계하는 방법
Process Synchronization 문제
- 공유 데이터(shared data)의 동시 접근(concureent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있음
- 일관성 유지를 위해서는 협력 프로세스 간의 실행순서를 정해주는 메커니즘이 필요
*Race Condition: 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황으로 인해 데이터의 최종 연산 결과가 마지막에 그 데이터를 다룬 프로세스에 따라 달라지는 현상
- race conditon 을 막기 위해서는 concurrent process가 동기화되어야 함
Critical Section (임계 영역)
- n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
- 각 프로세스의 code segment에는 '공유데이터를 접근하는' 코드인 critical section이 존재
- 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
- 문제 해결 시도
- 임계영역 앞 뒤 section을 두어 해당 section에 진입하면 다른 프로세스가 진입 불가하도록 하는 방법
- entry section에서 lock을 걸고, exit section에서 lock을 풂
- SW적으로 Race Condtiion을 해결하는 알고리즘 3가지 소개
프로그램적 해결법의 충족 조건
- Critical Section 문제를 해결하기 위해 만족해야할 3가지 조건
- Mutual Exclusion(상호배제): 프로세스 Pi가 Critical Section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
- Progress(진행): 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
- Bounded Waiting(한정대기): 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
Algorithm 1
- 프로세스마다 자신의 turn에 대한 변수를 가짐
- 자신의 턴이 아니라면 while문에서 대기
- 다른 프로세스가 빠져나오면서 turn 값을 변경해주면 while문이 종료되어 critical section 진입
- 문제점: critical section에 접근하는 상대 프로세스의 빈도에 따라 내가 critical section에 들어갈 수 있는 가능성이 달라짐.
- 즉 상대방이 critical section에 진입했다가 나의 turn으로 변수를 바꿔주지 않는 이상 내가 다시 critical section에 들어갈 수 없게 됨.
⇒ Progress 조건에 위배
Algorithm 2
- flag 변수를 통해 critical section에 진입할 것임을 알리고, 상대 프로세스가 진입해있는지 확인함.
- algorithm 1과 달리 상대 프로세스가 turn을 바꿔주지 않아도 상대가 flag를 true로 만들지만 않았다면 critical section에 진입 가능
- 그러나 프로세스 1이 flag를 true로 만들고 critical section에 진입하기 전에 CPU를 빼앗긴 후에 프로세스 2가 while문의 조건을 확인하면 critical section에 들어간 프로세스가 아무도 없지만 진입하지 못하는 상황이 발생 ⇒ Progress 조건에 위배
Algorithm 3 ( Peterson's Algorithm )
- SW적 해결법의 3가지 조건을 모두 만족하는 알고리즘
- Flag 변수와 turn 변수를 모두 활용
- 경우의 수를 모두 따져보면 3가지 조건에 위배되는 상황이 발생하지 않음
- 그러나 Busy Waiting의 문제가 있음
- 상대 프로세스가 cpu burst time이 길고 critical section을 빠져나오는 시간이 길다면, 자신이 CPU를 할당받은 시간 동안 다른 작업을 하지 못 하고 while문만 수행하다가 끝나는 상황 발생
Synchronization Hardware
- 지금까지 SW적으로 문제를 해결하는 알고리즘은 꽤 복잡함
- 그 이유는 고급언어로 기술된 코드는 instruction 단위를 통제할 수 없기 때문임
- 만약 lock을 체크하고, lock이 안 걸려 있으면 lock을 거는 두 행위가 atomic 한 것이 보장된다면 복잡한 SW 코드를 작성하지 않아도 됨
- 이를 보장해주는 기계어를 통해 HW적 동기화 방법을 사용할 수 있음
- 즉 상대방의 진입여부를 확인하고 lock을 거는 행위가 atomic 하다면 lock을 걸고 나서 CPU를 빼앗겨서 두 프로세스 모두 critical section에 진입하지 못 하는 상황이 발생할 수 없음
- while문에서 상대방의 진입 여부를 test하고 lock을 걸어줌, 만약 lock이 false면 true로 만들고 진입, lock이 true면 똑같이 true를 덮어 씌우고 진입 x(while문 조건 충족), 이렇게 test & modify 가 동시에 일어남이 보장되고, 상대의 lock 여부 확인 후 바로 while문을 빠져나올 수 있다면 간단하게 동기화가 가능
Hello World