Post

[운영체제] 5장 CPU 스케줄링

Posted
By Keem
16 min read

CPU 스케줄링

1. CPU 스케줄링 개요

CPU 스케줄링은 준비 상태의 스레드 중 하나를 선택하는 스레드 스케줄링이다

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

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

  • 작업(JOB) 스케줄링
    • 대기중인 job 중에 메모리에 적재할 작업 결정
  • CPU 스케줄링
    • 프로세스/스레드 중 에 하나를 선택하여 CPU 할당

※ 디스크 스케줄링 (12장에서 공부) - 디스크 입출력 요청 중 하나 선택

※ 다중 프로그래밍의 도입 목적 - CPU 유휴 시간 줄여 CPU 활용율 향상 목적

CPU스케줄링

1.2 CPU burst와 I/O burst

  • CPU가 코드를 집중적으로 실행하는 상황을 CPU burst라고 부르고 이 시간을 CPU burst 시간이라고 한다. 그리고 I/O 장치에 의해 입출력이 이루어지는 상황을 I/O burst

cpu-ioburst

1.3 cpu 스케줄링의 기본 목표

  • CPU 스케줄링 - Ready 상태 스레드 중 하나 선택하는 과정
    • CPU 활용률 향상 -> 컴퓨터 시스템 처리율 향상

※ 컴퓨터 시스템 마다 목표가 다를 수 있다.

1.4 CPU 스케줄링의 기준(criteria)

  • CPU 활용률 - 가동시간 중 CPU 사용시간의 비율
  • 처리율 - 단위 시간 당 처리한 스레드 수
  • 공평성 - CPU 시간 공평하게 배분하는 것
  • 응답시간 - 대화식 사용자, 사용자에 대한 응답시간
  • 대기 시간 - Reday 큐에서 대기하는 시간 (CPU 할당까지)
  • 소요 시간 - 시스템에 진입하고 완료까지 걸린 시간
  • 시스템 정책 우선 - 특별한 목적 달성을 위함
    • 실시간 시스템 - 스레드가 완료 시한내에 이루어지도록
    • 급여 시스템 - 안전을 관리하는 스레드 우선
  • 자원 활용율 - 자원의 활용률 ↑

1 .5 CPU 스케줄링과 타임 슬라이스

  • 하나의 스레드가 너무 오래 CPU를 사용하지 않도록

타임 슬라이스

  • 스케줄된 스레드에게 한 번 할당하는 CPU 시간
  • 커널이 스케줄을 단행하는 주기 시간
  • 타임 퀀텀, 타임 슬롯이라고도 함

2. CPU 스케줄링 기본

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

2.1.1 시스템 호출 끝에 I/O 요청하여 Blocked될 때 - 시스템 호출
  • Blocked 상태로 만들고 스케줄링
  • CPU 활용률 향상 목적
2.1.2 스레드가 자발적으로 CPU 반환할 때 - 시스템 호출
  • yield() 시스템 호출 등을 통해 자발적으로 CPU 반환
  • Running -> Ready 후 스케줄링
  • CPU 자발적 양보
2.1.3 타임 슬라이스가 소진되어 타이머 인터럽트 발생
  • 균등한 CPU 분배의 목적
2.1.4 더 높은 스레드가 요청한 입출력 작업 완료 - 인터럽트
  • 현재 스레드 강제 중단시키고 준비 리스트
  • 높은 순위의 스레드 깨워서 스케줄링
  • 우선순위 지키기 위한 목적

2.2 CPU 스케줄링과 디스패치（dispatch）

dispatch

※ 스케줄러 코드는 커널에 함수 형태로 존재로 시스템 호출/ISR 끝나는 마지막 단계에서 실행

  • 디스패처 코드 - 컨텍스트 스위칭 실행
    • 스케줄러 코드에 의해 선택된 스레드를 CPU가 실행하도록 하는 커널 코드의 한 부분이다.

디스패처 코드나 스케줄러 코드는 실행 시간이 가능한 짧도록 작성되어야 한다.

​ -> 스케줄러 오버헤드

2.3 스케줄링 타입 : 선점 스케줄링과 비선점 스케줄링

비선점 스케줄링 : 현재 실행중인 스레드 강제 중단 X

  • CPU 더 이상 사용 불가 (I/O Block, or Sleep)
  • 자발적으로 CPU 양보
  • 종료할 때

