Concurrency Control (병행 제어)

데이터의 접근

1. 저장 공간에 데이터가 있다
2. 연산할 데이터를 실행 공간으로 가져온다
3. 실행 공간에서 연산한다
4. 연산 결과를 저장 공간에 반영한다

• 실행 공간 : CPU나 프로세스, 컴퓨터 내부 등
• 저장 공간 : 메모리, 해당 프로세스의 주소 공간, 디스크

Race Condition (경쟁상태)

두 개 이상의 스레드나 프로세스가 공유 자원에 동시에 접근하려고 할 때, 예상치 못한 결과가 발생하는 현상을 말한다

멀티쓰레드 또는 멀티 프로세스 환경에서 여러 개의 스레드나 프로세스가 동시에 공유 자원(메모리, 파일, 데이터베이스 등)에 접근하면서 데이터를 수정하려고 할 때 발생한다.

이를 해결하기 위해 동기화 기법(락, 세마포어, 뮤텍스 등)을 사용하여 공유 자원에 대한 접근을 조절하거나, 스레드나 프로세스간의 통신을 통해 실행 순서나 시점을 조절하여 레이스 컨디션을 방지할 수 있다

OS에서 Race Condition은 언제 발생할까?

1. 커널 수행 중 인터럽트 발생 시
   → 양쪽 다 커널 코드이므로 커널 주소 공간 공유하기 때문에
2. 프로세스가 시스템 콜을 하여 커널모드로 수행중인데 컨텍스트 스위치가 일어나는 경우
   → 현재 프로세스의 커널 코드와 다음 프로세스의 커널 코드가 동일한 커널 주소 공간을 공유하게 된다
3. 멀티프로세서에서 공유 메모리 내의 커널 데이터
   → 각각의 프로세서가 다른 캐시를 가지고 있고, 캐시 일관성 프로토콜에 따라 메모리 갱신이나 동기화가 이루어지기 때문에

임계 영역

여러 개의 프로세스나 스레드가 공유 자원에 접근하는 코드 영역

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

1. 상호 배제(Mutual Exclusion): 한 순간에는 오직 하나의 프로세스나 스레드만이 임계 영역에 들어갈 수 있어야 한다. 다른 프로세스나 스레드들은 대기 상태에 놓이게 된다
2. 진행(Progress): 임계 영역에 들어가려는 프로세스나 스레드가 없는 경우, 임계 영역에 들어가려는 프로세스나 스레드는 바로 들어갈 수 있어야한다.
3. 유한 대기(Bounded Waiting): 임계 영역에 들어가려는 프로세스나 스레드가 있어도, 무한히 기다리는 일이 없어야 한다. 즉, 어떤 프로세스나 스레드도 영원히 임계 영역에 들어가지 못하는 상황이 발생하지 않아야 한다.

세마포어(Semaphores)

두 개의 주요 연산, wait(대기)와 signal(신호)을 이용하여 공유 리소스에 대한 접근을 조절하는 동기화 기법이다. 일반적으로 정수 변수로 구현되며, 초기값을 설정하고 wait() 연산은 세마포어 값을 감소시키고, signal() 연산은 세마포어 값을 증가시킨다. 세마포어 값이 0보다 작아지면 대기 상태로 전환되어 다른 프로세스가 해당 리소스를 사용할 수 없게 된다.

데드락

둘 이상의 프로세스나 스레드가 서로가 가진 리소스를 기다리며, 그 상태가 무한히 지속되는 상황을 의미한다.

예를 들어, 프로세스 A가 프로세스 B가 점유한 리소스를 기다리고 있고, 동시에 프로세스 B도 프로세스 A가 점유한 리소스를 기다리는 경우 데드락이 발생 한다. 이 경우 두 프로세스 모두 상대방이 점유한 리소스를 얻지 못하고 영원히 기다리며, 작업이 진행되지 않게 된다

기아현상

운영체제에서 프로세스나 스레드가 원하는 리소스를 계속해서 얻지못하여 작업이 지연되는 현상을 의미한다. 예를 들어 우선순위가 낮은 프로세스가 항상 우선순위가 높은 프로세스에게 밀려서 리소스를 얻지 못하고 작업이 계속 지연되는 경우 기아 현상이 발생한다.

동기화에 관한 고전적인 문제

Bounded-Buffer Problem(Producer-Consumer Problem)

: 생산자 - 소비자 문제

Buffer in shared memory

• Producer

1. Empty 버퍼가 있나요? (없으면 기다림)
2. 공유데이터에 lock을 건다
3. Empty buffer에 데이터 입력 및 buffer 조작
4. Lock을 푼다
5. Full buffer 하나 증가

• Consumer

1. full 버퍼가 있나요? (없으면 기다림)
2. 공유데이터에 lock을 건다
3. Full buffer에서 데이터 꺼내고 buffer 조작
4. Lock을 푼다
5. empty buffer 하나 증가

• Shared data
  • buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)
• Synchronization variables
  • mutual exclusion → Need binary semaphore (shared data의 mutual exclusion을 위해)
  • resource count → Need integer semaphore (남은 full/empty buffer의 수 표시)

Readers-Writers Problem

• 한 프로세스가 DB에 write 중 일 때 다른 프로세스가 접근하면 안됨

• read는 동시에 여럿이 해도 됨

• solution

  • writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다
  • writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다
  • 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다
  • Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다

• Shared data

  • DB 자체
  • readcount; 현재 DB에 접근 중인 Reader의 수

• Synchronization variables

  • mutex 공유 변수 readcount를 접근하는 코드(critical section)의 nutual exclsion 보장을 위해 사용
  • db Reader와 writer가 공유 DB 자체를 올바르게 접근하는 역할

Dining-Philosophers Problem

• Synchronization variables
  • semaphore chopstick[5] // Initially all values are 1
• 식사를 하려면 젓가락 2쪽이 필요한데 젓가락은 왼쪽, 오른쪽에 각 1개씩만 주어진다
  젓가락을 들고 밥을 먹고 배가 불러지면 젓가락을 내려놓고 다시 생각한다
• 앞의 solution의 문제점
  • 데드락 가능성이 있다
  • 모든 철학자가 동시에 배가 고파서 왼쪽 젓가락을 집어버린 경우
• 해결 방안
  • 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다
  • 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다
  • 비대칭
    • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록

Monitor

세마포어의 단점을 해결한 상호배제 메커니즘
모니터는 운영체제가 처리하는 것이 아니라 프로그래밍 언어 차원에서 지원하는 방법이다.
대표적으로 자바에서 모니터를 지원하는데 자바에서 싱크로나이즈 키워드가 붙으면 이 키워드가 붙은 함수들은 동시에 여러 프로세스에서 실행시킬 수 없다.
즉, 상호배제가 완벽하게 이루어진다. 모니터의 구현만 완벽하다면 프로그래머는 세마포어처럼 wait() 함수나 signal() 함수를 임계영역에 감싸지 않아도 돼서 편리하고 안전하게 코드를 작성할 수 있다

• Semaphore의 문제점
  • 코딩하기 힘들다
  • 정확성의 입증이 어렵다
  • 자발적 협력이 필요하다
  • 한번의 실수가 모든 시스템에 치명적 영향
• 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct

세마포어와의 차이점은 lock을 걸 필요가 없다

• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없음
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용

condition x,y;

• Condition variable은 wait와 signal 연산에 의해서만 접근 가능

x.wait();

x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전 까지 suspend된다

x.signal();

x.signal()은 정확하게 하나의 suspend 된 프로세스를 resume 한다.
Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.