[운영체제] 병행 프로세스, 상호배제와 동기화, 임계영역

-병행 프로세스 개념

• 프로세스 여러 개가 동시에 실행되는 것.

• 독립적으로 작업을 수행, 다른 프로세스와 협력하며 특정 기능 수행
• 프로세스 간 교신이 필요

• 상호 작용

• 제한된 자원을 공유하기 위함이며, 상호 작용하는 프로세스는 순서에 맞게 실행되도록 동기화 되어야함

 

-다중 프로세싱 시스템은 프로세스 동기화 알고리즘이 필요

• 프로세서들이 모든 입출력 장치와 메모리를 참조 가능.
• 동시에 동일한 자원에 접근할 경우 충돌이 발생할 경우 이를 해결

 

-상호배제와 동기화

• 상호배제 (Mutual Exclusion)

특정 공유 자원을 한 순간에 한 개의 프로세스만 사용할 수 있을 때, 프로세스 하나가 공유 데이터에 접근하는 동안 다른 프로세스가 해당 데이터를 접근할 수 없게 하는 것.

• 프로세스 간 동기화

공유자원을 동시에 사용하지 못하게 실행을 제어하는 기법

순차적으로 재사용 가능한 자원을 공유하기 위해 상호작용하는 프로세스 사이에서 나타남.

 

-ATM기 예제 프로세스

-생산자/소비자 프로세스

-생산자와 소비자의 공유 버퍼

생산자는 counter++ 소비자는 counter--

-두 코드의 동시 수행시 counter값이 맞는지 기계어로 작성 확인

-생산자, 소비자 프로세스가 병행 실행되는 경우

-동기화 실행 방법

동기화를 실행시키기 위해서 임계영역이라는 것을 사용한다.

• 임계 영역

공유 변수를 어느 한 순간에 한 프로세스만 조작할 수 있도록 한다.

• 상호 배제

예에서 counter를 조작하는 부분을 임계영역으로 설정, 상호 배제함.

ex)비행기 활주로가 임계영역이 될 수 있음.

 

-임계구역(Critical Section: CS)

• 공유 메모리가 참조되는 프로그램의 부분(데이터나 데이터 구조)으로 다수의 프로세스가 접근 가능한 영역이면서 한 순간에 하나의 프로세스만 사용할 수 있는 영역(공유 자원의 독점을 보장하는 코드 영역)을 의미.
• 하나의 프로세스가 공유 데이터를 접근하는 코드를 실행할 때에 그 프로세스가 임계구역에 있다라고 정의.

• 임계영역 내에서 빠른 속도로 작업 수행, 한 프로세스가 오랫동안 머무르면 안된다.
• 프로세스가 무한 루프 등에 빠지지 않도록 관리

-상호 배제(Mutual Exclusion)

다중 프로세서 환경에서도 임계구역에서 실행하고 있는 프로세스는 오직 하나만 있어야 한다.

 

-진입 상호 배제

• 프로세스 하나가 임계 영역에 다른 프로세스가 임계영역에 들어가지 못하게 하는 것.
• 임계 영역에 들어가기를 원하는 프로세스는 진입 상호배제를 수행해야함.

• 프로세스가 접근하지 않은 임계 영역은 잠금 상태
• 프로세스는 임계 영역에서 작업을 수행하기 전에 키를 얻어 임계 영역의 잠금 상태를 해제해야함.
• 프로세스가 키를 반환할 때까지 다른 모든 프로세스에 대해 잠김 상태 유지

• 

  임계 영역을 이용한 상호배제

 

-임계 구역(critical section) 문제

• 문제를 해결하려면 프로세스 동기화 프로토콜을 설계해야 한다.
• 병행 프로세스의 실행 결과가 실행 순서에 상관없이 일정하도록 프로세스 상호간에 협조하는 프로토콜을 설계

 

-병행 프로세스의 전형적인 구조

• 진입영역(진입코드)

  - 각 프로세스는 접근하려는 자원의 임계영역에 들어갈 수 있는지 여부를 미리 요청해야 하며, 이를 코드로 구현한 부분이다.

