OS | Chapter 6 Synchronization Tools

Yunny.Log ·2022년 10월 17일
0

OS

목록 보기
6/8
post-thumbnail
post-custom-banner

Synchronization Tools and Examples

6.1 배경 : Need for Process Synchronization

  • Concurrent access to shared data may result in data inconsistency
  • 공유 데이터 (shared data)에 두 개 이상의 프로세스가 동시에 접근하면 DATA INCONSISTENCY (데이터 비일관성) 발생 가능
  • Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes.
  • 데이터 일관성을 유지하기 위해서는 협력 프로세스의 질서 있는 실행을 보장하는 메커니즘이 필요합니다.
  • (+) 논리 주소 공간을 공유하는 협력적 프로세스의 질서 있는 실행을 보장하여, 이를 통해 데이터의 일관성을 유지하는 다양한 메커니즘 필요 !
  • (+) 동기화 : DATA CONSISTENCY (데이터의 일관성) 을 유지하기 위한 메커니즘

  • (+) 여러 프로세스를 동시에, 혹은 병렬적으로 실행할 때 데이터의 무결성 (integrity of data)을 공유하면 아래와 같은 문제가 발생

생산자-소비자 문제

  • 두 프로세스, 즉 생산자 (producer)와 소비자 (consumer) 프로세스가 동시에 (concurrent) 실행될 때 두 프로세스 사이의 버퍼 (buffer)가 유한하기 때문에 발생할 수 있는 문제

생산자 프로세스는 새로운 아이템을 버퍼에 넣고, 이때 버퍼 내부의 아이템 개수를 계산하는 count 변수의 값이 1 증가함. 반대로 소비자 프로세스는 버퍼 내부의 아이템을 읽어오고, count는 1 감소함.
만약 두 프로세스가 동시에 실행된다면?

버퍼가 비었는데 소비자 프로세스가 아이템을 읽으려고 할 때
버퍼가 꽉 찼는데 생산자 프로세스가 아이템을 넣으려고 할 때
문제가 발생하며 제대로 동작하지 않을 것임.

Possibility of Interleaving

  • 인터리빙 (interleaving): '끼워넣기'. 어떤 명령의 흐름 속에 다른 명령, 혹은 프로세스가 섞여서 수행되는 현상

  • If both the producer and consumer attempt to update the buffer
    concurrently, the assembly statements may get interleaved.

  • Interleaving depends upon how the producer and consumer
    processes are scheduled.

  • 이처럼 생산자와 소비자 사이에 임의적인 순서로 인터리빙 (interleaving)이 발생할 경우 사용자가 원하는 결과와 전혀 다른 결과가 매번 발생할 수 있으며, 이 때문에 데이터 불일치 문제가 발생할 수 있음.

Example: Incorrect Interleaving

Race Condition < 경쟁 상황 >

  • (+) 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황

  • The situation where several processes access and manipulate shared data concurrently.

  • The final value of the shared data depends upon which process finishes last.

  • 2개 이상의 프로세스 (혹은 스레드)에서 동일 (혹은 공유) 데이터에 동시에 접근해서 처리할 때, 실행의 결과는 어떤 순서에 따라 데이터에 접근하는지에 따라 달라짐.

  • 마지막에 수행되는 애가 누군지에 따라서 달라지게 되는 것이지!

  • To prevent race conditions, concurrent processes must be synchronized
    race condition을 방지하려면 동시 프로세스를 동기화해야 합니다.

  • The statements

    • counter ++;
    • counter --;
      must be performed atomically.

  • Atomic operation : an operation that completes entirely without interruption. - 중단 없이 완전히 완료되는 작업

  • (+) Multiprocessor system에서 여러 CPU들이 공유자원 (특히 메모리)에 접근 할 때, 접근 순서를 의도적 또는 비 의도적으로 직렬화하여 의도치 않는 결과를 피하는 operation : atomic operation

  • 경쟁 상태를 막기 위해서는 특정 시간에 한 프로세스만 공유 데이터를 사용하도록 해야 함.
  • 이렇듯 경쟁 상태를 막기 위한 방법을 프로세스 동기화 (process synchronization)

