Table of Contents

• 프로세스
  • 프로세스의 네 가지 상태
  • 프로세스의 구조
  • 프로세스의 생성과 복사
  • 프로세스의 전환
  • 프로세스의 계층 구조
• 스레드
  • 스택을 스레드마다 독립적으로 할당하는 이유
  • PC Register를 스레드마다 독립적으로 할당하는 이유
• CPU 스케줄러
  • FCFS(First Come First Served)
  • SJF(Shortest - Job - First)
  • SRTF(Shortest Remaining Time First)
  • Priority Scheduling
  • Round Robin
• 멀티 프로세싱, 멀티 스레딩
  • 멀티 태스킹
  • 멀티 프로세싱
  • 멀티 스레딩
• 스레드 동기화
  • Thread-safe
  • 뮤텍스와 세마포어
• 임계구역(Critical Section)
  • 임계구역 해결 조건
  • 임계구역 해결 방법
• 교착 상태(Deadlock)
  • 자원 할당 그래프
  • 교착 상태 필요조건
  • 교착 상태 해결방법
    • 교착 상태 예방과 회피
    • 교착 상태 검출과 회복
• 참고

프로세스

• 프로세스란 실행중인 프로그램
  • 프로그램은 하드디스크 같은 저장장치에 저장
  • 프로그램을 실행하면 해당 코드가 메모리에 올라와서 작업이 진행된다
• 스케줄링의 대상이 되는 작업(task)과 같은 의미로 쓰인다
• 프로세스 내부에는 최소 하나의 스레드(thread)를 가지고있는데, 실제로는 스레드(thread)단위로 스케줄링을 한다
• 하드디스크에 있는 프로그램을 실행하면, 실행을 위해서 메모리 할당이 이루어지고, 할당된 메모리 공간으로 바이너리 코드가 올라가게 된다. 이 순간부터 프로세스라 불린다.

프로그램에서 프로세스로의 전환

프로세스는 컴퓨터 시스템의 작업 단위로 태스크라고도 불린다.

시분할 방식 시스템에서 프로그램이 프로세스로 전환될 때 어떤 일이 일어나는지 살펴보자

우선 운영체제는 프로그램을 메모리의 적당한 위치로 가져온다. 그와 동시에 주문서에 해당하는 작업 지시서(프로세스 제어블록)를 만든다. 프로세스 제어블록에는 프로세스를 처리하는 데 필요한 다양한 정보가 들어 있다. 프로그램이 프로세스로 전환되려면 운영체제로부터 프로세스 제어블록을 받아야 한다. (프로세스 제어블록은 운영체제가 해당 프로세스를 위해 관리하는 데이터 구조이기 때문에 운영체제 영역에 만들어진다) 프로세스가 종료되면 메모리에서 삭제되고, 프로세스 제어블록도 폐기된다.

프로세스 제어블록에 포함된 대표적인 정보

- 프로세스 식별자(Process ID, PID) : 프로세스 식별번호
- 프로세스 상태 : new, ready, running, waiting, terminated 등의 상태를 저장
- 프로그램 카운터 : 프로세스가 다음에 실행할 명령어의 주소
- CPU 레지스터
- CPU 스케쥴링 정보 : 프로세스의 우선순위, 스케줄 큐에 대한 포인터 등
- 메모리 관리 정보 : 페이지 테이블 또는 세그먼트 테이블 등과 같은 정보를 포함
- 입출력 상태 정보 : 프로세스에 할당된 입출력 장치들과 열린 파일 목록
- 어카운팅 정보 : 사용된 CPU 시간, 시간제한, 계정번호 등

프로세스의 네 가지 상태

• 실행되기 전의 프로세스는 준비상태에 있다
• 자원을 할당받은 프로세스를 실행상태에 있다
• 프로세스는 실행 도중 데이터를 필요로 할 수 있다
  • 입출력 장치에게 데이터를 요청해야 한다
  • CPU는 해당 프로세스의 실행을 멈추고, 다른 프로세스를 처리해야 한다
  • 그동안 해당 프로세스는 대기상태에 들어간다
  • 입출력 장치로부터 데이터를 받아오면 다시 준비상태로 들어간다
• 시간 내에 처리하지 못한 프로세스는 다시 준비상태로 돌아간다
• 시간 내에 처리된 프로세스는 종료상태가 된다