• 출구영역

  - 임계 영역에서 수행을 마치고 나갈 프로세스를 선택.

• 잔류영역

  - 진입영역과 출구영역을 제외한 나머지 영역으로, 임계영역을 마치고 나와 수행함.

 

-임계영역 문제의 기본 가정

• 각 프로세스는 0이 아닌 속도로 실행된다.
• n개의 프로세스의 상대적인 실행 속도에 대한 가정은 없다.
• n개의 프로세스의 실행순서에 대한 가정은 없다.
• 많은 cpu가 존재할 수 있다.
• 동일한 메모리 영역을 동시에 접근할 수 없도록 제어하는 메모리 하드웨어가 있다.
• 임계 구역 문제에 대한 해결책을 찾는 것은 진입 구역과 출구 구역의 코드를 정의하는 것이다.

 

-임계영역 문제 해결책에 대한 3가지 요구조건

• 상호배제(Mutual Exclusion)

항상 최대한 하나의 프로세스만이 임계구역에서 실행할 수 있다.

한 프로세스가 임계구역에 있으면 다른 프로세스는 임계구역에 진입할 수 없다.

• 진행(Progress)(vs 과잉차단)

임계구역에 프로세스가 없고 다른 프로세스들이 임계 구역 진입을 요구할 때에 진입 프로세스 선택은 무기한 연기될 수 없다.

• 한계 대기(Bounded Waiting)(vs 무한대기)

하나의 프로세스가 임계 구역 진입을 요청한 후에 진입이 허용될 때까지 진입을 기다리는데 한계를 두어야 한다.

그렇지 않으면 진입 요청한 프로세스느 기아상태가 될 수 있다.

 

임계영역 문제해결(SW - 소프트웨어 해결책)

-알고리즘 1

• 구현 방식

한 개의 공유변수(turn)를 사용하여 해결.

두 개의 프로세스(P1, P2)가 교대로 실행됨

• 임계영역 진입 turn 값에 따라 진입 여부
• 프로세스는 반드시 한 번씩 번갈아 들어갔다 나와야 함.
• 상호 배제 조건 만족, 진행 조건을 충족시키지 않음.

-알고리즘 2

• 두 개의 변수를 사용해 상호배제를 해결

boolean flag[2];

• 상호배제조건 만족, 진행 조건은 만족하지 않음.

while 순환문에서 무한루프

임계 구역에 들어갈 수 있는지 구분할 수 있음.

 

-데커(Dekker) 알고리즘

• Bool flag[2] 와 int turn의 공유 변수를 가짐

초기값은 flag[0] = flag[1] = false이고, turn = 0 또는 1의 값을 가짐.

• Pi의 구조

임계영역에 들어가려면 falg[i]=true로 설정한 후, Pj가 임계영역에 들어가려 하거나 이미 임계영역에 있는지 확인한다.

Pj가 임계구역에 있지않고 들어가려 하지도 않으면 flag[j]=false, Pi가 임계영역으로 진입.

임계영역에서 나오는 Pi프로세스는 빠져나옴 flag[i]=false을 알리고, turn은 기회를 양보하기 위해서 j로 함.

데코 알고리즘 사용 예

-데커의 알고리즘 특징

특별한 하드웨어 명령문 필요 없음

임계 영역 바깥에서 수행중인 프로세스가 다른 프로세스들이 임계 영역 진입을 막지 않음

임계 영역에 들어가기를 원하는 프로세서를 무한정 기다리게 하지 않는다.

 

-피터슨 알고리즘

• 프로세스들은 boll flag[2], int turn의 공유변수를 가진다.
• Pi의 구조

• 임계영역에 들어가려면 먼저 flag[i]=true하여 임계영역에 들어가고 싶다는 의사 표시
• trun=j로 설정한 후, 프로세스 j가 임계영역에 들어갈 의사가 없다면 flag[j]=false 임계영역에 들어갈 수 있음.
• 두 개의 프로세스가 동시에 임계영역에 진입하려고 한다면 turn변수가 늦게 수행된 프로세스가 기회를 양보한다.
• 임계영역에서 나오는 프로세스는 flag[i]를 false 함으로써, 다른 프로세스가 임계영역에 들어가도록 허용한다.

