[혼자 공부하는 컴퓨터구조+운영체제] Chapter 11 CPU 스케줄링

Chapter 11 CPU 스케줄링

1. CPU 스케줄링 개요

프로세스 우선순위/ 스케줄링 큐/ 선점형과 비선점형 스케줄링

 

CPU 스케줄링(CPU scheduling)

• 운영체제가 프로세스에게 공정하고 합리적으로 CPU 자원을 배분하는 것
• 컴퓨터 성능하고 직결

프로세스 우선순위

프로세스마다 우선순위가 다름

-> 우선순위 ↑ 프로세스 = 빨리 처리해야 하는 프로세스(ex. 입출력 프로세스)

 

프로세스는 실행 상태, 대기 상태 반복하며 실행

• 입출력 집중 프로세스(I/O bound process)
  • 입출력 작업 ↑ 프로세스
  • ex. 비디오 재생, 디스크 백업 작업
  • 실행 상태 < 입출력 위한 대기 상태
  • *입출력 버스트 ↑ 프로세스
• CPU 집중 프로세스(CPU bound process)
  • CPU 작업 ↑ 프로세스
  • ex. 복잡한 수학 연산, 컴파일, 그래픽 처리
  • 실행 상태 > 입출력 위한 대기 상태
  • *CPU 버스트 ↑ 프로세스

• 입출력 버스트(I/O burst): 입출력장치 기다리는 작업
• CPU 버스트(CPU burst): CPU 이용하는 작업

=> 프로세스 중요도 맞게 프로세스가 CPU 이용 -> 우선순위(priority) 부여

프로세스의 PCB에 우선순위 명시, PCB에 적힌 우선순위 기준 -> 먼저 처리할 프로세스 결정

---

스케줄링 큐(scheduling queue)

운영체제가 매번 모든 PCB 검사하여 먼저 자원 이용할 프로세스 결정 -> 비효율적

=> (CPU 사용하고 싶은 프로세스/ 메모리에 적재되고 싶은 프로세스/ 특정 입출력장치 사용하고 싶은 프로세스) 줄 세움

-> 스케줄링 큐로 구현하고 관리(효율적 스케줄링)

*큐: 선입선출(First In First Out) 자료 구조 But, 스케줄링에서 반드시 X

• 준비 큐(ready queue)
  • CPU를 이용하기 위해 기다리는 줄
• 대기 큐(waiting queue)
  • 입출력장치 이용하기 위해 기다리는 줄

---

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

• 선점형 스케줄링(preemptive scheduling)
  • 하나의 프로세스가 자원 사용 O -> 운영체제) 자원 강제로 빼앗아 다른 프로세스에 할당
  • 하나의 프로세스가 자원 사용 독점 X
  • 프로세스마다 정해진 시간만큼 CPU 사용, 타이머 인터럽트 발생 -> 운영체제) 자원 빼앗아 다음 프로세스에 할당 
  • (+) 한 프로세스의 자원 독점 막고 프로세스들에 자원 골고루 배분 O
  • (-) 문맥 교환 과정에서 오버헤드 발생할 수 있음
• 비선점형 스케줄링(non-preemptive scheduling)
  
  • 하나의 프로세스가 자원 사용 O -> 종료 or 스스로 대기 상태 전에 다른 프로세스가 끼어들 수 X
  • 하나의 프로세스가 자원 사용 독점 O
  • (+) 문맥 교환 과정에서 발생하는 오버헤드 ↓
  • (-) 모든 프로세스 골고루 자원 사용 X

---

2. CPU 스케줄링 알고리즘

선입 선처리 스케줄링/ 최단 작업 우선 스케줄링/ 라운드 로빈 스케줄링
/ 우선순위 스케줄링/ 다단계 큐 스케줄링/ 다단계 피드백 큐 스케줄링

선입 선처리 스케줄링(FCFS; First Come First Served Scheduling)