프로세스의 상태

• 생성 상태
  • 프로세스가 메모리에 올라와 실행 준비를 완료한 상태
  • 프로세스를 관리하는데 필요한 프로세스 제어블록이 생성됨
• 준비 상태
  • 생성된 프로세스가 CPU를 얻을 때까지 기다리는 상태
  • 디스패치: CPU 스케줄러가 준비 상태에 있는 여러 프로세스 중 다음에 실행할 프로세스를 선정하는 일
• 실행 상태
  • 준비 상태에 있던 프로세스가 CPU를 얻어 실제 작업을 수행하는 상태
  • 프로세스 제어블록을 CPU에 전달
  • 주어진 시간내 작업이 끝나지 않은 경우 다시 준비 상태로 돌아감(클록이 인터럽트를 사용해 CPU에 알림)
  • 작업이 끝날때까지 준비 상태와 실행 상태를 왔다 갔다함
• 완료 상태
  • 실행 상태의 프로세스가 시간내 작업을 마치면 완료 상태로 진입
  • 프로세스 제어블록이 사라진 상태
• 대기 상태
  • 프로세스가 입출력을 요청하면 입출력 관리자가 입출력을 완료하기 전까지 프로세스를 대기 상태로 옮겨둔다
  • 입출력 관리자가 입출력을 완료하면 프로세스를 대기 상태에서 준비 상태로 옮긴다

컨텍스트 스위칭

컨텍스트 스위칭(context switching)은 CPU를 차지하던 프로세스가 나가고 새로운 프로세스를 받아들이는 작업을 말한다. 이 때 두 프로세스 제어블록의 내용이 변경된다. 실행 상태에서 나가는 프로세스 제어블록에는 CPU에 있던 지금까지의 작업 내용을 저장하고, 반대로 실행 상태로 들어오는 프로세스 제어블록의 내용으로 CPU를 다시 세팅한다. 이와 같이 두 프로세스의 프로세스 제어블록을 교환하는 작업을 컨텍스트 스위칭이라 한다.

컨텍스트 스위칭은 인터럽트가 걸렸을 때 발생한다.

• 타임아웃 인터럽트: 프로세스가 할당받은 시간을 초과한 경우
• Out-Of-Memory 인터럽트: 프로세스가 할당받은 메모리를 초과한 경우

프로세스의 구조

• 코드 영역
  • 프로그램의 코드가 기술된 곳으로 텍스트 영역이라고도 함
  • 자기 자신을 수정하는 프로그램은 존재하지 않기 때문에, 코드는 읽기 전용으로 처리
• 데이터 영역
  • 코드가 실행되면서 사용되는 변수나 파일 등의 각종 데이터를 모아놓는 곳
  • 변수는 기본적으로 읽기와 쓰기가 가능
• 스택 영역
  • 프로세스를 실행하기 위해 부수적으로 필요한 데이터를 모아놓은 곳
  • 예를들어, 함수가 호출되면 함수를 수행하고 마치면 다시 되돌아올 위치를 이 영역에 저장
  • 스택 영역은 운영체제가 사용자의 프로세스를 작동하기 위해 유지하는 영역이므로 사용자에게는 보이지 않음
• 힙 영역
  • 동적으로 할당되는 데이터들을 위해 존재하는 공간이다. ex) malloc

위의 특징 외에도 코드 영역과 데이터 영역은 선언할 때 그 크기가 결정되는 정적 영역이지만,
스택 영역과 힙 영역은 프로세스가 실행되는 동안 크기가 늘어났다 줄어들기도 하는 동적 영역이다

원칙적으로 서로 다른 프로세스 간의 메모리 공간 접근은 허용되지 않는다.
만약 프로세스 간 서로 다른 자원에 접근하려면 프로세스 간의 통신을 해야한다.

프로세스의 생성과 복사

프로세스는 프로그램을 실행할 때 새로 생성된다. 사용자가 프로그램을 실행하면 운영체제는 프로그램을 메모리에 가져와 코드 영역에 넣고 프로세스 제어블록을 생성한다. 그리고 메모리에 데이터 영역과 스택 영역을 확보한 후 프로세스를 실행한다.

프로세스를 새로 생성하는 방법뿐만 아니라 실행 중인 프로세스로부터 새로운 프로세스를 복사하는 방법도 있다.

fork()

