[운영체제] Concurrency: Mutual Exclusion and Synchronization - 1

운영체제 설계의 핵심 3가지 주제

 

Multiprogramming(멀티프로그래밍)

- 단일 처리 시스템 상에서 다수의 프로그램 관리

 

Multiprocessing(멀티프로세싱)

- 멀티프로세서 시스템 상에서 다수의 프로세스 관리

 

Distributed processing(분산 처리)

- 다수의 분산된 컴퓨터 시스템 상에서 수행되는 다수의 프로세스 관리

 

 

ㅡ> Concurrency(병행성) 문제가 발생

 

Concurrency Issues

- 프로세스 간 통신

- 자원에 대한 공유와 경쟁

- 프로세스들의 동기화

- 프로세스에 대한 시간 할당

 

 

Concurrency Terms

 

 

먼저 3가지 용어에 대해 알아보자.

 

Atomic Operation (원자적 연산)

- 함수 또는 액션으로 더이상 분할할 수 없는 단위

 

Critical Section (임계 영역)

- 공유 자원을 접근하는 프로세스 내부의 코드 영역. 다른 프로세스가 이 영역에 있을 때, 이 프로세스 또한 이 영역을 수행할 수 없다.

 

Deadlock (교착상태)

- 두 개 이상의 프로세스들이 더 이상 진행을 할 수 없는 상태 각 프로세스가 다른 프로세스의 진행을 기다리면서 대기하고 있을 때 발생

 

Livelock (라이브락)

- 두 개 이상의 프로세스들이 다른 프로세스의 상태 변화에 따라 자신의 상태를 변화시키는 작업만 수행하고 있는 상태

 

Mutual Exclusion (상호 배제)

- 한 프로세스가 공유 자원을 접근하는 임계영역 코드를 수행하고 있으면, 다른 프로세스들은 공유 자원을 접근하는 임계 영역 코드를 수행할 수 없다는 조건

 

Race Condition (경쟁상태)

- 두 개 이상의 프로세스가 공유 자원을 동시에 접근하려는 상태

 

Starvation (기아)

- 특정 프로세스가 수행 가능한 상태임에도 불구하고 매우 오랜 기간 동안 스케줄링되지 못하는 경우

 

 

Principles of Concurrency (병행성의 원리)

 

mutual exclusion을 보장해 줄 수 있는 방법

 

- semaphore(세마포어)

- monitor

- message passing

 

Difficulties of Concurrency 

 

프로세스들이 수행되는 상대 속도는 운영체제의 스케줄링 정책과 다른 프로세스들의 활동, 그리고 운영체제가 인터럽트를 처리하는 방법 등에 따라 동적으로 변한다. 하지만 이처럼 동적으로 변하는 특징은 다음과 같은 어려움을 가져온다.

 

- 전역 자원의 공유에 어려움이 발생한다.

- 운영체제가 자원을 최적으로 할당하기 어려워진다.

- 프로그래밍 오류를 찾기 어려워진다.

 

 

예시1 (단일처리기 기반 멀티프로그래밍 시스템)

같은 실행파일을 갖고 두개의 Thread(Process)를 만듦, global 변수 chin과 chout은 두 개의 thread에서 공유

 

1. 프로세스 P1이 echo함수를 호출한다. echo 함수는 우선 getchar 함수를 호출하여 사용자의 문자 입력을 대기한다. 

만일 사용자가 'x'를 입력하였다면, getchar는 그 입력결과를 chin 변수에 저장한다. getchar는 그 입력결과를 chin 변수에 저장한다. 이때 운영체제가 P1을 선점하고 다른 프로세스 P2의 수행을 결정하였다고 가정하자.

 

2. 프로세스 P2가 활성화되고 이 프로세스 역시 echo 함수를 호출해 'y'를 입력하였다면 chin 변수에 'y'가 저장될 것이다.

결국 프로세스 P2는 계속 수행하면서 화면에 'y'를 출력할 것이다.

 

