운영체제 정리 3. 병행성 : 상호배제와 동기화

병행성 관련 용어

-원자적 연산 : 명령어들로 구성된 함수 또는 액션으로 더 이상 분할할 수 없는 단위 어떤 프로세스도 중간 상태를 볼 수 없고 연산을 중단할 수 없다 이 명령어들은 수행되거나 되지않거나 둘중 하나이다.

-임계영역 : 공유 자원을 접근하는 프로세스 내부의 코드 영역, 두개의 프로세스가 임계영역에 들어가서는 안된다.

-교착상태 : 두개 이상의 프로세스들이 더 이상 진행을 할 수 없는 상태, 각 프로세스가 다른 프로세스의 진행을 기다리면서 대기할때 발생한다.

-라이브락 : 두개 이상의 프로세스들이 다른 프로세스의 상태 변화에 따라 자신의 상태를 변화 시키는 작업만 하는 상태,프로세스들이 열심히 일하는 것처럼 보이지만 실제로는 유용하지 않은 작업들을 하고 있다.

-상호 배제 : 한 프로세스가 공유자원을 접근하는 임계역영 코드를 수행하는 중이면 다른 프로세스들은 공유 자원에 접근하는 임계영역 코드를 수행할 수 없다는 조건이다.

-경쟁상태 : 두개 이상의 프로세스가 공유 자원을 동시에 접근하려는 상태, 최종 수행 결과는 프로세스들의 상대적인 수행 순서에 따라 달라진다.

-기아 : 특정 프로세스가 수행 가능한 상태임에도 매우 오랜 기간 동안 스케줄링 되지 못하는 경우

상호 배제 요구조건

-상호 배제가 강제되어야 한다.

-임계영역 외의 코드에서 수행이 멈춘 프로세스는 다른 프로세스의 수행을 간섭해서는 안된다.

-기아 상태, 교착 상태가 발생해서는 안된다.

-임계영역이 비어있고 임계영역 진입을 원하는 프로세스는 즉시 임계영역에 들어 갈 수 있다.

-프로세스 개수나 상대적인 프로세스 수행 속도에 대한 가정은 없어야 한다.

-임계영역에 들어간 프로세스는 일정시간 내에 임계영역에서 나와야 한다.

기계 명령어 접근 방법의 특성

-장점

-단일처리기 시스템뿐만 아니라 공유 메모리를 사용하는 멀티프로세서 시스템에서도 사용가능하다.

-간단하고 검증이 쉽다.

-서로 다른 변수를 사용하면 여러 개의 임계영역을 지원할 수 있다.

-단점

-바쁜대기를 사용한다. 바쁜대기란 임계영역에 진입하기 위한 허가를 획득할 때까지 변수를 테스트하는 명령을 반복 실행하며 대기하는 것을 말한다. 이로인해 임계영역에 진입하는 것을 대기하고 있는 프로세스는 처리기를 계속 사용하게된다.

-기아가 발생 할 수 있다. 프로세스의 길이나 특성, 대기시간 등을 고려하지 않기 때문에 무한정 기다리는 프로세스가 생길 수도 있다.

-교착상태에 빠질 수 있다.단일처리기 시스템에서 P1이라는 프로세스가 임계영역에 진입했는데 그때 P2라는 P1보다 우선순위가 높은 프로세스가 생겨서 OS가 P2를 스케줄하여 P2에게 자원을 할당하려 할때 P2와 P1이 같은 자원을 사용하려 하면 P2는 상호배제조건에 의해 바쁜대기에 들어가고 이때 계속 처리기를 점유하고 있기때문에 우선순위가 높은 P2로 인해 P1은 다시 스케줄링될 수 없다.

인터럽트 금지

소프트웨어를 이용한 상호배제

-Dekker 알고리즘

-첫번째 시도

turn이라는 전역 변수를 선언하여 turn의 값이 자신의 프로세스 번호와 같으면 임계영역을 수행 할 수 있도록 하는 방법으로 바쁜 대기를 사용한다는 점도 좋지 않지만 느린 프로세스를 기준으로 수행속도가 맞춰지게 된다. 또한 한 프로세스가 실행중에 임계영역 내에서 작업이 중단되면 다른 프로세스는 영구히 기다리게된다.

-두번째 시도

flag를 정의 하여 flag[0]은 P0에, flag[1]은 P1에 대응시키고 임계영역에 진입하려는 프로세스는 flag값을 계속 보다가 값이 false가 되면 자신의 flag값을 true로 만들고 임계영역에 들어가는 방식으로 한 프로세스가 임계 영역 안에서 실패하거나 자신의 플래그를 true로 바꾼 후 임계 영역에 들어가기 바로 전에 실패하면 다른 프로세스는 영구히 블록된다. 또한 상호배제역시 갖추어지지 않았다.