커널이 제공하는 fork() 시스템 호출은 실행 중인 프로세스로부터 새로운 프로세스를 복사하는 함수이다. 이 함수는 워드 프로그램, 브라우저 등에서 프로그램을 하나 더 실행할 때 전형적으로 호출된다. 이렇게 프로세스를 복사하게 되면 기존의 프로세스는 부모 프로세스가 되고, 새로 생긴 프로세스는 자식 프로세스가 된다.

프로세스의 전환

exec()

exec() 시스템 호출을 사용하면 복사된 프로세스를 새로운 프로세스로 전환할 수 있다. 이 함수를 사용하는 목적은 프로세스의 구조체를 재활용하기 위함이다.

새로운 프로세스를 만들려면 제어블록을 만들고 메모리의 자리를 확보하는 과정이 필요하다. 또한 프로세스를 종료하고 사용한 메모리를 청소(garbage collection)하기 위해 상위 프로세스와 부모-자식 관계를 만들어야 한다.

exec()를 사용하면 이미 만들어진 제어블록, 메모리 영역, 부모-자식 관계를 그대로 사용할 수 있어 편리하다. 새로운 코드 영역만 가져오면 되기 때문에 운영체제의 작업이 수월하다.

exec() 함수의 동작과정은 간단하다. 호출을 하면 코드 영역에 있는 기존의 내용을 지우고 새로운 코드로 바꾼다. 또한 데이터 영역이 새로운 변수로 채워지고 스택 영역이 리셋된다. 제어블록의 내용 중 프로세스 구분자, 부모 프로세스 구분자, 메모리 관련 사항 등은 변하지 않지만 프로그램 카운터 레지스터 값을 비롯한 각종 레지스터와 사용한 파일 정보가 모두 리셋된다.

프로세스의 계층 구조

위에서 배운 프로세스의 복사와 전환은 프로세스의 계층 구조를 이해하는데 핵심 열쇠가 된다.

fork()와 exec()를 사용하면 프로세스들을 자동적으로 부모-자식 프로세스의 계층 구조로 만들어준다. 프로세스를 계층 구조로 만들면 프로세스 간의 책임 관계가 분명해져서 시스템을 관리하기가 수월하다. 프로세스가 작업을 마쳐서 그 프로세스가 사용하던 자원을 회수(garbage collection)할 때 특히 편리하다. 만약 모든 프로세스가 독립적으로 만들어지면 프로세스가 종료될 때마다 운영체제가 직접 자원을 회수해야 하기 때문에 작업이 복잡해질 것이다. 그러나 모든 프로세스를 부모-자식 관계로 만들면 자식 프로세스가 작업을 마쳤을 때 사용하던 자원을 부모 프로세스가 회수하면 된다.

고아 프로세스

부모 프로세스는 자원을 회수하기 위해 자식 프로세스가 끝날 때까지 기다려야 된다. 그런데 부모 프로세스가 먼저 종료되거나 자식 프로세스가 비정상적으로 종료되어 부모 프로세스에 연락이 안되는 경우도 있다. 이렇게 부모 프로세스가 먼저 종료되고 비정상적으로 남아있는 자식 프로세스를 고아 프로세스 또는 좀비 프로세스라고 한다. 좀비 프로세스는 자식 프로세스를 종료했음에도 부모가 뒤처리를 하지 않을 때 발생한다. 이런 좀비 프로세스가 많아지면 자원이 낭비되게 된다. 따라서 운영체제는 반환되지 못한 자원을 주기적으로 회수해야 한다.

스레드

스레드는 프로세스의 실행 단위라고 할 수 있다. 한 프로세스 내에서 동작되는 여러 실행 흐름으로 프로세스 내의 주소 공간이나 자원을 공유할 수 있다. 스레드는 스레드 ID, 프로그램 카운터, 레지스터 집합, 그리고 스택으로 구성된다. 같은 프로세스에 속한 다른 스레드와 코드, 데이터 섹션, 그리고 열린 파일이나 신호와 같은 운영체제 자원들을 공유한다. 하나의 프로세스를 다수의 실행 단위로 구분하여 자원을 공유하고 자원의 생성과 관리의 중복성을 최소화하여 수행 능력을 향상시키는 것을 멀티스레딩이라고 한다. 이 경우 각각의 스레드는 독립적인 작업을 수행해야 하기 때문에 각자의 스택과 PC 레지스터 값을 갖고 있다.