3. 얼마 후 프로세스 P1의 수행이 다시 재개될 때 P1은 자신이 중지된 이후부터 수행한다. 즉, chout = chin 부터 수행할 것이다. 하지만 다시 수행하려 할 때는 chin에 'y'가 저장되어있어서 사용자는 'x'를 입력했지만 'y'가 출력될 것이다.

 

 

*공유되는 전역 변수에 대한 접근이 없는 경우

 

 

 

1. 프로세스 P1이 echo 함수를 호출하고, echo 함수는 우선 getchar 함수를 호출하여 사용자의 문자입력을 받는다.

만일 사용자가 'x'를 입력받으면 getchar는 그 입력 결과를 chin 변수에 저장하고 운영체제가 P1을 선점하고 다른 프로세스 P2의 수행을 결정하였다고 하자.

 

2. 프로세스 P2가 활성화 되지만 P1이 echo 함수 내에 있기 때문에, P2는 echo 함수로 진입하지 못하고 일시중지된다.

 

3. 얼마 후, P1은 수행이 재개되고 echo의 실행이 완료된다. 그러면 chin 변수에 저장되었던 문자 'x'가 출력된다.

 

4. P1이 echo 함수에서 나오면 P2는 일시중지 상태에서 깨어나 수행이 재개되고 'y'를 입력하면 'y'를 출력한다.

 

 

 

 

예시2 (멀티프로세서)

 

 

1. 두 개의 프로세스 P1과 P2가 각각 서로 다른 처리기에서 동시에 수행되고 있고, 모두 echo 함수를 호출한다.

 

2. echo 함수 내부에서 두 프로세스는 다음과 같은 순서로 진행을 의미한다.

 

수행 결과 P1에서 입력받은 문자는 화면에 출력되기 전에 손실되고, 프로세스 P2에서 입력받은 문자가 화면에 두번 출력된다.

 

 

예시1 에서는 전역 변수를 서로 공유하기 때문에 concurrency 문제가 발생한다.

 

예시2 에서는 메모리를 서로 공유하기 때문에 concurrency 문제가 발생한다.

 

 

 

Race condition(경쟁상태)가 발생하면 최종 수행 결과는 프로세스들의 수행 순서에 따라 달라진다.

 

 

 

Process Interaction (프로세스 간 상호작용)

 

Process unaware of each other

- 프로세스들 간에 자원에 대한 경쟁(competition)

Process indirectly aware of each other

- 자원 공유를 통한 협력(cooperation by sharing)

Process directly aware of each other

- 통신을 통한 협력(cooperation by communication)

 

 

 

 

Process unaware of each other

 

Competition (경쟁)

 

- 프로세스는 서로에 대해 존재를 모른다.

 

- 프로세스는 실행중에 자원에 접근해야하는데, 만약 두 프로세스가 같은 자원을 접근하려한다면 운영체제는 한 프로세스에게만 자원을 할당해 줄 것이고 나머지 하나는 기다릴 것이다.

 

- 각 프로세스는 다른 프로세스의 실행에 영향을 받지 않는다.

 

- 운영체제가 프로세스 사이의 경쟁을 컨트롤함.

 

 

Control Problems (발생가능한 문제)

 

- Mutual Exclusion (상호배제)

 

  process A가 critical section에 있다면 다른 어떤 process도 그 critical section에 들어가면 안된다.

 

 

 

- Deadlock (교착상태)

 

프로세스 P1, P2가 있고 자원 R1, R2가 있다고 가정하자. 각 프로세스는 자신의 작업을 완료하기 위해 두 자원이 모두 필요하지만, P1->R2, P2->R1 을 할당받아 사용 중이다. 이때 P1이 자원 R1을 사용하려 하지만, Mutual exclusion에 의해 P1은 R1을 할당받지 못하고 P2도 R2를 할당받지 못해 서로 상대방이 자원을 제공해줄 때 까지 기다릴 뿐, 할당받은 자원은 반납하지 않는다. 따라서 두 프로세스는 서로 대기만 할 뿐 더 이상 수행을 진행하지 못한다.

 

 

