반효경 운영체제 - 5. Process Synchronization

반효경 교수님의 운영체제 강의를 듣고 내용을 정리한 글입니다.

Process Synchronization이란?

데이터의 접근 - 연산 - 결과 저장 과정에 일어나는 순서에 따른 발생할 수 있는 문제, 다시 말하면 Storage box를 여러 개의 execution box가 공유하기 때문에 발생할 수 있는 문제라고 할 수 있다.

• Race Condition
  • 의미 : 여러 주체가 동시에 하나의 객체에 접근하려고 할 때 원치않는 결과를 얻을 수 있다.
  • 발생 : CPU - Memory 관계, 컴퓨터 내부 - 보조저장장치(디스크), 프로세스 - 프로세스의 주소 공간 등
    • 일반적으로 프로세스는 자신의 주소 공간을 가지므로 문제가 되지 않지만, 시스템콜을 통해 공유 메모리를 사용하는 프로세스의 경우나, 커널 내부 데이터를 접근하는 루틴들 간에 발생 가능하다.
    • ex) 커널모드 수행 중 인터럽트로 커널모드 다른 루틴 수행 시

OS에서 Race Condition은 언제 발생하는가?

• Interrupt Handler와 커널의 race
  • 수행하는 것이 둘다 커널 코드이므로 kernel address space 공유
  • Interrupt Handler가 커널 내부의 변수를 조작하는 경우(아래 예시)
  • 최종적으로 Kernel이 Count에 Store하므로 Interrupt의 조작은 반영이 안됨
  • 해결 : 인터럽트를 처리하지 않고 조작이 끝난 후에 인터럽트를 처리

• 시스템콜을 통해 커널 모드에서 수행 중에 context switch가 발생한 경우
  • 해결 : 커널 모드에서 수행 중일때는 CPU를 preempt하지 않음, 커널 모드에서 사용자 모드로 돌아갈 때 preempt

커널 모드에서 Context Switch 발생

• Multi Processor
  • 어떤 CPU가 마지막으로 변수를 store했는가?
  • 방법 1) 데이터를 접근할 때 데이터에 대한 lock(접근) / unlock(저장)을 하는 방법
  • 방법 2) 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법

Process Synchronization 문제

• 공유 데이터의 동시 접근은 데이터의 불일치 문제를 일으킬 수 있다.
• 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요
• Race Condition
  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
• Race Condition을 막기 위해 동시 접근 프로세스는 동기화가 되어야한다.

The Critical-Section Problem

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

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

Mutex(상호 배제)

한 프로세스가 Critical Section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.

Progress(진행)

아무도 Critical Section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.

Bounded Waiting(유한 대기)

프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.

Critical Section 문제 해결 - Synchronization 알고리즘

Turn 변수 이용하기

문제 해결을 위한 아주 단순화한 동기화 알고리즘을 생각해보자. 아래 강의 노트처럼 간단한 Turn 변수를 이용하는 방법이 있겠다. Critical Section에 접근하려는 프로세스는 자신의 turn일 때만 들어갈 수 있고, turn을 다른 프로세스에게 넘긴다.

• Mutex를 만족
• Progress 불만족

process에 들어가려는 빈도가 다를 수 있기 때문에, progress 조건을 만족시키지 않는다.

 

Flag를 이용하는 방법

크리티컬 섹션에 들어가고자 할 때, 플래그를 true로 바꾸고 상대방의 플래그가 있는지를 확인하고 기다린다. 둘 다 2행까지 수행 후 서로 양보하는 상황 발생 가능하다.

• Mutex를 만족
• Progress 불만족
• Bounded Waiting 불만족

피터슨의 알고리즘 - 턴과 플래그를 모두 사용

모든 조건을 만족하는 알고리즘이다. 상대방의 차례이고, 상대방이 임계 영역에 들어가려는 의사가 있는 경우에만 상대를 기다린다. 임계영역에 들어가고 싶다는 의사를 flag로 표현하고, 상대방에게 턴을 먼저 양보한다. 이 때, 상대방도 flag로 의사가 표현되어있고 차례에 해당할 때만 기다린다.

 

• Busy Waiting(Spin Lock) - 계속 CPU와 메모리를 사용하면서 기다린다.
  • 즉, 상대방이 CPU를 사용해야 Waiting이 끝나는데도 while 조건을 검사하면서 CPU를 낭비하는 상황

 

 

Synchronization Hardware

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

• read & assign을 하나의 instruction으로 지원하는 경우

 

Semaphores

Semaphore는 앞의 방식들을 추상화시킨 추상 자료형이다. Atomic 연산으로 접근 가능하다.

