병행 프로세스와 동기화

병행 프로세스

병행 프로세스는 다른 프로세스의 상태를 전혀 모르는 상태로 실행한다. 이것을 병행 프로세스의 비동기성이라고 한다. 병행 프로세스가 비동기적으로 실행될 때, 공유 자원에 접근하는 경우 데이터의 무결성이 훼손될 수 있다. 따라서 중간에 싱크가 필요한 경우, 운영체제가 개입하여 적절한 처리가 필요하다.

공유된 자원 접근의 rule

• 한 번에 한 프로세스만이 접근하도록 하고
• 해당 자원에 대해 의도했던 실행을 완료하도록 보장한다.

프로세스가 공유 자원에 접근할 때 처리할 것

• count라는 변수에 프로세스 A와 프로세스 B가 접근하는 상황에서,
• A의 count에 대한 조작 중 CPU가 B로 넘겨지더라도
• B의 count에 대한 조작은 허용되어서는 안된다.

경쟁 상태

• 프로세스들이 공유 데이터에 대해 서로 접근을 시도하는 상황
• 이로 인해 발생하는 문제
  • 상호 배제
  • 교착 상태(Deadlock)
  • 기아(Starvation)

상호 배제

임계 영역

• Critical Resource에 대해 접근하고 실행하는 프로그램 내의 코드 부분
• Critical Resource : 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원
• ex) PA : cnt = cnt+1, PB : cnt = cnt-1

Mutual Exclusion

• 한 번에 하나의 프로세스만이 임계영역을 실행해야함
• 임계 영역의 성공적인 실행을 위해서는 맨 먼저 상호배제가 지켜져야함
• 임계 영역에 있지 않은 프로세스가 다른 프로세스의 임계 영역 진입을 막으면 안됨
• 비어 있는 임계 영역에 대한 진입은 바로 허용하되, 특정 프로세스의 진입 시도가 계속 무산되어 기아를 겪으면 안됨

⭐임계 영역을 진입할 때와 나올 때 꼭 해야하는 일⭐

• 임계 영역에 들어가고자 하는 프로세스는 먼저 임계 영역 내에 다른 프로세스가 있는지 확인한 후 있으면 기다린다
• 없다면 들어가면서 자신이 나올 때까지 다른 프로세스가 들어오지 못하도록 한다
• 임계 영역을 벗어날 때는 자신이 나오는 사실을 알려 다른 프로세스가 들어올 수 있도록 한다

상호 배제를 위한 소프트웨어 기법들

운영체제의 지원 없이 프로세스들 간에 자신의 프로그램에서 임계영역 앞뒤로 적절한 코딩을 하여 상호배제를 해결하는 방식이다. Busy Wait로 인해 CPU를 낭비할 수도 있고, 프로그래머의 실수로 인한 오류도 생길 수 있다.

Peterson Solution

** 참고 : Dekker 알고리즘은 Peterson 알고리즘에 의해 간결화되었다.

변수의 의미

• flag[i] : 어느 것이 본인의 차례인지 확인
• turn : flag가 둘다 true가 되어 두 프로세스 모두 임계 영역 진입이 불가능한 문제가 발생할 때, turn 값을 지정하여 둘다 true가 되는 경우 trun이 가리키는 프로세스를 실행한다.

임계 영역에 들어가는 조건
- 상대 flag가 false이거나
- 상대 flag가 true이고 turn이 0이면

Lamport의 베이커리 알고리즘

알고리즘 설명

• n개의 프로세스들이 상호 배제를 지키도록 하는 알고리즘

• choosing : 현재 i번째 프로세스가 number 값을 받는 중인지
  • true이면 받는 중, false이면 값을 다 받았다는 신호
• number : 진입을 원하는 프로세스가 받는 값
  • 진입을 원한 적이 없거나(초기화 상태), 진입을 하고 끝난 프로세스는 값이 0
  • 진입 희망을 요청한 순서대로 오름차순 값을 가짐
• for문 : 상호배제가 필요한 프로세스들을 검사
  • 첫번째 while문 : number 값을 받고 있는 프로세스가 있다면 기다린다
  • 두번재 while문 : 현재 프로세스 값이 비교대상보다 크다면 기다린다 → 임계영역에 도달하려면 비교 대상의 프로세스에서 while문이 거짓이어야함

