기타

운영체제에서의 동기화

citron031 2022. 12. 1. 22:41

프로세스는 여러개가 동시에 실행될 수 있고, I/O 요청시 CPU는 idle하지 않고 다른 프로세스의 일을 처리한다.

동기화를 통해서 여러개의 프로세스가 CPU를 공유하면서 데이터를 수정한다.

이때 수행중인 퀀텀(quantum)이 끝나면, 수정 도중에 나가야 한다.

이후 다른 프로세스가 공유 데이터에 접근하여 데이터를 사용하면, 수정중이었던 불안정한 데이터를 사용하게 되고 그 결과 예상치 못한 데이터가 산출된다.
🧨 따라서 프로세스의 최종 결과가 잘못된다.
🧨 데이터의 비일관성을 해소하기 위해서, 순차적으로 수행하는 매커니즘이 필요하다.

Race Condition

  • 공유 영역(critical-section)에서 프로세스들의 사이에 제어가 없어 예측하지 못한 값이 발생하는 상태

Critical Serction Problem

  • 각 프로세스들은 critical section segment의 코드를 가진다.
  • 하나의 프로세스가 공유 영역에 들어가면, 다른 프로세스는 공유 영역에 들어갈 수 없다. (한 번에 하나의 프로세스)
  • 문제의 해결을 위해서는 각 프로세스는 반드시 공유 영역에 진입하기 위해서 권한을 요청해야 하고, 공유 영역에 프로세스가 있다면(Lock), 그 프로세스가 공유 영역에서 나온 후에야 진입할 수 있다.

Critical Serction Problem에 대한 해결책

⚽ Mutual Exclusion

한번에 하나의 프로세스만 들어갈 수 있게 프로세스가 들어오면 공유 영역을 Lock한다.

⚾ Bounded Waiting

공유 영역 바깥에서 공유 데이터 사용을 위해 기다리는 프로세스는 영원히 기다리면 안된다.

각 프로세스가 0이 아닌 속도로 실행될 때, 즉 공유 영역에 진입하려는 프로세스와 공유 영역에서 수행중인 프로세스들은 모두 실행중이어야 한다.

공유 영역에 들어가는 프로세스에 대해서는 어떠한 전제조건도 없어야 한다. 할당되는 CPU 속도도 차별이 있으면 안된다.

🏀 Progress

공유 영역이 비어있으면, 공유 영역 바깥에서 기다리는 대기중인 프로세스는 아무런 이유없이 못들어가면 안된다.

즉, 공유 영역이 비어있으면 대기중인 프로세스는 즉시 공유 영역에 진입해야 한다.

  • Preemptive : kernel 모드에서 다른 프로세스에게 CPU를 강제로 내준다.
    이때는 일관된 데이터를 사용하지 못할 수 있기에 동기화가 필요하다.
  • Non-Preemptive : 공유 영역에서 실행중인 프로세스가 스스로 공유 영역에서 나올때까지 CPU를 다른 프로세스에 빼앗기지 않는다.
    수행속도가 느릴 수 있다.

Petersion's Solution

  • 소프트웨어로 구성된 해결책이다.
  • 하드웨어로 된 해결책보다는 느리다.
  • while문을 사용하여 기다리는 중이라면, 진행을 하지 못하고 루프에 갇힌다. (busy waiting)
  • 따라서 overhead가 발생하는 방법이다.
  • flag[i]를 사용하여 프로세스 i가 공유 영역에 들어가려고 하면 true, 아니면 flase로 표기한다.
  • 한 번에 하나의 프로세스만이 공유 영역에 들어갈 수 있다.

🎈 하드웨어로 동기화하면 cs(critical-section)이 사용중이라면, interrupt를 disable해야 한다.
왜냐하면, 만약 cs에서 오류가 발생하면 빠져나올 수 없기에 위험하다. (interrupt를 enable할 수 없다.)

  • 다만, CUP가 여러개인 멀티 프로세스에서 다른 CPU의 프로세스는 disable interrupt의 영향을 받지 않기에 여전히 cs에 진입할 수 있다.
    따라서 모든 CPU에게 이 사실을 알려야 하고 이 과정에서 overhead가 발생한다.
  • interrupt가 없는 상태를 Atomic으로 표현한다. (All or Noting)

Mutex Locks

Petersion's Solution보다 빠르다.

low level, 즉 하드웨어에 좀 더 가깝기 때문에 더 빠르다.

boolean 변수를 이용해서 cs를 보호하고 release한다.

이때, boolean 변수는 true로 시작하고 항상 atomic하다.
(수행중 다른 프로세스의 인터럽트를 걸 수 없다)
하지만, 여전히 busy waiting이 있고(while loop) check, wait를 하며 시간낭비가 발생한다. (overhead)

🎩 context switching이 필요하지 않아 잠깐 Lock을 유지할 경우 사용한다.
context switching가 굉장히 짧은 경우 state wait보다 busy waiting이 더 빠르기 때문이다. (여전히 running 상태)
하지만, context switching가 더 길면 CPU 퀀텀이 낭비되고 block한 후에 다른 프로세스를 구동하는 것이 더 효율적이다.
그리고 이것을 Semaphore를 통해 구현한다.

Semaphore

  • busy waiting이 없다. CPU는 자발적으로 포기되고 waiting state로 상태가 전환된다.
  • wait와 signal의 두 개의 atomic 함수만 존재한다.
  • semaphore는 임의의 정수이거나 binary일 수 있다.
  • 반드시 wait와 signal은 동시에 실행될 수 없다.
  • 따라서 이 둘은 cs에 구현되는데 이러한 경우 busy waiting이 발생할 수 있다. (overhead)
    • busy waiting을 없애기 위해서 각 semaphore에 연결된 queue를 사용한다. (integer와 next list의 pointer를 가짐)
  • 큐가 기다리게 하는 block(CPU를 자발적으로 내줌)과 waiting 큐에서 프로세스를 하나 제거해 ready 큐로 보내는 wakeup이 있다.
    (ready 큐의 프로세스는 CPU를 할당받으면 cs를 이용 가능하다.)
  • semaphore에서 deadlock과 starvation이 발생할 수 있다.

Deadlock

  • 결코 일어나지 않을 이벤트를 무한히 기다려 결국 시스템이 다운된다.

Starvation

  • 낮은 우선순위의 프로세스가 계속해서 높은 우선순위를 갖는 프로세스의 유입때문에 오랜 시간 기다렸지만, 실행되지 못하는 상태를 의미한다.

🤿 위의 두 문제를 해결하기 위해서 우선순위를 반전시키는 해결책이 있을 수 있다. 임시적으로 우선순위를 높여 프로세스가 실행될 수 있도록 한다.

Monitors

  • object-oriented 동기화이다.
  • 세마포어의 단점을 보완한 매커니즘이다.
  • 모니터 안에 구현된 변수는 모니터 안에서 정의된 함수에서만 사용이 가능하며, 한번에 한 프로세스만 이 함수에 출입가능하다.
  • 하지만 모니터가 완벽한 동기화를 제공하는가? 그것은 아니다.
    따라서, wait와 siganl이 필요할 수 있다.
  • 따라서 모니터는 condition variables이나 세마포어를 함께 사용하기도 한다.
저작자표시