6 분 소요

[참고자료] [Operating System Concepts 에센셜] 저자(글) · Abraham Silberschatz, Peter Baer Galvin , Greg Gagne 번역 조유근, 박민규 , 고건

Chapter 5. Process-Synchronization



5.1 Background

프로세스는 동시실행이 가능하다.

  • Time sharing, multitasking(멀티 프로세싱, 멀티쓰래딩) 은 한 프로세스가 미리 정해진 시간만 수행하고 입출력 요청이 오면 다른 프로세스를 병행한다.
  • 개별 프로세스는 언제든 다른 프로세스로 전환
    • 일정 시간 후엔 스케쥴링으로 다시 수행하지만 실행 중단은 필수
  • 다수 프로세스간 데이터 공유는 일관성이 깨진다.
    • 이를 막기 위해 프로세스간 동기화가 필요하다.
  • 동기화 프로세스를 Cooperating process라고 한다.



Producer-consumer problem

생산자 프로세스

소비자 프로세스

bounded buffer 를 사용하며 shared memory인 링버퍼를 갖고 있다.

  • 동기화

    • 프로세스가 병행 수행한다.

    • 병행 실행하는 프로세스 들 간에 공유 데이터(링버퍼)에 대한 접근이 있다.

  • 결론

    • 병행 실행 프로세스가 있고 공유 데이터가 있으면 동기화 문제가 발생한다.

    • 공유 데이터의 접근을 통제하는 것이 동기화 문제의 해결책이다.

    • counter - 생산자는 counter를 1증가시키고, 소비자는 counter를 1 감소시킴.



Race condition

“병렬 프로세스들이 공유 데이터 접근 시 일관성이 깨지는 상황”

counter를 증기시키기 위해서는 값을 레지스터에 저장시키고 레지스터의 값을 증가 시킨다음에 카운터에 넣는다.

나쁜 예

생산자가 공유데이터 접근하는 동안에 소비자가 끼어드는 문제가 있음.

좋은 예(한번에 한 프로세스만 공유변수를 접근하도록)



5.2 Critical Section Problem

임계 지역 이란 공유 데이터 접근 구역이다.

n개중에서 한 프로세스가 자신의 크리티컬 section안에 있다면 다른 프로세스들은 각자의 크리티컬 세션을 실행하면 안된다.

entry section

critical section

exit section

remainder section

으로 나눠야한다.



Solution of Critical Section Problem

프로세스 i의 모습은 다음과 같다.

  • 크리티컬 세션은 entry, exit 의 반복으로 이루어져 있다.
    • entry section: 공유데이터 접근 코드(크리티컬 세션)
    • exit section : 공유데이터와 상관없는 코드 (remainder section)
  • An example:
    • turn이 j이면 크리티컬 세션에 접근하지 못한다.

프로세스 i는 while(turn ==j)를 통해 차례가 j이면 entry section에 있고 크리티컬 세션을 진입하고 난뒤에 exit section에서 다시 turn을 j로 바꿔준다.



Solution to Critical-Section Problem

  • 모든 크리티컬 세션은 3가지에 만족 해야 한다.
  1. Mutal Exlusion(상호 배제) - 여러 프로세스 Pi가 자신의 크리티컬 세션에 있다면, 나머지 프로세스들은 각자의 크리티컬 세션을 실행하면 안된다.
  2. Progress - 한 프로세스가 remainder에 있으면 다른 프로세스의 크리티컬 세션 진입에 관여하면 안된다. entry section끼리 결정할 일이다. 크리티컬 세션 대기 프로세스끼리 다음 크리티컬 세션을 결정할 일이지 remainder에 있으면서 끼어들면안된다.
  3. Bounded Waiting - 누가 다음 크리티컬 세션에 들어갈 지는 영원히 결정이 미뤄지면 안된다. 무한반복하면 안된다.



5.3 Peterson’s Solution

  • 특수한 하드웨어 기술 없이 SW로 상호배제 문제를 해결한다.

각각 별도의 cpu에서 두 프로세스가 동작중이라면?

CPU1 에서 x번지에 store 하려고 한다. 10을 쓰려고한다.

CPU2 에서는 x번지에 20을 쓰려고한다.

두개의 코어에서 공통의 메모리 위치에 store를 동시에 하려 한다.

x번지는 10일까 20일까?

동시에 접근하려할때 순서에 승부가 난다.(10일수도 20일수도) → 이것은 기본적으로 하드웨어가 보장한다.

두 프로세스는 두 변수를 공유한다.

  • int turn; # 값이 0또는 1을 가지게 된다. 다음번 크리티컬 세션에 진입할 프로세스가 0번일까 1번일까를 의미.
  • Boolean flag[2]; # flag[0] 이 True이면 ”0번 프로세스가 자신의 크리티컬 세션에 진입하려한다를 의미”



/P0/

  • flag[0] = true; #진입의사를 밝힘
  • turn = 1; #다음번 크리티컬 진입 프로세스를 1로 둠.
  • while(flag[1] && trun ==1) 둘중 하나가 false면 크리티컬 세션에 진입.

