프로세스 동기화

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

Process Synchronization

• 여러 개의 프로세스를 실행 하면서 자원 들도 무작위로 가져가서 쓰게 되는데 이를 관리하기 위해 운영체제에서는 프로세스 동기화 기능을 제공해준다.
• Shared memory, Shared Variable 환경에서 프로세스 또는 스레드가 동시에 자원접근 하는 상황에서 사용된다.

Race Condition

• Producer와 Consumer 사이 count값을 증가할 때, 어셈블리어를 통해 register를 관리하게 되는데, 이 때 context switching이 발생하게 된다.
• 해당 상황에서 서로 다른 프로세스가 count 변수에 접근하여 조작할 일이 생기는데 이런 상황을 Race Condition이라고 한다.
  • 둘 이상의 프로세스가 하나의 자원에 접근하는 것

Ciritical Section Problem

• 임계영역 문제라고 한다.
• Race Condition을 해결하기 위한 문제이다.
• 한 프로세스가 Critical Section(파일 쓰기, 전역 변수 값 변경, 테이블 업데이트 등)에 접근해 있을 때, 다른 프로세스는 Critical Section에 들어오면 안되게 코드를 짜는 것이다.
• 프로세스가 Critical Section에 진입 전, 현재 사용중인 프로세스가 있는지 체크하는 과정을 거쳐야 하고,
• 현재 Critical Section을 사용중인 프로세스는 종료 후 다른 프로세스가 진입할 수 있도록 체크 값을 변경해 주어야 한다.
  • 어플리케이션 개발자는 이 체크 값을 변경해 주는 것만 해주면 되고,
  • 운영체제 개발자는 이것을 변경할 수 있는 인터페이스를 제공해야 한다.
• 이러한 문제를 해결하기 위한 알고리즘은 세 가지를 만족해야 한다.
  • 1. Mutual Exclusion(상호배제)
    • 한 프로세스가 critical section에 들어오면 다른 프로세스는 들어오지 말아야 한다.
    • 제일 중요한 조건이다.
  • 2. Progress
    • 한 프로세스가 critical section에 진입하려 할 때, critical section이 비어 있다면 바로 진입 가능해야 한다.
  • 3. Bounded Waiting
    • fairness(공평함)
    • 한 프로세스가 critical section을 사용하면 반드시 다른 프로세스가 critical section을 사용해야 한다.
    • 번갈아 가면서 사용할 수 있어야 한다.
    • 이 것은 프로세스가 수행되는 것에 있어서 먼저 들어온 프로세스만 실행되지 않게 하기 위함이다.
    • 다음 두 가지 조건은 만족한다고 가정한다.
      • 프로세스의 속도는 0이 아니다(멈춰있지 않다).
        • 반드시 프로세스는 진행 중인 상태다.
      • 두 프로세스 간 연관성은 없다.
• Critical section 문제를 해결하기 위해 다음과 같은 단계로 솔루션을 살펴보겠다.
  • 1. Software
    • 엄밀히 말하면 소프트웨어 만으로는 해결되지 않는다.
    • 하지만 먼저 소프트웨어를 봐야 해당 문제를 살펴볼 수 있기 때문에 솔루션을 살펴본다.
  • 2. Hardware
    • 해당 문제를 해결하기 위해 제공해주는 명령어를 어떻게 활용할지 살펴본다.
  • 3. Operating System
    • 하드웨어를 통해 문제를 해결하면 낭비가 발생하니 운영체제 레벨에서 어떻게 효율적으로 해결할 수 있는지 살펴본다.

Peterson’s Solution(Software Solution)

• 소프트웨어로 처리 하려면 진입 전과 후에 소프트웨어적인 처리를 해주어야 하는데, 어떤 메모리의 내용을 항상 레지스트리에 저장하고 관리해야 한다.
  • 이러한 작업이 한단계로 끝나지 않기 때문에, 중간에 섞이면 의도치 않은 Race Condition이 또 발생하게 된다.
  • 소프트웨어 방식의 해결방법은 위와 같은 어려움이 있다.
• critical section의 진입여부를 관리할 값 이외에 또 다른 지역 변수를 통해 진입여부 값을 관리하게 된다.
  • 1. flag
    • 각 프로세스가 critical section를 진입하기 위한 의사 표현 값이다.
    • 진입하고 싶다면 true로 표시하고, 그렇지 않다면 false로 의사 표현을 한다.
    • 프로세스마다 존재한다.
  • 2. turn
    • 현재 critical section을 이용할 수 있는 순서를 관리하기 위한 변수이다.
• flag 변수를 통해 Mutual Exclution과 Progress, Bounded Waiting 조건을 해결할 수 있다.
• flag 변수를 변경하기 위해 여러 단계를 거치는데, 이 단계 수행 동안 Race Condition 이 발생하면 너무 복잡해 지므로 소프트웨어 솔루션은 사용할 수 없다.

