[OS] Ep.9 Synchronization(1)

GLICO·2024년 12월 1일

OS

목록 보기

9/11

Classic Example

Withdrawing money form a bank account

친구들과 같이 돈을 관리하는 계좌에 30만원이 들어 있는 상황
A와 B가 서로 다른 ATM에 가서 동시에 10만원 씩 출금한다면?

int withdraw(account, amount){
	balance = get_balance(account);
    balance = balance - amount;
    put_balance(account, balance);
    
    return balance;
}

Local variables are NOT shared among threads

Refer to data on the stack
Each Thread has its own stack
Never pass/share/store a pointer to a local variable on anoter thread's stack

공유 가능한 것들

Global variables (전역변수)
Stored in static data segment, accessible by any thread
Dynamic objects (동적 할당된 객체)
Stored in heap, shared through the pointers

각각의 Thread는 ( $T_1, T_2, T_3$ )는 자신의 Register, Stack을 가지고 있고 다른 Thread의 Stack에는 접근할 수 없다.
Code, Data, File을 공유한다.

Race Condition

Concurrency leads to non-deterministic results!

Program results vary from run to run even with same inputs, depending on timing

공유 데이터에 대한 동시 접근은 데이터의 일관성(Consistency)를 해치는 결과를 낳을 수 있음

Race Condition
공유 데이터에 대해 여러 Process가 동시에 접근, 변경을 시도하는 상황

데이터 일관성을 유지하기 위해서는 서로 협력하여 수행되는 Process들(Cooperating Process)이 순차적으로 수행하게 만드는 기법이 필요함

Process 간의 동기화 (Process Synchronization)
Synchronization restricts the concurrency
(모순적이게도 Concurrency를 해칠 수 밖에...)
Scheduling is not under programmer's control

Critical Section

여러 Process들이 공유하는 데이터에 접근하는 Code 영역
한 번에 오직 하나의 Proecess만이 Critical Section에 진입해야 함

Critical Section을 가지는 Process의 Modeling

Critical Section 해결의 조건들

Critical Section 문제를 해결하는 Algorithm은 아래와 같은 세 가지 조건을 만족해야 함

Mutual Exclusion (상호 배제)
만약 Process A가 Critical Section에 진입해 있다면, 다른 모든 Process는 진입할 수 없어야 함
Progress (진행)
만약 어떤 Process도 Critical Section내에 있지 않고, Critical Section에 진입하려는 Process가 존재한다면, Remainder Section에서 실행 중이 아닌 Process들 (= 진입하려는 Process들) 만이 누가 진입할지 결정할 수 있어야 함 -결정은 무한히 연기될 수 없음 (Deadlock-free)
Bounded Waiting
Process가 Critical Section에 진입할 때까지 걸리는 시간에 Limit이 존재해야 함(Starvation-free)

두 Process를 위한 Algorithm

Shared Variables:

int turn = 0; 으로 초기화
turn = 0일 때,

만족 조건 : Mutual Exclusion
불만족 조건 : Progress, Bounded Waiting

turn=0으로 초기화 된 것이 문제이다.
프로세스 $P_0$ 가 언제 실행될지 모르는 상황에서 $P_1$ 이 실행되면은 $P_1$ 은 무한 루프를 돌고 있다. (Progress, Bounded Waiting 불만족)

다른 알고리즘(Flag)

Shared Variables:

boolean flag[2]; flag[0] = flag[1] = flase로 초기화
flag[0] = true일 때, $P_0$ 가 critical section에 진입 가능
flag[1] = true일 때, $P_1$ 가 critical section에 진입 가능
만족 조건 : Mutual Exclusion
불만족 조건 : Progress, Bounded Waiting

그림과 같이 1,2,3,4 순서대로 코드가 실행되버리면, flag[0]와 flag[1]이 모두 true의 값을 가지게 되고 두 프로세스는 무한 루프에 빠져버려 진행되지 않는다.

Peterson Solution

Shared Variables:

int turn;
boolean flag[2]; flag[0] = flag[1] = flase로 초기화

