프로세스 동기화 & 상호배제 #1 - Critical Section, Mutual exclusion primitives

Process Synchronization (동기화)

다중 프로그래밍 시스템

• 여러 개의 프로세스들이 존재
• 프로세스들은 서로 독립적으로 동작
• 공유 자원 또는 데이터가 있을 때, 문제 발생 가능
  -> 공유된 자원, 데이터를 수정하거나 생성하는 등의 경우에 문제 발생 가능성 

동기화 (Synchronization)

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

 

Asynchronous and Concurrent P’s

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

Terminologies

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

 

Critical Section

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

• Atomicity (원자성), Indivisible (분리불가능)
• 한 기계어 명령의 실행 도중에 인터럽트 받지 않음

프로세스 Pi와 Pj에서 공유 데이터 sdata에 +1 하는 연산을 수행한다.

동시에 작업할 때 2가 되어야 하지만 그 결과를 보장할 수 없다.

 

 

Mutual Exclusion (상호배제)

Race condition을 제거하기 위한 방법

하나의 프로세스가 Critical Section(임계 영역)에 진입 시 다른 프로세스의 접근을 막는다.

 

Mutual Exclusion Methods

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에 진입하는 것을 방해 하면 안됨
    -> CS가 비어있는 상태에서 다른 프로세스가 진입하는 프로세스를 방해 X
• Bounded waiting (한정대기)
  
  • 프로세스의 CS 진입은 유한시간 내에 허용되어야 함

 

Two Process Mutual Exclusion

 

ME Primitives version 1

• P0은 turn이 0일때 접근가능, P1은 turn이 1일 때 접근가능
• CS에서 빠져나온 후 상대방에게 turn을 넘겨준다.

Progress 조건 위배

• P0이 critical section에 진입 하지 않는 경우에 P1은 CS에 진입 불가
• 한 Process가 두 번 연속 CS에 진입 불가

 

ME Primitives version 2

• 진입시 flag : true , 나올 때 falg : false
• P0의 flag가 true 이면 P1은 진입 불가

Mutual exclusion 조건 위배

• P0이 P1의 flag를 체크하고 나서 Preemption이 일어나고 P1이 CS에 진입 하고 P0이 다시 수행 된다면 두 프로세스가 모두 CS에 진입하게 된다.

 

ME Primitives version 3

• 다른 프로세스의 flag를 확인하기 전에 먼저 flag를 true로 변화

Progress, Bounded waiting 조건 위배

• P0의 flag를 true로 바꾸고 나서 preemption이 일어나면 P1과 P2 모두 진입 불가

 

 

강의

www.youtube.com/watch?v=wdaf2gy83uU&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=12