스택을 스레드마다 독립적으로 할당하는 이유

스택은 함수 호출 시 전달되는 인자, 되돌아갈 주소값 및 함수 내에서 선언하는 변수 등을 저장하기 위해 사용되는 메모리 공간이므로 스택 메모리 공간이 독립적이라는 것은 독립적인 함수 호출이 가능하다는 것이고 이는 독립적인 실행 흐름이 추가되는 것이다. 따라서 스레드의 정의에 따라 독립적인 실행 흐름을 추가하기 위한 최소 조건으로 독립된 스택을 할당한다.

PC Register를 스레드마다 독립적으로 할당하는 이유

PC 값은 스레드가 명령어의 어디까지 수행하였는지를 나타낸다. 스레드는 CPU 를 할당받았다가 스케줄러에 의해 다시 선점당한다. 그렇기 때문에 명령어가 연속적으로 수행되지 못하고 어느 부분까지 수행했는지 기억할 필요가 있다. 따라서 PC 레지스터를 독립적으로 할당한다.

CPU 스케줄러

스케줄링 대상은 Ready Queue 에 있는 프로세스들이다.

FCFS(First Come First Served)

• 특징
  • 먼저 온 고객을 먼저 서비스해주는 방식, 즉 먼저 온 순서대로 처리.
  • 비선점형(Non-Preemptive) 스케줄링
    일단 CPU 를 잡으면 CPU burst 가 완료될 때까지 CPU 를 반환하지 않는다. 할당되었던 CPU 가 반환될 때만 스케줄링이 이루어진다.
• 문제점
  • convoy effect
    소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.

SJF(Shortest - Job - First)

• 특징
  • 다른 프로세스가 먼저 도착했어도 CPU burst time 이 짧은 프로세스에게 선 할당
  • 비선점형(Non-Preemptive) 스케줄링

-문제점

• starvation
  효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안되는 것이다. 이 스케줄링은 극단적으로 CPU 사용이 짧은 job 을 선호한다. 그래서 사용 시간이 긴 프로세스는 거의 영원히 CPU 를 할당받을 수 없다.

SRTF(Shortest Remaining Time First)

• 특징
  • 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
  • 선점형 (Preemptive) 스케줄링
    현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.
• 문제점
  • starvation
  • 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없다.

Priority Scheduling

• 특징
  • 우선순위가 가장 높은 프로세스에게 CPU 를 할당하는 스케줄링이다. 우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.
  • 선점형 스케줄링(Preemptive) 방식
    더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.
  • 비선점형 스케줄링(Non-Preemptive) 방식
    더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.
• 문제점
  • starvation
  • 무기한 봉쇄(Indefinite blocking)
    실행 준비는 되어있으나 CPU 를 사용못하는 프로세스를 CPU 가 무기한 대기하는 상태
• 해결책
  • aging
    아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자.

Round Robin

• 특징
  • 현대적인 CPU 스케줄링
  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다.
  • 할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.
  • RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
  • RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.
• 장점
  • Response time이 빨라진다.
    n 개의 프로세스가 ready queue 에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
  • 프로세스가 기다리는 시간이 CPU 를 사용할 만큼 증가한다.
    공정한 스케줄링이라고 할 수 있다.

멀티 프로세싱, 멀티 스레딩

197년대 까지는 프로세서는 하나의 프로세스를 실행해서 종료하고, 또 하나의 프로세스를 실행하고 종료하는 방식으로 동작했다. 다시 말해 멀티 태스킹을 할 수 없었다. 그러다 80년대에 들어서 운영체제(OS)에서 멀티 태스킹을 지원하기 시작했다. 멀티 태스킹은 OS의 스케줄링을 이용해 여러 프로세스를 시분할로 함께 실행시키는 것이다. 예를 들어 10개의 프로그램을 실행했을 때, CPU는 각 프로세스에 작은 단위의 시간을 할당해 마치 여러 프로세스가 동시에 실행되는 듯하게 만드는 것이다.

