운영체제 - 5장 CPU 스케줄링

기본 개념

다중 프로그래밍의 목적은 CPU 이용률 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는데 있다.

CPU-I/O 버스트 사이클

CPU-I/O 버스트 사이클 : 순환 구조로 CPU 실행과 I/O 대기 형태의 진행 방식이다.

(CPU버스트 다음에는 I/O 버스트가 있다.)

(CPU 버스트의 일반적인 형태)

CPU 스케줄러

CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로세스 중에서 하나를 선택해 실행해야 한다.

선점 및 비선점 스케줄링

CPU 스케줄링 선택은 프로세스가 다음과 같은 때 취할 수 있다.

• 실행에서 대기 상태로 될 때
• 실행에서 준비 상태로 될 떄
• 대기에서 준비 상태로 될 때
• 종료 되었을 때

위에 스케줄링 방식은 비선점 방식이다. (종료나 대기상태가 아니면 CPU를 놓치 않음)

나머지는 전부 선점 방식이다. (CPU를 한정된 시간 동안만 할당)

• 공유 데이터에 접근 할 때 (race condition 발생 가능)
• 커널 모드일 때 (비선점일 수도 있지만 대부분의 현대 OS가 선점으로 처리한다.)
• 중요한 OS 활동 때 인터럽트가 발생할 때

디스페처

CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이며 다음과 같은 작업을 포함한다.

• 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump) 하는 일

디스패치 지연 : 디스페처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데까지 소요되는 시간

스케줄링 기준

• (최대화) CPU 사용률 : 가능한 한 CPU를 최대한 바쁘게 유지하기

  • 유닉스 계열은 top 커맨드로 사용률을 알 수 있다.
  • 40%는 가벼운 시스템, 90%는 무거운 시스템으로의 범위를 가져야 한다.

• (최대화) 처리량 : 단위 시간당 완료된 프로세스의 개수

• (최소화) 총처리(반환) 시간 : 프로세스의 제출 시간과 완료 시간의 간격 (프로세스의 시작 부터 끝날 때까지의 시간)

• (최소화) 대기 시간 : 프로세스가 준비 큐에서 대기하면서 보낸 시간의 합

  • CPU time 이나 I/O time을 스케줄러가 줄일 수 없으므로, 대기시간을 프로세스가 ready queue에 머무는 시간으로 정의한다.

• (최소화) 응답 시간 : 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간

  • 반환시간이 같아도 응답시간이 짧으면 결과를 미리 볼 수 있는 효과가 있다.

  • 응답시간의 평균을 줄이는 것보다 편차를 줄이는 것이 일반적으로 더 중요하다.

(최소화/최대화) : 스케줄링 알고리즘 최적화 기준

스케줄링 알고리즘

선입선출 스케줄링 (FCFS)

비선점 알고리즘이다.

호위 효과 (convoy effect) : 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기 위해 기다리는 것

최단 작업 우선 스케줄링 (SJF)

Shortest-next-cpu-burst 알고리즘이 더 맞는 표현이다.

각 프로세스에 다음 CPU 버스트 길이를 연관시킨다. 이 스케줄링은 프로세스 전체 길이가 아니라 다음 CPU 버스트의 길이에 의해 스케줄링 된다.

프로세스 집합에 대해 최소한의 평균 대기 시간을 반환해주기 때문에, SJF는 사실 최적의 알고리즘이다.

하지만, 다음 CPU 요청의 길이를 알기 쉽지 않기 떄문에 실제로 구현하기가 힘들다.

다음 CPU 버스트에 대해 아는 방법은 예측밖에 없다. 그러니 CPU 타임을 예측해서 프로세스를 고를 수 밖에 없다.

지수 평균을 이용해 이전 CPU 버스트의 길이를 사용하여 위에 방법을 실행할 수 있다.

라운드 로빈 (RR = FCFS + preemption)

선입선출과 유사하짐나 시스템들이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다.

일반적으로 10에서 100밀리초 정도의 시간 할당량 혹은 타임 슬라이스라는 단위의 시간을 정의한다.

준비 큐는 원형 큐로 동작한다.

