2-3) 운영체제 - CPU 스케줄링

(참고: Fastcampus 강의, 강민철의 인공지능 시대 필수 컴퓨터 공학 지식)

3. CPU 스케줄링

Contents

1. 프로세스 우선순위
2. 스케줄링 큐
3. 선점형 vs. 비선점형 스케줄링
4. CPU 스케줄링 알고리즘

(1) 프로세스 우선순위

a) 스케줄링이란?

• 모든 프로세스(및 스레드는), 실행 되기 위해서 자원을 필요로 한다!

• OS가 공정/합리적으로 자원을 배분하는 방법은?

  \(\rightarrow\) “스케줄링”

b) 우선 순위

정해진 시간마다 돌아가면서 사용…? No!

\(\rightarrow\) 프로세스마다 “우선 순위”가 다르기 때문에!

우선 순위 (priority)를 확인하는 방법

• ps -el 명령어를 사용하면 프로세스의 상세한 정보
  • 우선순위(priority) 관련 정보는 다음 두 컬럼에서 확인

컬럼	의미 (둘 다 낮을수록 높은 우선순위)
PRI	커널에서 사용하는 실제 우선순위 값 (Priority)
NI	nice 값. 사용자가 설정하는 우선순위 힌트 (nice value)

• PRI (Priority): 실제 CPU 스케줄러가 참고하는 우선순위 (숫자가 낮을수록 우선순위 높음).
• NI (nice value): 사용자가 조정할 수 있는 값. 범위는 -20 (가장 높은 우선순위) ~ 19 (가장 낮은 우선순위). 기본은 0.

$$ ps -el
F S UID   PID PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
4 S 1000 1234  1000 0  20   0 -   1234 -      pts/0    00:00:00 bash
4 R 1000 1235  1234 5  20   0 -   4567 -      pts/0    00:00:01 python

c) 우선 순위 차이를 보이는 대표적인 프로세스 유형

“I/O bound” process & “CPU bound” process

둘은 어떻게 구분됨?

• 프로세스가 어떤 자원을 더 많이 사용하는지에 따라 나뉨!
• OS가 이 둘을 다르게 우선순위(priority) 처리하는 이유와도 관련이 있음
  • I/O Bound: 높은 우선순위. CPU를 잠깐만 사용하므로
  • CPU Bound: 낮은 우선순위. CPU를 오래 사용하므로

I/O Bound Process (입출력 중심 프로세스)

• 특징: CPU는 잠깐만 사용하고, 대부분의 시간을 입출력(I/O) 작업에 소비

  (예: 디스크 읽기, 네트워크 통신, 사용자 입력 대기 등)

• 예시: 텍스트 편집기, 웹서버, DB 쿼리 대기

• 운영체제 정책:

  이 프로세스들이 빨리 I/O를 마치고 다시 대기하지 않도록 높은 우선순위를 줌

  → I/O 장치 자원을 더 효율적으로 사용하려는 목적

CPU Bound Process (계산 중심 프로세스)

• 특징: 거의 모든 시간을 CPU 계산에 소비

  (예: 대규모 행렬 곱, 이미지 처리, 머신러닝 학습 등)

• 예시: 과학 시뮬레이션, 대규모 연산 프로그램

• 운영체제 정책:

  CPU 자원을 너무 독점하지 않도록 상대적으로 낮은 우선순위를 설정

  → 다른 I/O 중심 프로세스들이 기회를 얻도록 함

구분	I/O Bound	CPU Bound
주 활동	I/O (디스크, 네트워크 등)	계산/연산
CPU 사용 시간	짧음	김
우선순위 (일반적)	높음	낮음
목적	빠르게 I/O 처리 후 다시 대기	효율적으로 CPU 스케줄링 조정

(2) 스케줄링 큐

a) 한정된 자원

자원은 한정, but 실행 중인 프로세스는 여러 개!

\(\rightarrow\) 프로세스들의 요구 사항을, 일목 요연하게 관리하는 방법은??