6.2 임계 구역 문제 : Critical Section (CS)

  • n processes all competing to use some shared data.

  • Each process has a code segment, called critical section, in which the shared data is accessed.
    각 프로세스에는 critical section이라는 코드 세그먼트가 있으며, 여기서 공유 데이터에 액세스합니다.

  • Problem - ensure that when one process is executing in its critical section, other process is not allowed to execute in its critical section.
    한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다는 사실 => 그 결과 경쟁 상태가 발생하지 않음.

  • 임계구역 문제는 프로세스들이 데이터를 협력적으로 공유하기 위하여 자신들의 활동을 동기화할 때 사용할 수 있는 프로토콜(약속)을 설계하는 것

  • 임계구역 ㅣ 여러 프로세스가 하나의 시스템에서 동작할 때 각 프로세스는 코드 세그먼트를 가지는 구역

  • (+) 한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다는 사실

  • (+) 임계구역 문제는 프로세스들이 데이터를 협력적으로 공유하기 위하여 자신들의 활동을 동기화할 때 사용할 수 있는 프로토콜(약속)을 설계하는 것

  • (+) 두 프로세스가 동시에 같은 임계 영역을 실행하지 못하게 되면 프로세스 동기화는 자연스레 이루어지고 데이터는 공동 공유 (cooperatively share)가 가능함.

  • Approaches to CS Implementation (임계구역 설정을 위한 다양한 접근법들)

    • Software-based approaches (software checks to ensure CS)
      – No guarantee that they will work correctly on modern computers
      코드가 알아서 cs 접근하게 조정
    • Synchronization instructions such as TestAndSet and Swap
      하드웨어마다 race condition 방지 가능한 안내문
    • Semaphore
    • High-level synchronization construct such as monitor

Properties of a CS Implementation

  • Ciritical Section 문제를 해결하기 위해선 위에서 명시한 것 처럼 3가지 요구조건을 만족해야 한다

① 상호 배재(Mutual Exclusion)

  • 프로세스 Pi가 임계 부분에서 실행 중이면 다른 프로세스는 해당 임계 부분에서 실행될 수 없습니다.
  • (+) 이미 한 process가 critical section에서 작업중이면 다른 process는 critical section에 진입해서는 안된다.

② 진행(Progress)

  • 해당 중요 섹션에서 실행 중인 프로세스가 없고 해당 중요 섹션에 들어가려는 일부 프로세스가 있는 경우 다음으로 중요 섹션에 들어갈 프로세스의 선택을 무기한 연기할 수 없습니다.
  • 임계구역을 사용하고 있지 않다면 다른 프로세스가 접근할 수 있도록 한다
  • 자신의 임계구역에서 실행되는 프로세스가 없고, 그들 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지를 결정하는데 참여할 수 있으며, 이 선택은 무기한 연장될수 있다.
  • (+) critical section에서 작업중인 process가 없다면 다른 process가 critical section에 진입할 수 있어야 한다.
  • (+) 임계영역에 어떤 스레드의 접근도 없을 때 항상 접근이 가능해야 한다
  • (+) 두 쓰레드에서 누가 먼저 들어갈 것인가에 대한 결정이 유한 시간 내에 일어나야한다는 조건

③ 한정된 대기(bounded waiting)

  • 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.
  • 임계구역 진입횟수에 한계를 두어 같은 프로세스가 계속해서 독점해서 사용하지 못하게 한다. -> 다른 프로세스들이 기아상태에 빠지지 않게 한다
  • (+) 모든 프로세스가 cs 에 들어가기 위한 기회를 가질 수 있게 하는 것
  • (+) 한 프로세스만 cs에 계속 들어가면 결국 프로세스는 starvation 현상을 겪
  • 즉 어떤 프로세스가 cs 사용하고 싶은데 한 프로세스가 계속 그 cs 점유하면 안되니 횟수나 제한이 필요

< Software-based Approach >

  • 프로세스는 작업을 동기화하기 위해 몇 가지 공통 변수를 공유 가능

