운영체제론[8]: CPU 스케줄러 1

CPU 스케줄러는 준비 큐에 있는 프로세스 중에서 선택하고 CPU 코어를 그 중 하나에 할당한다.

큐는 다양한 방식으로 정렬될 수 있다.

 

CPU 스케줄링 결정은 프로세스가 다음 중 하나의 상태로 전환될 때 발생한다.

1. 실행 중인 상태에서 대기 상태로 전환될 때

2. 실행 중인 상태에서 준비 상태로 전환될 때

3. 대기 상태에서 준비 상태로 전환될 때

4. 종료될 때

 

실행 중인 상태에서 대기 상태로 전환될 때와 종료될 때는 비선점(nonpreemptive)이다. -> CPU를 안놔줌

running -> ready 일때와 waiting -> ready 일때는 선점(preemptive)이다. -> CPU를 한정된 시간만 사용

 

공유 데이터에 대한 액세스를 고려해야함 - 경쟁상태 발생 가능

커널 모드에서 선점을 고려해야함. - 대부분 OS는 선점

중요한 OS활동 중 인터럽트 발생을 고려해야함 - 불가피한 경우, interrupt 처리를 미룸

 

 

Dispatcher

디스패처 모듈은 스케줄러 내에 task의 실행 순서를 제어하는 역할을 한다.

- context 전환

- user mode 전환

- 프로그램을 다시 시작할 위치로 이동하여 해당 프로그램을 다시 시작

 

디스패치 레이턴시 : 하나의 프로세스를 중지하고 다른 프로세스를 시작하는데 걸리는 시간

 

 

 

Scheduling Criteria (스케줄링 기준)

CPU 이용률 : CPU를 최대한 활용해서 작업을 수행 - 클 수록 좋음

처리량(Throughput) : 시간 당 완료한 프로세스의 수 - 클 수록 좋음

반환 시간 : 특정 프로세스가 시작해서 끝날 때까지의 시간 - 작을 수록 좋음

대기 시간 : 프로세스가 레디큐에서 기다리는 시간 - 작을 수록 좋음

응답 시간 : 요청이 제출된 후 첫 번째 응답이 생성될 때까지 걸리는 시간, 평균보다 편차가 중요 - 작을 수록 좋음

 

 

 

FCFS 스케줄링 (First-Come, First-Served Algorithm)

먼저 들어오는대로 해결하는 Nonpreemptive(비선점) algorithm이다.

Convoy-effect: 긴 CPU-bound job때문에 짧은 job이 계속 CPU를 기다리는 현상이 있다.

짧은 job이 먼저 올수록 평균 대기 시간이 짧아진다.

 

 

SJF 스케줄링 (Shortest-Job-First Algorithm = Shortest-next-CPU-burst)

각 프로세스와 해당 프로세스의 다음 CPU 버스트 길이를 연관시키고, 가장 짧은 시간에 프로세스를 스케줄링한다.

SJF는 최적으로, 특정 프로세스 집합에 대해 최소 평균 대기 시간을 제공하지만 다음 CPU 요청의 길이를 알기 어렵다.

 

 

CPU 요청의 시간 길이는 추정만 가능하다. (이전과 비슷할 것으로 예상한다)

그 다음 예측된 CPU burst가 가장 짧은 프로세스를 선택한다.

이전 CPU burst의 길이를 사용해서, 지수 평균을 사용해서 수행 가능하다.

 

a는 일반적으로 1/2로 설정된다.

선점형 버전은 shortest-remaining-time-first라고 한다.

-> 비선점: 새로 도착한 job이 현재 실행중인 job보다 짧아도 기다린다.

-> 선점 : 새로 도착한 job이 현재 실행중인 job보다 짧으면 교체한다.

 

a=0이면 예측값은 과거의 평균 CPU burst 시간에 의존한다. 

a=1이면 예측값은 최근 CPU burst 시간에 의존한다.

 

 

RR 스케줄링 (Round Lobin) - FCFS + preemption

각 프로세스는 작은 CPU 시간 단위인 타임퀀텀(10~100 밀리초)을 할당 받는다.

이 시간이 경과하면 프로세스는 선점되어 준비큐의 끝으로 이동한다.

 

준비 큐에 n개의 프로세스가 있고, 타임퀀텀이 q이면 각 프로세스는 최대 q 시간 단위로 CPU 시간의 1/n을 받는다.

어떤 프로세스도 (n-1)q 이상의 시간을 기다리지 않는다.

 

타이머 인터럽트는 매 타임퀀텀마다 발생해서 다음 프로세스를 스케줄링한다.

