[23-01/운영체제] CPU 스케줄링

1. CPU 스케줄링 개요

운영체제에서 일어나는 다양한 스케줄링

■ 스케줄링은 왜 필요할까?

- 자원에 대한 경쟁이 있는 곳에서 경쟁자 중 하나 선택

    - 자원 : CPU, 디스크, 프린트, 파일, 데이터베이스 등 IO, CPU

- 컴퓨터 시스템 여러 곳에서 발생

 

■ 컴퓨터 시스템 내 다양한 스케줄링

• 작업(job) 스케줄링
  • 배치시스템에서
  • 대기중인 배치 작업(Job) 중 메모리에 적재할 작업 결정
• CPU 스케줄링 - 프로세스 스케줄링
  • 프로세스/스레드 중에 하나를 선택하여 CPU 할당
  • 오늘날 CPU 스케줄링은 커널 수준의 스레드 스케줄링
• 디스크 스케줄링
  • 디스크 장치 내에서
  • 디스크 입출력 요청 중 하나 선택
• 프린터 스케줄링
  • 프린팅 작업 중 하나 선택하여 프린터 할당

다중프로그래밍과 스케줄링

■ 다중프로그래밍의 도입 목적 리뷰

- CPU 유휴 시간 줄여 CPU 활용률 향상 목적

- 프로세스가 I/O를 요청하면 다른 프로세스에게 CPU 할당

memo : 프로세스 스케줄러 : 프로세스를 준비(Ready) 상태 -> 실행(Run)상태로 전이

 

■ 다중프로그래밍과 함께 2가지 스케줄링 도입

• 작업 스케줄링 (Job Scheduling)
  • 디스크 장치로부터 메모리에 올릴 작업 선택 (초기 다중프로그래밍 시스템에서)
  • 처음에 혹은 프로세스가 종료할 때마다
• CPU 스케줄링 (CPU Scheduling)
  • 메모리에 적재된 작업 중 CPU에 실행시킬 프로세스 선택

 

CPU burst와 I/O burst

memo : 간단하게 표현하면 작업

■ 프로그램의 실행 특성

- CPU 연산 작업과 I/O 작업 (화면 출력, 키보드, 입력, 파일 입출력 등)이 순차적으로 섞여 있음

- CPU burst - I/O burst - CPU burst - I/O burst의 반복 ...

 

● CPU burst

- 프로그램 실행 중 CPU 연산(계산 작업)이 연속적으로 실행되는 상황

● I/O burst

- 프로그램 실행 중 I/O 장치의 입출력이 이루어지는 상황

 

memo : CPU 하는일 없어보이지만 그렇지 않음

 

CPU 스케줄링의 정의와 목표

■ 정의

- 실행 준비 상태(Ready)의 스레드 중 하나를 선택하는 과정

 

■ 기본 목표

- CPU 활용률 향상 -> 컴퓨터 시스템 처리율 향상

 

-> 컴퓨터 시스템에 따라 CPU 스케줄링의 목표가 다를 수 있음

 

CPU 스케줄링의 기준 (Criteria)

■ 스케줄링 알고리즘의 다양한 목표와 평가 기준 - 목적 ★

① CPU 활용률 (CPU Utilization) 향상 ↑

- 전체 시간 중 CPU의 사용 시간 비율, 운영체제 입장

 

② 처리율 (Throughput) 향상 ↑

- 단위 시간당 처리하는 스레드 개수, 운영체제 입장

 

③ 공평성 (Fairness) 경과 시간 예측

- CPU를 스레드들에게 공평하게 배분, 사용자 입장

- 시분할로 스케줄링

- 무한정 대기하는 기아 스레드가 생기지 않도록 스케줄 (요즘은 그렇지 않음. 옛날 이야기임)

 

④ 응답시간 (Response Time) ↓

- 대화식 사용자의 경우, 사용자에 대한 응답 시간, 사용자 입장

 

⑤ 대기시간 (Waiting Time) ↓

- 스레드가 준비 큐에서 머무르는 시간, 운영체제와 사용자 입장

 

⑥ 소요 시간 (Turnaround Time) ↓ - 반환시간

- 프로세스(스레드)가 컴퓨터 시스템에 도착한 후(혹은 생성된 후) 완료될 때까지 걸린 시간, 사용자 입장

 

