[OS] Process Synchronization 2 : Critical-Section, Semaphores

doodung·2022년 5월 5일
0

OS - 운영체제

목록 보기
13/15
post-thumbnail

The Critical-Section Problem | 임계구역

  • critical-section 공유데이터 접근하는 코드

  • n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

  • 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재

  • Problem

    • 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

      공유데이터를 접근하는 코드가 critical section이다.

      공유데이터 접근하는 코드가 실행중이면 critical section에 다른 프로세스는 들어갈 수 없다.


Initial Attempts to Solve Problem

보통 프로그램 코드는 크리티컬 섹션이거나 아니거나로 구분할 수 있다. (공유 데이터에 접근 하는 코드이거나 아니거나)


프로그램적 해결법의 충족 조건


entry section에 넣어야 하는 조건들

  1. Mutual Exclusion | 상호 배재

    • 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.
  2. Progress | 진행

    • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
    • 당연한 얘기지만 이 조건이 만족하지 못할 수도 있음. 코드를 잘못짜면.
  3. Bounded Waiting | 유한 대기

    • 특정 프로세스 입장에서 프로세스가 critical section에 들어가려고 요청한 후 부터 그 요청이 허용될때까지
      다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. (기아현상 생기지 않게)
    • critical section에 들어가려 하는 프로세스가 3개면 2개만 번갈아가면서 들어갈때, 나머지 1개가 마냥 기다려야 할 때 이 조건을 만족하지 못한다고 하는 것.

  • 가정
    - 모든 프로세스 수행 속도는 0보다 크다
    • 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

이러한 조건들을 만족하면서 락을 잘 걸었다 푸는 알고리즘을 알아보자.

1. Algorithm 1


이런 문제가 생기는 이유는 critical section에 들어왔다가 나가는 것을 CPU를 빼앗기지 않고 이 과정을 한번에 수행하면 문제되지 않는데,
CPU를 빼앗기고 안빼앗기고는 대게 CPU에서 단일 인스트럭션 끝나면 CPU를 빼앗길 수 있음.
그런데 고급언어의 이러한 코드들은 단일 인스트럭션이 아니기 때문에 이거를 수행하는 도중에 CPU를 빼앗길 수 있어서 문제가 발생함

이 코드는 프로세스 P0를 위한 코드.

P1을 위한 코드는
while(turn≠1)
critical section
turn=0;
으로 생각하면 된다.

즉, 과잉양보 : 반드시 한번씩 교대로 들어가야만 함 (swap-turn) 상대가 turn을 내값으로 바꿔줘야만 내가 들어갈 수 있음

특정 프로세스가 더 빈번히 critical section을 들어가야 한다면?
while문을 이용해 돈다. turn은 누구차례인지를 나타낸다.
my turn일때 critical secion에 들어감. 들어갔다 나오면 turn1로 프로세스를 바꿔줌
결국 while 문을 돌면서 본인 차례가 아니면 기다리고, 본인 차례가 오면 critical section에 들어가고, 들어갔다 나올 때 turn을 바꿔주는 것이다.
그래서 이 코드는 상호배제는 만족한다. (둘이 동시에 critical section에 들어갈 가능성은 없다.)

그런데 문제점은 Progress 조건을 만족하지 못한다. critical section은 반드시 교대로 들어가도록 코딩되어있다. 반드시 하나가 critical section을 들어갔다 나와야지만 상대방에게 줄 수 있다.
프로그램들이 critical section에 들어가는 빈도는 프로세스마다 다르다. 그래서 극단적으로 만약에 p0가 빈번히 들어가고 싶고, p1이 한번만 들어가고 안들어가고 싶다고 하면, p0도 영원히 못들어간다. 상대방이 turn을 바꿔주지 않기 때문에

따라서 critical section을 잘 풀지 못하는 알고리즘이다.


2. Algorithm 2


프로세스 2개가 각각 자신의 flag를 가지고 있음. flag는 본인이 critical section에 들어가야 한다는 것을 표현하는 것.
처음에는 flag 값이 false (둘다 critical section에 들어갈려고 하는건 아니라는 뜻.)

critical section에 들어갈려면 본인의 flag를 True로 만든다. 그 다음에 상대방 flag를 체크한다. (혹시 상대방도 flag를 세팅해놨는지) 상대방 flag가 세팅되어있다면 기다린다. 세팅하지 않았다면 critical section에 들어가고, 들어갔다 나올때 본인의 flag를 false로 만들어 상대방도 들어갈 수 있게 한다.

이 알고리즘도 문제가 있다. Progress 조건을 만족하지 못한다.
Pi가 flag를 true로 했을때 cpu가 뺏기고, Pj가 flag를 true로 된 상황이면, 둘의 flag가 모두 true이므로 계속 기다리게 된다.
결국 flag를 내려놓는 것은 critical section에서 나와야 할 수 있기 때문.


3. Algorithm 3 : Peterson’s Algorithm


