[운영체제] CPU 스케줄링

CPU 스케줄링 개요

1) 운영체제에서 일어나는 스케줄링

#1 자원에 대한 스케줄링

• 자원에 대한 경쟁이 있는 컴퓨터 시스템 여러 곳에서 발생

#2 다양한 스케줄링

• 작업 스케줄링 : 대기 중인 배치 작업 중 어떤 작업을 메모리에 적재할지
• CPU 스케줄링 : 프로세스/스레드 중에 하난를 선택하여 CPU를 할당하는 스케줄링
• 디스크 스케줄링 : 디스크 장치 내에서 디스크 입출력 요청 중 하나를 선택
• 프린터 스케줄링 : 프린팅 작업 중 하나를 선택하여 프린터 할당

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

• CPU의 유휴시간을 줄이기 → CPU 활용률 향사어
• 작업 스케줄링과 CPU 스케줄링 도입

3) CPU burst I/O burst

• cpu burst : 프로그램 실행 중 cpu 연산이 연속적으로 실행하는 상황
• I/O burst : 프로그램 실행중 I/O 장치의 입출력이 이루어지는 상황
• 프로그램의 일반적인 실행 특징

4) CPU 스케줄링

• 실행 준비 상태의 스레드 중 하나를 선택하는 과정
• cpu 활용률 극대화를 통해 컴퓨터 시스템 처리율 향상

#1 CPU 스케줄링의 기준

• cpu 활용률 : 전체 시간 중 cpu 사용 시간 비율
• 처리율 : 단위시간당 처리하는 프로세스의 개수
• 공평성 : 무한정 대기하는 기아 스레드가 생기지 않도록 스케줄, cpu를 스레드들에게 공평하게 배분 ( 시분할 )
• 응답시간 : 대화식 사용자의 경우, 명령에 응답하는데 걸리는 시간
• 대기시간 : 스레드가 준비 큐에서 머무를는 시간
• 소요시간 : 프로세스가 컴퓨터 시스템에 도착한 후 완료될 때까지 걸린 시간
• 시스템 정책 우선 : 컴퓨터 시스템의 특별한 목적을 달성하기 위한 스케줄링

#2 타임 슬라이스

• 대부분 운영체제에서 하나의 스레드가 너무 오래 cpu를 사용하도록 허용 X
• 타임 슬라이스 : 스케줄된 스레드에게 한 번 할당하는 cpu 시간

CPU 스케줄링의 기본

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

1. 스레드가 시스템 호출 끝에 I/O를 요청하여 블록 ( CPU 활용률 향상 )
2. 스레드가 자발적으로 CPU 반환 ( CPU의 자발적 양보 )
3. 스레드의 타임 슬라이스가 소진되어 타이머 인터럽트 발생 ( 균등한 CPU 분배 )
4. 더 높은 순위의 스레드가 요청한 입출력 작업 완료, 인터럽트 발생 ( 우선 순위를 지키기 위해 )

2) CPU 스케줄링과 디스패치

#1 스케줄링

• 스케줄링 담당하는 커널이나 프로세스가 존재하지 않음
• 스케줄링 코드는 커널 코드의 일부
• 시스템 호출이나 인터럽트 서비스 루틴이 끝나는 마지막 단계에서 실행

#2 디스패쳐

• 컨텍스트 스위칭을 실행하는 커널 코드
• 스케줄러에 의해 선택된 스레드를 cpu가 실행하도록 하는 작업
• 스케줄러와 디스패러 모두 실행 시간이 짧도록 작성

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

#1 선점 스케줄링

• 현재 실행중인 스레드를 강제 중단시키고 다른 스레드 선택, cpu 할당
• 타임 슬라이스가 소진되어 인터럽트가 발생하거나 더 높은 순위의 스레드가 준비 상태일 경우 발생

#2 비선점 스케줄링

• 현재 실행중인 스레드를 강제로 중단시키지 않음
• cpu를 더 이상 사용하지 못하거나 자발적으로 양보할 경우 스케줄링 발생

→ 오늘날 범용 운영체제는 선점 스케줄링 타입 사용

4) 기아와 에이징

#1 기아

• 스레드가 스케줄링에서 선택되지 못한 오랫동안 준비 리스트에 있는 상황
• 우선 순위 기반 시 더 높은 순위의 스레드가 계속 시스템에 들어오는 경우
• 짧은 스레드를 우선 실행 시 자신보다 짧은 스레드가 계속 도착하는 경우
• 스케줄링 알고리즘 설계 시 기아 발생을 면밀히 확인 필요

#2 에이징

• 기아의 해결책으로 스레드가 준비 리스트에 머무를는 시간에 비례하여 스케줄링 순위를 높이는 방법
• 오래 기다릴 수는 있지만 최우선 순위에 도착을 보장함으로써 언젠가는 처리가 될 수 있음을 설계

CPU 스케줄링 알고리즘

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

• FCFS(First Come First Served) : 도착한 순서대로 스레드를 준비 큐에 넣고 도착한 순서대로 처리
• Shortest Job First : 가장 짧은 스레드 우선 처리
• Shortest Remaining Time First : 남은 시간이 짧은 스레드가 준비 큐에 들어오면 이를 우선 처리
• Round-robin : 스레드들을 돌아가면서 할당된 시간만큼 실행
• Priority Scheduling : 우선 순위를 기반으로 하는 스케줄링
• Multilevel queue scheduling : 스레드와 큐 모두 n개의 우선순위 레벨로 할당하여 큐의 우선순위 → 스레드 우선순위 대로 스케줄링
• Multilevel feedback queue scheduling ; 큐만 n개의 우선순위 레벨을 가지고 스레드 처음 진입시 제일 높은 순위 큐 대기 후 실행 타음 슬라이스가 다할 경우 아래 레벨로 이동

