졍's 기술 블로그

1. 교착상태(Deadlock)

: Process나 Thread가 결코 일어날 수 없는 특정 Event를 기다리는 상태

2. 교착 상태의 4가지 필요 조건

4가지를 모두 만족해야 교착 상태가 발생한다.

• 상호 배제(Mutual Exclusion)
  : 여러 Process/Thread가 동시에 한 자원에 접근하지 못하도록 막는것
• 점유와 대기(Hold and Wait)
  : Process/Thread가 자원을 점유한 상태로 다른 자원을 점유하기 위해 대기하는 것
• 비선점(Nopreemption)
  : Process에서 자원을 할당 받으면 작업을 완료할 때까지 System에서 Process의 제어를 뺏을 수 없음
• 순환 대기(Circular Wait)
  : 점유와 대기를 하는 형태로 Cycle에 갇혀 빠져나갈 수 없는 상태

3. 교착 상태 해결법

: 교착 상태의 해결법으로는 교착 상태 예방, 교착 상태 회피, 교착 상태 탐지 및 복구, 교착 상태 무시가 있다.

3.1. 교착 상태 예방

: 교착 상태 필요 조건 중 하나를 거부하는 방식으로 예방하는 방법이다.

교착 상태는 발생하지 않으면 좋지만, 교착 상태가 발생하지 않는 환경을 만들어버린다면 자원을 효율적으로 사용할 수 없다.

e.g., 필요 조건 중 점유와 대기 조건을 거부해 한 Process가 자신이 필요한 자원을 모두 사용할 수 있을 때만 작업을 시작한다면 자원을 효율적으로 사용할 수 없다.

3.2. 교착 상태 회피

: 교착 상태를 인정하고 피해가는 방법으로 자원을 요청할 때마다 System의 상태를 판단하고 회피하는 전략을 사용한다.

☞ Overhead가 심하다.

e.g., 은행원 Algorithm

은행원 Algorithm
: System을 안전 상태/불안전 상태(교착 상태가 발생할 가능성이 있는 경우)로 구분하고 불안전 상태일 때는 대기하고 안전 상태일 때만 자원을 빌려주는 Algorithm으로 할당한 자원 수 고정, Process 수 고정, 제한된 시간 안에 자원 반납 등의 많은 조건이 필요하다.
☞ 현실에서는 자원이 동적으로 왔다갔다해 현실적으로는 불가능한 Algorithm이다.

3.3. 교착 상태 탐지 및 복구

: 교착 상태가 발생한 것 같을 때 탐지하고 복구하는 방법으로 교착 상태가 자주 발생하는 System에서 일반적으로 사용하는 방법이다.

☞ 교착 상태 회피에 비해 Overhead가 적다.

• 교착 상태 탐지
  : 교착 상태 존재 여부 및 교착 상태에 연관된 Process와 자원을 알아내는 전략을 사용하며 교착 상태의 4가지 필요 조건 중 순환 대기 존재 여부에 초점을 맞춰 교착 상태를 탐지한다.
  ☞ 탐지 Algorithm도 회피 Algorithm과 마찬가지로 Overhead가 있으므로 얼마나 자주(주기적으로, 자원 즉시 할당 여부에 따라, CPU 이용률에 따라 등) 탐지 Algorithm을 호출하는지가 관건이다.
  e.g., 자원 할당 그래프 소거
  더보기

  자원 할당 그래프 소거 방식

  

• 교착 상태 복구
  : 순환 대기를 깨서 교착 상태로부터 회복하는 방식이다.
  e.g., 순환 대기가 깨질 때까지 Process 종료, 순환 대기에 포함된 Process 제어권 뺏고 Rollback
  ☞ 희생양이 될 Process는 남은 수행 시간, 자원 유형의 수 등 Systemp마다 다른 기준의 우선순위에 따라 결정된다.
      e.g., MySQL의 경우 Transaction Timeout시 교착상태이든 아니든 가장 작은 Transaction을 Rollback하며 Transaction의 크기는 삽입, 업데이트, 삭제된 행 수에 의해 결정된다.

