5. CPU 스케줄링

0. 서론

프로세스에서 실행하는 작업은 두 가지로 나뉨

• CPU Burst
  → CPU를 사용하는 작업
• I/O Burst
  → 입출력장치를 사용하는 작업

 

CPU Bound Process & I/O Bound Process

• 각각 CPU 집중 프로세스와 I/O 집중 프로세스를 의미
  → CPU 집중 프로세스는 소수의 긴 CPU Burst로 구성됨
  → I/O 집중 프로세스는 다수의 짧은 CPU Burst로 구성됨
• 일반적으로 컴퓨터 시스템 내에서 수행되는 프로세스는 I/O 집중 Process가 더 많음
  → 이는 대부분 대화형 작업으로 사용자와 인터랙션을 해가며 프로그램을 수행
• 두 프로세스가 동시에 CPU를 요구했다면?
  → I/O Bound Process에 먼저 CPU를 할당하는 것이 효율적
  → I/O Bound Process는 입출력장치가 입출력 작업을 완료하기 전까지는 어차피 Blocked 상태가 될 예정이기 때문

 

이렇듯 모든 프로세스가 CPU를 차례대로 돌아가며 사용하는 것보다 각각의 상황에 맞게 CPU를 배분하는 것이 더 효율적이기에 CPU 스케줄링이 등장

 

1. CPU Scheduler & 디스패처

CPU Scheduler (단기 스케줄러)

• Ready Queue에 있는 프로세스 중 CPU를 할당할 프로세스를 선택하는 역할을 수행
  → 하드웨어, 소프트웨어가 아닌 커널의 일부 (코드)

디스패처 (Dispatcher)

• CPU 제어권을 CPU 스케줄러에 의해 선택된 프로세스에 이양하는 역할을 수행
  → 이 과정을 문맥 교환 (Context Switch)이라고 함
  → 하드웨어, 소프트웨어가 아닌 커널의 일부 (코드)

CPU 스케줄링이 필요한 경우

• 1. Running → Blocked
  → I/O 시스템 콜
• 2. Running → Ready
  → Timer 인터럽트
• 3. Blocked → Ready
  → I/O 완료 인터럽트
  
• 4. Running → Terminated
  → 프로세스 종료

비선점형 스케줄링 (Non-preemptive Scheduling)

• 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전 까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식
• 위의 1번과 4번의 경우가 해당 

선점형 스케줄링 (Preemptive Scheduling)

• 프로세스가 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식
• 위의 2번과 3번의 경우가 해당

 

2. 스케줄링 알고리즘 성능 척도

시스템 입장에서의 성능 척도

• CPU Utilization (이용률)
  → 전체 시간 중 CPU가 일한 시간의 비율
• Throughput (처리량)
  → 단위 시간당 CPU가 처리한 프로세스의 개수

 

프로세스 입장에서의 성능 척도

• Turnaround Time (턴어라운드 타임, 소요 시간)
  → 프로세스가 CPU를 요청한 시점부터 CPU Burst가 끝날 때까지 걸린 총시간 (대기 시간 포함)
  
• Waiting Time (대기 시간)
  → CPU Burst 중 프로세스가 Ready Queue에서 대기한 시간의 합
• Response Time (응답 시간)
  → 프로세스가 Ready Queue에서 최초로 CPU를 얻기까지 대기한 시간

 

3. FCFS 스케줄링 (First Come First Served Scheduling)

Ready Queue에 삽입된 순서대로 프로세스를 처리하는 방식

• 비선점형 스케줄링

 

단점

• 호위 효과 발생 (Convoy Effect) 
  → CPU Burst가 짧은 프로세스가 CPU Burst가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상

 

4. SJF 스케줄링 (Shortest Job First Scheduling)

Ready Queue에 삽입된 프로세스 중 (추정) CPU Burst Time이 가장 짧은 프로세스부터 실행하는 방식

• 기본적으로 비선점형 스케줄링으로 분류
• 선점형 스케줄링으로 구현 가능 → SRT 스케줄링

 

SRT 스케줄링 (Shortest Remaining Time Scheduling)

• 현재 수행 중인 프로세스의 남은 CPU Burst Time보다 더 짧은 CPU Burst Time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
• 최소 평균 대기 시간 보장 (Optimal)

 

5. 우선순위 스케줄링

프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 방식

• 비선점형 스케줄링 및 선점형 스케줄링으로 모두 구현 가능
• 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
• 예) SJF 스케줄링, SRT 스케줄링 등

 