선점 스케줄링 : 현재 실행중인 스레드 강제 중단 O

  • 타임 슬라이스 소진으로 인한 인터럽트
  • 인터럽트 OR 시스템 호출 시 더 높은 순위 스레드가 READY 상태일 때

※ 범용 운영체제에서 대부분 선점 스케줄링

preemptive

2.4 기아와 에이징

기아 - Ready 상태에서 오랜 동안 선택되지 못한 스레드
  • 우선순위 기반 시스템에서
  • 짧은 스레드 우선 실행에서

기아 발생을 방지하는 것이 바람직함

에이징 - 기아의 해결책
  • Ready 리스트에 머무는 시간에 비례하여 우선 순위 ↑(실행보장)

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

3.1 FCFS 스케줄링

  • 알고리즘 : 먼저 도착한 스레드 먼저 스케줄링
  • 스케줄링 파라미터 : 스레드 도착 시간
  • 스케줄링 타입 : 비선점 스케줄링
  • 스레드 우선 순위 : 없음
  • 기아 : 발생하지 않음
  • 성능 - 처리율 낮음
    • 호위 효과 - 늦게 도착한 스레드 오래 대기

fcfs

※ 대기 시간이 짧다 -> 각 스레드의 응답시간이 짧다

3.2 SJF(Shortest Job First) 스케줄링

  • 알고리즘 : 최단 작업 우선 스케줄링
    • 실행 시간 가장 짧은 스레드
    • 도착 시 짧은 순으로 큐에 삽입
  • 스케줄링 파라미터 : 스레드 별 예상 실행 시간
    • 실행 시간 추정 불가능
  • 스케줄링 타입 : 비선점 스케줄링
  • 스레드 우선 순위 : 없음
  • 기아 : 발생 가능
    • 짧은 스레드 계속 도착하면 실행 보장 X

  • 성능 이슈 : 짧은 스레드 먼저 실행 -> 대기 시간 최소화

  • 문제점 : 실행 시간 예측 불가 -> 사용 안함

sjf

3.3 SRTF(Shortest Remaining Time First) 스케줄링

  • 알고리즘 : 최소 잔여 시간 우선 스케줄링
    • 남은 시간이 짧은 스레드 우선 실행 (SJF의 선점 스케줄링 버전)
  • 스케줄링 파라미터 : 스레드 별 예상 실행 시간 (알 수 없음)
  • 스케줄링 타입 : 선점 스케줄링 (강제 중단 O)
  • 스케줄링 우선순위 : 없음
  • 기아 : 발생 가능 - (SJF의 문제와 일맥상통)
  • 성능 이슈 : 실행 시간 기준으로 하여 평균 대기 시간 최소화

SRTF

3.4 RR(Round-Robin) 스케줄링

  • 알고리즘 : 공평한 실행 기회를 주기 위해
    • 큐에 대기중인 스레드들을 타임 슬라이스 주기로
    • 타임 슬라이스 소진 시 큐 마지막으로
  • 스케줄링 파라미터 : 타임 슬라이스
  • 스케줄링 타입 : 선점 스케줄링
  • 스케줄링 우선순위 : 없음
  • 기아 : 없음 (슬라이스 정해져 있어 실행 보장)
  • 성능 이슈 : 공평, 기아 x, 구현 쉬움
    • 스케줄링이 잦음 - 스케줄링 오버헤드 (스케줄링, 디스패치) -> 타임 슬라이스 작으면 극대화
    • 균형된 처리율 : 타임 슬라이스 크면 - FCFS / 작으면 - SJF, SRTF

※ 늦게 도착한 짧은 스레드 FCFS보다 빨리 완료 / 긴 스레드는 SJF보다 빨리 완료

RR1RR2
• 평균 대기 시간: (3 + 4 + 2 + 3)/4 = 3ms
• 스케줄링 횟수: 6번
• 컨텍스트 스위칭 횟수: 5번		• 평균 대기 시간: (5 + 4 + 1 + 3)/4 = 13/4 = 3.25ms
• 스케줄링 횟수: 10번
• 컨텍스트 스위칭 횟수: 9번

※ 대기 시간 + (스케줄링 + 컨텍스트 스위칭 시간)

