05 CPU 스케줄링

1. CPU 스케줄링 개요

자원 : CPU, 디스크, 프린터, 파일, 데이터베이스 등 CPU 스케줄링 : 준비상태에 있는 스레드들 중 하나를 선택하여 CPU를 할당하는 과정 디스크 스케줄링 : 디스크 입출력 요청 중 하나를 선택하여 디스크 장치를 사용하도록 하는 과정

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

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

• 작업 스케줄링(job scheduling)
• CPU 스케줄링(CPU scheduling)

초기 다중프로그래밍 시스템 → 사용자가 작성한 작업을 읽어 디스크 장치에 저장하고 몇개의 작업을 메모리에 적재 후 이들을 다중프로그래밍 방식으로 처리 작업 스케줄링 : 메모리에 적재된 프로세스가 종료하면 디스크에서 기다리는 작업 중 하나를 선택하여 메모리에 적재 CPU 스케줄링 : 실행중인 프로세스가 I/O를 실행할 때 메모리에 적재된 다른 프로세스 중 cpu에 실행시킬 프로세스를 선택하는 과정

1.2 cpu brust와 I/O brust

프로그램은 CPU brust - I/O brust - … - CPU brust - I/O brust를 반복함

cpu brust : cpu가 코드를 집중적으로 실행하는 상황 I/O brust : I/O 장치에 의해 입출력이 이루어지는 상황

CPU 집중 프로세스 : cpu brust 시간 > I/O brust 시간 I/O 집중 프로세스 : cpu brust 시간 < I/O brust 시간

I/O brust 동안 cpu 유휴 시간을 줄이기 위해 cpu를 다른 프로세스에게 할당하는 cpu 스케줄링 도입

1.3 cpu 스케줄링의 기본 목표

• cpu 활용률 향상
• 컴퓨터 시스템 처리율 향상

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

• CPU 활용률(CPU utilization) : 컴퓨터 전체 가동시가네 대한 cpu 사용 시간 비율
• 처리율(throughput) : 단위 시간 당 처리하는 스레드 개수
• 공평성(fairness) : 모든 스레드에게 cpu 사용시간을 공평하게 배분하는 것
• 응답시간(response time) : 사용자에 대한 응답 시간 최소화
• 대기시간(waiting time) : 스레드가 준비 리스트에서 cpu를 할당받을 때까지 기다리는 시간
• 소요시간(turnaround time) : 작업이 컴퓨터 시스템에 진입하는 시점에서 완료까지 걸린 시간
  • 배치 시스템 : 작업 제출 ~ 결과 반환
  • 다중프로그래밍 : 프로세스 시작 ~ 종료
  • 사용자 입장 : 작업 시작 후 결과 얻기까지 걸린 시간
• 시스템 정책 우선(high policy enforcement) : cpu 스케줄링이 시스템의 정책에 맞도록 이루어져야 함
• 자원 활용률(high resource effieniecy)

1.5 cpu 스케줄링과 타임 슬라이스

운영체제는 스레드가 CPU를 사용할 타임 슬라이스를 정하고 이 시간동안 CPU를 사용하게 함

2. CPU 스케줄링 기본

1. 스레드가 I/O를 요청하는 시스템 호출을 실행하여 블록 상태(Blocked)가 되거나 자원을 기다리는 상태가 될 때 다른 스레드에게 CPU를 할당하는 경우
2. 스레드가 자발적으로 CPU를 반환하는 경우
3. 스레드에게 할당된 타임 슬라이스가 다 소진되어 타이머 인터럽트가 발생할 때
4. 현재 실행중인 스레드보다 더 높은 순위의 스레드가 요청한 입출력 작업이 완료되어 I/O 인터럽트가 발생한 경우

2.2 CPU 스케줄링과 디스패치

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

cpu 스케줄링은 커널에 의해 이루어짐

CPU 스케줄링을 담당하는 별도의 커널 스레드나 프로세스는 없다

• 모놀리식 커널의 경우 스케줄링을 전담하는 별도의 스레드가 없고 스케줄링 코드는 시스템 호출이나 인터럽트 서비스 루틴에 호출되는 코드 형태로 존재

CPU 스케줄링 코드가 실행되는 자세한 시점은? 시스템 호출이나 인터럽트 서비스 루틴이 서비스를 마치는 마지막 과정에서 스케줄링이 필요할 때

디스패처(dispatcher)코드 실행

스케줄러 코드에 의해 선택된 스레드를 cpu가 실행하도록 하는 커널코드의 한 부분

• CPU 레지스터들을 스레드 A의 TCB-A에 저장하고 스레드 B의 TCB-B에 저장된 레지스터들을 CPU에 적재하는 컨텍스트 스위칭 실행
• 디스패치 실행 결과 cpu는 이전에 스레드 b가 중단되었던 상태에서 실행 시작

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

비선점 스케줄링

