CPU 스케줄링 개요

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

• 자원에 대한 스케줄링
  - 자원에 대한 경쟁이 있는 곳에는 경쟁자 중 하나 선택
• 컴퓨터 시스템 여러 곳에서 발생

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

• 작업 스케줄링

  • 배치시스템에서 대기 중인 배치 작업 중 메모리에 적재할 작업 결정

• CPU 스케줄링
  - 프로세스/스레드 중에 하나를 선택해서 CPU 할당

  • 오늘날 CPU 스케줄링은 스레드 중 하나를 선택하는 스레드 스케줄링

• 디스크 스케줄링
  - 디스크 장치 내에서 디스크 입출력 요청 중 하나 선택
  

• 프린터 스케줄링
  - 프린팅 작업 중 하나 선택하여 프린터 할당

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

• 다중프로그래밍의 도입 목적
  - CPU 유휴시간 줄이기 -> CPU 활용률 향상
  • 프로세스가 I/O를 요청하면 다른 프로세스에게 CPU 할당
• 다중프로그래밍과 함께 2가지 스케줄링 도입

1) 작업 스케줄링

• 디스크 장치로부터 메모리에 올릴 작업 선택
• 처음에 혹은 프로세스가 종료할 때마다

2) CPU 스케줄링

• 메모리에 적재된 작업 중 CPU에 실행시킬 프로세스 선택

CPU burst 와 I/O burst

• 프로그램의 일반적 실행 특성
  - CPU 연산 작업과 화면 출력, 키보드, 입력, 파일 입출력 등 I/O 작업 섞여 있음
  
• CPU burst
  - 프로그램 실행 중 CPU 연산이 연속적으로 실행되는 상황
  
• I/O burst
  - 프로그램 실행 중 I/O 장치의 입출력이 이루어지는 상황

CPU 스케줄링의 정의와 목표

• 프로그램의 실행의 특징
  - CPU burst -> I/O burst -> CPU burst -> I/O burst ..

  • 연산작업 - 입출력작업 - 연산작업 - 입출력작업

• CPU 스케줄링 : 실행 준비 상태의 스레드 중 하나를 선택하는 과정

• CPU 스케줄링의 기준
  - 컴퓨터 시스템들은 기본 목표 외에 서로 다른 스케줄링 목표를 가질 수 있음
  

• 스케줄링 알고리즘의 다양한 목표와 평가 기준★
  1) CPU 활용률 - 전체 시간 중 CPU의 사용시간 비율 (운영체제 입장)
  2) 처리율 - 단위 시간 당 처리하는 프로세스의 개수 (운영체제 입장)
  3) 공평성 - CPU를 스레드들에게 공평하게 배분 (사용자 입장)
  - 시분할로 스케줄링
  - 무한정 대기하는 기아 스레드가 생기지 않도록 스케줄링
  4) 응답 시간 - 대화식 사용자의 경우, 명령에 응답하는데 걸리는 시간 (사용자 입장)
  5) 대기 시간 - 스레드가 준비 큐에서 머무르는 시간 (운영체제와 사용자 입장)
  6) 소요 시간 - 프로세스(스레드)가 컴퓨터 시스템에 도착한 후 완료될 때까지 걸린 시간 (사용자 입장) - 배치 처리 시스템에서 주된 스케줄링의 기준
  7) 시스템 정책 우선 - 컴퓨터 시스템의 특별한 목적을 달성하기 위한 스케줄링 (운영체제 입장)
  - 예 : 실시간 시스템에서는 스레드가 완료 시한 내에 이루어지도록 하는 정책
  - 예 : 급여 시스템에서는 안전을 관리하는 스레드 우선 정책 등
  8) 자원 활용률

타임 슬라이스

• 대부분 운영체제에서 하나의 스레드가 너무 오래 CPU를 사용하도록 허락하지 않음
• 타임 슬라이스와 스케줄링
  - 스케줄된 스레드에게 한 번 할당하는 CPU 시간
  • 커널이 스케줄을 단행하는 주기 시간
• 타이머 인터럽트의 도움을 받아 타임 슬라이스 단위로 CPU 스케줄링
• 현재 실행 중인 스레드 강제 중단, 준비 리스트에 삽입
  - 타임 퀀텀, 타임 슬롯이라고도 함