-이러한 소프트웨어 해결책의 단점

• 임계구역에 진입하기를 원하는 프로세스는 busy waiting 한다. ( 필요없이 cpu시간을 낭빟나다.)
• 임계 구역이 긴 경우에는 임계 구역 진입을 기다리는 프로세스를 대기 상태로 전환하는 것(blocking이 효과적이다.

-기타 유용한 상호배제 알고리즘

 

-임계영역 문제 해결(HW - 하드웨어적 임계영역 문제 해결)

• 명령어 확장 : 같은 메모리 영역에 2가지의 동작은 원자적으로(atomically) 실행하는 명령어 제공

기계를 비교하거나 단어 내용을 검사 및 수정 또는 내용을 바꾸는(Swap)명령을 사용하여 임계영역 문제 해결

 

원자적 연산

: 중단 없이 실행하고 중간에 다른 사람이 수정할 수 없는 최소 단위 연산, 메모리의 1비트에서 작동하고, 대다수 기계에서 워드의 메모리 참조, 할당은 원자적이지만 나머지 많은 명령은 원자적이지 않다.

 

-Test-And-Set을 이용한 상호배제 알고리즘

• 단일 프로세서 또는 메모리를 공유하는 다중 처리 환경과 관계없이 적용되며, 간단하여 쉽게 적용된다는 장점을 가진다.
• 임계영역에 진입하려는 프로세스에 바쁜 대기가 발생.
• 무한 연기 가능성이 발생할 수는 있지만 프로세스 수가 많으면 거의 발생하지 않음.

• 

  TestAndSet을 이용한 상호배제

TestAndSet 명령어의 장단점

-하드웨어 해결책의 장단점

• 장점

• 임의 개수의 프로세스에 적용 가능
• 단일 프로세스와 공유 메모리 기반 다중 프로세스에 적용 가능
• 간단하고 검증 쉬움
• 다중 임계영역 지원

• 단점

• 바쁜 대기
• 기아상태 발생 가능
• 교착상태 발생 가능
• 응용 프로그래머가 사용하기 복잡

 

-운영체제는 프로세스 동기화를 위한 도구를 제공한다.

• 세마포어
• 모니터

-세마포어

• 복잡한 문제에 있어서 상호배제를 해결하기 위한 동기화 도구(운영체제가 제공)

• 다익스트라가 상호배제의 문제를 극복하기 위해 제안함.
• 세마포어의 유명한 예 ' 열차의 진행 가능 여부'를 나타내는 차단기.

-차단기 올라감 : 정지/대기(운영체제는 자원이 없어 기다리는 경우)

-차단기 내려감 : 진행(프로세스가 해당 자원을 사용할 수 있는 자유 상태)

 

-세마포어 정의

프로세스 동기화 문제 해결을 위한 두 가지 연산(P, V)

-세마포어 사용(중요)

세마포어 사용 방법

-세마포어 종류

• 이진 세마포어

세마포어 S를 상호배제에 사용, 1 또는 0으로 초기화, P와 V의 연산 교대 실행

• 계수 세마포어

유한한 자원에 접근 제어 가능, 여러 번 획득, 해제할 수 있도록 count 자원의 사용 허가 값으로 사용

사용 가능한 자원 수로 초기화하므로, count를 초기의 세마포어 수로 초기화시킨다.

-생산자-소비자 문제를 세마포어로 해결하는 법

-읽기-쓰기 문제

-세마포어 구현

• 이진 세마포어는 0, 1값만 가짐. (Mutex: 동기화 대상이 하나일 때)
• 교착상태 발생 가능

영원히 서로만을 기다리면서 생을 마감할 프로세스들

 

• 바쁜 대기 발생 가능

한 프로세스가 임계 영역에 있을 때, 임계영역에 들어가기를 원하는 다른 프로세스가 진입 코드를 계속 순환하여 프로세스 시간 낭비함.

-모니터

-모니터의 구조

 

출처 : 저서명: 운영체제 개정 3판, 저자: 구현회, 출판사: 한빛아카데미, 발행년: 2017