그러나 시대가 계속 발전함에 따라 우리는 프로세스 하나의 더 높은 성능을 기대하기 시작했다. 그래서 인텔과 같이 CPU를 만드는 회사에서는 CPU 한개에 여러 개의 코어를 탑재한 멀티 코어 칩을 만들어 냈다. 우리는 이제 정말로 동시에 여러 프로세스를 실행할 수 있게 되었다. 이는 코어 하나에 온전히 하나의 프로세스만 할당함으로써 프로세스의 성능을 높게 유지할 수 있었다.

그러나 소프트웨어 개발자들은 여기서 그치지 않고, 하나의 프로세스를 여러 프로세서가 협력해 처리하는 병렬 처리를 통해 프로세스 하나의 성능을 극대화 시키는 방법을 고민하고 있었다. 그렇게 등장한 것이 바로 멀티 프로세싱이다. 멀티 프로세싱은 하나의 프로세스를 여러 프로세서가 병렬 처리하는 것을 말한다. 하나의 프로세스를 여러 프로세서가 나눠서 처리하기 위해 프로세스를 나누는 작업은 프로그래머의 몫이다.

마지막으로 작업을 프로세서에게 나눠주는 단위를 프로세스가 아니라 스레드 단위로 할 수도 있다. 이를 멀티 스레딩이라 한다. 스레드는 스택 영역만 분리되고 나머지 영역은 공유한다. 그리고 스레드는 하나의 프로세서에 최대 2개의 스레드를 할당할 수 있다. (하지만 코어가 스레드 2개를 병렬처리하는 것은 아니고 컨텍스트 스위칭을 통해 번갈아가며 처리한다)

하나의 프로세스를 처리하기 위해 2개 이상의 프로세서를 사용하는 것을 병렬 컴퓨팅이라 한다.

하나의 프로세서가 여러 개의 프로세스 또는 스레드를 처리하도록 하는 것을 동시성 프로그래밍이라 한다.

지금까지 멀티 태스킹, 멀티 프로세싱, 멀티 스레딩에 관한 개념이 등장하게 된 배경에 대해 설명했다.

이제 각각의 특징과 장단점에 관해 조금 더 얘기해보자.

• 프로세스
  • 운영체제로부터 자원을 할당받는 작업의 단위
  • 프로그램이 인스턴스화 되어 메모리에 올라온 상태
• 스레드
  • 프로세스가 할당받은 자원을 이용하는 실행의 단위
  • 스레드는 프로세스 내에서 각각 Stack만 따로 할당받고 Code, Data, Heap 영역은 공유

멀티 태스킹

멀티 태스킹은 task를 OS의 스케쥴링에 의해 task를 번갈아가며 수행하는 것을 의미한다. 여러개의 task를 자주 번갈아가며 수행하다보니 사용자는 동시에 여러 task가 수행되고 있다고 느끼게 된다. 현대 컴퓨터도 OS의 스케줄링을 이용해 시분할 방식으로 멀티 태스킹을 지원하고 있다.

멀티 프로세싱

멀티 프로세싱은 다수의 프로세서가 서로 협력적으로 일을 처리하는 것을 의미한다. 프로세스 간 통신을 하기 위해서는 IPC를 통해야 한다.

• 장점
  • 독립된 구조로 안전성이 높은 장점이 있다.
  • 프로세스 중 하나에 문제가 생겨도 다른 프로세스에 영향을 주지 않아, 작업속도가 느려지는 손해정도는 생기지만 정지되거나 하는 문제는 발생하지 않는다.
• 단점
  • 메모리 사용량이 많다
  • 독립된 메모리 영역이기 때문에 작업량이 많을수록( Context Switching이 자주 일어나서 주소 공간의 공유가 잦을 경우) 오버헤드가 발생하여 성능저하가 발생 할 수 있다.
  • Context Switching 과정에서 캐시 메모리 초기화 등 무거운 작업이 진행되고 시간이 소모되는 등 오버헤드가 발생한다.

멀티 스레딩

멀티 스레딩은 하나의 프로세스를 스레드 단위로 프로세서에게 할당해 병렬 처리하는 것을 의미하며, 여러 개의 스레드는 서로 자원을 공유할 수 있다.

• 장점
  • 멀티 스레딩의 모든 이점은 결국 메모리 영역 공유라는 특징에서 비롯된다
  • 스택 영역을 제외한 나머지 영역을 공유하기 때문에 자원의 효율성이 증가
  • 힙 영역을 이용해 스레드간 데이터를 주고 받을 수 있기 때문에 통신 비용 감소
  • Context Switching 할 때 스택 영역만 처리하면 되기 때문에 빠른 응답 시간 및 처리 비용 감소
    • (캐시 메모리 초기화할 필요 없음)