피터슨의 알고리즘

앞의 turn과 flag를 함께 사용한다.
그래서 Pi가 critical section에 들어가고자 할때, 먼저 flag를 true로 만든다. 그리고 turn을 상대방으로 바꿔놓는다. 그리고 들어가기 전에 체크를 한다. 상대방이 깃발을 들고있고, 이번이 상대방 차례인지를 체크한다.
while 안의 두가지중에 한가지라도 만족 못하면 critical section에 들어간다.
빠져나올때 flag를 false로 만든다.

이 방법은 모든 경우의 수를 따져서, 중간에 cpu를 빼앗긴다고 하더라도 앞에 있는 세가지 조건인
1. 상호배제 2. progress 3. 유한대기 를 모두 만족하는 알고리즘이다.

  • 생각보다 간단해 보이지만 코드 순서 하나라도 바꾸면 제대로 동작을 안할 수도 있음. 최적화된 코드이다.

그런데 이 코드도 문제가 있다. Busy Waiting == Spin Rock 문제. (계속 cpu와 메모리를 쓰면서 락을 거는 것) 만약 어떤 프로세스가 이미 critical section에 들어가있는 상태에서 다른 프로세스가 cpu를 잡으면 while을 돈다.
그럼 빠져나갈 수 없는데, 본인의 cpu 할당시간 동안 계속 while 돌면서 check함. 하지만 조건이 만족되지는 않음.

조건이 만족 될려면 상대방이 cpu를 잡아서 변수를 바꿔줘야 하기 때문. 쓸데없이 check하면서 본인의 cpu할당시간을 while문만 돌다가 끝나게 될 수 있다.
이 것을 busy waiting이라고 한다.


4. Synchronization Hardware


하드웨어 적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단이 해결된다.

이런 문제가 생기는 이유는 데이터를 읽는것과 쓰는것을 하나의 인스트럭션으로 처리할 수 없기 때문이다.
만약 내가 어떤 데이터를 읽으면서 동시에 데이터를 쓰는 것이 하나의 인스트럭션으로 가능 하다면, 적어도 인스트럭션을 실행하는 도중에 cpu를 빼앗기지 않을 것이다.
그래서 인스트럭션 하나를 가지고 읽고, 쓰고를 동시에 할 수 있다면 간단하게 rock을 걸고 푸는 문제를 해결 가능하다.

Test_and_set 인스트럭션 : a라는 데이터의 현재값을 읽어내고, a라는 값을 1로 바꿔줌. 이걸 하나의 인스트럭션으로 처리하는 것.
a가 만약 0이라고 하면 1. 0이 읽힘 2. 그 후 a의 값을 1로 변경

이게 지원이 된다면, 소프트웨어적으로 코드를 복잡하게 짤 이유 없이,
락을 걸고 푸는 코드가 간결하게 바뀌게 된다.

코드를 보면, lock이라는 변수를 하나 두고, 처음에 0을 넣는다.
critical section에 들어가기 전에 누군가가 들어가있으면 lock이 걸려있을것임, 그래서 그것을 체크 함. 그게 아니면 내가 lock을 거는 것.
그래서 while(testandset(lock)) lock이 0이면 아무도 critical section에 들어가지 않았으니 lock을 걸고(lock을 1로 변경) critical section에 들어가면 된다.
만약 lock이 이미 1이었다면, while을 돌면서 기다리고 있는 것.

프로그래머가 매번 이런 작업을 한다는 것은 불편한 일이다. 보통은 간소하게 하기위해 고급 추상 자료형인 세마포어를 정의하고,
프로그래머 입장에서 이런 작업을 하는 것이 아니라, 연산만 해줘서 락을 걸고 락을 푸는 작업을 할 수 있다.


Semaphores | 세마포어


앞의 방식들을 추상화시킴

추상 자료형이란 ? object + operation

세마포어를 왜 사용할까 ? 락을 걸고 락을 푸는 것을 간단하게 프로그래머에게 제공할 수 있다.
어떤 공유자원을 획득하고 반납하는 것을 세마포어가 처리해준다.

  • Semaphore S
    • integer variable : 정수값. (자원의 갯수라고 생각하면 된다.)
    • 아래의 두 가지 atomic 연산에 의해서만 접근 가능

  • P연산 : 세마포어 변수(공유데이터) 획득하는 과정 : 락을 거는 과정
  • V연산 : 다 사용 후 반납하는 과정 : 락을 푸는 과정

세마포어 S 변수값이 5일때 (자원이 5개일 때), P연산을 한번 하면 그 자원을 하나 가져가서 4가 된다. 또 다른 프로세스가 P연산을 하면 3가된다.
V연산은 자원이 4인 상태에서 하면 5가 된다.