#1 First Come First Served (FCFS)

• 먼저 도착한 스레드 먼저 스케줄링
• 스레드 별 도착시간을 파라미터로 가짐
• 비선점 스케줄링
• 스레드 우선 순위는 없음
• 기아는 발생하지 않는다 (오류로 인한 무한 루프 제외)
• 처리율이 낮으며, 긴 스레드가 cpu를 오래 사용하면 늦게 도착한 짧은 스레드가 오래 대기하는 호위 효과 발생

#2 Shortest Job First (SJF)

• 예상 실행 시간이 가장 짧은 스레드 선택
• 스레드 별 예상 시간을 파라미터로 가짐 (예상 시간을 아는 것이 비현실적)
• 비선점 스케줄링
• 스레드 우선 순위는 없으며 기아는 발생 가능 (긴 스레드는 무한 대기 가능)
• 짧은 스레드가 먼저 실행되어 평균 대기 시간이 최소화
• 실행시간의 예측이 불가능하여 현실에서는 사용이 어려움

#3 Shortest Remaining Time First (SRTF)

• 남은 실행 시간이 가장 짧은 스레드 선택
• SJF 알고리즘의 선점 스케줄링 버전
• 스레드 별 예상 실행 시간과 남은 실행 시간 값
• 선점 스케줄링
• 스레드 우선 순위는 없으며 기아는 발생 가능 (긴 스레드는 무한 대기 가능)
• SJF와 마찬가지로 실행 시간의 예측이 불가능하여 현실에서는 사용이 어려움

#4 Round Robin (RR)

• 공평한 실행 기회를 위해 타임 슬라이스를 주기로 돌아가면서 선택
• 타임 슬라이스를 파라미터로 가짐
• 선점 스케줄링
• 스레드 우선 순위는 없으며, 기아도 없음
• 공평하고 기아가 없으며 구현이 쉽다
• 하지만 잦은 스케줄링으로 스케줄링 오버헤드가 큼
• → 타임 슬라이스가 크면 FCFS 작을 경우 SJF/SRTF와 비슷

#5 Priority 스케줄링

• 우선순위에 따라 준비 큐에 삽입하고 스레드 실행
• 스레드 별 고정 우선 순위
• 스케줄링 타입은 둘 다 가능
  • 비선점 경우 : 현재 실행 중인 스레드가 종료될 때만 스케줄링
  • 선점 경우 : 실행 중인 스레드보다 더 높은 우선 순위의 스레드 도착 시 현재 스레드를 중단 후 스케줄링
• 스레드 우선 순위가 있으며 기아 발생 가능 (낮은 우선 순위의 스레드가 무한 대기 가능)
• 스레드 별 고정 우선 순위를 가지는 실시간 시스템에서 사용

#6 Multi-level Queue 스케줄링

• 스레드들을 n개의 우선순위 레벨로 구분, 레벨이 높은 스레드들을 우선적으로 처리
• 알고리즘
  • 고정된 n개의 큐 사용, 각 큐의 고정된 우선 순위 할당
  • 스레드들의 우선 순위도 n개의 레벨로 분류
  • 각 큐마다 스케줄링 기법 사용
  • 스레드 도착 시 우선 순위로 해당 레벨 큐에 삽입되며 다른 큐로 이동 불가
  • 가장 높은 순위의 큐가 빌 때, 다음 순위의 큐에서 스케줄링
• 스레드의 고정 우선 순위가 파라미터
• 비선점/선점 모두 가능 : 높은 레벨의 큐에 스레드가 도착 시 중단 여부로 달라짐
• 스레드 우선 순위는 있으며 기아는 발생 가능 (낮은 우선 순위의 스레드가 무한 대기 가능)
• 스레드의 고정 순위를 가진 시스템에서 활용

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

• 기아를 없애기 위해 여러 레벨 큐 사이에 스레드 이동 가능하도록 설계
• 짧은 스레드, I/O가 많은 스레드, 대화식 스레드를 우선 처리하여 평균 대기 시간을 줄일 수 있음
• 알고리즘
  • 스레드는 도착 시 최상위 레벨 큐로 삽입
  • 가장 높은 레벨의 큐에서 스레드를 선택하며 비어있을 경우 그 아래 큐에서 선택
  • 스레드의 CPU-burst가 큐 타임 슬라이스를 초과하면 아래 큐로 이동
  • 자발적으로 중단 시 현재 큐 끝에 다시 삽입
  • I/O로 실행 중단 시 현재 큐 끝에 다시 삽입
  • 큐에 있는 시간이 오래되면 기아를 막기위해 하나 위의 레벨 큐로 이동
  • 최하위 레벨 큐는 FCFS나 긴 타임 슬라이스의 RR 스케줄링 사용하며 최하위 큐에 존재하는 스레드들은 다른 큐로 이동 불가
• 각 큐의 큐 시간 할당량이 파라미터
• 선점 스케줄링
• 스레드의 우선 순위는 없으며 에이징 기법을 통해 기아 발생을 막음

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

1) 멀티 코어 시스템에서의 cpu 스케줄링

• 싱글 코어 cpu 스케줄링을 멀티 코어 시스템에서 사용할 경우
• → 컨텍스트 스위칭 오버헤드 증가 → CPU 친화성 적용
• → 코어 별 부하 불균형 문제 → 부하 균등화 기법 (푸시 / 풀 마이그레이션 )

#1 CPU 친화성

• 스레드를 동일한 코어에서만 실행하도록 스케줄링
• 코어 친화성, CPU pinning, 캐시 친화성으로도 부름

#2 푸시/풀 마이그레이션

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