프로세스 동기화 문제

해당 게시글은 kocw에서 제공하는 금오공과대학교 최태영 교수님의 무료 강의를 공부하고 정리하기 위해서 만들어졌습니다.

Deadlock and Starvation

• 세마포어를 사용하면서 발생하는 문제점들이 있다.
• Deadlock
  • 여러 프로세스 여러 세마포어를 동시에 waiting 하는 상황이 발생할 때, 무한정 기다리는 현상을 뜻한다.
  • 세마포어는 한 개로 관리하면 성능 이슈가 발생하기 때문에, 여러 개를 두어 관리한다.
• Starvation(기아현상)
  • 특정 프로세스들이 자원을 사용 못하는 경우
  • 리얼타임 시스템과 같이 프로세스에 우선순위가 있는 경우,
  • 우선순위가 높은 프로세스는 waiting queue에 늦게 도착하더라도 우선적으로 처리가 된다.
  • 이렇게 되면 상대적으로 우선순위가 낮은 프로세스는 실행되지 못하는 상황이 발생한다.
• Priority Inversion

Classical Problems of Synchronization

• Bounded Buffer Problem
  • Producer와 Consumer 사이 바운디드 버퍼(환형 큐)를 통해 메세지를 주고 받고 count 변수를 사용해 메세지의 개수를 관리하려고 했을 때,
  • count 변수에 문제가 발생하면서 제대로 된 값이 나오지 않은 문제
  • 이것을 세마포어로 해결할 수 있다.
  • Producer 에서 현재 빈 공간에 대한 세마포어를 생성하고, 빈 공간이 존재할 때만 동작하도록 wait(empty); 를 걸어둔다.
    • empty는 빈 공간에 대한 세마포어로 초기 값은 N으로 설정한다.
  • 이렇게 되면 기존 바운디드 버퍼가 비어있는지 확인했던 busy waiting 로직은 제거하고 세마포어를 통해 처리할 수 있게 된다.
  • Consumer 에서는 반대로 현재 버퍼가 꽉 찼는지 관리할 full이라는 세마포어를 생성하고 이 것을 기다리는 형태로 사용할 수 있다.
  • 즉, Producer는

wait(empty);
wait(mutex);

Critical Section…

signal(mutex);
signal(full);

- Consumer는

wait(full);
wait(mutex);

Critical Section…

signal(mutex);
signal(empty);

- 위와 같은 형태로 작성하게 된다.
- mutex는 bounded waiting을 해결하기 위한 세마포어이다.

• Readers-Writers Problem
  • 게시판 형태의 웹 서비스에서 글을 읽는 것이 많고 쓰는 것이 적은 상황일 때, 크리티컬 섹션 접근을 해결하기 위한 문제
    • 읽기는 여러명이 읽더라도 문제가 발생하지 않는다.
  • 읽기와 쓰기 두 개의 프로세스로 나눠서 처리하는 것이 좋다.
    • 전통적인 방식으로 크리티컬 섹션을 처리 하기보다 두 개의 프로세스를 나눔으로써 크리티컬 섹션 접근을 해결할 수 있다.
  • 이 것도 마찬가지로 세마포어로 해결할 수 있다.
  • read 프로세스와 write 프로세스 사이에 세마포어를 두고, 크리티컬 섹션 접근을 관리한다.
  • read 프로세스가 실행되지 않는 상황이어야 write 프로세스를 실행시킬수 있기 때문에
  • 현재 write 프로세스가 실행된 개수를 관리할 readcount 변수를 둔다.
  • readcount가 0일 때, write 프로세스를 실행할 수 있게 해준다.
• Dining-Philosophers Problem
  • 식탁 위 다섯명의 철학자가 앉아 있고 접시도 5 개, 젓가락도 5 개가 존재할 때, 철학자들이 젓가락 한 쌍을 가지고 식사를 할 수 있도록 해결하는 문제
    • 젓가락은 각 한 쌍씩 필요하기 때문에 총 10개가 필요하다.
  • 이 문제를 해결하려면 shared variable이 무엇인지 알아야 한다.
  • 젓가락이 shared variable이 되며, 세마포어로 설정해야 한다.
  • 각 프로세스(철학자)는 현재 자기 인덱스와 (인덱스 + 1)의 젓가락(공용 변수)을 가지고와서 크리티컬 섹션을 접근할 수 있다.
    • (index + 1) % 5
    • 다섯명이기 때문에 5로 나눠준다.
  • 해당 해결법의 문제는 deadlock이 발생한다는 점이다.
  • 이 것을 해결하기 위해 젓가락을 사용하기 위한 영역을 크리티컬 섹션으로 묶어서 처리해야 한다.
  • 이러한 방식도 문제가 되는 것이 함수로 작성되기 때문에, 컴파일 단계에서 오류가 검출되지 않는다는 것이다.
    • 순서를 바꿔서 작성하거나,
    • 실수로 wait을 두 번 작성하는 경우 등

