[운영체제] 피터슨 알고리즘(Peterson's algorithm)

 

 

 

 

 

알고리즘 개요 및 소개

 

피터슨 알고리즘(Peterson's algorithm) 알고리즘은 임계구역에 대한 고전적인 소프트웨어 기반 해결책을 설명한다.

임계구역 문제를 해결하기 위한 좋은 알고리즘적인 설명을 제공하고 상호 배제, 진행, 한정된 대기의 요구 조건을 중점으로 다루는 소프트웨어를 설계하는데 필요한 복잡성을 잘 설명하는 알고리즘이며 임게구역 문제를 해결하기 위한 3가지 조건을 모두 만족하는 알고리즘이다.(운영체제 10판, 퍼스트북)

 

 

피터슨 알고리즘 소스코드

 

문제점

이 소스코드는 현대 컴퓨터에서는 정상 작동하지 않는 문제가 있다. 현대 컴퓨터 구조가 load와 store 같은 기본적인 기계어를 수행하는 방식 때문에 Peterson의 해결안이 이러한 구조에서 올바르게 실행된다고 보장할 수 없다.(운영체제 10판, 퍼스트북)

 

이 문제를 해결하기 위해서는 소스코드의 순서가 바뀌는것을 방지해야한다.

 

의존성이란?

어떤 코드를 병렬화한다고 할 때, 어떤 조건을 만족하게 해야 올바르게 작동하는 병렬 코드를 만들 수 있을까?

이 문제에 해단 해답은 프로그램 코드가 실행되는 순서에 달렸다. 올바른 병렬 프로그램은 역시 순서를 지켜가며 실행된다. 이 순서를 결정짓는 요소가 바로 의존성이다. (프로그래머가 몰랐던 멀티코어 CPU 이야기)

 

의존성(dependence)의 종류는 2가지가 있다.

 

1. 데이터 의존성(data depedence)

   두 명령어 사이에서 일어나는 데이터 의존성은 읽기/쓰기의 순서에 따라 RAW, WAW, WAR으로 구분이 가능하다.

 

2. 컨트롤 의존성(control dependence)

    IF문과 같은 조건 분기문으로 인해 명령어 사이에 의존성이 만들어지는 것을 컨트롤 의존성이라 한다.

 

3. 메모리 의존성(memory dependence)

    포인터로 인해 생기는 의존성을 메모리 의존성이라 한다.

 

4. 루프 전이 의존성(loop-carried dependence)

    데이터 의존성은 for, while과 같은 루프에서도 발생할 수 있다 이러한 의존성을 루프 전이 의존성이라 한다.

 

해결방법- Volatile 키워드를 사용해서 메모리가 레지스터에 올라가는 것을 막자

다음의 코드가 어떻게 작동할지 생각해보자

 

코드를 봤을 때에는 별다른 문제가 없어 보이고 정상적으로 10이라는 값이 나올 거 같다. 하지만 이 코드는 정상적으로

작동하지 않는다. 그러면 이번에 flag변수를 volatile 키워드를 사용해서 다시 작동시키면 어떻게 될까

이번에는 정상적으로 원하는 값이 나온다 그 이유는 컴파일러가 최적화를 진행하기 때문이다. 비주얼 스튜디오에서

어셈블리어 코드를 사용해서 확인해보면 코드가 다른 것을 확인할 수 있다.

확인하는 방법은 디버그 상태에서 디버그-창-디스 어셈블리를 클릭하면 확인할 수 있다.

왼쪽은 volatile 사용하기 전이며 오른쪽은 사용한 후이다.  어셈블리 코드를 잘 모르더라도 왼쪽 코드는 좀 이상하다는 것을 알 수 있다. 이렇게 컴파일러는 컴파일할 때 판단을 해서 최적화를 진행하고 flag 변수를 매 반복문마다 확인하지  않기 때문에 무한 반복문에 걸리게 되는 것이다.  그렇기 때문에 volatile 키워드를 사용해 매 반복문마다 변수를 확인할 수 있게 해야 하며 이것을 메모리 가시성 문제라고도 한다.

 

해결방법- 메모리 펜스를 사용해서 CPU가 코드의 순서를 바꾸는 것을 막자

volatil 키워드를 사용했으니 컴파일러는 처리했지만 아직 문제가 더 남아있다. 바로 CPU의 Out-of-Other 문제이다.

Out-of-Other이란 CPU가 최적화를 통해서 서로 의존성이 없다고 판단하면 코드의 순서를 마음대로 바꾸는 것을 말한다.

이 문제는 아무리 어셈블리 코드를 확인해도 알 수가 없다. 

 

이 경우의 문제점은 코드의 순서가 바뀜으로 인해 피터슨 알고리즘에서 flag [0]=true 부분과 turn=1 부분의 순서가 바뀌게 되며 상호 배제가 깨지기 때문에 원하는 값이 나오지 않게 된다. 그렇기 때문에 이 코드 사이에 메모리 펜스를 사용해야 하며 

std::atomic_thread_fence(std::memory_order_seq_cst) 명령어를 사용해 순서가 중요한 코드의 순서를 지키도록 해야 한다.

 

 

위의 문제를 해결한 피터슨 알고리즘 소스코드

피터슨 알고리즘이 정상 작동하는 것을 확인할 수 있다.

 

후기

피터슨 알고리즘은 소프트웨어적인 방법으로 상호 배제를 하는 알고리즘으로 유명한 알고리즘이다.

예전 학부생 시절 배웠던 내용을 다시 정리하면서 복습을 진행하였다.  여기에서는 컴파일러와 CPU의 최적화로 인한 문제를 설명했지만 멀티스레드에는 캐시 문제나 ABA 문제 등이 남아있다. ABA문제는 더 공부를 진행 후 진행해볼 예정이며 다음에는 하드웨어적 명령인 CAS(Compare_And_Set)을 사용해서 동기화를 진행해볼 예정이다.

 

출처 및 레퍼런스

-Book: 운영체제 10판(퍼스트북)-

-Book: 프로그래머가 몰랐던 멀티코어 CPU 이야기

-수업시간에 배웠던 내용

 

관련 글

[운영체제(Operator System)] - [운영체제] 임계구역( Critical Section)