Day17 - jeremy0405/Codesquad_CS GitHub Wiki

프로세스 동기화

Race Condition

메모리를 공유하는 연산자(CPU or Process)가 많을 경우 Race Condition이라고 한다. 이 경우 메모리를 공유하는 코드 영역(Critical-Section)에서 데이터 동기화를 통해 데이터가 망가지는 것을 방지해야 한다.

OS에서 Race Condition이 발생하는 경우

1. kernel 수행 중 인터럽트 발생 시
2. Process가 system call을 해서 kernel mode로 수행 중인데 context switch가 일어난 경우
3. Multiprocessor에서 shared memory 내의 kernel data

위의 1, 2 상황에서의 Race condition 해결법

→ 인터럽트가 들어 와도 중요작업(커널작업) 끝낸 후에 인터럽트를 처리함

3 상황에서의 Race condition 해결법

1. 한번에 하나의 CPU만 커널에 들어갈 수 있도록 함 → 엄청 비효율적이라서 사용하지 않음
2. 하나의 CPU가 데이터에 접근한 상태라면 lock을 걸어서 다른 CPU를 기다리도록 함

Critical section 문제를 풀기 위해서 만족해야 할 조건 3가지

1. Mutual Exclusion (상호 배제)
   • 프로세스 하나가 critical section에 들어가면 다른 프로세스가 들어가지 못하게 하는 것
2. Progress
   • 아무도 critical section에 들어가 있지 않다면 들어가게 프로세스가 하나만 들어가게 허락해주는 것
3. Bounded Waiting
   • 기다리는 시간이 유한해야 함 (언젠가 critical section에 들어가게 해줘야 함)
   • critical section에 들어가고자 하는 프로세스가 3개일 때 1 2 번 프로세스만 계속 왓다갓다하고 3번이 못들어가는 Starvation 현상이 발생함

Critical-Section을 해결하는 알고리즘

1. int turn을 가지는 방법 → 앞에 들어갔던 프로세스가 turn을 다음 프로세스 차례롤 바꾸고 나가주면 자신의 turn이 되면 들어가능 방식으로 Critical-Section에 하나의 프로세스만 들어가도록 함

   → turn을 내 값으로 변경해줘야 내가 들어갈 수 있음 → 아무도 critical section에 들어가지 않았다면 turn을 누가 내 값으로 변경해줌?? → Progress 조건을 만족하지 못함

2. boolean flag[]를 가지는 방법

   → 내가 들어가고 싶으면 자신의 flag배열을 ture로 만든 이후 flag배열을 모두 다 본 후에 자신을 제외한 것들이 모두 false일때만 critical section에 들어감.

   → 만약 다른애도 true를 들고 동시에 나도 true를 들게 된다면 Progress조건을 만족하지 못함

3. 1, 2 방법을 짬뽕 int turn과 boolean flag[]를 모두 가지고 있음.

   상대방이 깃발을 들고 있고 상대방 차례이면 기다림

   상대방이 깃발을 들고 있지만 내 차례이면 내가 들어감

   → Busy Waiting(spin lock) 문제 내 차례를 확인할려고 while(1)의 무한 루프를 돌면서 계속 나의 값을 체크해야 한다. → CPU와 메모리를 계속 낭비하는 것

위의 알고리즘을 해결하는 방법은 프로그래밍 코드로써 Software적으로 해결하려는 것이다.

Critical section 문제를 Hardware로 풀면 굉장히 쉽게 풀 수 있다.

Hardware적으로 Critical section을 푸는 방법

• Test & Set
  • 데이터를 읽는 작업과 쓰는 작업을 동시에 수행하도록 하드웨어가 지원한다. 따라서 누군가 읽고 있을 때 다른 프로세스가 데이터를 쓰는 작업을 해서 데이터의 손실을 유발할 수 있는 가능성을 원천 차단한다.
  • 들어가기 전에 값을 읽을 때는 무조건 읽고 1로 세팅하고 처리 다하고 나갈 때 값을 0으로 바꿔줌