임계 영역 진입 조건

• 자신의 number 값이 가장 작으면
• 진입이 원하는 프로세스가 기존 값보다 1 큰 값을 받는데, 이는 큐처럼 진입 희망을 요청한 순서대로 처리하기 위함임

상호 배제를 위한 하드웨어 기법들

인터럽트 금지 기법과 하드웨어 명령어를 사용한 기법이 있다. 상식적으로 인터럽트를 금지하면 임계 영역의 실행보다 더 시급한 일을 못하게 되고, 인터럽트 금지는 처리기 단위이므로 멀티 코어 시스템에서는 다른 처리기에서 접근할 가능성이 있기 때문에 사용할 수 없다. 주로 하드웨어 명령어인 test and set이나 exchange를 활용한다.

아이디어

• 하드웨어는 특정 메모리 주소에 대한 접근을 한 번에 하나의 요청으로 제한한다.
• 특정 메모리 위치에 대한 읽기와 쓰기 등의 작업을 한 번의 접근에 처리해주는 명령어가 있다면
• 이런 종류의 기계명령어는 원자적(Atomic)으로, 실행 동안 끊기지 않고(Indivisible) 완료된다.
• 기계 명령어는 실행이 끝날 때까지 중간에 CPU를 뺏기지 않는다는 점을 이용한다.

testandset

test and set 명령어는 target을 true로 바꾸고 매개변수로 받았던 bool 값을 반환한다.
이 명령어를 활용한 알고리즘을 분석해보자.

• lock이 false로 초기화되었다.
• i번째 프로세스가 최초로 실행되었다고 가정할 때, while문의 조건은 거짓이 되어 임계 영역에 진입한다. lock은 true 값을 가진다.
• 임계 영역 실행을 마치면 lock을 false로 돌린다.

장점

• 간단함
• 다중처리 시스템에도 쉽게 쓸 수 있음
• 한 프로그램 내에서 서로 다른 변수를 사용하여 여러개의 임계영역을 지원함
  • lock이 임계영역에 대응

단점

• 여전히 바쁜 대기를 한다
• 차례가 정해지지 않기 때문에 어떤 프로세스는 기아를 겪을 수 있다
• 임계영역 실행 중 높은 우선순위를 가지는 프로세스에게 CPU를 뺏길 경우 교착 상태에 빠질 수 있다
  • CPU를 뺏은 높은 우선순위의 프로세스는 lock이 true이기 때문에 while문을 계속 맴돈다.
  • 이 while문을 빠져나오려면 lock이 false로 바뀌어야 하는데, 이 문장이 CPU를 뺏긴 낮은 우선순위의 프로세스가 실행해야 한다.
  • 그런데 우선순위가 낮으므로 다시 실행할 수 없어 계속 while문을 맴도는 교착 상태에 빠진다.
• 교착 상태 해결
  • Priority가 낮은 프로세스에게 이 임계 영역에 접근하는 프로세스들의 우선순위 중 가장 높은 값+1을 임시로 주어 임계 영역에 진입힌다.
  • 우선 순위가 높기 때문에 CPU를 뺏기지 않는다.
  • 빠져나올 때 우선순위를 원상복구한다.

세마포어

세마포어란?

• 특수한 명령들로만 접근할 수 있게 허용되는 보호된 변수
• 프로그래밍 언어와 운영체제 수준에서 병행성을 위해 제공되는 기법이다

세마포어의 종류 : 값의 범위에 따라

• Binary Semaphore : 0 또는 1
• Counting, Integer Semaphore : 음이 아닌 모든 정수

세마포어를 위한 특수한 명령

• 세마포어 값을 초기화
  

• P(wait, down)
  • 아직 사용 가능하다면 1 감소하여 사용 표시
  • 사용 불가능하다면 사용 가능해질 때까지 wait
• V(signal, up)
  • 실행 가능한 프로세스가 있다면 실행 상태로 만듦
  • 없다면 사용하고 있지 않음을 표시
• S에 대한 접근은 P, V를 통해서만 허용된다

block & wait VS busy waiting

busy waiting

• while에서 맴돌기 때문에 CPU 낭비
• 하지만 다른 프로세스가 금방 실행된다.

block and wakeup