만약 $n$개의 프로세스들이 준비 큐에 있고 시간 할당량이 $q$ 라면 각 프로세스들은 한 개의 $q$ 단위에서 $1/n$의 CPU time을 받는다. 어떤 프로세스도 $(n-1)q$ 시간 단위 이상 대기하지 않는다.

타이머가 매 할당량마다 인터럽트해서 다음 프로세스로 넘어 간다.

시간 단위 $q$가 너무 크면 FIFO와 같은 성능을 내고, 너무 작으면 문맥 교환 때문에 오버헤드가 너무 커진다. (문맥 교환은 10 마이크로초보다 적다)

(RR 예제)
평균적으로 반환 시간은 SJF보다 길지만, 반환 시간은 더 낫다.

우선순위 스케줄링

우선순위(정수)가 각 프로세스들에 연관되어 있으며, CPU는 가장 높은 우선순위를 가진 가진 프로세스에 할당된다. (정수가 적을수록 높은 순위)

우선순위가 같은 프로세스들은 선입선출로 처리된다. SJF는 우선순위가 다음 CPU 버스트 time의 역인 우선순위 스케줄링이다.

우선순위 스케줄링의 문제점은 기아 상태이고 해결 방안으로 노화와 RR 결합이 있다.
기아 : 낮은 우선순위에 프로세스들은 계속해서 실행되지 못한다.
노화 : 대기하는 프로세스들의 우선순의를 점진적으로 증가시킨다.

(RR과 결합한 우선순위 스케줄링 예제)

다단계 큐

우선순위마다 별도의 큐를 갖게하고 우선순위 스케줄리이 우선순위가 가장 높은 큐에서 프로세스를 스케줄하게 하는 방법

여기서도 우선순위가 같은면 라운드 로빈으로 처리한다.

• 높은 우선순위를 무조건 먼저 실행할 수도 있고
• 큐에 따라 time-slice를 배정할 수도 있다.

다단계 피드백 큐

