프로세스 동기화1

Sirius·2024년 9월 1일

데이터의 접근

경쟁 상태(Race Condition)

1) 같은 메모리를 공유하는 멀티 프로세서 시스템(주체: CPU)

일반적으로 프로세스들은 각자 하나의 주소공간이 있다.(Virtual Memory) 따라서 Race Condition이 발생하지 않는다.
그러나 공유 자원에 접근하는 경우에 Race Condition이 발생한다.

S-box(메모리 주소공간)를 공유하는 E-box(CPU 프로세스)가 여럿있는 경우 Race Condition의 가능성이 있다.

Multiprocessor System에서 하나의 메모리를 각각의 CPU가 공유하고 있다면 하나의 CPU가 A데이터를 읽어간 동안에 또 다른 CPU가 A데이터를 읽어가는 경우이다.

2) 커널 내부 데이터를 접근할때

여러 프로세스나 커널 쓰레드가 커널 내부 데이터에 동시에 접근할 때도 경쟁 상태가 발생할 수 있다.

OS에서 Race Condition은 언제 발생하는가?

전부다 커널 데이터와 관련(공유자원)

1) kernel 모드 수행중 인터럽트 발생시 (하드웨어 인터럽트)

갑자기 인터럽트가 발생했는데 이 인터럽트 처리루틴이 동일한 공유 데이터에 접근하는 경우이다(기본적인 상황)

해결점: 먼저 하던일 다 끝내기 전까지 인터럽트를 받아들이지 않는것이 Race Condition의 해결점이다.

2) 프로세스가 System Call을 하여 커널모드로 수행중인데 문맥교환이 일어난 경우(타이머 인터럽트 -> 문맥교환)

해결점: 프로세스가 커널모드에 있을때는 할당시간이 끝나도 CPU를 뺏기지 않도록 한다.

3) 멀티프로세서에서 shared memory 내의 kernel data 접근

해결점1: 커널 전체에 락을 거는 방법
한번에 하나의 CPU만이 커널에 들어갈 수 있다. lock을 걸고 데이터를 변경, 데이터 변경 후 lock을 푼다.

해결점2: 공유 데이터별로 락을 건다(Detail)
커널 내부에 있는 각 공유데이터에 접근할때마다 그 데이터에 대한 lock/unlock을 하는 방법

프로세스 동기화(Process Synchronization) 문제

공유데이터의 동시 접근은 데이터의 불일치 문제(inconsistency)를 발생시킨다.
일관성 유지를 위해서는 협력 프로세스 간의 실행순서를 정해주는 메커니즘 필요(접근막음)

Race Condition: 데이터의 최종연산 결과는 마지막에 그 데이터를 다룬 프로세스에 의하여 달라짐
-> 프로세스 동기화가 필요하다.

Critical-Section Problem

하나의 프로세스가 critical section에 있을때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 함 -> 기다려야 한다.

프로세스의 일반적인 구조

do{
	entry section; //critical section으로 들어감(lock을 건다.)
    critical section;
    exit section;//critical section에서 나옴(lock을 푼다.)
    remainder section;
}while(1);

Critical Section 문제를 풀기위해 만족해야할 조건 3가지

1) 상호 배제(Mutual Exclusion)
: 프로세스가 Critical Section에 들어가 있으면 다른 프로세스는 Critical Section에 못 들어감

2) 진행(Progress)
: Critical Section에 아무도 들어가 있지 않은 상황에서 내가 들어가고 싶어하면 넣어줘야 함

3) 유한 대기(Bounded Waiting)
: 특정 2개의 프로세스가 번갈아가면서 critical section에 들어가서 나머지 1개의 프로세스가 critical section에 들어가지 못하는 상황일때 횟수의 한계를 준다.

1) Solved 알고리즘 1

turn=0 -> p0프로세스
turn=1 -> p1프로세스

int turn;
turn=0;
do{
	while(turn!=0);
    critical section
    turn=1;
    remainder section
}while(1);

내 차례가 아닌동안에는 while문 돌면서 기다린다(turn이 0이 아닌경우)
그러나 turn이 0이 되면 critical section으로 들어간다.
critical section에서 나오면 상대방 차례(p1)으로 바꿔준다.

문제점: 상호 배제는 만족하지만 진행이 만족되지 않는다.

이 알고리즘은 두 프로세스가 동시에 critical section에 들어가려고 할 때, 하나의 프로세스가 반드시 다른 프로세스가 나올 때까지 기다려야 한다.
따라서 프로세스 0이 크리티컬 섹션에 들어갔다가 빠져나오면서 turn을 1로 바꿔도 고정으로 turn!=0을 박아 놓았기 때문에 프로세스 1(turn=1)이 무한대기상태에 빠진다.
따라서 고정된 상수가 아니라 flag 변수로 설정하는 것이 필요함!

2) Solved 알고리즘 2

boolean flag[2];
initially flag[모두] = false; // 처음은 모두 들어가고 싶은 상태가 아니다.

do{
	flag[i] = true; // 자기가 들가고 싶으면 자신의 flag true로 만든다.
    while(flag[j]); // 상대방 flag면 무한반복
    critical section
    flag[i]=false; // 나올때 자신의 flag를 false로 바꿈
    remainder section
}while(1);

문제점: pi가 flag를 든 상태에서 CPU를 뺏긴다. pj가 CPU를 받아서 자신의 flag를 든다. ciritical section에는 들어가지 못하고 깃발만 2개인 상황이 된다.
즉 상대방이 문맥교환으로 CPU를 가지게 되면 깃발이 2개여서 둘다 critical sectin에 진입하지 못하게 된다.

CPU를 뺏기는 타이밍은 다 읽고 이제 쓰려고 할때 뺏긴다.

3) Solved 알고리즘 3: Peterson 알고리즘

중간에 CPU를 뺏길 수 있음을 고려해서 알고리즘을 짰다.
turn과 flag가 모두 등장

do{
	flag[i] = true; // 깃발을 들어서 의사표현
    turn = j; // turn을 상대방 turn으로 바꿈
    while(flag[j] && turn==j); // 상대방이 깃발을 들고있고, 상대방의 차례인지 체크(turn)
    critical section // 아니라면 내차례이므로 진입
    flag[i]==false; // 마치고 깃발내림
    remainder section
}while(1);

앞의 3가지 조건을 모두 만족한다.
그러나 Busy Waiting의 문제점이 있다(while 루프)

Synchronization Hardware

데이터를 읽는 것, 데이터를 쓰는것을 하나의 인스트럭션으로 처리할 수 없기에 문제가 발생했던 것이다.
다읽고 이제 쓰려고 할때 뺏기는거지 읽는 도중에 뺏기지는 않는다.
만약 하나의 인스트럭션으로 위에것이 실행가능 하다면 적어도 인스트럭션 하나가 실행되는 도중에 CPU를 빼앗기지 않는다. (Test_and_set이 하나의 인스트럭션)