Synchronization Hardware(Hardware Solution)

• 의외로 cpu가 하나만 존재하면 아주 쉽게 critical section 문제를 해결할 수 있다.
• critical section 문제가 발생하는 이유는 프로세스가 레지스터를 변경하는 순서가 섞였기 때문이다.
  • 즉 타이머 인터럽트가 발생했기 때문이다.
• 그렇기 때문에 해당 문제를 해결하기 위해 critical section에 진입시 인터럽트가 발생하지 않도록 막으면 된다.
• 문제는 cpu가 두 개 이상인 경우 인터럽트를 막더라도 cpu 각자 수행 하기 때문에 자원 경쟁을 피할 수 없다.
• 듀얼 코드 이상의 cpu는 하드웨어적으로 지원이 되어야 Mutual Exclusion을 해결할 수 있다.
• 하드웨어에서 지원하는 것을 Atomic Operation이라고 한다.
  • 기본적으로 어셈블리 언어는 각자 Atomic Operation으로 구성된다.
  • 즉, 인터럽트가 되지 않는다.
• 이 것을 가능하게 하기 위해서는 두가지 방법이 있다.
  • 1. 메모리의 값을 테스트하고 특정한 값으로 설정하는 것
    • lock을 통해 mutual Exclusion과 progress를 만족시킬 수 있다.
  • 2. 메모리의 값을 변경하는 것
• Mutex Locks
  • 중간에 Lock을 둠으로써 critical section 문제를 해결했는데, 이것을 Mutex Locks라고 한다.
  • 진입시 Lock을 거는 것을 acquire lock이라고 하고 푸는 것을 release lock이라고 한다.
  • 이들 lock을 수행하는 것은 함수가 아니라 하나의 명령어로 수행되어야 정상적으로 lock 을 시킬 수가 있다.
    • 함수로 정의하면 중간에 끼어들 여지가 생긴다.
• 이런 식으로 하드웨어 솔루션을 통해 critical section 문제를 해결할 수 있는데, 운영체제 솔루션이 필요한 이유가 있다.
  • bussy wait을 위해 하나의 프로세스가 cpu 시간을 기다리는데에만 다 쓸 수 있기 때문이다.

Semaphore(Operating System Solution)

• 크리티컬 섹션을 구현하기 위해 사용자가 복잡한 로직을 작성하지 않고 함수 하나로 처리할 수 있도록 운영체제는 제공하고 있다.
• 이 함수 내부에서는 세마포어라는 공용 변수를 가지고 기존 lock 대신 사용하고 있다.
  • entry 구간에서 wait(sem);을 하여 세마포어를 기다리고,
  • 끝나는 구간에서 signal(sem);을 하여 세마포어를 처리한다.
• 세마포어는 하나의 integer 변수를 갖는다.
  • 이 변수는 처음에 1로 초기화 된다.
  • wait 함수 내에서 해당 변수가 0 보다 작은지 확인하고 루프를 실행한다.
    • 변수 값이 0 이하인 경우 무한 루프를 돈다.
    • 변수 값이 1 이상인 경우 루프를 탈출하고, 1 감소 시킨다.
  • signal 함수 내에서는 해당 변수의 값을 1 증가 시킨다.
  • 실상은 더 복잡한 로직으로 구현되어 있다.
• 그러나 위와 같은 방식은 bounded waiting이 만족되지 않는다.
  • 작업이 끝난 프로세스가 연달아서 critical section에 접근할 수 있기 때문이다.
  • 실제로 세마포어는 훨씬 복잡하게 동작하며 이러한 문제를 해결하고 있다.
• 이러한 세마포어는 counting semaphore라고 한다.
  • 이전에 배운 lock도 세마포어의 일종이며 binary semaphore 라고 한다.

Semaphore Implementation

• 운영체제에서 busy waiting(루프를 돌면서 블락 시키는 것)을 없애기 위해서 세마포어를 제공한다.
• busy waiting은 어떤 조건이 만족할 때가지 cpu를 점유하면서 아무 동작도 하지 않는 것이다.
• 이것을 없애기 위해 waiting queue에 집어넣고 조건이 만족되면 ready queue로 옮기는 형식으로 사용한다.
• 세마포어를 구현하기 위해서 커널에서 명령어를 제공한다.
  • block
    • 블락이 된 프로세스를 cpu에서 꺼내서 waiting queue에 넣는 명령어
    • 이렇게 꺼내진 프로세스 정보(PCB)는 세마포어 내에 리스트로 기록된다.
  • wakeup
    • waiting queue에서 조건이 만족된 프로세스를 꺼내오는 명령어
    • PCB를 Ready queue로 옮긴다.
• 이러한 명령어가 수행 가능하도록 세마포어 내부에 연결 리스트를 구현해야 한다.