[OS] 공룡책_5 CPU 스케줄링

5.1 기본 개념

• 다중 프로그래밍의 목적은 CPU 이용률을 최대화 하기 위해 항상 실행 중인 프로세스를 가지게 하는 데 있다.
• 거의 모든 컴퓨터 자원들은 사용되기 전에 스케줄 된다.

5.1.1 CPU-I/O 버스트 사이클

• 프로세스의 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.
• 짧은 CPU 버스트가 많이 있으며, 긴 CPU 버스트는 적다.
• I/O중심의 프로그램은 전형적으로 짧은 CPU 버스트를 많이 가진다.
  

5.1.2 CPU 스케줄러

• CPU가 사용 가능 상태가 되면 운영체제는 준비 큐에 있는 프로세스 중 하나를 선택해서 실행한다.
• 선택 절차는 CPU 스케줄러에 의해서 수행된다.

5.1.3 선점 및 비선점 스케줄링

비선점 스케줄링

• CPU가 한 프로세스에 할당되면 프로세스가 종료하거나 대기 상태로 전환할 때까지 CPU를 점유한다.

선점 스케줄링

• CPU 스케줄러에 의해 점유 상태를 강제로 가져올 수 있다.
• 두 프로세스가 같은 데이터를 공유할 때, 선점 스케줄링에 의해 데이터의 일관성이 깨질 수 있다.
  • 한 프로세스가 자료를 갱신하는 동안 다른 프로세스가 실행 가능 상태가 되어 선점할 경우.
• 현재 대부분의 최신 운영체제는 선점 스케줄링 알고리즘 사용.

5.1.4 디스패처 (Dispatcher)

CPU 스케줄러에 의해 선택된 프로세스에 CPU 코어 제어를 주는 모듈이다.

• 프로세스 간 문맥 교환
• 사용자 모드로 전환
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

디스패처는 모든 문맥 교환 시 호출되므로, 빠르게 수행되어야 한다.

5.2 스케줄링 기준

• CPU 이용률(utilization)

• 처리량(throughtput): 단위시간당 완료된 프로세스의 개수

• 총 처리 시간(turnaround time): 프로세스의 제출 시간과 완료시간의 간격이다.
  

• 대기 시간(waiting time): 프로세스가 준비큐에서 대기한 시간의 합

• 응답 시간(response time): 대화식 시스템에서는 총처리 시간이 최선의 기준이 아닐 수 있다. 응답시간은 하나의 요구에 대한 응답이 나올 때까지 걸리는 시간이다.

CPU 이용률과 처리량을 최대화하고, 목적에 맞게 총 처리 시간, 대기 시간, 응답 시간을 최소화 하는 것이 바람직하다.

5.3 스케줄링 알고리즘

5.3.1 선입 선처리 스케줄링 (First-Come First-Served, FCFS)

• 먼저 요청한 프로세스가 CPU를 할당 받는다.

• 일반적으로 평균 대기 시간이 길어진다. -> 바람직하지 않다.

호위 효과(convoy effect)

모든 다른 프로세스들이 하나의 긴 CPU 사용 프로세스가 CPU를 양도하기를 기다리는 것.

5.3.2 최단 작업 우선 스케줄링 (Shortest-Job-First, SJF)

• 가장 작은 CPU 버스트를 가진 프로세스에게 CPU를 먼저 할당한다.

• 최적이긴 하지만, 다음에 올 프로세스의 CPU 버스트의 길이를 알 수 없기 때문에 엄밀한 구현은 불가능하다. -> 그 값을 예측해서 사용한다.

최소 잔여 시간 우선 스케줄링 (shrtest remaining time first)

• SJF는 선점형이거나 비선점형일 수 있다.
• 선점형일 경우 실행되고 있는 프로세스의 잔여시간보다 새로 들어온 프로세스의 CPU 버스트가 더 짧은 경우 CPU를 선점한다.

5.3.3 라운드 로빈 스케줄링 (Round-Robin scheduling)

• 시간할당량(time quantum)또는 타임 슬라이스(time slice)라고 하는 작은 단위의 시간을 정의한다.
• 스케줄러는 준비큐를 돌면서 한 프로세스에 한 번의 시간할당량 동안 CPU를 할당한다.
• RR 알고리즘의 성은 시간 할당량의 크기에 매우 많은 영향을 받는다.
  • 너무 크면 FCFS와 다를 바가 없다.
  • 너무 작으면 문맥 교환에서 발생하는 오버해드가 커진다.

5.3.4 우선순위 스케줄링 (Priority Scheduling)

SJF는 우선순위 스케줄링의 특수한 경우이다.
우선순위는 내부적, 외부적으로 정의될 수 있다.

내부적 정의

• 시간 제한
• 메모리 요구
• 열린 파일 수
• 평균 I/O 버스트
• 평균 CPU 버스트

외부적 정의

• 프로세스 중요성
• 컴퓨터 사용을 위해 지불되는 비용 유형과 양
• 작업 후원 부서
• 정치적 요인

우선순위 스케줄링 알고리즘의 주요 문제는 무한 봉쇄(indefinite blocking)또는 기아상태(starvation)이다.

우선순위가 낮은 프로세스들이 CPU를 무한히 대기하다가 계속해서 우선순위가 밀려서 CPU자원을 사용하지 못 하는 경우를 의미한다.

해결방안으로 노화(aging)이 사용된다.
대기하는 프로세스의 우선순위를 점진적으로 증가시킨다.

5.3.5 다단계 큐 스케줄링 (Multilevel Queue Scheduling)

각 프로세스 유형마다 별도의 큐를 운영하고, 각 큐마다 자체 스케줄링 알고리즘을 가지는 방식이다.

• 프로세스 유형에 따라 응답 시간 요구사항이 다를 수 있다.
• 프로세스 유형마다 우선순위가 다를 수 있다.
• 큐와 큐 사이의 스케줄링도 반드시 필요하다.

5.3.6 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.

• 낮은 우선순위의 큐에서 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다.
• 기아상태를 방지할 수 있다.

다단계 피드백 큐 스케줄러는 가장 일반적인 CPU 스케줄링 알고리즘이다.
설계중인 특정 시스템에 부합하도록 구성이 가능하다.

5.4 스레드 스케줄링

대부분 최신 운영체제에서는 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드이다.

• 사용자 수준 스레드는 라이브러리에 의해 관리되고 커널은 그들의 존재를 알지 못한다.
• CPU에서 실행되기 위해 사용자 수준 스레드는 커널 수준 스레드에 연결돼야 한다.

5.4.1 경쟁 범위 (Contetion Scope)

사용자 수준 스레드와 커널 수준 스레드의 차이 중 하나는 그들이 어떻게 스케줄 되느냐에 있다.

프로세스 경쟁 범위(Process-Contention Scope, PCS)

• 사용자 수준 스레드의 스케줄은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁한다.

• 사용자 수준 스레드가 스케줄되는 것은 실제로 CPU상에서 실행 중이라는 것을 의미하지 않는다.

  시스템 경쟁 범위(System-Contention Scope, SCS)

• CPU상에 어떤 커널 스레드를 스케줄 할 것인지 결정한다.

• Windows, Linux같은 일대일 모델을 사용하는 시스템은 SCS만을 사용하여 스케줄 한다.