Chapter6 프로세스 동기화 & 상호배제

Chapter6 프로세스 동기화 & 상호배제

1. 동기화(Synchronization)란?

• 다중 프로그래밍 시스템내에서 프로세스들은 서로 독립적인 동작을 하기 때문에, 공유 자원을 사용할 때 문제가 생김 → 동기화가 필요
  • 동기화(Synchronization) : 프로세스들이 서로 동작을 맞추는 것
  • 비동기적(Asynchronous) : 프로세스들이 서로에 대해 모름
  • 병렬적(Concurrent) : 여러 개의 프로세스들이 동시에 시스템에 존재

 

1.1 용어

• Shared data(공유 데이터, Critical data) : 공유 데이터
• Critical Section(임계 영역) : 공유 데이터를 접근하는 코드 영역
• Mutual Exclusion(상호 배제) : 둘 이상의 프로세스가 동시에 critical sectiond에 진입하는 것을 막는 것
• 기계어 명령(machine instruction) : 명령 실행 중에 인터럽트를 받지 않음(원자성, 분리불가)
• primitive : 기본 연산

 

1.2 Mutual Exclusion

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

  

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

2. Mutal Exclusion Solution

2.1 SW Solution

2.1.1 Dekker's Algorithm

• Two Process ME을 보장하는 최초의 알고리즘

• 

 

2.1.2 Peterson's Algorithm

• Dekker's 알고리즘의 간략화 버전

• 

 

2.1.3 Dijkstra's Algorithm

• 최초로 프로세스 n개의 상호 배제 문제를 소프트웨어적으로 해결

• 

• 

2.1.4 문제점

• 속도가 느림
• 구현이 복잡함
• ME primitive 수행 중에 Preemtion이 될 수 있음
• Busy waiting

2.2 HW Solution

2.2.1 TAS(Test And Set) Instruction

• Test와 Set을한번에 수행하는 기계어
  • 실행 중 interrupt를 받지 않음
•  

• 

• 

  • 3개 이상의 프로세스의 경우, Bounded Waiting 조건 위배
    • Starvation이 나타날 수 있음
• 특징
  • 구현이 간단
  • Busy Waiting 존재 → Semaphore로 해결

2.3 OS supported SW Solution

2.3.1 Spinlock

• 정수 변수

• 

• 연산의 종류
  • 초기화, P(), V() 연산으로만 접근가능

    • 

    • OS가 support 해줌
    • 전체가 한 instruction cycle에서 수행 됨
• 특징
  • 멀티 프로세서 시스템에서만 사용 가능
  • Busy waiting

 

2.3.2 Semaphore

• Busy Waiting 문제를 해결한 solution
• 음이 아닌 정수형 변수(S)를 가지고 함
  • 임의의 변수(S) 하나씩 ready queue 하나가 할당 됨
• 연산의 종류
  • 초기화, P(), V()
    • P : 검사, V : 증가

    • 

    • 모두 indivisible 연산(OS support)
• 종류
  • Binary semaphore : S가 0과 1 두 종류의 값만 가짐, 상호배제나 프로세스 동기화 목적으로 사용
  • Counting semaphore : S가 0이상의 정수값을 가질 수 있음, Producer-Consumer 문제 등을 해결하기 위해 사용
• 특징
  • No busy waiting
  • wake-up 순서는 비결정적 → starvation
• 해결할 수 있는 동기화 문제들
  • Mutual Exclusion
  • Process Synchronization problem
    • Processe들의 실행 순서 맞추기

    • 

  • Producer-Consumer problem
    • Producer : 메시지를 생성하는 프로세스 그룹
    • Consumer : 메시지를 전달받는 프로세스 그룹

    • 

      
      
      • 단일 버퍼 일 때

      • 

      • N개의 버퍼일 때

      • 

      • 

  • Reader-Wirter problem
    • Reader : 데이터 읽기 연산만 수행
    • Writer : 데이터에 대해 갱신 연산을 수행

    • 

    • 데이터 무결성 보장 필요
      • Reader들은 동시에 데이터 접근 가능
      • Writer들이 동시에 데이터 접근할 때, 동기화 필요
    • 해결법 : reader나 writer 한 쪽에 우선권 부여
  • Dining philosopher problem

 

2.3.3 Eventcount/sequencer

• 은행의 번호표와 비슷한 개념
• Sequencer
  • 정수형 변수
  • 생성시 0으로 초기화, 항상 증가만 함
  • 발생 사건들의 순서 유지
  • ticket() 연산으로 접근 가능
    • 현재까지 ticket() 연산이 호출 된 횟수를 반환
• Eventcount
  • 정수형 변수
  • 생성시 0으로 초기화, 항상 증가만 함
  • 특정 사건의 발생 횟수를 기록
  • read(E), advance(E), await(E, v)연산으로만 접근 가능
    • read(E) : 현재 Eventcount 값 반환
    • advance(E) : E ← E + 1, E를 기다리는 프로세스를 깨움(wake-up)
    • await(E, v) : v는 정수형 변수, E < v이면 E에 해당하는 프로세스를 대기시킴
• Mutual Exclusion solution

  • 

• Producer-Consumer proble solution

  • 

• 특징
  • No busy waiting
  • No starvation

2.4 Language-Level Solution

2.4.1 Monitor

• 공유 데이터와 Critical Section의 집합
• 구조
  • Entry queue(진입 큐) : 모니터 내의 procedure 수만큼 존재
  • Mutual exclusion : 모니터 내에는 항상 하나의 프로세스만 진입 가능
  • Information hiding(정보 은폐) : 모니터 내의 프로세스만이 공유 데이터 접근 가능
  • Condition queue(조건 큐) : 모니터 내의 특정 이벤트를 기다리는(signal()) 프로세스가 대기하는 곳
  • Signaler queue(신호제공자 큐) : 모니터에 항상 하나의 신호제공자 큐가 존재
    • signal() 명령을 보낼 프로세스가 임시 대기
• 자원 할당 문제 solution

  • 

  • 

• Producer-Consumer Problem solution

  • 

  • 

• Reader-Writer Problem solution
  • reader/writer 프로세스들간의 데이터 무결성 보장
  • writer 프로세스에 의한 데이터 접근 시에만 상호 배제 및 동기화가 필요

  • 

• Dining philosopher problem solution
  • 5명의 철학자가 생각하는 일 또는 스파게티 먹는 일만 반복적으로 수행
  • 포크는 철학자들 사이에 1개씩 존재(총 5개)하고 스파게티를 먹으려면 양 옆의 포크(2개)가 필요
  • 공유 자원 : 스파게티, 포크

  • 

  • 

  • 

• 특징
  • Language-level 구조
  • 사용이 쉬움
  • Deadlock등 error 발생 가능성이 낮음
  • 지원하는 언어에서만 사용 가능
  • 컴파일러가 OS를 이해하고 있어야 함