운영체제의 기초 - 10. Process Synchronization 1

Semaphores: Why Process Synchronization?

CPU의 개수가 증가한다고 성능도 비례하여 증가하지 않음

--> Synchronization 문제 때문

핸드폰 락업현상: 스마트폰이 멈춘 상태. 화면도 그래도 있지만 키를 눌러도 진행되지 않는 현상

- 스마트폰에 있는 input키를 누르면 interrupt가 발생

- interrupt 처리가 안됨 -> 입력한 input이 애플리케이션으로 전달이 안됨

- why? synchronization 문제임

- synchronization을 하다가 잘못 꼬이면 Deadlock이 발생함

- Deadlock으로 인해 아무 반응도 할 수 없는 상태에 도달하는 것

Syn(= together) + Chron(= time): Process들이 interaction을 할 때 발생 

왜 프로세스가 interaction 해야하는가?

- 복잡한 시스템을 decomposition하여 구현한 결과가 프로세스이므로 프로세스들이 interaction해야 시스템이 돌아감

- degree of concurrency를 놓이기 위해 여러개로 쪼갬

- 프로세스가 많아지면 리소스 공유가 이뤄지기 때문에

moduler design, concurrency, resource sharing 이 3가지 이유로 process가 interaction해야 함

그런데 이 interaction을 하면 synchronization문제가 발생함

리소스 관점에서 보면 전혀 논리적으로 연관없는 프로세스 와도 인터렉션 한다

- 소켓 통신에서 서로 타겟이 아닌 두 프로세스 사이에도 컴퓨터 간에 ehternet이 연결되어 있어 

   ethernet controller로 인한 interrupt가 발생하기 때문에 인터렉션한다

프로세스들이 interaction하게 되면 나타나는 특징

- 리소스와 컴퓨터 시스템의 상태를 share한다 (물리적 하드웨어 장치뿐만 아니라 글로벌변수 역시 쉐어링 대상이다)

- 인터렉션 발생하면 프로세스 수행이 Non-deterministic(비결정성)해진다

   프로세스 수행을 재생할 수 없고, temporal(시간의 제약을 받는)한 수행결과물은 보장되지 않는다

결국 프로세스 간에 interaction은 resource sharing의 형태로 나타나게 된다

실제로 어떤 나쁜 영향을 미치는지 확인해 보자

여기서 보려고 하는 예는 원자로를 모니터링 하는 시스템

원자로 안에 2개의 온도센서를 모니터링 (값 차이가 범위를 넘어가면 알람)

여기서는 두가지 파트가 있어야 함

- Proc1: 온도센서 값을 읽고 업데이트 (인터럽트 서비스 루틴으로 구현)

- Proc2: 읽어온 값 비교

그러나 제대로 동작하지 않는 프로그램임

Reentrant Code (재진입 가능 코드)

여러 Process들에 의해 동시에 호출되거나, 이전 호출이 완료되기 전에 반복 호출되어도 올바르게 수행되는 코드

프로세스와 인터럽트 서비스 루틴의 concurrency도 유지해야 함

iTemperatures 공유의 문제

- 온도 값 비교(과거 온도값 비교 10=10) 후 현재 온도체크를 위해 [0]배열에 온도값을 11으로 업데이트한 후

   [1]배열 온도값을 11으로 업데이트 할 때 interrupt 발생하여 메인(온도차이 계산) 수행

- [0]은 현재 온도값 11, [1]은 과거 온도값 10

- [1]도 현재 온도값 10 업데이트 했다면 정상이지만 결과 (11 != 10) 되어 알람이 울림

해결: iTemp 읽어오는 구간을 Non-break(=atomic)하게 만든다

하나의 C sentence로 만들었음

잘 동작할까? Nope

하나의 조각인 것처럼 보이지만 어셈블리 코드로 하면 여러 instruction들의 sequence가 됨

어떻게 하면 두개의 온도를 읽어오는 Operation을 atomic하게 만들 수 있을까?

Operation을 수행하는 중간에 interrupt가 발생 안하게끔 하면 됨

인터럽트를 disable 시키면 됨

atomic operation을 구현하는 것은 S/W적으로는 어렵다(가능하지만 엄청 복잡함)

H/W적인 도움이 필요 

Synchronization을 필요로 하는 또 다른 예

