[운영체제] 5. CPU 스케줄링

도서 기반 내용 정리

운영체제 | Abraham Silberschatz - 교보문고

 

목차

• CPU 스케줄링
• 스케줄링 기준
• 스케줄링 알고리즘

 

CPU 스케줄링

---

CPU-I/O burst cycle

프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.
프로세스 실행은 CPU 버스트 다음 I/O 버스트가 번갈아 실행된다.
마지막 CPU 버스트는 실행 종료하기 위한 요청과 함께 끝낸다.

CPU 스케줄러 (Scheduler)

CPU가 유휴 상태가 될 때, 레디 큐에 있는 어떤 프로세스에게 CPU 코어를 할당할 지 결정한다.

선점 및 비선점 스케줄링

CPU 스케줄링 결정이 발생하는 상황

1. 한 프로세스가 running -> waiting 상태로 전환될 때
   ex) I/O 요청 || 자식 프로세스가 종료되기를 기다리기 위해 wait() 호출할 때
2. 프로세스가 running -> ready 상태로 전환될 때
   ex) 인터럽트 발생 시
3. 프로세스가 waiting -> ready 상태로 전환될 때
   ex) I/O 종료 시
4. 프로세스가 종료할 때

비선점(Nonpreemptive) 스케줄링 방식

• 스케줄링 발생 경우 : 1, 4
• 프로세스가 자발적으로 CPU 제어를 포기하는 경우다.

선점(preemtive) 스케줄링 방식

• 스케줄링 발생 경우 : 1, 2, 3, 4
• 운영체제가강제로 프로세스의 사용권을 통제하는 방식
• CPU를 프로세스로부터 뺏을 수 있는 경우다.

디스패처 (Dispatcher)

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

• Dispatch : 운영체제가 프로세스를 프로세서에 할당하는 것 (ready -> running)

디스패치 지연 (Dispatch latency)

디스패처가 하나의 프로세스를 정지하고, 다른 프로세스 수행을 시작하는 데까지 소요되는 시간

디스패처 역할

 

스케줄링 기준

---

CPU 이용률 (Utilization)

가능한 CPU를 최대한 바쁘게 유지해야한다.
실제 시스템에선 40% ~ 90%까지 범위를 가져야 한다.

처리량 (Throughput)

단위 시간당 완료된 프로세스의 개수

총 처리 시간 (turnaround time)

프로세스의 제출 시간과 완료 시간의 간격이다.
준비큐에서 대기 시간, CPU에서 실행하는 시간, I/O시간을 합한 시간이다.

응답 시간 (response time)

하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간
응답이 시작되는 데까지 걸리는 시간이고, 응답을 출력하는데 걸리는 시간은 아니다.

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

 

스케줄링 알고리즘

---

이러한 스케줄링 알고리즘은 처리 코어가 하나뿐이라고 가정하고 설명한다.

FCFS (First-Come First-Served Scheduling)

CPU를 먼저 요청하는 프로세스에게 CPU를 할당해주는 스케줄링

• 비선점 스케줄링 방식
• 큐로 쉽게 관리할 수 있다.
• 프로세스가 레디 큐에 진입 시, PCB를 큐의 끝에 연결한다.
  CPU가 가용 상태가 되면, 준비 큐의 앞부분에 있는 프로세스에 할당한다.
• 단점 : 종종 평균 대기 시간이 매우 길 수 있다.
• 호위 효과 (convoy effect) : 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하길 기다리는 것

 

SJF (Shortest-Job-First Scheduling)

CPU가 이용 가능해지면, 다음 프로세스 중 가장 작은 CPU 버스트(프로세스 수행 시간)를 가진 프로세스에게 할당하는 알고리즘

• 선점형 및 비선점형 스케줄링 모두 해당한다.
• 동일한 CPU 버스트를 가진 프로세스는 FCFS를 적용한다.
• 새로 준비큐에 들어온 프로세스의 실행시간이 실행중인 프로세스의 남은 시간보다 짧으면,
  선점형 SJF 알고리즘은 현재 실행하는 프로세스를 선점할 것이다.
• 최소의 평균 대기 시간을 가진다.
• 최적의 알고리즘이지만, 다음 CPU 버스트의 길이를 알 방법이 없다.
  따라서 그 값을 예측한다.

 

라운드 로빈 스케줄링 (Round-Robin Scheduling, RR Scheduling)

레디 큐를 돌면서 한 프로세스에 한 번의 시간 할당량(time quan-tum) 동안 CPU를 할당하는 알고리즘

• 선점형 스케줄링
• 여기서 준비 큐는 원형 큐로 동작한다.
  시간 할당량이 끝났을 때 종료되지 못한 프로세스의 PCB는 큐의 제일 마지막에 추가된다.
• 시간 할당량 크기에 매우 많은 영향을 받는다.
  • 시간 할당량이 매우 크면 -> FCFS 알고리즘과 같아진다.
  • 시간 할당량이 매우 적으면 -> 매우 많은 context switch가 발생한다.
  • 따라서 시간 할당량이 context switch 시간과 비교해 더 커야한다.
• 총 처리 시간 또한 시간 할당량의 크기에 좌우된다.
  시간 할당량의 크기가 크더라도, 반드시 개선되진 않는다.

 

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

특정 기준으로 프로세스에 우선순위를 부여해 우선순위에 따라 CPU를 할당하는 알고리즘

• 선점형, 비선점형 모두 해당한다.
  
  • 선점형 -> 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스보다 높다면, CPU를 선점한다.
  • 비선점형 -> 레디큐의 제일 처음에 새로운 프로세스를 넣는다.
• 우선순위가 같은 경우 FCFS로 스케줄된다.
• 기아 상태(Starvation) 문제 : 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생하는 문제
• Aging : 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시켜 기아 문제를 해결한다.

 

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

프로세스 우선순위에 따라 여러 개의 큐로 분할하고,
가장 높은 우선순의 큐부터 프로세스를 스케줄하는 방식이다.

• 라운드 로빈과 결합하면 효과적이다.
  가장 높은 큐에 여러 프로세스가 있는 경우 라운드 로빈 순서로 실행된다.

• 프로세스 유형에 따라 프로세스를 여러 개의 개별 큐로 분할하기 위해
  다단계 큐 스케줄링 알고리즘을 사용할 수도 있다.
• 예를 들어 백그라운드(배치) 큐는 FCFS 알고리즘에 의해 스케줄 되고,
  포그라운드(대화형) 큐는 RR 알고리즘에 의해 스케줄 될 수 있다.
• 일반적으로 고정 우선순위의 선점형 스케줄링으로 구현된다.

 

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

다단계 큐와 유사하지만, 프로세스가 하나의 큐에 종속되는 것이 아닌, 큐들 사이를 이동하는 것을 허용하는 방식이다.

• 다단계 큐 스케줄링은, 한 큐에 할당되면 프로세스 끝날때까지 해당 큐에서 대기해야 한다.
  이에 비해 융통성이 더 높다.
• CPU 버스트 타임을 이용해 프로세스의 우선순위를 실시간으로 변경시킬 수 있다.
  높으면 -> 낮은 곳으로 이동
  낮으면 -> 높은 곳으로 이동
• 낮은 우선순위 큐에서 너무 오래 대기하는 프로세스의 기아 문제를 예방할 수 있다.