• 단점
  • 멀티 스레딩의 단점도 결국 메모리 영역 공유라는 특징에서 비롯된다
  • 모든 스레드가 자원을 공유하기 때문에 한 스레드에 문제가 생기면 전체 프로세스에 영향을 미친다.
  • 자원을 공유하기에 임계 구역에서 동기화에 문제가 발생할 수 있다. (병목현상, 데드락 등)
  • (임계 구역: 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원)
  • (동기화를 위해 작업 처리 순서와 공유 자원에 대한 접근을 컨트롤해야함 -> 뮤텍스, 세마포어)
  • (이로 인해 과도한 락이 발생하고 오히려 병목현상이 발생해 결과적으로 성능이 저하될 가능성이 높다)

스레드 동기화

• 같은 프로세스내의 스레드는 서로 자원을 공유함
• 임계 구역에 여러 스레드가 동시에 접근하면 동기화가 지켜지지 않을 수 있음

Thread-safe

• Thread-safe란?
  • 직역하면 스레드 안전.
  • 멀티스레드 환경에서 여러 스레드가 동시에 하나의 객체 및 변수(공유 자원)에 접근할 때, 의도한 대로 동작하는 것을 말한다.
  • 이러한 상황을 “Thead-safe하다” 라고 표현한다.
• Thread-safe하게 구현하기
  • Thread-safe하기 위해서는 공유 자원에 접근하는 임계영역(critical section)을 동기화 기법으로 제어해줘야 한다.
    • 이를 ‘상호배제’라고 한다.
  • 동기화 기법으로는 Mutex나 Semaphore 등이 있다.
• Reentrant
  • Reentrant는 재진입성이라는 의미로, 여러 스레드가 동시에 접근해도 언제나 같은 실행 결과를 보장한다는 의미이다.
  • 이를 만족하기 위해서 해당 서브루틴에서는 공유자원을 사용하지 않으면 된다.
    • 예를들어 정적(전역) 변수를 사용하거나 반환하면 안 되고 호출 시 제공된 매개변수만으로 동작해야한다.
  • 따라서, Reentrant하다면 Thread-safe하지만 그 역은 성립하지 않는다.

뮤텍스와 세마포어

• 뮤텍스(Mutex)
  • 공유된 자원의 데이터를 여러 스레드가 접근하는 것을 막는 것
  • 상호배제라고도 하며, Critical Section을 가진 스레드의 Running time이 서로 겹치지 않도록 각각 단독으로 실행하게 하는 기술이다.
  • 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 synchronized 또는 lock을 사용한다.
    • 즉, 뮤텍스 객체를 두 스레드가 동시에 사용할 수 없다.
• 세마포어(Semaphore)
  • 공유된 자원의 데이터를 여러 프로세스가 접근하는 것을 막는 것
  • 리소스 상태를 나타내는 간단한 카운터로 생각할 수 있다.
    • 운영체제 또는 커널의 한 지정된 저장장치 내의 값이다.
    • 일반적으로 비교적 긴 시간을 확보하는 리소스에 대해 이용한다.
    • 유닉스 시스템 프로그래밍에서 세마포어는 운영체제의 리소스를 경쟁적으로 사용하는 다중 프로세스에서 행동을 조정하거나 또는 동기화 시키는 기술이다.
  • 공유 리소스에 접근할 수 있는 프로세스의 최대 허용치만큼 동시에 사용자가 접근하여 사용할 수 있다.
  • 각 프로세스는 세마포어 값을 확인하고 변경할 수 있다.
    • 1) 사용 중이지 않는 자원의 경우 그 프로세스가 즉시 자원을 사용할 수 있다.
    • 2) 이미 다른 프로세스에 의해 사용 중이라는 사실을 알게 되면 재시도하기 전에 일정 시간을 기다려야 한다.
    • 세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경함으로써 다른 세마포어 사용자들이 기다리도록 해야한다.
  • 세마포어는 이진수 (0 또는 1)를 사용(Mutex)하거나, 또는 추가적인 값을 가질 수도 있다.