+ 오버헤드 최소화

 

+ memo

선점형 : 하나의 프로세스가 다른 프로세스 대신에 프로세서를 차지할 수 있음.

비선점형 : 하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 사용할 수 없음. (작업시간 예측 가능)

ex) 1명씩 이용 가능한 연습실이 있음. 선점형이면 들어가있는 사람을 끄집어낼 수 있지만, 비선점형은 불가능함

 

타임 슬라이스

■ 대부분의 운영체제

- 하나의 스레드가 너무 오래 CPU를 사용하도록 허용되지 않음

 

■ 타임 슬라이스와 스케줄링

● 타임 슬라이스 (Time Slice)

- 스케줄된 스레드에게 한 번 할당하는 CPU 시간

    - 스레드가 CPU 사용을 보장받는 시간

- 커널이 스케줄을 단행하는 주기 시간 (동일한 시간에 여러 작업 가능한 것처럼 보임)

    - 타이머 인터럽트의 도움을 받아 타임 슬라이스 단위로 CPU 스케줄링

    - 현재 실행중인 스레드 강제 중단(Preemption), 준비 리스트에 삽입

- 타임 퀸텀(Time Quantum), 타임 슬롯(Time Slot)이라고도 함

 

2. CPU 스케줄링 기본

CPU 스케줄링이 실행되는 4가지 상황

■ CPU 스케줄링은 언제 시행될까? 계속 발생 - 켜놓고만 있어도 발생함

1. 스레드가 시스템 호출 끝에 I/O를 요청하여 블록 될 때
- 스레드를 블록 상태로 만들고 스케줄링
- (CPU 활용률 향상 목적)

2. 스레드가 자발적으로 CPU를 반환할 때
- yield() 시스템 호출 등을 통해 스레드가 자발적으로 CPU 반환
- 커널은 현재 스레드를 준비 리스트에 넣고, 새로운 스레드 선택
- (CPU의 자발적 양보)

3. 스레드의 타임 슬라이스가 소진되어 타이머 인터럽트 발생
- (균등한 CPU 분배 목적)

4. 더 높은 순위의 스레드가 요청한 입출력 작업 완료, 인터럽트 발생
- 현재 스레드를 강제 중단(preemption)시켜 준비 리스트에 넣고
- 높은 순위의 스레드를 깨워 스케줄링
- (우선순위를 지키기 위한 목적)

 

CPU 스케줄링과 디스패치 (Dispatch)

■ CPU 스케줄링 코드의 위치와 실행 시점

- 스케줄링 담당하는 커널 스레드나 프로세스가 있는가? 없음

1. 스케줄링 코드는 어디에 위치? 커널 내 함수

- 스케줄링 코드는 커널 코드의 일부로서 호출되어야 실행되는 함수 형태

- 독립적으로 실행되는 프로세스나 스레드 아님

2. 스케줄링 코드가 실행되는 시점

- 시스템 호출이나 인터럽트 서비스 루틴이 끝나는 마지막 단계에서 실행

 

■ 디스패처(dispatcher) 코드 실행

● 디스패처 코드

- 컨텍스트 스위칭을 실행하는 커널 코드

- 스케줄러에 의해 선택된 스레드를 CPU가 실행하도록 하는 작업

- 커널 모드에서 사용자 모드로 전환

 

-> 스케줄러와 디스패처 모두 실행 시간이 짧도록 작성

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

■ 실행중인 스레드의 강제 중단 여부에 따른 CPU 스케줄링

● 비선점 스케줄링(Non-Preemptive Scheduling) 타입

- 현재 실행중인 스레드를 강제로 중단시키지 않는 타입

    - 실행을 시작하면, 완료되거나 CPU를 더 이상 사용할 수 없는 상황이 될 때까지 강제 중단시키지 않고 스케줄링도 하지 않는 방식

- 스케줄링 시점

    - CPU를 더 이상 사용할 수 없게 된 경우 : I/O로 인한 블록 상태, sleep 등

    - 자발적으로 CPU 양보할 때

    - 종료할 때

memo : 프로세스 응답시간 예측 용이함. 대화형 시스템에 부적합 (빠른 응답 필요한 것)

 