q가 크면 FIFO가 되고, q가 작으면 컨텍스트 스위칭이 자주 일어나 오버헤드가 발생한다.

 

보통 SJF보다 평균 반환 시간(프로그램 실행 시간)이 높지만, 더 나은 응답 시간(요청이 처음 시작되는데까지의 시간)을 보인다.

일반적으로 대부분의 프로세스가 타임퀀텀 안에 next CPU burst를 마칠 수 있으면 turnaround time(반환시간)을 줄일 수 있다.

 

"경험의 법칙 : CPU burst의 80%는 타임퀀텀보다 짧아야한다."

 

 

 

Priority 스케줄링

각 프로세스에는 우선순위가 할당된다.

CPU는 우선순위가 가장 높은 프로세스에 할당된다.

선점 방식은 우선순위가 높은 프로세스가 생기면 그 프로세스에게 CPU를 할당하고, 비선점 방식은 일단 실행중인 프로세스를 기다린다.

 

SJF는 예측된 다음 CPU burst 시간의 역수를 우선순위로 사용하는 스케줄링이다.

 

문제점은 Starvation, 우선 순위가 낮은 프로세스는 실행되지 않을 수 있다.

이는 시간이 경과함에 따라 프로세스의 우선순위를 높이는 방법으로 해결할 수 있다.

 

 

 

Priority + Round Robin

우선순위가 같은 프로세스끼리는 round-robin 을 사용한다.

 

Multilevel Queue를 사용해서, 같은 우선순위의 프로세스는 같은 큐에 들어간다.

가장 높은 우선순위의 큐에서 프로세스를 스케줄링한다. 현재 프로세스가 종료되거나 대기상태가 되면 가장 높은 우선순위 큐에서 대기중인 프로세스 중 가장 높은 우선순위의 프로세스를 실행한다.

 

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

이 경우엔 높은 우선순위가 전부 끝나지 않았더라도 할당된 퀀텀을 사용하면 다음 우선순위로 넘어간다.

 

 

Multilevel Feedback Queue

프로세스는 다양한 큐 간 이동할 수 있고, 이를 통해 에이징 기능을 구현할 수 있다.

Multilevel Feedback Queue는 다음 매개변수로 정의된다.

- 큐의 개수

- 각 큐에 대한 스케줄링 알고리즘

- 프로세스를 업그레이드 할 때 사용되는 방법

- 프로세스를 강등시킬 때 사용되는 방법

- 프로세스가 서비스를 받을 큐를 결정하는 방법

 

다음은 multilevel feedback queue의 예시다.

Q0은 8밀리초의 타임퀀텀을 가지는 라운드 로빈 스케줄링을 사용한다.

Q1은 16밀리초의 타임퀀텀을 가지는 라운드 로빈 스케줄링을 사용한다.

Q2는 FCFS 스케줄링을 사용한다.

 

새로운 작업은 Q0에 들어와서 FCFS 방식으로 서비스를 받고, 8밀리초 안에 안끝나면 Q1으로 이동한다.

Q1에서도 FCFS로 서비스를 받고 16밀리초 안에 안끝나면 Q2로 이동한다.

Q2에서는 FCFS 방식으로 서비스를 받는다.

 

 

 

Thread 스케줄링

사용자 수준 스레드와 커널 수준 스레드 간 구별

스레드가 지원되면 프로세스 대신 스레드가 스케줄링된다.

Many-to-One, Many-to-Many, 스레드 라이브러리는 사용자 수준 스레드를 LWP에서 실행하도록 스케줄링한다.

  - process contention scope(PCS)로 알려져 있으며, 스케줄링 경쟁이 프로세스 내에서 발생한다.

  - 일반적으로 개발자가 설정한 우선순위에 따라 수행된다.

 

커널 스레드 스케줄링은 system-contention-scope(SCS)이고 시스템 내 모든 스레드 간 경쟁한다.

 

스레드 생성시 PCS 또는 SCS 스케줄링을 지정할 수 있도록 API가 제공된다.

PTHREAD_SCOPE_PROCESS는 PCS 스케줄링을 사용한다.

PTHREAD_SCOPE_SYSTEM은 SCS 스케줄링을 사용한다.

 

하지만 OS에 따라서 PCS와 SCS를 지원 안할 수도 있고, linux와 macOS는 PTHREAD_SCOPE_SYSTEM만 지원한다.

 

PTHREAD는 user-level / kernel-level 모두에서 구현될 수 있기에 두가지 scope가 존재한다.

 

 

 

Multiple-Processor 스케줄링

여러개의 CPU가 사용 가능한 경우, CPU 스케줄링은 더 복잡해진다.

