[Operating System ⑥] 프로세스 동기화와 상호배제

4 분 소요

[Operating System ⑥] 프로세스 동기화와 상호배제

프로세스 동기화와 상호배제

HPC Lab 김덕수 교수님의 운영체제 강의를 정리한 내용입니다. :+1:

강의링크


목차

:point_right: [1] 프로세스 동기화와 상호배제

  1. 동기화란

  2. 비동기와 병행

  3. 관련용어

  4. 상호배제

  5. 상호배제의 방법들

  6. 상호배제 프리미티브가 만족해야하는 조건들

  7. 두 프로세스의 상호 배제



:pushpin: 프로세스 동기화와 상호배제

1-A. 동기화란

Process Synchronization 동기화

우리가 사용하는 컴퓨터는 여러 개의 Process들이 존재하는 다중 프로그래밍 시스템이다. 이러한 시스템에서는 Process들이 독립적으로(동시에) 동작한다.
이 때 자원 한 개를 여러 Process가 동시에 사용하려 한다면 어떨까?

:raising_hand: 예시
Process A와 Process B가 동시에 도화지에 그림을 그리려 한다면?
도화지에는 A도 B도 원치 않는 결과물이 생길 것이다. 그런 상황을 막기 위해서, A와 B는 대화가 필요하다.

  • 나는 이쪽을 그릴 테니 너는 저쪽을 그려
  • 나는 이 시간에 그릴 테니 너는 저 시간에 그려라

이렇게 각 Process들이 동작을 맞추는 행위를 동기화라고 한다.

1-B. 비동기와 병행

그렇다면 ‘비동기적(Asynchronous)’이라는 말과 ‘병행적(Concurrent)’라는 말은 어떻게 해석할 수 있을까?

  1. 비동기적(Asynchronous)
    • 프로세스 A와 B가 서로 동작은 맞추는 행위가 동기적이라면, 비동기적은 프로세스 A와 B가 서로 어떻게 동작하는지 알지 못하는 것을 말한다.
  2. 병행적(Concurrent)
    • 병행적이라는 말은 프로세스들이 동시에 시스템에 존재하며, 동시에 동작을 하는 것을 의미한다.

만약 병행 수행중인(동시에 작업중인) 비동기적(서로 모르는) 프로세스들이 자원에 동시에 접근하려 한다면, 문제가 발생할 수 있다.

1-C. 관련용어

  1. Shared data / Critical data : 공유 데이터
    • 여러 프로세스들이 공유하는 데이터로 공유할 때 잘못 건드리면 문제가 되는 중요한 데이터이다.
  2. Critical section: 임계 영역
    • 공유 데이터에 접근하는 코드 영역이다.
  3. Mutual exclusion: 상호 배제 :heavy_exclamation_mark:
    • 둘 이상의 프로세스가 동시에 임계 영역에 진입하는 것을 막는 것이다.

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

  • Atomicity(원자성)/Indivisible(분리 불가능): 하나의 명령은 실행 도중에 분리될 수 없다. 즉, 인터럽트를 받지 않는다.


상호배제 예시


위의 그림은 같은 코드를 가진 프로세스 Pi와 Pj가 공유데이터 sdata를 활용하여 작업을 하는 그림을 나타낸다.
두 프로세스는 0이라는 s(hared)data의 값을 가져온 뒤에 +1연산을 하여 다시 sdata에 저장하는 동일한 코드를 가지고 있다.

두 프로세스가 작업을 마치면 sdata값은 반드시 2가 될까?
그렇지 않은 경우를 살펴보자.

기계어로 컴파일된 Pi와 Pj 코드

<br<

Pi와 Pj가 컴파일 되면, 위의 그림과 같이 3단계의 머신 인스트럭션으로 번역된다.

Pi와 Pj의 machine instruction 내용

  1. 공유데이터인 sdata를 읽어와서 Ri에 저장해라
  2. Ri값에 1을 더해라
  3. Ri값으로 sdata를 초기화해라

각각의 instruction은 Atomic하기 때문에 중간에 방해를 받을 수 없다.
하지만, Instruction들의 사이사이에는 방해를 받을 수 있고, 명령 수행과정이 달라짐에 따라서 결과값이 달라질 수 있는 상황을 Race condition(달리는 순서에 따라 결과가 달라지는 상태)이라 한다.

Race condition 예시
명령 수행 과정 1 -> 2 -> (preemption) -> A -> B -> C -> 3


1-D. 상호배제

그럼 Race condition과 같은 문제를 방지하기 위해 어떤 방법이 필요할까?

이를 위한 방법이 바로 상호배제이다. 앞에서 본 예시에서의 race condition 상황을 막기 위해서는 1~3작업이 일어나는 중(Critical section)에는 인터럽트가 들어올 수 없도록 해야한다.


즉, 이미 하나의 프로세스가 Critical section에 들어와 있다면 다른 프로세스가 들어오는 것을 막아주는 작업이 필요한 것이다.

1-E. 상호배제의 방법들

Mutual Exclusion Methods

상호배제 구현을 위한 기본연산들을 알아보자.


  1. enterCS() primitives: 임계영역에 들어가기 위한 연산
    • 하나의 프로세스만 들어가야 하기 때문에, Critical section에 프로세스가 존재하는지를 검사한다.
  2. exitCS() primitives: 임계영역으로 부터 나올 때 사용하는 연산
    • 임계영역에서 벗어난다는 것을 시스템에 알려줌으로서, 다른 프로세스가 진입할 수 있게 한다.