3.5 Priority 스케줄링

  • 알고리즘 : 우선 순위에 따라 스레드 실행
    • 모든 스레드에 고정 우선순위 할당
  • 스케줄링 파라미터 : 스레드 별 고정 우선 순위
  • 스케줄링 타입 : 선점/비선점 스케줄링
    • 선점 스케줄링 : 더 높은 순위의 스레드 도착 시 현재 스레드 강제 종료
    • 비선점 선점 스케줄링 : 현재 실행 중인 스레드 종료 시 스케줄링
  • 스케줄링 우선순위 : 있음
  • 기아 : 발생 가능
    • 높은 우선 순위 계속 도착 시
    • 에이징 기법으로 해결 가능
  • 성능 이슈 - 우선 순위 ↑ 대기, 응답 시간 ↓
  • 특징 - 스레드 별 고정 우선 순위 가지는 실시간 운영체제에서 사용

3.6 MLQ (Multi-level Queue) 스케줄링

mlq

  • 알고리즘 :
    • 고정된 n 개의 큐에 우선 순위 별로 분류하고 스케줄링
    • 다른 큐로 옮길 수 없으며, 높은 우선 순위 큐가 비면 다음 우선 순위 큐에서 스케줄링
  • 스케줄링 파라미터 : 스레드의 고정 우선 순위
  • 스케줄링 타입 : 선점/비선점 스케줄링
  • 스케줄링 우선순위 : 있음
  • 기아 : 발생 가능
    • 높은 우선 순위 큐가 먼저 스케줄링 되기 때문에
  • 성능 이슈 : 스레드의 고정 순위를 가진 시스템에서 활용
    • 전체 스레드를 백그라운드, 포그라운드 스레드의 2개의 그룹으로 구성
    • 시스템 스레드, 대화식 스레드, 배치 스레드 등 3개의 레벨로 나누고 …

3.7 MLFQ(Multi-level Feedback Queue) 스케줄링

MLFQ

  • 설계 의도 : MLQ의 기아 없애기 위해 레벨 큐 스레드 이동 가능하도록
    • 짧은 스레드, I/O 많은 스레드, 대화식 스레드 우선 처리 -> 평균 대기 시간 줄임
  • 알고리즘 : (I/O Burst(대화식) 높은 우선 순위 가지게 됨)
    • 도착하면 가장 높은 레벨 큐에 삽입
    • 가장 높은 큐에서부터 실행 -> 타임 슬라이스 넘으면 Low Level Queue로
    • yeild or interrupt -> 동일 큐로 다시 삽입
    • Low level Queue에서 대기 ↑ -> Higher Level Queue로 이동
    • 최하위는 FCFS or Long Time Slice Round Robin
  • 스케줄링 파라미터 : 각 큐의 큐 타임 슬라이스
  • 스케줄링 타입 : 선점 스케줄링
  • 스케줄링 우선순위 : 없음
  • 기아 : 발생하지 않음 (에이징)
  • 성능 이슈 : 짧거나 I/O Burst 빨리 실행 -> CPU 활용률 높음
mlfq1
T1의 대기 시간=3 + 2 = 5ms
T2의 대기 시간=1 + 6 + 6 = 13ms
T3의 대기 시간=3 + 4 + 6 = 13ms
평균 대기 시간=(5ms + 13ms + 13ms)/3 = 31ms/3 = 10.3ms

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

4.1 멀티코어 CPU와 병렬처리

| multicore | multithreading | | :———————————————————-: | :———————————————————-: |

4.2 멀티 코어 시스템에서 CPU 스케줄링과 작업 분배

실글 코어 CPU 스케줄링 기법을 멀티 코어 CPU에 사용하면

  • 컨텍스트 스위칭 후 오버헤드 증가
  • 코어별 부하 불균형

cpuaffinity

컨텍스트 스위칭 후 오버헤드 - CPU(코어) 친화성으로 해결
  • 스레드를 동일한 코어에서 실행하도록 스케줄링
  • 코어 친화성, CPU 피닝, 캐시 친화성
코어별 부하 불균형 - 부하 균등화 기법으로 해결
  • 푸시 마이그레이션 기법
    • 감시 스레드가 짧거나 빈 큐를 가진 코어에 다른 큐의 스레드 옮김
  • 풀 마이그레이션
    • 처리할 스레드가 없으면 다른 코어의 큐에서 스레드 가져옴
운영체제, 정리
operating system
This post is licensed under CC BY 4.0 by the author.