자원공유 문제를 해결하기 위해 버퍼를 guard하는 플래그변수를 둔다

- BufferIsAvail 이 플래그 변수임 (True일 때만 프로세스가 들어감)

- 여기서 share하는 프로세스는? UseBuffer()와 BufferIsAvail

그러나 플래그값을 설정하기 전에 인터럽트가 발생하여 한 버퍼에 두개의 프로세스가 동시 접근하는 상황이 발생

Synchronization: interaction하는 프로세스들이 자원을 공유하는 것

Synchronization의 문제: OS이 아무런 조작을 하지 않으면 문제가 생기는 것, Race Condition

Race Condition(경합 조건)

여러 Process들이 동기화 절차를 거치지 않고 동시에 자원을 사용하기 위해 경쟁함으로써 그 수행 결과를 예측할 수 없게 되는 상황

해결방법

- 자원을 공유하는 코드 구간을 atomic하게 만드는 것

- 어떻게 atomic하게 만들었는가? interrupt를 disable시킴

- 프로세스와 인터럽트 서비스 루틴에 대해 문제를 해결하는 방법임

프로세스와 프로세스의 문제해결 방법은?

- 싱글프로세스에서는 인터럽트를 방지(interrupt disable)하면 Context Switching도 일어나지 않게 되어 문제해결

- 그러나 강력한 조치방법이기 때문에 종종 좋지 않은 문제가 발생함...

앞의 BufferIsAvail의 문제는 읽고 modify(수정)하는 구간을 다른 프로세스가 진입하는 것을 허용한 것임

그래서 그것을 막아줘야 함

Critical section: Code Section 코드의 한 조각을 Non-interrupt하게 atomic하게 만든 것

Critical section안에서는 한 프로세스만 들어갈 수 있음

Critical section안에는 Mutual exclusion이라는 현상이 나타나야 한다.

- 즉, Critical section안에 한 프로세스가 들어가 있으면 다른 프로세스는 배제 (Mutual exclusion) 시킬 수 있는 능력이 필요한 것

OS은 Mutual exclusion 메커니즘을 제공해야 한다

Mutual exclusion의 요구사항

- 주어진 시간에 언제나 하나의 프로세스만 허용 되어야 한다.

- 여러개의 프로세스가 진입을 원하면 그 중 하나만 진입할 수 있도록 허용해야 합니다.

- 이미 Mutual exclusion 안에 들어간 프로세스는 최대한 빨리 나와야 한다

- Mutual exclusion은 프로그램을 하다보면 빈번하게 발생하기 때문에 성능도 굉장히 좋아야 한다

우리가 가지고 있는 Mutual exclusion 메커니즘은?

interrupt disable과 enable

Semaphores: Semaphores (1)

interrupt disable과 enable은 너무 강력한 수단이라 자주 사용하기에 적합하지 않음

그래서 개발한 Mutual exclusion(상호배제) 메커니즘은 Semaphore (덴마크 dijkstra 박사님)

프린터는 전형적인 Non-Preemptive 자원임

프로세스  >>  프린터 쓰는 사람

Waiting Queue  >>  벤치

OS  >>  수위 아저씨

Critical Section  >>  프린트 방

Semaphore  >> 방 열쇠

API  >>  수위아저씨와의 대화 ("열쇠 줘")

Semaphore: Synchronization을 제공해 주는 integer(정수) 변수 받는 것이다 (1=열쇠있음, 0=열쇠없음)

세마포어 API

1) 열쇠 줘 Operation을 lock(S) = wait(S) = P(S)

2) 열쇠 받아 Operation을 unlock(S) = signal(S) = V(S)

동기화 뿐만아니라 스케줄링에도 관여한다

- wait (running->wait), signal(wait->ready)은 프로세스 state transition을 야기한다)

- signal은 타겟에게 컨트롤을 찔러줌 (control transfer의 관점도 있다)

주목할 점

- P operation과 V operation 모두 semaphore를 파라미터로 하고 있고

- 두 개가 같은 프린터 룸에 들어가고 싶으면 같은 세마포어 변수를 파라미터로 줘야 한다

- 세마포어 변수가 프린터 자원을 가드하는 세마포어 변수다

- 세마포어는 integer 변수라고 했으니 값을 초기화 시켜야 함 (초기값 1로 지정)

- integer 값으로 0과 1을 갖을 수 있다.