• 차이
  1. 가장 큰 차이점은 관리하는 동기화 대상의 개수
     • Mutex는 동기화 대상이 오직 하나뿐일 때, Semaphore는 동기화 대상이 하나 이상일 때 사용한다.
  2. Semaphore는 Mutex가 될 수 있지만 Mutex는 Semaphore가 될 수 없다.
     • Mutex는 상태가 0, 1 두 개 뿐인 binary Semaphore
  3. Semaphore는 소유할 수 없는 반면, Mutex는 소유가 가능하며 소유주가 이에 대한 책임을 가진다.
     • Mutex 의 경우 상태가 두개 뿐인 lock 이므로 lock 을 가질 수 있다.
  4. Mutex의 경우 Mutex를 소유하고 있는 스레드가 이 Mutex를 해제할 수 있다. 하지만 Semaphore의 경우 이러한 Semaphore를 소유하지 않는 스레드가 Semaphore를 해제할 수 있다.
  5. Semaphore는 시스템 범위에 걸쳐있고 파일시스템상의 파일 형태로 존재하는 반면 Mutex는 프로세스 범위를 가지며 프로세스가 종료될 때 자동으로 Clean up 된다.

임계구역(Critical Section)

• 여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분
• 공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에, 한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야 한다.
• 임계 구역을 여러 프로세스가 함께 사용할 수 있도록 설계한 경우, 임계 구역 문제가 발생할 수 있다

임계구역 해결 조건

• 상호 배제: 한 프로세스가 임계구역에 들어가면 다른 프로세스는 들어갈 수 없다
• 한정 대기: 어떤 프로세스도 무한 대기하지 않아야 한다 (진입 시도 회수를 제한한다)
• 진행의 융통성: 한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다

임계구역 해결 방법

• 세마포어
  • 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법
  • 소프트웨어상에서 Critical Section 문제를 해결하기 위한 동기화 도구
  • 임계구역에 진입하기 전에 스위치를 사용 중으로 놓고 임계구역으로 들어가는 방법
  • 카운팅 세마포: 가용한 개수를 가진 자원 에 대한 접근 제어용으로 사용되며, 세마포는 그 가용한 자원의 개수 로 초기화 된다. 자원을 사용하면 세마포가 감소, 방출하면 세마포가 증가 한다.
  • 이진 세마포: MUTEX 라고도 부르며, 상호배제의 (Mutual Exclusion)의 머릿글자를 따서 만들어졌다. 이름 그대로 0 과 1 사이의 값만 가능하며, 다중 프로세스들 사이의 Critical Section 문제를 해결하기 위해 사용한다.
  • 단점: Busy Waiting(바쁜 대기). Spin lock이라고 불리는 Semaphore 초기 버전에서 Critical Section 에 진입해야하는 프로세스는 진입 코드를 계속 반복 실행해야 하며, CPU 시간을 낭비했었다. 이를 Busy Waiting이라고 부르며 특수한 상황이 아니면 비효율적이다. 일반적으로는 Semaphore에서 Critical Section에 진입을 시도했지만 실패한 프로세스에 대해 Block시킨 뒤, Critical Section에 자리가 날 때 다시 깨우는 방식을 사용한다. 이 경우 Busy waiting으로 인한 시간낭비 문제가 해결된다.
  • Deadlock(교착상태): 세마포가 Ready Queue 를 가지고 있고, 둘 이상의 프로세스가 Critical Section 진입을 무한정 기다리고 있고, Critical Section 에서 실행되는 프로세스는 진입 대기 중인 프로세스가 실행되야만 빠져나올 수 있는 상황을 지칭한다.
• Mutex Lock
  • 뮤텍스는 상태가 0, 1로 이진 세마포어로 부르기도 함
  • 동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section 에 진입하는 프로세스는 Lock 을 획득하고 Critical Section 을 빠져나올 때, Lock 을 방출함으로써 동시에 접근이 되지 않도록 한다.
  • 한계: 다중처리기 환경에서는 시간적인 효율성 측면에서 적용할 수 없다.
• 모니터
  • 고급 언어의 설계 구조물로서, 개발자의 코드를 상호배제 하게끔 만든 추상화된 데이터 형태이다.
  • 공유자원에 접근하기 위한 키 획득과 자원 사용 후 해제를 모두 처리한다. (세마포어는 직접 키 해제와 공유자원 접근 처리가 필요하다. )

교착 상태(Deadlock)

