[CS] 3-2. 운영체제 - 동기화와 교착 상태, CPU 스케줄링

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.

1. 동기화와 교착 상태

앞에서 프로세스 간 통신에 대해 설명했는데, 그 상황을 한 번 상기해 보자. 프로세스 A가 공유 메모리 공간에 글을 쓰고 프로세스 B가 읽는다고 가정하면, 두 프로세스는 서로 같은 공간에서 자원을 공유하고 있다. 혹은 프로세스 내부의 스레드 2개가 프로세스가 할당받은 파일을 수정하게 되는 경우 두 스레드는 하나의 파일 자원을 공유하고 있다. 이렇게 프로세스나 스레드가 공유하는 자원은 공유 자원(shared resource)라고 한다.

만약 공유 자원을 다수의 프로세스나 스레드가 동시에 어떤 규칙 없이 마구잡이로 접근하게 된다면 어떻게 될까? 이때 공유 자원에 접근하는 코드 중 동시 실행 시 문제가 발생할 수 있는 코드는 임계 구역(critical section)이라고 부르며, 이 임계 구역에 동시에 접근해서 실행하면 문제가 발생할 수 있다.
앞에서 프로세스 A가 공유 메모리에 글을 쓰고, 프로세스 B가 읽는다고 했었다. 만약 실행 순서가 뒤바뀌게 된다면 아직 적히지 않은 메모리에 접근하려고 했기 때문에 오류가 발생하게 된다. 즉 프로세스 A의 공유 메모리에 데이터를 쓰는 코드와 프로세스 B가 공유 메모리를 읽는 코드는 임계 구역이 된다.

이렇게 동시에 임계 구역의 코드를 실행하여 문제가 발생하는 상황을 레이스 컨디션(race condition)이라고 하며, 레이스 컨디션이 발생하면 데이터 일관성이 손상될 수 있기 때문에 하나가 실행되면 다른 작업은 그 작업이 끝날 때까지 대기해야 한다. 
개발의 영역에서, 레이스 컨디션을 방지하고 임계 구역을 관리하기 위해서는 프로세스와 스레드가 동기화(synchronization)되어야 한다. 동기화란 2가지 조건을 준수하여 실행하는 것을 의미한다.

• 실행 순서 제어 : 프로세스 및 스레드를 올바른 순서로 실행하기
• 상호 배제 : 동시에 접근하면 안되는 자원에 하나의 프로세스 및 스레드만 접근하기

---

1-2 동기화 기법

실행 순서와 상호 배제를 보장하기 위한 동기화 기법에는 무엇이 있는지 하나씩 알아보자. 참고로 앞으로 설명할 기능들은 대부분의 프로그래밍 언어에서 제공하고 있는 기능임을 인지하고 확인하자.

뮤텍스 락

뮤텍스 락은 상호 배제를 보장하기 위한 동기화 도구로 다음과 같은 원리로 동작한다.

임계 구역에 접근하고자 한다면 반드시 락을 획득해야 하고, 임계 구역에서 작업이 끝났다면 락을 해제해야 한다.

원리에서처럼, 전형적인 뮤텍스 락은 프로세스나 스레드가 공유하는 변수 lock과 2개의 함수(acquire, release)로 구현된다. 임계 구역에 진입하려면 lock.acquire()를 통해 락을 획득하고, 작업이 끝나면 lock.release()를 통해 해제한다. lock.release 이전에 다른 작업이 lock.acquire()를 사용해 락을 얻으려고 해도 획득할 수 없다. 

C++, 파이썬에서는 이미 뮤텍스 락이라는 이름으로 별도로 구현되어 있으며, 자바는 이름은 다르지만 ReentrantLock의 형태로 구현되어 있다.

세마포

뮤텍스 락은 하나의 공유 자원일때 사용하는 동기화 도구이다. 다만 늘 공유 자원이 하나만 있는 것은 아니다. 세마포는 공유 자원이 여러 개일때 사용할 수 있는 동기화 도구이다. 뮤텍스 락과 유사하지만 좀 더 일반화된 방식의 동기화 도구이다. 세마포는 철도 신호기에서 유래한 단어로 철도 신호기를 떠올려보면, 신호기가 내려오면 stop, 올라가면 go라는 신호로 간주해 움직인다. 이처럼 임계구역에서 2가지 신호를 기반으로 관리한다. 세마포는 뮤텍스 락과 유사하게 하나의 변수와 두 개의 함수로 구성된다.