이렇게 하면 한번에 한 프로세스만 크리티컬 세션에 진입할 수 있다.

(p0이 실행되려면 p1이 임계구역에 있지 않아야한다.)

1번 경우: p1 이 entry에 있을때 turn == 0으로 바꾼다.

2번 경우 : p1이 임계구역에서 나와 exit section에서 flag[1]==false로 바꾸고 remainder에 있을때.



p0이 크리티컬 세션에 있다면

  • 상호배제
    • 0번이 크리티컬 세션에 들어가 있으면 다른 프로세스는 진입 x
      • p1이 들어가려면 flag[0]이 false거나 turn == 1 이여야하는데,
    • flag[0]는 true 상태이다, 다음 프로세스를 의미하는 turn == 0 상태이다.
    • true, true에서 p1는 while문 통과 못한다.
    • 따라서 상호배제 만족.
  • Progress (한 프로세스가 remainder에 있으면 다른 프로세스의 크리티컬 세션에 관여하면 안된다. )
    • p1이 remainder section에 있으면 flag[1]=false; 이상태에서 p0가 진입 하려한다면?
      • p0 코드는 무조건 while문에서 벗어난다. flag[1] == false이기 때문에.
      • 결론은 remaider section에 있을때 임계구역을 나오면서 자신의 진입의사를 false로 바꾸기 때문에
  • Bounded Waiting( 누가 다음 크리티컬 세션에 들어갈 지는 영원히 결정이 미뤄지면 안된다. 무한반복하면 안된다.)

p1이 진입시도하고 있어서

flag[1] == true, turn == 1,

첫번째 진입시도에 실패해도 두번째에 진입 가능하다. 무한정 진입 못하는 경우가 발생하지 않는다.



5.4 Synchronization Hardware

“동기화를 위한 하드웨어”

  • 임계지역 문제의 2번째 솔루션은 동기화 하드웨어이다.
  • 임계구역에 한 프로세스가 들어가면 인터럽트를 끄면된다.
  • 하지만 단일 cpu에서만 가능하고, 멀티 프로세서 상태에선 사용을 못한다.
  • 별도의 하드웨어 장치가 있는 것이아니라 하드웨어 명령을 제공한다.
    • test_and_set
    • compare_and_swap Instruction
    • Atomic하다.(분할 불가능한)



test_and_set

  • *traget → 명령 대상이 되는 메모리 번지
  • 대상 메모리 위치를 true로 만들고, true로 만들기 전의 값을 리턴한다.



Solution using test and set

lock == False로 시작한다. 따라서 test and set 결과가 그대로 false로 리턴해서 진입가능하다.

한 프로세스가 while 문으로 들어가 있을때는 lock이 True로 바뀌어 다른 프로세스는 while문을 진입 할 수 없다.

크리티컬에 진합하고 entry section에서 lock을 다시 false로 바꿔줘서 다른 프로세스가 진입할 수 있다.

상호 배제와 Progress는 만족하지만 bounded watiting은 만족하지 않는다. lock의 개념만 있다.

atomic하기 때문에 한 프로세스만 진입한다.



compare and swap(특정한 메모리값 읽기)

int * value → 메모리값

int expected → 현재값

int new value → 새로운 값.

코드를 보면

현재값을 temp에 넣고

메모리값과 현재 값이 같으면 메모리값을 새로운 값으로 교체하고

리턴은 test and set과 마찬가지로 원래 값을 리턴한다.



Solution compare and swap

먼저

expected 0과 같기 때문에 new값 1로 바껴서 lock==1이되고 리턴 값은 0 이 된다.

따라서 critical section에 들어가게 된다.

  • 다른 프로세스들은 lock==1이기때문에 진입을 못한다.

compare and swap 과 test and set은 거의 같은 알고리즘을 따른다.

상호 배제와 Progress는 만족하지만 bounded watiting은 만족하지 않는다. lock의 개념만 있다.

atomic하기 때문에 한 프로세스만 진입한다.



Bounded-waiting Mutual Exclusion with test_and_set

3번조건 : 크리티컬 세션을 무한번 진입시도 하는 경우는 없어야한다.

여러개가 test _ and _ set을 하면 경쟁을 통해 한 프로세스(쓰레드)가 들어간다. 하지만 누가 들어갈지 보장이 없었다.

자 먼저 boolean lock, boolean waiting[n]을 보자.

boolean lock - 앞의 lock과 같은 용도

boolean waiting[n] - 프로세스 pi의 임계 구역 진입 의사 표현이다.

먼저 waiting[i] 와 key가 true이기 때문에 while문에 들어가서 key = true이기 때문에 무한 반복하게 된다.

exit section부터 보면

i의 다음을 j라고 하고,

while문 조건에 의해 j를 i까지 돌려서 waiting[j]가 true일때를 찾아라! 이다.

만약에 다 돌렸는데 없으면 (아무도 진입의사가 없는것이기 때문에) lock을 해제한다.

