[문과 코린이의 IT 기록장] 운영체제(OS) - Process Synchronization(프로세스 동기화) (데이터의 접근, Race Condition (경쟁 상태), OS에서의 Race Condition, Process Synchronization(=프로세스 동기화 = 병행 제어) 문제, The Critical-Section Probelm (임계구역 문제), Syncronization과 관련된 세 가지 문제점 - Semaphore 활용, Monitor)
운영체제
운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 본 강좌에서는 이와 같은 운영체제의 개념과 역할, 운영체제를 구성하는 각
www.kocw.net
[문과 코린이의 IT 기록장] 운영체제(OS) - 운영체제(운영체제(OS)란?, 운영체제(OS)의 기능 및 목표,
[문과 코린이의 IT 기록장] 운영체제(OS) - 운영체제(운영체제(OS)란?, 운영체제(OS)의 기능 및 목표, 운영체제의 분류, 몇 가지 용어, 운영체제의 예, 운영체제의 개괄적인 구조) 운영
vansoft1215.tistory.com
[문과 코린이의 IT 기록장] 운영체제(OS) - System structure & Program execution (컴퓨터 시스템 구조, 동기
[문과 코린이의 IT 기록장] 운영체제(OS) - System structure & Program execution (컴퓨터 시스템 구조, 동기식 입출력과 비동기식 입출력, 서로 다른 입출력 명령어, 저장장치 계층 구..
vansoft1215.tistory.com
[문과 코린이의 IT 기록장] 운영체제(OS) - 프로세스(Process) (프로세스의 개념, 프로세스의 상태 (Pro
[문과 코린이의 IT 기록장] 운영체제(OS) - 프로세스(Process) (프로세스의 개념, 프로세스의 상태 (Process State), PCB, 문맥 교환 (Context Switch), 프로세스를 스케줄링 하기 위한 ..
vansoft1215.tistory.com
[문과 코린이의 IT 기록장] 운영체제(OS) - Process Management (프로세스 생성 (Process Creation), 프로세스
[문과 코린이의 IT 기록장] 운영체제(OS) - Process Management (프로세스 생성 (Process Creation), 프로세스 종료 (Process Termination), fork() 시스템 콜, exec() 시스템 콜, wait(..
vansoft1215.tistory.com
[문과 코린이의 IT 기록장] 운영체제(OS) - CPU 스케줄링 (CPU and I/O Bursts in Program Excution, CPU Scheduler &
[문과 코린이의 IT 기록장] 운영체제(OS) - CPU 스케줄링 (CPU and I/O Bursts in Program Excution, CPU Scheduler & Dispatcher, Scheduling Criteria (성능 척도), Scheduling Algorit..
vansoft1215.tistory.com
1. 데이터의 접근
- Process Synchronization을 공부하기 앞서, 컴퓨터 시스템 안에서 데이터가 접근되는 패턴에 대해 이야기하고자 함.
* 컴퓨터 시스템 내에 어떤 위치에 있던, 데이터를 접근하는 것은 이와 같은 경로를 지나간다.
ex.
| E-box | S-box |
| CPU | Memory |
| 컴퓨터 내부 | 디스크 |
| 프로세스 | 그 프로세스의 주소공간 |
- 이와 같이 데이터를 읽어오고 다시 원래 위치에 새로운 데이터를 반영하는 과정에서, Process Synchronization이 발생한다.
ex. 데이터를 읽기만 하는 것은 문제 X, 데이터를 읽어오고 연산을 실행한 후 다시 데이터에 저장하는 경우에는, 여러 프로세스들이 데이터에 접근하면 결과값에 문제가 생김.
2. Race Condition (경쟁 상태)
# S-box(Memory Address Space)를 공유하는 E-box(CPU Process)가 여러개 있는 경우, Race Condition의 가능성이 있다.
* 이와 같이 여러 주체가 하나의 데이터를 동시에 접근하고자 할 때 발생하는 문제점을, race condition이라고 한다.
* 따라서 이를 조율해줄 수 있는 방식이 필요하다.
3. OS에서의 Race Condition
[ OS에서 Race Condition이 발생하는 경우 ]
1. kernel 수행 중 인터럽트 발생 시
2. 프로세스가 System call을 하여, kernel mode로 수행중인데, context switch가 일어나는 경우
3. Multiprocessor에서 shared memory 내의 kernel data
1) Kernel 수행 중 인터럽트 발생 경우
(1) 문제점
(2) 해결방안
2) Kernel mode로 수행중인데, Context switch가 일어나는 경우
(1) 문제점
(2) 해결방안
- Kernel mode에서 수행중일 때는 CPU를 선점할 수 없도록 함.
- 그리고 Kernel mode에서 User mode로 돌아갈 때 선점할 수 있도록 변경함.
* 할당시간에 약간의 편차가 생기긴 하겠지만, time-sharing 시스템은 real-time system이 아니기 때문에, 시간을 딱 맞춰야 하는 것이 아니여서, 이와 같은 방법을 활용해 복잡한 문제를 좀 더 효율적으로 해결할 수 있음.
3) MultiProcessor (CPU가 여러개 있는 경우)
(1) 문제점
- 이 경우는 앞에서 설명한 어떠한 해결방안도 적용될 수 없음.
ex. 인터럽트를 막아서 해결할 수 있지 않음. cpu1의 인터럽트를 막는것이 cpu2에 영향을 주는것이 아니기 때문
즉, multiprocessor의 경우 interrupt enable/disable로 해결되지 않음.
(2) 해결방안
방법 1 ) 한번에 하나의 CPU만이 커널에 들어갈 수 있도록 하는 방법
* 여러 cpu가 운영체제 커널에 동시에 접근하기 때문에 발생하는 문제이므로, 이 커널에 접근하는 cpu를 한개로 제한하는 것이 해결방안이 된다.
방법 2 ) 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법
* count데이터에 접근할 때, lock을 걸고, 수정 후 돌려줄 때 unlock을 한다.
4. Process Synchronization(=프로세스 동기화 = 병행 제어) 문제
| # Race condition - 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황 - 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다. |
- 공유 데이터(shared data)의 동시 접근(concurrent acces)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다.
- 일관성(consistency) 유지를 위해서는, 협력 프로세스(cooperating process)간의 실행순서(orderly execution)을 정해주는 매커니즘이 필요하다.
- Race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 한다.
5. The Critical-Section Probelm (임계구역 문제)
* critical-section (임계구역) : 공유데이터를 접근하는 코드
- n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우에, 각 프로세스의 code segment에는, 공유데이터를 접근하는 코드인 critical section이 존재한다.
- 하나의 프로세스가 critical section에 있을 때, 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
- 따라서, 공유데이터를 접근하는 코드를 실행중이면, cpu를 다른 프로세스에게 뺐기더라도, 공유데이터를 접근하는 critical section에 들어가지 못하게 해야 한다. 즉, P1이 공유데이터를 접근하고 있다면, P2는 접근하지 못하고 기다려야 한다.
1) The critical section(임계구역) 문제를 해결하기 위해서
[ 프로세스들의 일반적인 구조 ]
do{
entry section // lock
critical section // 공유데이터를 접근하는 코드
exit section // unlock
remainder section
} while(1)
- 어떤 프로세스던지간에, 위와 같이 공유데이터를 접근하거나 / 접근하지 않는 형식으로 구성되어 있을 것이다.
- 임계구역 문제는, 일반적으로 공유데이터를 동시접근할 때 발생하는 문제이기 때문에, 공유데이터를 접근하는 코드 이전에 entry section(lock)을 걸어 여러 프로세스들이 들어가는 것을 막고, exit section(unlock)을 통해 다른 프로세스가 들어갈 수 있도록 하면 해결될 수 있다.
2) 프로그램적 해결법의 충족 조건
- critical section 문제를 풀기 위해서, 만족해야 할 조건이 3가지가 존재함.
1. mutual exclusion (상호 배제)
- 프로세스 Pi가 critical section 부분을 수행중이면, 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.
- 즉 배타적으로 접근이 가능해야 한다.
2. Progress (진행)
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면, critical section에 들어가게 해주어야 한다.
* 종종 여러개의 프로세스가 동시에 들어가고자 하는 것을 막다보니, 아무도 들어와있지 않음에도 아무도 들어갈 수 없는 상황으로 코드를 작성하게 되기도 함.
3. Bounded Waiting (유한 대기)
- 프로세스가 critical section에 들어가려고 요청한 후부터, 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
* 이는 특정 프로세스 입장에서 critical section을 들어가지 못하고, 지나치게 오래 기다리는 Starvation현상이 생기지 않게 해야한다는 것을 이야기하고 있는 것이다.
# 이 세 가지의 조건들을 만족하면서, critical section의 문제를 풀 수 있는 알고리즘을 이야기해보고자 함.
3) The critical section Probelm 해결방법 - 소프트웨어 차원
(1) Algorithm 1
/* 프로세스 P0에 대한 코드 - 프로세스는 P0와 P1만 존재함 */
do{
while(turn !=0)
critical section // 공유데이터를 접근하는 코드
turn = 1;
remainder section
} while(1)do{
while(turn !=0)
// critical section에 들어가기 전에 while문을 돌면서 체크한다.
// 변수 turn은 몇번재 프로세스인지를 나타내주는, 즉 누구 차례인지를 나타내주는 변수이다.
ex. trun = 0 (프로세스 0번 차례)
// 즉 turn = 0으로 되어 있다면, P0 프로세스는 접근하지 못하고 while문을 계속 돈다.
critical section // 공유데이터를 접근하는 코드
turn = 1;
// crtical section에서 모든 작업이 끝나면, turn=1로 바꿔주면서 프로세스 P1이 접근할 수 있도록 해준다.
remainder section
} while(1)
- 이 코드는, Mutual exclustion은 만족한다.
- 그러나 문제점은 여전히 존재한다.
a. 아무도 cricial section에 없는데도 불구하고 아무도 들어가지 못하는 Progress의 조건은 만족시키지 못하고 있다.
b. 이 알고리즘은 Critial section에 교대로 들어가도록 되어있기 때문에, P0과 P1가 균일하지 않게 crticla section에 들어가고자 할 때 효율성이 떨어진다.
(2) Algorithm 2
/* 프로세스 P0에 대한 코드 - 프로세스는 P0와 P1만 존재함 */
do{
flag[i] = true;
while(flag[j]);
critical section // 공유데이터를 접근하는 코드
flag[i] = false;
remainder section
} while(1)do{
flag[i] = true;
// flag 변수 : 프로세스가 critical section에 들어가고자 한다는 의중을 표시하는 것 (프로세스는 각각 이를 지님)
// 처음 flag의 값은 항상 false임. (critical section에 들어가고자 하는 상태 X)
while(flag[j]);
// 상대방 flag를 체크하고, 상대방이 세팅해놓았다면 기다림.
critical section // 공유데이터를 접근하는 코드
flag[i] = false;
// critical section을 사용한 후에는, flag를 false로 만들어줌
remainder section
} while(1)
[ 문제점 ]
- P0가 본인의 flag를 들고 있는 상태에서, 본인의 CPU를 뺐기게 되면 P1에게 넘어간다.
- 그러면 flag만 두 프로세스가 들고 있는 상태이기 때문에, 둘 다 critial section에 들어가지 못하고 while문에서 계속 기다리게 된다.
- flag를 내려놓는 행위는 critical section에 들어갔다가 나와야 할 수 있는데, 그러지 못해서 영원히 아무도 critcal section에 들어가지 못할 수 있음.
(3) Algorithm 3 (= Peterson's Algorithm)
/* 프로세스 P0에 대한 코드 - 프로세스는 P0와 P1만 존재함 */
do{
flag[i] = true;
turn = j;
while(flag[j] && turn == j);
critical section // 공유데이터를 접근하는 코드
flag[i] = false;
remainder section
} while(1)do{
flag[i] = true;
turn = j;
// turn을 상대방 turn으로 바꿔놓음.
while(flag[j] && turn == j);
// 이후 critical section에 들어가기 전에 체크를 한다. 상대방이 flag를 들고 있고, 상대방 turn인 경우 둘 다 만족하는 경우만 while문에서 기다린다. (하나라도 만족하지 않으면 critical section에 접근한다)
critical section // 공유데이터를 접근하는 코드
flag[i] = false;
remainder section
} while(1)
- 이 방법은 앞의 충족 조건 3가지를 모두 만족시키는 방법이다.
- 그러나 이 방법 또한 또 다른 문제점이 존재한다. : Busy Waiting (= spin lock)
* 만약 프로세스 P0가 critical section에 들어가 있는 상태에서, 프로세스 P1이 CPU를 잡게 되면 while문을 돌면서 조건을 체크해야 할 것이다. 그런데 그것을 확인하고 권한을 획득하는 과정에서 CPU를 낭비하게 된다.
4) The critical section Probelm 해결방법 - 하드웨어 차원
- 하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결이 가능하다.
* 즉 데이터를 읽고 쓰는 것을 하나의 명령어로 처리할 수 있다면 해결된다는 것이다.
* 명령어 하나를 실행하는 도중에 CPU를 빼앗기지는 않기 때문 (interrupt는 명령어 하나를 처리 한 후 확인)
Synchronization variable;
boolean lock = false;
do{
while(Test_and_Set(lock));
critical ection;
lock = false;
remainder section;
}Synchronization variable;
boolean lock = false;
do{
while(Test_and_Set(lock));
// lock이 0이면 Critical section에 아무도 들어가있지 않기 때문에, 들어가면 되는 것
// Critical section에 들어갈 때는 lock을 1로 변환시킴.
critical ection;
lock = false;
remainder section;
}
| - 이러한 작업들을 프로그래머가 매번 직접 하는 것은 어려움. - 그래서 일반적으로는 프로그래머가 좀 더 간편하게 활용할 수 있도록, 고급 추상 자료형인 semaphore를 정의하고, 프로그래머들은 직접 작업을 하는게 아닌 연산만 하면 lock을 걸고 풀 수 있도록 하고 있음. |
5) Semaphores (추상 자료형)
- 앞의 방식들을 추상화시킨다.
* 추상자료형은 논리적으로 정의하는거지, 실제로 컴퓨터에서 자료형이 어떻게 구현되느냐 하고는 별개의 자료형이다.
Semaphore S;
// 변수 S는 정수값을 가질 수 있음.
cf ) 변수 S = 자원의 개수를 의미함.
// semaphore라는 변수에 대해 정의되는 연산은 P연산 ,V연산 두가지 존재
cf ) P연산과 V연산은 automic하게 이루어지고 있다는 것을 가정하고 있다. (즉, semaphore라는 것은 구체적인 구현을 나타내는게 아닌, 추상적으로 연산자체를 정의해놓는 것임)
P(S):
while(S<=0) dp no-op;
S--;
// semaphore변수 값을 획득하는 과정. 즉, 공유데이터를 획득하는 과정
* 변수 S에 대해 P연산을 하게 되면, S값이 0이하인 동안에는 while문을 돌면서 대기하고 있는다. (자원을 가져갈 수 없는 상태이기 때문)
* 그러다, S값이 양수가 되면 그 때 S의 값을 1 빼고 자원을 획득하게 됨.
V(S):
S++;
// semaphore변수 값을 사용하고 반납하는 과정, 즉 공유데이터를 사용하고 반납하는 과정
* 사용이 다 끝나고 나면, S값을 1 증가시켜 반납해줌
# 이 방법 또한, 자원이 없을 때 P연산을 하게 되면 계속 대기하게 되면서 본인의 CPU시간을 다 사용하는 busy wait문제가 발생할 수 있다.
(1) Critical section of n Process
- critical section문제에 semaphore를 활용해보기
// Synchronization variable
semaphore mutex;
// Process Pi
do{
P(mutex);
critical section;
V(mutex);
remainder section;
}while(1);// Synchronization variable
semaphore mutex; // semaphore변수 mutex (하나씩 알고리즘으로 코딩하는게 아닌, 이와같이 추상자료형 활용)
// Process Pi
do{
P(mutex); // mutex변수 P연산
critical section;
V(mutex); // mutex변수 V연산
remainder section;
}while(1);
# 아직까지 busy-wait(=spin lock)문제가 발생한다. 이를 해결하기 위해서는?
: block & wakeup(=sleep lock) 방식으로 구현해주면 된다.
(2) Block & Wakeup(=Sleep lock) Implementation
- 누군가 이미 공유데이터를 쓰고 있으면, 쓸데없이 while문을 돌면서 기다리는 것이 아닌, 그 프로세스 자체를 blocked시켜서 cpu를 아에 반납하고 잠들어있다가, 공유데이터를 가지고 있던 프로세스가 내놓으면 그 때 깨어나서 공유데이터를 얻는(wakeup)방식을 수행
/* Semaphore 정의 */
typedef struct{
int value; // semaphore 변수
struct process *L; // Process wait queue
}semaphore;- block와 wakeup을 다음과 같이 가정
a. block
: 커널은 block을 호출한 프로세스를 suspend시킨다. 그리고 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다.
b. wakeup(P)
: block된 프로세스 P를 wakeup시킨다. 그리고 이 프로세스의 PCB를 ready queue로 옮긴다.
/* Semaphore 연산 정의 */
P(S):
S.value--;
if(S.value <0)
{
add this process to S.L;
block();
}
V(S):
S.value++;
if(S.value<=0)
{
remove process P from S.L;
wakeup(P);
}
P(S): // 자원을 획득하는 과정
S.value--; // 자원의 여분이 있다면 바로 획득
if(S.value <0) // 자원의 여분이 없다면 (음수는 여분 획득 불가능)
{
add this process to S.L; // S.L에 연결됨
block(); // block 실행 : 자원이 생기면 깨어나게 됨
}
V(S):
S.value++; // S값 1 증가시킴
if(S.value<=0) // 자원의 여분이 존재한다면
{
remove process P from S.L; // P = S.L
wakeup(P); // 자원을 반납할 때 연결된 프로세스를 하나 깨워줌
}
(3) Busy-wait방식 vs Blocked & Wakeup 방식
- 일반적으로는 Blocked & Wakeup방식을 활용하는 것이 효율적이다.
* 쓸데없이 CPU를 낭비하는 시간이 사라지기 때문.
- 그러나 Block & Wakeup방식 또한 오버헤드를 발생시킨다는 문제가 있다.
* 프로세스의 상태를 ready에서 blocked상태로 바꿔주고, blocked상태에서 ready상태로 바꿔주는 과정에서 발생
- 따라서 Critical section의 길이가 매우 짧은 경우에는 Busy-Wait 방식을 활용하는 것이 더 좋을 수 있다.
(4) Two types of Semaphores (Semaphore의 두 가지 종류)
a. Counting semaphore
- 도메인이 0 이상인 임의의 정수값
- 주로 resource counting에 사용 (여분의 자원을 counting하는 용도로 활용)
b. Binary semaphore (=mutex)
- 자원의 개수가 1개인 경우
- 즉 0 또는 1의 값만 가질 수 있는 semaphore를 이용한다.
- 주로 mutual exclusion (lock/unlock)에 사용
6) Semaphore 활용시 주의점 (Deadlock & Starvation)
1) Deadlock
- 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
* Semaphore S,Q 두 개 있다고 가정.
** 즉 이 상황은 P0가 자원 하나를 획득하고, P1가 또 다른 자원을 획득한 상태에서, 두 프로세스 모두 자원을 놓지 못하고 상대방이 가진 것을 영원히 기다리면서 조건이 충족되지 않는 상태를 나타낸다. 이를 deadlock라고 한다.
[ 해결 방법 ]
- 자원을 획득하는 순서를 똑같이 맞춰주면 됨.
2) Starvation
- indefinite blocking.
: 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
* 즉, 영원히 특정 프로세스가 자원을 얻지 못하고 기다리는 것을 의미함.
* deadlock 또한 starvation의 일종이라고 볼 수 있음.
6. Syncronization과 관련된 세 가지 문제점 - Semaphore 활용
1) Bounded-Buffer Problem (Producer-Consumer Problem)
[ 이 문제에서는 프로세스가 두 가지 종류가 있다. ]
a. Producer (생산자 프로세스) : 공유버퍼에다 데이터를 하나씩 만들어서 넣는 역할을 함.
b. Consumer (소비자 프로세스) : 데이터를 하나씩 빼서 사용하는 역할을 함.
* 각각 하나씩만 존재하는 것이 아닌 여러개 존재
[ 여기서 Synchronization과 관련한 어떤 문제들이 발생하는가? ]
a. 생산자 프로세스 둘이 같은 위치에 동시에 데이터를 만들어 넣고자 했을 때 발생하는 문제
b. 소비자 프로세스 둘이 같은 위치에 데이터를, 동시에 꺼내쓰고자 할 때
- 이 두 상황에서 lock을 걸고 푸는 상황이 필요하며, 이를 Semaphore변수로 구현하게 됨
c. 버퍼의 개수가 유한하기 때문에, 생산자가 더 이상 데이터를 만들지 못하거나, 소비자가 사용할 데이터가 없는 자원의 상태가 나타날 수 있음.
* 생산자 입장 : 비어있는 버퍼의 개수가 counting해야 할 자료
* 소비자 입장 : 채워져있는 버퍼의 개수가 counting해야 할 자료
* Shared data : buffer 자체 및 buffer 조작 변수 (empty/full buffer의 시작 위치)
* Synchronization variables (싱크로나이제이션 변수)
- mutual exclusion : binary semaphore 필요 (공유 데이터의 mutual exclusion을 위해)
- resource count : integer semaphore 필요 (남은 full/empty buffer의 수 표시)
[ semaphore를 이용한 공유데이터 관리 - Producer-Consumer Problem을 Semaphore로 푸는 방법]
Synchronization variables :
semaphore full = 0; // 데이터가 들어있는 버퍼의 개수를 세기 위한 변수
empty = n; // 데이터가 비어있는 버퍼의 개수를 세기 위한 변수 (공유 버퍼의 개수)
mutex = 1; // lock을 결기 위한 변수
Producer : // 생산자 프로세스들이 어떤 절차를 거치고 있는가
do{...
produce an item in x
...
P(empty); // empty 버퍼가 있으면 획득 (empty = 0이라면 기다려야 함)
P(mutex); // 이 버퍼에 데이터를 집어넣기 위해 mutex lock을 검
...
add x to buffer // 데이터 집어넣음
...
V(mutex); // 버퍼 조작이 끝났으면, 걸었던 lock을 품
V(full); // 데이터가 존재하는 버퍼의 개수를 1 증가시키기 위해 V(full) 진행
} while(1);
Consumer : // 소비자 프로세스들이 어떤 절차를 거치고 있는가
do{
P(full); // 데이터가 들어있는 버퍼가 존재하는지를 보고 P(full) 진행 (full = 0이라면 기다려야 함)
P(mutex); // 버퍼의 데이터를 가져가기 위해 mutex lock을 걸음
...
remove an item from buffer to y
...
V(mutex); // 버퍼 조작이 끝나면, 걸었던 lock을 품
...
consume the item in y // 버퍼 데이터 소비
...
V(empty); // 데이터가 비어있는 버퍼의 개수를 1 감소시키기 위해 V(empty) 진행 (1 증가)
} while(1);
2) Readers and Writers Problem
- 한 프로세스가 DB(공유데이터)에 write중일 때, 다른 프로세스가 접근하면 안됨 (이 문제 해결 필요)
- 그러나 DB(공유데이터)에 read는 동시에 여럿이 가능함.
[ Semaphore를 이용한 해결책 ]
1) Read, Write 모두 lock을 걸고 푸는 방법
2) Read는 동시접근이 가능하도록, Write는 동시접근이 불가능하도록 하는 방법
- Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다.
- Writer는 대기중인 Reader가 하나도 없을 때, DB 접근이 허용된다.
- 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
- Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.
[ Shared data ]
- DB자체
- int readcount = 0; // 현재 DB에 접근중인 Reader의 수
[ Synchronization variables ]
- semaphore mutex = 1; // 공유변수 readcount를 접근하는 코드 (critical section)의 mutual exclusion보장을 위해 사용
- db = 1; // Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할
/* Wirter */
P(db); // DB에 대한 lock걸기
...
writing DB is performed // DB(공유데이터) 쓰기
...
V(db); // DB에 대한 lock풀기
// Starvation 발생 가능/* Reader */
P(mutex);
// readcount 변수 lock 걸기 (readcount변수도 공유변수이기 때문에 그냥 증가시키면 문제 발생)
readcount++;
// readcount(몇명의 reader가 읽고 있는지를 나타내는 공유변수) 1증가
if(readcount==1) P(db);
// 만약 접근한 프로세스가 최초의 rader라면(아무도 읽지 않은 상황이라면) DB에 lock 걸기
// 최초의 reader가 아니라면, 그냥 접근
V(mutex);
// readcount 변수 lock 풀기
...
reading DB is performed
// DB읽기 끝남
...
P(mutex);
// readcount 변수 lock 걸기
readcount--;
// readcount -1감소
if(readcount==0) V(db);
// 마지막 reader라면, DB에 대해 lock을 풀기
V(mutex);
// readcount 변수 lock 풀기
[ Starvation 발생 문제 ]
- reader가 lock을 걸은 이후부터 도착하는 reader들은, 무조건 읽을 수 있도록 코드를 구현해 놓음.
- 따라서, 계속 reader들이 도착하게 되면, writer는 오랜 시간동안 기능하지 못하게 될 수 있음.
# 이는 queue에 우선순위를 둬서, wirter가 일정 수준 이상은 기다리지 않도록, 지나치게 늦게 들어온 reader에게는 lock이 걸려 있음에도 기다리도록 한 후, writer가 접근할 수 있도록 구현하면 된다.
3) Dinning-Philosophers Problem
[ Synchronization variables ]
semaphore chopstick[5]; // 공유자원 젓가락
[ Philosopher i ] - semaphore를 활용한 간단한 코딩
do{ // 이 행동을 다섯명의 철학자들은 무한반복한다
P(chopstick[i]); // 왼쪽 젓가락 들기
P(chopstick[(i+1)%5]); // 오른쪽 젓가락 들기
...
// 왼쪽, 오른쪽 젓가락을 다 들어야 먹을 수 있음
eat(); // 먹는 일 (철학자가 하는 일 1)
...
V(chopstick[i]); // 왼쪽 젓가락 내려놓기
V(chopstick[(i+1)%5]); // 오른쪽 젓가락 내려놓기
...
think(); // 생각하는 일 (철학자가 하는 일 2)
...
} while(1)
# 이 코드(해결책)는 굉장히 위험한 문제점을 가지고 있다. : Deadlock의 가능성 존재
- 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우, 오른쪽 젓가락은 영원히 잡을 수 없는 상태가 된다.
* 철학자는 하나의 젓가락을 잡았다면, 본인이 밥을 먹고 배가 불러지기 전까지는 젓가락을 놓지 않기 때문.
# 해결방안
1. 4명의 철학자만이 동시에 테이블에 앉을 수 있도록 한다.
2. 젓가락을 두 개 모두 집을 수 있을 때에만, 젓가락을 집을 수 있도록 권한을 준다.
3. 비대칭 : 짝수 철학자는 왼쪽 젓가락부터 잡도록 하고, 홀수 철학자는 오른쪽 젓가락부터 잡도록 한다.
[ Semaphore를 활용한 해결법(해결방안 2 사용) - Dinning-Phliosophers Problem ]
* 이 코드는 semaphore의 원리에 맞게 잘 짜여진 코드는 아님.
* semaphore 다음에 배우는 monitor를 통해, 좀 더 쉽게 Process Synchronization문제를 해결할 수 있음.
enum {thinking, hungry, eating} state[5]; // 공유변수 : 상태변수
semaphore self[5] = 0; // 각각 5명의 철학자가 젓가락 잡는 권한을 줄 것인지를 정하는 변수
// ex. self[1] = 0; 1번 철학자는 젓가락을 잡을 수 있는 권한이 없다.
semaphore mutex = 1; // 공유변수에 대한 동시접근을 막기 위해 lock을 나타내는 변수인 mutex
// cf. 철학자의 상태는 옆의 다른 철학자에도 영향을 미칠 수 있기 때문
/* Philosopher i */
do
{
pickup(i);
eat();
putdown();
think();
} while(1)/* test 함수 */
void test(int i){
if (state[(i+4)%5] != eating && state[i] == hungry && state[(i+1)%5] != eating)
// 왼쪽 철학자, 오른쪽 철학자 모두 먹고 있지 않고, 내가 배가고픈 상태일때
{
state[i] = eating; // 먹는 상태로 변환
V(self[i]); // V연산을 통해 0->1로 변환시킴.
// cf. 일반적인 semaphore는 자원의 권한을 1로 시작하는데, 이 코드에서는 권한을 0으로 설정한 후, test단계에서 조건을 만족하면 1로 바꾼다. 이를 V연산을 통해 실행한다.
}
}
/* pickup() 함수 */
void pickup(int i){
P(mutex); // 상태를 건들이기 때문에 lock을 건다.
state[i] = hungry; // 자신의 상태를 hungry로 바꾼다.
test(i); // test 함수 호출
V(mutex); // lock을 푼다.
P(self[i]); // 젓가락을 잡을 수 있는 권한을 얻게 되었으니, P연산을 실행함.
// cf. 만약 test연산에서 if문을 만족하지 못했다면, self[i]가 1이 될 때(권한이 생길 때)까지 P(self[i]) 내에서 기다려야 함.
}/* putdown() 함수 */
void putdown(int i){
P(mutex); // 상태 변환을 위해서 lock걸기
state[i] = thinking; // 상태 변환
test((i+4)%5); // 왼쪽 철학자 테스트
test((i+1)%5); // 오른쪽 철학자 테스트
// 철학자 테스트를 통해, 왼쪽 오른쪽 철학자가 나때문에 밥을 못먹고 있었다면, 권한 부여
V(mutex); // lock풀기
}
7. Monitor
1) Semaphore의 문제점
- 코딩하기 힘들다
- 정확성(correctness)의 입증이 어렵다. (즉 버그를 잡기 쉽지 않음)
- 자발적 협력(voluntary cooperation)이 필요하다.
- 한번의 실수가 모든 시스템에 치명적인 영향을 미친다.
ex 1 . Mutual exclusion 깨지는 문제
V(mutex)
Critical Section // V연산을 먼저 잘못하게 되면, 동시 접근 문제 발생 가능
P(mutex)
ex 2 . Deadlock 문제
P(mutex)
Critical Section
P(mutex) // lock 획득 이후 또 획득하고자 하면, lock 반환이 안되고 계속 0인 상황에서 어느 누구도 critical section에 들어가지 못하는 상황 발생 가능
2) Monitor
- 동시 수행중인 프로세스 사이에서 추상 자료형(abstract data type)의 안전한 공유를 보장하기 위한, high-level synchronization construct
- 즉 어떤 공유데이터를 접근하기 위해서는, monitor라고 정의된 내부의 프로시저를 통해서만 접근할 수 있게 하는 것임.
monitor monitor-name // monitor는 구조체의 형태 : 프로그래밍 언어마다 monitor 지원방법은 다름
// 이러한 형태라면 객체지향 프로그래밍 쪽에서 지원해주는 montior일 것임
{
shared variable declarations // 공유데이터에 대한 선언
procedure body P1(...){ // 공유데이터에 접근하기 위한 함수들
...
}
procedure body P2(...){
...
}
procedure body Pn(...){
...
}
{
initialization code // 초기화
}
}
- 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
- 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 없음.
- 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
: condition X,Y;
// 자원의 개수를 세도록 하는 semaphore변수와 비슷한 역할 (그러나 값을 세지는 않음)
// X라는 자원이 여분이 있으면 바로 접근 가능하게 해주고, 여분이 없어서 기다려야 한다면 그 줄에 가서 기다리도록 하는 함수(wait)을 정의하고, 또 접근을 하고 빠져나갈 때에는 프로세스(signal)을 호출해서, 혹시 기다리고 있는 프로세스가 있다면 빠져나갈 수 있도록 도움
- condition variable은 wait과 signal연산에 의해서만 접근이 가능함.
1) X.wait();
: X.wiat()을 호출한 프로세스는, 다른 프로세스가 X.signal()을 부르기 전까지 suspend된다.
2) X.signal(); // V연산 지점과 비슷
: X.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다.
: Suspend된 프로세스가 없다면 아무런 문제도 발생하지 않는다.
cf ) 프로세스 A가 monitor 내부에서 공유데이터를 접근하는 코드를 실행하고 있던 도중에 CPU를 빼았겼다고 하면, 프로세스 B가 monitor 코드를 접근하고자 했다 하더라도, 프로세스 A는 monitor 내부에 active한 상태로 남아있기 때문에, 프로세스 B는 밖에 있는 entry queue에 줄 서서 기다리게 된다. 프로세스 B는 monitor 내부에 active한 프로세스 수가 0이 될 때 (프로세스 A가 CPU를 얻어서 다 쓰고 나가던가, 프로세스 A가 충족되지 않은 상태에 있어 잠들게 되던가), monitor에 들어가서 실행하게 된다.
3) Bounded-Buffer Problem (Producer-Consumer Problem) - Monitor로 해결
monitor bounded_buffer{
int buffer[N];
condition full, empty; // 공유변수
// condition은 값을 가지지 않고, 자신의 큐에 프로세스를 매달아서 sleep시키거나, 큐에서 프로세스를 깨우는 역할만 함
void produce(int x){ // 생산자
if there is no empty buffer // 비어있는 버퍼가 없다면
empty.wait(); // empty의 줄에 가서 기다림 (blocked상태)
add x to an empty buffer // 빈 버퍼가 하나 추가된 경우, 데이터 집어넣기
full.signal(); // 데이터를 넣었으면, 소비자를 위해 full줄의 하나를 깨워주기
}
void consume(int *x){ // 소비자
if there is no full buffer // 차있는 버퍼가 없다면
full.wait(); // full의 줄에 가서 기다림 (blocked상태)
remove an item from buffer and store it to *x // 버퍼에서 꺼내서, *x에 저장함. (데이터 사용)
empty.signal(); // 데이터를 빼갔으면, 생산자를 위해 empty줄의 하나를 깨워주기
}
}
4) Dining Philosophers Example - Monitor로 해결
monitor dining_philosopher{
enum{thinking, hungry, eating) state[5];
condition self[5]; // 다섯명의 철학자 상태를 공유변수로 표시
void pickup(int i){
state[i] = hungry;
test(i);
if(state[i] != eating)
self[i].wait(); // 줄에 가서 기다리기
}
void putdown(int i){
state[i] = thinking;
test((i+4)%5);
test((i+1)%5);
// 인접 철학자들이 밥을 먹도록 해줌
}
void test(int i){
if((state[(i+4)%5] != eating) && (state[i] == hungry) && (state[(i+1)%] != eating)){
state[i] = eating;
self[i].signal();
}
}
void init(){
for(int i=0; i<5 ; i++)
state[i] = thinking;
}
}Each philosopher :
{
pickup(i); // monitor에 들어가는 함수
eat();
putdown(i); // monitor에 들어가는 함수
think();
} while(1)
| * 유의사항 - 아직 공부하고 있는 문과생 코린이가, 정리해서 남겨놓은 정리 및 필기노트입니다. - 정확하지 않거나, 틀린 점이 있을 수 있으니, 유의해서 봐주시면 감사하겠습니다. - 혹시 잘못된 점을 발견하셨다면, 댓글로 친절하게 남겨주시면 감사하겠습니다 :) |
