5. CPU 스케줄링

CPU 스케줄링이 무엇인가?

운영체제는 프로세스 간 CPU 교환을 통해 그 사용률을 극대화한다. 앞서 다룬 병행성을 갖게 해준 멀티 프로그래밍을 떠올리면 된다. 다시 말해 운영체제의 CPU 스케줄링은 준비 큐에서 대기 프로세스를 선택하고 CPU를 할당하는 작업이다. 스케줄링 방법에 따라 프로세스를 처리하는 성능이 좌지우지 되므로 CPU 스케줄링은 운영체제 설계의 핵심이다.

선점 및 비선점 스케줄링

• 선점 스케줄링: CPU를 프로세스로부터 가져올 수 있는 케이스
• 비선점 스케줄링: 프로세스가 자발적으로 CPU를 반납하는 케이스

대부분 현대 운영체제에서는 선점 스케줄링을 사용한다. 비선점 스케줄링은 실시간 스케줄링에 적합하지 않다. CPU 제어 권한을 프로세스가 포기하기 전까지 소유하므로 균형있게 CPU소유 시간을 제어해야하는 운영체제 입장에서는 적합하지 않은 방법이다.

 스케줄링 알고리즘을 평가하는 기준

• CPU 이용률
• Throughput: 단위 시간당 완료된 프로세스의 개수
• 총 처리 시간
• 대기 시간
• 응답 시간

PC와 같은 Interactive system에서는 평균 응답 시간의 최소화가 아닌 편차를 최소화하는 것이 더 적합하다고 제시하지만, CPU 스케줄링에서 편차를 최소화하는 알고리즘 연구는 거의 없다.

스케줄링 알고리즘

• FCFS(FIFO): 선입선출 큐 형태, 평균 대기 시간의 편차가 크게 발생할 수 있다.
• SJF(Shortest-Job-First): 작업량이 가장 작은 프로세스부터 처리한다. 프로세스 길이가 아닌 CPU 버스트 크기가 기준
• Round-Robin: 시간 할당량(타임 슬라이스)만큼 CPU를 할당한다. 만약 시간 내 작업이 완료되지 못하면 남은 작업을 원형 큐 마지막으로 이동시킨다
• Priority: 우선순위가 높은 프로세스부터 처리한다. 우선 순위가 낮은 프로세스가 영영 실행되지 않는 Starvation 현상이 발생할 수 있다. 이를 해결하기 위한 방법으로 일정 시간마다 우선순위를 증가시키는 Aging 기법이 있다.

Linux - CFS

Linux는 Completely Fair Scheduler(CFS)를 시스템의 디폴트 스케줄링 알고리즘으로 사용한다. 해당 알고리즘의 스케줄러는 Red-Black tree를 형태로 실행 가능한 태스크를 관리한다.

---

5.4 스레드 스케줄링 이후부터는 현재 제대로 이해하기 어려운 내용이라 패스한다.

추후 필요해지면 아마 추가 자료를 봐야할 듯