flag와 turn을 모두 사용하는 방식이지만, turn을 0으로 초기화하지 않음.

만족 조건 : Mutual Exclusion, Progress, Bounded Waiting

두 Process가 동시에 수행되더라도, Turn 값에 의하여 결정됨

Peterson Solution의 한계

3개 이상의 Process에서는 구현이 쉽지 않음.

하드웨어로 처리하면 알고리즘이 매우 간단하게 됨

간단한 방법

Critical Section에 들어가면서 Interrupt를 Disable함

User Program이 Interrupt를 Control하는 것은 바람직하지 않음

Scalable 하지 않음

Process의 숫자가 많아 질 때 문제가 생길 소지

동기화를 위한 Instruction이 도입됨

Synchronization Instruction

CPU에서 지원하여 원자적(Atomic)으로 수행되는 명령어(Instruction)를 이용

원자적이란?
명령어가 수행되는 동안 방해 받지 않음(= Uninterruptible)

Test and Set 명령어

아래의 코드는 Atomic하게 동작함

boolean TestAndSet(boolean *target){
	boolean rv = *target;
    *target = true;
    return rv;
}

Mutual Exclusion with Test-and-set

Shared Variables:

boolean lock = false;

Process $P_i$

do {
	while(TestAndSet(&lock));
    	critical section
    lock = false;
    	remainder section
}

critical section에 들어오면서 lock을 true로 변경해줌 + return값은 아직 false

Mutual Exclusion with Swap

Shared Variables:

boolean lock;
boolean waiting[n];

Process $P_i$

do {
	waiting[i] = true;
    while(waiting[i] == true)
    	swap(&lock, &waiting[i]);
    		critical section
    lock = false;
    	remainder section
}

H/W에서 제공하는 Instruction인 TestAndSet()과swap() 연산은 Atomic하기 때문에, Mutual Exclusion과 Progress(Deadlock-free)를 만족하지만, Bounded Waiting 같은 조건은 User Program에서 제공해야 한다.

# Example : Bounded Waiting Solution

// Shared Data
boolean waiting[n];
boolean lock; 

do {
	waiting[i] = TRUE;
    key = TRUE;
    while(waiting[i] && key)
    	key = TestAndSet(&lock);
    waiting[i] = FALSE;
    
    // critical section
    
    j = (i + 1) % n;				// i 이후의 프로세스들부터 보겠다.
    while((j != i) && !waiting[j])  // 순회하면서 waiting = TRUE인 프로세스를 찾음
    	j = (j + 1) % n;			// 순차적으로 다음 프로세스를 본다
    if (j == i)   					// 대기중인 프로세스가 없다면, lock을 해제한다
    	lock = FALSE;
    else
    	waiting[j] = FALSE;			// 대기중인 프로세스가 있다면 해당 프로세스를 critical section으로...
        
    // remainder section
    
} while (TRUE);

Semaphores

세마포어: 두 개의 원자적 연산을 가지는 정수 변수

원자적인 연산:
- Wait() 또는 P()
- Signal() 또는 V()
이 변수는 2개의 원자적인 연산(Atomic Operation)에 의해서만 접근됨

P는 Critical Section 들어가기 전에, V는 나와서 수행함

P와 V연산은 서로 독립적으로, 그리고 원자적으로 수행됨

하나의 Process가 P를 수행하여 세마포어의 값을 수정하는 동안,
다른 Process에서 P나 V를 수행하여 같은 세마포어의 값을 수정하지 못함

Semaphores의 구현 - Busy Waiting

Busy Waiting 이용 (Original)

P(Sem) {
	while (Sem <= 0);
    Sem = Sem - 1;
}
  
S(Sem) {
	S = S + 1;
}

Busy Waiting은 Critical Section에 진입할 조건이 될 때까지 Loop를 돌며 기다린다.