• 교착 상태는 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 말한다.
• 컴퓨터 시스템에서 교착 상태는 시스템 자원, 공유 변수(또는 파일), 응용 프로그램(데이터베이스) 등을 사용할 때 발생할 수 있다.
• 세마포가 Ready Queue 를 가지고 있고, 둘 이상의 프로세스가 Critical Section 진입을 무한정 기다리고 있고, Critical Section 에서 실행되는 프로세스는 진입 대기 중인 프로세스가 실행되야만 빠져나올 수 있는 상황을 지칭한다.

자원 할당 그래프

프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것이다.

자원 할당 그래프를 사용하면 자원의 할당과 대기 상태를 한눈에 파악할 수 있다.

교착 상태 필요조건

• 상호 배제: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다
• 비선점: 한 프로세스가 사용 중인 자원은 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다
• 점유와 대기: 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태이어야 한다
• 원형 대기: 점유와 대기를 하는 프로세스 간에 관계가 원을 이루어야 한다

위 조건이 하나라도 만족되지 않으면 교착 상태는 일어나지 않는다.

교착 상태 해결방법

교착 상태 예방과 회피

예방(prevention)

교착 상태 발생 조건 중 하나를 제거하면서 해결한다 (자원 낭비 엄청 심함)

• 상호배제 부정 : 여러 프로세스가 공유 자원 사용
• 점유대기 부정 : 프로세스 실행전 모든 자원을 할당
• 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
• 순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구

회피(avoidance)

교착 상태 발생 시 피해나가는 방법

• 은행원 알고리즘(Banker’s Algorithm)
  • 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
  • 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
  • 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기

교착 상태 검출과 회복

교착 상태 검출

교착 상태 검출은 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방법. 만약 교착 상태가 발견되면 이를 해결하기 위해 교착 상태 회복 단계를 밟는다.

교착 상태를 검출하는 방법에는 크게 타임아웃 방법과 자원 할당 그래프를 이용하는 방법이 있다.

타임아웃

일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다.

• 장점: 쉽게 구현
• 단점: 엉뚱한 프로세스가 종료될 수 있다. 분산 데이터베이스에는 적용 불가(교착 상태 때무인지, 네트워크 때문인지 알 수 없음)

위와 같은 문제에도 불구하고 타임아웃은 대부분의 데이터베이스와 운영체제에서 많이 선호한다. 그 이유는 자원 할당 그래프를 이용한 방법은 구현하기가 힘들기 때문이다.

자원 할당 그래프를 이용

• 장점: 교착 상태를 정확하게 파악 할 수 있다
• 단점: 그래프를 유지, 갱신하고 사이클을 검사하는 추가 작업으로 인한 오버헤드가 발생

교착 상태 회복

교착 상태를 유발한 프로세스를 강제 종료한다

• 교착 상태를 일으킨 모든 프로세스를 동시에 종료
  • 이 방법은 작업을 시작하면 다시 교착 상태를 일으킬 가능성이 높다
  • 그래서 다시 실행할 때는 어떤 프로세스를 먼저 실행할지 순서를 정해 순차적으로 실행해야 한다
• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
  • 순서대로 종료하면서 나머지 프로세스의 상태를 파악하는 방법
  • 우선순위가 낮은 프로세스를 먼저 종료한다
  • 우선순위가 같은 경우 작업시간이 짧은 프로세스를 먼저 종료한다
  • 위의 두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료한다

참고

• 쉽게 배우는 운영체제 책 참고
• JaeYeopHan/Interview_Question_for_Beginner
• WeareSoft/tech-interview
• 위키백과 스레드
• 얼음연못, 멀티 프로세스와 멀티 스레드(파이썬은 멀티스레드 언어일까?)
• 우당탕탕 개발, 멀티프로세싱, 멀티프로그래밍,멀티태스킹,멀티스레딩
• wooody92’s blog, 멀티 프로세스(Multi Process)와 멀티 스레드(Multi Thread)
• 인파, 프로세스 vs 쓰레드 차이 정리
• Noah, Process, Thread 차이가 뭐예요?
• 비동기와 멀티스레딩
• Kishore’s Blog, Process vs Thread vs Core
• Quora, Why does a core only have two threads in a processor?
• Fork vs Spawn in Python Multiprocessing
• oxylabs, Concurrency vs Parallelism: The Main Differences