CPU 스케줄링 기본

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

1) 스레드가 시스템 호출 끝에 I/O를 요청하여 블록될 때

• 스레드를 블록 상태로 만들고 스케줄링
• CPU의 활용률 향상 목적

2) 스레드가 자발적으로 CPU를 반환할 때

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

3) 스레드의 타임슬라이스가 소진되어 타이머 인터럽트 발생

• 균등한 CPU 분배 목적

4) 더 높은 순위의 스레드가 요청한 입출력 작업 완료, 인터럽트 발생

• 현재 스레드를 강제 중단시켜 준비 리스트에 넣고
• 높은 순위의 스레드를 깨워 스케줄링
• 우선순위를 지키기 위한 목적

CPU 스케줄링과 디스패치

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

• 스케줄링을 담당하는 커널 스레드나 프로세스는 없음

• 스케줄링 코드는 커널 내에 코드 형태로 위치
  - 스케줄링 코드는 커널 코드의 일부
  - 별도로 실행되는 프로세스나 스레드 형태가 아님
  - 커널은 마치 응용프로그램을 컴파일(빌드) 하여 완성한 바이너리 모듈 같음, 메모리에 그대로 적재되는 한 덩어리의 바이너리

• 스케줄링 코드가 실행되는 시점
  - 시스템 호출이나 인터럽트 서비스 루틴이 끝나는 마지막 단계에서 실행
  

• 디스패쳐 코드 실행

• 디스패쳐 코드 : 컨택스트 스위칭을 실행하는 커널 코드
  - 스케줄러에 의해 선택된 스레드를 CPU가 실행하도록 하는 작업

  • 커널 모드에서 사용자 모드로 전환
  • 새로 선택된 스레드가 이전에 중단된 곳에서 실행하도록 점프

** 스케줄러와 디스패쳐 모두 실행 시간이 짧도록 작성

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

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

1) 비선점 스케줄링

• 현재 실행 중인 스레드를 강제로 중단시키지 않는 타입
  - 일단 스레드가 CPU를 할당받아 실행을 시작하면, 완료되거나 CPU를 더 이상 사용할 수 없는 상황이 될 때까지 스레드 강제 중단 시키지 않고 스케줄링도 하지 않는 방식
• 스케줄링 시점
  - CPU를 더 이상 사용할 수 없게 된 경우 : I/O 로 인한 블록 상태, sleep 등
  • 자발적으로 CPU를 양보할 때
  • 실행 중 종료할 때

2) 선점 스케줄링

• 현재 실행 중인 스레드를 강제 중단 시키고 다른 스레드 선택, CPU 할당
• 스케줄링 시점
  - 타임슬라이스가 소진되어 타이머 인터럽트가 발생될 때
  • 인터럽트나 시스템 호출 종료 시점에서, 더 높은 순위의 스레드가 준비 상태일 때

• 비선점 스케줄링
  - 이미 할당된 자원을 다른 프로세스가 강탈할 수 없음
  - 응답시간의 예측이 편하며, 일괄처리 방식에 적합
  - 단점으로는 덜 중요한 작업이 자원을 할당받으면 중요 작업이 와도 먼저 처리될 수 없음
  - FCFS(FIFO구조 알고리즘), SJF, HRN, 우선순위, 기한부

• 선점 스케줄링
  - 우선순위가 높은 프로세스를 빠르게 처리할 수 있음
  - 어떤 프로세스가 자원을 사용하고 있을 때 우선순위가 더 높은 프로세스가 올 경우 자원을 강탈함
  - 빠른 응답 시간을 요구하는 시스템에서 사용
  - 오버헤드가 크다
  - Round Robin, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백큐

기아와 에이징

1) 기아

• 스레드가 스케줄링에서 선택되지 못한 채 오랫동안 준비리스트에 있는 상황
• 사례
  - 우선순위를 기반으로 하는 시스템에서 더 높은 순위의 스레드가 계속 시스템에 들어오는 경우
  - 짧은 스레드를 우선 실행시키는 시스템에서, 자신보다 짧은 스레드가 계속 도착하는 경우
  - 스케줄링 알고리즘 설계 시 기아발생을 면밀히 평가
  • 기아가 발생하지 않도록 설계하는 것이 바람직함

2) 에이징