• 변수 S : 사용 가능한 공유 자원의 개수를 나타내는 변수
• wait() : 임계 구역 진입 전 호출하는 함수
• signal() : 임계 구역 진입 후 호출하는 함수

이때, 변수 S는 임계구역에 진입할 수 있는 프로세스의 개수와 같다. 이 점을 인지하고 2 함수의 동작방식을 간단하게 설명하겠다.
wait()는 함수 호출이 되면 사용 가능한 공유 자원의 개수를 나타내는 변수 S를 1 감소시키고, 변수 S의 값이 0보다 작은지 확인한다. 즉 공유 자원이 남아 있다면 wait()를 호출한 프로세스는 임계 구역에 진입할 수 있다. 만약 남아있지 않다면 wait()를 호출한 프로세스 및 스레드는 대기 상태로 전환되어 임계 구역에 진입할 수 없다. 
반대로 signal()은 임계 구역에서 작업이 끝난 프로세스 혹은 스레드가 호출한다. 함수 호출이 되면 사용 가능한 공유 자원의 개수를 나타내는 변수 S를 1 증가시키고, 변수 S의 값이 0 이하인지 확인한다. 만약 S가 0 이하라면, 임계 구역 진입을 위해 대기하는 프로세스나 스레드가 있다는 의미이므로, 대기 상태의 프로세스 중 하나를 준비 상태로 변환한다.

세마포는 크게 이진 세마포와 카운팅 세마포로 구분할 수 있다. 위에서 설명한 방식은 카운팅 세마포로, 이진 세마포는 S가 0과 1의 값만을 가지며, 뮤텍스락과 유사하게 동작한다. 따라서 일반적으로 세마포라 함은 카운팅 세마포를 의미한다.

조건 변수와 모니터

모니터에 대해서 이해하기 위해서는 조건 변수에 대해서 먼저 이해해야 한다. 조건 변수란 실행 순서 제어를 위한 동기화 도구로 특정 조건에 따라 프로세스를 실행 / 일시 중단 함으로써 실행 순서를 제어할 수 있다. 조건 변수는 wait()과 signal() 함수를 호출할 수 있는데 다음과 같다.

• wait() : 아직 특정 프로세스가 실행될 조건이 되지 않았을 때, 실행을 중단한다.
• signal() : 특정 프로세스가 실행될 조건이 충족되었을 때, 실행을 재개한다.

예를 들어, 2개의 쓰레드가 있는데, A가 cv라는 조건 변수에 대해 실행 도중 cv.wait()을 실행했다면, 다른 스레드에서 cv.signal()을 호출하기 전까지 대기 상태로 접어들게 된다.

모니터는 공유 자원과 그 공유 자원을 다루는 함수로 구성된 동기화 도구로, 상호 배제부터 실행 순서 제어를 위한 동기화까지 모두 가능하다. 작동 원리는 다음과 같다.

• 공유 자원 접근을 위해 정해진 공유 자원 연산을 통해 모니터 내로 접근한다.
• 모니터 내에 진입하여 실행되는 프로세스(스레드)는 하나여야만 한다.
• 이미 모니터 내에 프로세스(스레드)가 있다면 큐에서 대기해야 한다.

이렇게 기본적으로 상호 배제를 구현하지만, 앞에서 설명한 조건 변수를 함께 사용한다면 실행 순서 제어도 가능하다. 말만 들으면 이해가 어려우니, 예시를 통해 확인해 보자.

1. 동시에 실행되는 프로세스 A, B 중 반드시 A가 먼저 실행된다는 가정을 해본다.

2. 프로세스 B 실행 전에 프로세스 A의 실행이 끝났는지를 검사한다.

3. 모니터 내에 진입해 프로세스 B가 실행된다면 프로세스 A는 실행이 종료된 것이므로 문제가 없다.

4. 그러나 프로세스 A가 종료되지 않았는데 B가 모니터 내로 진입했다면, cv.wait()을 통해 대기 상태로 변환한다.

