6. 프로세스 동기화 & 상호배제 (1) - 개요

강의 링크 : www.youtube.com/watch?v=wdaf2gy83uU&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=12

다중 프로그래밍 시스템의 경우

1. 여러 개의 프로세스들이 존재하고,
2. 프로세스들은 서로 독립적으로 동작하며, (동시에 동작)
3. 공유 자원 또는 데이터가 있을 때 문제가 발생할 수 있다
   • 문제 예시
     • A, B가 하나의 도화지 위에 그림을 동시에 그린다면 원하지 않는 결과물이 나올 수 있음
   • 해결 방법
     • A와 B가 대화를 나눈다. -> 여기서 대화라는 개념이 "동기화"가 되는 것

1. 동기화(Synchronization)

• 프로세스들이 서로 동작을 맞추는 것
• 프로세스들이 서로 정보를 공유하는 것

2. 프로세스의 특징

1) 비동기적 (Asynchronous)

• 프로세스들은 서로에 대해 모른다

2) 병행적 (Concurrent)

• 여러 개의 프로세스들이 동시에 시스템에 존재한다.

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

3. 용어 정리

1) Shared data (공유 데이터)

Critical data라고도 부름

(공유할 때 건드리면 크게 문제가 되니 critical data라고도 부름)

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

2) Critical section (임계 영역)

• 공유 데이터를 접근하는 코드 영역(code segment)

3) Mutual exclusion (상호배제)

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

4. Critical Section 예시

가운데 sdata는 공유 데이터 (share data)를 의미하고, 양 옆의 Pi, Pj 블록 내부의 주황색 영역이 CS임(sdata에 접근하므로)

• 공유 데이터 : sdata
• 프로세스 P1, 프로세스 P2에서 각각 sdata에 접근하는 코드 영역, 즉 CS는 주황색으로 칠해진 부분임

주황색에 적힌 식으로 코드를 짤 경우, C 혹은 C++과 같은 언어에서 컴파일러가 MI (Machine instruction, 기계어 명령)로 번역한다.

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

기계어 명령 : 실제로 프로세서(CPU)가 실행하는 가장 작은 단위의 명령어

• Atomicity (원자성)
  • 더 이상 쪼갤 수 없다. == 한 번 수행하면 중간에 멈출 수 없다.
• Indivisible (분리불가능)
  • 더 이상 쪼갤 수 없다. == 한 번 수행하면 중간에 멈출 수 없다.

-> 즉, 한 기계어 명령의 실행 도중에 인터럽트 받지 않음

위의 그림을 MI단위로 나누어 그려보면 다음과 같다.

CPU의 작업은 모두 레지스터를 통해 이루어집니당. 메모리 영역에 존재하는 데이터를 레지스터로 가져와서 작업 후에 그 결과를 다시 메모리에 가져다 놓는 고런 식이죠.

• 실행 순서에 따라 명령 수행 과정 (1), (2)가 존재할 수 있고, 각각의 결과가 다를 수 있다는 것을 알 수 있음
• -> 이를 "Race condition"이라고 함

5. Mutual Exclusion (상호배제)

• 누군가 CS(critical section)에 있으면, 다른 코드가 접근하지 못하도록 하는 것

상호배제 ! P1이 현재 CS에 존재한다면 P2는 진입할 수 없습니다.

6. Mutual exclusion primitives

mutual exclusion을 만들기 위한 가장 기본의 연산

(1) enterCS() primitive

CS 진입할 때 연산

• CS(critical section)에 진입하기 전에 검사한다
  • 다른 프로세스가 critical section안에 있는지
  • 마치, 화장실에 들어가기 전에 사람이 있는지 확인하는 것처럼

(2) exitCS() primitive

CS에서 나올 때의 연산

• CS를 벗어날 때의 후처리 과정
  • CS를 벗어나고, 이를 시스템한테 알린다.

7. Requirements for ME primitives

Mutual exclusion primitives를 만들기 위해 필요한 조건

(1) Mutual exclusion(상호배제)

• Critical section(CS)에 프로세스가 있으면, 다른 프로세스의 진입을 금지

(2) Progress (진행)

• CS안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해하면 안됨
• 안에 아무것도 존재하지 않으면 들어갈 수 있어야함

(3) Bounded waiting (한정대기)

bounded : 제한된

• 프로세스의 CS진입은 유한시간 내에 허용되어야 함

8. Two Process Mutual Exclusion

ME Primitives 구현 예시들 (조건에 위배되는 예시 3가지)

(1) turn을 사용하는 방법

turn을 사용한 방식입니다 ~!

• 내 턴이면 들어갈 수 있음
• P0은 turn값이 1이라면 기다리다가, turn이 0인 경우 CS로 진입하고, CS를 빠져나오면서 turn을 1로 바꿔준다.

[위배 상황]

1. 만약 turn의 값이 0인데, P0이 repeat을 돌다가 죽어버리면 ?

• CS에 아무 것도 존재하지 않지만, P1의 경우 turn이 0이므로 CS에 접근할 수 없다.

-> Progress 조건 위배 (CS가 비어있다면 들어갈 수 있어야함)

2. 만약 P0이 CS에 진입하고 빠져나와서 turn이 1인 상태에서 P1이 repeat을 지나 CS에 접근하는 시간보다, P0이 다시 repeat을 지나 while문에 도달한 경우?

• CS가 비어있기 때문에 진입할 수 있어야하는데, turn이 1이기 때문에 진입 불가

-> Progress 조건 위배 (CS가 비어있다면 들어갈 수 있어야함)

(2) flag를 사용하는 방식1

상대의 flag를 확인하고, 상대가 CS영역에 진입하지 않은 것을 확인했을 때 (상대의 flag가 False일 때) -> 진입

flag를 이용한 방식입니다

1. 상대의 flag를 확인한다.
2. 만약 상대의 flag가 True라면
   • 상대가 CS에 존재하는 것이므로 -> 대기
3. 만약 상대 flag가 False라면
   • 상대가 CS에 존재하지 않는 것이므로 -> 내가 들어감 & 내 flag는 True로 바꿈

[위배 상황]

1. 만약 P0이 진행되다가 Preemption화살표가 그려진 부분에서 Preemption이 발생한다면?
   • P1이 진행됨.
   • flag[1] = True
   • Preemption 부분으로 다시 넘어옴 (P0)
   • Preemption된 곳이 flag[0] = True 직전이었으므로, flag[0] = True로 갱신해 줌
   • flag[0] = True, flag[1] = True
   • -> 두 개 모두 true가 되어 Mutual exclusion 조건을 위배하게 됨. (기존에 P1이 CS에 존재했는데, P0도 CS에 진입하게 되므로)

(3) flag를 사용하는 방식2

앞의 방식과 달리 내 flag를 먼저 바꾸고 -> 상대의 flag를 확인한 후 CS로 진입

flag를 사용한 방식입니다. 앞의 방식과 순서가 조금 다릅니다용

[위배 상황]

1. flag[0] = true로 갱신
2. preemption 발생
3. flag[1] = true로 갱신
4. P0으로 넘어갈 경우, preemption이 발생한 지점이 상대의 flag를 확인하기 직전이므로 현재 상대의 flag가 true라서 무한 대기가 됨
5. -> Bounded waiting 조건 위배
6. CS에 진입한 프로세스 존재 X
7. -> Progress 조건 위배