CS

[운영체제]프로세스 스케줄링

그레고리력 2021. 7. 9. 20:12

스케줄러


프로세스를 스케줄링하기 위한 Queue 종류

  • Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합
  • Ready Queue : 현재 메모리 내에 있으면서 CPU에 할당되어 실행되기를 기다리는 프로세스의 집합
  • Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합

스케줄러 종류

장기스케줄러(Long-term scheduler or job scheduler)

  • 대용량 메모리(하드디스크, SSD)에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue 로 보낼지 결정
  • 메모리와 디스크 사이의 스케줄링을 담당

단기스케줄러(Short-term scheduler or CPU scheduler)

  • CPU 와 메모리 사이의 스케줄링을 담당
  • Ready Queue 에 존재하는 프로세스 중 어떤 프로세스를 동작 시킬지 결정
  • 프로세스에 CPU 를 할당(scheduler dispatch)

중기스케줄러(Medium-term scheduler or Swapper)

  • 프로세스를 통째로 메모리에서 디스크로 쫓아냄 (swapping)
  • 프로세스에게서 memory 를 deallocate
  • 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러.
  • 프로세스의 상태(ready -> suspended)

CPU 스케줄러(Ready Queue 에 있는 프로세스)


FCFS(First Come First Served)

  • 비선점형(Non-Preemptive) 스케줄링(할당되었던 CPU 가 반환될 때만 스케줄링이 이루어짐)
  • convoy effect(소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮춤)

SJF(Shortest Job First)

  • CPU burst time 이 짧은 프로세스에게 CPU 우선 할당
  • 비선점형(Non-Preemptive) 스케줄링
  • starvation(사용 시간이 긴 프로세스는 거의 영원히 CPU 를 할당받을 수 없음)

SRTF(Shortest Remaining Time First)

  • 새로운 프로세스가 도착할 때마다 새로운 스케줄링
  • 선점형 (Preemptive) 스케줄링
  • 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다
  • starvation(새로운 프로세스가 도달할 때마다 스케줄링을 다시해 CPU 사용시간을 측정할 수가 없음)

Priority Scheduling

  • 우선순위가 가장 높은 프로세스에게 CPU 를 할당
  • 선점형 스케줄링(Preemptive) 방식, 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점
  • 비선점형 스케줄링(Non-Preemptive) 방식, 더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 앞에 넣음
  • starvation, 무기한 봉쇄(Indefinite blocking)
  • 해결책 :aging(아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여줌)

Round Robin

  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 부여
  • 할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다
  • CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
  • 공정한 스케줄링
  • 설정한 할당시간이 너무 커지면 FCFS와 같고 너무 작아지면 잦은 context switch 로 overhead 가 발생