• 준비 큐에 삽입된 순서대로 프로세스 처리(비선점형 스케줄링 방식)
• CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식
• 공정해보이지만, 프로세스가 기다리는 시간 ↑ 확률 O
• 호위 효과(convoy effect): CPU 버스트가 ↑ 프로세스가 준비 큐 앞에 오면 그 뒤에 ↓ 프로세스도 기다려야 함
  • ex. 프로세스 A: 17ms/ B: 5ms/ C: 2ms -> 프로세스 C는 2ms 실행하기 위해 22ms(17 + 5) 기다려야 함

최단 작업 우선 스케줄링(SJF; Shortest Job First Scheduling)

• 준비 큐에 삽입된 프로세스 중 CPU 이용 시간의 길이가 가장 ↓ 프로세스부터 실행
• 비선점형 스케줄링 알고리즘
  • But, 선점형으로 구현 O -> 선점형 최단 작업 우선 스케줄링: 최소 잔여 시간 우선 스케줄링

라운드 로빈 스케줄링(round robin scheduling)

• 선입 선처리 스케줄링 + 타임 슬라이스
  타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
  • 타임 슬라이스 ↑ -> ~= 선입 선처리 스케줄링 => 호위 효과
  • 타임 슬라이스 ↓ -> 문맥 교환에 발생하는 비용 ↑ => CPU) 프로레스 처리 < 프로세스 전환
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용(선점형 스케줄링) 

최소 잔여 시간 우선 스케줄링(SRT; Shortest Remaining Time)

• 최단 작업 우선 스케줄링 알고리즘(: 작업 시간 ↓ 프로세스부터 처리)
  + 라운드 로빈 알고리즘(: 정해진 타임 슬라이스만큼 돌아가며 CPU 사용)
• => 정해진 타임 슬라이스만큼 CPU 사용, 다음 프로세스는 남아있는 작업 시간 가장 ↓ 프로세스 선택

우선순위 스케줄링(priority scheduling)

• 프로세스에 우선순위 부여, 가장 ↑ 우선순위 가진 프로세스부터 실행
  • 우선순위 같은 프로세스 -> 선입 선처리
• 최단 작업 우선 스케줄링(: 작업 시간 ↓ 프로세스에 ↑ 우선순위)
  , 최소 잔여 시간 우선 스케줄링(: 남은 시간 ↓ 프로세스에 ↑ 우선순위)
  => 우선순위 스케줄링의 일종
• (-) 기아(starvation) 현상: 우선순위 ↓ 프로세스는 (준비 큐에 먼저 삽입되었어도) 실행 계속 연기될 수 있음
• (해결) 에이징(aging): 오랫동안 대기한 프로세스 우선순위 높이는 방식

다단계 큐 스케줄링(multilevel queue scheduling)

• 우선순위별로 준비 큐를 여러 개 사용(우선순위 스케줄링의 발전된 형태)
• 우선순위 가장 ↑ 큐에 있는 프로세스 먼저 처리, 비면 그 다음 우선순위 큐에 있는 프로세스 처리
• (+) 프로세스 유형별로 우선순위 구분하여 실행
• (+) 큐별로 타임 슬라이스 여러 개 지정, 다른 스케줄링 알고리즘 사용
• (-) 프로세스들이 큐 사이 이동 X(= 기아 현상) -> (해결) 다단계 피드백 큐 스케줄링

다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)

• 다단계 큐 스케줄링의 발전된 형태
• 프로세스들이 큐 사이를 이동 O -> 에이징 기법(: ↓ 우선순위 큐에서 오래 기다리는 프로세스 -> 점차 우선순위 ↑ 큐로 이동)
• 새로 준비 상태가 된 프로세스 O -> 우선순위 가장 ↑ 우선순위 큐에 삽입, 일정 시간(타임 슬라이스) 동안 실행
  • IF. 프로세스가 해당 큐에서 실행 끝 X -> 다음 우선순위 큐에 삽입되어 실행
• => CPU를 비교적 오래 사용해야 하는 CPU 집중 프로세스 자연스럽게 우선순위 ↓
  , CPU를 비교적 적게 사용하는 입출력 집중 프로세스들 자연스럽게 우선순위 ↑ 큐에서 실행

---

출처

[한빛미디어] 혼자 공부하는 컴퓨터 구조+운영체제