만약에 있다면 waiting[j] = false로 바꿔주기 때문에 진입 의사가 있는 프로세스는 진입이 가능하다.

while문 조건을 먼저 보면 waiting[i]와 key중 하나가 false여야한다.

  1. waiting[i] == false인 경우
    • 누군가 exit section에서 waiting[j] = false해줄 경우.



5.5 Mutex Locks

“임계 구역 문제는 응용프로그래머가 직접 사용하기 어렵다. 쉽게 사용할 수 있는 SW도구가 Mutex lock이다”

Mutex locks

  • 임계지역 진입 가능 여부 boolean 변수이다.
  • acquire() lock을 열어 임계 지역을 얻을 수 있는 함수
  • release() lock해제 함수

acquire, lock은 atomic하게 동작한다.

하지만 이 솔류션은 busy waiting(while문의 무한 반복) 을 야기한다.  = spinlock이라고도 부른다.



5.6 Semaphore

“다익스트라가 고안한 동기화 SW도구”

S로 표기(정수형 변수이다.)

  • wait(), signal()로 atomic하게 동작한다.

wait 함수는

S가 양수가 될때까지 기다렸다가 S를 감소시킨다.

signal함수는

S의 값을 1로 증가시킨다.



Semaphore Usage

  • counting Semaphore
    • S가 0~N사이의 값 가지도록 하며 컴퓨터 내의 가용 자원수를 나타낸다.
  • Binary Semaphore
    • S가 0또는 1, mutex lock과 동일한 효과이다.
P1:
	S1;
	signal(sysch);
P2:
	wait(synch);
	S2;



Semaphore Implementation

  • 같은 Semaphore에 대해서 두 프로세스가 동시에 wait(),signal()할 수 없도록 보장한다.(atomic)
  • wait(),signal() 코드 자체가 critical section이다.
  • 하지만 busy waiting이 존재한다.



Semaphore Implementation with no Busy waiting

  • 세마포어마다 waiting queue를 사용한다.

  • block
    • waiting queue에다가 넣기
  • wake up
    • Ready queue에다가 넣기

코드를 보면

먼저 1을 감소시키고

if S→value < 0 // 즉 이미 음수거나 0일때(이는 현재 공유 자원이 다른 프로세스에 의해 사용 중) wait queue에다가 넣는 block한다.

signal

먼저 1을 증가시키고

만약 여전히 0,음수라면 //wait q가 있다는 뜻이다. 이를 삭제하고.

wake up으로 ready 큐로 옮긴다.



Deadlock and Starvation

  • Deadlock
    • 세마포어를 잘못 사용하면 데드락이 발생한다.
      • 둘 이상의 프로세스가 영원히 발생하지 않을 사건을 무한정 기다린다.

만약에 다른 core에서 S와 Q에 접근한다면?

wait(s)는 즉시 성공

wait(Q)도 즉시성곤.

하지만 wait(Q)와 wait(S)는 무한정 기다리게 된다.

우선순위 역전이 일어난다.



5.7 동기화에 대한 고전적인 문제들

  1. Bounded-Buffer(생산자 소비자 문제)
  2. Reader - Writers
  3. Dining - philosophers



Bounded Buffer

생자 소비자의 데이터 일관성이 깨지는 문제

  • 버퍼의 크기는 N개이다. (=Bounded Buffer)
  • mutex라는 이름의 세마포어 (바이너리 세마포어_ 는 1로 시작한다.
    • mutex : 접근 상호 배제 보장
  • full
    • consumer 제한(데이터 수)
  • empty
    • producer 제한(빈칸의 수)

생산자는 wait(empty)를 통해 빈 공간을 기다린다. 그다음 mutex를 통해 버퍼에 값을 넣는다. signal(mutex)로 mutex공간 접근 가능을 얘기해주고 signal(full)로 데이터가 들어갔다고 알려준다.

소비자는 wait(full)을 signal(full)을 통해 데이터 값이 찼다는 것을 알 수 있고, signal(mutex)를 통해 wiat(mutex)를 알 수있다. 값을 읽고 삭제한다음에 signal(mutex)로 접긍할 수 있다고 얘기하고 signal(empty)를 통해 값이 비었다고 알려준다.

bounded buffer는 버퍼 사이즈와 관계없이 한개의 데이터에 대해서 접근 가능하다.



Readers - Writers Problem

Readers

  • 공유 데이터 집합이며 읽기만 수행한다. (업데이트는 수행하지 않는다._

Writers

  • 읽기쓰기는 하지 않고 업데이트만한다.

  • 우선순위 부여 방식이다.

  • 다수의 reader는 얼마든지 동시 접근이 가능하다.

  • writer는 한번에 한 writer프로세스만 접근 가능하다.

  • Shared Data

    • Data set (Reaeder 와 writer가 공유하는 데이터 셋)

    • read_count(현재 몇개의 Readers가 있는지 → 다수의 리더는 가능하기 때문에)

    • rw_mutex (리더와 롸이터가 공유하는 세마포어)

댓글남기기

참고