3.4. 교착 상태 무시

: 교착 상태가 드물게 발생하는 System에서 일반적으로 사용하는 방법이다.

0. 용어 정리

• Race Condition(경쟁 조건)
  : 여러 Process/Thread가 동시에 같은 Data를 조작할 때 타이밍이나 접근 순서에 따라 결과가 달라질 수 있는 상황
• Synchronization(동기화)
  : 여러 Process/Thread를 동시에 실행해도 공유 Data의 일관성을 유지하는 것
• Critical Section(임계 영역)
  : 공유 Data의 일관성을 보장하기 위해 한 번에 하나의 Precess/Thread만 진입해 실행가능한 영역
• Mutual Exclusion(상호 배제)
  : 공유 Data의 일관성을 보장하기 위해 한 번에 하나의 Process/Thread만 진입해 실행할 수 있도록 하는 Algorithm

1. Mutual Exclusion을 보장할 수 있는 방법

: Lock을 사용한다.

// 실제 동작 Code가 아닌 개념 이해를 돕기위한 Code 입니다.

do{
	acquire lock // 여러 Process/Thread가 Lock을 획득하기 위해 경합
    	critical section // Lock을 획득한 단 하나의 Process/Thread만이 Critical Section에 들어가 실행
    release lock // Critical Section에서의 실행을 마치면 Critical Section을 빠져나오며 Lock 반환
    	reminder section
} while(TRUE)

Mutual Exclusion을 보장하는 상호 배제 기법으로는 Spin Lock, Mutex, Semaphore가 있다.

2. Spin Lock

: Lock을 획득할 수 있을 때까지 Lock 획득을 반복해서 시도하는 방식

☞ Lock을 획득하기 전까지 Lock이 다른 Process/Thread에 의해 선점되었는지 확인하는 것 자체가 CPU Cycle을 잡아먹는 일이기 때문에 CPU를 낭비한다.

Single Core, Multi Core에서의 Spin Lock

더보기

Single Core에서는 Spin Lock으로 Lock이 반환되기를 계속 기다리더라도 Lock을 획득하기 위해서는 이미 누군가 획득한 상태인 Lock을 반환해야하는데 이는 결국 Context Switching이 필요하다.
☞ Single Core에서의 Spin Lock은 이점이 없다.

Multi Core에서는 Spin Lock으로 Lock이 반환되기를 기다리다가 Thread 1이 Lock을 반환하자마자 Thread 2가 Lock을 획득하므로 Context Switching이 일어나지 않는다.

2.1. 동작 예제

// 실제 동작 Code가 아닌 개념 이해를 돕기 위한 Code입니다.

volatile in lock = 0; // global -> 여러 Thread가 동시에 Lock에 접근 가능

// 여러 Thread가 호출할 함수
void critical(){
	
    while(test_and_set(&lock) == 1); // 여러 Thread가 while loop를 통해 Lock을 획득하려 시도
    ... critical section // Lock 획득에 성공한 하나의 Thread가 Critical Section에 들어와 실행
    lock = 0 // Critical Setcion에서 수행 완료 후 Lock 반환
    
}

// 실제 TestAndSet()의 동작 원리를 간단히 구현한 함수
// 공유되는 Lock에 대해 Lock의 원래 저장값을 반환하고 Lock 값은 1로 변경
int test_and_set(int* lockPtr){
	
    int oldLock = *lockPtr; // 원래 가지고 있던 Lock 값 가져오기
    *lockPtr = 1; // Lock 값을 1로 변경
    
    return oldLock; // 원래 가지고 있던 Lock 값을 반환
}

2.2. 동작 과정

Thread 1이 먼저 수행된 후 Thread 2가 수행되는 경우