• CPU 낭비 없이 바로 대기로 빠짐
• 하지만 큐로 들어가기 때문에 실제 실행 속도는 느릴 수 있다.
• 임계 영역이 매우 짧게 끝나는 경우는 busy waiting이 낫다.
  • busy waiting은 짧게 while문을 맴돌고 다른 프로세스가 바로 실행된다.
  • 반면 block and wakeup은 대기에 들어가고 나중에 실행된다.

이진 세마포어를 사용한 상호배제 알고리즘

• s가 1로 초기화되었고, i번째 프로세스가 최초 실행된다고 가정하면
• P(s)를 거쳐 s는 0이 되고, 임계 영역에 진입한다.
  • 임계 영역을 실행 도중에 CPU 뺏겨도 s가 0이므로 대기 상태로 들어간다.
• V(s)를 거쳐 s는 1이 된다.
  • s가 1이 되고 다른 애가 뺏으면 이제 임계 영역을 실행할 수 있다.

정수 세마포어를 활용하는 예시 : Pool 관리

• 공유자원을 여러 명이서 사용할 수 있는 경우, Pool로 관리되고 있다고 한다.
• 예를 들어 프린터기가 10개 있는 실습실에서, 비어있는 프린터가 있다면 누구나 출력 작업을 할 수 있도록 한다.
• s를 10으로 초기화하고, 임계 영역을 출력 작업으로 놓는다.
• 이때 s는 임계영역의 진입이 허용되는 프로세스 수를 나타낸다.
  • 임계 영역 진입 전, P에 의해 s가 1 감소한다. (사용 표시)
  • 임계 영역 실행 후, V에 의해 s가 1 증가한다. (사용 완료 표시)
  • s가 0이면 현재 사용 가능한 프린터가 없다는 뜻으로, 대기한다.

생산자 소비자 문제

문제 설명

• 생산자 : 데이터를 만들어 버퍼에 저장한다.
• 소비자 : 버퍼에 있는 데이터를 소비한다.
• 생산자와 소비자가 버퍼에 동시에 접근할 수 있으므로, 버퍼는 공유 자원이다.
• 버퍼에 대한 접근, 즉 저장하고 꺼내는 일들은 상호배제 되어야 한다.
• 버퍼가 꽉 차있을 때는 생산자가 기다려야 하고, 소비할 데이터가 없으면 소비자가 기다려야 한다.
• 참고로 버퍼는 원형 버퍼이다.

알고리즘

• in : 버퍼에 넣을 위치
• out : 버퍼에서 꺼낼 위치

세마포어 활용

• s : 버퍼 접근 상호배제. 이진 세마포어

• e, f : 채우거나 꺼낼 수 있는 공간이 있는지 확인. 정수 세마포어

  • e : 빈 공간의 개수
  • f : 데이터가 있는 공간의 개수
    

• 버퍼에 접근하는 임계 영역 앞뒤로 s 세마포어의 P, V가 사용된다.

• e와 f도 동작에 맞게 변경한다.

• 만약 버퍼가 꽉 차서 e가 0이라면, 생산자 코드의 P(e)에서 대기에 걸린다.

• 버퍼가 비어서 f가 0이라면, 소비자 코드의 P(f)에서 대기에 걸린다.

• 단점

  • 다음 차례의 임계 영역 진입을 위한 선택 기준이 없어서 기아를 유발함
  • 임계 영역 앞뒤의 세마포어 연산 순서가 중요하다. 만약 소비자에서 P(f)와 P(s)의 순서를 바꾼다면.
    • P(s)를 먼저 통과해 s가 1이 된다.
    • P(f)에서 f가 0이어서 (버퍼가 빈 상태) 대기에 걸린다.
    • 그런데 대기를 풀어줄 생산자 임계 영역 진입 전, s가 1이기 때문에 임계 영역에 진입할 수 없다.
    • 결국 교착 상태에 빠진다.

Eventcount와 Sequencer

Eventcount와 Sequencer

• Eventcount와 Sequencer는 특별한 명령으로만 접근 가능한 정수형 변수이다.
• 초기값은 0이고, 세마포어와 달리 값이 감소하지 않는다.
• Sequence : 번호표. ticket()에 의해 증가한다.
• Eventcounter : 현재 처리 중인 번호. advance()에 의해 증가한다.

연산 설명

