운영체제 정리(2)

본 글은 Youtube ‘HPC Lab. KOREATECH’의 "[Course] Operating System (CPA310)-운영체제 강의" 의 ppt 내용을 요약한 정리본 입니다.

강의 Instructor: Duksu Kim

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

(Process Synchronization and Mutual Exclusion)

 

(1) Process Synchronization

다중 프로그램링 시스템: 여러 개의 프로세스들이 존재

프로세스들은 서로 독립적으로 동작

공유 자원 또는 데이터가 있을 때, 문제 발생 가능

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

 

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

 

Shared data(= Critical data)

Critical section(임계 영역): 공유 데이터를 접근하는 코드 영역(code segment)

Mutual exclusion(상호배제): 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것.

 

1) Mutual exclusion mehtods

- Mutual exclusion primitives: enterCS() primitive, exitCS() primitive

2) 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 solutions:
  • TestAndSet(TAS) instructino
• OS supported SW solution
  • Spinlock
  • Semaphore
  • Eventcount/wequencer
• Language-Level solution
  • Monitor

1. Dekker's alogirhtm

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

2. Dijkstra's Alogirhtm

flag[]값 | 의미

idle       프로세스가 임계 지역 진입을 시도하고 있지 않을 때

want-in  프로세스의 임계 지역 진입 시도 1단계일 때

in-CS     프로세스의 임계 지역 진입 시도 2단계 및 임계 지역 내에 있을 때

 

3. SW Solution들의 문제점

속도가 느림

구현이 복잡함

ME primitive 실행 중 preemption 될 수 있음

busy waiting, Inefficient

---------------------------------------------------------------------

4. TAS instruction(TestAndSet)

Test와 Set을 한번에 수행하는 기계어

Target값을 반환하면서, Target값을 True로 변환.

Machine instruction --> 실행 중 interrupt를 받지 않음(preemption 되지 않음)

Busy waiting --> inefficient

HW solution의 장점: 구현이 간단

                        단점: Busy waiting-->Inefficient

Busy waiting 문제를 해소한 상호배제 기법 --> Semaphore 대부분의 OS들이 사용하는 기법

3개 이상의 프로세스의 경우, Bounded Waiting 조건 위배 --> 한 프로세서가 Critical Section에 못 들어갈 수도 있음.

 

•  N-process mutual exclusion

5. Os supported SW solution

• Spinlock: 
  
  • 정수형 변수 S
  • 초기화, P()(물건 꺼내가, 자물쇠 걸어 --> 물건이 없으면 뺑뺑돌면서 기다려), V()(물건 반납, 자물쇠 풀어) 연산으로만 접근 가능
    • 위 연산들은 indivisible(or atomic) 연산
      • OS support --> 보장
      • 전체가 한 instruction cycle에 수행 됨.

init active =1; --> 임계 지역을 실행중인 프로세스 없음. 0이면 있음.

P(active); 자물쇠 걸어-->P연산은 중간에 preemptive 되지 않고 끝까지 수행됨을 보장하기 때문에, 동시에 들어가거나 아무도 못들어가는 문제 발생하지 않음.

Critical Section

V(active); 자물쇠 풀어.

 

문제: 

- 멀티 프로세서 시스템에서만 사용 가능

- Busy waiting!

• Semaphore (s)
  • 1965년 Dijkstra가 제안
  • Busy waiting 문제 해결
  • 음이 아닌 정수형 변수(s)
    • 초기화 연산, P(), V()로만 접근 가능
      • P: Probern(검사)
      • V: Verhogen(증가)
    • 임의의 s 변수 하나에 ready queue 하나가 할당 됨.
• Binary semaphore
  • s가 0과 1 두 종류의 값만 갖는 경우
  • 상호배제나 프로세스 동기화의 목적으로 사용
• counting semaphore
  • S가 0이상의 정수값을 가질 수 있는 경우
  • Producer-Consumer 문제 등을 해결하기 위해 사용
    • 생산자-소비자 문제
• 초기화 연산
  • s 변수에 초기값을 부여하는 연산
