운영체제)#12 Process Synchronization

<Background>

■ 프로세스는 동시에 수행될 수 있다

-> 동작을 불완전하게 끝내면서 언제나 인터럽트 될 수 있다.

 

■ 동시에 공유 데이터(shared data)에 접근하는 것은 데이터 비일관성(data inconsistency)을 유발할 수 있다.

 

■ 데이터 일관성(data consistency)을 유지하는 것은 협력적인 프로세스들의 실행 순서를 안정화 하는 기술이 필요하다. (야구게임프로그램)

//야구는 매 턴마다 20명의 선수가 해야 하는 일을 정해주는 순서가 있다.

//각각의 선수는 자기 일을 하는 스레드로 볼 수 있다.

//그 스레드 들은 독립적이지만 상호간의 순서가 있다.

//이를 동기화라고 한다.

 

■ 문제 설명

-> 모든 버퍼를 채우는 consumer-producer 문제를 위한 해결책이 필요하다고 가정해보자.

우리는 전체 버퍼의 숫자 track을 유지하는 integer counter를 가짐으로써 해결 할 수 있다.

처음에, counter는 0으로 설정되어 있다. 이것은 새로운 버퍼를 생성한 후에 producer에 의해 증가된다. 그리고 이것이 버퍼를 소모한 후에 consumer에 의해 감소된다.

//원형 버퍼를 사용 했을 때의 문제점

//모든 버퍼를 다 쓸 수 있는 해결책으로 공유변수를 둔다.

//공유변수의 문제점은 동기화 문제가 생긴다.

 

 

 

<Bounded-Buffer>

■ shared data

 

#define BUFFER_SIZE 10

typedef struct {

...

} item;

item = buffer[BUFFER_SIZE];

int in = 0;

int out = 0;

int counter = 0;

 

 

■ Producer process

■ Consumer process

 

 

■ 수정된 알고리즘

//공유변수 counter가 존재한다.

 

■ The statements

counter++;

counter--;

반드시 atomically하게 수행된다.

 

■ Atomic 동작은 동작이 인터럽트 없이 완전히 수행되는 것을 의미한다. Indivisibe ...

 

■ The statement "count++"는 다음과 같은 기계어로 실행될 수 있다 :

register1 = counter

register1 = register1 + 1

counter = register1

 

■ The statement "count--"는 다음과 같이 실행 될 수 있다:

register2 = counter

register2 = register2-1

counter = register2

//실제 count++, count-- 라는 동작은

//memory에서 count값을 cpu로 불러오고(1)

//cpu에서 값을 연산 해줘서(2)

//그 값을 memory로 돌려준다(3)

//이렇게 총 3가지 명령으로 분리가능하다.

 

■ 만약 producer와 consumer 둘 다 버퍼를 동시 업데이트를 시도하면, 어셈블리어 statements는 아마 interleaved 될 수도 있다.

//앞서 말한 count++의 1,2,3번 명령어와 count--의 1,2,3번 명령어가 섞일 수 있다.

 

■ interleaving은 producer와 consumer 프로세스가 스케쥴이 어떻게 되어있는지에 달려있다.

 

■ counter 변수가 처음에 5라고 가정해보자. interleaving된 statements중 한 개는 다음과 같다.

//3개의 명령이 2개 실행하고 조금 쉬었다가 1개 실행한다고 가정한다.

//원래 의도한 대로라면 counter는 5-> 6-> 5 가 되어야 하는데, 4가 되어버림

//공유변수를 양쪽 스레드가 다 사용을 하려해서 생기는 문제, atomic 하지 못했다.

 

<Race Condition>

■ Race condition :　몇몇의 프로세스 접근 - 그리고 공유된 데이터를 동시에 접근할 때 상황이 발생한다.

공유된 데이터의 최종 값은 어떤 프로세스가 마지막으로 끝났는지에 의존한다.

 

■ Race condition을 막기 위해, 동시에 일어나는 프로세스들은 반드시 동기화(synchronized) 돼야 한다.

//한 번에 한 프로세스만 count를 사용해야 한다.

 

■ 프로세스 P0와 P1은 fork() 시스템 콜을 사용하여 자식 프로세스를 생성한다.

■ 다음 available process identifier(pid)를 표현하는 커털 변수 next_available_pid의 Race condition

 

■ 상호적인 예외(Mutual Exclusion)가 없다면, 같은 pid는 다른 두 개의 프로세스에 할당될 수 있다.

 

<Critical Section Problem> //임계영역

■ n개의 프로세스를 가진 시스템을 생각해보자. {p0,p1,...pn-1}

 

■ 각 프로세스는 segment of code의 임계 영역(critical section)을 가지고 있다.

-> 프로세스는 공통 변수를 테이블을 업데이트, 파일 쓰기를 통해 바꾸는 영역을 가진다. //임계영역

-> 임계 영역(critical section)에서 한 개가 처리되면, 다른 것들은 그 영역에 있을 수 없다.

 

■ Critical section 문제는 이것을 해결하기 위해 프로토콜을 디자인하는 것이다.

■ 각 프로세스는 반드시 entry section안에 critical section에 입장하기 위한 허락을 받아야 한다.