스레드를 강제 중단 시키지 않고 실행중인 스레드가 더이상 cpu를 사용할 수 없는 상황이 오면 스케줄링 시행

• cpu를 더 이상 사용할 수 없게 된 경우 : I/O로 인한 블록 상태, sleep()
• 자발적 cpu양보 : yield() 시스템 호출
• 스레드 종료

선점 스케줄링

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

• 타임 슬라이스가 소진되었을 때
• 인터럽트나 시스템 호출 종료 시점에서 더 높은 순위의 스레드가 대기 상태에 있을 때

2.4 기아와 에이징

기아(starvation) : 스레드가 스케줄링 과정에서 선택되지 못한 채 오랫 동안 준비리스트에 있는 상황

• 우선순위 기반 시스템에서 높은 순위의 스레드가 계속 들어오는 경우
• 실행시간이 짧은 스레드를 우선으로 하는 알고리즘에서 짧은 스레드가 계속 들어오는 경우

에이징(aging) : 스레드가 준비리스트에 머무르는 시간에 비례하여 우선순위를 높여주는 기법

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

3.1 FCFS(First Come First Served) 스케줄링

먼저 도착한 스레드를 먼저 스케줄링

스케줄링 파라미터	스케줄링 타입	스레드 우선순위	기아
스레드 별 큐 도착시간	비선점	없음	발생 X

• 성능 이슈
  • 긴 cpu brust를 실행하는 스레드가 cpu를 양도할 때까지 대기하거나 늦게 도착한 짧은 스레드들이 오래 대기 → 시스템 전체가 느려짐
  • 처리율이 낮지만 단순하고 구현이 용이

3.2 SJF(Shortest Job First) 스케줄링

실행 시간이 가장 짧은 스레드를 우선 선택 큐를 순회하여 시간이 가장 짧은 스레드를 선택하거나 스레드가 큐에 도착할 때 정렬하여 구현

스케줄링 파라미터	스케줄링 타입	스레드 우선순위	기아
스레드 별 예상도착시간	비선점	없음	발생 가능

• 성능 이슈
  • 대기중인 모든 스레드의 대기시간이 짧아지므로 평균 대기시간 감소
  • 스레드 실행 시간 예측 불가능 → 현실에서 사용 x

평균 대기 시간 : (0+4+2+3)/4 = 2.25ms

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

SJF의 선점 스케줄링 버전, 실행 시간이 가장 짧은 스레드를 우선 스케줄

스케줄링 파라미터	스케줄링 타입	스레드 우선순위	기아
스레드 별 예상 실행시간	선점	없음	발생 가능

• 성능 이슈
  • 스레드들의 평균 대기시간 최소화
  • 실행시간 예측 X

평균 대기 시간 : (1+4+0+3)/4 = 2ms

3.4 RR(Round-Robin) 스케줄링

공평한 실행 기회를 주기 위해 큐에 대기중인 스레드들을 타임 슬라이스 주기로 돌아가면서 선택 도착하는 스레드는 큐 끝에 삽입되고 준비리스트의 맨 앞에 스레드를 선택하여 실행

스케줄링 파라미터	스케줄링 타입	스레드 우선순위	기아
타임 슬라이스	선점	없음	없음

• 성능이슈
  • 잦은 스케줄링과 컨텍스트 스위칭에 소요되는 시간이 큼
  • 타임 슬라이스가 작을수록 스케줄링 횟수 증가로 성능 저하

• 타임 슬라이스가 2ms - 평균 대기시간 : (3+4+2+3)/4 = 3ms - 스케줄링 횟수 : 6번 - 컨텍스트 스위칭 : 5번 - FCFS에 가까운 알고리즘
• 타임 슬라이스가 1ms
  • 평균 대기시간 : (5+4+1+3)/4 = 3.25ms
  • 스케줄링 횟수 : 10번
  • 컨텍스트 스위칭 : 9번
  • SJF/SRT에 가까운 알고리즘

3.5 Priority 스케줄링

큐에서 가장 높은 우선순위의 스레드를 선택하는 알고리즘

스케줄링 파라미터	스케줄링 타입	스레드 우선순위	기아
스레드들의 우선순위 값	선점/비선점 모두 가능	스레드마다 고정 우선순위	발생 가능

• 성능 이슈
  • 우선순위가 높을수록 대기시간과 응답시간이 짧음
  • 고정 우선순위를 가지는 실시간 시스템에서 주로 사용

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

• 설계의도
  • 스레드들을 n개의 우선순위 레벨로 구분하고 레벨이 높은 스레드를 우선 처리할 목적으로 설계

n개의 레벨 큐(우선순위 큐)를 두고 스레드를 레벨에 따라 큐에 삽입 가장 높은 레벨의 큐에서 맨 앞에 있는 스레드 선택

