Shared Data Problem

• Multi-Thread를 사용하게 되면 전역변수와 같은 shared data를 동시에 접근하는 일이 생길 수 있다. 그 과정에서 shared data의 값을 동시에 수정하게 되면 예상치 못한 문제점이 일어날 수 있다.
  • 이러한 상황은 data inconsistent 문제를 야기함
  • 해결방법 : 어떤 한 프로세스가 Critical-Section에 접근하면 다른 프로세스를 Critical-Section에 접근을 못하게 함 ⇒ mutex locks, semaphore
    • Mutual Exclusion (Mutex : 상호배제) : single core == binary semaphore
    • Semaphore : multi core == counting semaphore

Semaphore 구조 (busy waiting)

• 세마포어 상수 S를 1로 설정하고 wait()함수와 signal()함수를 통해 접근을 조절함
  • wait(S)함수 : S가 0이하일 때 while문에 프로세스를 가두고 S가 1이상이 되면 while문을 빠져나와 S를 1감소시키는 함수
  • signal(S)함수 : S를 1증가시키는 함수
  • 순서는 항상 wait함수 호출 후 → critical section에 접근 → signal함수 호출
• S가 1인 상태에서 A프로세스가 critical-section에 접근하기 위해 wait()함수를 호출하면 S가 1이상이므로 while문에 가둬지지 않고 S를 1감소시키고 wait()함수를 빠져나와 critical-section에 접근 ⇒ 그 과정에서 S는 0이되므로 B프로세스가 critical-section에 접근하기 위해 wait()함수를 만나면 while문에 갇히게 됨 ⇒ A프로세스가 signal()함수를 통해 접근을 마치면 S는 다시 1이되어 B프로세스가 while문을 빠져나와 critical-section에 접근 가능
• 이러한 구조는 busy wating을 발생시킴 (while문 계속 실행) ⇒ 해결방법 : counting semaphore

Counting Semaphore (=no busy waiting)

• 기존의 busy waiting을 개선시키고자 wait함수 내에 block()함수를 넣고 signal함수에 wakeup()함수를 넣음
• waiting queue를 이용해 여러개의 프로세스 접근을 제어할수 있음
• 문제점 : Deadlock과 Starvation에 빠질 수 있음
  • Deadlock : 2개 혹은 그 이상의 프로세스가 서로 의존적으로 wait함수를 호출하는 경우
    • 예를 들어 P0 프로세스가 wait(S)와 wait(Q)를 실행하고 P1프로세스가 wait(Q)와 wait(S)를 실행하는 경우 서로가 서로를 풀어줘야 하지만 둘다 block에 걸린상황으로 교착상태에 빠지게 됨 ⇒ Deadlock
  • Starvation : LIFO(last in, first-out)구조의 스택같은 우선순위 세마포어에서 많이 발생, 우선순위가 낮은 프로세스는 계속 block이 될 수 있음

Deadlock의 4가지 조건

• Mutual exclusion : only one process at a time can use a resource
• Hold and wait : a process holding at least one resource is waiting to acquire additional resources held by other processes.
• No preeption
• Circular wait
• 위의 4가지 조건을 전부 만족시키면 Deadlock이 발생