< Software-based Approach (Algorithm 1) > - 공유변수

  • Shared variables: (turn 이라는 변수 공유)
    • int turn = 0; if turn == i then, Pi can enter its critical section.
    • turn 이라는 변수가 i 일 때 Pi가 cs 에 접근 가능

  • 내 차례가 아니라면 ( while ( turn != i ) ; ) spin lock 에 걸리게 하기

  • 내 차례라면 cs 진입

  • Satisfies mutual exclusion, but not progress requirement.
    상호배제는 만족인데 프로세스 요구조건은 만족 못했어

  • (+) 프로세스 요구 조건 : 두 쓰레드에서 누가 먼저 들어갈 것인가에 대한 결정이 유한 시간 내에 일어나야한다는 조건

  • Requires strict alternation (보라색 부분)
    – if turn == 0 and P1 is ready to enter its critical section, P1 cannot do so, even though P0 may be in its remainder section (not in the critical section).

< Software-based Approach (Algorithm 2) >

  • 다른 프로세스가 들어가고 싶다고 하면 기존 프로세스를 기다리게 하는 것

  • Shared variables

    • boolean flag [2];
    • initially flag [0] = flag [1] = false
    • if flag [i] == true, then Pi is ready to enter its critical section

  • Satisfies mutual exclusion, but not progress requirement.

  • Consider the case where,

    • T0 : P0 sets flag [0] = true
    • T1 : P1 sets flag [1] = true
      => 너무 둘다 양보함 => 둘다 true, 둘다 무한대기, 어느 누구도 자원할당받지 못하지
    • 두 쓰레드에서 누가 먼저 들어갈 것인가에 대한 결정이 유한 시간 내에 일어나야한다는 조건

< Software-based Approach (Peterson’s Algorithm) >

  • (+) Peterson 해결안은 Critical Section과 Remainder Section을 번갈아 가며 실행하는 두 개의 프로세스로 한정된다. 보통 프로세스는 P0와 P1로 번호를 매긴다. Peterson의 해결안은 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다. 이는 다음과 같다.

  • turn 이라는 아이를 추가해서 순서를 설정 (process 요구조건)

int turn; 
// Critical Section으로 진입할 순번을 나타내는 변수
boolean flag[2];
// 각 프로세스가 Critical Section으로 진입할 
// 준비가 되었다는 것을 표현한 배열

flag[i]가 참이라면 Pi가 Critical Section으로 진입할 준비가 된다.

  • (+) PLUS

  • Critical Section으로 진입하기 위해서는 Pi는 먼저 flag[i]를 참으로 만들고, turn을 j로 지정

  • 이렇게 함으로써 Pi는 Pj가 Critical Section으로 진입하기를 원한다면 진입 가능하다는 것을 보장한다.

  • 만일 두 프로세스가 동시에 진입하기를 원한다면 진입 turn은 거의 동시에 i와 j로 지정될 것이다.

  • 이 때의 경우 turn의 궁극적인 값이 둘 중 누가 먼저 Critical Section으로 진입할 것인가를 결정한다.

  • flag[j]가 false(Pj가 remainder section 수행)가 되거나 turn이 i(Pj는 준비완료됬고, Pi가 Entry Section에서 대기하고 있음)일 경우 Pi는 Critical Section에 들어갈 수 있다.

  • (+) PLUS 2

  • 두 프로세스에 각각 플래그 (깃발)를 세워 프로세스가 실행 중임을 나타냄. (각 플래그가 true인 경우 실행 중인 것)

  • turn 변수는 다음에 실행할 프로세스를 가리킴.

  • 한 프로세스의 플래그가 true이면 다른 프로세스가 실행되지 못하도록 제한하여 두 프로세스가 동시에 데이터에 접근하는 상황을 막음.

1. 상호 배재(Mutual Exclusion)

  • flag[2]와 turn 변수에 의해서 하나의 프로세스만 Critical Section에서 연산을 수행할 수 있음으로 Mutual Exclusion는 지켜진다.