단점
CPU Cycle을 낭비할 수 있음
대기 중인 Process 중에서 누가 Critical Section에 진입할지 결정할 수 없음 (Bounded Waiting (= Starvation)

Semaphores의 구현 - Sleep Queue

Sleep Queue를 이용한 구현

Busy Waiting 방식의 CPU Cycle을 낭비하는 문제를 해결
Semaphore의 자료구조에 Sleep Queue를 추가하여, 대기 중인 Process를 관리
- Semaphore의 값이 양수가 되어 Critical Section에 진입이 가능하게 되면, Sleep Queue에서 대기 중인 Process를 깨워 실행시킴

typedef struct {
	int value;					// 세마포어 값
    struct process *list;		// 세마포어를 대기하는 프로세스의 sleep queue
} semaphore;

P(semaphore *S){
	S -> value--;
    if (S -> value < 0){
		add this process to S -> list;	// 프로세스를 sleep queue에 삽입
        sleep();
    }
}

V(semaphore *S){
	S -> value++;
    if (S -> value <= 0)
    	remove a process P from S -> list;  // 프로세스를 sleep queue에서 꺼내온 후,
        wakeup(P);							// 실행
    }
}

Semaphores의 종류

2가지의 Semaphore

Counting Semaphore
- Semaphore 값은 범위가 정해져 있지 않음
- 초기값은 가능한 자원의 수로 정해짐
Binary Semaphore
- Semaphore value가 가질 수 있는 값은 0과 1
- Counting Semaphore보다 구현이 간단함

Binary Semaphore를 이용하여 Counting Semaphore를 구현할 수 있음

Binary Semaphore는 TestAndSet()과 같은 Hardware의 도움을 받아서 구현할 수 있음

H/W Instruction(TestAndSet) -> Binary Sem -> Counting Sem

Binary Semaphore의 구현

TestAndSet()을 이용하여 구현

Semaphore S : 현재 Critical Section에 진입한 Process가 있는지 나타냄 (True or False)

P(S)

while (test_and_set(&S));
S의 값이 리턴되고, S는 true로 바뀜

V(S)

S = false;
진입한 Process가 없음을 나타내어 wait()에서 대기 중인 Process를 진입 가능하도록 함

Counting Semaphore의 구현

Binary Semaphore를 이용하여 구현

Counting Semaphore를 CS라 하고, value는 C = 0이라 하자.
2개의 Binary Semaphore S1, S2를 이용 (S1 for Mutex, S2 for delay)
S1 = 1, S2 = 0 으로 초기화 (C가 양수라고 가정)

# Wait Operation (P)
P(S1);
C--;
if (C < 0){
	V(S1);
    P(S2);
}
else
	V(S1);
    
    
# Signal Operation (V)
P(S1);
C++;
if (C <= 0) {
	V(S2);
}
V(S1);

Semaphore의 구현

Kernel이 Single Thread인 경우

P/V를 System Call로
kernel내에서 처리하여 Semaphore 동작을 구현함
Kernel내의 수행이 Non Preemptive이므로, Kernel에 들어간 것이 Critical Section에 들어간 것임

Kernel이 Multithread인 경우

P/V를 System Call로
Kernel 내에서 별도로 동기화를 진행

Semaphore의 단점

Deadlock이 발생할 가능성이 존재함

P와 V의 연산이 분리되어 있기 때문에 잘못 사용할 경우에 대책이 없음

P(); -> Critical Section -> P();
Critical Section 후에 Lock을 풀어주는 V()가 없으므로, 한 Process가 Critical Section에 진입하면, 나올 수 없다.
(다른 Process들이 Critical Section에 진입 못하므로 Deadlock 발생)
V(); -> Critical Section -> P();
Critical Section 전에 Lock을 걸어주는 P()가 없으므로, 여러 Process가 동시에 Critical Section에 진입 할 수 있으므로, Mutual Exclusion을 보장 못함

Deadlock

두 개 이상의 Process들이 끝없이 이벤트를 기다리고 있는 상황
그 이벤트는 기다리고 있는 Process만이 발생 시킬 수 있는 것

Monitor

High-level 언어에서의 동기화 방법

