CPU 스케줄링 (명품_운영체제 Ch 05)

February 5, 2025

스케줄링

다중프로그래밍의 도입 이후 운영체제는 다음 2가지 스케줄링을 시행하였다

작업 스케줄링
- 메모리에 적재된 스레드가 종료되면 디스크에서 기다리는 작업 중 하나를 선택하여 메모리에 적재
- 상태 변화 : New -> Ready
CPU 스케줄링
- 실행중인 스레드가 특정 상황으로 인해 실행이 중단되었을 때 메모리에 적재된 스레드 중 CPU에 실행시킬 스레드 선택하는 과정
- 상태 변화 : Ready -> Running

프로그램은 CPU burst -> I/O burst -> .. -> CPU burst -> I/O burst의 반복이다

CPU burst
- CPU가 코드를 집중적으로 실행하는 상황
I/O burst
- I/O 장치에 의해 입출력이 이루어지는 상황
CPU 집중(CPU intensive) 프로세스
- CPU burst 시간이 I/O burst 시간보다 훨씬 많을 때
I/O 집중(I/O intensive) 프로세스
- I/O burst 시간이 CPU burst 시간보다 훨씬 많을 때 I/O burst 시간 동안 CPU의 유휴 시간을 줄이기 위해 CPU 스케줄링이 도입되었다

CPU 스케줄링

Ready 상태의 스레드 중 Running 상태로 변경할 스레드를 선택하는 과정

발생 상황
- 실행중인 스레드가 I/O를 요청하는 시스템 호출을 실행하여 Block 상태가 되거나, 자원을 기다리는 상태가 될 때
- 실행중인 스레드가 자발적으로 CPU를 반환하는 경우(ex yield() 시스템 호출)
- 실행중인 스레드의 타임 슬라이스 소진으로 인한 타이머 인터럽트
- 실행중인 스레드보다 우선순위가 높은 스레드의 입출력 작업이 완료되어 발생한 I/O 인터럽트
목적
- CPU 활용률 향상(유휴 시간 감소)
- 컴퓨터 시스템 처리율 향상(처리 스레드 개수 증가)
평가 기준(시스템 마다 다양함)
- CPU 활용률(CPU utilization) 증가
  - CPU 사용 시간 / 컴퓨터 시스템 가동 시간
- 처리율(throughput) 증가
  - 단위 시간 당 처리하는 스레드 개수
- 응답 시간(response time) 최소화
  - 사용자의 요청에 대한 반환 시간
- 대기 시간(waiting time) 최소화
  - 스레드가 준비 리스트에서 CPU 할당을 기다리는 시간
- 소요 시간(turnaround time) 최소화
  - 프로세스가 시작되어 종료될 때까지 걸린 시간
- 시스템 정책 우선(high policy enforcement)
  - 시스템의 종류(보안 중심, 실시간 등)에 따라 해당 정책에 맞도록 이루어짐
- 지연 활용률(high resource efficency)
  - CPU나 I/O 장치 등의 자원이 놀지 않도록 하는 것(처리율 증가)
타임 슬라이스(time slice)
- 한 스레드가 CPU를 사용할 수 있는 시간
- 운영체제(커널)는 타임 슬라이스를 정하고 타이머를 통해 이 시간이 되면 스레드를 강제 중단시켜 준비 리스트에 삽입한다

CPU 스케줄링의 진행 과정

위에 기재된 특정 상황으로 인해 새로 실행할 스레드를 선택해야함 -> 스케줄러 코드를 통해 선택 -> 이후, 스케줄러 코드는 디스패처 코드를 호출 -> 디스패처 코드를 통해 컨텍스트 스위칭 수행

스케줄러(scheduler) 코드
- 준비 리스트에 있는 스레드 중 실행할 스레드를 선택, 이후에 디스패처 코드를 실행함
디스패처(dispatcher) 코드
- 스케줄러 코드에 의해 선택된 스레드를 CPU가 실행하도록 하는 커널 코드의 한 부분(컨텍스트 스위칭을 수행하는 코드)
- 기존에 실행되던 스레드 A의 TCB에 현재 레지스터 값을 저장하고, 새로 실행될 스레드 B의 TCB에 저장된 레지스터 값을 CPU에 복사한다(이것이 컨텍스트 스위칭이다)
- 디스패치 결과, 복사된 스레드 B의 레지스터 값에 따라 특정 시점부터 실행을 시작한다

CPU 스케줄링 타입