b) 스케줄링 큐(Scheduling Queue)란?

OS가 CPU 할당을 기다리는 프로세스들을 정리해 놓은 대기 줄

( = 프로세스들을 상태별로 줄 세워 놓는 시스템의 “대기열” )

c) 스케줄링 큐의 종류

1. Job Queue: 시스템에 들어온 모든 프로세스가 처음 들어가는 큐
2. 준비 큐: Ready Queue: CPU 할당을 기다리는 프로세스들이 대기
3. 대기 큐: Waiting/Device Queue (I/O Queue): I/O 작업이 끝나기를 기다리는 프로세스들이 대기

요약

• OS는 여러 개의 큐를 관리
• 각 프로세스는 현재 상태에 따라 큐 사이를 이동함 (예: Ready → Running → I/O → Ready).
• 스케줄러가 Ready Queue에서 하나를 꺼내 CPU에 할당함.

(3) 선점형 vs. 비선점형 스케줄링

한 프로세스 실행 도중, 다른 급한 프로세스가 실행되어야 한다면?

• OK. 상황 봐서. \(\rightarrow\) 선점형
• NO. 무조건 대기. \(\rightarrow\) 비선점형

선점형 vs. 비선점형

• 선점형:
  • (장) 프로세스에 자원을 고루 할당 가능
  • (단) 문맥 교환 과정의 오버헤드
• 비선점형:
  • (장) 고르지 않은 자원 분배
  • (단) 문맥 교환 과정에서의 오버헤드 적음

(4) CPU 스케줄링 알고리즘

a) FIFO 스케줄링

• 먼저 요청한 프로세스 부터
• 비선점형
• 부작용: 호위 효과 (convoy effect)

b) SJF 스케줄링

• 최단 작업 우선 (Shortest Job First) 스케줄링
• CPU 이용 시간이 짧은 프로세스부터 실행
• 효과: 호위효과 방지

c) Round Robin 스케줄링

• FIFO + 타임 슬라이스
  • FIFO처럼 선착순이긴 하되, “타임 슬라이스”만큼만 실행!
• 선점형

d) SRT 스케줄링

• SJF + Round Robin
  • SJF처럼 짧은 프로세스부터 하되, “타임 슬라이스”만큼만 실행!

e) 우선순위 스케줄링

• 프로세스마다 “우선순위 부여”

  \(\rightarrow\) 우선 순위 높은 순으로 스케줄링

• 두 종류
  • (1) “최단 작업 우선” 스케줄링: 작업 시간 짧은 순으로
  • (2) “최소 잔여 시간” 스케줄링: 남은 작업 시간 짧은 순으로
• 문제점: 아사 현상 (starvation)
  • 우선 순위 낮은것은, 한없이 계속 연기됨…ㅠㅠ
• 해결책: 에이징 (aging)
  • 대기 시간이 길어질 수록, 우선순위를 높여줌

f) 다단계 큐 스케줄링

• 우선 순위별로 준비 큐를 여러개 사용
  • 우선순위가 높은 프로세스 처리
  • 다음으로 우선순위 높은 프로세스 처리
  • 다음으로 우선순위 높은 프로세스 처리
  • …
• 프로세스 유형 별로 큐 구분 가능
  • e.g., CPU 바운드, I/O 바운드, ..
• 큐 별로 다른 스케줄링 알고리즘 적용 가능
  • 큐 1) FIFO 큐
  • 큐 2) Round Robin
  • ..
• 큐 별로 다른 타임살리으스도 적용 가능
• 기본적으로 프로세스는, 큐 간의 이동 불가능!

g) 다단계 피드백 큐 스케줄링

• 프로세스가 큐 간의 이동 가능

• 높은 우선 순위 큐에 삽입

  (실행이 끝나지 않을 경우, 낮은 우선순위 큐에 삽입)

• 에이징 사용
• CPU bound, I/O bound 프로세스 구분 가능