본 글은 인프런 강의를 바탕으로 정리한 개인 학습 기록입니다.
출처: <그림으로 쉽게 배우는 운영체제>

목차

1. CPU스케줄링 개요
2. 다중큐
3. 스케줄링 목표
4. FIFO
5. SJF
6. RR
7. MLFQ

1. CPU스케줄링 개요

---

1) 컴퓨터 자원

• 필수 장치
  • CPU
  • 메모리
• 주변 장치
  • 하드디스크
  • 키보드
  • 마우스 등

2) 프로세스와 스레드

• 프로그램을 실행하면 메모리에 프로세스가 생성됨
• 각 프로세스는 1개 이상의 스레드를 가짐
• 실제 실행은 스레드를 중심으로 이루어짐

3) CPU 스케줄링

• 운영체제가 프로세스나 스레드에 CPU를 할당하고 회수하는 작업
• 메모리에는 여러 프로세스가 있기 때문에 운영체제가 어떤 작업에 CPU를 줄지 결정해야 함

4) CPU Burst와 I/O Burst

• CPU Burst
  • CPU를 사용해 계산이나 명령 실행을 하는 구간
• I/O Burst
  • 입출력 작업을 수행하는 구간

5) CPU 스케줄러가 결정해야 하는 것

(1) 누구에게 CPU를 줄 것인가

• 동시에 많은 프로세스가 실행을 기다림
• 한 프로세스만 계속 실행하면 공정성 문제가 생김

(2) 얼마나 오래 CPU를 줄 것인가

• 시분할 방식에서는 CPU를 일정 시간만 할당함
• 시간이 끝나면 CPU를 회수하고 다른 프로세스에 넘김

2. 다중큐

---

1) 프로세스 상태 전이

• 프로세스가 생성되면 준비 상태로 이동함
• 준비 상태에서 CPU를 기다리다가 CPU 스케줄러에 의해 실행 상태가 됨
• 실행 중에는 다음과 같은 일이 일어남:
  • 시간이 다 되면 준비 상태로 돌아감
  • I/O 요청이 생기면 대기 상태로 감
  • 작업이 끝나면 완료 상태가 됨

2) 준비 큐

• 준비 상태의 프로세스들은 준비 큐에서 관리됨
• CPU를 할당받기 위해 기다리는 상태임
• 보통 FIFO 방식으로 관리함
• 우선순위에 따라 여러 개의 준비 큐로 나눌 수도 있음

3) 대기 큐

• 실행 중 I/O 요청이 발생하면 프로세스는 대기 큐로 이동함
• 대기 큐는 보통 I/O 종류별로 따로 관리됨
• 예:
  • 하드디스크 작업 → HDD 큐
• I/O가 끝나고 인터럽트가 발생하면 다시 준비 상태로 돌아감

4) 큐에 들어가는 것

• 큐에 들어가는 것은 프로세스 자체가 아니라 PCB
• 운영체제는 PCB를 통해 프로세스 상태와 정보를 관리함

5.) CPU 스케줄러의 역할

• 준비 큐에 있는 PCB들을 보고 어떤 프로세스를 실행할지 결정함
• 즉, CPU 스케줄러는 준비 상태의 프로세스들 중 하나를 골라 실행 상태로 바꿈

3. 스케줄링 목표

---

1) 리소스 사용률

• CPU나 I/O 장치가 놀지 않도록 최대한 활용하는 것
• 자원을 효율적으로 쓰는 것이 목표임

2) 오버헤드 최소화

• 스케줄링 자체에 너무 많은 계산이 들면 비효율적임
• 컨텍스트 스위칭이 너무 자주 일어나도 손해
• 따라서 스케줄링 비용을 줄이는 것이 중요함

3) 공평성

• 특정 프로세스만 계속 CPU를 쓰지 않도록 해야 함
• 여러 프로세스에 공정하게 자원을 나누는 것이 목표임
• 다만 공평성의 기준은 시스템에 따라 달라질 수 있음

4) 처리량

• 같은 시간 안에 더 많은 작업을 끝내는 것
• 작업 수를 최대한 많이 처리하는 것이 목표임