• 기아의 해결책
• 스레드가 준비리스트에 머무는 시간에 비례하여 스케줄링 순위를 높이는 기법
  - 오래 기다릴 수는 있지만 언젠가는 가장 높은 순위에 도달하는 것을 보장

CPU 스케줄링 알고리즘

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

1) FCFS(First come First served) - 비선점 스케줄링

• 도착한 순서대로 스레드를 준비 큐에 넣고 도착한 순서대로 처리

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

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

3) Shortest remaining time first - 선점 스케줄링

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

4) Round - robin - preemptive

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

5) Priority Scheduling - 선점/비선점 스케줄링 둘 다 구현 가능

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

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

• 스레드와 큐 모두 n개의 우선순위 레벨로 할당, 스레드는 자신의 레벨과 동일한 큐에 삽입
• 높은 순위의 큐에서 스레드 스케줄링, 높은 순위의 큐가 빌 때 아래 순위의 큐에서 스케줄링
• 스레드는 다른 큐로 이동하지 못함
• 예 : Background process, Foreground process

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

• 큐만 n개의 우선순위 레벨을 둠. 스레드는 레벨이 없이 동일한 우선 순위
• 스레드는 제일 높은 순위의 큐에 진입하고 큐타임슬라이스가 다하면 아래 레벨의 큐로 이동
• 낮은 레벨의 큐에 오래 있으면 높은 레벨의 큐로 이동

[참고]

여러 개의 큐

• 레디 큐를 여러 개로 분할
  -> foreground
  -> background

• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  -> foreground - RR
  -> background - FCFS

• 큐에 대한 스케줄링이 필요

• 포그라운드 큐 : 사용자와 소통 중심
  백그라운드 큐 : 배치 프로그램

FCFS

• 선입선처리 알고리즘
  - 먼저 도착한 스레드 먼저 스케줄링
• 스케줄링 파라미터 : 스레드 별 도착 시간
• 스케줄링 타입 : 비선점 스케줄링
• 스레드 우선 순위 : 없음
• 기아 : 발생하지 않음
  - 스레드가 오류로 인해 무한 루프를 실행한다면 뒤 스레드의 기아 발생
• 성능 이슈
  - 처리율 : 낮음
  - 호위 효과 발생 : 긴 스레드가 CPU를 오래 사용하면, 늦게 도착하면 짧은 소레드는 오래 대기
  

SJF

• 최단작업 우선 스케줄링 알고리즘
  - 예상 실행시간이 가장 짧은 스레드 선택
  - 스레드가 도착할 때, 예상 실행시간이 짧은 순으로 큐 삽입, 큐의 맨 앞에 있는 스레드 선택
  
• 스케줄링 파라미터 : 스레드 별 예상 실행 시간
• 스케줄링 타입 : 비선점 스케줄링
• 스레드 우선 순위 : 없음
• 기아 : 발생 가능
  - 지속적으로 짧은 스레드가 도착하면, 긴 스레드는 언제 실행 기회를 얻을지 예측할 수 없음
• 성능 이슈
  - 짧은 스레드가 먼저 실행되므로 평균 대기 시간 최소화
• 문제점
  - 실행 시간의 예측이 불가능하므로 현실에서는 거의 사용되지 않음
  

SRTF

• 최소 잔여 시간 우선 스케줄링 알고리즘
• 남은 실행 시간이 가장 짧은 스레드 선택
• SJF의 선점 스케줄링 버전
  - 실행시간이 짧은 순으로 스레드들을 큐에 삽입, 한 스레드가 끝나거나 실행시간이 더 짧은 스레드가 도착할 때, 가장 짧은 스레드 선택
  - 큐의 맨 앞에 있는 스레드 선택
• 스케줄링 파라미터 : 스레드 별 예상 실행 시간과 남은 실행 시간 값
  - 이 시간을 아는 것은 불가능. 비현실적
• 스케줄링 타입 : 선점 스케줄링
• 스레드 우선 순위 : 없음
• 기아 : 발생 가능
  - 지속적으로 짧은 스레드가 도착하는 경우 긴 스레드는 언제 실행 기회를 얻을 수 있을지 예상할 수 없음
• 성능 이슈
  - 실행 시간이 짧은 프로세스가 먼저 실행되므로 평균 대기 시간 최소화
