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

출처 : https://www.youtube.com/watch?v=wdaf2gy83uU&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=12

 

 

 

Process Synchronization (프로세스 동기화)

 

• 다중 프로그래밍 시스템
  • 여러 개의 프로세스들이 존재
  • 프로세스들은 서로 독립적으로 동작 (동시에 동작)
  • 공유 자원 또는 데이터가 있을 때, 문제 발생 가능
• 동기화 (Synchronization) : 대화
  • 프로세스들이 서로 동작을 맞추는 것
  • 프로세스들이 서로 정보를 공유하는 것

 

 

Asynchronous and Concurrent P's

 

• 비동기적(Asynchronous)
  • 프로세스들이 서로에 대해 모름
• 병행적(Concurrent)
  • 여러 개의 프로세스들이 동시에 시스템에 존재
• 병행 수행중인 비동기적 프로세스들이 공유 자원에 동시에 접근 할 때 문제가 발생할 수 있음

 

Terminologies

 

• Shared data(공유 데이터) or Critical data
  • 여러 프로세스들이 공유하는 데이터
• Critical section(임계 영역)
  • 공유 데이터를 접근하는 코드 영역(code segment)
• Mutual exclusion(상호 배제)
  • 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것

 

 

기계의 명령의 특성

• Atomicity(원자성), Indivisible(분리 불가능) : 하나의 명령이 수행되고 있을 때에는 이 명령이 끝날때까지는 반드시 수행이 되어야 한다, 중간에 누가 방해할 수 없다. = 한 기계어 명령의 실행 도중에 인터럽트를 받지 않는다.

 

Process Pi와 Process Pj가 동시에 shard data에 1을 더하는 연산을 수행한다고 해보자.

우리는 Pi가 1을 더하고 Pj가 1을 더했으므로 shared data는 0 -> 2가 될 것이라고 생각한다.

 

 

하지만 상황에 따라서 값이 달라질 수 있다.

 

s = s + 1 이라는 과정은 machine instruction에 의해서 3개의 과정으로 이루어지게 된다.

 

1. 어떤 register Ri에 sdata 값을 읽어와라.

2. register Ri에 1을 더해라.

3. register Ri에 값을 shared data에 저장해라.

 

우리는 atomicity에 의해서 각 단계가 수행하는 동안에는 다른 명령을 수행할 수 없지만 각 단계가 끝났을 때에는 다른 명령을 수행할 수 있다.

 

만약 명령 수행 과정 (2)의 순서대로 진행된다면, Ri와 Rj에는 모두 0 + 1 = 1이 되어 shared data 가 2가 아닌 1이 될 수 있다.

 

이렇게 명령 수행 과정의 순서에 따라 결과가 달라지는 Race condition이 발생할 수 있다.

 

우리가 원하는 결과를 보장하기 위해서 Mutual Exclusion (상호 배제)가 등장하게 된다.

 

Mutual Exclusion이란 하나의 프로세스가 critical section에 들어와 있으면 다른 프로세스가 들어오지 않게 만드는 것이다. 즉, 위 예시에서 명령 수행 과정 (1)의 과정을 거치도록 만드는 것이다.

 

 

Mutual Exclusion Methods

 

• Mutual exclusion primitives (Mutual exclusion을 구현하기 위한 기본이 되는 연산)
  • enterCS() primitive
    • Critical section 진입 전 검사
    • 다른 프로세스가 critical section 안에 있는지 검사
  • exitCS() primitive
    • Critical section을 벗어날 때의 후처리 과정
    • Critical section을 벗어남을 시스템이 알림

 

 

Requirements for Mutual Exclusion primitives (Mutual Exclusion primitives를 만족하기 위한 요구 사항)

 

• Mutual exclusion (상호 배제)
  • Critical section(CS)에 프로세스가 있으면, 다른 프로세스의 진입을 금지
• Progress (진행)
  • CS 안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해하면 안됨
  • ex) CS가 비어있는데 프로세스 A가 프로세스 B가 CS에 못들어가도록 막는 상황은 발생해서는 안된다.
• Bounded waiting (한정 대기)
  • 프로세스의 CS 진입은 유한 시간 내에 허용되어야 함 (프로세스는 언젠가는 CS에 들어갈 수 있어야 한다)

 

 

Two Process Mutual Exclusion

 

Version 1

 

Turn을 만들어서 내 턴일 때 CS를 진입하는 방식을 생각해보자.

우리가 아는 그 턴 맞다.

 

상대방의 턴일 때에는 계속 기다리고 있다가 내 턴이 되면 CS에 진입하고, 나올 때 Turn을 상대방의 턴으로 넘겨준다.

 

이 방식의 경우의 문제점은 Progress 조건에 위배된다는 것이다.

 

만약의 최초의 Turn이 0번이라고 할 때, 프로세스 P0가 repeat 단계에서 죽어버리면, Turn은 계속 P0의 턴이 되어버린다. CS는 비어있는데 P1은 자신의 턴이 오지않아 CS에 진입을 할 수 없게 되어버린다.

 

혹은, P0가 CS에 진입한 후, 퇴장할 때 Turn을 P1에게 넘겨줬다. 그런데 아직 P1은 repeat 단계에 머물러있는데, P0가 한 바퀴 돌아서 enterCS 단계에 있다면, CS가 비어있는데 P1이 P0가 CS에 진입하지 못하도록 방해하는 꼴이 되어버린다.

 

Version 2

 

P0와 P1에게 깃발을 만들어서 상대방의 깃발이 False 상태면 나의 깃발을 True 상태로 만든 뒤에 CS에 진입하고, CS에서 나올 때 자신의 깃발을 False 상태로 만드는 것이다.

 

이 경우의 문제점은 Mutual exclusion을 위배할 수 있다는 것이다.

 

만약 P0가 P1의 깃발이 false인것을 확인한 뒤에 자신의 깃발을 올리기 전에, 마찬가지로 P1가 P0의 깃발이 내려가 있는 것을 확인하고 자신의 깃발을 올려버리면 CS에 P0와 P1이 둘 다 들어가버리게 되는 경우가 발생할 수 있다.

 

 

Version 3

 

version 2에서 깃발을 먼저 True로 만든 뒤에 상대편의 깃발을 확인하는 방법이다.

 

이 경우의 문제점은 Progress, Bounded waiting을 위배하게 된다.

 

P0이 깃발을 True로 놓고, P1도 깃발을 True로 놓으면 P0와 P1 둘 다 반복문에서 탈출하지 못해 CS에 진입을 할 수 없는 상황에 놓이게 된다. 즉, CS는 비어있는데 상대편으로 인해 들어가지 못하고, 시간이 아무리 흘러도 아무도 들어가지 못하는 상황이 되어버린다.