11-1 CPU 스케줄링 개요

CPU 스케줄링 : CPU 자원을 프로세스에게 공정하고 합리적으로 배분

프로세스 우선순위

• 프로세스마다 다른 우선순위 priority를 고려해야 함

입출력 집중 프로세스 I/O bound process

• 입출력 작업이 많은 프로세스
• 실행 상태보다 입출력 위한 대기 상태가 많음

CPU 집중 프로세스 CPU bound process

• CPU 작업이 많은 프로세스
• 대기 상태보다 실행 상태가 많음

CPU 버스트, 입출력 버스트

• CPU 버스트 : CPU를 이용하는 작업
• 입출력 버스트 : 입출력장치를 기다리는 작업
• 프로세스는 CPU 버스트와 입출력 버스트를 반복하며 실행

스케줄링 큐

운영체제는 CPU를 사용할 프로세스, 메모리에 적재될 프로세스, 특정 입출력장치를 사용할 프로세스를 모두 스케줄링 큐를 구현하여 관리한다.

(자료구조 관점에서 큐는 선입 선출이지만, 스케줄링에서 큐는 반드시 선입선출일 필요 없음)

준비 큐

• CPU를 사용할 준비 상태의 프로세스가 기다리는 줄

1. 준비 상태의 프로세스는 PCB의 준비 큐 마지막에 삽입
2. OS는 PCB들이 큐에 삽입된 순서대로 프로세스 실행. 우선순위가 높은 프로세스를 먼저 실행

대기 큐

• 입출력장치를 이용하기 위해 대기 상태에 있는 프로세스가 기다리는 줄

1. 같은 장치를 요구한 프로세스는 같은 대기 큐에서 기다림
2. 입출력 완료 인터럽트 발생 시, OS는 대기 큐에서 작업 완료된 PCB 찾고, 준비 상태로 변경, 대기 큐에서 제거 -> 준비 큐로 이동

선점형과 비선점형 스케줄링

선점형 preemptive scheduling

• 프로세스가 CPU 차지하고 있어도 OS가 프로세스로부터 자원을 빼앗아 다른 프로세스에게 할당 가능
• 프로세스들에게 자원을 골고루 배분 가능
• 오버헤드 발생 가능

비선점형 non-preemptive scheduling

• 프로세스가 종료되거나 스스로 대기 상태에 들어가기 전까지 자원을 빼앗기지 않음
• 자원 독점
• 오버헤드 적음
• 모든 프로세스가 자원을 골고루 사용 못함

11-2 CPU 스케줄링 알고리즘

스케줄링 알고리즘 종류

1. 선입 선처리 스케줄링 FCFS

• First Come First Scheduling
• 비선점형 스케줄링
• 준비 큐에 삽입된 순서대로 프로세스 처리
• 프로세스가 기다리는 시간이 길어질 수 있음
• 호위 효과 convoy effect
  • CPU를 오래 사용하는 프로세스가 먼저 도착하면, CPU를 짧게 사용하는 프로세스는 오랜 시간을 기다려야 함

2. 최단 작업 우선 스케줄링 SJF

• Shortest Job First Scheduling
• 비선점형 스케줄링
• CPU 이용 시간이 가장 짧은 프로세스부터 실행
• 선점형으로 구현되면 선점형 최단 작업 우선 스케줄링

3. 라운드 로빈 스케줄링

• round robin scheduling
• FCFS에 타임 슬라이스 개념 더해짐
• 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 정해진 시간만큼 돌아가며 CPU 이용
• 선점형 스케줄링
• 타임 슬라이스가 매우 크면 선입 선처리와 같음 - 호위 효과 발생
• 너무 작으면 문맥 교환 비용 너무 큼

4. 최소 잔여 시간 우선 스케줄링 SRT

• Shortest Remaining Time
• 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
• 정해진 타임 슬라이스만큼 CPU 사용, 다음 프로세스로 남은 작업 시간이 가장 적은 프로세스 선택
• 선점형 스케줄링

5. 우선순위 스케줄링

• priority scheduling
• 가장 높은 우선순위 먼저 실행
• 우선순위가 같으면 선입 선처리
• 기아 starvation 현상 가능
  • 먼저 준비 큐에 삽입되었지만 우선순위가 높은 프로세스로 인해 실행 연기
• 에이징 aging 으로 기아 현상 방지
  • 오랫동안 대기한 프로세스의 우선순위를 점차 높임

6. 다단계 큐 스케줄링

• multilevel queue scheduling
• 우선순위 별로 준비 큐를 여러 개 사용
• 우선순위가 가장 높은 큐가 비어있으면, 그 다음 우선순위 큐의 프로세스 처리
• 프로세스 유형별로 우선순위 구분 가능
• 큐별로 타임 슬라이스 다르게 지정 가능
• 큐별로 다른 스케줄링 알고리즘 사용 가능
• 기아 현상 가능

7. 다단계 피드백 큐 스케줄링

• multilevel feedback queue scheduling
• 다단계 큐 스케줄링 + 프로세스는 큐 사이를 이동할 수 있음

1. 새로 준비 상태가 된 프로세스는 우선순위가 가장 높은 큐에 삽입, 타임 슬라이스 동안 실행
2. 프로세스가 해당 큐에서 실행이 안끝나면 다음 우선순위 큐에 삽입
3. 프로세스가 안끝아면 2 를 반복.
4. CPU를 오래 사용하는 프로세스(CPU 집중 프로세스)는 우선순위가 낮아짐, CPU를 적게 사용하는 프로세스(입출력 집중 프로세스)는 우선순위가 높은 큐에서 실행

• 에이징 기법으로 기아 현상 예방
  • 낮은 우선순위 큐에서 오래 기다리는 프로세스를 점차 우선순위 높은 큐로 이동시키기