Baymax

열심히 화이팅

2 분 소요

1. 스케줄링 기본 개념

💡 면접 대비: CPU 스케줄링의 목적과 기준은 OS 면접의 필수 주제입니다.

1.1 Queueing model

  • 서버-요청 모델
    • CPU-프로세스
    • 디스크-I/O
    • 프린터-작업

1.2 선점형 vs 비선점형 서버

  • 비선점형(Nonpreemptible)
    • 비선점 스케줄링만 허용
    • 예: 디스크, 프린터
  • 선점형(Preemptible)
    • 선점/비선점 스케줄링 모두 허용
    • 예: CPU

2. CPU 스케줄링 기준

2.1 스케줄링 기준

  1. CPU 중심 (시스템)
    • CPU 이용률: CPU를 최대한 바쁘게 유지
    • 처리량: 단위 시간당 완료되는 프로세스 수
  2. 프로세스 중심 (사용자)
    • 반환 시간: 특정 프로세스 실행에 걸리는 시간
    • 대기 시간: ready 큐에서 대기한 시간
    • 응답 시간: 요청 제출부터 첫 응답까지의 시간

2.2 최적화 기준

  • 최대화: CPU 이용률, 처리량
  • 최소화: 반환 시간, 대기 시간, 응답 시간

3. 프로세스 동작 특성

💡 면접 대비: CPU-bound와 I/O-bound 프로세스의 특징과 차이점을 이해하는 것이 중요합니다.

3.1 CPU-I/O 사이클

  • 프로세스는 CPU 사용과 I/O를 반복적으로 수행
  • CPU burst와 I/O burst의 반복
  • CPU-bound 프로세스는 I/O-bound 프로세스보다 긴 CPU burst

CPUIO

4. 스케줄링 알고리즘

4.1 FCFS (First-Come First-Served)

💡 면접 대비: 가장 기본적인 스케줄링 알고리즘으로, convoy effect를 설명할 수 있어야 합니다.

  • 원리: 가장 오래 대기한 프로세스 선택

  • 특징: 비선점형

  • 문제점
    • CPU 독점 가능성
    • CPU-bound 프로세스 선호
    • I/O 장치 활용도 저하

  • 예시

    • Process Burst Time
      P1 24
      P2 3
      P3 3

      P1, P2, P3 순서로 도착

      fcfs1

      Waiting time for P1 = 0; P2 = 24; P3 = 27
      Average waiting time: (0 + 24 + 27)/3 = 17

      P2, P3, P1 순서로 도착

      fcfs2

      Waiting time for P1 = 6; P2 = 0; P3 = 3
      Average waiting time: (6 + 0 + 3)/3 = 3

      이전 케이스보다 좋음.

4.2 Round Robin (RR)

  • 원리: FCFS + 시간 할당량
  • 특징
    • 시분할 환경에 적합
    • 문맥 교환 오버헤드 발생
  • 시간 할당량 설정
    • 문맥 교환 시간보다 충분히 커야 함
    • 일반적인 상호작용보다 커야 함

  • 예시

    • Process Burst Time
      P1 53
      P2 17
      P3 68
      P4 24

      RR

4.3 SJF (Shortest Job First)

💡 면접 대비: 평균 대기 시간 관점에서 최적이지만, 실제 구현의 어려움을 설명할 수 있어야 합니다.

  • 원리: 가장 짧은 CPU burst 시간 예측

  • 유형
    • 비선점형 SJF
    • 선점형 SJF (SRTF: Shortest Remaining Time First)
  • 특징
    • 최적의 평균 대기 시간
    • CPU burst 예측의 어려움
    • 기아 현상 가능성

  • 예시

    • Process Arrival Time Burst Time
      P1 0.0 7
      P2 2.0 4
      P3 4.0 1
      P4 5.0 4

      SJF

4.4 다단계 큐 스케줄링 (Multilevel Queue)

  • 원리: 여러 개의 준비 큐를 다른 알고리즘으로 스케줄링
  • 특징
    • 각 큐마다 다른 스케줄링 알고리즘
    • 큐 간 스케줄링 필요

4.5 다단계 피드백 큐 (MLFQ)

💡 MLFQ는 현대 OS에서 가장 널리 사용되는 스케줄링 방식입니다.

  • 원리
    • 프로세스가 큐 간 이동 가능
    • 동적 우선순위
    • 우선순위 큐들로 구성

5. 현대 운영체제의 스케줄링

5.1 Linux 스케줄링

  • 특징
    • 우선순위 기반, 시분할, 선점형
    • POSIX.4 호환
    • 실시간 및 일반 프로세스 지원
  • 스케줄링 정책
    • SCHED_FIFO: 고정 우선순위 실시간
    • SCHED_RR: 시간 할당량이 있는 실시간
    • SCHED_OTHER: 일반 프로세스

5.2 Windows 스케줄링

  • 32단계 우선순위
    • 실시간 우선순위 (16-31)
    • 가변 우선순위 (1-15)
  • 5개 우선순위 클래스
    • High-priority-class
    • Above-normal-priority-class
    • Normal-priority-class
    • Below-normal-priority-class
    • Idle-priority-class

6. 스케줄링 알고리즘 평가

6.1 평가 방법

  1. 결정적 모델링
    • 미리 정의된 작업부하 사용
    • 간단하고 빠름
    • 너무 구체적
  2. 큐잉 모델
    • 수학적 분석
    • 통계적 접근
  3. 시뮬레이션 분석
    • 실제 시스템 추적 데이터 사용
    • 가장 현실적인 평가 방법

참고 자료

  • Operating System Concepts (10th Edition)
  • Understanding the Linux Kernel
  • Windows Internals (7th Edition)

댓글남기기

참고