다중 프로세스는 다음 중 하나일 수 있다.

- 멀티코어(CPU)

- 멀티스레드 코어

- NUMA(Non Uniform Memory Access) 시스템

- Heterogeneous multiprocessing - 모바일에서 절전용 성능이 떨어지는 코어를 추가로 갖고 있는 형태

 

대칭적 다중 처리(Symmetric MultiProcessing)는 각 프로세서가 자체 스케줄링을 수행하는 경우를 뜻한다.

모든 스레드는 공통으로 사용 가능한 준비 큐(a)에 있을 수 있다.

각 프로세서는 자체적인 개별 스레드 큐(b)를 가질 수 있다.

 

a는 ready queue를 공유하기 때문에 경쟁상태에 놓일 수 있다. 따라서 locking이 필요해서 성능이 저하되고 high contention을 유발한다.

b는 가장 일반적인 상태로, caches의 성능이 좋지만 workload balance 알고리즘이 필요하다.

 

 

최근에는 여러 개의 프로세서 코어를 동일한 물리 칩에 배치하는 것이 트랜드이다. - 더 빠르고 전력 소모가 적다.

코어 당 하드웨어 스레드 수도 증가하고 있는데 memory stall(CPU가 메모리와 협업할 때 아무것도 안함)이 발생할 때 다른 스레드를 작업한다. 하드웨어 스레드의 개수가 2개 이상일 때 가능하다. 각 하드웨어 스레드는 별도의 IP와 레지스터를 가진다.

 

 

 

Multithreaded Multicore System

멀티스레드 멀티코어 시스템에서, 칩-멀티스레딩(CMT)는 각 코어에 여러 개의 하드웨어 스레드를 할당한다.

쿼드코어 시스템에서 코어 당 하드웨어 스레드가 2개씩 있는 경우, 운영체제는 8개의 논리 프로세서로 본다.

 

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

 

두가지 수준의 스케줄링이 있다.

1. 운영체제가 논리적 CPU에서 실행할 소프트웨어 스레드를 결정 - 여기서 소개하는 모든 스케줄링 알고리즘 

2. 각 코어가 물리적 코어에서 실행할 하드웨어 스레드를 결정 - round-robin, dynamic urgency value

 

 

SMP시스템에서는 효율성을 위해 모든 CPU 로드를 유지해야한다.

로드 밸런싱은 코어가 개별적인 큐를 가지고 있을 때, 작업 부하를 균등하게 분산시키기 위해 시도된다. 

push migration은 주기적인 작업으로 각 프로세서의 부하를 확인하고 부하가 많은 CPU에서 다른 CPU로 이동시킨다.

pull migration은 비어있는 프로세서가 바쁜 프로세서에서 작업을 가져온다.

 

Processor Affinity(프로세서 친화성)이 있다는 것은, 한 프로세서에서 스레드가 실행되면 해당 프로세서의 캐시 내용에는 해당 스레드가 수행한 메모리 액세스가 저장된다.

로드밸런싱은 부하를 균형있게 유지하기 위해 스레드를 다른 프로세서로 이동할 수 있기에 프로세서 친화성이 영향을 받을 수 있다. 이동한 스레드는 캐시에 저장돼있던 내용을 잃을 수 있다.

 

soft affinity은 운영체제가 스레드를 같은 프로세서에서 실행하도록 유지하려하지만 보장되지 않는다.

hard affinity은 프로세서가 프로세서 세트를 지정할 수 있도록, 같은 프로세서에서만 작동하도록 보장한다.

 

 

 

NUMA and CPU 스케줄링

NUMA(Non-Uniform Memory Access)는 비대칭적 메모리 액세스를 의미한다.

NUMA시스템은 여러 개의 물리적 프로세서로 구성돼있고, 각각의 프로세서는 자신이 직접 액세스할 수 있는 메모리 노드를 갖고 있다.

따라서 한 프로세서가 자신의 메모리 노드에 액세스하는 것보다 다른 프로세서의 메모리 노드에 액세스하는 것이 더 느리다.

 

NUMA 시스템에서는 CPU 스케줄링을 할 때 프로세서가 액세스할 수 있는 메모리 노드에 따라 스케줄링을 결정한다.

프로세서 A가 메모리 노드 1 에 있는 데이터를 처리해야하는 작업을 수행하고 있다면, 프로세서 A를 메모리 노드1에 가까운 프로세서로 스케줄링 해야한다.

이로써 프로세서는 자신이 직접 액세스할 수 있는 메모리 노드에 더 빠르게 액세스할 수 있고, 시스템의 전체적인 처리 속도를 향상시킬 수 있다.