[운영체제] 프로세스 동기화

데이터의 접근

• 데이터를 읽어와서 연산된 데이터를 다시 위치한 데이터에 저장
  • (1) CPU(연산) Memory(스토리지)
  • (2) 컴퓨터 내부(연산) 디스크(스토리지)
  • (3) 프로세스(연산) 프로세스의 주소 공간(스토리지)

데이터를 읽기만 한다면 동기화 문제가 중요하지 않지만 연산을 하여 다시 저장하는 경우에는 동기화 문제가 중요하게 됩니다.(다르게 읽어 연산을 하여 다르게 저장할 수도 있으니)

 

 

Race Condition

• 공통적인 데이터를 동시에 사용하려는 경우 한 가지의 연산만 처리될 때 경쟁상태라고 말합니다.
• 하나의 주체가 읽어갔는데 그동안 다른 주체가 읽어가서 연산을 실행하여 생기는 문제라고 이해하시면 됩니다.
• 위의 경우에서 예시를 들면 ++ -- 를하면 그대로가 되어야 하는데 나중에 ++를 하는 도중에 --를실행시켜 --만 된 경우입니다.

 

 

OS에서의 Race Condition

• 운영체제에서의 커널과 관련된 문제
• 프로세스는 일반적으로는 자기 주소 공간만 접근하기 때문에 Race Condition은 발생하지 않는다.
• 프로세스들이 직접 실행할 수 없는 부분 운영체제에 요청하는 부분은 시스템 콜을 통해 실행합니다.
• 커널의 코드가 그 프로세스 대신 실행(커널의 데이터를 접근), 이러한 상황에서 CPU를 뺏겨서 또 다른 프로세스가 시스템 콜을 한다면 Race Condition 발생하게 된다.
• 운영체제의 커널 데이터가 공유 데이터라 문제가 발생합니다.

대표적 OS Race Condition

1.Kernel 수행 중 인터럽트 발생 시

위의 사진에서 Race Condition은 kernel에서 실행을 할때 Count를 로드를 시키고 증가시키고 저장하는 과정을 진행하게 되는데 로드를 시키고 증가하려는 와중에 Interrupt handler가 발생하여 Count --를 하게 됩니다. 

그리고 그 이후에 Inc를하여 Store를 하는 과정을 진행하게 되는데 보통 저희가 원하는 값은 그대로(+1 -1 하여서) 여야 하는데 위 사진의 경우 Count를 로드하고 Inc 과정 중에 진행하였기 때문에 그대로 플러스만 하게 된 값만 반영하게 됩니다.(근본적으로는 데이터를 공유하여서 발생하는 문제)

 

해결책은 위의 사진의 경우 Count++를 먼저 실행 후 작업이 끝난 이후 인터럽트를 실행시켜줍니다.

작업이 끝날 때까지는 인터럽을 발생하지 않게 하는 것.!(순서만 정해주면 됩니다.)

 

2. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우

해결책: 커널 모드에서 수행 중일 때는 CPU를 선점하지 않고 커널 모드에서 사용자 모드로 돌아갈 때 선점합니다.

 

3. Multiprocessor에서 shared memory내의 kernel data

 

해결책은: 커널 내부에 있는 공유 데이터에 대한 lock / unlock을 하여 관리

​ 한 번에 하나의 CPU만 커널에 들어가게 하는 방법

Process Synchronization

문제공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있습니다.

일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정리해주는 메커니즘이 필요.

The Critical-Section Problem(임계 구역) -> 공유데이터를 접근하는 코드

n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재합니다.

공유 데이터에 접근하는 코드를 Critical-Section입니다.

Problem: 하나의 프로세스가 Critical-Section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.(사용 중이면 기다려야 한다)

 

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

• Mutual Exclusion(상호배제)
  • 프로세스 Pi가 Critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
  • 이건 공유 데이터에 들어갔으면 다른 프로세스는 못 들어오게 해야한다는 의미
• Progress(진행)
  • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
  • 둘다 안들어가 있다면 들어가게 해줘야한다는 의미
• Bounded Waiting(유한 대기)
  • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야한다.
  • 특정 프로세스 입장에서 지나치게 오랫동안 기다리게 하면 안된다는 의미
  • 만약 프로세스가 3명이 있을 때 두개만 들어가고 한개만 계속 기다리게 하면 안된다는 의미

 

 