• 문제점
  - 실행 시간 예측이 불가능하므로 현실에서는 거의 사용되지 않음
  

RR

• 스레드들에게 공평한 실행 기회를 주기 위해 큐에 대기중인 스레드들을 타임 슬라이스 주기로 돌아가면서 선택하는 알고리즘
• 도착하는 순서대로 스레드들을 큐에 삽입
• 타임 슬라이스가 지나면 큐 끝으로 이동
• 스케줄링 파라미터 : 타임 슬라이스
• 스케줄링 타입 : 선점 스케줄링
• 스레드 우선 순위 : 없음
• 기아 : 없음
  - 스레드의 우선순위가 없고, 타임 슬라이스가 정해져 있어, 일정 시간 후에 스레드는 반드시 실행
• 성능 이슈
  - 공평하고, 기아현상 없고, 구현이 쉬움
  - 잦은 스케줄링으로 전체 스케줄링 오버헤드가 큼. 특히 타임슬라이스가 작을 때 더욱 큼
  - 균형된 처리율 : 타임슬라이스가 크면 FCFS에 가까움, 작으면 SJF/SRTF 에 가까움
  • 늦게 도착한 짧은 프로세는 FCFS보다 빨리 완료되고, 긴 프로세스는 SJF보다 빨리 완료됨

Priority 스케줄링

• 우선순위에 따라 스레드들 실행시키기 위한 목적인 알고리즘
• 가장 높은 순위의 스레드 선택
  - 현재 스레드가 종료되거나 더 높은 순위의 스레드가 도착할 때, 가장 높은 순위의 스레드 선택
  - 모든 스레드에 고정 우선 순위 할당, 종료 때까지 바뀌지 않음
  - 도착하는 스레드는 우선순위 순으로 큐에 삽입
• 스케줄링 파라미터 : 선점/비선점 스케줄링
  - 선점 스케줄링 : 더 높은 스레드가 도착할 때 현재 스레드 강제 중단하고 스케줄링
  - 비선점 스케줄링 : 현재 실행 중인 스레드가 종료될 때 비로소 스케줄링
• 스레드 우선 순위 : 있음
• 기아 : 발생 가능
  - 지속적으로 높은 순위의 스레드가 도착하는 경우 언제 실행 기회를 얻을 수 있을지 예상할 수 없음
  - 큐 대기 시간에 비례하여 일시적으로 우선순위를 높이는 에이징 방법으로 해결 가능
• 성능 이슈
  - 높은 우선순위의 스레드일 수록 대기 혹은 응답시간 짧음
• 특징
  - 스레드 별 고정 우선 순위를 가지는 실시간 시스템에서 사용
  

MLQ

• 설계 의도 : 스레드들을 n개의 우선순위 레벨로 구분, 레벨이 높은 스레드들을 우선적으로 처리하는 목적
• 알고리즘
  - 고정된 n 개의 큐 사용, 각 큐에 고정 우선순위 할당
  - 각 큐는 나름대로의 기법으로 스케줄링
  - 스레드는 도착 시 우선 순위에 따라 해당 레벨 큐에 삽입. 다른 큐로 이동할 수 없음
  - 가장 높은 순위의 큐가 빌 때, 그 다음 순위의 큐에서 스케줄링
• 스케줄링 파라미터 : 스레드의 고정 우선순위
• 스케줄링 타입 : 비선점/선점 모두 가능
  - 비선점 스케줄링 : 현재 실행중인 스레드가 종료할 때 비로소 스케줄링
  - 선점 스케줄링 : 높은 레벨의 큐에 스레드가 도착하면 중단하고 높은 순위의 레벨 큐에서 스케줄링
• 기아 : 발생 가능
  - 지속적으로 높은 순위의 스레드가 도착하는 경우 언제 실행 기회를 얻을 수 있을지 예상할 수 없음
• 성능 이슈와 활용 사례
  - 스레드의 고정 순위를 가진 시스템에서 활용
  • 예 : 전체 스레드를 백그라운드 스레드와 포그라운드 스레드의 2개의 그룹을 구성
  • 예 : 시스템 스레드, 대화식 스레드, 배치 스레드 등 3개의 레벨로 나누고 시스템 스레드를 우선적으로 스케줄링
  • 예 : 대학에서 교수, 교직원 , 대학원생, 학부생 등 사용자를 4개의 레벨로 나누고, 사용자에 따라 실행시킨 스레드 레벨로 스케줄링

