Happy Day:)

Math, Computer Engineering

4 분 소요

4. 동기화 하드웨어(Synchronization Hardware)

lock을 사용하는 임계구역 문제 해결책

image

임계구역을 lock으로 보호하여, 경쟁조건을 방지함

Lock의 구현

  • 소프트웨어 알고리즘 - 복잡하고 비효율적
  • 하드웨어 지원
    • 인터럽트 금지(disable)
    • Atomic 명령어

인터럽트 금지(Interrupt Disable)

임계구역 실행 동안 인터럽트를 방지하여 선점을 허용하지 않음

  • 현재 수행중인 코드가 선점되지 않고 계속 수행함

단일 프로세서 시스템에서는 임계구역 문제 해결 가능

image

멀티 프로세서 시스템에서는 적용 불가능

  • 한 CPU의 인터럽트를 금지시켜도, 다른 CPU는 여전히 임계구역에 진입할 수 있음.
  • 모든 CPU의 임계구역 진입을 방지하기 위해서, 모든 CPU의 인터럽트를 금지시키는 것은 시간이 소요되므로 비효율적임.

시스템 클록(시계)에 대한 영향

시스템 클록이 인터럽트에 의해서 갱신되는 시스템에서, 인터럽트 금지는 시간에 영향을 줄 수 있음

원자적 명령어(Atomic Instruction)

연속되는 여러 개 동작(read-modify-write 동작)을 원자적으로(인터럽트 되지 않고/분리되지 않고) 수행하는 기계어 명령어

Atomic 명령어의 예

Test and Set (TAS) instruction

word 내용을 검사(test)하고 변경(set)하는 동작을 원자적으로 수행

Swap instruction

두 word의 내용의 교환(swap)을 원자적으로 수행

Lock 변수 사용하기 – Atomic 명령어 사용

  • 두 상태: 0 (unlock, open, 사용 중이 아님), 1 (lock, close, 사용 중)
  • atomic 명령어를 사용하여 lock 변수를 조작함

TAS 또는 SWAP 명령어를 사용한 lock 변수의 조작

Test and Set (TAS) instruction SWAP instruction
image image

5. 뮤텍스 락(Mutex Locks)

뮤텍스 락(Mutex Locks)은 동시에 공유 리소스에 접근할 수 있는 스레드의 수를 제한하여 상호배제를 구현하는 기술로 보통 상호배제를 위한 가장 기본적인 기법 중 하나이다.

  • 두 함수 제공
    • acquire() – lock 획득
    • release() – lock 반환

임계 구역 문제에 대한 하드웨어 기반 해결안

  • 응용 프로그래머에게는 복잡하며 일반적으로 직접 사용할 수 없음
  • 해결방법 – 운영체제에서 응용프로그래머에게 이를 위한 소프트웨어 도구를 제공 → Mutex Lock

스핀락(Spinlock) : busy-waiting mutex lock

루프를 반복 실행하면서 lock 획득을 기다림 CPU cycle이 낭비됨 → 단일 프로세서 시스템에서 특히 문제임 멀티프로세서 시스템에서 짧은 시간 내에 lock 획득이 예상되면 스핀락이 유용함 - context switching이 없음

Busy-waiting이 없는 Mutex Lock

Busy-waiting이 없는 Test and Set을 사용한 상호 배제

lock을 획득하지 못하면 프로세스는 lock을 기다리는 대기상태로 전환 하고 CPU를 내어 놓음

6. 세마포(Semaphores)

Mutex Lock보다 더 정교하고 강력한 프로세스 동기화 도구

세마포 S

  • 특별한 표준 동기화 연산을 통해서만 접근 할 수 있는 정수 변수.
  • 세마포 값은 대개 사용 가능한 특정 자원의 수를 나타냄

Semaphore 연산

  • 초기화 연산 – semaphore S 값 초기화
  • 두 개의 원자적(atomic) 연산 (by Dijkstra)
    • P operation (Proberen = test) → wait(S), acquire(S)
    • V operation (Verhogen = increment) → signal(S), release(S)

image

Semaphore 용도

  • 상호 배제(Mutual exclusion) → 이진 세마포(binary semaphore)
  • 유한 개수의 자원 접근, 한정된 concurrency → counting semaphore
  • 프로세스 동기화: signaling

Binary semaphore  상호배제 구현 (mutex lock과 유사)

  • semaphore 값: 0 or 1 (1로 초기화)
  • 임계구역 접근 제어에 사용

카운팅 세마포(Counting Semaphore)

Counting semaphore  한정된 concurrency, 유한 개수 자원 접근

  • semaphore 값: 가용 자원 개수를 의미(최대 가용 자원 개수로 초기화)
  • 유한 개수의 자원의 접근 제어에 사용

image