Java의 Thread에서 동기화를 위한 방법으로 Monitor가 사용됨

한 순간에 하나의 Process만 Monitor에서 할동하도록 보장

공유데이터(필드값)와 공유데이터를 접근하는 코드(함수)를 하나의 모니터(객체)에 구성

Application은 Semaphore와 같이 P와 V연산에 대한 고려 없이 Procedure를 호출하는 것 만으로 동기화를 해결할 수 있음

Procgrammer는 동기화 제약 조건(P, V)을 명시적으로 코드화 할 필요 없음

GLICO

Its me Glico

이전 포스트

[OS] Ep.8 Thread

다음 포스트

[OS] Ep.9 Synchronization(1)

OS

Classic Example

Withdrawing money form a bank account

Sharing Resources

Local variables are NOT shared among threads

공유 가능한 것들

Race Condition

Concurrency leads to non-deterministic results!

공유 데이터에 대한 동시 접근은 데이터의 일관성(Consistency)를 해치는 결과를 낳을 수 있음

데이터 일관성을 유지하기 위해서는 서로 협력하여 수행되는 Process들(Cooperating Process)이 순차적으로 수행하게 만드는 기법이 필요함

Critical Section

Critical Section

Critical Section을 가지는 Process의 Modeling

Critical Section 해결의 조건들

Critical Section 문제를 해결하는 Algorithm은 아래와 같은 세 가지 조건을 만족해야 함

두 Process를 위한 Algorithm

Shared Variables:

다른 알고리즘(Flag)

Shared Variables:

Peterson Solution

Shared Variables:

Peterson Solution의 한계

3개 이상의 Process에서는 구현이 쉽지 않음.

간단한 방법

Critical Section에 들어가면서 Interrupt를 Disable함

User Program이 Interrupt를 Control하는 것은 바람직하지 않음

Scalable 하지 않음

동기화를 위한 Instruction이 도입됨

Synchronization Instruction

CPU에서 지원하여 원자적(Atomic)으로 수행되는 명령어(Instruction)를 이용

Test and Set 명령어

Mutual Exclusion with Test-and-set

Shared Variables:

Process PiP_iPi​

Mutual Exclusion with Swap

Shared Variables:

Process PiP_iPi​

Semaphores

세마포어: 두 개의 원자적 연산을 가지는 정수 변수

P는 Critical Section 들어가기 전에, V는 나와서 수행함

P와 V연산은 서로 독립적으로, 그리고 원자적으로 수행됨

Semaphores의 구현 - Busy Waiting

Busy Waiting 이용 (Original)

Busy Waiting은 Critical Section에 진입할 조건이 될 때까지 Loop를 돌며 기다린다.

Semaphores의 구현 - Sleep Queue

Sleep Queue를 이용한 구현

Semaphores의 종류

2가지의 Semaphore

Binary Semaphore를 이용하여 Counting Semaphore를 구현할 수 있음

Binary Semaphore는 TestAndSet()과 같은 Hardware의 도움을 받아서 구현할 수 있음

Binary Semaphore의 구현

TestAndSet()을 이용하여 구현

Semaphore S : 현재 Critical Section에 진입한 Process가 있는지 나타냄 (True or False)

P(S)

V(S)

Counting Semaphore의 구현

Binary Semaphore를 이용하여 구현

Semaphore의 구현

Kernel이 Single Thread인 경우

Kernel이 Multithread인 경우

Semaphore의 단점

Deadlock이 발생할 가능성이 존재함

P와 V의 연산이 분리되어 있기 때문에 잘못 사용할 경우에 대책이 없음

Deadlock

Deadlock

Monitor

High-level 언어에서의 동기화 방법

한 순간에 하나의 Process만 Monitor에서 할동하도록 보장

Application은 Semaphore와 같이 P와 V연산에 대한 고려 없이 Procedure를 호출하는 것 만으로 동기화를 해결할 수 있음

[OS] Ep.8 Thread

[OS] Ep.10 Synchronization(2)

0개의 댓글

Process $P_i$

Process $P_i$