10. Process Synchronization

1. 데이터의 접근

• 데이터는 보통 한 공간에서 저장과 연산이 이루어지지 않고 S(Storage)-Box와 E(Execution)-Box로 나뉘어 저장과 연산을 하는 공간이 구분되어 있다.
• E-box와 S-box의 대응 관계의 예시
  • CPU-Memory : multiprocessor system에서 process synchronization 문제가 발생할 수 있다.
  • 컴퓨터내부-디스크
  • 프로세스-그 프로세스의 주소 공간 : 공유메모리를 사용하는 프로세스들 사이에서, 또는 커널 내부 데이터를 접근하는 루틴들 사이에서 process synchronization 문제가 발생할 수 있다.
• 이로 인해 만약 S-box를 공유하는 E-box가 여럿 있는 경우 Race Condition의 가능성이 있다.
• Race Condition
  • 여러 프로세스들이 동시에 공유 데이터에 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 의해 결정된다.

2. OS에서 race condition이 발생하는 경우

• 커널 모드 실행 중에 인터럽트가 발생해 인터럽트 처리 루틴이 수행되는 경우
  • 양쪽 다 커널 코드이기 때문에 커널 주소 공간을 공유하게 된다.
  • 이를 해결하기 위해 커널 모드 실행 중에 인터럽트가 발생하는 경우 해당 인터럽트 실행을 현재 실행 중인 커널 모드의 프로그램을 끝낼 때까지 지연시킨다.
• 프로세스가 시스템 콜을 하여 커널 모드로 수행 중인데 context switch가 일어나는 경우
  • 한 프로세스가 시스템 콜을 해 커널 모드로 수행 중일 때 할당 시간이 끝나거나, 다른 프로세스가 CPU를 할당받아야 하는 경우 커널 모드가 끝나기 전에 다른 프로세스가 CPU를 할당받는다. 이때 다른 프로세스도 커널 모드를 수행 중일 때 할당 시간이 끝나는 경우 race condition이 발생할 수 있다.
  • 이를 해결하기 위해 커널 모드에서 수행 중일 때는 CPU를 preempt하지 않고, 사용자 모드로 돌아간 뒤에 preempt한다.
• Multiprocessor에서 공유 메모리 내의 커널 데이터
  • 작업 주체가 여럿이 있기 때문에 발생하는 문제이다.
  • 이를 해결하기 위해서는 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하거나, 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 한다.

3. Process Synchronization(Concurrency Control)

• 공유 데이터의 동시 접근으로 인해 데이터의 불일치 문제가 발생할 수 있다.
• 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 매커니즘이 필요하다.
• 즉, race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 한다.

4. Critical-Section Problem

• Critical Section(임계 구역) : 공유 데이터를 동시에 사용하기를 원하는 각 프로세스의 공유 데이터를 접근하는 코드
• 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
• 이 문제를 해결하기 위해 충족해야 할 조건
  • mutual exclusion : 한 프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 critical section에 들어가면 안 된다.
  • progress : 어떤 프로세스도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
  • bounded waiting : 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