코드를 보면 S값이 0이하이면 계속 기다리는 상태이다. 그러다 자원이 양수가 되면 즉, 누군가 자원을 내어놓으면 그때 S-1을 하고 자원을 획득한다.
획득이 되었으면 자원을 사용한다. 자원 사용 후 V연산으로 S+1을 해서 반납을 한다.

P연산과 V연산은 atomic한 연산이 되는 것을 가정한다. 세마포어는 추상적으로 연산 자체를 정의한 방법이기 때문이다.

여기서도 busy wait 문제가 생긴다. 자원이 없을 때 P연산을 하게 되면 계속 기다리다가 본인의 CPU 시간을 다쓰고 반납하게 된다.


Critical Section of n Processes : 임계구역 문제에 세마포어를 사용하면?


1. Busy-wait Implementation

세마포어 변수 mutex를 1로 넣고, P연산과 V연산을 하면 된다.
P와 V의 구현은 시스템의 몫이고, 프로그래머는 추상 자료형 형태인 세마포어로 간단하게 P연산과 V연산만 해주면 된다.

busy wait 문제 == spin lock

다른 방식으로도 구현할 수 있다. Block & Wakeup (=sleep lock)의 방식으로.
lock을 못얻으면 쓸데없이 cpu를 쓰지 않고 block상태 (잠들어버리게 한다)

어떤 프로세스가 cpu를 사용하다가 i/o처럼 오래걸리는 작업을 하러 가면 그 프로세스는 blocked 상태가 되어 cpu를 얻을 수 있는 권한이 없어진다.
이 blocked 상태에서는 해당하는 자원을 받으면 ready queue로 돌아올 권한이 생기는 것.

마찬가지로 공유 데이터를 접근하는 것도 마찬가지다. 누군가 공유데이터를 쓰고 있으면 쓸데없이 기다리는 것이 아니라, process를 blocked시키고 있다가
공유데이터를 누가 반납하면 그때 깨움.


2. Block / Wakeup Implementation

세마포어 변수 값과 잠들어 있는 프로세스들을 연결하기 위한 queue가 만들어지게 된다.
지금 세마포어를 획득할 수 없으면 그 프로세스를 block 시키게 되고, 누군가가 세마포어를 쓰고 나서 반납하게 되면 block된 프로세스 중에 하나를 wake up

예를 들어 세마포어 변수가 하나 있으면 그친구를 누군가가 획득을 했을거고, 획득 못한 친구들을 아래 처럼 세마포어 변수 queue에다가 PCB를 매달아놓음.

  • P연산 : 세마포어 변수(공유데이터) 획득하는 과정 : 락을 거는 과정
  • V연산 : 다 사용 후 반납하는 과정 : 락을 푸는 과정

P연산은 자원의 여분이 있다면 획득하고, 자원의 여분이 없다면 block상태로 잠든다.
V연산은 자원을 반납하고 끝나는 것이 아니라, 혹시 이 자원을 기다리면서 잠들어있는 상태의 프로세스가 있으면 그것을 깨워주는 wakeup방식이 V연산에 들어가야 한다.

P연산에서 세마포어 변수 값을 1 빼준다. 그 값이 만약 음수라고 하면 이미 누군가가 다 가져가고 자원의 여분이 없다는 것이다.

그래서 이 프로세스를 S.L 구조체 변수의 리스트에다가 프로세스를 연결시킨다음 BLOCKED 를 시킨다. 그러고 자원이 생기면 깨어날수 있을 것이다.

V연산에서 자원을 다 쓰고 나면 세마포어 변수 값을 1더해주고, if 안의 값이 0 이하일 때는 내가 자원을 내놓았는데도 값이 0이라는건 자원을 기다리면서 누가 잠들어 있다는 뜻이다. if 안의 값이 양수라면 기다리는 프로세스가 없다는 것이다.

그래서 0 이하이면 잠들어있는 프로세스 하나를 세마포어 리스트에서 빼가지고 프로세스를 깨워주는 wakeup을 해줘야 한다.

앞의 방식과는 다름을 알 수 있다. 앞에서 S는 자원의 개수였지만 S.value는 음수면 자원을 기다리고 있고, 양수면 기다리지 않고 있다는 상황을 말해준다.


Which is better?

보통 block/wakeup을 쓰는것이 효율적이다. cpu 이용률이 높아지기 때문.

하지만 block/wakeup도 오버헤드가 있다. 상태를 잠들고, 깨워주고 하는 바꿔주는 작업이 필요하기 때문.
그래서 Critical section의 길이가 매우 짧은 경우에는 busywait을 해도 큰 문제는 없다.

Two Types of Semaphores

  • Counting semaphore : 자원의 개수가 여러개인 경우
    • 도메인이 0 이상인 임의의 정수값
    • 주로 resource counting에 사용
  • Binary semaphore (=mutex) : 자원의 개수가 1개인 경우
    • 0 또는 1 값만 가질 수 있는 semaphore
    • 주로 mutual exclusion (lock/unlock)에 사용
profile
반가워요!

0개의 댓글