CPU 스케줄링

CPU 스케줄링 
시스템에서는 순간에 한 프로세스만 실행될 수 있다. 그러므로 CPU의 이용률을 최대화 하기 위해 항상 실행중인 프로세스를 가지게 해야 한다.


CPU-입/출력 버스트 사이클(CPU-I/O Burst Cycle)
프로세스 실행은 CPU실행과 입/출력 대기의 사이클로 구성되는데, CPU는 이 두상태를 왔다갔다 한다. 프로세스는 CPU 버스트로 실행 된다. 

CPU 버스트 -> 입/출력 버스트 -> CPU 버스트 -> ….. -> CPU 버스트 -> 입/출력버스트 -> 종료 CPU


스케줄러(CPU Scheduler) 
실행 준비가 되어 있는 메모리 내의 프로세스들 중 하나에게 CPU를 할당한다. 



선점 스케줄링(Preemptive Scheduling)
비선점 스케줄링은 CPU가 한 프로세스에 할당되면 종료하든 사용 후 반환할 때까지 CPU를 점유한다. 선점 스케줄링은 공유 자료에 대한 접근을 조정하는 데 필요한 비용을 유발한다. 



디스패처(Dispatcher) CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈로, 문맥 교환, 사용자 모드 전환, 프로그램 재시작을 위한 위치로 이동 등의 일을 한다. 


스케줄링 기준
 - CPU 이용률, 처리량, 총 처리 시간, 대기 시간, 응답 시간 


스케줄링 알고리즘
준비 완료 큐에 있는 어느 프로세스에게 CPU를 할당할 것인지를 결정 

- 선입 선처리 스케줄링(First-Served Scheduling) : 먼저 요청한 프로세스가 먼저 할당 받는다. 

- 최단 작업 우선 스케줄링(SJF) : 각 프로세스에게 다음 CPU 버스트 길이를 연관시키는데, 가장 작은 CPU버스트를 가진 프로세스에게 할당한다.

 - 우선순위 스케줄링(Priority Scheduling) : 가장 높은 우선순위를 가진 프로세스에게 할당 무한 봉쇄 문제 : 낮은 우선순위 프로세스가 무한 대기하는 현상 

- 라운드 로빈 스케줄링(Round-Robin Scheduling) : 준비 완료 큐를 돌면서 한 번에 한 프로세스에게 시간할당량 동안 CPU를 할당한다.

 - 다단계 큐 스케줄링(Multilevel Queue Scheduling) : 준비완료 큐를 다수의 별도의 큐로 분류하는데, 각 큐는 1.시스템 프로세스, 2.대화형 프로세스, 3.대화형 편집프로세스, 4.일괄 처리 프로세스, 5.학생 프로세스로 나뉘며, 각 우선순위를 가지며, 각 큐는 CPU 시간의 일정량을 할당 받아 자기 큐에 있는 다양한 프로세스들을 스케줄 할 수 있다. 

- 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling) : 프로세스가 큐들 사이를 이동하는 것을 허용. 프로세스가 CPU시간을 많이 사용하면 낮은 우선순위의 큐로 이동된다. 또한 낮은 우선순위에 오래 대기하는 프로세스는 높은 우선순위로 이동한다.

- 다중 처리기 스케줄링(Multiple-Processor Scheduling) : 대칭 다중 처리(SMP)를 사용하여 각 처리기가 독자적인 스케줄링을 한다.



쓰레드 스케줄링
사용자와 커널 쓰레드의 차이는 어떻게 스케줄링 되느냐의 차이인데,
- 사용자 수준 쓰레드는 LWP 상에서 스케줄링한다. 동일한 프로세스에 속한 쓰레드들 사이에서 CPU를 경쟁하기 때문에 프로세스 경쟁범위(PCS)라 한다. 
- 커널 수준 쓰레드는 CPU상에 어떤 커널 쓰레드를 스케줄할 것인지 결정하기 위해 시스템-경쟁범위(SCS)를 사용한다.



운영체제 세례들 

- Solaris 스케줄링 : 우선순위 기반 스케줄링을 하며, 실시간,시스템,시분할,대화형 총 4개의 스케줄링 클래스를 정의한다. 디폴트는 시분할로 다단계 피드백 큐를 사용해 동적으로 우선순위를 바꾸고 서로 다른 길이의 시간 조각을 할당한다.

- Window XP스케줄링 : 선점기반 스케줄링을 사용하여 가장 높은 우선순위의 쓰레드가 항상 실행되도록 보장한다. 준비 상태에 있는 스레드가 없으면 유후(idle)쓰레드를 실행시킨다.

- Linux 스케줄링 : 전통적 UNIX 스케줄러의 두가지 문제는 SMP 시스템을 위한 충분한 지원 부족과 시스템상의 태스크 증가시 확장의 어려움 이였다. 이에 새로운 알고리즘은 시스템 상의 태스크 개수와 상관없이 항상 상수 시간에 실행된다(O(1)).