[쉽게 배우는 운영체제] 4-1. CPU 스케줄링

조성호 님의 "쉽게 배우는 운영체제" 책을 정리한 포스팅 입니다

 

1. 스케줄링 단계

고수준 스케줄링

• 시스템 내의 전체 작업 수 조절
• 동시에 실행 가능한 프로세스의 총 개수를 제한
• 어떤 프로세스를 실행 대기열에 추가할지 결정

 

중간 수준 스케줄링

• 시스템의 활성 프로세스 수를 조절함
• 스왑, 프로세스 상태 전환 의 방법 사용
• 메모리 자원 관리 및 시스템 부하 조절

 

저수준 스케줄링

• 준비 상태에 있는 프로세스 중에서 어떤 것을 실행할지 결정
  • 스케줄링 알고리즘 사용
  • CPU 자원 할당 최적화
• 프로세스 상태 관리
  • 프로세스의 상태 간의 전환을 관리

 

2. 스케줄링 종류

선점형 스케줄링

• OS가 실행중인 프로세스의 CPU를 강제로 빼앗을 수 있는 방식
• 대부분의 저수준 스케줄러가 채택함

 

인터럽트

• CPU가 OS로부터 인터럽트를 받으면, 현재 실행 중인 작업을 중단하고 인터럽트부터 처리
• 인터럽트 처리가 완료되면 원래의 작업으로 돌아감

 

비선점형 스케줄링

• OS가 실행중인 프로세스의 CPU를 강제로 빼앗을 수 없는 방식
• 과거 일괄 작업 시스템에서 채택한 방식

 

3. 스케줄링 고려사항

전면 프로세스

• 사용자와 상호작용이 가능한 프로세스
  • 사용자의 요구에 즉각 반응해야 함
• 높은 우선순위 부여

 

후면 프로세스

• 사용자와 상호작용이 없는 프로세스
• 낮은 우선순위 부여
  • 시스템 자원이 유휴 상태일 때 실행되도록 해야 함

 

프로세스 우선순위

• CPU 스케줄러는 프로세스에 우선순위를 부여하여 스케줄링함
• 사용자가 프로세스의 우선순위를 정할 수 있음

 

CPU 집중 프로세스

• CPU를 많이 사용하는 프로세스
• CPU 버스트가 긴 작업이 주를 이룸
• 멀티코어 활용 가능성 높음
• 공정한 자원 분배 중요 (RR, Priority-based Scheduling)

 

CPU 버스트

• 프로세스가 CPU를 할당받아 연속적으로 실행되는 시간 구간

 

I/O 집중 프로세스

• 입출력 작업을 많이 수행하는 프로세스
• 스케줄링 요구 사항
  • 자주 대기 상태로 전환되므로 빠르게 복귀할 수 있도록 스케줄링 필요
  • SJF, Multilevel Queue Scheduling

 

4. 다중 큐

우선순위 부여 방식

고정 우선순위 방식

• 프로세스가 끝날때까지 바뀌지 않음

 

변동 우선순위 방식

• 우선순위가 프로세스 작업 중간에 변하는 방식

 

준비 상태

• 우선순위 큐로 PCB를 관리함
• 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입됨
• CPU 스케줄러는 우선순위가 가장 높은 큐의 맨 앞에 있는 프로세스에 CPU를 할당함

 

대기 상태

• 입출력 장치 별 프로세스 관리
• 여러 개의 PCB를 동시에 꺼내 준비 상태로 옮김

 

5. 스케줄링 알고리즘

선택 기준

• CPU 사용률: CPU가 사용된 시간
• 처리량: 단위 시간 당 작업을 마친 프로세스의 수
• 대기 시간: 작업을 시작하기 전까지 대기하는 시간
• 응답 시간: 프로세스 시작 후 첫번째 출력 또는 반응이 나올 때까지 걸리는 시간
• 실행 시간: 작업이 시작된 후 종료되기까지 시간
• 반환 시간: 대기시간을 포함하여 실행이 종료될 때까지의 시간

 

비선점형 알고리즘

FCFS (First Come First Served)

• 준비 큐에 도착한 순서대로 CPU 할당
• 일괄 처리 작업 시스템에서 사용함 
  • i/o call 시, context switch X
  • 전체 시스템 효율성이 떨어짐

 

SJF (Shortest Job First)

• 준비 큐에 있는 프로세스 중, 실행 시간이 가장 짧은 작업부터 CPU 할당
• OS가 종료 시간을 정확히 예측하기 어려움
• 공평하지 못함

 

HRN (Highest Response Ratio Next Scheduling)

• SJF 스케줄링에서 발생할 수 있는 Starving 문제를 해결하기 위해 설계됨
• 최고 응답률 우선이라는 기준을 사용하여 스케줄링함
• Response Ratio
  • = Waiting Time + Service Time / Service Time
  • 대기 시간이 길수록 실행 시간이 짧을수록 응답률이 높아짐
  • 대기 시간도 고려하여 응답률을 계산하므로 Starving 현상이 완화됨
• 여전히 공평성이 부족함

 

선점형 알고리즘

Round Robin

• 순환 순서 방식
  • 한 프로세스가 자신의 time slice동안 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
  • 모든 작업이 완료될 때까지 계속 순환하면서 실행됨

 

SRT (Shortest Remaining Time)

• SJF와 Round Robin 방식을 혼합
• 성능이 좋지 않음
• 종료 시간을 예측하기 어려워 Starving 현상이 일어남

 

다단계 큐

• 우선순위에 따라 준비 큐를 여러 개 사용
• 각 단계 큐에 Round Robin 방식 사용
• 상위 우선순위 큐의 작업이 끝나기 전까지 하위 큐 프로세스 작업 수행 불가
• 우선순위에 따라 다양한 스케줄링 가능 (타임 슬라이스 조절 등)

 

다단계 피드백 큐

• 우선순위가 낮은 프로세스에 불리한 다단계 큐 문제를 보완
• CPU를 사용하고 난 프로세스의 우선순위가 낮아짐