Monitors

• 위와 같이 발생하는 문제들을 해결하기 위해 프로그램 언어 디자이너들은 크리티컬 섹션을 사용자가 알고 쓰게 하기 위한 기능을 제공해준다.
• 이 중 하나가 모니터라고 한다.
• 일반적인 class와 비슷하며, monitor 키워드를 통해 작성하고 이 안에는 shared variable이 작성된다.
• 기존 (wait-C.S-signal) 로 이루어진 코드를 함수로 대체한다.
• 이 함수는 모니터 내에 작성되며 사용자 측에서는 이 함수를 호출해서 사용한다.
• 모니터 내에 작성된 함수는 동일한 크리티컬 섹션을 접근하는 것이기 때문에,
• 반드시 하나의 함수만 실행될 수 있다.(동시 실행 불가)
• 따라서 하나의 함수가 호출되면 하나는 블락이 된다.
• 모니터를 쓰더라도 데드락을 해결하기가 쉽지가 않다.
  • 항상 하나의 함수만 실행되기 때문에 데드락이 잘 생기진 않는다.
• 모니터를 사용해도 기다리는 코드가 존재하면 문제가 발생한다.
  • 모니터 함수 내에서 기다리는 코드가 존재한다면, wait을 쓸 수 밖에 없다.
  • 따라서 모니터로 wait과 signal을 분리했지만, 대기 로직 때문에 어쩔수 없이 쓰는 쪽도 wait과 signal을 써야 한다.
• 이러한 블락을 처리하기 위해 condition variable을 모니터 내에서 생성하고 관리하게 된다.
  • 메세지 관리 같은 경우 메세지 큐의 상태를 관리할 full, empty 같은 조건 변수들이 해당된다.
• 모니터의 블락은 세마포어와 다르게 어떤 값에 종속된 형태로 블락이 되는게 아니라 그냥 블락이 된다.
• 누군가 condition variable을 signal을 해주어야 블락이 해제된다.
  • 아무도 wait 하지 않는 상황에서 signal을 하면 의미 없이 지나간다.

Condition Variables Choices

• 프로세스에서 사용하는 모니터 함수 내에서 condition variable을 동시에 사용하게 되는 경우 크리티컬 섹션이 깨지게 되는 문제가 발생한다.
  • 모니터 함수 자체는 크리티컬 섹션으로 정의된다.
  • 그러나 함수 실행중 블락이 발생하고, 다른 프로세스에서 다른 모니터 함수를 실행하여 signal을 해주게 될 경우, 결국 동시에 크리티컬 섹션에 접근하는 상황이 되는 것이다.
• 이 것을 해결하기 위해 두 가지 옵션을 사용할 수 있다.
• 첫 번째 옵션은, wait을 좀 더 기다린다.
  • signal을 해주어도 wait이 바로 풀리는 것이 아니라 함수 종료 이후에 wait을 풀어주는 것이다.
• 두 번째 옵션은, signal을 해준 프로세스가 잠시 블락이 되는 것이다.
  • signal 이후 블락이 해제된 프로세를 실행시켜주고 해당 프로세스가 다 실행된 이후 다시 signal을 해준 프로세스를 마저 실행시켜 준다.
• 세 번재 옵션도 있긴 한데, signal 함수를 매번 맨 끝에 놓도록 권유하는 것이다.
  • 마지막에 signal을 호출하는 것이기 때문에 사실상 wait가 풀려도 signal 해준 프로세스는 끝난 것이기 때문이다.

Monitor Solution to Dining Philosophers

• 5명의 철학자 문제를 풀기 위해 철학자들이 식탁에 들어서기 전 필요한 작업을 해준다.
  • 식탁을 식당안에 두고 출입문을 통해 들어갈지 말지 제한한다고 생각 해본다.
• 한 명의 철학자만 현재 식탁에 앉을지 결정할 수 있으며, 식탁에 앉을 철학자는 이름표를 작성하고 들어간다.
• 철학자는 입장 전 이 이름표를 가지고 본인과 인접한 철학자가 이미 들어가 있으면 기다린다.
  • 젓가락 사용을 원활하게 하기 위함이다.
  • 인접한 철학자가 없다면 옆에 젓가락을 사용하여 한 쌍의 젓가락을 사용할 수 있게 된다.
  • 그렇게 함으로써 데드락 문제를 해결한다.
• 철학자는 기다리기 시작하면 외부에서 부를 때까지 계속 대기할 수 밖에 없다.
• 식사를 마친 철학자는 외부로 나가면서 이름표를 확인하고 본인과 인접한 철학자의 이름표를 넣어두고, 이름표가 넣어진 철학자는 식사를 하러 들어간다.
• 위와 같은 시나리오를 모니터로 구현할 수 있다.