• 임계영역의 진입을 시도하는 프로세스들에게 순번 표를 부여하여, 기다린 순서대로 처리되도록 하여 기아를 방지한다. (vs 세마포어)
• ticket(s) : 번호표 뽑기
  • s 증가
• read(E) : 전광판의 숫자 보기
  • E 읽기, 현재 처리 중인 번호 확인
• advance(E) : 한 명이 서비스될 때마다 창구 직원에 의해 숫자 증가
  • E 증가, 대기 중인 프로세스를 깨운다.
• await(E, v) : 그 값이 내 번호표 값이 될 때까지 기다린다
  • E < v이면, 프로세스 E를 대기시킨다.

변수

• p, c : 생산자와 소비자를 위한 sequencer 변수
• in, out : 생산자와 소비자를 위한 eventcount 변수
• array[n] : 버퍼

생산자

• await(in, pord) : 내 차례인지 확인
  • pord와 in의 관계
    • in < pord : pord는 번호표만 받으면 올라가고, in은 생산이 완료되어야 하기 때문에, 작업이 밀리면 pord가 in보다 크다.
    • in == pord : 자기 차례에 해당되는 순간은 in과 port가 같다.
    • in > pord : 시스템 오류
  • in ≥ pord라면 아래로 내려간다.
  • in < pord라면 대기로 빠진다. 이 대기는 생산자가 생산을 해서 in이 증가하면 해결된다.
• await(out, pord-n+1) : 버퍼가 full인지 확인
  • 버퍼가 full인지 확인하는 방법
    • 데이터를 저장할 수 있는 공간이 1개 이상이면 full이 아니다.
    • 데이터를 저장할 수 있는 공간은 버퍼의 전체 크기 중 예약된 애들은 빼고, 소비해서 생기는 추가 공간을 더하면 된다. 이 값이 1보다 크면 full이 아니다.
    • 생산된 횟수인 in이 아니라 생산측 번호표를 뺀 이유 : 어차피 도착한 순서대로 실행되기 때문에, 예약이 꽉 차면 더이상 값을 저장할 수 없다.
    • n - pord + out ≥ 1이면 full이 아닌 것이다.
    • full이 아닌 조건 : out < n - port + 1
  • n - pord + out ≥ 1 : full이 아니므로 정상 실행
  • n - pord + out < 1 : full이므로 대기한다. 이 대기는 소비자가 소비를 해서 out이 증가하면 해결된다.
• advance(in)
  • 생산 완료 후, 현재 생산 번호표 1 증가
  • await(in, pord) : 내 차례인지 확인
    • 이 대기 조건을 해결할 수 있다.
  • await(in, out-1) : empty인지 확인
    • 이 대기 조건을 해결할 수 있다.

소비자

• await(out, cord) : 내 차례인지 확인
  • cord와 out의 관계
    • out < cord : cord는 번호표만 받으면 올라가고, out은 소비가 완료되어야 하기 때문에, 작업이 밀리면 cord가 out보다 크다.
    • out == cord : 자기 차례에 해당되는 순간은 out과 cord가 같다.
    • out > cord : 시스템 오류
  • out ≥ cord라면 아래로 내려간다.
  • out < cord라면 대기로 빠진다. 이 대기는 생산자가 생산을 해서 out이 증가하면 해결된다.
• await(in, cord+1) : 버퍼가 empty인지 확인
  • 버퍼가 empty인지 확인하는 방법
    • 실제 생산된 횟수 - 소비 예약 횟수 < 1이면 empty이다.
    • empty : in - cord < 1
  • in - cord < 1 : empty이므로 대기.
    • 생산을 해서 in이 증가하면 해결된다.
  • in - cord ≥ 1 : empty가 아니므로 진행한다.
• advance(out)
  • 소비 완료 후, 현재 소비 번호표 1 증가
  • await(out, cord) : 내 차례인지 확인
    • 이 대기 조건을 해결할 수 있다.
  • await(out, pord-n+1) : 버퍼가 full인지 확인
    • 이 대기 조건을 해결할 수 있다.

Monitor

모니터