5. 이후에 프로세스 A가 진입해 종료가 끝나면 cv.signal()을 호출해 종료됨을 알리고 프로세스 B를 실행한다.

위와 같은 모니터를 활용한 동기화 방식을 쓰는 대표적인 예가 자바의 synchronized 키워드다. 아래와 같이 synchronized 키워드를 사용한 메서드는 하나의 프로세스(스레드)만 실행할 수 있다.

public synchronized void example(int value){
	this.count += value;
}

스레드 안전

프로그래밍 언어 공식 문서를 읽다 보면, 스레드 안전이라는 용어가 자주 나온다. 스레드 안전이란 멀티스레드 환경에서 어떤 변수나 함수, 객체에 동시 접근이 이루어져도 실행에 문제가 없는 상태를 의미한다. 예를 들어 자바의 경우 ArrayList의 add 메서드는 스레드 안전하지 않지만, Vector의 add 메서드는 스레드 안전성이 보장되어 있다. 내부적으로 클래스를 살펴보면 vector의 경우 add 메서드에 synchronized 키워드로 구현되어 이를 보장한다.

---

1-3 교착 상태

프로세스를 실행하기 위해서는 자원이 필요한데, 만약 서로 다른 2개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다리게 된다면 어떤 프로세스도 작업을 이어나갈 수 없는 교착 상태가 발생할 수 있다. 교착 상태란 일어나지 않을 사건을 기다리며 프로세스의 진행이 멈춰버리는 현상을 말한다. 교착 상태가 발생하는 조건은 크게 4가지가 있다.

1. 상호 배제 : 한 번에 하나의 프로세스만 해당 자원을 이용 가능했기 때문에 발생한다. 한 프로세스가 사용하는 자원을 다른 프로세스가 접근 불가능한 상호 배제 상황에서 발생할 수 있다.
2. 점유와 대기(hold and wait) : 한 프로세스가 어떤 자원을 할당받은 상태(점유)에서 다른 자원 할당받기를 기다린다면(대기) 교착 상태가 발생할 수 있다.
3. 비선점 : 비선점이라는 뜻은 결국 해당 자원을 이용하는 프로세스의 작업이 끝나야 그 자원을 쓸 수 있다는 뜻이다. 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 경우 발생할 수 있다.
4. 원형 대기 : 프로세스와 프로세스가 요청한 자원이 원을 이루는 형태일 때 일어날 수 있다.

교착 상태의 해결법

교착 상태를 해결하는 방법은 크게 3가지 정도 있는데, 각각 살펴보자

1. 교착 상태 예방 : 애초에 조건에 부합하지 않도록 자원을 분배해 예방한다.
   • 교착 상태를 발생시키는 원인 4가지 중 하나를 충족하지 못하게 하여 예방한다.