[참고]

• MLF 스케줄링
  -> FIFO + RR 스케줄링
  -> 작업을 전면 작업(대화형, foreground task) 과 후면 작업(일괄처리형, background task) 로 분류한다면 두 유형의 반응 시간이 다르므로 서로 다르게 스케줄링 해야한다.
  -> 전면 작업은 후면 작업에 비해 높은 우선순위를 갖는 경우가 많다.
  예를 들어, 쇼핑몰에서 쇼핑은 빠르게 백그라운드에서 다운로드는 느리게

MLFQ

• 설계 의도
  - 1962년에 개발된 알고리즘
  - 기아를 없애기 위해 여러 레벨의 큐 사이에 스레드 이동 가능하도록 설계
  - 짧은 스레드와 I/O가 많은 스레드, 대화식 스레드의 우선처리. 스레드 평균대기시간 줄임
  
• n개의 레벨 큐
  - n개의 고정 큐. 큐마다 서로 다른 스케줄링 알고리즘
  - 큐마다 스레드가 머무를 수 있는 큐타임 슬라이스가 있음. 낮은 레벨의 큐일 수록 더 긴 타임 슬라이스
  - I/O 집중 스레드(대화식 스레드)는 높은 순위의 큐에 있을 가능성이 높음
  
• 알고리즘
  - 스레드는 도착 시 최상위 레벨의 큐에 삽입
  - 가장 높은 레벨의 큐에서 스레드 선택. 비어 있으면 그 아래의 큐에서 스레드 선택
  - 스레드의 CPU-burst가 큐 타임 슬라이스를 초과하면 강제로 아래 큐로 이동 시킴
  - 스레드가 자발적으로 중단한 경우, 현재 큐의 끝에 삽입
  - 스레드가 I/O로 실행이 중단된 겨웅, I/O가 끝나면 동일한 레벨 큐 끝에 삽입
  - 큐에 있는 시간이 오래되면 기아를 막기 위해 하나의 위 레벨 큐로 이동
  - 최하위 레벨 큐는 주로 FCFS나 긴 타임 슬라이스의 RR로 스케줄. 스레드들은 다른 큐로 이동 못함
• 스케줄링 파라미터 : 각 큐의 큐 시간 할당량
• 스케줄링 타입 : 선점 스케줄링
• 스레드 우선 순위 : 없음
• 기아 : 발생하지 않음. 큐에 대기하는 시간이 오래되면 더 높은 레벨의 큐로 이동시킴(에이징 기법)
• 성능 이슈
  - 짧거나 입출력이 빈번한 스레드, 혹은 대화식 스레드를 높은 레벨의 큐에서 빨리 실햄 -> CPU 활용률이 높음
  

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

멀티코어 시스템의 구조

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

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

• 멀티코어 시스템에서 싱글코어 CPU의 스케줄링을 사용할 때 문제점

1) 컨텍스트 스위칭 오버헤드 증가문제

• 이전에 실행된 적이 없는 코어에 스레드가 배치될 때

• 캐시에 새로운 스레드의 코드와 데이터로 채워지는 긴 경과 시간

• 해결
  - CPU 친화성 (CPU affinity) 적용
  - 스케드를 동일한 코어에서만 실행하도록 스케줄링
  - 코어 친화성 (Core affinity), CPU 피닝(pinning), 캐시 친화성(cache affinity) 라고도 부름
  

2) 코어별 부하 불균형 문제

• 스레드를 무작위로 코어에 할당하면, 코어마다 처리할 스레드 수의 불균형 발생

• 해결
  - 부하 불균등 기법으로 해결
  - 푸시 마이그레이션 : 감시 스레드가 짧거나 빈 큐를 가진 코어에 다른 큐의 스레드를 옮겨놓는 기법
  - 풀 마이그레이션 : 코어가 처리할 스레드가 없게 되면, 다른 코어의 스레드 큐에서 자신이 큐에 가져와 실행시키는 기법
  

** 여러가지 스케줄링 기법 Youtube로 찾아보고 더 자세히 이해하기

이 글이 문제가 된다면 삭제하겠습니다.