일반적인 동기화

  • (예) 프로세스 P1의 A 부분 실행 후에 프로세스 P2의 B 부분이 실행되어야 함
  • Code:

image

Semaphore 구현

바쁜 대기(Busy waiting) Semaphore

spinlock과 유사하게 구현

바쁜 대기 없는(No Busy waiting) Semaphore

  • 프로세스의 block-wakeup 방법 이용
  • semaphore를 획득할 수 없을 때 semaphore 대기 큐에 자기 프로세스를 추가하고 자신을 block 시킴
  • semaphore를 사용 가능하게 되면, semaphore 대기 큐에서 한 프로세스를 꺼내어 ready queue로 이동하여, 대기 중인 하나의 프로세스를 wakeup시킴

No busy-waiting 세마포 구현

Sempahore S

  • value – 세마포 값
  • list – 이 세마포를 대기하는 프로세스 리스트 (세마포 대기 큐)

Sempahore 연산

image

  • 세마포 값을 먼저 감소 → 음수 가능
  • 음수의 크기는 세마포를 대기하는 프로세스들의 개수임 (세마포 검사와 감소의 순서가 busy-waiting 방법과 반대)
  • 두 프로세스가 같은 세마포에 대해 P 또는 S 연산이 중첩되어 실행되지 않도록 해야 함. (atomic 실행)

교착상태(Deadlock)와 기아(Starvation)

Semaphore를 사용한 코드는 교착상태와 기아가 발생할 수 있음

교착상태

두 개 이상의 프로세스들이 그들 중 한 프로세스에 의해서만 발생될 수 있는 사건을 무한정 기다리고 있어서, 진행이 되지 않는 상황

기아 – 무한 봉쇄(indefinite blocking)

</span>

  • 일부 프로세스가 무한정 대기할 수 있는 상황
  • (예) 세마포 대기 리스트가 LIFO 순서로 되어 있으면 리스트 앞쪽에 있는 프로 세스는 제거되지 못할 수 있음 (세마포가 빈번히 사용되는 경우)

7. 고전적인 동기화 문제

lock을 사용하는 임계구역 문제 해결책

유한 버퍼 문제(Bounded-Buffer Problem) Readers와 Writers 문제 식사하는 철학자 문제(Dining-Philosophers Problem)
image image image
두 프로세스가 하나의 자료 공유 여러 프로세스가 하나의 자료 공유
- 일부는 읽기만 수행
-일부는 갱신 수행		 여러 프로세스가 여러 자료 공유

Dining-Philosophers Problem

image

  • 여러 프로세스들에게 여러 자원을 할당할 필요가 있는 병행 제어(concurrency control) 문제를 단순하게 나타낸 예임.
  • 철학자 → 프로세스(process), 젓가락 → 자원(resource)

8. 모니터(Monitors)

Semaphore 사용의 문제점

프로그래머가 잘못 사용하면 다양한 유형의 오류 발생 가능

잘못된 Semaphore 사용 예

  • P와 V 연산의 순서를 반대로 사용
  • V대신에 P를 사용
  • P 또는 V를 누락

이러한 실수가 아니어도 동작의 정확성을 증명하기 어렵고 식사하는 철학자 문제와 같이 교착상태를 유발할 수 있다.

모니터

  • 병행 프로그래밍(Concurrent Programming)을 위한 지원
    • 병행 프로그래밍이 순차 프로그래밍보다 어려움
    • 세마포와 같은 기능을 직접 사용하지 않고 병행 프로그래밍을 위해 고수준의 상호배제를 지원하는 기능이 개발됨
    • 잘못 사용할 위험성을 줄임
  • 모니터(Monitor)
    • 프로세스 동기화를 위한 편리하고, 효율적이고, 안전한 방법을 제공하는 고수준의 동기화 추상화 데이터 형(ADT) – data와 procedure를 포함
    • monitor에서 정의된 procedure만에 monitor 내의 local data를 접근가능
    • monitor의 procedure들은 한 번에 하나의 프로세스만 진입하여 실행할 수 있음 → 상호배제 보장

조건 변수(Condition Variables)

  • Condition: 모니터에서 동기화에 사용되는 특별한 자료형 condition x, y;
  • Condition 변수를 사용하는 연산 - wait, signal wait(), signal()
    • wait(x) 를 호출한 연산은 프로세스는 다른 프로세스가 signal(x)을 호출할 때까지 일시 중지(suspend)됨
    • signal(x) 연산은 정확히 하나의 프로세스만 재개시킴. 일시 중지된 프로세스가 없으면, 아무런 영향이 없음

모니터 내에서의 동기화

조건변수에 대한 두 연산(wait, signal)을 사용하여 수행함

태그: ,

카테고리:

업데이트:

댓글남기기

참고