그런데 그것은 critical section뒤에 exit section으로 뒤따라 질 수 있고, 그 다음 remainder section 으로 따라가 질 수 있다. //진입구역, 임계구역, 출구구역, 자유구역

<Critical Section>

■ 일반적인 p1 프로세스의 구조는 다음과 같다.

//entry section은 필요한 셋팅을 하거나, 관련 없는 부분을 처리하는 부분

 

//critical section에서 c++,c--같은 명령을 실행

 

//exit section은 critcal section에 관련된 나머지 일을 한다.

 

//앞선 section들과 관련 없는 다른 일을 실행

 

 

 

 

 

<Solution to Critical-Section Problem> //이러한 3가지 문제를 해결해야함

■ 1. Mutual Exclusion(상호배제) : 만약 프로세스 Pi가 그것의 임계구역에서 실행된다면, 다른 프로세스는 그들의 임계구역에서 실행될 수 없다. //한 프로세스만 임계구역에 들어갈 수 있다.

 

■ 2. Progress(진행) : 만약 임계구역에서 실행되는 프로세스가 없고, 그들의 임계구역에 들어가고자 하는 어떤 프로세스들이 존재하면, 다음으로 임계구역에 들어갈 프로세스의 선택이 무한하게 연기될 수 없다. //무한하게 연기될 수 없고, 진행이 되어야 한다.

 

■ 3. Bounded Waiting(한계 대기) : bound는 반드시 다른 프로세스가 임계구역에 임장하려는 요청이 만들어진 후와 요청이 승인되기 전에 그들의 임계구역에 들어가는 것을 허용하는 시간의 숫자만큼 존재해야 한다. //무한하게 있을 수는 없다.

-> 각 프로세스가 0이 아닌 속도로 실행된다고 가정하자.

-> n 프로세스의 상대적인 속도와 관련해서는 가정하지 않는다.

 

 

 

 

<Algorithm1>

■ 공통 변수

-> int turn = 0;

-> if (turn == i) → Pi가 그것의 임계구역에 들어갈 수 있다.

 

■ 프로세스 Pi

do {

while(turn != i);

critical section

turn = j;

remainder section

} while(1);

 

//초기 I값은 0, turn 값도 0이므로 무한루프에 빠지지 않고 critical section으로 넘어간다.

//그 다음 turn을 j로 바꾼다. 그 뒤로 나머지 섹션을 실행한다.

 

■ mutual exclusion? progress?를 만족 시켰는가?

-> 왜?

//즉, Pi가 임계구역에 들어가 있는 동안에, Pj는 while(turn != j) 줄에서 무한루프를 돌고 있다.

//turn이 i아니면 j만 선택하므로 상호 배제(mutual exclusion)를 만족 한다

 

//초기 turn값이 0인데 Pj가 먼저 실행되면, 무한루프 돌게 된다.

//이 무한 루프는 Pi가 임계영역으로 들어간 뒤 turn값을 바꿔줘야 풀린다.

//무조건 Pi가 먼저이므로 progress, bounded waiting을 만족하지 않는다.

 

//또한 Pi가 응답이 없으면, Pj는 동작할 수 없다.

 

 

 

 

<Algorithm2>

■ 공통변수

-> boolean flag[2]; 초기 flag[0] = flag[1] = false

-> flag[i] == true → Pi가 그것의 임계영역으로 들어갈 준비가 됨

 

■ 프로세스 Pi

//나는 임계구역으로 들어가고 싶다.

//다른 프로세스는 어떤가?

 

//다른 프로세스가 false면 임계구역으로 들어간다.

 

 

//flag를 false로 다시 바꿔준다.

 

//Pi가 remainder section을 수행할 때, Pj는 임계구역으로 들어갈 수 있다.

 

//번갈아서 실행될 필요가 없다.

//둘 다 critical section에 같이 들어갈 일은 없다.

//상호 배제(mutual exclusion)를 만족 한다.

 

//문제점? Pi와 Pj가 짧게 번갈아서 실행된다고 가정

//우연히 동시에 true가 되면 둘 다 while에서 멈춘다.

//progress, bounded waiting을 만족하지 않는다.

 

 

 

  

<Algorithm3 - Peterson's Solution>

■ 문제를 해결하는 좋은 알고리즘 적 묘사

■ 두 개의 프로세스 솔루션

■ load와 store 명령어가 atomic하다고 가정; 즉, 인터럽트 될 수 없다.

 

■ 두 개의 프로세스는 2개의 변수를 공유한다.

-> int turn;

-> Boolean flag[2];

 

■ 변수 turn은 어떤 누구의 turn이 임계구역으로 갈지를 나타낸다.

 

■ flag 배열은 프로세스가 임계구역으로 들어갈 준비가 되었는지 나타낼 때 사용된다. flag[i] = true는 프로세스 Pi가 준비가 되었다는 것을 의미한다.

 

 

<Algorithm for Process Pi>

//세 가지 항목을 모두 만족하는 알고리즘

//tight하게 번갈아서 실행되면, 어떻게 되는지도 고려해보자