ex)

P0은 while 문장을 실행하여 flag[1]이 false임을 확인

P1은 while 문장을 실행하여 flag[0]이 false임을 확인

P0는 flag[0]을 true로 하고 임계영역에 진입

P1은 flag[1]을 true로 하고 임계영역에 진입

둘다 임계영역에 진입하게 됌

-세번째 시도

만약 P0가 flag[0]를 true로 설정하면, P1이 임계 영역에 들어갔다가 나올 때까지 자신의 임계 영역에 있을 수 없다. P0가 자신의 플래그를 설정할 때 P1이 이미 자신의 임계영역에 있다면 P0는 P1이 임계 영역을 떠날때 까지 while문에서 블록되는 방식으로 상호배제를 보장하지만 만약 두 프로세스가 각각 while문을 실행하기 전에 자신들의 플래그를 true로 설정하게 되면 각 프로세스는 상대방이 임계영역에 들어갔다고 판단하고 이로인해 교착상태가 발생한다.

-네번째 시도

좀 더 각 프로세스가 양보하게 하는 방식으로 문제를 해결하기 위해 각 프로세스는 flag에 임계영역에 들어가려는 의도를 나타내지만 다른 프로세스에게 양보하기 위해 플래그를 재설정할 준비가 되어있는 방식으로 올바른 해결책에 가까우나 결점을 가지고 있다.

ex)

P0는 flag[0]를 true로 설정

P1은 flag[1]를 true로 설정

P0는 flag[1]를 검사

P1은 flag[0]를 검사

P0는 flag[0]를 false로 설정

P1는 flag[1]를 false로 설정

P0는 flag[0]를 true로 설정

P1은 flag[1]를 true로 설정

이러한 순차가 무한히 확장될 수 있고, 프로세스도 임계영역에 들어가지 못할 수 있다. 확률은 적지만 즉 라이브락이 생기게된다.

-피터슨 알고리즘

-데커알고리즘을 진화시킨 버전 책에서는 우아(?)한 해결책을 제안했다고 말한다.

전역 배열 변수 flag가 상호 배제와 관련된 각 프로세스의 위치를 나타내며 전역 변수 turn은 병행 수행에 의한 충돌을 해결해 준다. P0를 예를 들어 알고리즘을 돌려보면 P0이 flag[0]을 true로 설정, P1은 자신의 임계 영역에 들어갈 수 없다. 반면에, 서로 임계 영역에 들어가지 못하도록 방지하는 것도 막을 수 있다. P0가 자신의 while 문에서 블록되어 있다면, 이것은 flag[1]은 true이고 turn = 1임을 의미한다. P0는 flag[1]이 false가 되거나 turn이 0이 되면 자신의 임계 영역에 들어 갈 수 있게 된다.

세마포어

-세마포어란 프로세스간에 시그널을 주고받기 위해 사용되는 정수 값을 의미한다. 세마포어는 initialize, decerment, increment의 세개지 원자적 연산만을 지원하며 Decrement연산은 프로세스를 블록시키고 increment연산은 블록되었던 프로세스를 깨운다. 이러한 세마포어를 카운팅 혹은 일반 세마포어라 한다.

-이진 세마포어 : 0또는 1을 값으로 가질 수 있는 세마포어

-세마포어 연산 종류 

-세마포어 초기화(initialize) : 세마포어는 음수가 아닌 값으로 초기화된다.

-semWait 연산(decerment) : 세마포어 값을 감소시킨다. 만일 값이 음수가 되면 semWait를 호출한 프로세스는 블록되며 그렇지 않으면 계속 수행 될 수 있다.

-semSignal 연산(increment) : 세마포어 값을 증가시킨다. 만약 값이 0이나 음수라면 semWait 연산으로 블록된 프로세스를 깨운다.

-세마포어의 단점

-일반적으로 프로세스가 세마포어를 감소시키기 전까지는 그 프로세스가 블록될지 안될지 알 수 없다.

-단일처리기 시스템에서 프로세스가 세마포어를 증가시키고 블록된 프로세스를 깨우면, 이 두 프로세스 모두 수행 가능 상태되어 누가 먼저 수행될지 알 수 없다.

-세마포어에 시그널을 보낼 때, 우리는 다른 포로세스가 대기 중인지 여부를 알 필요가 없다. 블록된 프로세스의 개수가 0또는 1일 수 있다.

세마포어를 이용한 생산자 소비자 문제 해결 방법

