프로세스 동기화 & 상호배제 (Process Synchronization and Mutual Exclusion)

Process Synchronization (동기화)

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

Asynchronous and Concurrent P's

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

Terminologies

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

Critical section (example)

사진출처 - https://youtu.be/wdaf2gy83uU

• sdata에 s는 shared를 의미한다. 어떤 데이터에다 1을 더해주는 연산을 한다.
• Pi와 Pj 모두 똑같은 연산을 하고 있다.
• Pi와 Pj가 동시에 메모리에서 작동된다면, 우리는 메모리 sdata가 2가 되기를 기대한다. 하지만 꼭 그렇지 않을 수도 있다.
• 기계어 명령(machine instruction)은 실제로 프로세서가 실행하는 작은 단위의 명령어를 의미한다.
• 기계어 명령의 특징은 더이상 쪼갤 수 없는 원자성과 분리불가능이 있다. 기계어 명령은 한번 수행하면 그것이 끝날 때까지 계속 실행하게 된다. 중간에 누군가가 방해할 수 없다(쪼갤 수 없다).
• 즉 하나의 기계어 명령 실행 중에는 인터럽트를 받지 않는다, 방해를 받지 않는다.

Critical Section (example)

사진 출처 - https://youtu.be/wdaf2gy83uU

• s = s+1 연산이 실제로 총 3개의 연산으로 생성되게 된다.
• Load Ri, sdata : 어떤 레지스터 아래 shared data 값을 읽어와라
• Add Ri, 1 : 레지스터에다 1을 더해라
• Store Ri, sdata : 레지스터 값을 sdata에다 다시 저장해 놓아라
• CPU라는 것은 안에 레지스터를 가지고 있다. CPU의 작업은 레지스터를 통해 이루어진다.
• 실제 동작은 메모리 상에 있는 데이터를 레지스터에 가져와서 작업을 한 후에 그 결과를 다시 메모리에 쓰게 되어 있다.
• 1. 맨 처음 shared data의 값을 가지고 오게 한다. 그러면 Ri의 아래에는 0이 들어가게 된다.
• 2. 1을 더하니 1이 된다.
• cpu를 할당받은 상태 : running, cpu를 기다리고 있는 상태 : ready, preemption : 중간에 cpu를 빼앗긴 상태
• Race condition : 명령의 수행 과정에 따라 결과 sdata는 1이 될 수도 있고 2가 될 수도 있다.

Mutual Exclusion (상호배제)

사진 출처 - https://youtu.be/wdaf2gy83uU

• Race condition을 막기 위해 등장함
• 프로세스가 실행되는 중에는 preemption이 일어날 수 없도록 해야 한다.
• 한개의 프로세스가 Critical section에 들어와 있으면 다른 프로세스가 들어오는 것을 막아준다.

Mutual Exclusion Methods

• Mutual exclusion primitives
  primitives : 가장 기본이 되는 연산
  • enterCS() primitive : Critical Section에 들어가는 연산
    • Critical section 진입 전 검사 / 들어가기 전 노크
    • 다른 프로세스가 critical section 안에 있는지 검사
  • exitCS() primitive : Critical Section을 나오는 연산
    • Critical section을 벗어날 때의 후처리 과정 / 나가기 전 시스템에게 벗어났음을 알림
    • Critical section을 벗어남을 시스템이 알림

Requirements for ME primitives

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

Two Process Mutual Exclusion

사진출처 - https://youtu.be/wdaf2gy83uU

• version 1
• 내 턴이면 들어갈 수 있음
• Progress 조건 위배 : 비었는데 들어가지 못하는 경우

• version 2
• flag라는 것을 둬서 들어갈거면 깃발을 들고 들어가지 않을 거면 깃발을 내리자

<참고>

• https://youtu.be/wdaf2gy83uU