프로그램적 해결법을 위한 알고리즘

Algorithm1

turn의 변수는 누구의 차례인가를 의미하는 변수입니다.

여기서는 자기의 턴이 아니라면 계속하여 대기(while문)를 하다 자신의 턴이 되면 그때 공유데이터에 접근할 수 있게 합니다.

그 이후 자신의 턴을 사용하여 다른 프로세스의 턴으로 바꿔주는 코드입니다.

프로세스 별로 turn에 대한 변수를 다르게 가지고 있는다고 생각하시면 될 것 같습니다.!

위의 코드는 상호 배제는 만족하지만 Progress만족을 하지 못합니다.(아무도 없는데 들어가는 코드가 없습니다.)

코드를 보시면 반드시 교대로 들어가게끔 구현하였습니다. 

만약 P0은 빈번하게 들어가고 싶지만 P1은 가끔 실행하다 보면 P0은 들어가고 싶어도 못 들어가게 되는 경우가 존재합니다. 

 

Algorithm 2

위의 코드는 Flag를 추가를 하여 구현하는 것입니다.

Flag는 다른 프로세스가 들어가고 싶어 하는지 확인하기 위한 배열입니다.

그리하여 맨 처음에는 다 들어갈 의지가 없다고 표시하여 시작하고 코드를 시작하면서 자신이 들어갈 의지가 있다고 시작합니다.

 

위의 알고리즘도 문제가 존재합니다.

Process i가 Flag true로 바꾼 순간  Process j가 CPU를 빼앗아 버린다면 둘 다 critical section에 들어가지는 않았는데 계속 기다리기만 하는 현상이 발생하게 됩니다.

 

