강의/운영체제-반효경

[운영체제] CPU Scheduling

JJJaewon 2024. 2. 17. 22:52
반응형

CPU Scheduling

  • CPU Burst
    • CPU를 사용하는 단계
  • I/O Burst
    • I/O 작업하는 단계
  • CPU bound job : CPU를 많이 사용하는 작업
  • I/O bound job : I/O를 많이 사용하는 작업
  • CPU 스케줄링이 필요한 이유
    • I/O 가 CPU 사이에 자주 끼기 때문

CPU Scheduler와 디스패처

  • 스케줄러 : ready 상태 프로세스 중 CPU를 줄 프로세스를 고름
  • 디스패처 : CPU 의 제어권을 스케줄러로부터 선택된 프로세스에게 넘김
    • 이 과정을 context switch라고 함
  • CPU 스케줄링 언제 필요?
    • Running → Blocked (I/O)
    • Running → Ready (할당 시간 만료 timer interrupt)
    • Blocked → Ready (I/O 완료 후 인터럽트)
    • Terminate

비선점, 선점으로 크게 두가지 분류를 할 수 있음

성능 척도 (Scheduling Criteria)

  • 어떤 알고리즘이 좋은지 판별하기 위한 척도
  • 시스템 입장
    • CPU utilization (이용률) : 전체 시간 중에 CPU가 놀지 않고 일한 비율
    • Throughput (처리량) : 단위 시간 당 몇개의 작업을 완료했나
  • 프로그램 입장 (고객 입장)
    • Turnaround time (소요 시간, 반환 시간) : CPU 쓰러 들어와서 다쓰고 나갈 때가지 걸린 시간 (대기 시간 포함)
    • Waiting time (대기 시간) : CPU를 쓰기 위해 기다린 시간
    • Response time (응답 시간) : 레디 큐에 들어와서 처음으로 CPU를 얻기까지 걸린 시간

FCFS (First-Come-First-Served)

  • 비선점
  • 먼저 온게 먼저
  • 앞에 어떤 프로세스가 버티냐에 따라 상당히 다른 퍼포먼스
  • 긴 프로세스 떄문에 짦은 프로세스가 많이 대기하는 것 → Convoy effect

SJF (Shortest-Job-First)

  • 비선점, 선점 두가지 버전 존재 (선점은 SRJF)
  • CPU burst time이 가장 짧은 프로세스에게 할당
  • 평균 대기 시간이 가장 짧음 (선점형의 경우)
  • 문제점
    • Starvation : 긴 프로세스는 계속 CPU 할당을 못받음
    • CPU 사용 시간을 미리 알수 없음
      • 추정을 통해서 해결 → 과거의 CPU burst time을 이용하여 추정

Priority Scheduling

  • 우선순위 높은 프로세스에게 CPU 할당
  • 선점, 비선점 두가지 다 가능
  • SJF 도 일종의 priority scheduling
  • 문제
    • 기아 현상
  • Solution
    • aging : 오래 기다리면 우선순위를 조금씩 높여주는 것

Round Robin (RR)

  • 각 프로세스에 동일한 크기의 할당 시간(time quantum)을 줌
  • 보통 10 ~ 100 밀리세컨드
  • 할당 시간이 끝나면 선점되고 큐의 맨뒤로
  • 응답 시간이 좋음
  • 어떤 프로세스도 (n - 1)q time unit 이상 기다리지 않는다
  • 성능
    • q 가 크면 → FCFS와 다를게 없음
    • q 가 작으면 → context switch 오버헤드 높음

Multilevel Queue

  • 레디 큐가 여러개
  • 위로 갈수록 우선순위 높음
    • 시스템 프로세스
    • interactive 프로세스
    • interactive editing process
    • batch process
    • student process
  • foreground (interactive)
  • background (batch - no human interaction)
  • 각 큐마다 독립적인 스케줄링 알고리즘 가짐
    • foreground - RR
    • background - FCFS
  • 큐끼리의 스케줄링도 필요
    • 고정 우선순위 스케줄링
      • foreground 다 끝나면 background
      • 기아 현상 야기
    • 타임 슬라이스
      • 각 큐에 CPU time 적절 비율로 할당

Multilevel Feedback Queue

  • 프로세스가 다른 큐로 이동 가능
  • aging을 구현하는 하나의 방법
  • 상위 큐일수록 퀀텀이 짧음 → 맨 아래는 FCFS
  • 처음 프로세스는 우선순위 가장 높음
  • 다 끝내지 못할 시 하나씩 강등됨

Multiple-processor scheduling

  • CPU가 여러 개인 경우의 스케줄링
  • Homogeneous processor
    • queue에 한줄로 세워서 각 프로세서가 알아서 꺼내감
    • 반드시 특정 프로세서에서 수행되어야하는 작업의 경우 문제가 복잡해짐
  • Load sharing
    • 일부 프로세서에 쏠리지 않도록 부하 공유하는 메커니즘
    • 별개 큐 vs 공동 큐
  • Symmetric Multiprocessing (SMP)
    • 각 프로세서가 각자 알아서 스케줄링
  • Assymmetric multiprocessing
    • 하나의 프로세서가 시스템 데이터 접근, 공유 책임지고 나머지 프로세서는 이를 따름

Real-Time Scheduling

  • hard real-time system
    • 정해진 시간 안에 반드시 끝내도록 스케줄링해야함
  • soft real-time system
    • 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
    • 데드라인 완전 엄수까지는 아님

Thread Scheduling

  • Local Scheduling
    • ULT 의 경우 사용자 수준의 스레드 라이브러리에 의해 어떤 스레드를 스케줄할지 결정
  • Global Scheduling
    • KLT의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
반응형