2. 교착 상태 회피 : 교착 상태의 위험이 있을 때 자원을 할당하지 않는 방식으로 회피한다.
   • 기본적으로 교착 상태에 대해서 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주한다.
   • 대표적인 알고리즘으로는 은행원 알고리즘(banker's algorithm)이 있다.
3. 교착 상태 검출 후 회복 : 교착 상태를 검출한 후에 회복한다.
   • 앞의 2가지는 발생 전에 막는 사전 조치였다면, 이 방식은 사후 조치에 해당한다.
   • 교착 상태가 검출되면, 프로세스를 자원 선점을 통해 회복시키거나, 교착 상태에 있는 프로세스를 강제 종료함으로써 회복시킬 수 있다.

---

참고

[OS] Process 동기화(세마포어,뮤텍스,모니터)

[운영체제] 데드락(Deadlock, 교착 상태)이란?

---

2. CPU 스케줄링

운영체제는 다양한 프로세스(스레드)에 CPU의 사용을 배분함으로써 CPU 자원을 관리한다고 설명했다. 이 배분방법이 바로 CPU 스케줄링이다. CPU 스케줄링 알고리즘은 이런 스케줄링 절차를 의미하며, 이 알고리즘을 결정하고 수행하는 운영체제의 일부분을 CPU 스케줄러라고 한다.

우선순위

모든 프로세스는 CPU의 자원을 필요로 하기 때문에, 운영체제는 공정하고 합리적으로 자원을 할당해야 한다. 운영체제는 프로세스 별로 우선순위를 판단하여 PCB에 명시하고 우선순위가 높은 프로세스일수록 CPU의 자원을 더 빨리, 더 많이 할당한다.

그렇다면 어떤 프로세스에 우선순위를 높게 할당할까? 가장 대표적인 고려 요소는 CPU 활용률이다. 운영체제는 CPU 활용률을 높게 유지할 수 있도록 우선순위를 할당한다. CPU 활용률이란 전체 CPU 가동 시간 중 작업을 처리하는 시간의 비율을 의미한다. 운영체제는 높은 CPU 활용률을 유지하기 위해 기본적으로 입출력 작업이 많은 프로세스의 우선순위를 높게 유지한다.

대부분의 프로세스들은 CPU와 입출력장치를 모두 사용해 실행과 대기 상태를 오간다. 이때 프로세스가 CPU를 이용하는 작업을 CPU 버스트라고 하고, 입출력장치를 기다리는 작업을 입출력 버스트라고 한다. 또한 입출력 작업이 많은 프로세스는 입출력 집중 프로세스, CPU 작업이 많은 프로세스는 CPU 집중 프로세스라 불린다.
만약 입출력 집중 프로세스와 CPU 집중 프로세스가 동시에 자원을 요청했다면, 입출력 집중 프로세스를 가능한 빨리 실행시켜 끊임없이 입출력장치를 작동시킨 다음, CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 합리적이다.

스케줄링 큐

운영체제는 자원을 이용하고 싶은 프로세스들에게 줄을 서서 기다릴 것을 요구하는데, 이 줄은 스케줄링 큐를 통해 구현된다. 운영체제가 관리하는 줄인 큐는 다양한 종류가 있지만 대표적으로 준비 큐, 대기 큐에 대해서 알아보자.

준비 큐는 CPU를 이용하고 싶은 프로세스의 PCB가 서는 줄을 의미하고, 대기 큐는 대기 상태에 접어든 프로세스의 PCB가 서는 줄을 의미한다. 입출력 작업일 경우 주로 대기큐에서 완료 인터럽트를 기다리고, 준비 상태인 프로세스는 준비 큐의 마지막에 삽입되어 순서를 기다린다.

선점형 스케줄링과 비선점형 스케줄링

스케줄링은 프로세스의 실행이 끝나면 기본적으로 이루어진다. 그러나 어떤 프로세스가 작업이 끝나지 않았는데도 스케줄링 수행되는 대표적인 시점이 2개가 있다. 하나는 실행 상태에서 입출력 작업을 위해 대기 상태로 전환될 때이고, 또 하나는 실행 상태에서 타이머 인터럽트가 발생해 준비 상태로 변경될 때이다.

이때, 위 상황 모두에서 수행되는 스케줄링 유형을 선점형 스케줄링이라고 하고, 전자에서는 수행되는 스케줄링 유형을 비선점형 스케줄링이라고 한다. 선점형 스케줄링은 어떤 프로세스가 CPU를 할당받아 사용하고 있더라도 운영체제가 그걸 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링을 의미한다. 따라서 타이머 인터럽트 기반 스케줄링은 선점형에 해당한다. 비선점형 스케줄링은 그와 반대로 어떤 프로세스가 작업이 종료되거나 스스로 대기 상태에 접어들기 전에 끼어들 수 없는 스케줄링을 의미한다. 각각에는 다음과 같은 장단점이 있다.

선점형 스케줄링	비선점형 스케줄링
더 급한 프로세스가 끼어들 수 있어 CPU 독점을 막을 수 있음.	문맥 교환 과정이 적어 오버헤드 발생은 적음
문맥 교환 과정에서 오버헤드가 발생할 수 있음	당장 CPU를 사용해야하는 프로세스일지라도 이미 작업 중이라면 무한정 기다릴 수 밖에 없음

2-1 CPU 스케줄링 알고리즘

앞에서 잠깐 설명했듯, 운영체제가 CPU를 프로세스에 배분하는 방법을 CPU 스케줄링 알고리즘이라고 했다. 그 알고리즘은 매우 다양하겠지만 대표적인 7가지 정도에 대해서만 알아보자.

선입 선처리 스케줄링	준비 큐에 삽입된 순서대로 먼저 CPU를 요청한 프로세스부터 CPU를 할당하는 방식. 기다리는 시간이 매우 길어질 수 있고, 호위 효과() 문제가 있다.
최단 작업 우선 스케줄링	준비 큐에 삽입된 프로세스 중 CPU를 이용하는 시간이 짧은 프로세스부터 먼저 실행하는 스케줄링 방식
라운드 로빈 스케줄링	선입 선처리 + 타임 슬라이스라는 개념이 더해진 스케줄링으로, 큐에 삽입된 순서대로 실행하되 타임 슬라이스만큼만 CPU를 이용하는 선점형 스케줄링이다.
최소 잔여 시간 우선 스케줄링	최단 작업 우선 + 라운드 로빈을 합친 방식으로, 정해진 타임 슬라이스만큼 CPU를 이용하되, 남아 있는 작업시간이 가장 적은 프로세스를 다음으로 CPU를 이용할 프로세스로 정한다.
우선순위 스케줄링	프로세스에 우선순위를 부여하고 우선순위 순으로 실행하는 방식이다. 다만 우선순위가 낮은 프로세스는 큐에 먼저 삽입되더라도 계속 지연되는 아사 현상 문제가 있다. 이를 위해 에이징 기법을 통해 오래 대기한 프로세스의 우선순위를 점차 올리는 방식으로 해결하기도 한다.
다단계 큐 스케줄링	우선순위 스케줄링의 진화한 형태로 우선순위별로 여러 개의 준비 큐를 사용하는 방식이다. 다만 프로세스들이 큐 사이를 이동할 수 없기 때문에 아사 문제가 여전히 발생할 수 있다.
다단계 피드백 큐 스케줄링	다단계 큐의 문제를 해결한 방식으로 프로세스들이 큐 사이를 이동할 수 있다.

전통적인 이론에서는 어떻게 CPU 스케줄링이 이루어지는 지에 대해서는 확인해 볼 수 있었다. 다만 실제 운영체제에서는 어떻게 이루어지고 있는지 리눅스 기반 운영체제에서 확인해 보자.

---

2-2 리눅스 CPU 스케줄링

리눅스에서는 상황에 따라 다양한 스케줄링 알고리즘이 사용될 수 있는데, 이는 스케줄링 정책을 보면 알 수 있다. 스케줄링 정책이란 새로운 프로세스를 언제 어떻게 선택하여 실행할지를 결정하기 위한 규칙의 집합으로, 리눅스에서는 크게 다음과 같은 5가지 스케줄링 정책을 사용한다.

스케줄링 정책	적용 상황
SCHED_FIFO	실시간성 프로세스에 적용되는 정책(높은 우선순위)
SCHED_RR
SCHED_NORMAL	일반적인 프로세스에 적용되는 정책
SCHED_BATCH	일반적인 프로세스만큼 자주 선점하지 않는 배치 작업에 적용되는 정책
SCHED_IDLE	우선순위 매우 낮은 프로세스에 적용되는 정책

FIFO, RR은 RT라는 스케줄러에 의해 이뤄지는 스케줄링으로 실시간성이 강조된 프로세스에 적용되는 정책이다. NORMAL은 CFS라는 스케줄러에 의해 스케줄링이 이루어진다. 사실 자세한 내용은 조금 딥해지는 부분이 있기 때문에 더 깊게 학습하기를 윈 한다면 아래 참고 사항에서 추가적으로 확인하면 좋겠다. 핵심은 리눅스 CPU 스케줄링에서는 전통적인 CPU 스케줄링 방식과 조금 다르게 타임 슬라이스를 가중치에 따라 다르게 할당할 수 있다는 것만 인지하고 있자.

---

참고

CPU 스케줄링 알고리즘 요약정리

 

프로세스 스케줄링 (+리눅스에서의 스케줄링 예시)

 

[운영체제] Linux의 CPU 스케줄링 (CFS 알고리즘)을 파보자!