-생산자 소비자 문제는 병행 처리의 특성과 해결 방법을 논의 할 때 자주 사용되는 문제이다. 이 문제는 데이터를 만드는 생산자와 데이터를 사용하는 소비자로 구성된다. 하나 또는 그 이상의 생산자는 데이터를 생성하고, 이것을 버퍼에 저장한다. 소비자는 한 번에 하나씩 버퍼에서 데이터를 꺼내 소비한다. 이 문제의 요구조건은 생산자와 소비자가 동시에 버퍼에 접근 되어서는 안된다는 것이다.

위 그림은 무한 버퍼라고 할 때 일반 세마포어를 이용해서 문제를 해결 한 것이다. 생산자와 소비자는 병행적으로 실행된다. 만약 소비자가 먼저 실행될 경우 세마포어 n의 값이 음수가되면서 블록에 걸리고 생산자가 실행되어 버퍼를 채우며 n의 값을 올려 소비자의 블록을 푼다.

-유한 버퍼 생산자 소비자 문제 해결

 문제무한 버퍼와 같은 원리로 작동을 하며 무한 버퍼와는 달리 유한 버퍼이므로 버퍼가 꽉 찰 때를 표시해줄 수 있는 e값이 있다. e가 꽉찬 상태 즉 e가 음수가 되면 블록이 걸리게 되며 소비자만이 작동하게 된다.

판독자/기록자 문제

-생산자/소비자 문제와 같이 병행성 기법을 테스트할 때 사용하는 문제이다. 판독자/기록자 문제의 조건은 이러하다.

1. 여러 판독자가 공유 데이터를 동시에 읽을 수 있다.

2. 한 순간에는 단 하나의 기록자만이 공유 데이터를 변경할 수 있다.

3. 기록자가 데이터를 변경하고 있는 동안에는 판독자가 그 파일을 읽을 수 없다.

-세마포어로 푼 판독자/기록자 문제(판독자 우선ver)

보기에서는 판독자와 기록자각각 하나만을 보여주지만 판독자와 기록자가 늘어나도 이 방법을 적용할 수 있다. 기록자가 데이터를 갱신 할 때 상호 배제를 위해 wsem을 사용하면, 결국 임의의 한 기록자가 공유 데이터 영역을 사용하고 있는 동안 다른 기록자/판독자는 그 영역을 사용할 수 없게 된다. 기록자와 같이 판독자도 wsem을 사용하지만 다수의 판독자를 허용하기 위해 처음 읽기를 시도한 판독자만 wsem에 대한 semWait를 호출한다. 현재 읽기 중인 판독자가 없을 때는 읽기를 시도하는 최초의 판독자만 wsem을 사용한다는 것이고 그 이후의 판독자는 wsem에 의한 semWait를 호출 하지 않아도 된다는 것이다, 전역 변수 readcount는 판독자의 수를 관리하는 것에 이용되고, 이 변수에 대한 상호배제를 위해 세마포어x가 이용된다.

모니터

-모니터란 프로그래밍 언어 수준에서 제공되는 구성체(라이브러리, 클래스 등)로, 세마포어와 동일한 기능을 제공하고 보다 사용하기 쉽다는 장점을 가지고 있다.

-모니터의 특징

-외부에서 변수에 대한 직접 접근이 허용되지 않으므로 지역 변수는 프로시저(명령문의 집합자세히는 쿼리문의 집합)으로 접근 해야된다.

-프로세스는 모니터의 프로시저 중 하나를 호출하여 모니터로 들어간다.

-한 순간에 하나의 프로세스만이 모니터에 접근 가능하다. 모니터가 이미 사용중이면 그 자리가 빌 때까지 대기한다.

메세지

-메세지란 프로세스의 상호배제시 만족되어야 할 두 가지 요구사항 동기화(상호배제)와 통신(정보교환)인데, 이 두 가지 기능을 동시에 제공하는 대표적인 방식이다. 메세지에는 메세지 전송을 하는 send와 메세지를 받는 receive라는 두가지 기본 기능이 있다.

위의 프로그램에서는 mayconsume과 mayproduce라는 두개의 메일박스를 사용한다. 생산자가 데이터를 만들면 이를 메세지로 mayconsume에 보낸다. 이 메일박스에 적어도 하나의 메세지가 존재하면 소비자는 계속하여 수행될 수 있다. 코드가 시작될 때 mayconsume은 전역 변수 capacity에 의해 용량이 정해지고 mayproduce는 capacity만큼null로 초기화된다.

메세지를 사용하면 단지 시그널만을 전달하는 것이 아닌 데이터를 전달 할 수 있고 또 매우 유연하여 두 개의 메일 박스에 접근만 가능하면 다수의 생산자 소비자도 가능하다. 또 한 분산환경에서도 사용이 가능하다.