운영체제 6 : Process Synchronization and Mutual Exclusion (1)

프로세스 동기화 & 상호 배제에 대해서 살펴보자.

 

• synchronization (동기화)
• Critical Section (임계 영역)
• Mutual Exclusion (상호 배제)

 

• Mutual Exclution Methods
• Mutual Exclution Primitives (turn, flag)

 

---

 

Process Synchronization (동기화)

 

동기화라는 개념이 어떻게 나왔을까?

다중 프로그래밍 시스템이 등장하면서 시작되었다.

 

다중 프로그래밍 시스템

: 여러 개의 프로세스들이 서로 독립적으로 동시에 동작한다.

 

- 따라서 공유 자원 또는 데이터가 있을 때, 문제가 발생할 수도 있다.

 

동기화 (Synchronization)

: 자원을 공유할 때 생기는 문제를 방지하기 위해 프로세스들이 대화하는 것이다.

 

- 프로세스들이 서로 동작을 맞추고, 정보를 공유한다.

 

비동기적 (Asynchronous)

: 프로세스들이 서로에 대해 모르는 상태이다.

 

병행적 (Concurrent)

: 여러 개의 프로세스들이 동시에 시스템에 존재하여 동작하는 상태이다.

 

 

즉, 병행 수행 중인 비동기적 프로세스들이 공유 자원에 동시 접근할 때 문제가 발생할 수 있다.

어떤 방식으로 문제가 발생하는 지 살펴보자.

 

 

---

 

용어 정리 (Terminologies)

 

Shared data, Critical data (공유 데이터)

: 여러 프로세스들이 공유하는 데이터

 

Critical Section (임계 영역)

: 공유 데이터를 접근하는 코드 영역

 

Mutual exclusion (상호 배제)

: 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것

 

 

---

 

Example

둘 이상의 프로세스가 동시에 Critical Section 에 진입하는 예시를 살펴보자.

 

두 프로세스 Pi 와 Pj가 sdata에 1을 더하려는 작업을 동시에 수행하면 어떻게 될까?

 

 

 

기계어 명령 (machine instruction)의 특성

- Atomicity (원자성), Indivisible (분리 불가능)

 

- 한 기계어 명령의 실행 도중에 인터럽트를 받지 않는다. 즉, 인터럽트는 기계어 사이 사이에 생길 수 있다.

 

 

위의 명령어를 기계어로 변환하면 아래와 같다.

 

기계어 명령으로 변환

 

결과 : sdata 는 상황에 따라 0 또는 1 값을 가진다.

- Pi 와 Pj 가 sdata를 동시에 가져와서 처리를 하면 모두 1 이라는 값을 sdata에 넣을 것이다.

 

- 둘 중 하나가 실행된 후에 다른 하나가 이어 실행된다면 sdata는 2 라는 값을 가질 것이다.

 

Race condition

: 이렇게 실행 순서에 따라서 결과가 달라지는 것

 

 

그래서 어떤 프로세스가 CS 에 들어와 있으면 다른 프로세스가 들어오는 것을 막는 상호 배제가 필요하다.

상호 배제를 구현할 방법을 찾아보자.

 

 

---

 

 

Mutual Exclusion Methods

상호 배제는 2가지 연산으로 3가지 조건을 만족해야 한다.

Mutual exlcusion primitives (가장 기본이 되는 연산)

: 상호 배제를 구현하기 위한 기본 연산으로 2가지가 있다.

 

1. enterCS( ) primitive

- Critical section 진입 전 검사하는 것

 

- 다른 프로세스가 Critical section 안에 있는 지 검사한다.

 

2. exitCS( ) primitve

- Critical section을 벗어날 때의 후처리 과정

 

- Critical section을 벗어났다는 사실을 시스템에게 알린다.

 

 

Requirements for ME primitives

: 상호배제 primitive 가 이뤄지기 위해 만족해야할 조건

 

1. Mutual exclusion (상호배제)

: CS 에 프로세스가 있으면, 다른 프로세스의 진입을 금지한다.

 

2. Progress (진행)

: CS 안에 있지 않은 프로세스가 CS에 진입하는 것을 방해하면 안된다.

 

3. Bounded waiting (한정 대기)

: 프로세스의 CS 진입은 유한시간 내에 허용되어야 한다. 즉, 무한정 대기할 수 없다.

 

 

---

 

Two Process Mutual Exclusion

1. ME Primitives 첫 번째 방법 (turn)

전략

P0 가 자신의 차례(turn)에 CS에 들어가서 작업을 수행하고, 다음 차례(turn)에 P1 이 CS에 들어가서 작업을 수행한다.

 

Progress 조건 위배

- P0 가 CS 에 진입하기 전에 죽어서 종료된다면 P1 은 자신의 turn이 오지 않아 CS 에 진입할 수 없다.

 

- 한 프로세스가 두 번 연속 CS 에 진입할 수 없다.

 

 

2. ME Primitives 두 번째 방법 (flag)

전략

CS 에 들어가기 전에 다른 프로세스가 CS에 들어가 있는 여부를 flag를 보고 파악한다.

 

만약 CS가 비었다면 자신의 flag를 최신화하고 CS에 들어간다.

 

Mutual exclusion 조건 위배

- P0가 실행되기 위해 P1의 flag를 보고 while문을 통과한다.

 

- P0가 flag를 최신화 하기 직전에 Preemption 되어 잠시 멈춘 경우, P1은 그 사이에 CS에 들어갈 수 있다.

 

- 뒤늦게 P0가 flag를 최신화 하지만 CS에는 두 프로세스가 들어간다.

 

 

3. ME Primitives 세 번째 방법 (flag)

전략

이전의 문제를 해결하기 위해, 들어갈 거라는 신호로 while문을 시작하기 전에 flag를 최신화 한다.

 

Progress, Bounded waiting 조건 위배

- P0 가 flag 최신화 후에 preemption이 되어 잠시 멈추었다면, P1은 flag를 최신화하고 while문을 돌 것이다.

 

- P0 가 다시 실행하려고 보니 P1의 flag 때문에 while문을 돌고 두 프로세스 모두 CS에 들어가지 못한다.

 

 

 

 

다음 글에서 ME를 구현할 다른 방법들을 살펴보자.

---

본 글은 HPC Lab. KOREAHECH YOUTUBE 채널의 김덕수 교수님 강의를 보고 작성되었습니다.

[Course] Operating System (CPA310) - 운영체제 강의