임계영역(Critical Section)문제의 Software Solution
Dekker's Algorithm
두 개의 프로세스
Eisenberg , McGuire's Algorithm
n개의 프로세스에 대해서 waiting 타임이 n-1을 lower bound를 가짐
Peterson's Algorithm
임계구역(Critical Section) 문제를 소프트웨어적으로 해결하기 위한 알고리즘
현대 컴퓨터 구조가 load, store와 같은 기본적인 기계어를 수행하는 방식이기 때문에 피터슨의 해결안(소프트웨어적인 방법)은 임계 구역 문제 해결을 보장할 수 없다.
상호 배제, 진행, 한정된 대기의 요구 조건을 중점으로 수행하는 소프트웨어를 설계함.
critical section문제를 가장 완전하게 해결한 알고리즘
2개의 프로세스(n개도 가능) critical section과 remainder section을 왔다갔다하는 상황:
while 문돌때 critical section, remainder section이 있음
flag[i] i = true; 부분~ -> entry 섹션
flag[i] = false; -> exit 섹션
=> 레이스 컨디션 방지
int turn;과 boolean flog[2] (깃발 두 개, turn 하나) 변수 선언
예)두 집에 있는 개를 동시에 데꼬나오면 두 개가 싸우니까 산책중일땐 한쪽 집에 플래그를 세우고 다른 집 개는 집에있음, 산책이 끝나면 깃발내리고 다른 집 깃발을 올리고 산책시킴
플래그 0은 Pi꺼 플래그 1은 Pj꺼
flag[i]에다가 true -> i가 나 지금 산책할거야
turn 은 j로 바꿈 -> 다음은 네 차례야
while (flag [j]가 true고 turn이 true이면 -> j가 산책중
critical section을 빠져나오면 플래그도내리고 turn도 차례바꿔줌 -> i차례
산책 후 flag[i] -> false로 바꿔줌
=> pi 와 pj는 절대 동시에 critical section 진입하지 않는다.
pthread_create로 두 개의 스레드 create함 (producer, consumer)
producer 실행이 끝날때까지 기다리다가 consumer가 실행되기:
producer 쪽에서 ciritical section 빠져 나올때 flag[0]을 false로 딱 바꿔주는 순간 -> 대기하고 있떤 consumer 쪽 while(flag[0] && turn ==0) 을 빠져나온 후 자기 critical section 실행
#include <stdio.h>
#include <pthread.h>
#define true 1
#define false 0
int sum = 0;
int turn; // 전역변수
int flag[2]; // 전역변수
int main()
{
pthread_t tid1, tid2;
pthread_create(&tid1, NULL, producer, NULL); // 스레드 create
pthread_create(&tid2, NULL, consumer, NULL); // 스레드 create
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
printf("sum = %d\n", sum);
}
void *producer(void *param)
{
int k;
for (k = 0; k < 10000; k++) {
/* entry section */
flag[0] = true; // flag[0] : producer
turn = 1; // 다음차례 : consumer (1)
while (flag[1] && turn == 1) // flag 1이고 turn 1차례면 대기
;
/* critical section */ // while 문 빠져나오면 여기 실행
sum++;
/* exit section */
flag[0] = false; // 나올때 false 로 바꿔줌
/* remainder section */
}
pthread_exit(0);
}
void *consumer(void *param)
{
int k;
for (k = 0; k < 10000; k++) {
/* entry section */
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0) // floag[0]이 돌고있으면 true니까 여기걸림
// false 해주는순간 빠져나와 다음꺼진입
;
/* critical section */
sum--;
/* exit section */
flag[1] = false;
/* remainder section */
}
pthread_exit(0);
}=> 동기화 Synchronization 되긴하지만 피터슨의 해결안이 소프트웨적으로 완벽히 동기화를 보장할 수 없다.
근데 항상 성공하지가 않음 .. 10000번 돌면서 실패해서 값이 0이 나오지 않는다.
완벽하지 않음
기계어 레벨로 생각해야함
turn =1 ; 을 확인하고 while (flag[1] && turn ==1 확인하는 과정에서 컨텍스트스위칭 나면 권한 얻는과정이 문제가 생긴다.
=> 피터슨 솔루션 동작x
그래도 피터슨 solution 제시되는 이유
임계 구역 문제를 해결하는 것의 좋은 알고리즘적인 설명을 제공
상호 배제, 진행, 한정된 대기의 요구사항과 관련된 복합적인 개념을 설명할 수 있다.
개념적으로는 완벽히 상호배제, 진행, 한정된 대기를 해결한다.
코드를 통해 개념을 알기는 좋다. 상호배제(mutual exclusion), 진행(progress) (dead lock안됨), 대기한정(bounded waiting)(기아 안됨) 을 다 증명할 수 있다.
-> producer는 flag[j]==false 이고 turn = i 이어야만 실행하니까 상호배제, 진행, 대기한정 개념적으로 해결
상호 배제(Mutul Exclusion) 조건:
2개 이상의 프로세스가 동시에 공유자원에 접근하는 것을 예방하는 것
진행(Progress, No DeadLock) 조건
진행이 되지 않으면 프로세스들끼리 임계구역 들어가기위해 다른 프로세스의 해제를 기다리기 위해 계속 대기하게된다. -> 교착상태(DeadLock) 가 없어야한다.
한정된 대기(Bounded-Waiting, No Starvation) 조건
한 프로세스가 대기중일때 우선순위가 밀려 다른 프로세스가 계속선점해서 무한 대기한다. -> 기아(starvation) 가 없어야한다.
하드웨어적 솔루션
기계어 레벨에서 막 컨텍스트스위치가 일어나면 원자성을 보존해주지 못한다.
하드웨어 인스트럭션 사용가능
memory barriers or fences
hardware instructions
atomic variables 원자성있게
Atomicity
원자성 : 더이상 쪼갤 수 없다.
atomic operation : 원자적 동작 , 더 이상 쪼갤 수 없는 uninterruptable한 오퍼레이션 단위 인터럽트를 걸 수 없다.
어떤 인스트럭션 자체를 스페셜 하드웨어 인스트럭션으로 만들어서 -> atomic 한 instructions으로 만들자
예) a++ 같은거 3개의 인스트럭션으로 나누지말고 cpu 회로를 잘 만들어서 원 클락에 해결하게 하자 // i , j 를 swap 하는 작업같은 것
-> test_and_set() , compare_and_swap()
위와 같은 명령으로 하드웨어 인스트럭션을 만들었다고 생각하면 단위 오퍼레이션이 된다. ->인터럽트 안됨!
전역변수 lock
데드락, 기아 다 해결되는건 없음, 적어도 상호배제는 해결된다.
Atomic Variable
compare_and_swap() instruction 을 atomic variable로 만든 도구로 사용한다.
single variable 의 race condition 발생하면 이걸 mutual exclusion 할 수 있는 atomic operation을 만들기는 쉽다.
public class Peterson1 {
static int count = 0;
static int turn = 0;
static boolean[] flag = new boolean[2]; // 플래그
public static void main(String[] args) throws Exception {
Thread t1 = new Thread(new Producer()); // 스레드두개 생성
Thread t2 = new Thread(new Consumer());
t1.start(); t2.start();
t1.join(); t2.join();
System.out.println(Peterson1.count);
}
}
static class Producer implements Runnable {
@Override
public void run() {
for (int k = 0; k < 10000; k++) {
/* entry section */
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1)
;
/* critical section */
count++;
/* exit section */
flag[0] = false;
/* remainder section */
}
}
}
static class Consumer implements Runnable {
@Override
public void run() {
for (int k = 0; k < 10000; k++) {
/* entry section */
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0)
;
/* critical section */
count--;
/* exit section */
flag[1] = false;
/* remainder section */
}
}
}-> 오류 계속 생김// 결과: 1, -2, -1, 0 ..
컨택스트 스위칭을 카바하지 못함
내부적인 구조는 자바가 알아서하겠지만 'flag는 Atomic변수다'를 알아야함
Atomic 변수이기 때문에 read, write 할때 인터럽트(컨텍스트 스위치)가 발생하지 않는다.
import java.util.concurrent.atomic.AtomicBoolean;
// 원자 변수 사용 , 자바 제공
public class Peterson2 {
static int count = 0;
static int turn = 0;
static AtomicBoolean[] flag; // AtomicBoolean으로 선언
static { // 스태틱 생성자 , 이 클래스 생성될때 초기화
flag = new AtomicBoolean[2];
for (int i = 0; i < flag.length; i++)
flag[i] = new AtomicBoolean(); // atomicBoolean 두개 생성
}
}
static class Producer implements Runnable {
@Override
public void run() {
for (int k = 0; k < 100000; k++) {
/* entry section */
flag[0].set(true); // set함수 이용
turn = 1;
while (flag[1].get() && turn == 1) // get메소드 사용
;
/* critical section */
count++;
/* exit section */
flag[0].set(false);
/* remainder section */
}
}
}
static class Consumer implements Runnable {
@Override
public void run() {
for (int k = 0; k < 100000; k++) {
/* entry section */
flag[1].set(true); // set 메소드
turn = 0;
while (flag[0].get() && turn == 0) // get 메소드
;
/* critical section */
count--;
/* exit section */
flag[1].set(false);
/* remainder section */
}
}
}=> 결과 계속 0나옴 // 동기화 성공