CPU 스케줄링은 실행 중인 스레드를 강제로 중단시키는지에 따라 비선점 스케줄링(non-preemptive scheduling)과 선점 스케줄링(preemptive scheduling)으로 나뉜다

비선점 스케줄링

스레드가 CPU를 할당받아 특정 상황이 될 때까지 강제 중단하지 않고, 스케줄링도 하지 않는 방식

스케줄링이 진행되는 상황
- CPU를 더 이상 사용할 수 없게 된 경우
  - I/O로 인한 Block 상태, sleep()
- 자발적 CPU 양보
  - yield() 시스템 호출
- 스레드 실행 완료
스케줄링 알고리즘 예시
- SRTF(Shortest Remaining Time First)
- Priority 스케줄링(non-preemptive version)

선점 스케줄링

현재 실행중인 스레드를 강제로 중단시켜 준비 리스트로 이동시키고 스케줄링하는 방식

강제 스케줄링이 진행되는 상황
- 타임 슬라이스가 소진되었을 때
  - 비선점 스케줄링은 타임 슬라이스를 사용하지 않음(단순한 모니터링 용도로는 사용될 수 있음)
- 인터럽트나 시스템 호출 종료 시점에서 더 높은 순위의 스레드가 대기 상태에 있을 때
대부분의 운영체제가 사용함
스케줄링 알고리즘 예시
- RR(Round Robin)
- SJF(Shortest Job First)
- Priority(preemptive version)

구분	비선점(Non-Preemptive)	선점(Preemptive)
I/O 인터럽트 발생 후	Ready 상태의 스레드가 있어도 현재 실행중인 스레드가 끝날 때까지 기다림	더 높은 우선순위의 스레드가 있으면 즉시 선점(리스트 전체에서)
시스템 호출 후	현재 스레드가 Block 상태가 되면 스케줄링 발생	현재 스레드가 Block 상태가 되거나, 그 전에도 우선순위가 높은 스레드가 있으면 선점 가능(리스트 전체에서)
타이머 인터럽트	무시(기존 스레드 실행)	타임 슬라이스 초과 시 강제 선점

기아와 에이징

기아(starvation)
- 스레드가 스케줄링 과정에서 선택되지 못한 채 오랜 시간 준비 리스트에 있는 상황
- 스케줄링 알고리즘에 따라 발생하는 이유가 다름
  - 우선순위 알고리즘 : 계속 자신보다 높은 순위의 스레드가 리스트에 들어옴
  - 짧은시간 알고리즘 : 계속 자신보다 실행 시간이 짧은 스레드가 리스트에 들어옴
에이징(aging)
- 기아에 대한 해결책으로 준비 리스트에 오래 머무를수록 스레드의 우선순위를 높여주는 기법
- 오래 기다릴 수는 있지만 언젠가는 가장 높은 순위가 되어 실행될 것이기 때문에 평생 머무르지는 않도록 보장해준다

스케줄링 알고리즘

CPU 스케줄링 알고리즘들은 준비 상태의 스레드를 대상으로 하며, 준비 리스트를 큐라고 부르고 큐에서의 대기시간을 성능으로 비교한다

FCFS(First Come First Served)

큐에 먼저 도착한 스레드를 먼저 스케줄링
비선점 스케줄링
우선순위 없음
기아 발생 X
- 보통의 경우 발생하지 않지만 앞선 스레드에서 무한 루프가 발생하면 멈출 수 없어 기아가 발생할 수 있음
긴 스레드가 실행중이면 그 뒤의 짧은 스레드들이 오래 대기하게 됨

SJF(Shortest Job First)

실행 시간이 가장 짧은 스레드를 먼저 실행
비선점 스케줄링
우선순위 없음
기아 발생 가능
- 짧은 스레드가 계속 도착하면 긴 스레드는 무한 대기
성능적으론 우수하지만 스레드의 실행 시간을 예측할 수 없기에 현실에서 사용할 수 없는 알고리즘

SRTF(Shortest Remaining Time First)

남은 실행 시간이 가장 짧은 스레드를 먼저 실행
선점 스케줄링 (실행중인 프로세스의 남은 시간보다 더 짧은 스레드가 있으면 교체)
우선순위 없음
기아 발생 가능
- 짧은 스레드가 계속 도착하면 긴 스레드는 무한 대기
SJF와 마찬가지로 스레드의 실행 시간을 예측할 수 없기에 현실에서 사용할 수 없는 알고리즘

RR(Round-Robin)