프로세스가 큐들 사이를 이동하는 것을 허용하는 스케줄링이다. (가장 일반적이면서도 복잡한 알고리즘이다.

이동하는 방식으로는

• 큐를 이동할 수 있는 방식으로 CPU를 많이 사용했으면 밑으로 내리고
• 너무 오래 기다리고 있으면 위로 올리기도 한다.

노화도 이런 방식으로 구현될 수 있다.

다단계 피드백 큐 스케줄러는 다음의 매개변수에 의해 정의된다.

• 큐의 개수
• 각 큐를 위한 스케줄링 알고리즘
• 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
• 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
• 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법

선입선출 스케줄링 (FCFS)

비선점 알고리즘이다.

호위 효과 (convoy effect) : 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기 위해 기다리는 것

최단 작업 우선 스케줄링 (SJF)

Shortest-next-cpu-burst 알고리즘이 더 맞는 표현이다.

각 프로세스에 다음 CPU 버스트 길이를 연관시킨다. 이 스케줄링은 프로세스 전체 길이가 아니라 다음 CPU 버스트의 길이에 의해 스케줄링 된다.

프로세스 집합에 대해 최소한의 평균 대기 시간을 반환해주기 때문에, SJF는 사실 최적의 알고리즘이다.

하지만, 다음 CPU 요청의 길이를 알기 쉽지 않기 떄문에 실제로 구현하기가 힘들다.

다음 CPU 버스트에 대해 아는 방법은 예측밖에 없다. 그러니 CPU 타임을 예측해서 프로세스를 고를 수 밖에 없다.

지수 평균을 이용해 이전 CPU 버스트의 길이를 사용하여 위에 방법을 실행할 수 있다.

라운드 로빈 (RR = FCFS + preemption)

선입선출과 유사하짐나 시스템들이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다.

일반적으로 10에서 100밀리초 정도의 시간 할당량 혹은 타임 슬라이스라는 단위의 시간을 정의한다.

준비 큐는 원형 큐로 동작한다.

만약 $n$개의 프로세스들이 준비 큐에 있고 시간 할당량이 $q$ 라면 각 프로세스들은 한 개의 $q$ 단위에서 $1/n$의 CPU time을 받는다. 어떤 프로세스도 $(n-1)q$ 시간 단위 이상 대기하지 않는다.

타이머가 매 할당량마다 인터럽트해서 다음 프로세스로 넘어 간다.

시간 단위 $q$가 너무 크면 FIFO와 같은 성능을 내고, 너무 작으면 문맥 교환 때문에 오버헤드가 너무 커진다. (문맥 교환은 10 마이크로초보다 적다)

(RR 예제)
평균적으로 반환 시간은 SJF보다 길지만, 반환 시간은 더 낫다.

우선순위 스케줄링

우선순위(정수)가 각 프로세스들에 연관되어 있으며, CPU는 가장 높은 우선순위를 가진 가진 프로세스에 할당된다. (정수가 적을수록 높은 순위)

우선순위가 같은 프로세스들은 선입선출로 처리된다. SJF는 우선순위가 다음 CPU 버스트 time의 역인 우선순위 스케줄링이다.

우선순위 스케줄링의 문제점은 기아 상태이고 해결 방안으로 노화와 RR 결합이 있다.
기아 : 낮은 우선순위에 프로세스들은 계속해서 실행되지 못한다.
노화 : 대기하는 프로세스들의 우선순의를 점진적으로 증가시킨다.

(RR과 결합한 우선순위 스케줄링 예제)

다단계 큐

우선순위마다 별도의 큐를 갖게하고 우선순위 스케줄리이 우선순위가 가장 높은 큐에서 프로세스를 스케줄하게 하는 방법

여기서도 우선순위가 같은면 라운드 로빈으로 처리한다.

• 높은 우선순위를 무조건 먼저 실행할 수도 있고
• 큐에 따라 time-slice를 배정할 수도 있다.

다단계 피드백 큐

프로세스가 큐들 사이를 이동하는 것을 허용하는 스케줄링이다. (가장 일반적이면서도 복잡한 알고리즘이다.

이동하는 방식으로는

• 큐를 이동할 수 있는 방식으로 CPU를 많이 사용했으면 밑으로 내리고
• 너무 오래 기다리고 있으면 위로 올리기도 한다.

노화도 이런 방식으로 구현될 수 있다.

다단계 피드백 큐 스케줄러는 다음의 매개변수에 의해 정의된다.

• 큐의 개수
• 각 큐를 위한 스케줄링 알고리즘
• 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
• 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
• 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법
  

스레드 스케줄링

4장에서 프로세스 모델에 스레드를 도입하면서 사용자 수준과 커널 수준 스레드를 구별하였다.

대부분 최신 운영체제에서는 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드이다.

다대일 다대다 모델에서 사용자 수준 스레드를 스레드 라이브러리에 의해 관리되었다. (커널은 그들의 존재를 몰랐음) CPU상에서 실행되기 위해서 LWP(가상 프로세서로 논리적인 뷰 제공)를 통한 간접적인 방식일지라도 사용자 스레드는 커널 스레드에 사상되어야 한다.

프로세스 경쟁 범위, PCS (process-contention scope)

사용자 수준과 커널 수준 스레드의 차이는 어떻게 스케줄링 되느냐이다.

스레드 라이브러리는 사용자 수준 스레드를 가용한 LWP상에서 스케줄 한다.

이러한 기법은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스 경쟁 범위라고 한다. (통상 프로그래머들의 의해 우선순위가 결정된다)

CPU상에 어느 커널 스레드를 스케줄 할 것인지 결정하기 위해서 커널은 시스템 경쟁 범위(SCS)를 사용한다.

Pthread 스케줄링

API는 스레드 생성 시 PCS인지 SCS인지 구분할수 있게 해준다.

• PTHREAD SCOPE PROCESS는 PCS 스케줄링을 사용하여 스레드를 스케줄 한다.
• PTHREAD SCOPE SYSTEM은 SCS 스케줄링을 사용하여 스레드를 스케줄 한다.

이는 운영체제마다 제한도가 다를수 있다. 리눅스 맥OS는 SCS만 가능하다.

Pthread는 사용자 수준, 커널 수준 둘 다에서 구현이 가능하여 두 가지 범위가 존재한다.

다중 처리기 스케줄링

CPU 스케줄링은 여러개의 CPU가 사용 가능할 때 더 복잡해진다.

다중처리기는 다음 중 하나의 구조일 수 있다.

• 다중 코어 CPU
• 다중 스레드 코어 (하나의 코어가 다중 하드웨어 스레드를 지원)
• NUMA 시스템 (Non Uniform Memory Access)
• 이기종(Heterogeneous) 다중 처리 (모바일 시스템에서 동일한 기능을 하지만 전원을 절약하기 위해 성능이 떨어지는 코어를 추가로 가지고 있는 형태)

다중 처리기 스케줄링에 대한 접근 방법

대칭 다중 처리 (SMP) : 각 프로세서는 스스로 스케줄링 할 수 있다. (리눅스, 맥, 윈도우, 안드로이드, iOS)

(Astmmetric multiprecessing에서는 한 프로세서(마스터)가 스케줄링을 담당)

각 프로세서의 스케줄러가 준비 큐를 검사하고 실행할 스레드를 선택하여 스케줄링이 진행된다.

다중 코어 프로세서

현대 컴퓨터 하드웨어는 동일한 물리적인 칩 안에 여러개 의 처리 코어를 장착한 다중 코어 프로세서이다.

빠르고 적은 전력을 사용한다. 코어당 다중 스레드(하드웨어적인) 또한 늘어나고 있다.

메모리 스톨이라고 하는 이 상황은 최신 프로세서가 메모리보다 훨씬 빠른 속도로 작동하기 때문에 주로 발생한다.

메모리 스톨 : CPU가 메모리에서 데이터를 가져오거나 내보낼 때 아무것도 안하는 현상

멀티스레드 다중코어 시스템
모든 코어가 한 개의 하드웨어 스레드보다 많다.

만약 한 개의 스레드가 메모리 스톨이 일어나면 다른 스레드로 교체한다.

Chip-multithreading(CMT)
단일 하드웨어 코어에 여러 하드웨어 스레드를 할당하는 것

인텔에서는 하이퍼-스레딩 또는 동시 다중 스레딩이라고 한다.

프로세서에는 4개의 컴퓨팅 코어가 있으며 각 코어에는 2개의 하드웨어 스레드가 있다.
운영체제 관점에서 볼 때 8개의 논리적 CPU가 있다.

코어 내에서 두 개의 하드웨어 스레드가 스위칭할 때 파이프 명령어가 깨지므로 비용 증가를 감안해야 한다. 각 코어는 하나의 하드웨어 스레드만 실행 가능하다.

(이중 스레드 처리 코어의 2단계 스케줄링을 묘사한 그림이다.)

1단계 : 운영체제가 각 하드웨어 스레드(논리적 CPU)에서 실행할 소프트웨어 스레드를 선택할 떄 결정해야 하는 스케줄링 결정을 한다.

2단계 : 각 코어가 실행할 하드웨어 스레드를 결정하는 방법을 명시한다.

부하 균등화(load balancing)

만약 SMP라면 부하를 모든 처리기에 균등하게(효율적으로) 배분하는 것이 중요하다.

• load balancing: 모든 처리기 사이에 부하가 고르게 배분되도록 시도한다.

  • 코어를 개별적인 큐를 가지고 있는 경우에만 의미가 있음

• push migration: 특정 태스크가 주기적으로 각 처리기의 부하를 검사하고 만일 불균형 상태로 발력지면 과부하인 처리기에서 쉬고 있거나 덜 바쁜 처리기로 스레드를 이동시킴으로 부하를 분배한다.

  • 특정 태스크가 주기적으로 검사하는 방식

• pull migration: 안정된 처리기가 부하된 처리기의 대기중인 프로세서를 pull 한다.

  • idle 처리기가 자발적으로 짐을 덜어주는 방식

모바일 시스템에서는 동일한 기능을 하지만 배터리를 절약하기 위해 성능이 떨어지는 코어를 추가로 가질 수 있다. 이런 시스템을 HMP라고 한다.

처리기 신호도(processor affinity)

프로세스 선호도 : (SMP를 지원하는 대부분의 운영체제에서) 스레드를 한 프로세서에서 다른 프로세서로 이주시키지 않고 대신 같은 프로세서에서 계속 실행시키면서 warm cache를 이용하려 한다.

약한 선호도 : 운영체제가 동일한 처리기에서 프로세스를 실행시키려고 노력하는 정책을 가지고 있지만 보장하지 않을 때

강한 선호도 : 프로세스가 자신이 실행될 처리기 집합을 명시할 수 있게 하는 것

실시간 CPU 스케줄링

일반적으로 연성 실시간 시스템과 경성 실시간 시스템으로 구분한다.

• 연성 실시간 시스템 : 중요한 실시간 프로세스가 스케줄 되는 시점에 관해 아무런 보장을 하지 않는다.
  오직 중요 프로세스가 그렇지 않은 프로세스들에 비해 우선권을 가진다는 것만 보장한다.

• 경성 실시간 시스템 : 더 엄격한 요구 조건을 만족시켜야 한다.

지연시간 최소화

이벤트 지연시간 : 이벤트가 발생해서 그것을 인지하고 서비스를 시작할 때까지 지연시간

두 가지 유형의 지연시간이 실시간 시스템의 성능을 좌우한다.

• 인터럽트 지연시간 : CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴이 시작하기까지의 시간
• 디스패치 지연시간 : 스케줄링 디스패처가 하나의 프로세스를 블록시키고 다른 프로세스를 시작하는 데까지 걸리는 시간을 말한다.

디스패치 지연시간 충돌 단계 2가지 요소

• 커널에서 동작하는 프로세스에 대한 선점
• 높은 우선순위의 프로세스가 필요한 자원을 낮은 우선순위 프로세스 자원이 방출

우선순위 기반 스케줄링

실시간 스케줄링을 위해서는 스케줄러는 반드시 선점과 우선순위 기반 스케줄링을 지원해야 한다.

경성 실시간 시스템은 데드라인을 세우는 것까지 지원해야 한다.

일정한 간격으로 CPU가 필요하기 때문에 프로세스들은 주기적이다.

Rate-Monotonic

선점 가능한 정적 우선순위 정책을 이용하여 주기 태스크들을 스케줄한다.

주기를 갖는 프로세스는 CPU 버스트가 항상 같다는 전제하에,

짧은 주기는 높은 우선순위이고, 긴 주기는 낮은 우선순위를 갖는다.

Earliest Deadline First Scheduling (EDF)

마감시간에 따라서 우선순위를 동적으로 부여한다.

마감시간이 빠를수록 높은 우선순위, 마감시간이 늦을수록, 낮은 우선순위를 갖는다.

일정 비율의 몫 스케줄링(proportinate share scheduling)

모든 으용들에 T개의 시간 몫을 할당하여 동작한다.

한 개의 응용이 N개의 시간 몫을 할당받으면 그 응용은 모든 프로세스 시간 중 N/T 시간을 할당받게 된다.

예를 들어, T = 100인 시간 몫이 있다고 할 때,
3개의 프로세스 A, B, C에 이를 나누어 할당한다고 가정하자.
A는 50 몫, B는 15 몫, C는 20 몫을 할당받았다고 할 때,
일정 비율의 몫 스케줄링 기법은 A가 모든 처리기 시간의 50%를, B가 15%를, C가 20%를 할당받는 것이다.

POSIX 실시간 스케줄링

POSIX는 실시간 컴퓨팅용으로 POSIX.1b라는 확장을 제공한다.

API는 실시간 스레드를 관리하기 위한 함수를 제공한다.

실시간 스레딩을 위한 두 스케줄링 클래스를 정의한다:

• SCHED FIFO : 선입선출 큐를 사용해서 선입선출 방식으로 스레드가 스케줄된다.
• SCHED RR : 같은 우선순위의 스레드에 시간 할당량을 제공하는것을 제외하면 SCHED FIFO와 비슷하다.

---

이후 추가 예정...

운영체제 사례들

알고리즘의 평가