● 선점 스케줄링(preemptive Scheduling) 타입

- 현재 실행중인 스레드를 강제 중단시키고 다른 스레드 선택

- 스케줄링 시점

    - 타임슬라이스가 소진되어 타이머 인터럽트가 발생될 때

    - 인터럽트나 시스템 호출 종료 시점에서, 더 높은 순위의 스레드가 준비 상태일 때

memo : 대화형 시스템에 적합 - 시분할 시스템

 

 

■ 오늘날

- 일부 실시간 임베디드 시스템 운영체제 - 비선점 스케줄링 (작업이 많지 않음. 아두이노 - 절차 지향)

- 그 외 대부분의 운영체제 - 선점 스케줄링

 

기아와 에이징

■ 기아 (Starvation) - 노화현상

- 스레드가 스케줄링에서 선택되지 못한 채 오랜 동안 준비 리스트에 있는 상황

- 스케줄링 알고리즘 설계 시 기아 발생을 면밀히 평가

    - 기아가 발생하지 않도록 설계하는 것이 바람직함

● 사례

• 우선순위를 기반으로 하는 시스템에서, 더 높은 우선순위의 스레드가 계속 시스템에 들어오는 경우
• 짧은 스레드를 우선 실행시키는 시스템에서, 자신보다 짧은 스레드가 계속 도착하는 경우

■ 에이징 (Aging)

- 기아의 해결책

- 스레드가 준비 리스트에 머무르는 시간에 비례하여 스케줄링 순위를 높이는 기법

    - 오래 기다릴 수는 있지만 언젠가는 가장 높은 순위에 도달하는 것 보장

 

3. 다양한 CPU 스케줄링 알고리즘

기본적인 CPU 스케줄링 알고리즘들

1. FCFS (First Come First Served) (비선점 스케줄링)

- 도착한 순서대로 처리

memo : 제일 쉬움. 자료구조로 치면 FIFO

 

2. Shortest Job First (비선점 스케줄링)

- 가장 짧은 스레드 우선 처리

 

3. Shortest Remaining Time First (선점 스케줄링) SRT

- 남은 시간이 짧은 스레드가 준비 큐에 들어오면 이를 우선 처리

 

4. Round-Robin (선점 스케줄링) ★

- 스레드들을 돌아가면서 할당된 시간(타임 슬라이스)만큼 실행

 

5. Priority Scheduling (선점/비선점 스케줄링 둘 다 구현 가능) X중요하지 않음

- 우선 순위를 기반으로 하는 스케줄링. 가장 높은 순위의 스레드 먼저 실행

 

6. Multilevel queue scheduling (선점/비선점 스케줄링 둘 다 구현 가능) ★

- 스레드와 큐 모두 n개의 우선순위 레벨로 할당, 스레드는 자신의 레벨과 동일한 큐에 삽입

- 높은 순위의 큐에서 스레드 스케줄링, 높은 순위의 큐가 빌 때 아래 순위의 큐에서 스케줄링

- 스레드는 다른 큐로 이동하지 못함

- ex) background process, Foreground process

 

7. Multilevel feedback queue scheduling (선점/비선점 스케줄링 둘 다 구현 가능) ★

- 큐만 n개의 우선순위 레벨을 둠. 스레드는 동일한 우선순위.

- 스레드는 제일 높은 순위의 큐에 진입하고 큐타임슬라이스가 다하면 아래 레벨의 큐로 이동

 

FCFS

■ 알고리즘

- 선입선처리 : 먼저 도착한(큐의 맨 앞에 있는) 스레드 먼저 스케줄링

■ 스케줄링 파라미터 : 스레드 별 큐 도착 시간

■ 스케줄링 타입 : 비선점 스케줄링★

■ 스레드 우선순위 : 없음