단점 및 해결

• 기아 (Starvation)
  → 우선순위가 낮은 프로세스의 실행이 우선순위가 높은 프로세스에 의해 계속해서 연기되는 현상
• 에이징 (Aging)
  → 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
  → 기아 현상 해결 가능

 

6. Round Robin 스케줄링

정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 방식

• 선점형 스케줄링
• 타임 슬라이스가 끝나면 프로세스는 타이머 인터럽트에 의해 다음 프로세스에 CPU를 선점당하고 Ready Queue의 맨 뒤에 삽입됨

 

타임 슬라이스의 크기가 매우 중요함

• 타임 슬라이스의 크기가 지나치게 크다면
  → 사실상 FCFS 스케줄링과 다를 바 없음
• 타임 슬라이스의 크기가 지나치게 작다면
  → 문맥 교환 오버헤드 증가

 

일반적으로 SJF 스케줄링보다 Turnaround Time이 길지만, Response Time은 짧음

• Round Robin 스케줄링의 목적은 CPU Burst Time이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 동시에, CPU Burst Time이 긴 프로세스가 불이익을 당하지 않도록 하는 것
• 프로세스의 CPU Burst Time에 비례해 Turnaround Time이 증가하게 되므로 매우 합리적

 

7. Multilevel Queue

일반적으로 성격이 다른 프로세스들을 별도로 관리하고, 프로세스 성격에 맞는 스케줄링을 적용하기 위해 Ready Queue를 별도로 두는 방식

• 각 큐에 대한 스케줄링 및 각 큐 내 프로세스에 대한 스케줄링 필요
• Foreground Queue
  → Interactive (대화형) 프로세스 삽입
  → Response Time을 짧게 하기 위해 Round Robin 스케줄링을 주로 사용
• Background Queue
  → Batch (계산 위주) 프로세스 삽입
  → Response Time이 큰 의미를 가지지 않기 때문에 문맥 교환 오버헤드를 줄이기 위해 FCFS 스케줄링을 주로 사용

 

Multilevel Feedback Queue

• CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 Multilevel Queue와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능
  → 프로세스가 도착 시 가장 높은 우선순위의 Queue에 삽입
  → 프로세스가 정해진 타임 슬라이스 내에 작업을 처리하지 못할 시 더 낮은 우선순위의 Queue로 강등시킴
  → 일정 주기마다 모든 작업을 가장 높은 우선순위의 Queue로 승격시킴
  → 따라서 이 방식은 CPU Burst Time이 짧은 프로세스에 더 많은 기회 제공

 

8. 그 외

Multi-Processor Scheduling

• CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
  → Homogeneous : 동질의
  → Heterogeneous : 이질의
  
• Homogeneous Processor인 경우
  → Ready Queue에 프로세스를 한 줄로 세워서 각 프로세서가 알아서 꺼내 가게 할 수 있음
• Heterogeneous Processor인 경우
  → 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우 문제가 더 복잡해짐
  → 일부 프로세서에 Job이 몰리지 않도록 부하를 적절히 분산하는 Load Balancing 메커니즘이 필요
• Symmetric Multiprocessing (SMP)
  → 각 프로세서가 각자 알아서 스케줄링 결정
• Asymmetric Multiprocessing (AMP)
  → 하나의 프로세서가 스케줄링 및 데이터 접근을 책임지고 나머지 프로세서는 거기에 따름

 

Real-Time Scheduling

• Hard Real-Time Systems
  → 정해진 시간 내에 반드시 끝내도록 스케줄링
• Soft Real-Time Systems
  → 일반 프로세스에 비해 높은 우선순위를 갖도록 스케줄링

 

Thread Scheduling

• Local Scheduling
  → User Level Thread의 경우 사용자 수준의 Thread Library가 어떤 Thread를 스케줄링할지 결정 (운영체제가 Thread의 존재를 모름)
  
• Global Scheduling
  → Kernel Level Thread의 경우 일반 프로세스와 마찬가지로 커널의 CPU 스케줄러가 어떤 Thread를 스케줄링할지 결정

 

이화여자대학교 반효경 교수님의 운영체제 강의를 정리한 글입니다.

http://www.kocw.net/home/cview.do?cid=3646706b4347ef09

운영체제

 

또한 반효경 교수님의 "운영체제와 정보기술의 원리" 책을 참고하였습니다.

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=238716482

운영체제와 정보기술의 원리