14. CPU Scheduling

CPU 스케줄링은 왜 생겼을까?

 

운영체제의 발전을 공부하면서 다중프로그래밍이 도입된 것을 알게됐다.

다중 프로그래밍은 I/O 처리로 인한 CPU Idle Time을 줄여서 CPU 활용률을 향상 시키기 위해서 도입 되었는데 이 때, 다중 처리를 하기 위한 기법이 CPU 스케줄링이다. 스레드까지 공부하면서 알게 된 내용은 CPU는 스레드를 스케줄링해야 한다는 것이다. 근데 어떤 스레드를 선택할 것인지 골라야한다.

 

위와 같은 정책을 가진 알고리즘을 크게 CPU 스케줄링 알고리즘이라고 하고 엄밀하게는 스레드 스케줄링이라고 한다.

다중 프로그래밍은 2가지 스케줄링을 통해 발생한다.

1. 작업 스케줄링(job scheduling) - 디스크 장치로부터 메모리에 올릴 작업을 선택하는 것이다. 프로세스가 시작하거나 종료 할 때, 사용하는 기법이다.

2. CPU 스케줄링(CPU Scheduling) - 작업 스케줄링으로 메모리에 적재된 작업 중 CPU에 실행시킬 스레드를 선택한다.

 

프로그램은 일반적으로 두 가지의 특성을 가진다.

1. CPU burst - CPU 집중 프로세스의 특성이다. 프로그램 실행 중 CPU 연산이 자주 발생하는 상황이다.

2. I/O burst - I/O 집중 프로세스의 특성으로 I/O 장치의 입출력이 자주 발생하는 상황이다.

이렇게 프로그램은 CPU-burst와 I/O burst가 반복해서 수행되는 특징이 있으므로 이 특징을 이용해서 CPU 스케줄링의 기준을 명확하게 설정해야한다.

 

Time slice, Time slot, Time quantum

 

시분할 다중프로그래밍에서는 CPU에게 스케줄 시간을 할당한다.

커널이 스케줄을 처리하는 주기 시간으로 타이머 인터럽트로 타임 슬라이스 단위로 스케줄링한다.

타임 슬라이스 내에 스레드가 종료되지 않는다면 강제로 중단(preemption)하고, 대기 큐에 삽입한다.

 

CPU 스케줄링이 실행되는 상황

 

1. 스레드가 시스템 호출 끝 I/O 요청으로 블록되고 새로운 스레드를 선택한다.
   • CPU 활용륭 향상이 목적
2. 스레드가 자발적으로 CPU를 반환할 때, Yield() 시스템 호출로 현재 스레드는 레디 큐에 삽입된다.
   • CPU의 자발적인 양보
3. 스레드의 타임 슬라이스가 종료되어 Timer Interrupt가 발생하여 스레드가 레디 큐에 삽입된다.
   • CPU의 균등한 분배
4. 더 높은 순위의 스레드가 요청한 입출력 작업이 완료되어 인터럽트가 발생하여 스레드를 레디 큐에 삽입한다.
   • 스레드 실행 우선순위를 지킨다.

즉, 스레드 컨텍스트 스위칭이 발생하는 시점과 동일하다. 우선순위 개념이 추가만 되었다.

CPU 스케줄링은 시스템 호출이 발생하면 스레드 스케줄링으로 어떤 스레드를 수행할지 결정하고 디스패처(Dispatcher)에 의해 해당 스레드의 TCB 구조체에서 PC 주소를 CPU에 전달하면 실행상태가 된다.

 

이 때, 스케줄링 코드는 커널 내 목적 프로그램 형태로 저장되어 실행된다.

디스패처 코드는 컨텍스트 스위칭을 실질적으로 실행하는 커널 코드이다.

CPU 스케줄링으로 인한 컨텍스트 스위칭 과정

 

CPU 스케줄링 타입으로는 선점 스케줄링과 비선점 스케줄링이 존재한다.

선점 스케줄링(Preemptive Scheduling)과 비선점 스케줄링(Non-Preemptive Scheduling)

 

• 비선점 스케줄링
  • 현재 실행중인 스레드를 강제로 중단시키지 않는다.
  • 즉, I/O가 발생하거나 Yield, 종료와 같이 CPU가 쉴 때만 스케줄링을 한다는 의미이다.
• 선점 스케줄링 (오늘 날의 방식)
  • 현재 실행중인 스레드를 강제 중단 시키고 다른 스레드를 선택한다.
  • 타이머 인터럽트나 시스템 호출 등으로 스레드에 대한 역할이 끝났을 때 스케줄링 한다.

스케줄링을 하면서 문제가 발생하게 되는데 대표적인 예시가 기아이다.

 

기아(starvation) 현상은 스레드가 레디 큐에서 계속 머무는 상태인데 비선점 스케줄링이든 선점 스케줄링이든 둘 다 발생할 수 있다. 대표적인 예시로 우선순위 시스템에서 더 높은 순위의 스레드가 계속해서 레디큐에 추가되는 경우다.

에이징(aging) 기법을 기아 현상의 해결책으로 두는데 스레드가 대기 큐에서 대기한 시간에 비례해 스케줄링 우선순위를 높이는 기법을 사용한 것이다. 에이징 기법도 처리하는데 오래 걸릴 수는 있지만 가장 높은 순위로 도달하는 것이 보장된다.

 

CPU 스케줄링의 기준(criteria)

• CPU 활용률 (CPU utilization), CPU 사용 시간 비율
• 처리율 (throughput), 시간 당 처리하는 프로세스의 개수
• 공평성 (fariness), CPU를 스레드들에게 공평하게 배분되어야 한다. 
  그렇지 않으면 기아 스레드가 생겨서 무한정 대기하는 현상이 발생한다.
• 응답시간 (response time), 명령에 응답하는데 걸리는 시간이 짧을수록 좋다.
• 대기시간 (waiting time), 스레드가 레디 큐에서 머무르는 시간
• 소요시간 (turnaround time), 스레드가 시스템에서 완료될 때까지 걸린시간
• 시스템 정책 (policy enforcement), 특별한 목적
  실시간 시스템의 특정 시간 설정 등
• 자원 활용률 (resource efficiency)