2. 진행(Progress)

  • 각 프로세스가 자신이 Critical Section을 수행할 동안 while문에서 다른 프로세스를 유한하게 대기하도록 만드는 방법을 통하여 Progress를 지킬 수 있다.

3. 한정된 대기(bounded waiting)

  • 각 프로세스들은 Critical Section에 진입하려는 요청을 한 후부터 다른 프로세스가 Critical Section을 수행하는 동안 유한하게 대기함으로 bounded waiting 또한 지켜진다.

  • No guarantee to work on modern computers
    (i.e., processors or compilers may reorder instructions with no dependencies)
    Peterson의 해결안은 최신 컴퓨터 아키텍처에서 작동한다고 보장되지 않는다.
    주된 이유는 시스템 성능을 향상하기 위해 프로세스 또는 컴파일러가 종속성이 없는 읽기 및 쓰기 작업을 재정렬 할 수 있기 때문이다

  • What value of x will be printed here ?
    Peterson 해결안의 entry section의 첫 두 문장의 순서를 바꾸게 되면 임계구역 문제를 해결할 수 없다.
    (initially, boolean flag = false; x = 0;)

  • (+) peterson solution은 완벽한가?

  • peterson solution은 3가지 요구조건을 모두 만족 !

  • mutual exculsion

    • while(flag[j] && turn == j) 로 busy waiting을 사용하는 동기화 프로세스. 어떠한 스레드라도 해당 조건을 만족하면 무한루프에 빠진다.
    • 다른 프로세스에서 반복분의 조건을 변경한다면 무한루프에서 탈출할 수 있음
    • 하나의 프로세스가 busy waiting을 넘어 그 아래 임계구역을 넘어갈때 다른 프로세스가 busy waiting의 반복문 조건을 만족하도록 flag와 turn을 조작 => 오직 하나의 프로세스만이 임계구역에 도달할 수 있음

  • progress

    • 크리티컬 섹션을 이용하는 프로세스가 없는 경우, 어떤 프로세스라도 지체없이 크리티컬 섹션에 접근할 수 있는가?
    • 각 프로세스에 대해 초기 flag 값은 false를 가지고 있다가 크리티컬 섹션에서 할 작업이 생기면 피터슨의 솔루션에 접근하여 true 값을 가진다
    • flag가 2개인 경우에는 해당 조건을 고려할 필요가 없다. 상호배제에 의해서 이미 동기화 문제가 해결되기 때문

  • bounded waiting

    • 어떠한 프로세스도 무한히 대기하는 기아상태(starvation)에 빠져서는 안된다
    • 프로세스가 2개인 해당 솔루션에서는 한쪽이 대기를 하고있다면 다른 한쪽이 critical section을 작업을 한 후 해당 critical section을 작업한 프로세스의 flag가 false가 되는 순간 대기하던 프로세스가 바로 무한루프를 빠져나와 임계구역으로 진입(실행)하므로 기아상태는 발생하지 않는다

Synchronization Instruction

< Synchronization Instruction >

  • Many systems provide hardware support for critical section code.
    많은 시스템이 중요한 섹션 코드에 대한 하드웨어 지원을 제공합니다.

  • In uni-processors, we could disable interrupts.
    유니 프로세서에서는 인터럽트를 비활성화할 수 있습니다.

    - Currently running code would execute without preemption.
현재 실행 중인 코드는 선점 없이 실행됩니다.

- This is generally too inefficient on multiprocessor systems.
Operating systems using this are not broadly scalable.

멀티프로세서 시스템에서는 일반적으로 너무 비효율적입니다.
이를 사용하는 운영 체제는 광범위하게 확장되지 않습니다.

  • Modern machines provide special atomic hardware instructions.

  • (atomic = non-interruptable)

    • Either test memory word and set value (TestAndSet)
    • Or swap contents of two memory words (Swap)

  • (+) 많은 현대 기계들은 한 워드(word)의 내용을 검사하고 변경하거나, 두 워드의 내용을 원자적으로 교환(swap)할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어들을 제공,이 명령어들을 추상적으로 표현하자면 test_and_set()과 compare_and_swap()이 있다.