1. Thread 1의 test_and_set()의 반환값 = 0 (원래 Lock은 0으로 초기화 되어있었기 때문) 이므로 while loop 탈출해 Critical Section에서 작업을 수행한다.

    ☞ test_and_set()을 호출했으므로 Lock은 1로 변경된다.

2. Thread 2의 test_and_set()의 반환값 = 1 (1번 과정에서 Thread 1에 의해 Lock이 1로 변경되었기 때문) 이므로 while loop에 갇힌다.

    ☞ test_and_set()을 호출했으므로 Lock은 계속 1로 갱신된다.

3. Thread 1이 Critical Section에서 작업을 마치고 Lock을 반환한다.

    ☞ Lock이 0이 된다.

4. Thread 1이 Lock을 반환함과 동시에 Thread 2의 test_and_set() 반환값 = 0 (3번 과정에서 Thread 1에 의해 Lock이 0으로 변경되었기 때문) 이 되므로 while loop 탈출해 Critical Section에서 작업을 수행한다.

    ☞ test_and_set()을 실행했기 때문에 Lock은 1로 변경된다.

5. Thread 2가 Critical Section에서 작업을 마치고 Lock을 반환한다.

    ☞ Lock이 0이 된다.

∴ test_and_set()을 통해 Thread 1과 Thread 2가 Critical Section 안에서 동시에 작업을 수행할 수 없다. (= 상호 배제)

TestAndSet()

Atomic 명령어의 특징

3. Mutex

: Lock이 다른 Process/Thread에 의해 획득된 상태라면 Lock이 반환될 때까지 Queue에서 대기하는 방식

☞ CPU Cycle을 불필요하게 낭비하는 것을 최소화한다.

3.1. 동작 예제

// 실제 동작 Code가 아닌 개념 이해를 돕기 위한 Code입니다.
Class Mutex{
	int value = 1; // 이 값을 획득해야 Lock을 획득할 수 있다. (공유되는 Data)
    		       // value를 변경할 때 Critical Section 안에서 변경하지 않으면 Race Condition이 발생할 수 있다.
    int guard = 0; // Critical Section에 포함되어있는 value를 변경하기 위해 사용되는 변수
}