• 공유 데이터들과 임계 영역을 관리하는 소프트웨어 구성체
• 공유 데이터를 위한 변수, 초기화 루틴, 임계영역을 코딩한 프로시저로 이루어졌다.
• 변수 : 프로시저를 통해서만 접근 가능
• 프로세스 : 모니터의 프로시저 호출, 실행하여 모니터 안으로 진입하고 변수에 접근한다.
• 상호 배제 실현 : 언제나 모니터의 진입을 한 프로세스로 제한한다. 한번에 하나 이상의 프로세스만 모니터 안에 있도록 한다.

모니터의 의의

• 실수를 줄일 수 있도록 시스템에서 제공되는 언어 수준의 구조이다.
• 동기화 관련 부분이 모두 모니터 내부에 표현되어 있으므로, 제대로 작동되면 이것을 사용하는 병행 프로세스들 역시 오류 없이 실행된다.
• 사용자는 프로그램의 적당한 위치에 모니터 프로시저를 호출만 하면 된다.

모니터 운영 방식

• 대기 큐(진입 큐) : 한 프로세스가 들어가 있을 때를 대비해 호출될 프로시저 개수만큼의 대기 큐가 있어야 한다.
• 조건 큐 : 모니터 내의 프로세스가 실행 중에 특정 조건 때문에 대기해야할 경우, 다른 프로세스의 실행을 위해 이 조건 큐에 들어가서 기다린다. 모니터에서 요구되는 조건의 개수만큼 조건 큐가 존재한다.
• 신호자 대기 큐 : 조건 대기를 해결해줄 프로세스가 조건을 만족시키면 기다리던 프로세스가 모니터 진입을 하고, 해결 프로세스는 잠시 모니터를 비켜준다. 이 용도로 사용되는 큐이다. 대기하던 프로세스가 실행되고 나가면 다시 모니터에 진입하여 나머지 작업을 실행한다.
• 조건 변수 : 모니터에서만 선언하고 사용한다.
  • cwait(c) : 조건의 대기. 프로세스를 조건 큐에 대기시키고, 다른 프로세스의 모니터 진입을 가능하게 한다.
  • csignal(c) : 깨우기. 대기되었던 프로세스를 재개시키고, 자신은 신호자 대기 큐로 비켜준다.

• 버퍼에 동시 접근하는 프로시저 : append, take
• 공유 데이터 : buffer
• 지역 변수 : nextin, nextout, count
• 조건 변수 : notfull, notempty

• 생산자는 데이터를 만들고 append(x)를 호출하여 모니터 진입 요청

• 내부에 이미 프로세스가 있으면, append 대기 큐에서 기다리다.

• 모니터 내부가 비어있으면, 진입하여 append 프로시저의 full 조건을 검사한다.

• 만약 full이 맞으면, notfull 조건 큐로 이동한다.

  • notfull 조건을 벗어날 때까지 기다린다. 소비자가 소비를 하여 csignal(notfull)으로 해당 프로세스를 깨우면 그때 다시 모니터에 진입하여 나머지 작업을 실행한다.

• full이 아니라면, 데이터를 버퍼에 저장하고 신호 큐로 이동한다.

  • 이 프로세스는 empty여서 notempty 조건 큐에 대기하고 있는 프로세스의 대기를 해결한다.
  • 데이터를 버퍼에 저장하면 이제 소비자 프로세스는 나머지 작업을 진행할 수 있다. 따라서 데이터 저장이 끝나면 이 프로세스는 신호 큐로 비켜주고, 소비자 프로세스 작업을 진행한다.
  • 만약 notempty 조건 큐가 비어있었다면 마저 명령을 실행한다. 여기서는 깨워준 후 작업이 모두 끝났으므로 모니터를 빠져 나온다.

식사하는 철학자 문제

• 5명의 철학자가 앉아있고, 식탁에는 접시 5개와 5개의 포크가 있다.
• 스파게티를 먹으려면 자신의 오른쪽, 오니쪽 포크 두개가 필요하다.
• 포크는 공유 자원이며, 철학자들의 정상적인 식사를 보장해야 한다.
  

해결 방법

1. 동시 참여 가능한 프로세스 개수를 제한한다.
2. 포크를 집는 순서를 제한한다.
   • 홀수 철학자는 왼, 오
   • 짝수 철학자는 오, 왼
3. 모니터를 사용한다.
   • 모니터 안에는 프로세스 하나만 존재할 수 있으므로
   • 왼쪽 포크를 집는 동안 다른 철학자가 오른쪽 포크를 집어갈 가능성을 배제한다.