CPU 스케줄링

CPU 스케줄링

CPU는 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행. 이 때 어떤 프로세스를 다음에 처리할 지 선택하는 알고리즘을 CPU 스케줄링 알고리즘이라고 한다. 따라서 상황에 맞게 CPU를 어떤 프로세스에 배정하여 효율적으로 처리하는가가 관건이다.

Preemtive(선점) vs Non-Preemptive

1. Preemtive(선점)
   • 하나의 프로세스가 CPU를 차지하고 있을 떄, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식
   • SRT(Shortest Remaining Time First), 라운드 로빈(Round Robin), 다단계 큐(Multi Level Queue), 다단계 피드백 큐(Multi Level Feedback Queue)
2. Non-Preemptive(비선점)
   • 한 프로세스가 CPU를 점유했다면 I/O나 인터럽트 발생 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못함.

Preemtive(선점형) 스케줄링

1. SRT(Shortest Remaining Time) 스케줄링
   • 가장 짧은 시간이 소요되는 프로세스를 먼저 수행.
2. 라운드 로빈
   • 시분할 시스템의 성질을 활용.
   • 프로세스는 같은 크기의 CPU 시간을 할당. 프로세스가 할당된 시간 내에 처리 완료를 못하면 준비 큐 리스트의 가장 뒤로 보내지고, CPU는 대기 중인 다음 프로세스로 넘어감.
3. 다단계 큐(Multi Level Queue)
   • 프로세스를 그룹으로 나누어, 각 그룹에 따라 Ready Queue(준비 큐)를 여러 개 두며, 다른 큐마다 다른 규칙을 지정할 수 있다. (독자적인 스케줄링)
4. 다단계 피드백 큐(Multi Level Feedback Queue)
   • 프로세스의 특성에 따라 그룹을 나누어, 큐마다 서로 다른 CPU 시간 할당량을 부여. 새로운 프로세스는 높은 우선순위, 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동하고, 마지막 단계는 라운드 로빈 방식을 적용.
   • 다단계 큐와 다른 점: 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점.
   • 요즘 상용 운영체제

None-Preemtive(비선점형) 스케줄링

1. FCFS(First Come First Service)
2. SJF(Shortest Job First)
   • 수학적으로 평균 대기 시간이 제일 짧다. (Average Waiting Time). 하지만 실제 환경에서는 프로세스의 CPU 점유시간(Burst time)을 알 수 없다.
   • starvation 현상
3. Priority(우선순위)
   • 우선 순위에 따라 CPU 할당. 선점, 비선점 둘 다 활용.
   • 동일 순위는 FCFS
   • Starvation 문제. aging으로 해결(ready queue에서 기다리는 동안 일정 시간이 지나면 우선 순위를 일정량 높여줌)
4. HRN(Highest Response Ration Next)
   • SJF의 약점인 starvation현상을 보완.
   • 대기 중인 프로세스 중 대기시간이 긴 프로세스의 경우 우선순위가 높아지게 하여 우선순위를 결정하는 스케줄링 기법
   • 우선순위 = (대기시간 + 서비스 시간)/ 서비스 시간
   • 더 높은 값대로 우선순위를 고려

스케줄러의 종류

• 스케줄러
  • 작업 큐(Job queue) : 현재 시스템 내의 모든 프로세스의 집합
  • 준비 큐(Ready queue): 현재 메모리 내에 있으면서 CPU를 할당받고 실행되기 위해 기다리는 프로세스의 집합
  • 장치 큐(Device queue): 각각의 장치마다 서비스를 기다리며 줄 서있는 프로세스의 집합

• 장기 스케줄러(Long-term Scheduler)
  • 많은 프로세스들이 메모리에 한꺼번에 올라올 경우, 대용량 메모리(디스크)에 임시로 저장한다. 이 디스크 내에 저장되어 있는 프로세스 중 어떤 순서로 프로세스를 메모리에 적재할지 결정한다.
  • 메모리와 디스크 사이의 스케줄링을 담당한다. 상대적으로 호출되는 빈도가 적다.
  • 디스크와 같은 저장 장치에 작업들을 저장해 놓고 필요할 때 실행할 작업을 Job queue에서 꺼내 Ready Queue를 통해서 메인 메모리에 적재한다.
  • 프로세스의 상태
    • 시작상태(New) → 준비 상태(Ready)
    • Running(or Ready) → Terminated
• 단기 스케줄러(Short-term Scheduler)
  • CPU와 메모리 사이의 스케줄링을 담당. 장기 스케줄러에 비해 매우 많이 호출됨.
  • Ready Queue에 있는 프로세스 중 먼저 도착한 프로세스에게 CPU를 할당.
  • 스케줄링 시간이 지연되면 안되기 떄문에, 장기 스케줄러에 비해 실행되는 시간도 매우 짧다.
• 중기 스케줄러
  • 시분할 시스템에서 추가로 사용하며, 메모리에 대한 가중을 완화시킴
  • 메모리에 너무 많은 프로세스가 적재되어 CPU를 차지하기 위한 경쟁이 심해질 때, 우선순위가 낮은 프로세스들을 잠시 제거한 뒤(디스크로 swap-out), 나중에 경쟁이 완화되었을 때 다시 디스크에서 메모리에 적재시킨다(Swapping) → Swapping 기법
  • 프로세스의 상태 : ready → suspended(메모리에서 디스크로 나간 상태)
  • Unix나 Window에서는 장기스케줄러가 거의 사용되지 않음 → 중기 스케줄러 사용

참고자료

https://github.com/JaeYeopHan/Interview_Question_for_Beginner
https://github.com/WooVictory/Ready-For-Tech-Interview
https://technote-mezza.tistory.com/70