• Integer variable(자원의 개수)
• 아래 두가지 atomic 연산으로만 접근 가능
  • atomic 연산에 대한 전제
• P(S) : 공유 데이터를 획득하는 과정

• V(S) : 공유 데이터를 반납하는 과정

 

Semaphore의 구현 방법

1. Busy Waiting (=spin lock) : while문처럼 CPU를 사용하면서 대기하는 것
2. Block & Wakeup (=sleep lock) : 프로세스를 sleep시키고 인터럽트로 자고있는 프로세스를 깨우는 방식

 

Busy-wait vs block/wakeup

• 일반적으로 block/wakeup이 효율적이다.
• Block/wakeup도 overhead가 발생한다.
• Critical section 길이가 짧은 경우 Black/wakeup 오버 헤드가 더 커질 수 있다.

 

Block / Wakeup의 구현 방법

세마포어를 값과 process wait queue의 구조체로 정의, 세마포어의 큐를 PCB의 큐로 구현하는 방식이다. 자원을 반납할 때, 기다리는 프로세스를 깨워줘야한다.

 

• S가 자원의 개수의 의미와는 다르다.
• S가 음수면 다른 프로세스가 자원을 기다리고 있다는 의미.
• 양수는 여분이 있기 때문에 깨울 필요가 없다.

Two Types of Semaphores

• Counting semaphore는 도메인이 0 이상인 임의 정수 값으로, 주로 resource counting에 사용한다.
• Binary semaphore(=mutex)는 0 또는 1 값만 가질 수 있는 semaphore로, 주로 mutual exclusion(on/off)에 사용한다.

Deadlock and Starvation

• Deadlock : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
  • 자원을 획득하는 순서를 정해준다면 해결 가능, Q를 얻기위해서는 S를 얻어야하도록 만듦(Deadlock의 해결 방법 중 하나이다.)
• Starvation : Indefinite blocking - 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

데드락은 보통 아래 3가지의 유형으로 분류한다.

Bounded-Buffer Problem(Producer-Consumer)

Producer : buffer에 데이터를 집어넣는 역할

Consumer : buffer의 데이터를 사용하는 역할

Synchronization 변수들

1. mutex → binary semaphore 필요
2. buffer의 유한함 → 생산/소비의 불균형 발생 시 buffer 부족 발생 가능 → 남은 full/empty buffer 수를 표시하는 empty와 full이라는 integer 타입의 semaphore를 사용하여 나타낸다.

Readers-Writers Problem

한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근하면 안된다. 그러나, read는 동시에 여럿이 해도 상관이 없다.

그러므로 Writer가 db에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 reader들을 다 DB에 접근하게 해준다. Writer가 접근할 때는 reader가 없어야하므로, Writer는 대기 중인 reader가 없을 때 DB 접근이 허용된다. 일단 Writer가 DB에 접근 중이면 Reader는 접근 금지된다. Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.

공유변수

• mutex : readcount도 공유변수이므로 공유 변수를 조작 시 mutual exclusion 보장을 위해 lock이 필요
• db : write와 reader를 분리하기 위한 lock 변수
• readcount : 현재 DB에 접근 중인 Reader의 수

문제점 : reader는 일단 reader가 들어오면 계속 접근할 수 있기 때문에 계속 reader가 들어온다면 writer가 starvation 될 수 있다.

Dining-Philosophers Problem

•  문제점
  • Deadlock 가능성이 있다.
  • 모든 철학자가 동시에 왼쪽 젓가락을 집은 경우
  • Starvation
    • 양쪽 철학자가 번갈아가면서 젓가락을 집는 경우
• 해결 방법
  • 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
  • 젓가락을 두 개 모두 집을 수 있을 때에만 집을 수 있게 한다.
  • 비대칭
    • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록함

Monitor

• Semaphore의 문제점
  • 코딩하기 힘들다
  • 정확성의 입증이 어렵다
  • 자발적 협력이 필요하다
  • 한번의 실수가 모든 시스템에 치명적 영향

Monitor는 Semaphore의 위 문제점을 개선하여, 동시 수행 중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct이다. 공유 데이터는 모니터에 정의된 프로시저를 통해서만 접근 가능하며, lock을 걸 필요가 없다. 자원의 개수를 세주는 세마포어처럼 condition variable이 존재한다.

 

Condition variable은 wait와 signal 연산에 의해서만 접근 가능하다. 조건이 맞지 않아 프로세스를 잠들게 할 때 사용한다.

• wait - condition variable에 가서 줄서게 됨
• signal - condition variable에서 잠든 프로세스를 깨운다.
  
  • •