Synchronization Instruction - TestAndSet

  • atomic 하드웨어 instructions
  • 명령어는 원자적(atomically)으로 실행.
  • 아래의 그림은 test_and_set() 명령어의 정의문


  • 여기서 lock 을 무족권! true 로 변환하는 것

  • Critical Section의 Mutucal Exclsion 해결 알고리즘

  • lock이라는 공유 변수

  • does not meet bounded waiting requirement

  • (+) 한정 대기 : 어떠한 프로세스도 무한히 대기하는 기아상태(starvation)에 빠져서는 안된다

  • (+) 위의 알고리즘은 lock이라는 공유 변수가 한 프로세스에서 false일 경우

  • (+) lock을 true로 만들고 (test&set) 자신은 Critical Section으로 들어간다.

  • (+) Critical Section에서 빠져나온 프로세스가 lock을 false로 만들면, 다른 프로세스가 Critical Section에 들어가고 이러한 과정이 반복되는 알고리즘

  • (+)

    target = FALSE : target = TRUE, 반환값은 FALSE
    target = TRUE : target = TRUE, 반환값은 TRUE

  • (+) TestAndSet()은 입력값의 상태를 그대로 반환하고, 입력값은 항상 TRUE로 갱신하는 함수로 정리할 수 있다. TestAndSet() 명령어는 아래와 같이 사용된다. lock은 전역 변수다.

  • lock = FALSE 인 경우만 진입 가능하고, 퇴출 구역에서 lock = FALSE 로 갱신해줘야 다른 프로세스가 진입할 수 있다. lock을 획득한 하나의 프로세스만 임계구역에 진입할 수 있다는 점에서 Mutual Exclusive를 만족하고, 퇴출 구역에서 lock을 다시 FALSE로 바꿔준다는 점에서 Progress를 만족한다.

  • 그런데 TestAndSet()만 사용하면 한 가지 문제가 있다. 바로 임계구역의 세 가지 요구사항 중 Bounded Waiting을 만족하지 않는다는 것이다. 그 이유는 프로세스의 도착 순서와 무관하게 임계 구역에 진입할 프로세스가 정해지기 때문이다. 즉, fair 하지 않다! (순서 보장이 안되니깐 그 누구도 안될 수도 ! )
    => 그렇다면 프로세스의 도착 순서를 고려해준다면?
    => fair하기 때문에 임계구역의 세 가지 조건을 모두 만족하므로 유효한 알고리즘이 된다. Bounded Waiting 조건을 만족시켜주기 위해서는 아래와 같이 코드를 수정하면 된다.
    => Mutual Exclusion with TestAndSet()

Synchronization Instruction - Swap

  • (+) SWAP 정의문
  • Atomically swap two variables.

  • LOCK 이랑 KEY 를 SWAP

  • LOCK을 풀어주면 다른 PROCESS 들 접근 가능

  • (+) SWAP 설명 블로그 : 블로그 출처
    역시나 프로세스가 p0, p1 두개가 있다고 하자
    원래 lock = 0이라고 하고 시작하자.

  • p0이 먼저 compare_and_swap을 실행하면 기존값이던 0을 반환하므로 while문 조건은 false가 되어 critical section으로 들어간다.

  • p1 입장에서 보면 lock은 1로 바꼈으니 compare_and_swap이 1을 반환하므로 조건은 true가 되어 critical section으로 들어가지 못한다.

  • 하지만 p0가 critical section에서 lock=0을 수행하게 되면 그때 p1은 compare_and_swap이 0을 반환하여 조건이 false가 되고 critical section으로 들어갈 수 있다.
    이러한 일이 반복적으로 수행된다.

하지만, 위의 예시는 bounded waiting 요구를 충족하지 못한다.
이유는 아래와 같다.

Mutual Exclusion with TestAndSet()

  • 유한 대기 문제 해결 가능
boolean waiting[n]; 
boolean lock;