스케줄링 파라미터	스케줄링 타입	스레드 우선순위	기아
스레드 우선순위	선점/비선점 모두 가능 비선점 : 스레드가 종료할 때 스케줄링 하도록 구현 선점 : 실행중 더 높은 레벨의 스레드를 먼저 스케줄링	고정 우선순위	발생가능

• 성능 이슈
  • 스레드별로 고정 우선순위를 두고 높은 순위의 스레드를 먼저 실행시키는 시스템에서 사용
  • 높은 순위를 가진 스레드들의 대기 시간과 응답 시간이 짧음
  • 지속적으로 높은 레벨의 스레드 도착 시 기아 발생
  • 스레드를 다른 레벨 큐로 이동시켜 문제 해결

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

• 설계의도

  • cpu brust가 짧은 스레드, I/O작업이 많은 스레드, 대화식 스레드 우선 실행
  • 스레드의 평균대기시간을 줄이고 사용자의 응답시간을 줄이고 기아가 발생하지 안게 함

• n개의 레벨 큐

  • 우선순위로 구분된 n개의 큐를 둠
  • 우선순위가 없고 도착할 때 가장 높은 레벨의 큐에 삽입
  • 높은 레벨의 큐를 먼저 스케줄링하며, 높은 레벨의 큐가 비어있을 때만 아래 레벨의 큐에서 스케줄링

도착하는 스레드는 가장 높은 레벨 큐에 삽입됨 가장 높은 레벨 큐에서 스레드를 선택하여 실행시키고, 큐가 비었으면 아래 레벨 큐에서 선택하는 식으로 처리 실행중인 스레드의 cpu brust가 큐 타임 슬라이스보다 길어짐 → 강제 중단 뒤 아래 레벨의 큐로 이동 스레드가 실행 중 자발적 중단 → 동일 큐에 다시 삽입 I/O 요청시 큐에서 나옴 → 작업 후 동일 큐에 다시 삽입 대기 시간 길어짐 → 기아 방지를 위해 한 레벨 위의 큐로 이동 최하위 레벨 큐는 FCFS나 긴 타임 슬라이스의 RR로 스케줄

스케줄링 파라미터	스케줄링 타입	스레드 우선순위	기아
큐의 개수, 각 큐의 스케줄링 알고리즘, 우선순위 격하/격상 시점, 도착하는 스레드가 진입할 큐 등	선점	없음	없음

• 성능 이슈
  • cpu brust가 짧거나 입출력이 빈번한 스레드, 대화식 스레드에게 높은 우선순위를 제공하여 응답시간을 빨리하고 평균 대기시간을 감소시킴
  • 유연성이 뛰어나지만 알고리즘이 복잡하여 cpu 오버헤드가 증가되는 단점

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

4.1 멀티 코어 CPU와 병렬 처리

코어 : 레지스터들, 연산장치, 제어장치, 버스 인터페이스를 가지고 기계명령을 처리할 수 있는 프로세서

• 4개의 코어가 4개의 스레드를 병렬 실행
• 각 코어에서 실행되는 스레드가 동시에 시스템 호출을 실행하여 커널로 진입 가능

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

컨텍스트 스위칭 후 오버헤드 - 코어 친화성으로 해결

cpu 스케줄러에 의해 어떤 코어에 실행시키기로 결정된 스레드가 이전에 이 코어에서 실행된 적이 없음 → 새 스레드가 실행된 후 새 스레드의 코드와 데이터가 캐시에 적재되는 데 많은 시간 소요 → 최근 실행된 적 있는 스레드 중 하나를 선택한다면 캐시를 다시 채우는 과정 감소

CPU 친화성 : 프로세스나 스레드가 특정 cpu에서만 실행되도록 제한하는 스케줄링 특성

멀티 코어 운영체제에서는 코어 친화성을 위해 코어마다 스레드 큐를 두고 한 코어에서 실행이 중단된 스레드를 다시 동일한 코어의 큐에 삽입하는 방법을 사용

코어별 부하 불균형 - 부하 균등화 기법으로 해결

코어 사이의 부하 불균형 초래 → 많은 스레드가 몰린 코어는 대기시간과 처리시간이 길어짐 → 적은 코어는 노는 상태가 되어 코어 활용률과 시스템 처리율이 떨어짐

부하 균등화 기법 2가지

1. 푸시 마이그레이션
   • 스레드를 감시하는 별도의 감시 스레드를 두고 노는 코어가 생길 때 다른 스레드 큐로부터 스레드를 강제로 옮겨놓는 기법 → 스레드 개수를 균등하게 유지
2. 풀 마이그레이션
   • 처리할 스레드가 없을 때 다른 코어의 스레드 큐에서 스레드를 가져와 자신의 스레드 큐에 넣고 실행하는 기법

출처 - https://www.booksr.co.kr/product/%EB%AA%85%ED%92%88-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EC%88%98%EC%A0%95%ED%8C%90/