타임 슬라이스를 주기로 스레드를 교체, 큐에는 스레드의 도착 순서대로 삽입되어 있음
선점 스케줄링
우선순위 없음
기아 발생 X
구현이 쉽지만 잦은 스케줄링 및 컨텍스트 스위칭으로 인한 시간 소요가 크다

Priority

큐에서 가장 높은 우선순위의 스레드를 선택(삽입 시 정렬하여 가장 앞에 오도록 함)
선점/비선점 모두 가능
스레드마다 고정된 우선순위 존재
기아 발생 가능
- 지속적으로 높은 우선순위의 스레드가 도착하면 낮은 우선순위의 스레드는 무한 대기
고정 우선순위를 가지는 실시간 시스템에서 주로 사용됨

MLQ(Multi-level Queue)

각각 다른 레벨을 가진 n개의 큐에 그에 맞는 스레드들을 도착한 순서대로 삽입
->가장 높은 큐의 맨 앞 스레드부터 선택하여 해당 큐가 비어 있으면 다음 레벨 큐에서 선택
선점/비선점 모두 가능
n개의 고정 우선순위
기아 발생 가능
- 높은 순위의 큐에만 스레드가 계속 도착하면 낮은 순위 큐에 있는 스레드는 무한 대기
스레드 별 우선순위가 필요한 시스템에서 사용됨

MLFQ(Multi-level Feedback Queue)

다른 레벨을 가진 n개의 큐를 두고, 스레드는 우선순위 없이 높은 레벨 큐부터 차례대로 삽입
-> 큐에 추가로 별도의 스케줄링 알고리즘으 적용할 수 있다(일반적으로 RR, 레벨에 비례하게 타임 슬라이스를 설정한다)
-> 높은 순위 큐에 있는 스레드부터 실행되며 CPU burst가 끝나기전에 타임 슬라이스를 넘어가면 강제 중단되어 아래 레벨 큐로 이동된다(타임 슬라이스 전에 CPU burst가 끝나거나 I/O 작업이 요청되면 종료 후 동일한 큐에 다시 삽입된다)
선점 스케줄링
우선순위 없음
기아 발생 X
- 에이징 기법을 통해 일정 시간 이상 낮은 순위 큐에서 대기한 스레드를 한 단계 높은 큐로 이동시키지만, 큐 개수가 많거나 높은 레벨의 큐에 스레드들이 많다면 무한 대기는 아니더라도 오래 걸릴 수 는 있다
CPU burst가 짧거나 I/O가 빈번한 스레드, 혹은 대화식 스레드에게 높은 우선순위를 주어 응답 시간을 빨리하고 평균 대기 시간을 줄인다
큐의 개수, 타임 슬라이스 크기 등 파라미터 조절로 유연한 구현이 가능하지만 알고리즘의 복잡성으로 CPU의 오버헤드가 증가된다

멀티 코어 CPU에서의 스케줄링

CPU는 코어마다 독립적으로 스레드를 실행할 수 있다 싱글 코어 CPU에서 사용한 스케줄링 기법을 멀티 코어 CPU에 그대로 사용하면 문제가 발생한다

1 . 컨텍스트 스위칭 후 오버헤드 증가

코어마다 독립적으로 존재하는 캐시 메모리에 스위칭되는 스레드가 이전에 실행된 적이 있는지에 따라 캐시에 코드와 데이터를 적재하기 위한 시간이 소요된다
코어 친화성으로 해결(CPU affinity, CPU pinning)
- 스레드들을 특정한 동일 코어에서만 계속 실행되도록 스케줄링 하는 것
- 실행 중에 특정 이유로 중단 및 스위칭되어 스레드 큐로 들어가야 할 때 동일한 코어의 스레드 큐로 삽입된다 2 . 코어별 부하 불균형
각 코어들이 무작위로 스레드를 스케줄링 한다면 코어마다 처리하는 스레드의 양이 달라져 부하 불균형이 발생할 수 있다
부하 균등화 기법(load balancing)으로 해결
- 푸시 마이그레이션(push migration) 기법
  - 시스템에 스레드 큐를 감시하는 별도의 감시 스레드를 두고, 스레드 큐가 매우 짧거나 실행할 스레드가 없는 코어가 생기면 다른 스레드 큐로부터 스레드를 강제로 가져와 삽입하는 기법
- 풀 마이그레이션(pull migration) 기법
  - 코어가 처리할 스레드가 없어지면 다른 코어의 스레드 큐에서 스레드를 가져와 자신의 스레드 큐에 넣고 실행하는 기법