Algorithm 3(Peterson's Algorithm)

이번 알고리즘은 턴과 flag를 활용한 알고리즘입니다.

 

Semaphores(추상적 정의)

• Integer variable(변숫값이 자원의 개수)
• 아래의 두 가지 atomic 연산(실행되거나 안되거나 중간에 끊기는 게 없음)에 의해서 접근 가능

P->공유 데이터를 획득하는 과정

V->공유 데이터를 다 사용하고 반납하는 과정.

Critical Section of n Processes(세마포어 적용)

• 추상 자료 형태로 제공해주고 세마포어로 정의

Block / Wakeup Implementation

1. 세마포어를 획득할 수없다면 block를 시키고

2. 누군가가 세마포어를 쓰고 반납을 하면 깨워서 wakeup에 넣어 Queue로 대기하게끔 한다.

여기서 S.value는 상황을 나타냅니다.

음수-> 누군가가 자원을 다 사용해서 여분이 없다.

양수-> 자원이 여분이 있기 때문에 기다리지 않고 쓸 수 있다.

Two Types of Semaphores

• Counting semaphore
  • 도메인이 0 이상인 임의의 정수 값
• Binary semaphore(boolean => mutext)
  • 0 또는 1 값만 가질 수 있는 semaphore
  • 주로 lock/unlock에 사용

Deadlock and Starvation

Deadlock:둘 이상의 프로세스가 서로 상대방의 의해 충족될 수 있는 event를 무한히 기다리는 현상

P0은 P(S)를 가지고 P1은 P(Q)를 가진 이후 P0은 P(Q)를 가져야 하고 P1은 P(S)를 가져야 하는데 서로 자원을 가진 이후 놓지 않고 계속 기다리는 상황.(상대방이 가진 것을 놓지 않고 서로 영원히 기다리는 상황)

 

 

동기화 관련 3가지 문제

 

1.Bounded-Buffer Problem

공유되는 메모리에 대한 crital section에 대한 처리를 확실히 진행을 해주어야 합니다.

생산자와 소비자들이 공유된 메모리에 접근할 때에 락을 걸고 풀고 하는 과정을 통해 자원을 관리해야 합니다.

그리고 추상적 정의인 세마포어를 통해 관리하게 됩니다.

맨 처음 가정은 다 빈 data로 시작하여 full은 0이고 empty은 n으로 시작합니다. 그리고 프로세스는 1개를 가지고 처리하기위해기 위해 mutex를 활용합니다.

생산자 입장에서 코드의 실행은

처음 x라는 내용을 만들고, 

빈 버퍼가 있는지 확인을 하고, 있다면  P(mutex)를 통해 Lock 하는 과정을 진행하고 buffer에 x라는 내용을 추가하는 과정을 진행하고 Lock을 푸는 V(mutex)를 진행 후에 소비자들이 찾을 수 있게 V(full)이라는 과정을 진행합니다.

소비자의 입장은 생산자와 정반대로 진행합니다.

 

 

2.Reader-Writers Problem(읽는 프로세스와 쓰는 프로세스가 있다)

• 한 프로세스가 DB에 write 중일 때 다른 process가 접근하면 안 됨.
• 누군가는 쓸 때는 lock을 걸지만 read는 lock을 안 걸고 동시에 여럿이 읽어도 된다.
• shareddata ->DB 자체

읽을 때도 쓰는 걸 방지하기 위해 락을 걸지만 읽는 것은 허용해야 합니다.

그래서 readcount에 대한 락을 걸고 실행합니다. 그리고 마지막으로 읽는 사람이라면 이제 쓰기를 허락하기 위해 읽는 것에 대한 락을 풀어줍니다.

writer가 계속 기다리는 현상이 발생 가능성이 있습니다. 

3. Dining-Philosophers Problem(식사하는 철학자)

철학자들이 밥을 먹거나 생각을 하거나 둘 중의 하나입니다.

여기서 공유자원은 젓가락이 공유자원입니다.

왼쪽 젓가락과 오른쪽 젓가락을 잡으면 밥을 먹고 다 먹으면 왼쪽 젓가락과 오른쪽 젓가락을 놓고 밥을 먹습니다.

하지만 이 코드는

• Deadlock 가능성이 있다. (동시에 배가 고파 왼쪽 젓가락을 들고 있을 때 계속 다 기다리기만 할 수도 있다.)
• 모든 철학자가 동시게 배가 고파져 왼쪽 젓가락을 집어버린 경우

해결방안

• 4명의 철학자만이 테이블에 동시에 앉도록 한다
• 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
• 비대칭
  • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록

 

Semaphore의 문제점

• 한 번의 실수가 모든 시스템에 치명적 영향

세마포어를 잘 지키면 잘 동작이 되지만 프로그래머가 실수를 하여 실수가 나온다면 검증이 힘듭니다.

이러한 점을 보완하기 위해 Monitor가 존재합니다.

 

Monitor

개념: 한 번에 하나의 프로세스만 모니터에서 활동하도록 보장한다.

동작: 어떤 공유 데이터에 대해 모니터를 지정해 놓으면, 프로세스는 그 데이터를 접근하기 위해 모니터에 들어가야만 한다. 즉 , 모니터 내부에 들어간 프로세스에게만 공유 데이터를 접근할 수 있는 기능을 제공하는 것이다. 또한 프로세스가 모니터에 들어가고자 할 때 다른 프로세스가 모니터 내부에 있다면 입장 큐에서 기다려야 한다.

모니터 내부에 공유 변수에 대한 선언을 해놓고 공유 데이터에 접근하기 위한 것은 모니터 내부 함수를 통해 접근합니다.

락을할 필요가 없음

• 모니터 내에서 한 번에 하나의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없음.
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 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된 프로세스가 없으면 아무 일도 일어나지 않는다.(세마포어랑 비교)

모니터 안에서 하나의 프로세스만 활성화된다.라는 점이 중요 

모니터 안에서 공유자원에 대한 개수가 없다.

 

모니터 안에서 내부의 프로그램이 active 한 프로그램이 0 일 때만 들어갈 수 있다.

 

 

모니터를 활용한 Bounded-Bufferd Problem

본래는 Buffered에 대한 Lock을 진행해주어야 했는데 모니터에서는 공유 버퍼에 대한 Lock을 따로 진행하지 않습니다.(동시 접근은 모니터가 막아줘서)

 

생산자 입장에서는  만약 빈 버퍼가 없다면 empty라는 줄에서 기다리게 합니다.

만약 빈버퍼가 있다면 full.signal은 만약 내용이 있는 버퍼에서 소비자가 기다리고 있다면 깨워줘라