do{
    waiting[i] = true; // i번째 프로세스가 진입 요청
    key = true; 
    while(waiting[i] && key)
    	key = TestAndSet(&lock); // key = false, lock = true
    waiting[i] = false;
    
    CRITICAL SECTION
    
    (+) 프로세스의 도착 순서를 고려
    
    j = (i + 1) % n; // j 값으로 자신(i)의 다음 프로세스 값을 선정
    while((j != i) && !waiting[j])
    	j = (j + 1) % n; // 다음 프로세의 존재 탐색
        
    if(j == i) // 기다리는 애가 없어서 다시 자기 차례
    	lock = false;
    else // 가디라는 애가 있기 때문에 진입 구역의 while문 탈출할 수 있게 한다
    	waiting[j] = false;
        
    REMAINDER SECTION
    
} while(1);

  • (+)
  • pi가 critical section에 진입하는 경우는 오직 waiting[i] == false 이든지 key == 0 이 되어야 한다. lock이 0일 때에만 key가 0이 되고 lock 이 1로 바뀌면서 무한 루프에서 빠져나올 수 있다.
  • waiting 이라는 대기 순서를 통해 순서 보장
  • waiting[i]를 false로 바꾸고 critical section을 실행한 뒤, i를 순차적으로 증가시켜 자신과 같을 때까지 혹은 i가 기다리고 있을 때까지 무한 루프를 돌고, 선택된 프로세스를 critical section에 진입할 수 있도록 해주는 알고리즘

Semaphores

  • Synchronization tool that does not require busy waiting.

  • busy waiting : OS에서는 원하는 자원을 얻기 위해 기다리는 것이 아니라 권한을 얻을 때까지 확인하는 것을 의미

  • Semaphore S represents an integer variable, that can only be accessed via two indivisible (atomic) operations.
    세마포 S는 정수 변수로서, 초기화를 제외하고는 단지 두 개의 표준 원자적(atomical) 연산 wait()와 signal()로만 접근할 수 있다.

(1) wait

(2) signal

  • wait()와 signal() 연산 시 세마포의 정수 값을 변경하는 연산은 반드시 원자적으로 수행

< Two Types of Semaphore >

(1) Semaphores : Counting

Counting semaphore – integer value can range over an unrestricted domain.

  • 유한한 개수를 가진 자원에 대한 접근을 제어하는데 사용
  • 카운팅 세마포의 값은 제한 없는 영역

(2) Semaphores : Binary == mutex lock

  • (+) 1이면 진입하고 0이면 기다림

– integer value can range only between 0 and 1; can be simpler to implement than counting semaphore; also known as mutex lock.

mutex semaphore라고도 부르며 변수가 0 또는 1의 binary 값만 갖는 semaphore이다.

  • 이진 세마포의 값은 0과 1사이의 값만 가능

  • (+) 뮤텍스 락: 가장 간단한 동기화 도구. 임계 영역에 진입할 때 lock을 걸어 다른 프로세스에서 접근하지 못하게 하고, 임계 영역에서 빠져나올 때 lock을 푸는 방식. (2개의 프로세스 대상)

– In general, busy waiting wastes CPU cycles that some other process might be able to use productively.

– Spinlock – process spins while waiting for the lock.
: context switch 보다 spin lock으로 기다리게 하는 것이 better

– Have an advantage in that no context switch is required.
– When locks are expected to be held for short times, spinlocks are useful.
– Often employed on multiprocessor systems.

  • (+) 세마포어 구조체의 value 값이 1로 초기화된 경우다. 아까 위에서 value는 '사용 가능한 자원의 수'라고 했다. value가 1이라는 것은 여러 개의 프로세스가 하나의 자원을 가지고 경쟁한다는 뜻이다. 따라서 Mutex Lock와 거의 비슷하다고 할 수 있다.
  • (+) 다만 세마포어는 waiting queue를 가지고 있어 busy waiting 현상을 방지할 수 있다는 점만 다르다

