[운영체제 - 김덕수 교수님]프로세스 동기화 & 상호배제(1/7)

Process Synchronization(동기화)

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

‏‏‎ ‎

동시에 그림을 한 도화지에 두 명이 그림을 그리기로 했을 때,

서로 대화를 나눠 약속을 정해야한다. 여기서 대화가 동기화 이다.

‏‏‎ ‎

Asynchronous and Concurrent P's

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

동시에 (같은 자원에 대해) 작업 을 하는데 서로 모른다는 것은 대화를 하지 못한다는 것이고, 문제가 발생한다.

‏‏‎ ‎

Terminologies

• Shared data(공유 데이터) or Critical data
  • 여러 프로세스들이 공유하는 데이터
• Critical section(임계 영역)
  • 공유 데이터를 접근하는 코드 영역(code segment)
  • 예를들어 프로세스에서 어떤 코드가 A 메모리 영역을 보고 있는데, 다른 프로세스에서 또 다른 코드가 A 메모리 영역을 본다면, 이 코드들이 임계 영역이 되는 것이다.
• Mutual exclusion(상호배제)
  • 둘 이상의 프로세스가 동시에 critical section 에 진입하는 것을 막는 것

‏‏‎ ‎

Critical Section(example)

두 프로세스가 공유 데이터에 1을 더하는 연산을 한다고 할 때, 즉

Pi 와 Pj 가 같은 연산을 한다고 할 때, shared Data 에는 어떤 값이 들어가야 할까?

하나의 기계어 명령을 실행 중에는 방해받지 않는다

그렇지만, 위의 명령이 아래에 3개의 기계어인 것인데,

수행과정은 조건에 따라 달라질 수 있다.

만약 Race Condition 이라고 한다면, sdata 에 저장되는 값은 0 이다.

그 이유는 Pi - 1,2,3 명령을 하는 동안 Pj - a,b,c 명령이 제어권을 얻을 수 있다.

그렇게 되면 순서가 섞이므로 sdata == 1 이 되는 것이다.

이를 해결하기 위한 방법으로 Mutual Exclusion(상호배제) 가 나왔다.

‏‏‎ ‎

Mutual Exclusion(상호 배제)

임계 영역에 다른 작업이 들어 오는 것을 막는 것

‏‏‎ ‎

Mutual Exclusion Methods

이를 구현하는 방법을 생각해보자.

• primitives == 어떤 목적을 달성하기 위해 기본적인 연산

‏‏‎ ‎

• Mutual exclusion primitives
  • enterCS() primitive
    • Critical section 진입 전 검사
    • 다른 프로세스가 Critical section 안에 있는지 검사
  • exitCS() primitive
    • Critical section 을 벗어날 때의 후처리 과정
    • Critical section 을 벗어남을 시스템에 알림

‏‏‎ ‎

Requirements For ME primitives

• Mutual exclusion(상호배제)
  • Critical section(CS) 에 프로세스가 있으면, 다른 프로세스의 진입을 금지
• Progress(진행)
  • CS 안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해하면 안됨
• Bounded waiting(한정대기)
  • 프로세스의 CS 진입은 유한시간 내에 허용해야함

‏‏‎ ‎

Two Process Mutual Exclusion

[version1]

자신의 턴이면 들어갈 수 있다.

나오면서 상대편에게 알린다.

• ME
• Progess
• Bounded waiting

위의 조건을 다 만족할까?

1. P0 이 돌다가 죽어버리면?

임계 영역에 아무도 없다.

비어있지만 P1 은 들어갈 수 없다.

=> Progress 조건 위배

‏‏‎ ‎

1. P0 가 한번 실행을 하고나면?

다음은 P1 의 차례인데, 아직 오고 있다.

그래서 P0 이 다시 실행을 하려해도, 턴이 P1 에게 가기 때문에

임계 영역이 비어있음에도 P0은 실행을 할 수 없다.

=> Progress 조건 위배

‏‏‎ ‎

‏‏‎ ‎

[version2, 3]

‏‏‎ ‎

전략: 들어갈 거면 깃발을 들고 안들어갈 거면 깃발을 내리자

• ME
• Progess
• Bounded waiting

위의 조건을 다 만족할까?

‏‏‎ ‎

문제는 프로세스가 실행중에 깃발을 드니까, 그 사이 선점당하면

두 프로세스가 모드 깃발이 세워진 채로 실행을 한다.

=> 상호 배제 위반

그렇다면 해결책은?

프로세스 실행 전에 깃발을 들자(의사표시)

‏‏‎ ‎

들어가기 전에 깃발을 들면, 두 프로세스 모두 플래그는 세워져 있는데 while 문에서 걸리게된다.

=> Progress, Bounded waiting 조건 위반

‏‏‎ ‎