• 해결 알고리즘
  • 소프트웨어를 이용한 해결 방법(Peterson's algorithm)
    • 공유 변수인 flag와 turn을 적절히 활용해 구현하는 방법이다.
    • flag는 배열로, 배열 내 각 원소는 false로 초기화하고, turn은 int 변수이다.
    • i번째 프로세스에 대해 critical section에 들어가기 전 flag[i]를 true로 바꾸고 turn을 j(i != j)로 바꾼 뒤 flag[j]가 true이고 turn이 j인 경우 무한 루프를 돈다. 이는 상대방이 critical section에 진입함을 나타낸다. 만약 그렇지 않으면 critical section에 진입하고 이를 마치면 flag[i]를 false로 바꾼다.
    • critical section 해결 조건을 모두 만족하지만 busy waiting(spin lock) 문제가 발생한다. 즉, 무한 루프를 계속 도는 동안 해당 프로세스는 아무 일도 하지 않고 CPU와 memory만 쓰면서 기다리고 있기에 비효율적이다.
  • 하드웨어를 이용한 해결 방법
    • 하드웨어적으로 test and modify를 atomic하게 수행할 수 있도록 지원한다. 즉, 공유 데이터를 읽고 해당 데이터에 덮어쓰는 과정을 한 번에 할 수 있도록 한다.
    • 이를 활용하면 소프트웨어적으로 복잡하게 해결했던 문제를 간단히 해결할 수 있다.
    • 공유 변수인 lock을 false로 초기화한 뒤 위 작업을 한 번에 하는 함수인 test_and_set 함수를 실행시킨 결과가 true인 동안에 무한 루프를 돈다. test_and_set 함수는 현재 lock 변수의 값을 반환함과 동시에 lock 변수의 값을 true로 바꾼다. test_and_set 함수의 결과가 false이면 critical section을 수행하고 lock을 false로 바꾼다.

5. Semaphores(S)

• 앞의 방식들을 추상화시킨 것
• 정수 값을 가질 수 있다. 이 값은 자원의 개수를 의미한다.
• 두 가지 atomic 연산에 의해서마 접근이 가능하다.
  • P(S) : 공유 데이터를 획득하는 과정으로, S가 0 이하일 동안 무한 루프를 돌고, 그렇지 않으면 S를 1 감소시킨다.
  • V(S) : 공유 데이터를 반납하는 과정으로, S를 1 증가시킨다.
• busy-waiting 문제가 여전히 발생할 수 있다.
• 이를 해결하기 위해 block & wakeup(sleep lock)을 구현한다. 즉, 무한 루프를 도는 경우 해당 프로세스를 block시키고 공유 데이터를 얻을 수 있는 경우 ready 상태로 바꾼다.
  
  • P(S) : 우선 S의 값을 1 감소시키고, 만약 S의 값이 0보다 작으면 S를 기다리는 프로세스 리스트에 현재 프로세스를 추가하고 해당 프로세스를 blocked 상태로 바꾼다.
  • V(S) : 우선 S의 값을 1 증가시키고, 만약 S의 값이 0보다 작거나 같으면 S를 기다리는 프로세스 리스트에서 프로세스 하나를 꺼내 해당 프로세스를 ready 상태로 바꾼다.
• block & wakeup에도 overhead가 존재하기 때문에 critical section이 매우 짧은 경우 busy-waiting의 경우가 더 나을 수도 있지만 일반적인 경우 block & wakeup 방식이 더 낫다.
• semaphore의 종류
  • counting semaphore : 도메인이 0 이상인 임의의 정수값으로, 주로 resource counting에 사용한다.
  • binary semaphore(mutex) : 0 또는 1 값만 가질 수 있는 semaphore로 주로 mutual exclusion(lock/unlock)에 사용한다.

6. Deadlock and Starvation

• Deadlock : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
• Starvation
  • 특정 이유로 인해 어떤 프로세스가 계속 공유 데이터를 사용할 수 없는 현상 
  • indefinite blocking : 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

7. Classical Problems of Synchronization

• Bounded Buffer Problem(Producer-Consumer Problem)
  • 한정된 크기의 공유 buffer에 공유 데이터를 추가하는 producer와 공유 데이터를 사용하는 consumer가 정상적으로 작업을 수행해야 한다.
  • 공유 데이터에는 buffer 자체와 buffer를 조작하는 변수(empty/full buffer의 시작 위치)가 있다.
  • synchronization variable로 buffer 접근에 대해서는 mutex를, buffer 내 empty/full buffer의 개수로 counting semaphore를 사용한다.
  • producer의 경우 P(empty), consumer의 경우 P(full)을 실행해 자원이 남아 있는 경우에만 buffer에 접근한 뒤 buffer에 대한 lock을 걸고 작업을 수행한다. 작업이 끝나면 lock을 해제하고 producer의 경우 V(full), consumer의 경우 V(empty)를 수행해 자원이 남아있지 않아 작업을 수행하지 못한 consumer나 producer가 작업을 수행할 수 있도록 한다.
• Readers-Writers Problem
  • DB에 접근 중일 때 write의 경우 항상 한 프로세스에게만 허용해야 하지만 read의 경우 데이터를 바꾸지는 않기 때문에 여러 프로세스가 접근해도 무방하다. 
  • 따라서 writer가 DB에 접근 허가를 받지 못한 상태에서는 모든 대기중인 reader들이 DB에 대한 접근을 허용하고, writer는 대기 중인 reader가 없을 때 DB 접근을 허용한다. 단, writer가 DB에 접근 중이면 DB에서 빠져나갈 때까지 reader의 접근이 금지된다.
  • 공유 데이터에는 DB 자체와 readcount(DB에 접근 중인 reader의 수)가 있다.
  • synchronization variable로 공유 변수 readcount에 접근하기 위한 mutex와, reader와 writer가 DB 자체를 올바르게 접근하게 하는 db가 있다.
  • writer는 P(db)를 실행해 db 접근이 허용되면 작업을 수행하고, 끝나면 V(db)를 수행해 다른 프로세스의 db 접근을 허용한다. reader는 우선 readcount 조정을 위해 P(mutex)를 실행하고 readcount를 1 증가시킨다. 그리고 만약 readcount가 1, 즉 최초로 read를 한 프로세스라면 P(db)를 실행해 writer가 DB에 접근하지 못하도록 한다. 그 다음 V(mutex)를 실행해 다른 reader도 DB에 접근할 수 있도록 한다. 프로세스 자체의 작업을 수행한 후에는 다시 P(mutex)를 실행한 뒤 readcount를 1 감소시킨 뒤 만약 readcount가 0이 되면, 즉 DB에 접근하는 reader가 없는 경우 V(db)를 실행해 writer가 DB에 접근할 수 있도록 한다. 마지막으로 V(mutex)를 실행하면 reader의 DB 접근이 완전히 종료된다. 
  • 단, writer는 DB에 접근하는 reader가 아무도 없어야 DB에 접근 가능해서 starvation이 발생할 수 있다. 이는 writer가 DB에 접근하기 전 접근 가능한 reader의 수를 제한하는 등의 방식으로 해결할 수 있다.
• Dining-Philosophers Problem
  • 5명의 철학자가 5개의 접시와 5개의 젓가락이 놓여진 원탁에 앉아 식사를 할 때 어떻게 하면 모든 철학자가 식사를 할 수 있을지를 결정하는 문제이다.
  • 단순히 각 철학자마다 양쪽에 있는 젓가락에 P 연산을 수행한 뒤 식사하고 V 연산을 수행하게 하면 deadlock이 발생할 가능성이 생긴다.(모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우)
  • 해결 방안
    • 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
    • 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
    • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다.

8. Semaphore의 문제점

• 코딩하기 힘들다.
• 정확성의 입증이 어렵다.
• 자발적 협력이 필요하다.
• 한번의 실수가 모든 시스템에 치명적인 영향을 끼친다.

9. Monitor

• semaphore의 문제점을 해결하기 위한 구조
• 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization contruct
• monitor에 대한 동시 접근을 허용하지 않아 lock을 걸 필요가 없다.
• 공유 변수와 공유 데이터에 접근하기 위한 내부 함수가 구현되어 있다.
• 프로세스가 monitor 안에서 기다릴 수 있도록 하기 위해 condition variable을 사용한다. condition variable은 wait와 signal 연산에 의해서만 접근 가능하다.
  • x.wait()를 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend된다.
  • x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

 

 

출처 : 운영체제 강의