5) 대기 시간

• 프로세스가 요청한 뒤 실제로 실행될 때까지 기다리는 시간
• 이 시간을 줄이는 것이 중요함

6) 응답 시간

• 사용자의 요청에 얼마나 빨리 반응하는지
• 특히 대화형 시스템에서 중요함

목표 간 트레이드오프

• 모든 목표를 동시에 최고로 만족시키기는 어려움
• 대표적인 예:
  • 처리량을 높이려면 한 프로세스에 CPU를 오래 주는 편이 유리함
  • 응답 시간을 줄이려면 여러 프로세스에 CPU를 짧게 자주 나눠줘야 함
• 그래서 두 목표는 서로 충돌할 수 있음

시스템별 우선순위

• 빠른 반응이 중요한 시스템
  • 응답 시간을 더 중요하게 봄
• 대량 계산 중심 시스템
  • 처리량을 더 중요하게 봄
• 일반 사용자용 운영체제
  • 여러 목표 사이의 균형이 중요함

4. FIFO

---

1) FIFO(First In First Out)(FCFS)

• 먼저 도착한 프로세스를 먼저 실행하는 방식
• 줄을 선 순서대로 처리하는 것과 같음
• 한 프로세스가 시작하면 끝날 때까지 계속 실행
• 즉, 비선점 방식임

2) 장점

• 구조가 단순하고 이해하기 쉬움
• 구현이 쉬움
• 도착 순서를 그대로 따르므로 직관적임

3) 단점

• 긴 작업이 앞에 오면 뒤에 있는 짧은 작업도 오래 기다려야 함
• 그래서 평균 대기시간이 커질 수 있음
• I/O 작업 때문에 앞 프로세스가 멈춰 있으면 CPU가 비효율적으로 놀 수 있음

4) 평균 대기시간

• 각 프로세스가 실행되기 전까지 기다린 시간의 평균
• 스케줄링 성능을 판단하는 중요한 기준 중 하나임

5) 예시

도착 순서대로 실행

• P1 = 25초, P2 = 5초, P3 = 4초

• 대기시간

  • P1: 0초
  • P2: 25초
  • P3: 30초

• 평균 대기시간

  • ((0 + 25 + 30) / 3 = 18.3초)

짧은 작업부터 실행

• 실행 순서: P3 → P2 → P1

• 대기시간

  • P3: 0초
  • P2: 4초
  • P1: 9초

• 평균 대기시간

  • ((0 + 4 + 9) / 3 = 4.3초)

6) 의미

• 같은 프로세스들이 있어도 실행 순서에 따라 평균 대기시간이 크게 달라질 수 있음
• FIFO는 도착 순서만 따르기 때문에 이런 비효율이 생길 수 있음

5. SJF

---

1) SJF(Shortest Job First)

• CPU burst time이 짧은 프로세스를 먼저 실행하는 방식
• 실행 시간이 짧은 작업을 먼저 처리해서 전체 대기 시간을 줄이려는 아이디어

2) 장점

• 평균 대기 시간이 줄어들 수 있음
• FIFO보다 성능이 더 좋아질 수 있음
• 이론적으로는 효율적인 방식으로 평가됨

3) 한계 1: 실행 시간 예측이 어려움

• 프로세스가 실제로 얼마나 오래 실행될지 미리 알기 어려움
• 프로그램은 사용자 행동이나 작업 내용에 따라 실행 시간이 달라질 수 있음
• 그래서 어떤 작업이 짧은 작업인지 정확히 판단하기 어려움

4) 한계 2: 기아 문제

• 짧은 작업이 계속 들어오면 긴 작업은 계속 뒤로 밀릴 수 있음
• 이 경우 긴 작업이 아주 오랫동안 실행되지 못할 수 있음
• 이런 현상을 기아(starvation) 라고 함

5) 의미

• SJF는 평균 대기 시간 관점에서는 매우 좋아 보이지만
• 실제 시스템에서는 예측 문제와 공정성 문제 때문에 사용이 어려움

6. RR

---

1) 라운드 로빈(Round Robin)