위에서 Software, Hardware적으로 Critical Section을 안전하게 다루는 방법을 공부해보았는데 프로그래머가 항상 Critical Section을 다루기 위해서 위와 같이 코드를 작성하는 것은 굉장히 힘든 일이다. 따라서 프로그래머들을 위해서 Semaphore 라는 추상자료형이나 Monitor라는 것을 통해서 Critical Section을 보다 편리하게 관리할 수 있다.

Semaphore

Semaphore → 추상자료형 = 오브젝트 + 오퍼레이션

프로그래머가 추상적으로 Semaphore을 통해서 단순히 코딩을 할 수 있게 된다.

Semaphore :

• Object : Integer variable (자원의 개수) → 할당 할 수 있는 자원의 개수
  • 만약 Object의 Integer variable이 3이면 한d번에 3개의 프로세스가 데이터에 접근 가능
  • Object가 0 또는 1만 가질 수 있는 경우 : Binary Semaphore (=mutex) type
  • Object가 0 이상의 임의의 정수 값 : Counting Semaphore type
• operation : P 연산과 V연산 (atomic 연산 2개)으로 구성되어 있음
  • P 연산 : 데이터 lock (자원 획득 후 lock이므로 자원을 획득하는 과정)
  • V 연산 : 데이터 unlock (자원 반납 과정 + 혹시 대기자 있다면 깨워줌)

Semaphores를 구현하는 데에 있어서 2가지 방식이 있음

1. busy-waiting(=spin lock) 방식 → CPU를 잡고 while문을 계속 돌면서 기다림
2. Block/Wake up(=sleep lock) 방식 → 리스트에 재운 상태(CPU를 반납)로 담고 순서오면 깨워줌

2가지 방법 중 무엇이 더 좋을까?

당연히 Block/Wake up 방식이 훨씬 효율적 (blocked로 만들어서 CPU를 계속 들고 있지 않기 때문)

하지만 프로세스의 길이가 너무 짧은 경우에는 blocked, wake 하는 context switch 때문에 비효율적일 때도 있지만 보통은 항상 훨씬 효율적임

Semaphore에서 발생할 수 있는 문제점

1. Deadlock 현상

• 하나의 프로세스가 A데이터를 복사해서 B데이터에 붙여넣기 하려고 할 때 두 부분 모두 다 cpu를 획득해서 일을 해야 하는데 process1이 A에 접근하고 B에서 대기중이고 process2가 B에 접근하고 A에 접근하고 있으면 평생 무한 대기 상태에 빠짐.

  → 자원읠 획득하는 순서를 맞춰주면 Deadlock 현상을 해결할 수 있음

  → A데이터에 무조건 먼저 접근한 이후에 B를 접근하도록

1. Starvation 현상 (Deadlock도 Starvation의 일종)

• 특정 프로세스들만 자원을 공유하는 경우 다른 프로세스를 깨우지 않고 자기들끼리만 들어갔다가 깨우고 반복하는 경우를 말함.

Semaphore 자체의 문제점

• 코딩이 어려움
• 작성한 코드의 정확성 입증을 하기가 힘듬
• 한번의 프로그래머의 실수가 시스템에 치명적임

→ Monitor를 통해서 해결할 수 있음

Monitor

공유데이터를 접근하기 위해서는 Monitor의 내부의 프로시저를 통해서만 공유데이터를 접근하도록 하는 것

모니터가 원천적으로 모니터 내부에 있는 프로시저는 동시에 실행되지 않도록 함

→ 프로그래머가 직접 락을 걸 필요가 없어짐

→ 굉장한 장점!! → 보통 프로그래머가 락을 걸고 푸는 과정에서 실수가 많은데 이런 실수를 없앨 수 있음

자원의 개수는 Monitor도 알아야 하기 때문에

variable을 통해서 자원의 개수를 저장해놓음.

condition variable은 현재 signal(), wait()에 쓰일 상태만을 가지고 있음

buffer[N] → 자원의 개수

condition full, empty; → 컨디션을 나타내는 변수, 값을 가지지 않고 signal(), wait()에 쓰일 상태만을 가지고 있음.