• P()연산, V()연산
  • P(s) --> 자물쇠 거는, 물건을 꺼내가는
    • if(S>0) then S<-S-1; else(물건이 없을 때) wait on the queue Q_s;
  • V(s) -->자물쇠를 푸는 연산
    • if(exist waiting processes on Q_s) then wakeup one of them; else(기다리는 애가 없으면 물건을 하나 돌려놓고 나가) S<-S+1; 
• 모두 indivisible 연산
  • OS support (보장!)
  • 전체가 한 instruction cycle에 수행 됨
• Semaphore로 해결 가능한 동기화 문제들
  • 상호배제 문제(Mutual exclusion) --> ready queue(대기실)
  • 프로세스 동기화 문제(Process synchronization problem)
    • process들의 실행 순서 맞추기. 프로세스들은 병행적이며, 비동기적으로 수행
  • 생산자-소비자 문제(Producer-consumer problem)
    • Producer-Consumer problem with single buffer
      • Producer - P(consumed);V(produced); // Consumer - P(produced);V(consumed);
    • Producer-Consumer problem with N-buffers
      • circular queue가정 like container belt
      • Producer - P(mutexP); P(nrempty); V(nrfull); V(mutexP); //Consumer - P(mutexC); P(nrfull); V(nrempty); V(mutexC); 
  • Reader-Writer 문제
    • Reader: 데이터에 대해 읽기 연산만 수행(여러 명 가능)
    • Writer: 데이터에 대해 갱신 연산을 수행(한 명만)
    • 데이터 무결성 보장 필요
      • Reader들은 동시에 데이터 접근 가능
      • Writer들(또는 ㄱeader와 write)이 동시 데이터 접근 시, 상호배제(동기화) 필요
    • 해결법
      • reader/ writer에 대한 우선권 부여
        • reader preference solution
        • writer preference solution
  • Dining philosopher problem
  • 기타
  • No busy waiting: 기다려야하는 프로세스는 block(asleep)상태가 됨
  • Semaphore queue에 대한 wake-up 순서는 비결정적: starvation problem
• Eventcount/Sequencer
  • wake-up 순서 정하기 
  • 은행의 번호표와 비슷한 개념
  • Sequencer:
    • 정수형 변수
    • 생성시 0으로 초기화, 감소하지 않음
    • 발생 사건들의 순서 유지
    • ticket() 연산으로만 접근 가능
  • Ticket(S)
    • 현재까지 ticket() 연산이 호출 된 횟수를 반환
    • indivisible operation
  • Eventcount
    • 정수형 변수
    • 생성시 0으로 초기화, 감소하지 않음
    • 특정 사건의 발생 횟수를 기록
    • read(E), advance(E), await(E, v)연산으로만 접근 가능
  • read(E): 현재 Eventcount 값 변환
  • advance(E): E<-E+1, E를 기다리고 있는 프로세스를 깨움(wake-up)
  • await(E,v): V는 정수형 변수, if(E<v)이면 E에 연결된 Q_E에 프로세스 전달(push) 및 CPU scheduler 호출
  • No busy waiting
  • No starvation (FIFO scheduling for Q_E)
  • Semaphore 보다 더 low-level control이 가능

6. Language-Level solution (High-level Mechanism)

• Monitor
  • Object-Oriented concept과 유사, 사용이 쉬움
  • 공유 데이터와 Critical section의 집합
  • Conditional variable: wait(), signal() operation

(1) Monitor의 구조

- Entry queue(진입 큐): 모니터 내의 procedure(function) 수만큼 존재

- Mutual exclusion: 모니터 내에는 항상 하나의 프로세스만 진입 가능

- Information hiding(정보 은폐): 공유 데이터는 모니터 내의 프로세스만 접근 가능

- Condition queue(조건 큐): 모니터 내의 특정 이벤트를 기다리는 프로세스가 대기

- Signaler queue(신호제공자 큐): 모니터에 항상 하나의 신호제공자 큐가 존재, signal() 명령을 실행한 프로세스가 임시 대기