- Starvation (기아)

 

P1이 R을 사용하고 P2, P3가 R을 사용하기 위해 대기하고 있다고하자. P1이 critical section에서 빠져나와 R을 P3에게 할당했다하고 이 할당이 계속 반복되면 P2는 무한히 자원 R을 사용할 수 없게 된다. 이는 교착 상태는 아님에도 불구하고

자원 접근이 계속 거절되는 것이다.

 

Deadlock과 Starvation은 Mutual exclusion을 보장하려다 보니 부수적으로 발생

 

*Critical section : source code 중 한 영역, 공유 자원에 접근하는 부분

다음과 같은 코드에서 Process A의 printer_A에 a의 내용을 출력, Process B의 printer_A에 m의 내용을 출력이 critical section이라고 볼 수 있다.

또한 Process A가 실행되면 Process B에 코드는 Blocked되어 queue에 들어가서 기다리게 된다.

 

 

 

 

Process indirectly aware of each other

 

 

Cooperation by sharing (공유를 통한 협력)

 

- 프로세스들은 공유하는 데이터가 적절하게 관리될 수 있도록 서로 협력한다.

 

- 프로세스들은 그들 각각 PID에의해 서로 알지못한다.

 

 

Control problems

- Mutual Exclusion  <- OS가 알아서 해결 안해줌

 

 

 

- Deadlock

 

- Starvation

 

- Data coherences (데이터 일관성)

 

데이터들은 a=b라는 조건이 지켜져야하는데 변수 a,b는 P1,P2에 의해 공유된다.

 

 

위 같은 경우에 일관성이 유지되어 있고 각 프로세스가 개별적으로 수행된다면, 공유 데이터에 대한 처리가 완료된 후에도 데이터 일관성이 유지된다.

 

 

 

하지만 위처럼 mutual exclusion이 지켜지는 경우에도 데이터 일관성이 깨질 수 있다.

 

그렇기 때문에 공유를 이용한 협력의 경우에도 critical section의 개념이 중요하다.

 

 

 

 

 

Process directly aware of each other

 

Cooperation by communication

- 프로세스는 PID에 의해 서로 통신한다.

 

- 프로세스 사이에 실제로 공유되는 것은 없다. 그렇기 때문에 mutual exclusion 문제가 발생하지 않음.

 

 

Control problems

 

- Deadlock

 

각각 상대방으로 부터 메시지를 기다리며 블록되어 있는 경우

 

- starvation

 

프로세스 P1, P2, P3가 있을 때 P2와 P3가 모두 P1과 통신을 시도할때 P1이 P2와만 정보를 반복적으로 교환하면, P3는 계속 통신을 기다리며 대기하는 상황이 발생한다.

 

 

 

Requirements for mutual exclusion (상호 배제 요구조건)

 

1. 단 하나의 프로세스만이 Critical section에 접근할 수 있다.

 

2. non-critical section에서 멈춘 프로세스는 다른 프로세스의 수행을 간섭해서는 안된다.

 

3. Deadlock or starvation이 일어나지 않아야한다. (mutual exclusion을 보장한다고 deadlock 이나 starvation이 발생하지 않는 것이 아님.)

 

4. Critical section이 비어있다면, critical section에 들어가려 하는 프로세스는 바로 들어가야 한다.

 

5. 프로세스 속도나 프로세스 개수와 관련된 가정은 없어야 한다.

 

6. Critical section에 들어가서 무한히 머물 수는 없다.

 

How to satisfy Mutual Exclusion Requirements (상호배제 만족시키는 방법)

 

1. 모든 책임을 프로세스들이 담당하는 것

 

2. 특별한 용도로 설계된 기계어를 사용

 

3. 운영체제나 프로그래밍 언어에 의해 상호 배제 보장을 제공받는 것 (Semaphore, monitor, message passing)

 

 

 

 

Mutual Exclusion: Hardware Support