[OS] 6. 프로세스 동기화 - Mutual Exclusion

Process Synchronization (동기화)

다중 프로그래밍 시스템

• 운영체제에는 여러 개의 프로세스들이 존재 => 이러한 시스템을 다중 프로그래밍 시스템이다.
• 프로세스들은 서로 독립적으로 동작 (동시에 동작함)
• 공유 자원 또는 데이터가 있을 때 문제 발생 가능

예를들어 A가 어떠한 행동을 하려고 할 때 B가 A가 하려던 행동을 하면 서도 충돌이 발생함

이를 맞추기 위해 동기화 라는 것이 필요함.

동기화 (Synchronization)

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

비동기적 (Asyncjronous)

• 프로세스들이 서로에 대해 모름

병행적 (Concurrent)

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

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

 

용어 정리

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

 

Critical Section (example)

sdata 는 shared data, Pi와 Pj에서 +1연산을 concurrent하게 실행되고 있다. 

동시에 작업하게된다면 일반적인 관점에서 sdata에 2가 들어갈 것이라고 예상한다. 

프로그래밍 언어로 해당 연산에 대해 작성한다면 컴파일러가 Machine instruction으로 변역하게 된다.

번역 결과를 아래 그림에서 살펴본다면,

S = S + 1 의 연산이 MI으로 번역했을 때 3가지 과정으로 번역된다.

sdata에 값을 읽어와서(1번) 읽어온 값에 1을 추가(2번) 이후 sdata에 연산을 수행한 값을 저장(3번)

CPU의 작업과 동작

과연 결과가 2가 될까? => 상황에 따라 달라진다.

CPU를 할당받는 running 상태일 때 Cpu를 빼앗길 수 있다(Preemption=선점 스케줄링)

 

이를 위의 과정에서 생각해 본다면

• Preemption이 일어나서 Pi작업이 중지되고 Pj과정이 수행된다 (1번수행이후)
• Rj데이터를 가져오라고 할 것이다 (A과정)
• Rj+1을 한다 (B과정)
• B과정에서 Preemption 발생됨
• 이 사이에 2번 과정이 수행된다.
• Ri = 0 + 1 = 1 이 수행되고 3번과정 수행
• sdata에 Ri값 1을 저장
• C과정을 수행하면 Rj에 저장된 1값을 sdata에 저장함.

결과값 2를 기대하였는데 1이 저장됨.

실행순서에 따라 결과가 달라짐 => Race Condition

 

Mutual Exclusion (상호배제)

Race Condition을 방지하고 예산한 값을 도출하기 위한 방법

1,2,3을 실행하는 동안 다른 프로세스가 접근하지 못하게 하면 된다.

(CS(critical Section)에 누군가 있으면 다른 프로세스가 접근하지 못한다)

상호 배제의 개념

 

Mutual exclusion primitives

Multual exclusion을 어떻게 구현하냐?

primitive : 가장 기본이 되는 연산

enterCS () primitive

• Critical section 진입 전 검사
• 다른 프로세스가 critical section 안에 있는지 검사

exitCS () primitive

• Critical section 을 벗어날 때의 후처리 과정
• Critical section 을 벗어남을 시스템이 알림

 

Mutual exclusion primitives 를 만족해야 할 조건들

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

 

Two Process Mutual Exclusion

P0이 깃발이 내려간걸 확인후 CS에 들어가기 전에 잠시 멈춤.

그 사이에 P1이 깃발이 내려간걸 확인후 CS에 들어가서 작업을 한다.

이때 P0이 깃발이 내려간걸 확인하고 멈춘거여서 작업을 할당받으면 CS에 진입하게됨.

충돌이 일어남..

P0이 깃발을 올리고 잠시 멈춤 P1도 깃발을 올리고 잠시 멈춤.

P0이 CS에 들어가려고 할때 P1이 깃발이 들려있는 것을 보고 중지함

마찬가지로 P1이 CS에 들어갈려고 할때 P0이 깃발이 들려있는 것을 보고 중지함.

서로 CS에 진입하지 못하는 상황이 발생함.

 

 

어떻게 하면 상호배제가 잘 작동하는 알고리즘을 만들 수 있을까? (다음 포스팅 주제들)

Mutual Exclusion Solutions

• SW solutions
  
  • Dekker’s algorithm (Peterson’s algorithm)
  • Dijkstra’s algorithm , Knuth’s algorithm, Eisenberg and McGuire’s algorithm, Lamport’s algorithm
• HW solution
  
  • TestAndSet (TAS) instruction
• OS supported SW solution
  
  • Spinlock
  • Semaphore
  • Eventcount /sequencer
• Language Level solution
  
  • Monitor

 

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---