CPU 스케줄링의 목표 : CPU활용률 향상, 컴퓨터 시스템 처리율 향상, 모든 스레드에게 CPU 사용 시간 공평하게 배분, 사용자에 대한 응답 시간 최소화
타임 슬라이스 = 커널이 CPU 스케줄링을 하는 주기 시간. 타임 슬라이스마다 커널은 현재 실행중인 스레드를 강제 중단 시켜 준비 리스트에 삽입하고, 다른 스레드를 선택해 타임 슬라이스 동안 CPU 사용하게 함.
CPU 스케줄링 실행되는 상황 4가지
- 스레드가 I/O 요청하는 시스템 호출 실행해 블록 상태(Blocked)되거나, 자원을 기다리는 상태가 될 때, 다른 스레드에게 CPU를 할당하는 경우(CPU 의 유휴시간 줄이는 목적)
- 스레드의 자발적인 CPU양보. yield() 시스템 호출을 통해 스스로 실행을 중단하고, CPU를 자발적으로 내놓을 때, 현재 스레드를 준비 상태(Ready)로 만들어 준비 리스트에 넣고 CPU 스케줄링을 시행함.
- 스레드에게 할당된 타임 슬라이스 다 소진돼, 타이머 인터럽트가 발생할 때, 인터럽트 서비스 루틴 내에서 CPU 스케줄링이 실행됨 (균등한 CPU 분배 목적)
- 현재 실행중인 스레드보다 더 높은 순위의 스레드가 요청한 입출력 작업이 완료돼 I/O 인터럽트가 발생한 경우. 인터럽트 서비스 루틴에서 현재 스레드를 강제 중단시켜 준비 상태로 만들고 우선순위가 더 높은 스레드를 스케줄링해 실행시킴 (우선순위 지키기 위한 목적)
CPU 스케줄링을 담당하는 별도의 커널 스레드나 프로세스가 있는 것은 아님. 시스템 호출이나 인터럽트 서비스 루틴에 의해 호출되는 코드(함수)형태로 존재함
CPU 스케줄링 코드가 실행되는 시점은?
: 시스템 호출이나 인터럽트 서비스 루틴이 서비스를 마치는 마지막 과정에서 스케줄링이 필요할 때 호출됨!!
디스패처(dispatcher) 코드 = 스케줄러 코드에 의해 선택된 스레드를 CPU가 실행하도록 하는 작업을 수행하는 커널 코드의 한 부분
디스패처 코드는 가능한 실행시간이 짧도록 작성돼야함!
비선점 스케줄링
: 스레드가 CPU를 할당받아 일당 실행을 시작하면, 완료되거나 CPU를 더 이상 사용할 수 없는 상황이 될 때 까지 스레드를 강제로 중단시키지 않고 스케줄링도 하지 않는 방식. 스레드가 더 이상 CPU를 사용할 수 없는 상황이 돼야만 스케줄링 이뤄짐
-CPU를 더 이상 사용할 수 없게 된 경우 : I/O로 인한 블록, sleep()
-자발적 cpu 양보 : yield() 시스템 호출
-스레드 종료
: SRTF(Shortest Remaining Time First), Priority 스케줄링(non-preemptive verison)
현재 거의 사용되지 않음
선점 스케줄링
: 커널이 현재 실행 중인 스레드를 강제로 중단시켜 준비 리스트로 이동시키고, 스케줄링을 통해 다른 스레드에게 CPU를 넘겨주는 방식
-타임 슬라이스가 소진됐을 때 (소진되어 타이머 인터럽트 발생될 때)
-인터럽트/시스템 호출 종료 시점에서 더 높은 순위의 스레드가 대기 상태에 있을 때
: RR(Round Robin), SJF(Shortest Job First), Priority(preemptive verison)
기아(starvation) : 스레드가 스케줄링 과정에서 선택되지 못한채 오랫동안 준비 리스트에 있는 상황). 예로, 우선순위를 기반으로하는 시스템에서 더 높은 순위의 스레드가 계속 준비 리스트에 들어오면, 낮은 순위의 스레드는 계속 배재돼 오랫동안 대기하게 되고 언제 실행될지 알 수 없음
기아에 대한 해결책 -> ‘에이징(aging)기법’ : 스레드가 준비리스트에 머무르는 시간에 비례해우선순위를 높여주는 기법. 에이징을 사용하면 스레드가 오래 기다릴 순 있지만, 언젠가 가장 높은 우선순위에 도달하는 것이 보장됨.
싱글 코어 CPU에서 사용한 스케줄링 기법을 멀티 코어 CPU에서 그대로 사용할 때의 문제
컨텍스트 스위칭 오버헤드 증가 --> 코어 친화성으로 해결
-CPU 스케줄러에 의해 어떤 코어에 실행시키기로 결정한 스레드가 예전에 이 코어에서 실행된적이 없다면 새 스레드의 코드와 데이터가 캐시에 적재되는데 시간이 많이 소요됨. 만약 최근에 코어에서 실행된 적이 있는 스레드 중 선택한다면 캐시 채우는 과정이 줄어듦.
이 문제는 스레드를 동일한 코어에서만 계속 실행되도록 스케줄 하는 CPU 친화성(CPU affinity)로 해결됨. CPU 친화성이란 프로세스나 스레드가 특정 CPU 에서만 실행되도록 제한하는 스케줄러의 특성으로, 캐시 친화성 이라고도 부름.
코어별 부하 불균형 --> 부하 균등화 기법으로 해결
-멀티 코어 시스템에서 운영체제가 스레드를 무작위로 스케줄링 하면 어떤 코어는 많은 수의 스레드를 실행하고, 어떤 코어는 작은 수의 스레드를 실행함. 이렇게 코어 사이의 부하 불균형이 초래되면, 많은 스레드 몰린 코어에서 실행되는 스레드는 대기 시간&처리 시간이 길어지고 어떤 코어는 실행할 스레드가 없어 놀게 돼, 코어의 활용률과 시스템 처리율이 떨어짐
--> 부하 균등화 기법 사용
푸시 마이그레이션 기법 : 시스템에 ‘스레드 큐’ 감시하는 별도의 감시 스레드 두고 스레드 큐가 매우 짧거나 실행할 스레드가 없어 노는 코어가 생길 때, 감시 스레드는 다른 스레드 큐로부터 스레드를 강제로 옮겨 놓는 기법. 코어들이 처리하는 스레드 개수 균등하게 유지
풀 마이그레이션 : 코어가 처리할 스레드 없게 되면, 다른 코어의 스레드 큐에서 스레드 가져와 자신의 스레드 큐에 넣고 실행시키는 기법.