< Using Semaphores >

  • Busy Waiting을 피하기 위해 세마포 S를 대기하면서 일시 중지된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작되어야 한다.
  • 프로세스는 sleep() 연산에 의해서 일시 중지되고
  • wakeup() 연산에 의하여 재시작된다. (대기상태 <-> 준비 완료 상태)

  • signal 이 불리면 MUTEX: 다음 대기에 있던 process 가 CS 들어갈 수 있는 그런 구조

  • (+) -1하는 함수를 wait, +1하는 함수로 signal

  • (+)

  • shared data를 사용하려고 봤는데 shared data가 없어! 그럼 기다려야하니까 이 함수의 이름을 wait이라고 지었고,

  • 지금 비어있는 shared data가 있다! 그럼 안기다리고 사용하는거죠 (-1)

  • 그런데 만약 semaphore의 값이 0이야. 그러면 남은게 하나도 없다는 뜻이니까 기다려야한다고 해서 어쨋든 이름이 wait입니다.

  • 다 쓰고 나서는 세마포어 값을 +1시켜주면 돼죠?!

  • 내가 지금 다 쓴 이 shared data를 누군가 쓰려고 기다릴 수 있어요. 그래서 개한테 나 다썼으니 너 써! 신호를 보내줘야 하겠죠? 그래서 이 함수가 signal

  • (+) 세마포어 - 초기화 1 , 누가 사용하면 0 (줄어들어)

  • (+) lock - 초기화 0 , 누가 사용하면 1

  • mutex 초기값 : 1

  • semaphore flag 초기값 : 0

  • (+)

    • wait() 메소드가 호출되면 무한루프로 대기하는 것이 아닌, 프로세스를 대기 큐 (wait queue)로 보내 대기하게끔 함.

    • 이후 다른 프로세스에서 signal() 메소드를 호출하면 대기 큐에 있던 프로세스를 깨우고 (wakeup)

    • 준비 큐 (ready queue)로 보내 CPU 자원을 획득하기를 기다리도록 함.

      typedef struct
{
    int value;
    struct process* list; // linked list
} semaphore;

wait(semaphore* S)
=> 나를 대기큐로
{
    S->value--;
    if (S->value < 0)
    {
        add this process to S->list; // wait state
        sleep(); // 대기 큐로 이동함.
    }
}

signal(semaphore* S)
=> 나를 리스트(대기큐) 제거, 준비큐로 
{
    S->value++;
    if (S->value <= 0)
    {
        remove a process P from S->list; // ready state
        wakeup(P); // 준비 큐로 이동함.
    }
}

Deadlock & Starvation

  • Deadlock
    – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes.

대기 큐를 가진 Semaphore 구현은 두 개 이상의 프로세스들이, 오로지 대기 중인 프로세스들 중 하나에 의해서만 야기될 수 있는 signal()연산를 무한정 기다리는 상황이 발생할 수 있다. 이런 상태에 도달했을 때, 이들 프로세스들

  • Let S and Q be two semaphores initialized to 1.

출처 : 블로그

  • (+) S와 Q는 각각 1로 초기화된 binary semaphore라고 가정하자.
    두 개의 프로세스가 위와 같은 순서로 binary semaphore를 호출하면 어떻게 될까?
    첫 번째 순서를 먼저 보자. P0은 wait(S)를 호출했으므로 S의 value는 0이 되고, P1은 wait(Q)를 호출했으므로 Q의 value도 0이 된다.
    두 번째 순서를 보자. P0은 wait(Q)를 호출한다. Q의 value 값은 0이므로 P0은 block 상태가 된다. P1도 wait(S)를 호출하면 같은 이유로 block 상태가 된다. 어느 하나가 signal을 호출해야 ready queue에서 빠져나올 수 있는데 둘 다 block 상태이기 때문에 서로 영원히 기다리는 기이한 현상이 발생해버렸다. 이를 deadlock이라고 한다. 데드락은 다다음 글부터 자세히 다룰 예정이기 때문에 우선 넘어가자. 서로 영원히 기다리므로 starvation 문제도 덤으로 생긴다.
  • Starvation – indefinite blocking. A process may never be
    removed from the semaphore queue in which it is suspended.