■ 기아 : 발생하지 않음 ( 스레드가 오류로 인해 무한 루프를 실행한다면, 뒤 스레드 기아 발생

■ 성능 이슈

- 처리율 낮음

- 호위 효과 (Convoy Effect) 발생

    - 긴 스레드가 CPU를 오래 사용하면, 늦게 도착한 짧은 스레드 오래 대기

SJF (Shortest Job First)

■ 알고리즘

- 최단 작업 우선 스케줄링

- 실행 시간(예상 실행 시간)이 가장 짧은 스레드 선택

- 스레드가 도착할 때, 실행시간이 짧은 순으로 큐 삽입, 큐의 맨 앞에 있는 스레드 선택

■ 스케줄링 파라미터 : 스레드 별 예상 실행시간 (스레드의 실행 시간 예측 가능)

■ 스케줄링 타입 : 비선점 스케줄링

■ 스레드 우선순위 : 없음

■ 기아 : 발생 가능

- 짧은 스레드가 계속 도착하면, 긴 스레드는 실행 기회를 언제 얻을 지 예측할 수 없음

■ 성능 이슈

- 가장 짧은 스레드가 먼저 실행되므로 평균 대기 시간 최소화

 

SRTF (Shortest Remaining Time First)

■ 알고리즘

- 최소 잔여 시간 우선 스케줄링

- 남은 실행 시간이 가장 짧은 스레드 선택

- SJF의 선점 스케줄링 버전

    - 한 스레드가 끝나거나 실행 시간이 더 짧은 스레드가 도착할 때, 남은 실행 시간이 가장 짧은 스레드 선택

    - 실행 시간에 짧은 순으로 스레드들을 큐에 삽입 -> 큐 맨 앞에 있는 스레드 선택

■ 스케줄링 파라미터 : 스레드 별 예상 실행 시간과 남은 실행 시간 값

■ 스케줄링 타입 : 선점 스케줄링

■ 스레드 우선순위 : 없음

■ 기아 : 발생 가능

- 짧은 스레드가 계속 도착하면, 긴 스레드는 실행 기회를 언제 얻을 지 모름

■ 성능 이슈

- 실행 시간이 가장 짧은 스레드가 먼저 실행되므로 평균 대기 시간 최소화

memo : ★오버헤드 발생

 

RR (Round-Robin) ★

■ 알고리즘

- 스레드들에게 공평한 실행 기회를 주기 위함

- 큐에 대기중인 스레드들을 타임 슬라이스 주기로 돌아가면서 선택

- 스레드는 도착하는 순서대로 큐에 진입

- 스레드가 타임 슬라이스를 소진하면 큐 끝으로 이동

■ 스케줄링 파라미터 : 타임 슬라이스

■ 스케줄링 타입 : 선점 스케줄링

■ 스레드 우선순위 : 없음

■ 기아 : 없음

- 스레드의 우선 순위가 없고, 타임 슬라이스가 정해져 있어, 일정 시간 후에도 스레드는 반드시 실행

■ 성능 이슈

- 공평하고, 기아 현상없고, 구현이 쉬움

- 잦은 스케줄링으로 전체 스케줄링 오버헤드 큼. 특히 타임 슬라이스가 작을 때 더욱 큼

- 균형된 처리율 : 타임슬라이스가 크면 FCFS에 가까움, 적으면  SJF / SRTF에 가까움

    - 늦게 도착한 짧은 스레드는 FCFS보다 빨리 완료하고, 긴 스레드는 SJF보다 빨리 완료됨

memo : 시분할 시스템을 위해 개발. FIFO 기법을 선점형으로 변경

 

■ 타임 슬라이스 = 2ms일때

 

■ 타임 슬라이스 = 1ms일때

 

Priority 스케줄링

■ 알고리즘

- 우선순위에 따라 스레드를 실행시키기 위한 목적

- 가장 높은 순위의 스레드 선택

    - 현재 스레드가 종료되거나 더 높은 순위의 스레드가 도착할 때, 가장 높은 순위의 스레드 선택

- 모든 스레드에 고정 우선순위 할당, 종료 때까지 바뀌지 않음
- 도착하는 스레드는 우선순위 순으로 큐에 삽입

■ 스케줄링 파라미터 : 스레드 별 고정 우선순위

■ 스케줄링 타입 : 선점 스케줄링/비선점 스케줄링

- 선점 스케줄링 : 더 높은 순위의 스레드가 도착할 때 현재 스레드 강제 중단하고 스케줄링
- 비선점 스케줄링 : 현재 실행 중인 스레드가 종료될 때 스케줄링

■ 스레드 우선순위 : 없음

■ 기아 : 발생 가능

- 높은 순위의 스레드가 계속 도착하는 경우, 실행 기회를 언제 얻을 지 예상할 수 없음
- 큐 대기 시간에 비례하여 일시적으로 우선순위를 높이는 에이징 방법으로 해결 가능

■ 성능 이슈

- 높은 우선순위의 스레드일수록 대기 혹은 응답시간 짧음

■ 특징

- 스레드별 고정 우선순위를 가지는 실시간 시스템에서 사용

 

MLQ (Multi-Level Queue) 스케줄링

■ 설계 의도

- 스레드들을 n개의 우선순위 레벨로 구분, 레벨이 높은 스레드를 우선 처리하는 목적

■ 알고리즘

- 고정된 n개의 큐 사용, 각 큐에 고정 우선순위 할당

- 스레드들의 우선순위도 n개의 레벨로 분류

- 각 큐는 나름대로의 기법으로 스케줄링

- 스레드는 도착 시 우선순위에 따라 해당 레벨 큐에 삽입. 다른 큐로 이동할 수 없음

- 가장 높은 순위의 큐가 빌 때, 그 다음 순위의 큐에서 스케줄링

■ 스케줄링 파라미터 : 스레드의 고정 우선순위

■ 스케줄링 타입 : 비선점/선점 모두 가능

- 비선점 스케줄링 : 현재 실행중인 스레드가 종료할 때 스케줄링

- 선점 스케줄링 : 높은 레벨의 큐에 스레드가 도착하면 중단하고 높은 레벨 큐에서 스케줄링

■ 스레드 우선순위 :  있음

■ 기아 : 발생 가능

- 높은 순위의 스레드가 계속 도착하는 경우 실행 기회를 언제 얻을 지 예상할 수 없음

■ 성능 이슈와 활용 사례

- 스레드의 고정 순위를 가진 시스템에서 활용

 

MLFQ (Multi-Level Feedback Queue) 스케줄링

■ 설계 의도

- 1962년에 개발된 알고리즘

- 기아를 없애기 위해 여러 레벨의 큐 사이에 스레드 이동 가능하도록 설계

- 짧은 스레드와 I/O가 많은 스레드, 대화식 스레드의 우선 처리. 스레드 평균대기시간 줄임

■ n개의 레벨 큐

- n개의 고정 큐. 큐마다 서로 다른 스케줄링 알고리즘

- 큐는 준비 상태(Ready 상태)의 스레드가 저장된 큐

- 큐마다 스레드가 머무를 수 있는 큐 타임슬라이스 있음. 낮은 레벨의 큐일수록 더 긴 타임 슬라이스

- I/O 집중 스레드(대화식 스레드)는 높은 순위의 큐에 있을 가능성 높음

■ 알고리즘

- 스레드는 도착 시 최상위 레벨 큐에 삽입

- 가장 높은 레벨 큐에서 스레드 선택. 비어있으면 그 아래의 큐에서 스레드 선택

- 스레드의 CPU-burst가 큐 타임 슬라이스를 초과하면 강제로 아래 큐로 이동시킴

- 스레드가 자발적으로 중단한 경우, 현재 큐 끝에 삽입

- 스레드가 I/O로 실행이 중단된 경우, I/O가 끝나면 동일 레벨 큐 끝에 삽입

- 큐에 있는 시간이 오래되면 기아를 막기 위해 하나 위 레벨 큐로 이동

- 최하위 레벨 큐는 주로 FCFS나 긴 타임 슬라이스의 RR로 스케줄.

■ 스케줄링 파라미터 : 각 큐의 큐 타임슬라이스

■ 스케줄링 타입 : 선점 스케줄링

■ 스레드 우선순위 :  없음

■ 기아 : 발생하지 않음, 큐에 대기하는 시간 오래되면, 더 높은 레벨의 큐로 이동시킴(에이징기법)

- 높은 순위의 스레드가 계속 도착하는 경우 실행 기회를 언제 얻을 지 예상할 수 없음

■ 성능 이슈

- 짧거나 입출력이 빈번한 스레드, 혹은 대화식 스레드를 높은 레벨의 큐에서 빨리 실행 -> CPU 활용률이 높음

 

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

멀티 코어 시스템의 구조

 

멀티 코어 시스템에서의 멀티스레딩

코어 당 스레드 큐