이럴 경우 세마포어의 integer 수는 0, 1, 2 값을 갖는다

세마포어 종류

binary semaphore: 있다 없다를 분류하는 것

Counting semaphore: 여러개의 있다를 표현할 수 있는 것. share되는 자원의 개수만큼 세마포어가 있어야 한다

Q.슬라이드의 예제에서 Counting Semaphore의 초기값은 어떻게 설정해야 하는가?

A. 가용한 자원(프린터)이 2개 있으므로 Semaphore(열쇠)의 초기값은 2가 되어야 한다.

Synchronization문제를 보게 됐던 원인을 보겠습니다

- Buffer를 사용하게 했는데 BufferIsAvail이라는 플래그 변수가 문제가 됨

- 이것을 세마포어로 표현하면 IF문이 사라지게 됨

- Why? IF문에 P와 V안에 들어갔기 때문

- BufferIsAvail은 Buffer 인스턴스의 개수만큼 초기화 시킴

- 세마포어의 역할은 상호배제와 스케줄링이다

Task의 시작부분에 P를 넣어 waiting하게 하고 ISR(interrupt Service Routine)은 그 중간에 V를 넣어서 Task를 깨우게 하는 것

이 경우에는 pair로 사용하지 않음. 우리가 지금까지 봤던 세마포어는 pair로 사용이 됐음 (Critical section이라고 하는 코드의 시작과 끝을 표현해 줘야 했기 때문에)

자원의 동기화가 필요한 concurrent의 대표적인 예 (Dining Philosophers)

- synchronization(동기화) 문제, resource(자원) 문제, Deadlock(교착상태) 문제, starvation(기아상태) 문제를 다 포함한 예시임

Producer(데이터 생성) - Consumer(데이터 읽기)

생성된 데이터를 consumer에게 전달하기 위해서 중간에 buffer를 사용함

- buffer의 사이즈는 제한이 되어 있음

- producer가 너무 빨리 생성하게 되면 buffer가 꽉차게 됨 (producer은 기다리게 됨)

- 반대로 Consumer가 너무 빨리 읽게 되면 buffer가 비어있게 됨 (Consumer가 기다리게 됨)

이것을 프로그래밍 하면 어려움 그러나 세마포어를 이용하면 심플하게 작성할 수 있음

Q. Producer/Consumer 예제에서의 Shared Resource는 무엇인가?

A. Data와 Buffer

P operation 열쇠를 없애는 것, V operation 열쇠를 다시 생성하는 것

자원이 Created되면 V()가 되고 destroyed되면 P()가 된다.

Synchronization 메커니즘들을 비교해보기

(세마포어 - interrupt disable) 프린트 룸을 공유하는 것으로 예시 들겠음

ex) 만약 프린트 인쇄회사가 부산에 지사를 냄 (서울: task A, B | 부산: tack C)

      task C를 하는 동안 인터럽트 disable 하면 부산과 상관없는 서울의 A, B도 수행이 불가능 해짐

Interrupt Disable을 사용한 Synchronization의 문제

Interrupt Disable은 시스템 전체에 영향을 미치기 때문에 상관 없는 Process의 수행도 방해하게 됨

Structured Construct

if(  )  {            } // 괄호가 누락되면 컴파일러가 신텍스에러 발생

- 프로그래밍 할 때 한 부분에 문제가 생겼을 때 체계적으로 찾아줄 수 있는 것 (항상 같이 쓰는 것)

Semaphore의 단점

Unstructured Programming Construct이기 때문에 컴파일러 등의 도구를 사용한 디버깅이 어려움

- P( ) .... V( ) 중 하나가 누락되도 에러 안남 (또는 argument를 잘못 써도 알 수가 없음)

producer - consumer 예시를 다시 보겠음

producer - consumer 프로그래밍을 짠 것이라면 맞지만

buffer를 접근하는 것을 가드하기 위해서 프로그램을 짠 것이라면 잘못됨

P(S1), V(S1) 으로 적어야 맞다

- S1을 S2로 잘못 적어도 에러가 안나오기 때문에 오류를 찾기 어려움

이것이 세마포어의 가장 큰 문제임

- 세마포어는 Unstructured Programming Construct 기 때문에

- 세마포어 버그를 만들게 되면 찾기도 굉장히 어렵고 의도 파악도 굉장히 어려움

---

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=651

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=652