[CS] 운영체제 - 프로세스 동기화

데이터의 접근

순서는 아래와 같다.
1. 저장된 곳에 있는 Data를 연산하는 곳으로 보낸다.
2. 연산하는 부분에서 연산 후 연산 결과를 다시 원래 위치로 보낸다.

ex) CPU와 Memory (프로세스가 연산의 주체이고 주소공간이 저장소임)

 

Race condition

예를 들어 저장소를 다른곳에서 동시에 사용할 때 문제가 생길 수 있다.
이 때 이러한 문제를 해결해야 한다.
OS에서 Race condition 문제가 발생하는 상황은 다음과 같다.

1. Kernel 수행 중 인터럽트 발생 시
   • 커널모드 실행중 interrupt가 발생하여 인터럽트 처리루틴이 수행한다. 양 쪽 다 커널 코드 이므로 kernel address space가 공유된다.
2. Process가 system call을 해서 kernel mode로 수행 중인데 context switch가 일어나는 경우
   • 해결책: 커널 모드에서 수행 중일 때는 CPU를 preempt하지 않는다. 커널 모드에서 사용자 모드로 돌아갈 때 preempt
3. Multiprocessor에서 shared memory 내의 kernel data
   • 어떤 CPU가 마지막으로 count를 store 했는지?

 

프로세스 동기화의 문제

공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다.
일관성 유지를 위해서는 협렵 프로세스간의 실행 순서를 정해주는 매커니즘이 필요하다.
Race condition: 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다.
Race condition을 막기 위해서는 concurrent process는 동기화 되어야 한다.

 

임계 구역 문제 (The critical-Section Problem)

n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우이다.
각 프로세스의 code segement에는 공유 데이터를 접근하는 코드인 critical section이 존재한다.
문제: 하나의 프로세스가 critical section에 있을 때, 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
critical-Section이란 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원을 접근하는 코드를 말한다.

 

프로그램적 해결법의 충족 조건

Mutual Exclusion (상호 배제)

• 프로세스 P가 critical-Section 부분을 수행중이면 다른 모든 프로세스들은 그들의 critical-Section에 들어가면 안된다.

Progress

• 아무도 critical-Section에 있지 않은 상태에서 critical-Section에 들어가고자 하는 프로세스가 있으면 critical-Section에 들어가게 해주어야 한다.

Bounded Waiting(유한 대기)

• 프로세스가 critical-Section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical-Section에 들어가는 횟수에 한계가 있어야 한다.

위 충족 조건들은 모든 프로세스의 수행 속도가 0보다 크고, 프로세스들간의 상대적인 수행속도를 가정하지 않은 상태이다.
하드웨어적으로 지원하는 경우 문제가 간단히 해결된다.

 

Semaphores

세마포어는 두 개의 원자적 함수로 조작되는 정수 변수이다.
P 연산은 공유 데이터를 획득하는 과정이고
V 연산은 반납하는 과정이다.

 

Block/wakeup overhead vs critical section의 길이

critical section의 길이가 긴 경우 Block/Wakeup이 적당하다.
critical section의 길이가 매우 짧은 경우 Block/Wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질수 있다.
일반적으로는 Block/Wakeup 방식이 더 좋다.

 

Semaphores의 두가지 종류

Counting

• 도메인이 0 이상인 임의의 정수값이다.
• 주로 resource counting에 사용한다.

Binary semaphore

• 0 또는 1 값만 가질 수 있는 semaphore이다.
• 주로 mutual exclusion에 사용한다.

 

Deadlock, Starvation

Deadlock은 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 영원히 기다리는 현상이다.
Starvation은 프로세스가 suspend된 이유에 해당하는 semaphore 큐에서 빠져나갈 수 없는 현상이다.

 

Bounded-Buffer-Probelm

버퍼의 크기가 유한한 환경에서 일어나는 문제이다.
생산자(Producer) 프로세스가 있고, 소비자(Consumer) 프로세스가 있다.
(색칠된건 데이터가 들어있는 버퍼이고, 색이 없는건 비어있는 버퍼임)
생산자는 비어있는 버퍼가 있으면 공유데이터에 lock을 걸고(다른 프로세스의 진입을 막기위해 lock을 건다.) 비어있는 버퍼에 데이터를 만들어서 집어넣고 lock을 푼다.
소비자는 데이터가 있는 버퍼가 있으면 공유 데이터에 lock을 걸고(다른 프로세스의 진입을 막기위해 lock을 건다.) 데이터가 있는 버퍼에서 데이터를 꺼내고 버퍼를 조작한후 lock을 푼다.
생산자와 소비자 모두 작업 할 수 있는 버퍼가 없으면 기다린다.

 

Readers-Writers Problem

프로세스에는 읽는 프로세스와 쓰는 프로세스가 있다.
한 프로세스가 공유데이터(DB)에 쓰는 작업 중일 때 다른 process가 접근하면 안된다.
read는 동시에 여럿이 해도 상관 없다.
해결책은 다음과 같다.

• Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다.
• Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
• Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
• Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.

 

Dining-Philosophers Problem

여러 프로세스가 동시에 돌아갈 때 교착 상태가 나타나는 원인을 풀어놓은 문제이다.
해결 방안은 다음과 같다.

• 4명의 철학자만이 테이블에 동시에 앉을 수 있게 한다.
• 양쪽 모두를 집을 수 있을 때만 집게 한다.

 

Monitor

Semaphore에는 아래와 같은 문제점들이 있다.

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

모니터는 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct이다.
프로그래머 입장에서 Monitor를 사용하면 lock을 걸 필요가 없이 공유 데이터를 접근하면 된다. 

모니터 내에서는 한번에 하나의 프로세스만이 활동 가능하다.
프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다.
프로세스가 모니터안에서 기다릴 수 있도록 하기 위해 condition 변수를 사용한다.
condition 변수는 wait과 signal 연산에 의해서만 접근이 가능하다.