• 각 프로세스에 정해진 시간만큼만 CPU를 할당하는 방식
• 시간이 끝나면 현재 프로세스를 선점
• 해당 프로세스는 준비 큐 맨 뒤로 이동함
• 다음 프로세스가 CPU를 이어받음

2) RR의 특징

• 선점형 스케줄링 방식임
• 모든 프로세스가 번갈아 CPU를 받기 때문에 응답성이 좋고 공평성도 비교적 높음
• 특히 대화형 시스템에 적합함

3) 예시

• 프로세스:
  • P1 = 25초
  • P2 = 4초
  • P3 = 10초
• 타임 슬라이스:
  • 10초

실행 흐름

P1 실행 → 10초 사용 → 선점 → 잔여 15초
P2 실행 → 4초 사용 → 종료
P3 실행 → 10초 사용 → 종료
P1 다시 실행 → 10초 사용 → 잔여 5초
P1 마지막 실행 → 5초 사용 → 종료

대기시간

• P1: 0초 + 14초 + 0초
• P2: 10초
• P3: 14초

평균 대기시간

• 전체 합: 38초
• 평균: 38 / 3 = 12.67초

4) RR의 장점

• FIFO보다 응답성이 좋음
• 긴 작업이 CPU를 독점하지 못함
• 여러 작업이 동시에 실행되는 것처럼 보이게 할 수 있음

5) RR의 단점

• 컨텍스트 스위칭이 자주 발생함
• 프로세스 전환 비용이 누적되면 성능이 떨어질 수 있음
• 평균 대기시간만 비슷하다면 오히려 FIFO보다 비효율적일 수 있음 (컨텍스트 스위칭 시간 추가)

6) 타임 슬라이스가 클 때

• 선점이 거의 일어나지 않음
• 결국 FIFO처럼 동작하게 됨
• 사용자 입장에서는 반응성이 떨어질 수 있음

7) 타임 슬라이스가 작을 때

• 여러 프로세스가 더 자주 번갈아 실행됨
• 반응성은 좋아질 수 있음
• 하지만 컨텍스트 스위칭이 너무 많아져 오버헤드가 커짐

8) 의미

• 타임 슬라이스는 너무 커도 문제이고 너무 작아도 문제임
• 따라서 RR은 반응성과 오버헤드 사이에서 적절한 균형이 중요함 (타임 슬라이스를 최대한 크게 하면서 안 끊기게)

7. MLFQ

---

1) 왜 MLFQ(Multi Level Feedback Queue)가 필요한가

• 라운드 로빈은 타임 슬라이스 크기에 따라 문제가 생김
• 타임 슬라이스가 크면
  • I/O-bound 프로세스의 응답이 느려짐
• 타임 슬라이스가 작으면
  • 컨텍스트 스위칭이 자주 일어나 오버헤드가 커짐
• 그래서 두 문제를 함께 줄일 방법이 필요함

2) 프로세스 종류

• CPU-bound 프로세스

  • CPU 연산 비중이 큼
  • 처리량과 CPU 사용률이 중요함

• I/O-bound 프로세스

  • I/O 대기 비중이 큼
  • 빠른 응답 속도가 중요함

3) MLFQ의 기본 아이디어

• 우선순위가 높은 큐에는 짧은 타임 슬라이스
• 우선순위가 낮은 큐에는 긴 타임 슬라이스
• 처음에는 프로세스를 높은 우선순위 큐에서 실행함
• 실행 결과에 따라 큐를 이동시킴

4) 프로세스 이동 기준

• 타임 슬라이스를 끝까지 다 쓰면
  • CPU를 오래 쓰는 프로세스로 판단
  • 더 낮은 우선순위 큐로 이동
• 중간에 스스로 CPU를 반납하면
  • I/O 요청 가능성이 높음
  • 높은 우선순위를 유지할 가능성이 큼

5) 효과

• I/O-bound 프로세스

  • 높은 우선순위 큐에서 자주 CPU를 받아
  • 응답성이 좋아짐

• CPU-bound 프로세스

  • 아래 큐로 내려가면서 더 긴 타임 슬라이스를 받음
  • 컨텍스트 스위칭 오버헤드가 줄어듦