:pencil2: Note

  • Primitives : 컴퓨터 공학에서 Primitive란, 어떤 목적을 달성하기 위해 가장 기본이 되는 연산을 말한다.

1-F. 상호배제 프리미티브가 만족해야하는 조건들

Requirements for ME primitives

상호배제를 위한 기본연산들을 ME 프리미티브라하며, enterCS와 exitCS 프리미티브가 있었다. 이 프리미티브가 만족해야하는 조건들은 다음과 같다.

  1. Mutual exclusion (상호배제)
    • CS(Critical section)에 프로세스가 존재하면, 다른 프로세스가 들어오지 못하게 한다.
  2. Progress (진행)
    • CS 안이 비어있는 경우에 다른 프로세스가 들어가는 것을 방해해서는 안된다.
    • 즉, CS에 프로세스가 존재하지 않는 다면 어떠한 프로세스도 들어갈 수 있어야 한다.
  3. Bounded waiting (한정대기)
    • 프로세스는 제한된 대기시간 내에 CS에 진입해야 한다.
    • 무한정 대기해야 하는 상황을 만들어선 안되고, 언젠가는 진입할 수 있게 해야 한다.


1-G. 두 프로세스의 상호 배제

두 개의 프로세스에 대한 상호배제 케이스를 몇 가지 살펴보자.

ME Primitives version 1


:point_right: P0을 보자

  • turn : CS에 진입할 차례인 프로세스 idx
    • 차례가 돌아온 프로세스만이 CS에 진입할 수 있다.
  • while (turn = 1) do : turn이 1일 경우 while문에서 대기하고, turn이 0이 되면 P0의 차례이기 때문에 작업을 진행한다.

그렇다면 Version1의 논리가 ME Primitives의 3가지 조건을 만족할까? => Nope !

:-1: 반례1

  • turn == 0인 상태에서 P0이 작업을 하던 도중 죽었다.
  • CS에 프로세스 존재하지 않지만, turn에 1을 삽입하기 전에 P0가 죽었기 때문에, P1이 들어갈 수 없다.
  • 즉, [2] Progress (진행) 조건 위배

:-1: 반례2

  • P0가 작업을 마치고, turn을 1로 초기화 시켰다.
  • 하지만, P1이 CS로 접근하는 것보다, P0가 다시 CS로 접근하는 속도가 더 빨라 P0이 CS에 더 먼저 도착했다.
  • 이 때, CS가 비어있음에도 불구하고 turn이 1이기 때문에 P0는 들어갈 수 없다.
  • 즉, 2번 연속 진입이 불가하므로, [2] Progress (진행) 조건 위배

ME Primitives version 2


  • turn대신 flag라는 boolean 변수를 두었다.
  • CS에 진입하려면 flag (깃발)을 true (들고)로 하고, 퇴장하려면 flag를 false (내리자) 로 한다.
  • 즉, 다른 프로세스의 깃발을 확인하고 false일 경우 CS에 진입하고, 나의 깃발을 true로 둔 뒤에 작업이 끝나면 false로 변경한다.

Version2의 논리가 ME Primitives의 3가지 조건을 만족할까? => Nope !

:-1: 반례1

  • P0가 flag[1]가 false인 것을 확인하고, CS에 진입하기 직전에 preemption되었다.
  • 그 후 P1이 flag[0]가 false인 것을 확인하고, CS에 진입하여 작업을 진행한다.
  • 작업 중 preemption이 되고, P0가 다시 running상태가 되어 CS영역에 들어와 작업을 진행한다.
  • 이런 경우 CS안에 P0와 P1이 함께 있게 되므로, [2] Mutual Exclusion(상호배제) 조건이 위배된다.

문제는 프로세스가 CS에 진입하기 전에 flag를 초기화하기 때문.

ME Primitives version 3

version 2에서 flag가 CS 진입 전에 초기화되는 문제를 개선한 version 3 방법이다.


  • CS 진입 직전이 아니라 먼저 의사를 밝히고 들어가보자


Version3의 논리가 ME Primitives의 3가지 조건을 만족할까? => Nope !

:-1: 반례1

  • P0이 CS에 진입하겠다는 의사를 표한 뒤에(flag[0] = true) preemption된다.
  • 그 후 P1이 CS에 진입하려고 한다.
  • 현재 CS는 비어있는데도 불구하고 P1이 진입하지 못하는 문제가 발생한다.
  • 즉, [2] Mutual Exclusion(상호배제) 조건이 위배된다.


다음 시간에 더 발전된 상호배제 구현 논리에 대해서 알아보자



:bulb: 요약

프로세스 동기화와 상호배제

  1. 동기화 : 다중 프로그래밍 시스템에서 프로세스들이 서로 동작을 맞추는 (대화하는) 행위
  2. 비동기적, 병행적: 서로 모르는, 동시에 작업 중인
  3. 관련 용어 : Shared(critical) data, Critical section, Mutual exclusion
  4. 상호배제 : CS에 프로세스 존재하면 인터럽트 막음
  5. 상호배제 프리미티브 : enterCS, exitCS
  6. ME 프리미티브 조건 : ME, Progress, Bounded waiting
  7. 상호배제 논리들과 반례

태그:

카테고리:

업데이트:

댓글남기기

참고