Monitors

  • (+) mutex lock 혹은 Semaphores 를 사용할 때에도 타이밍 오류는 여전히 발생할 수 있다. 예로들어, wait()과 signal() 연산의 순서가 뒤바뀌는 경우, Critical Section이 끝나고 signal()대신 wait()이 호출되는 경우

  • (+) 모니터 형은 모니터 내부에서 프로그래머가 정의한 상호 배제가 보장되는 일련의 연산자 집합을 포함하는 ADT

  • (+) 모니터 구조물은 모니터 안에 항상 하나의 프로세스만이 활성화되도록 보장

  • (+) Monitor type: 모니터 내부에서 프로그래머가 정의한 mutual exclusion이 보장되는 일련의 연산자 집합을 포함하는 ADT이다.
    ADT(추상화된 데이터 형, abstract data type)은 데이터와 이 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어 보호한다. 이때 함수의 구현은 ADT의 특정한 구현과 독립적이다.
    오직 하나의 프로세스만 모니터에서 active하다(mutual exclusion)

  • High-level synchronization construct that allows the safe sharing of an abstract data type among concurrent processes (e.g., synchronized in Java).
    편리하고 효과적인 동기화 도구를 지지하기 위한 high-level language contructs.

    Monitors with Condition Variables

  • (+) condition이라는 구조물로 동기화 기법들을 제공해 보자.

  • (+) 자신의 동기화 기법을 작성할 필요가 있는 프로그래머는 하나 이상의 condition 형의 변수를 정의할 수 있다

  • Condition Variables은 추가적인 동기화 기법(additional synchronization mechanism)

  • Condition 형의 변수 정의(Variable declaration)

    • condition x, y;

  • To allow a process to wait within the monitor, a condition variable must be declared, as condition x, y;

  • condition형 변수에 호출될 수 있는 연산은 오직 wait()와 signal()

  • The operation x.wait(); means that the process invoking this operation is suspended until another process invokes x.signal();

이 연산을 호출한 프로세스는 다른 프로세스가 x.signal()을 호출할 때까지 일시 중지 되어야 한다는 것을 의미한다.

  • The x.signal operation resumes exactly one suspended process. If no process is suspended, then the x.signal operation has no effect.

일시 중지된 프로세스를 풀어준다. 만약 waiting하고 있는 프로세스가 없다면 아무일도 일어나지 않는다.

More on Condition Variables

  • Suppose that when the x.signal() operation is invoked by a process P, there is a suspended process Q associated with condition x (already in the monitor).

만약 process P가 x.signal()을 호출하고,
process Q가 x.wait()에서 일시 중단 됐다면,
무엇이 다음에 일어날까?

Q와 P 모두 동시에 실행될 수 없기 때문에 Q가 진행됐다면 P는 대기해야 한다.
모니터에서는 오직 하나의 프로세스만 실행이 가능하기 때문이다.
그래서 여기에는 두가지 상황이 일어날 수 있다. 그것은 아래와 같다.

< Possible solutions >

(1) Signal and wait :

만약 P가 x.signal()을 불렀다면 Q가 실행되고 P는 Q가 monitor을 떠날때까지 기다리거나 다른 condition을 기다랴야 한다. (Q가 먼저 시작)
P either waits until Q leaves the monitor, or waits for another
condition. (Hoare’s semantic) – a condition is true at a particular
instant in time when the signal occurs

(2) Signal and continue :

P가 x.signal()을 불렀다면 Q는 P가 monitor을 떠날때까지 기다리거나 다른 condition을 기다려야 한다. (P가 끝날때까지 기다리기)
위의 둘은 모두 장단점이 존재한다. 하지만 signal and continue가 조금 더 reasonable하다.

Q either waits until P leaves the monitor, or waits for another
condition. Q continues its execution in the monitor by rechecking the condition. (Brinch Hansen’s semantic or Mesa monitor semantic) – there will be fewer context switches than with the Hoare approach

profile
Yunny.Log
이전 포스트

OS | Chapter 5 : Synchronization CPU Scheduling

다음 포스트

OS | Chapter 7 Synchronization examples

post-custom-banner

0개의 댓글