Process Synchronization - hochan222/Everything-in-JavaScript GitHub Wiki

바로가기
바로가기
바로가기
바로가기

프로세스 동기화(Concurrency Control) 및 Deadlock

Race Condition

OS에서 Race Condition은 언제 발생하는가?

• 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황

• kernel 수행 중 인터럽트 발생 시

• Process가 system call을 하여 kernel mode로 수행중인데 context switch가 일어나는 경우

• Multiprocessor에서 shared memory내의 kernel data

The Critical-Section Problem

• n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment에는 공유데이터를 접근하는 코드인 critical section이 존재
• 공유데이터에 접근하는 코드를 Critical Section이라고 한다.

프로그램적 해결법의 충족 조건

• Peterson's Algorithm

• Busy Waiting(=spin lock)

Synchromization Hardware

• Test_and_set(a)

Semaphores

• integer variable
• 아래의 두가지 atomic 연산에 의해서만 접근 가능
• p 연산은 세마포어 변수를 획득하는 과정이고, v 연산은 다 사용하고나서 반납하는 과정이다.

busy-wait vs block / wake up

Two type of semaphores

• Counting semaphore
  • 도메인이 0 이상인 임의의 정수값
  • 주로 resource counting에 사용
• Binary semaphore(=mutex)
  • 0 또는 1 값만 가질 수 있는 semaphore
  • 주로 mutual exclusion (lock/unlock)에 사용

Deadlock and Starvation

• Deadlock
  • 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
• Starvation
  • indefinite blocking 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

Classical Problems of Synchronization

• Bounded-Buffer Problem (Producer-Consumer Problem)
• Readers and Writers Problem
• Dining-Philosophers Problem

Bounded-Buffer Problem (Producer-Consumer Problem)

Readers and Writers Problem

• 한 process가 DB에 write중일 때 다른 process가 접근하면 안됨
• read는 동시에 여럿이 해도됨
• solution
  • Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다
  • Writer는 대기중인 Reader가 하나도 없을 때 DB접근이 허용된다
  • 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
  • Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.

Reader가 계속 들어오면 Starvation 발생가능.. Writer가 계속 못함..

Dining-Philosophers Problem

• Deadlock 가능성이있다.

• 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우

• 해결방안

  • 4명의 철학자만이 테이블에 동시에 앉을 수 있도록한다
  • 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다
  • 비대칭
    • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록

Monitor

• 모니터 내에서는 한번에 하나의 프로세스만이 활동가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해