Mutex::lock(){
	while(test_and_set(&guard)); // value 값 변경 전 guard를 획득하기 위해 여러 Process/Thread가 경합
    
    // guard를 획득한 하나의 Process/Thread만 value 변경 Logic을 수행한다.
    if (value == 0){ // 누군가 value를 이미 획득한 상태라면
    	현재 Thread를 Queue에 넣는다; // 작업을 잠시 멈추고 쉬고 있을테니 Lock이 풀리면 깨워달라며 Queue에 들어간다.
        guard = 0; & go to sleep // Process/Thread를 Queue에 넣고 guard 변경(guard 반환)
    }
    else{ // value를 획득할 수 있으면
    	value = 0; // value 획득하고 value를 0으로 갱신(value 획득한 상태를 표시)한다.
        guard = 0; // value 변경 후 guard 0으로 갱신(guard 반환)
    }

Mute::unlock(){
	while(test_and_set(&guard)); // value 변경 전 여러 Process/Thread가 guard를 획득하기 위해 경합
    
    // guard를 획득한 하나의 Process/Thread만 value 변경 Logic을 수행한다.
    if (Queue에 하나라도 대기 중이라면){
    	그 중 하나를 깨운다;
    }
    else{ // 대기중인 Process/Thread가 하나도 없으면
    	value = 1; // value를 1로 갱신(value 반환)
    }
    guard = 0; // value 변경 혹은 Queue에서 Process/Thread 꺼낸 후 guard 0으로 갱신(guard 반환)
}

mutex -> lock(); // 여러 Process/Thread가 Lock을 획득하기 위해 경합
... critical section // Lock을 획득한 하나의 Process/Thread가 Critical Section에 들어가 작업 수행
mutex -> unlock(); // Critical Section에서 작업을 마친 후 Lock 반환

항상 Mutex가 Spin Lock보다 좋을까?

4. Semaphore

: Signal Mechanism을 가지는, 하나 이상의 Process/Thread가 Critical Section에 접근 가능하도록 하는 방법

4.1. 종류

• Binary Semaphore(이진 세마포어)
  : 한 번에 1개의 Process/Thread만 Critical Section에 접근할 수 있다.
  ☞ Mutual Exclusion을 보장한다.
• Counting Semaphore
  : 한 번에 value개의 Process/Thread만 Critical Section에 접근할 수 있다.

4.2. 동작 예제

// 실제 동작 Code가 아닌 개념 이해를 돕기 위한 Code입니다.
Class Semaphore{

    // 한 번에 value개의 Process/Thread가 Critical Section에 접근할 수 있다.
    int value = 1; // value를 획득해야 Lock을 획득할 수 있다. (공유되는 Data)
    			   // value를 변경할 때 Critical Section 안에서 변경하지 않으면 Race Condition이 발생할 수 있다.
    int guard = 0; // Critical Section에 포함되어있는 value를 변경하기 위해 사용되는 변수
}

Semaphore::wait(){
	while(test_and_set(&guard)); // value 변경 전 guard를 획득하기 위해 여러 Process/Thread가 경합
    
    // guard를 취득한 하나의 Process/Thread만 value 변경 Logic을 수행한다.
    if (value == 0){ // 이미 누군가 value를 획득한 상태라면
    	현재 Process/Thread를 Queue에 넣는다; // Process/Thread가 일을 잠시 멈추고 쉬고 있을테니 Lock이 풀리면 깨워달라며 Queue에 들어간다.
        
        guard = 0; & go to sleep; // Process/Thread를 Queue에 넣은 후 guard 변경(guard 반환)
    }
    else{ // value를 획득할 수 있다면
    	value -= 1; // value 획득한 후 value를 1 감소(value 획득한 상태를 표시)
        guard = 0; // value 변경 후 guard 0으로 갱신(guard 반환)
    }
}

Semaphore::signal(){
	while(test_and_set(&guard)); // value 변경 전 guard 획득하기 위해 여러 Process/Thread가 경합
    
    // guard를 획득한 하나의 Process/Thread만 value 변경 Logic을 수행
    if (Queue 안에 하나라도 대기 중이라면){
    	그 중에 하나를 깨워 준비시킨다;
    }
    else{ // 대기중인 Process/Thread가 하나도 없으면
    	value += 1; // value 1 증가(value 반환)
    }
    guard = 0; // value 변경 혹은 Queue에서 Process/Thread 꺼낸 후 guard 0으로 갱신(guard 반환)
}

Semaphore -> wait(); // 여러 Process/Thread가 Lock을 획득하기 위해 경합
... critical section // Lock을 획득한 하나의 Process/Thread가 Critical Section에 들어가 작업 수행
semaphore -> signal(); // Critical Section에서 작업을 마친 후 Lock 반환

Semaphore는 Process/Thread의 동작 순서를 정할 때도 사용할 수 있다.

더보기

Multi Core 환경에서 P1과 P2가 각각 Core를 할당받아 동시에 시작되는 경우

P1: task 1을 수행

P2: task 2를 수행한 후 task 3을 수행

 

Class Semaphore{
    int value = 0;
    int guard = 0;
}

P1이 task 1, P2가 task 2 수행이 동시에 진행되는 경우 task 1이 먼저 끝날지, task 2가 먼저 끝날지는 알 수 없지만 task 3은 task 1이 끝난 뒤에 수행된다는 것은 명확하다.

task 1이 먼저 끝나는 경우

1. P1이 task 1을 끝내고 signal() 호출함으로써 value = 1로 갱신

2. P2가 task 2를 끝내고 wait() 호출하면 value를 1 차감해 value는 0이 되고 wait() 반환되어 task 3 수행

 

task 2가 먼저 끝나는 경우

1. P2가 task 2를 끝내고 wait() 호출하지만 아직 value는 0이므로 자신을 Queue에 넣고 대기

2. P1이 task 1을 끝내고 signal() 호출하면 Queue에 들어있던 P2를 깨움

3. P2가 깨어나 task 3 수행

 

∴ signal()과 wait()가 같은 Process/Thread 안에서 실행될 필요가 없다.

5. Mutex와 Binary Semaphore의 차이점

Priority Inheritance

[참고]

https://youtu.be/gTkvX2Awj6g

1. 프로그램(Program)

: 어떤 작업을 위해 실행할 수 있는 파일로 일반적으로 Application(End User가 사용할 수 있는 Software)이라고 많이 표현된다.

☞ Process를 이용해 실행시킨다.

2. 프로세스(Process)

: 컴퓨터에서 실행되고 있는 컴퓨터 프로그램으로 하나의 실행 단위가 된다.

☞ OS(Operating System)에서 실행 가능한 File을 Memory에 올리면 해당 File을 Process로 실행한다.

☞ 하나의 Application을 실행하면 최소 1개의 Process가 뜬다.

2.1. 구성 요소

• Register : 명령이나 주소를 갖고 있는 CPU의 한 부분
• Counter : Program 안에서 현재 어느 위치를 실행시키고 있는지 가리키는 용도로 사용
• Stack : Function Call을 했을 때 Call Stack 등이 쌓이는 곳으로 지역 변수, 매개 변수, 반환값 등 일시적인 Data가 저장됨
• Heap : Process가 가지고 있는 Memory 중 위쪽에 할당되어 있는 부분으로 동적으로 할당 가능한 Memory
  ☞ Memory Size에 제한이 없다.
• Data : Static 변수, Global 변수 저장
• Code : 실행 명령들을 포함하는 Code

2.2. 특징

• 각각 독립된 메모리 영역(Code, Data, Stack, Heap의 구조)을 할당받는다.
• 기본적으로 Process 당 최소 1개의 Thread를 가지고 있다.
• 각 Process는 별도의 주소 공간에서 실행되며, 한 프로세스는 다른 프로세스의 변수나 자료 구조에 접근할 수 없다.
• 한 Process가 다른 Process의 자원에 접근하려면 프로세스 간의 통신(IPC, Inter Process Communication)을 사용해야 한다.
  e.g., 파이프, 파일, 소켓 등을 이용한 통신 방법 이용

3. 스레드(Thread)

: Process 내에서 실행되는 여러 흐름의 단위

☞ Process는 여러 개의 Thread를 가질 수 있으며 Thread 간 자원을 공유하면서 동시에(Concurrency) 수행된다.

동시성(Concurrency) vs 병렬(Parallelism)

- 동시성(Concurrency) : 보이기에는 동시에 수행되는 것처럼 보이지만 실제로는 시간을 매우 잘게 쪼개서 CPU의 자원을 나눠서 쓰는 것 (진정한 의미의 병렬은 아님)
Multi-Threading은 Concurrency에 가깝다.

- 병렬(Parallelism) : 실제로 동시에 수행되는 것
Multi-Processing은 Parallelism에 가깝다.

3.1. 특징

• Thread는 Process 내에서 각각 Stack 영역만 따로 할당받고 Code, Data, Heap 영역은 공유한다.
• 한 Thread가 Process 자원을 변경하면, 다른 이웃 스레드(Sibling Thread)도 그 변경 결과를 즉시 볼 수 있다.

4. Thread vs Process

5. 멀티 태스킹(Multi Tasking)

: 한번에 여러 개의 Application을 실행시키는 것

☞ Multi-Processing과 Multi-Threading 기술이 가능해졌다고 설명할 수 있다.

Multi-Processing과 Multi-Threading

CPU의 최대 활용을 위해 프로그램의 둘 이상의 부분을 동시에 실행하는 기술
e.g., 하나의 Program 안에서 2개의 부분 동시 실행, 2개의 Program 동시 실행 등

5. 멀티 프로세스 (Multi Process)

: 하나의 응용프로그램을 여러 개의 프로세스로 구성해 각 프로세스가 하나의 작업(Task)을 처리하도록 하는 것

☞ Single Core에서 Multi Process 불가능

5.1. 장점 vs 단점

Context Switching (컨텍스트 전환, 작업 전환, 프로세스 전환)
: 기본적으로 CPU의 자원을 Process/Thread에서 다른 Process/Thread로 전환하는 것으로 Context 전환을 통해 여러 Process가 단일 CPU를 공유할 수 있다.
e.g., Process ↔ Process, Thread ↔ Thread, Process ↔ Thread
☞ Multi Tasking 운영체제의 주요 기능이다.

더보기

과정 : 프로세스 제어 블록(PCB, Process Control Block)에서 CPU의 컨텍스트 상태를 복원하고 저장해 나중에 같은 시점에서 Process 실행을 재개
☞ Context 전환에 따른 비용 발생

e.g., Thread ↔ Thread
1. Thread1에서 하고 있는 작업을 PCB에 저장

2. Thread2에서 PCB로부터 기존 작업을 Load해 이어서 실행

5.3. Code

# Multi Processing
import multiprocessing
import threading
import os
import time

def hello(s):
  # pid : Process ID
  print('Function start!', s, 'pid:', os.getpid(), 'thread id:', threading.get_ident())
  time.sleep(1)

# Process 생성
t1 = multiprocessing.Process(target = hello, args = ['Hello World'])
t2 = multiprocessing.Process(target = hello, args = ['Hello Jjyoung'])

t1.start()
t2.start()

# 각 Process가 끝날 때까지 기다림
t1.join()
t2.join()

# 출력을 보면 pid가 다름
Function start! Hello World pid: 1890 thread id: 139996320056768
Function start! Hello Jjyoung pid: 1891 thread id: 139996320056768

6. Multi Thread

: Process 하나에 Thread 여러 개가 들어있는 것으로 하나의 Core를 여러개의 Thread가 동시에(Concurrent하게) 접근해 Context Switching이 일어난다.
☞ Single Core에서 Multi Thread 가능

6.1. 특징

• Stack 영역은 독립적으로 할당받지만 Heap, Code 영역은 공유하고 있다.
• Windows, Linux 등 많은 운영체제들이 Multi-Porcessing을 지원하고 있지만 Multi-Threading을 기본으로 하고있다.
• Web Server는 대표적인 Multi-Thread 응용 프로그램이다.

6.2. 장점 vs 단점

동기화 문제
: Thread 간의 자원 공유는 전역 변수(Data Segment)를 이용하므로 함께 사용할 때 충돌이 발생할 수 있다.

6.3. Code

# Multi Threading
import threading
import os
import time

def hello(s):
  # pid : Process ID
  print('Function start!', s, 'pid:', os.getpid(), 'thread id:', threading.get_ident())
  time.sleep(1)

# Thread 생성
t1 = threading.Thread(target = hello, args = ['Hello World'])
t2 = threading.Thread(target = hello, args = ['Hello Jjyoung'])

t1.start()
t2.start()

# 각 Thread가 끝날 때까지 기다림
t1.join()
t2.join()

# 출력을 보면 pid는 같지만 thread id는 다름
Function start! Hello World pid: 1882 thread id: 139995620914752
Function start! Hello Jjyoung pid: 1882 thread id: 139995612522048

[참고]

https://youtu.be/RrfASw-jfZ4

https://youtu.be/dzfij2nZbRw

https://gmlwjd9405.github.io/2018/09/14/process-vs-thread.html