프로세스 동기화 & 상호배제
프로세스 동기화(Process Synchronization)
동기화의 개념
다중 프로그래밍 시스템
- 여러 개의 프로세스들이 존재
- 프로세스들은 서로 독립적으로 동작
- 공유 자원 또는 데이터가 있을 때, 문제 발생 가능함
동기화: 프로세스들이 서로 동작을 맞추고, 정보를 공유하는 것
- 비동기적(Asynchronous) : 프로세스들이 서로에 대해 모름
- 병행적(Concurrent) : 여러 개의 프로세스들이 동시에 시스템에 존재
병행 수행중인 비동기적 프로세스들이 공유 자원에 동시에 접근할 때, 문제가 발생할 수 있음
Terminologies
- Shared data(공유 데이터) 0r Critical data : 여러 프로세스들이 공유하고 있는 데이터
- Critical section(임계 영역): 공유 데이터를 접근하는 코드 영역(code segment)
- Mutual exclusion(상호배제): 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것
위와 같이 두 프로세스가 sdata(shared data)에 1을 더하는 연산을 실행한다고 했을 때, 그 결과가 항상 2가 될까?
위 명령어를 compiler가 기계어로 번역하며, 그 결과는 다음과 같다.
기계어 명령(machine instruction)의 특성
- Atomicity(원자성), Indivisible(분리 불가능)
- 한 기계어 명령의 실행 도중에 인터럽트 받지 않음
일반적인 기계어 표현은 위와 같으며, s = s+1 이 위의 3가지 단계로 번역된다.
- cpu 내의 레지스터가 메모리의 데이터를 가져온다.
- 연산을 수행한다.
- 결과값을 메모리에 다시 저장한다.
이 때, 이 값이 항상 2가 되지 않을 수 있다.
1,2,3번 각각의 명령은 인터럽트를 받지 않는다. 그러나 1->2, 2->3 번으로 넘어가는 과정에서는 preemption 이 발생할 수 있다.
따라서 명령의 수행 과정에 따라 결과가 달라질 수 있으며, 이를 Race condition 이라고 한다. 이를 방지하는 것이 상호배제(Mutual Exclusion) 라고 한다.
하나의 프로세스가 CS(Critical Section) 에 진입해 있는 경우, 다른 프로세스의 접근을 막아주는 것을 뜻한다.
Mutual Exclusion Methods
상호배제를 구현하는 기본연산(primitives)
- enterCS() primitive
- CS 진입 전 검사
- 다른 프로세스가 CS 안에 있는지 검사
- exitCS() primitive
- cs를 벗어날 때의 후처리 과정
- cs을 벗어남을 시스템이 알림
Requirements for ME primitives
- Mutual exclusion(상호배제)
- Progress(진행)
- CS 안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해하면 안됨(비어 있는 CS에 접근하는 것을 방해하면 안됨)
- Bounded waiting(한정대기)
- 프로세스의 CS 진입은 유한시간 내에 허용되어야 함
구현 예시
version1
turn이라는 변수를 통해서 자신의 turn일 때, CS에 진입하고 수행이 완료되면 다른 프로세스로 turn을 넘김
문제점
- Progress 위반(어느 한쪽에서 process가 terminated되었을 때, 상대쪽으로 turn을 넘기지 못하여 CS진입이 불가)
- 하나의 Process가 연속으로 CS진입 불가
version2
flag 사용하여 상대방의 flag을 확인함. 진입 전에 깃발이 내려가 있으면 내 깃발을 올린 뒤에 진입하고, 수행완료 후에 깃발을 내림
문제점: 깃발을 확인하고 진입하기 직전에 Preemption 발생할 경우, Mutual exclusion 조건 위배
version3
위의 문제를 해결하기 위해서 이번에는 깃발을 먼저 올리고 상대방의 깃발을 확인함
문제점 : 깃발을 올리고 나서 preemption이 발생한 경우, Progress/Bounded watiting 조건 위배
이러한 문제점들을 해결하기 위해 나온 후속 솔루션들은 다음과 같다.
SW solutions
trun + flag
서로에게 양보
SW Solution의 문제점
- 속도가 느림
- 구현이 복잡함
- ME primitive 실행 중 preemption 될 수 있음
- 공유 데이터 수정 중은 interrupt를 억제하여 해결 가능(overhead 발생) - Busy waiting
- Inefficient
HW solution
Synchronization Hardware
TestAndSet(TAS) instruction
- Test와 Set을 한 번에 수행하는 기계어
- Machine instruction
- Atomicity, Indivisible
- 실행 중 interrupt를 받지 않음(preemption 되지 않음) - Busy waiting
taret의 값을 temp에 저장하여 반환하고, target을 True로 만들어준다.
단 3개 이상의 프로세스의 경우, Bounded waiting 조건 위배된다.
1번 프로세스가 작업을 하는 도중에 2,3번 프로세스가 들어온다면, 1번이 나갔을 때, 2번 또는 3번은 CS에 들어갈 수 없다. 그 와중에 4번 프로세스가 들어오면 마찬가지로 남은 프로세스 중 하나의 프로세스는 들어갈 수 없게 된다.
N개의 프로세스에 대한 ME를 해결하는 방법은 위와 같다. 추가된 사항은 waiting 이라는 변수다. 대기 중인 프로세스를 발견하여 waiting을 false로 바꿔주어 CS에 진입할 수 있도록 한다.
HW Solution 장단점
장점: 구현이 간단하다.
단점: Busy Waiting 이 여전히 존재한다.
이를 해결하기 위한 방법 - Semaphore(OS의 개입)
